Recherche

Mon sujet de thèse

Étude de primitives cryptographiques post-quantiques basées sur les codes correcteurs d’erreurs

En quelques mots…

Les avancées récentes autour de l’ordinateur quantique ont provoqué une accélération de la recherche autour d’une cryptographie post-quantique. En effet, cette cryptographie, qui doit être utilisable sur tout ordinateur, a pour but de résister autant aux ordinateurs quantiques qu’aux ordinateurs classiques actuels. C’est dans cette optique que le National Institute of Standards and Technology (NIST) a lancé en 2017 un appel à soumissions pour trouver les algorithmes qui pourront être standardisés dans les prochaines années. Parmi les soumissions proposées fin 2017, on trouve plusieurs familles, dont la cryptographie basée sur les codes correcteurs d’erreurs. C’est la famille de cryptosystèmes à laquelle je m’intéresse dans ma thèse.

Plus particulièrement, je m’intéresse aux attaques algébriques sur ces soumissions autour des codes correcteurs d’erreurs. Il s’agit de former un système d’équations polynomiales à partir des éléments publics et connus du cryptosystème, et de chercher à le résoudre. En complément de la résolution elle-même, on analyse également sa complexité, afin de savoir si l’attaque est réalisable en pratique ou si celle-ci est uniquement théorique.

Pendant la première partie de ma thèse, j’ai examiné la soumission au NIST appelée DAGS (pour DyAdic Generalized Srivastava). Avec mes encadrants, nous avons étudié une attaque réalisée précédemment sur ce cryptosystème. L’étude approfondie du fonctionnement de cette attaque a permis dans un premier temps d’améliorer significativement les temps de l’attaque sur les ensembles de paramètres déjà cassés. Dans un second temps, une meilleure compréhension de la complexité a rendu possible l’attaque de deux autres ensembles de paramètres. Ces travaux ont abouti à la soumission d’un article au Code-Based Cryptography Workshop (CBC), que j’ai pu présenter à Darmstadt, en Allemagne, en mai 2019. Suite à la première attaque, le cryptosystème DAGS n’a pas été retenu pour la suite de l’appel à soumissions.

Par la suite, j’ai poursuivi l’étude de la complexité de la résolution du système associé à DAGS. Tout d’abord, cela va permettre de fournir une complexité précise pour tous les ensembles de paramètres de DAGS qui ont été proposés lors de sa soumission et de donner des paramètres minimaux afin de garantir sa sécurité face à l’ataque présentée. L’autre intêret est de pouvoir accélérer une nouvelle fois la résolution en complétant le système avec de nouvelles équations. Enfin, cette analyse approfondie et les résultats qui en découlent pourront ensuite être étendus à des systèmes aux propriétés similaires, ou à des systèmes légèrement différents à l’aide d’une étude supplémentaire.

Mots clés : cryptographie post-quantique, systèmes polynomiaux multivariés, bases de Gröbner, cryptanalyse, attaques algébriques

Publications

Publications avec actes en conférence internationale

  • Bardet Magali, Bertin Manon, Couvreur Alain, Otmani Ayoub. Practical Algebraic Attack on DAGS. In : Baldi M., Persichetti E., Santini P. (eds) Code-Based Cryptography. CBC 2019. Lecture Notes in Computer Science, vol 11666. Springer, Cham. https://doi.org/10.1007/978-3-030-25922-8_5

Exposés et séminaires invités

  • Bardet Magali, Bertin Manon, Couvreur Alain, Otmani Ayoub. Practical Algebraic Attack on DAGS. Groupe de travail Cryptographie basée sur les codes, organisé par Jean-Pierre Tillich. INRIA Paris, avril 2019.
  • Bardet Magali, Bertin Manon, Couvreur Alain, Otmani Ayoub. Understanding the complexity of an algebraic attack on the DAGS cryptosystem. Journées Nationales de Calcul Formel. CIRM, Luminy, mars 2020. [Slides]
  • Bardet Magali, Bertin Manon, Couvreur Alain, Otmani Ayoub. Understanding the complexity of an algebraic attack on the DAGS cryptosystem. Journées Codes et Cryptographie 2020. Erdeven, Bretagne. Initialement prévu en mars 2020, reporté à novembre 2020 suite au Covid-19.
  • Bardet Magali, Bertin Manon, Couvreur Alain, Otmani Ayoub. Cryptosystème DAGS : fonctionnement, attaque et complexité. Séminaire Université Paris 8. Initialement prévu en mars 2020, reporté suite au Covid-19.

Diffusion de la culture scientifique

  • Bertin Manon. Overview of post-quantum cryptography. Journée des Doctorants de l’Association des Doctorants et Docteurs des Écoles Doctorales PSIME & MIIS de Rouen et Le Havre (ADDED). Rouen, juillet 2019.
  • Bertin Manon. Study of post-quantum cryptography schemes based on error-correcting codes. Journée de Doctorants du Laboratoire d’Informatique, du Traitement de l’Information et des Systèmes (LITIS). Le Havre, juillet 2019.
  • Bertin Manon. Étude de primitive cryptographiques post-quantiques basées sur les codes correcteurs d’erreurs. Participation à Ma Thèse en 180 secondes, vulgarisation du sujet de thèse pour le grand public. Caen, mars 2020.

Prix et distinctions

  • Prix de la meilleure présentation de la session Informatique lors de la Journée des Doctorants de l’ADDED. Rouen, juillet 2019.