Codes Structurés pour la Cryptographie: des Fondations Théoriques de la Sécurité aux Applications

In this PhD thesis, we focus on cryptography based on error-correcting codes, and more specifically on those offering a strong algebraic structure. Code-based cryptography is not new, as McEliece already proposed in 1978 an encryption scheme which relies, among other things, on the hardness of the decoding problem. It is important to note that McEliece cryptosystem still appears to be resistant to known attacks (even though its parameters needed to be updated to meet new security standards), including those involving quantum computers. In particular, this makes of McEliece the oldest cryptosystem with this property. Indeed, it is known since the 1990s that Shor algorithm poses a significant threat to the cryptography currently used inpractice. However, McEliece system suffers from a major drawback: its public keys are huge. In order to address this issue, it was proposed to use error-correcting codes with an additional algebraic structure, such as quasi-cyclic codes, which allow for a more compact representation and better performances. However, it is fundamental to ensure that this efficiency does not come at the expense of security. This is especially important as the National Institute for Standardsand Technology (NIST) has announced that the next post-quantum encryption standard will be chosen out of three candidates, two of them (BIKE and HQC) based on structured codes. Nevertheless, HQC relies on a different paradigm than that of McEliece: its security is based on the difficulty of the so-called decisional variant of the decoding problem. In the case of generic codes, it is known that the decisional and search versions, which is the most studied one, are in fact equivalent. However, the situation is much more uncertain in the case of structured codes for which no reduction from search to decision is known. Yet, the existence of theoretical reductions to well-established hard problems is an important characteristic toincrease confidence in a cryptosystem. In particular, one of the contributions of this thesis is an attack on code-based encryption schemes based on rank metric codes (another form of structured codes) that did not have this kind of reduction. This is the context of thesecond part of this thesis. Inspired by some techniques from lattice-based cryptography, we provide the first search-to-decision reduction for certain families of quasi-cyclic codes. It is based on a new interpretation of these codes using tools arising from the theory of function fields in positive characteristic, namely the Carlitz Modules. However, this reduction has certain limitations which we try to overcome. Finally, in the last part, we explore another application of these structured codes in the field of secure multiparty computation (MPC). The goal of an MPC protocol is to allow several players to perform a computation together so that they each only has partial knowledge of the input, and no one learns anything else thanthe output. It turns out that they can often benefit from long lists of correlated random elements to achieve fast computation, and a new tool called Pseudorandom Correlation Generators (PCG) was recently introduced to efficiently generate those long list. Thanks to our analysis of quasi-cyclic codes, we provide a more solid theoretical foundation for the best PCG constructions. Last but not least, we introduce for the first-time the decisional variant of the decoding problem of so-called quasi-abelian codes, and analyse its hardness in light of the techniques developed in this thesis. This allows us to overcome certain limitations of the state-of-the-art PCGs.Dans cette thèse, nous nous intéressons à la cryptographie fondée sur les codes correcteurs d'erreurs, et plus particulièrement sur ceux possédant une forte structure algébrique. La cryptographie à base de codes est ancienne, puisque McEliece proposait déjà en 1978 un schémade chiffrement reposant, entre autres, sur la difficulté du problème de décodage. Il est important de noter que le cryptosystème de McEliece est encore aujourd'hui résistant aux attaques, y compris à l'aide d'un ordinateur quantique (même si ses paramètres ont dû êtremis à jour pour s'adapter aux nouvelles normes de sécurité). En particulier, cela fait de McEliece le plus ancien cryptosystème avec cette propriété. En effet, il est connu depuis les années 1990 que l'algorithme de Shor présente une menace importante pour la cryptographie actuellement utilisée en pratique. Néanmoins, le système de McEliece souffre d'un gros inconvénient : ses clés publiques sont énormes. Afin de résoudre ce problème de taille, il a été proposé d'utiliser des codes correcteurs d'erreurs avec une structure algébrique additionnelle comme les codes quasi-cycliques, offrant une représentation plus compacte et de meilleures performances. Cependant, il est fondamental de s'assurer que cette efficacité ne se fasse pasau détriment de la sécurité. Ceci est d'autant plus important que le NIST (National Institute for Standards and Technology) a annoncé que le prochain standard de chiffrement post-quantique serait choisi parmi trois candidats, dont deux (BIKE et HQC) utilisent des codes structurés. Néanmoins, HQC est fondé sur un paradigme différent de celui de McEliece : sa sécurité repose sur la difficulté d'une variante dite décisionnelle du problème de décodage. Si dans le cas des codes génériques il est connu que les variantes de recherche et de décision sont en réalité équivalentes, la situation est beaucoup moins claire dans le cas des codes structurés pour lesquels aucune réduction de recherche-à-décision n'est connue. Cependant, l'existence deréductions théoriques vers des problèmes dont la difficulté est bien établie est une caractéristique importante pour accroître la confiance en un cryptosystème. En particulier, l'une des contributions de cette thèse est une attaque sur des chiffrements à base de codes en métrique rang (une autre forme de codes structurés) qui ne possédaient pas ce type de réduction. C'est dans ce contexte que se place la deuxième partie de cette thèse : inspirés par des techniques utilisées en cryptographie à base de réseaux euclidiens, nous donnons la premièreréduction de recherche-à-décision pour certaines familles de codes quasi-cycliques. Elle repose sur une nouvelle interprétation de ces codes à l'aide d'outils issus de la théorie des corps de fonctions en caractéristique positive : les modules de Carlitz. Cependant, cette réduction présente certaines limitations que nous tentons ensuite de lever. Finalement, dans une dernière partie nous explorons une autre application de ces codes structurés dans le domaine du calculmultiparti sécurisé (MPC). L'objectif d'un protocole de MPC est de permettre à plusieurs joueurs d'effectuer un calcul ensemble de telle sorte qu'ils n'aient chacun qu'une connaissance partielle de l'entrée, et que personne ne puisse apprendre autre chose que la sortie. Ils'avère qu'un outil appelé PCG a été récemment introduit afin de distribuer efficacement aux joueurs de longues listes d'éléments aléatoires corrélés qui permettent ensuite d'accélérer les calculs. Notre analyse des codes quasi-cycliques permet alors de donner desfondations théoriques plus solides aux meilleurs constructions de PCG. Enfin, en utilisant pour la première fois la variante décisionnelle du problème de décodage des codes dits quasi-abéliens, dont nous analysons la difficulté à la lumière des techniques développées dans cette thèse, nous sommes capables de lever certaines limitations des constructions de l'état de l'art