Code-based cryptography is an area of classical cryptography in which cryptographic primitives rely on hard problems and trapdoor functions related to linear error-correcting codes. Since its inception in 1978, the area has produced the McEliece and the Niederreiter cryptosystems, multiple digital signature schemes, identification schemes and code-based hash functions. All of these are believed to be resistant to attacks by quantum computers. Hence, code-based cryptography represents a post-quantum alternative to the widespread number-theoretic systems. This thesis summarizes recent developments in the field of code-based cryptography, with a particular emphasis on code-based signature schemes. After a brief introduction and analysis of the McEliece and the Niederreiter cryptosystems, we discuss the currently unresolved issue of constructing a practical, yet provably secure signature scheme. A detailed analysis is provided for the Courtois, Finiasz and Sendrier signature scheme, along with the mCFS and parallel CFS variations. Finally, we discuss a recent proposal by Preetha et al. that attempts to solve the issue of provable security, currently failing in the CFS scheme case, by randomizing the public key construct. We conclude that, while the proposal is not yet practical, it represents an important advancement in the search for an ideal code-based signature scheme.

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]. / 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].

Title: Goppa codes and their applications Author: Bc. Jaroslav Kotil Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc. Abstract: In this diploma paper we introduce Goppa codes, describe their para- metres and inclusion in Alternant codes, which are residual Generalized Reed- Solomon codes, and Algebraic-geometry codes. Aftewards we demonstrate deco- ding of Goppa codes and introduce Wild Goppa codes. We also describe post- quantum cryptography member: McEliece cryptosystem for which no effective attacks with quantum computers are known. We outline a usage of this crypto- system with Goppa codes and describe the security of the cryptosystem together with possible attacks of which the most effective ones are based on information- set decoding. Keywords: Goppa codes, Generalized Reed-Solomon codes, Algebraic-geometry codes, Post-quantum cryptography, McEliece cryptosystem 1

Le premier protocole cryptographique basé sur les codes correcteurs d'erreurs a été proposé en 1978 par Robert McEliece. La cryptographie basée sur les codes est dite post-quantique car il n'existe pas à l'heure actuelle d'algorithme capable d'attaquer ce type de protocoles en temps polynomial, même en utilisant un ordinateur quantique, contrairement aux protocoles basés sur des problèmes de théorie des nombres. Toutefois, la sécurité du cryptosystème de McEliece ne repose pas uniquement sur des problèmes mathématiques. L'implantation, logicielle ou matérielle, a également un rôle très important pour sa sécurité et l'étude de celle-ci face aux attaques par canaux auxiliaires/cachés n'a débuté qu'en 2008. Des améliorations sont encore possibles. Dans cette thèse, nous proposons de nouvelles attaques sur le déchiffrement du cryptosystème de McEliece, utilisé avec les codes de Goppa classiques, ainsi que des contre-mesures correspondantes. Les attaques proposées sont des analyses de temps d'exécution ou de consommation d'énergie. Les contre-mesures associées reposent sur des propriétés mathématiques et algorithmiques. Nous montrons qu'il est essentiel de sécuriser l'algorithme de déchiffrement en le considérant dans son ensemble et non pas seulement étape par étape / The first cryptographic protocol based on error-correcting codes was proposed in 1978 by Robert McEliece. Cryptography based on codes is called post-quantum because until now, no algorithm able to attack this kind of protocols in polynomial time, even using a quantum computer, has been proposed. This is in contrast with protocols based on number theory problems like factorization of large numbers, for which efficient Shor's algorithm can be used on quantum computers. Nevertheless, the McEliece cryptosystem security is based not only on mathematical problems. Implementation (in software or hardware) is also very important for its security. Study of side-channel attacks against the McEliece cryptosystem have begun in 2008. Improvements can still be done. In this thesis, we propose new attacks against decryption in the McEliece cryptosystem, used with classical Goppa codes, including corresponding countermeasures. Proposed attacks are based on evaluation of execution time of the algorithm or its power consumption analysis. Associate countermeasures are based on mathematical and algorithmic properties of the underlying algorithm. We show that it is necessary to secure the decryption algorithm by considering it as a whole and not only step by step