Approche algébrique pour l'étude et la résolution de problèmes algorithmiques issus de la cryptographie et la théorie des codes

First of all, during my PhD I focused on the public key cryptography, more exactly on the code-based cryptography. The main motivation is to study the security of the latest encryption schemes. For that, I analyzed in detail the structural properties of the main code families. Thus, my research was naturally directed to the study of the McEliece based encryption schemes, among which the latest MDCP based variant [MTSB13] and Polar codes variant [SK14]. In the case of the MDPC based variant, we manage to reveal an important weakness regarding the key pairs that are used in the protocol. Indeed, we proposed an efficient algorithm that retrieves the private key given the public key of the scheme. Next we counted the proportion of weak keys and we used the code equivalence problem to extend the number of weak keys. We published our results in an international conference in cryptography [BDLO16]. Next we studied the Polar codes and their application to public key cryptography.Since they were discovered by Arikan [Arı09], Polar codes are part of the most studied from an information theory point of view, family of codes. In terms of performance they are really efficient since they are capacity achieving over the Binary Discrete Memoryless Channels and they allow extremely fast encoding and decoding algorithms. Nonetheless, few facts are known about their structure. In this context, we have introduced an algebraic formalism which allowed us to reveal a big part of the structure of Polar codes. Indeed, we have managed to answer fundamental questions regarding Polar codes such as the dual, the minimum distance, the permutation group and the number of minimum weight codewords of a Polar code. Our results were published in an international conference in information theory [BDOT16]. We also managed to completely cryptanalyze the McEliece variant using Polar codes. The attack was a direct application of the aforementioned results on the structural properties of Polar codes and it was published in an international conference in postquantum cryptography [BCD+16].Tout d’abord, mon sujet de recherche porte sur le cryptographie à clé publique, plus précisément la cryptographie basée sur la théorie des codes correcteurs d’erreurs. L’objectif principal de cette thèse est d’analyser la sécurité des systèmes de chiffrement. Pour cela j’étudie les propriétés structurelles des différentes familles de codes linéaires utilisées dans la pratique. Mon travail de recherche s’est orienté de maniéré naturelle, vers l’étude des deux dernières propositions de cryptosystèmes, plus exactement le schéma de McEliece à base des codes MDPC [MTSB13](moderate parity check codes) et des codes Polaires [SK14]. Dans le cas des codes MDPC on a mis en évidence une faiblesse importante au niveau des clés utilisées par les utilisateurs du système. En effet, on a proposé un algorithme très efficace qui permet de retrouver une clé privé à partir d’une clé publique. Ensuite on a compté le nombre des clés faibles et on a utilisé le problème d’équivalence de codes pour élargir le nombre de clés faibles. On a publié notre travail de recherche dans une conférence internationale en cryptographie [BDLO16]. Ensuite on a étudié les codes Polaires et leur application à la cryptographie à clé publique. Depuis leur découverte par E. Arikan [Arı09], les codes Polaires font partie des famille de codes les plus étudié du point de vue de le théorie de l’information. Ce sont des codes très efficaces en terme de performance car ils atteignent la capacité des canaux binaires symétriques et ils admettent des algorithmes d’encodage et décodage très rapides. Néanmoins, peu des choses sont connu sur leur propriétés structurelles. Dans ce cadre la, on a introduit un formalisme algébrique qui nous a permit de révéler unegrande partie de la structure de ces codes. En effet, on a réussi à répondre à des questions fondamentales concernant les codes Polaires comme : le dual ou la distance minimale d’un code Polaire, le groupe des permutations ou le nombre des mots de poids faible d’un code Polaire. On a publié nos résultats dans une conférence internationale en théorie de l’information [BDOT16]. Par la suite on a réussi à faire une cryptanalyse complète du schéma de McEliece à base des codes Polaires. Ce résultat a été une application directe des propriétés découvertes sur les codes Polaires et il a été publié dans une conférence internationale en cryptographie post-quantique [BCD+16]