Academic literature on the topic 'Codes quasi-cycliques'

Dans cette thèse, nous abordons tout d'abord le problème de reconnaissance de codes. Il consiste à retrouver la structure d'un code correcteur d'erreurs utilisé lors d'une transmission de données seulement à partir de la séquence bruitée interceptée. Nous donnons ici des méthodes efficaces pour la reconnaissance d'un code connu, pour la reconstruction de codes appartenant à une famille tels que les codes cycliques et pour la détection des paramètres de codes convolutifs. Ensuite, nous étudions la structure des codes quasi-cycliques parallèlement aux résultats connus pour les codes cycliques. Nous donnons une construction d'une sous-famille de codes quasi-cycliques annulés par un polynôme à coefficients matriciels. Cette construction permet de trouver des codes ayant de bonnes distances minimales. Finalement, nous nous intéressons aux permutations laissant invariante la quasi-cyclicité d'un code<br>In this thesis, we first deal with the problem of recognition of codes. It consists in recovering the structure of an error-correcting code used during a data transmission only from the noisy intercepted sequence. We give efficient methods for the recognition of a known code, for the reconstruction of codes belonging to a family like cyclic codes and for the detection of parameters of convolutional codes. Then, we study the structure of quasi-cyclic codes in parallel of the results known for cyclic codes. We give a construction of a sub-family of quasi-cyclic codes cancelled by a polynomial with matricial coefficients. Some of these codes reach large minimum distances. Finally, we deal with permutations keeping the quasi-cyclicity of a code

Nous donnons une borne de la distance minimale d'un code quasi-cyclique a un generateur. Nous donnons egalement des bornes sur les poids de certaines classes de codes quasi cycliques sur un corps fini, deduits de codes cycliques irreductibles sur une extension. En outre, nous caracterisons une classe de codes quasi cycliques sur un corps fini, qui sont demultiplies de codes quasi cycliques sur une extension, et particulierement, tous les codes quasi cycliques sur corps fini qui sont demultiplies de codes cycliques sur une extension

Au sein des codes correcteurs d'erreurs et de la Théorie de l'Information, les codes quasi-cycliques tiennent une place particulière. Ces codes de longueur finie généralisent les codes cycliques et approchent les codes de longueur infinie que sont les codes convolutifs. Les codes quasi-cycliques possèdent de plus d'excellents paramètres : ils ont une grande capacité de correction. Nous présentons deux approches algébriques différentes pour ces codes : l'approche constructive proposée par Ling San et Patrick Solé, qui ont généralisé la construction cubique en la construction quintique et la construction septique, et l'approche cyclique reprise par Kristine Lally. Les treillis sont des graphes qui permettent de représenter les codes correcteurs d'erreurs, dans le but de les décoder avec l'algorithme de Viterbi. Il existe deux types de treillis : les treillis conventionnels et les treillis cycliques. À chacun de ces types de treillis nous associons une construction graphique de codes quasi-cycliques qui correspond à l'une des deux approches algébriques présentées précédemment : Pour les treillis conventionnels, la construction graphique est une généralisation de la construction de G. D. Forney. Elle rejoint l'approche de S. Ling et P. Solé sous certaines conditions. Les treillis cycliques sont associés à la représentation cyclique de K. Lally. Ces treillis permettent de représenter les codes avec moins de sommets que les treillis conventionnels. Enfin, de nouveaux codes auto-duaux, entre autres des codes de paramètres [70,35,12] et [72, 36,12], sont construits à partir des constructions cubiques, quintiques et septiques et du logiciel Magma<br>Quasi-cyclic codes are block codes. They generalize cyclic codes and approximate convolutional codes. Moreover, quasi-cyclic codes are asymptotically good. Trellises are oriented labeled graphs, which represent block codes. Trellises could be conventional or tail-biting. We present two different algebraic approaches to quasi-cyclic codes. We associate the algebraic structure, which extends the cubic construction (a+x | b+x | a+b+x) into the quintic and the septic constructions, to the conventional trellises. The cyclic approach is associated to the tail-biting trellises. We introduce a graphical construction for quasi-cyclic codes; this construction is based on trellises. In the case of convolutional trellises, this construction is a generalization of the squared and cubing constructions proposed by G. D. Forney Jr. Some algebraic constructions of new self-dual binary codes are given. These new codes have parameters [70, 35, 12] or [72, 36, 12] or other. They are obtained with the cubic, the quintic or the septic construction and they are constructed with the computer language Magma

Le sujet porte sur une classe de codes correcteurs d erreurs dits codes cycliques tordus, et ses applications a l'Informatique quantique et aux codes quasi-cycliques. Les codes cycliques classiques ont une structure d'idéaux dans un anneau de polynômes. Ulmer a introduit en 2008 une généralisation aux anneaux dits de polynômes tordus, une classe d'anneaux non commutatifs introduits par Ore en 1933. Dans cette thèse on explore le cas du corps a quatre éléments et de l'anneau produit de deux copies du corps a deux éléments.

L’utilisation des codes MDPC (Moderate Density Parity Check) quasi-cycliques dans le cryptosystème de McEliece offre un schéma de chiffrement post-quantique dont les clés ont une taille raisonnable et dont le chiffrement et le déchiffrement n’utilisent que des opérations binaires. C’est donc un bon candidat pour l’implémentation embarquée ou à bas coût.Dans ce contexte, certaines informations peuvent être exploitées pour construire des attaques par canaux cachés.Ici, le déchiffrement consiste principalement à décoder un mot de code bruité. Le décodeur utilisé est itératif et probabiliste : le nombre d’itérations de l'algorithme varie en fonction des instances et certains décodages peuvent échouer. Ces comportements ne sont pas souhaitables car ils peuvent permettre d’extraire des informations sur le secret.Une contremesure possible est de limiter le nombre d’instances de chiffrement avec les mêmes clés. Une autre façon serait de recourir à un décodage à temps constant dont la probabilité d’échec au décodage est négligeable. L’enjeu principal de cette thèse est de fournir de nouveaux outils pour analyser du comportement du décodeur pour la cryptographie.Dans un second temps, nous expliquons pourquoi l'utilisation des codes polaires n'est pas sûre pour le cryptosystème de McEliece. Pour ce faire, nous utilisons de nouvelles techniques afin de résoudre une équivalence de codes. Nous exhibons de nombreux liens entre les codes polaires et les codes de Reed-Muller et ainsi d'introduire une nouvelle famille de codes : les codes monomiaux décroissants. Ces résultats sont donc aussi d'un intérêt indépendant pour la théorie des codes<br>Considering the McEliece cryptosystem using quasi-cylcic MDPC (Moderate Density Parity Check matrix) codes allows us to build a post-quantum encryption scheme with nice features. Namely, it has reasonable key sizes and both encryption and decryption are performed using binary operations. Thus, this scheme seems to be a good candidate for embedded and lightweight implementations. In this case, any information obtained through side channels can lead to an attack. In the McEliece cryptosystem, the decryption process essentially consists in decoding. As we consider the use of an iterative and probabilistic algorithm, the number of iterations needed to decode depends on the instance considered and some of it may fail to be decoded. These behaviors are not suitable because they may be used to extract information about the secrets. One countermeasure could be to bound the number of encryptions using the same key. Another solution could be to employ a constant time decoder with a negligible decoding failure probability, that is to say which is about the expected security level of the cryptosystem. The main goal of this thesis is to present new methods to analyse decoder behavior in a cryptographic context.Second, we explain why a McEliece encryption scheme based on polar code does not ensure the expected level of security. To do so, we apply new techniques to resolve the code equivalence problem. This allows us to highlight several common properties shared by Reed-Muller codes and polar codes. We introduce a new family of codes, named decreasing monomial codes, containing both Reed-Muller and polar codes. These results are also of independent interest for coding theory