Supervision : Jean-Charles FAUGÈRE

Co-supervision : PERRET Ludovic, GOUGET Aline

Algebraic and Physical Security in Code-Based Cryptography

Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymmetric primitives which are threatened by quantum computers. More generally, it has been considered secure for more than thirty years, and allows 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 than 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 fundamental 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.

2014-2016 Publications

• 2016
  • J.‑Ch. Faugère, A. Otmani, L. Perret, F. De Portzamparc, J.‑P. Tillich : “Structural Cryptanalysis of McEliece Schemes with Compact Keys”, Designs, Codes and Cryptography, vol. 79 (1), pp. 87-112, (Springer Verlag) (2016)
  • J.‑Ch. Faugère, A. Otmani, L. Perret, F. De Portzamparc, J.‑P. Tillich : “Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups”, IEEE Transactions on Information Theory, vol. 62 (1), pp. 184-198, (Institute of Electrical and Electronics Engineers) (2016)
• 2015
  • F. Urvoy de Portzamparc : “Sécurités algébrique et physique en cryptographie fondée sur les codes correcteurs d’erreurs”, thesis, phd defence 04/17/2015, supervision Faugère, Jean-Charles, co-supervision : Perret, Ludovic, Gouget, Aline (2015)
• 2014
  • J.‑Ch. Faugère, L. Perret, F. De Portzamparc : “Algebraic Attack against Variants of McEliece with Goppa Polynomial of a Special Form”, Advances in Cryptology Asiacrypt 2014, vol. 8873, Lecture Notes in Computer Science, Kaohsiung, Taiwan, Province of China, pp. 21-41, (Springer) (2014)
  • J.‑Ch. Faugère, L. Perret, F. De Portzamparc, A. Otmani, J.‑P. Tillich : “Structural weakness of compact variants of the McEliece cryptosystem”, IEEE International Symposium on Information Theory - ISIT 2014, Honolulu, United States, pp. 1717-1721 (2014)