Academic literature on the topic 'Cryptographie à base de codes correcteurs'

Apres avoir rappele dans un premier chapitre les principales notions de codage et cryptographie, on donne un algorithme de chiffrement qui englobe les algorithmes de cryptographie standards utilisant des codes correcteurs d'erreurs (ceux de r. J. Mceliece (mc) et s. Harari (hal)), puis un cryptosysteme aleatoire avec feedback qui utilise un automate fini pour engendrer des permutations. Dans le chapitre suivant, une nouvelle famille de codes lineaires binaires correcteurs d'erreurs, dits en degrade, est introduite ; sa distance minimale est explicite et sa distribution de poids tend vers la loi normale. Ce nouveau code est utilise dans un cryptosysteme a clef secrete et revele un meilleur taux de transmission cryptographique que celui obtenu pour le systeme hal. Il a paru interessant d'analyser le comportement asymptotique de la distribution de poids d'un code en degrade couple avec un code simplexe, par la construction (u, u+v). Le resultat obtenu, par une methode non probabiliste, montre que le passage au code (u, u+v) ne modifie pas le comportement asymptotique de la distribution de poids. Enfin, dans un dernier chapitre, on developpe une notion de generateur aleatoire en temps polynomial, basee sur la theorie des automates et des chaines de markov, en utilisant les produits croises. En introduisant la notion de batterie de tests, il est alors possible de montrer que certains generateurs bases sur les chaines de markov fournissent de bons generateurs pseudo-aleatoires en temps polynomial

La cryptographie basée sur les codes correcteurs d’erreurs est un des domaines permettant de construire des cryptosystèmes post-quantiques, c’est à dire résistants à l’ordinateur quantique. Contrairement à la factorisation et au logarithme discret,qui sont les deux problèmes les plus utilisés à l’heure actuelle en cryptographie, aucun algorithme n’est connu pour résoudre le problème de décodage de codes correcteurs aléatoires en temps polynomial avec un ordinateur quantique.Dans cette thèse, on se concentre plus particulièrement sur la cryptographie basée sur la métrique rang, dans laquelle on étudie des codes correcteurs munis de la métrique rang plutôt que la métrique de Hamming. Cette métrique présente l’avantage de pouvoir construire des cryptosystèmes avec de plus petites tailles de clés, mais est moins mature que la métrique de Hamming. Nous présentons dans un premier temps deux nouveaux algorithmes de décodage en métrique rang : le premier est un algorithme combinatoire permettant de résoudre le problème de décodage dans le cas de codes aléatoires, et permet donc de mieux estimer la complexité des attaques. Le second est une amélioration de l’algorithme de décodage pour les codes Low Rank Parity Check (LRPC). Nous présentons ensuite deux cryptosystèmes basés sur les codes : un schéma de signature en métrique rang, Durandal, qui est une adaptation de l’approche de Schnorr-Lyubashevsky en métrique euclidienne, et une amélioration du schéma de chiffrement Hamming Quasi-Cyclic (HQC) en métrique de Hamming, pour lequel on propose une nouvelle analyse du taux d’échec de déchiffrement et l’utilisation d’une autre famille de codes correcteurs d’erreurs. Nous nous intéressons ensuite à deux adaptations de l’approche de Schnorr-Lyubashevsky, une en métrique de Hamming et l’autre en métrique rang, pour lesquelles on donne des cryptanalyses permettant de retrouver les clés publiques des schémas en utilisant la fuite d’information dans les signatures. Enfin nous présentons les choix effectués pour implémenter les cryptosystèmes en métrique rang dans la bibliothèque Rank-Based Cryptography (RBC)
Code-based cryptography is one of the fields allowing to build post-quantum cryptosystems, i.e secure against a quantum computer. Contrary to factorization and discrete logarithm, which are the two most used problems in cryptography right now, no algorithm is known to solve the decoding problem for random codes in polynomial time using a quantum computer. In this thesis, we focus on rank-based cryptography, in which we study codes based on the rank metric instead of the Hamming metric. This metric has the advantage of allowing to build cryptosystems with lower key sizes, but is less mature than the Hamming metric. Firstly, we present two new decoding algorithms in the rank metric : the first one is a combinatorial algorithm solving the decoding problem for random codes, hence allowing to better estimate the complexity of the attacks. The second one is an improvement of the decoding algorithm for Low Rank Parity Check (LRPC). We then present two code-based cryptosystems : a rank-based signature scheme which is an adaptation of the Schnorr-Lyubashevsky approach in the Euclidean metric, and an improvement of the Hamming Quasi-Cyclic (HQC) encryption scheme, for which we propose a new analysis of the decryption failure rate and the use of another family of error correcting codes. We then study two adaptations of the Schnorr-Lyubashevsky approach : one in the Hamming metric and the other one in the rank metric, for which we propose cryptanalysis allowing to recover secret keys using information leakage from the signatures. Finally we present the choices used to implement rank-based cryptosystems in the Rank-Based Cryptography (RBC) library

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art
Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art
Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art

Les bases de Gröbner constituent un outil important pour la résolution de systèmes d'équations algébriques, et leur calcul est souvent la partie difficile de la résolution. Cette thèse est consacrée à des analyses de complexité de calculs de bases de Gröbner pour des systèmes surdéterminés (le nombre m d'équations est supérieur au nombre n d'inconnues). Dans le cas générique (”aléatoire”), des outils existent pour analyser la complexité du calcul de base de Gröbner pour un système non surdéterminé (suites régulières, borne de Macaulay). Nous étendons ces résultats au cas surdéterminé, en définissant les suites semi-régulières et le degré de régularité dont nous donnons une analyse asymptotique précise. Par exemple dès que m > n nous gagnons un facteur 2 sur la borne de Macaulay, et un facteur 11,65 quand m = 2n (ces facteurs se répercutent sur l'exposant de la complexité globale). Nous déterminons la complexité de l'algorithme F5 (J-C. Faugère) de calcul de base de Gröbner. Ces résultats sont appliqués en protection de l'information, où les systèmes sont alors considérés modulo 2 : analyse de la complexité des attaques algébriques sur des cryptosystèmes, algorithmes de décodage des codes cycliques. Dans ce dernier cas, une remise en équation complète du problème conduit à utiliser des systèmes de dimension positive dont la résolution est de manière surprenante plus rapide. Nous obtenons ainsi un algorithme de décodage efficace de codes précédemment indécodables, permettant un décodage en liste et applicable à tout code cyclique.

La plupart des algorithmes de chiffrement à clé publique actuellement utilisés pour assurer la confidentialité et l'authenticité des télécommunication se fondent sur la difficulté de problèmes de théorie des nombres. Par exemple, la sécurité de RSA est fondé sur la difficulté calculatoire de factoriser un produit de grands nombres premiers. Mais en 1994, Shor a proposé un algorithme qui résout ce problème efficacement avec un ordinateur quantique. Les ordinateurs quantiques de grande taille n'existent pas encore, mais cela pourrait changer dans quelques décennies. Nous avons donc besoin de nouveau systèmes de chiffrement qui résistent aux attaques quantiques. En 2017, l'institut national des standards et technologies américain (NIST) a invité les chercheurs à soumettre des propositions pour standardiser de tels algorithmes. Une solution consiste à créer des cryptosystèmes fondés sur la difficulté de décoder des codes correcteurs d’erreurs. Une proportion significative des algorithmes proposés suite à l'appel du NIST utilise cette approche. Dans cette thèse, nous analysons différents cryptosystèmes post-quantiques fondés sur les codes correcteurs. D’abord, nous étudions les codes QC-MDPC et montrons que l’on peut retrouver la clé privée en observant le poids du syndrome ou le nombre d’itérations de l’algorithme de décodage. Ensuite, nous proposons des attaques qui exploitent la structure des cryptosystèmes Edon-K, RLCE et XGRS. Enfin, nous étudions la difficulté du problème du décodage générique dans le cas des codes ternaires, et en particulier avec une erreur de grand poids, comme dans la signature Wave
Today, most public-key cryptosystems used to ensure the privacy and authenticity of communications rely on the hardness of number theoretic problems. For instance, the security of the RSA algorithm is based on the fact that factoring a product of large prime numbers is computationally hard. However, in 1994, Shor proposed an algorithm to efficiently solve this problem using a quantum computer. Large-scale quantum computers do not exists yet, but this could change within the next decades. Therefore, we need new public-key cryptosystems that resist quantum attacks. This is known as post-quantum cryptography. In 2017, the American National Institute of Standards and Technologies (NIST) invited researchers to submit proposals for the standardisation of post-quantum cryptographic algorithms. One promising solution is to design cryptosystems based of the hardness of decoding error-correcting codes. A significant proportion of cryptosystems submitted to the NIST use this approach. In this thesis, we propose an analysis of different code-based post-quantum cryptosystems. First, we study the case of QC-MDPC codes and show that one can recover the private key by observing the syndrome weight or the number of iterations of the decoding algorithm. Then, we propose key-recovery attacks exploiting the structure of three cryptosystems: Edon-K, RLCE and XGRS. Finally, we study the hardness of the general decoding problem for ternary codes, in the large weight setting, which is used in the Wave signature scheme

Je traite du décodage de deux grandes familles de codes algébriques :
les codes cycliques binaires et les codes de Reed-Solomon sur un
alphabet $q$-aire (ainsi que les codes géométriques). En ce qui
concerne les codes cycliques, ceux-ci n'ont pas d'algorithme générique
de décodage, mis à part les codes BCH ou assimilés (bornes de
Hartman-Tzeng, de Roos). Au premier rang des codes intéressants pour
lesquels on ne connaît pas d'algorithme de décodage {\em générique}
figurent les {\em codes à résidus quadratiques}, qui ont de bons
paramètres. J'étudie une mise en équation du problème du décodage par
syndrôme de ces codes, que l'on peut résoudre avec des outils de base
de Gröbner. On obtient ainsi des algorithmes de décodage de complexité
raisonnable pour ces codes. Ces travaux ont fait l'objet d'une partie
de la thèse de Magali Bardet.


En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vus
comme des {\em codes d'évaluation}, et le problème de décodage associé
revient à approcher une fonction par des polynômes de base degré. De
grands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvé
un algorithme qui décode bien au delà des rayons classiques de
décodage, en relaxant l'hypothèse que la solution doit être unique. Je
propose d'améliorer certaines étapes de cet algorithme, en le rendant
plus rapide et déterministe (notamment en évitant une factorisation de
polynôme sur un corps fini), dans le cas des codes Reed-Solomon, et
dans le cas des codes géométriques. Ces travaux ont été effectués en
encadrant Lancelot Pecquet.

Du point de vue théorique, j'ai étudié des généralisations
multivariées, qui correspondent à certains codes: les codes produits
de Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bon
rayon de décodage, dans le cas des codes de petit taux. Dans le cas de
codes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sa
thèse sous ma direction, a produit et implanté un algorithme efficace,
plus que ceux basés sur l'algorithme de Guruswami-Sudan.



J'ai étudié les aspects négatifs du problème de décodage par syndrôme
des codes linéaires, et du décodage des codes de Reed-Solomon, quand
le nombre d'erreurs est élevé, en but d'application en cryptographie.
Dans le premier cas, j'ai construit une fonction de hachage
cryptographique à réduction de sécurité, c'est-à-dire que trouver une
faiblesse dans le fonction de hachage revient à résoudre un problème
réputé difficile de codage. J'ai aussi construit une nouvelle
primitive de chiffrement à clé publique, reposant sur la difficulté de
décoder les codes de Reed-Solomon.

Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar un
nouvel algorithme d'échange de clé multi-utilisateurs, fondé sur le
problème du logarithme discret. Raghav Bhaskar a fourni une preuve de
sécurité de ce protocole, pendant sa thèse sous ma direction. Nous
avons aussi étudié comment adapter ce protocole aux pertes de
messages, car notre protocole est un des seuls qui est robuste à ces
pertes.

Depuis une trentaine d’années, nous avons connaissance d’attaques ciblant des implantations de cryptosystèmes, exploitant des informations physiques telles que temps d’exécution. Il est donc naturel de se demander quelles menaces représentent ces attaques pour les implantations de schémas post-quantiques qui seront déployées dans l’industrie. Dans cette thèse, nous nous intéressons plus particulièrement à la résistance des algorithmes cryptographiques à base de codes correcteurs d’erreurs, vis à vis des attaques par canaux auxiliaires. Nous nous sommes focalisés sur deux schémas, ROLLO et BIKE, candidats au second tour de la standardisation post-quantique du NIST. Nous montrons à travers nos travaux que leur implantation en temps constant est notamment vulnérable aux attaques par analyse de consommation de courant. Pour mettre en évidence ces vulnérabilités, nous utilisons des techniques tels que l’apprentissage automatique et l’algèbre linéaire. De plus, pour les deux schémas, une seule trace de la consommation de courant est nécessaire pour remonter à la clé privée. Suite à la mise en évidence de ces vulnérabilités, nous proposons des stratégies de contre-mesures visant à prévenir ces attaques tout en maintenant le temps constant
For about three decades, we have been aware of attacks targeting implementations of cryptosystems, exploiting physical information such as execution time. Naturally, questions arise about the threats these attacks pose to the upcoming industry deployments of post-quantum schemes. In this thesis, we focus on the resistance of error-correcting code-based cryptographic algorithms against side-channel attacks. We specifically studied two schemes, ROLLO and BIKE, which were candidates for the second round of post-quantum standardization organized by NIST. Through our research, we demonstrate that their constant-time implementation is notably vulnerable to attacks using power consumption analysis. To demonstrate these vulnerabilities, we employ techniques such as machine learning and linear algebra. Furthermore, for both scheme, the attack requires a single trace of power consumption to recover the private key. Following the identification of these vulnerabilities, we propose countermeasure strategies to prevent these attacks while maintaining constant-time operation. For about three decades, we have been aware of attacks targeting implementations of cryptosystems, exploiting physical information such as execution time. Naturally, questions arise about the threats these attacks pose to the upcoming industry deployments of post-quantum schemes. In this thesis, we focus on the resistance of error-correcting code-based cryptographic algorithms against side-channel attacks. We specifically studied two schemes, ROLLO and BIKE, which were candidates for the second round of post-quantum standardization organized by NIST. Through our research, we demonstrate that their constant-time implementation is notably vulnerable to attacks using power consumption analysis. To demonstrate these vulnerabilities, we employ techniques such as machine learning and linear algebra. Furthermore, for both scheme, the attack requires a single trace of power consumption to recover the private key. Following the identification of these vulnerabilities, we propose countermeasure strategies to prevent these attacks while maintaining constant-time operation

Dans cette thèse, on s’intéresse à l’étude de systèmes de chiffrement ainsi que de schémas de signature dont la sécurité repose sur des problèmes difficiles de théorie des codes correcteurs d’erreurs. Ces activités de recherche ont été motivées, d’une part d’un point de vue théorique par la création de nouveaux schémas de signature avec des propriétés spéciales ainsi que d’une manière de réduire la taille de clés du schéma de McEliece, et d’autre part, d’un point de vue pratique visant à utiliser des propriétés structurelles afin d’obtenir des implémentations effectives d’un schéma de signature fondé sur les codes correcteurs d’erreurs. Comme l’indique son titre, cette thèse traite de la construction et de l’optimisation des cryptosystèmes basés sur des codes correcteurs d’erreurs et plus particulièrement de cinq nouveaux protocoles. On présente ici une version sécurisée du schéma de Stern dans un environnement à faibles ressources, une nouvelle construction du schéma de Kabatianski, Krouk et Smeets, un schéma de signature basé sur l’identité prouvé sûr dans le modèle de l’oracle aléatoire, un schéma de signature de cercle à seuil et enfin une réduction de la taille de clés du schéma de McEliece à l’aide de codes alternants quasi-cycliques. En annexe, on présente un travail traitant des attaques algébriques de registre à décalage avec mémoire. On présente aussi brièvement une étude des codes cycliques sur des anneaux de matrices
In this thesis, we are interested in the study of encryption systems as well as signature schemes whose security relies on difficult problems of error-correcting codes. These research activities have been motivated, a part of a theoretical point of view by creating : new signature schemes with special properties and a way of reducing the size of the key of the McEliece scheme, and on the other hand, a practical point of view to use structural properties to obtain effective implementations of a signature scheme which is based on error-correcting codes. As its title indicates, this thesis deals with the construction and optimization of cryptosystems based on error-correcting codes and more particularly five new protocols. It presents a secure version of the Stern scheme in a low-resources environment, a new construction of the Kabatianski, Krouk and Smeets scheme, a signature scheme based on the identity proved secure in the random oracle model, a threshold ring signature scheme and a reduction of the size of the key of the McEliece scheme using quasi-cyclic alternant codes. In the annex, this work deals with algebraic attacks against linear feedback shift register with memory. It also presents a brief study of cyclic codes on rings of matrices