Direction de recherche : Jean-Charles FAUGÈRE

Co-encadrement : PERRET Ludovic, GOUGET Aline

Sécurités algébrique et physique en cryptographie fondée sur les codes correcteurs d'erreurs

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. Une autre partie du travail envisagé pour cette thèse est d’étudier les différentes attaques physiques appliquées aux cryptosystèmes à base de codes et plus particulièrement au système de McEliece. Ces attaques pouvant s’appliquer aussi bien au moment de la génération des clés que du déchif- frement ou de la signature, les différents algorithmes seront étudiés.

Publications 2014-2016

• 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”, soutenance de thèse, soutenance 17/04/2015, direction de recherche Faugère, Jean-Charles, co-encadrement : 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)