Academic literature on the topic 'Code correcteur d'erreurs'

Dans cette thèse, nous étudions les canaux de communication dans un contexte non coopératif sous l'angle des codes correcteurs d 'erreurs, d'une part, et de la stéganographie, d'autre part. Nous prenons la place d'un observateur non légitime qui veut avoir accès à l'information échangée entre deux protagonistes. Nos travaux sur les algorithmes de reconstruction de codes correcteurs nous ont amenés à proposer un formalisme commun pour l'étude des codes linéaires, des codes convolutifs et des turbo-codes. Nous analysons tout d'abord finement l'algorithme de Sicot-Houcke, puis l'employons ensuite comme brique de base pour concevoir une technique de reconstruction des codes convolutifs totalement automatique et de complexité meilleure que les techniques existantes. Enfin, nous utilisons ces résultats pour retrouver les paramètres des turbo-codeurs. Dans le cadre de l'analyse stéganographique, nous proposons tout d'abord deux nouveaux modèles de sécurité qui mettent en oeuvre des jeux avec des attaquants réels. Nous adaptons ensuite l'analyse RS en un schéma de détection pour l'algorithme Multi Bit Plane Image steganography pour le domaine spatial proposé par Nguyen et al. à IWDW'06. Enfin, nous développons une approche nouvelle pour analyser les images JPEG. En étudiant les statistiques des coefficients DCT compressés, nous mettons en évidence des détecteurs possédant des performances élevées et indépendantes en pratique de la quantité d'information dissimulée. Nous illustrons ces résultats par un schéma de stéganalyse universelle d'une part, et un schéma de stéganalyse spécifique pour Outguess, F5 et JPHide and JPSeek, d'autre part.

Dans cette thèse, nous étudions les canaux de communication dans un contexte non coopératif sous l'angle des codes correcteurs d'erreurs, d'une part, et de la stéganographie, d'autre part. Nous prenons la place d'un observateur non légitime qui veut avoir accès à l'information échangée entre deux protagonistes. Nos travaux sur les algorithmes de reconstruction de codes correcteurs, nous ont amenés à proposer un formalisme commun pour l'étude des codes linéaires, des codes convolutifs et des turbo-codes. Nous analysons tout d'abord finement l'algorithme de Sicot-Houcke, puis l'employons ensuite comme brique de base pour concevoir une technique de reconstruction des codes convolutifs totalement automatique et de complexité meilleure que les techniques existantes. Enfin, nous utilisons ces résultats pour retrouver les paramètres des turbo-codeurs. Dans le cadre de l'analyse stéganographique, nous proposons tout d'abord deux nouveaux modèles de sécurité qui mettent en oeuvre des jeux avec des attaquants réels. Nous adaptons ensuite l'analyse RS en un schéma de détection pour l'algorithme Multi Bit Plane Image steganography pour le domaine spatial, proposé par Nguyen et al. à IWDW'06. Enfin, nous développons une approche nouvelle pour analyser les images JPEG. En étudiant les statistiques des coefficients DCT compressés, nous mettons en évidence des détecteurs possédant des performances élevées et indépendantes en pratique de la quantité d'information dissimulée. Nous illustrons ces résultats par un schéma de stéganalyse universelle d'une part, et un schéma de stéganalyse spécifique pour Outguess, F5 et JPHide and JPSeek, d'autre part.

Les codes correcteurs d'erreur et le problème lié de leur décodage constituent une des variantes envisagées en cryptographie post-quantique. De façon générale, un code aléatoire possède un groupe de permutations bien souvent trivial. Cependant, les codes impliqués dans la construction des cryptosystèmes et des fonctions cryptographiques basées sur les codes correcteurs possèdent généralement un groupe de permutations non-trivial. De plus, peu d'articles de cryptanalyse ne tiennent compte de l'information que représentent ces groupes de permutations. L'idée est donc d'utiliser le groupe de permutations des codes correcteurs afin d'améliorer les algorithmes de décodage. Il existe une multitude de façons de l'appliquer. La première à laquelle nous nous intéressons dans cette thèse est celle utilisant la permutation cyclique appelée “shift” sur du décodage par ensembles d'information. De cette façon, nous reprenons un travail initié par MacWilliams et y apportons une analyse précise de la complexité. Une autre façon est d'utiliser une permutation d'ordre deux afin de créer algébriquement un sous-code des codes de départ. Le décodage dans ce sous-codes, donc de paramètres plus petits, y est plus aisé et permet de récupérer de l'information pour effectuer le décodage dans le code de base. Pour terminer, nous étudions cette dernière technique sur les codes correcteurs bien connus que sont les codes de Reed-Muller permettant ainsi de prolonger les travaux lancés par Sidel'nikov-Pershakov<br>Error correcting codes and the linked decoding problem are one of the variants considered in post-quantum cryptography. In general, a random code has oftenly a trivial permutation group. However, the codes involved in the construction of cryptosystems and cryptographic functions based on error correcting codes usually have a non-trivial permutation group. Moreover, few cryptanalysis articles use the information contained in these permutation groups. We aim at improving decoding algorithms by using the permutation group of error correcting codes. There are many ways to apply it. The first one we focus on in this thesis is the one that uses the cyclic permutation called “shift” on information set decoding. Thus, we dwell on a work initiated by MacWilliams and put forward a detailed analysis of the complexity. The other way we investigate is to use a permutation of order two to create algebraically a subcode of the first code. Decoding in this subcode, of smaller parameters, is easier and allows to recover information in a perspective of decoding in the first code. Finally, we study the last pattern on the well known correcting codes, i. E. Reed-Muller codes, which extends the work initiated by Sidel'nikov-Pershakov

La transmission fiable de données sur un canal de transmission est un problème récurrent en Informatique. En effet, quel que soit le canal de transmission employé, on observe obligatoirement de la détérioration de l’information transmise, voire sa perte pure et simple. Afin de palier à ce problème, plusieurs solutions ont été apportées, notamment via l’emploi de codes correcteurs. Dans cette thèse, nous étudions un code correcteur développé en 2014 et 2015 pour l’entreprise Thales durant ma deuxième année de Master en apprentissage. Il s’agit d’un code actuellement utilisé par Thales pour fiabiliser une transmission UDP passant par un dispositif réseau, l’Elips-SD. L’Elips-SD est une diode réseau qu’on place sur une fibre optique et qui garantit physiquement que la transmission est unidirectionnelle. Le cas d’utilisation principal de cette diode est de permettre le suivi de la production d’un site sensible, ou encore de superviser son fonctionnement, tout en garantissant à ce site une protection face aux intrusions extérieures. A l’opposé, un autre cas d’utilisation est la transmission de données depuis un ou plusieurs sites non-sécurisés vers un site sécurisé, dont on souhaite s’assurer qu’aucune information ne pourra par la suite fuiter. Le code correcteur que nous étudions est un code correcteur linéaire pour le canal à effacements de paquets, qui a reçu la certification OTAN de la Direction Générale des Armées. Nous l’avons babtisé "Fauxtraut", anagramme de "Fast algorithm using Xor to repair altered unidirectionnal transmissions". Afin d’étudier ce code correcteur, de présenter son fonctionnement et ses performances, et les différentes modifications apportées durant cette thèse, nous établissons tout d’abord un état de l’art des codes correcteurs, en nous concentrant principalement sur les codes linéaires non-MDS, tels que les codes LDPC. Puis nous présentons le fonctionnement de Fauxtraut, et analysons son comportement (complexité, consommation mémoire, performances) par la théorie et par des simulations. Enfin, nous présenterons différentes versions de ce code correcteur développées durant cette thèse, qui aboutissent à d’autres cas d’utilisation, tels que la transmission d’information sur un canal unidirectionnel à erreurs ou sur un canal bidirectionnel, à l’image de ce que permet de faire le protocole H-ARQ. Dans cette partie, nous étudierons notamment le comportement de notre code correcteur via la théorie des graphes : calculer la probabilité de décoder convenablement ou non revient à connaître la probabilité d’apparition de cycles dans le sous-graphe de graphes particuliers, les graphes de Rook et les graphes bipartis complets. Le problème s’énonce simplement et s’avère compliqué, et nous espérons qu’il saura intéresser des chercheurs du domaine. Nous présentons une méthode permettant de calculer exactement cette probabilité pour de petits graphes (qui aboutit à un certain nombre de formules closes), et une fonction tendant asymptotiquement vers cette probabilité pour de plus grands graphes. Nous étudierons aussi la manière de paramétrer automatiquement notre code correcteur par le calcul modulaire et la combinatoire, utilisant la fonction de Landau, qui retourne un ensemble de nombres entiers dont la somme est fixée et le plus commun multiple est maximal. Dans une dernière partie, nous présentons un travail effectué durant cette thèse ayant conduit à une publication dans la revue Theoretical Computer Science. Il concerne un problème non-polynomial de la théorie des graphes : le couplage maximal dans les graphes temporels. Cet article propose notamment deux algorithmes de complexité polynomiale : un algorithme de 2-approximation et un algorithme de kernelisation pour ce problème. L’algorithme de 2- approximation peut notamment être utilisé de manière incrémentale : arêtes du flot de liens nous parviennent les unes après les autres, et on construit la 2-approximation au fur et à mesure de leur arrivée<br>Reliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them. In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed. The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs. In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm forthis problema