Description
Date depot: 7 décembre 2023
Titre: Attaques algébriques sur le système de McEliece
Directeur de thèse:
Jean-Pierre TILLICH (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: La recherche pour produire un ordinateur quantique s'est considérablement intensifiée ces dernières, poussée
par de grosses entreprises comme Amazon, Google ou IBM, voire de startups comme PsiQuantum par exemple.
De tels ordinateurs représenteraient une menace majeure pour la quasi-totalité de la cryptographie post-quantique
utilisée en pratique actuellement. Cette situation a poussé le NIST à lancer un processus visant à standardiser à terme des cryptosystèmes, des protocoles
d'échange de clés ou des signatures numériques qui résisteraient à un ordinateur quantique. Parmi les solutions qui se trouvent
être les finalistes de la 4ème ronde de la compétition, figure le système de McEliece.
Un des points forts de cette soumission est que c'est le système de chiffrement à clé publique le plus ancien qui n'ait pas été cassé : plus de 45 ans
d'existence! De nombreuses approches pour cryptanalyser ont été tentées sans que la structure
polynomiale sous-jacente à la clé de chiffrement n'ait pu être exploitée. Il est prévu que ce système soit encore en lice l'an prochain
comme l'explique l'email de Dustin Moody sur le forum du NIST datant du 18 septembre 2023.
Néanmoins, récemment une voie d'attaque permettant d'attaquer le système de McEliece en rendement très proche de $1$ a été proposée [BMT22,CMT23].
En un certain sens, les attaques récentes [BMT22,CMT23] sont parvenus à transformer le distingueur de [FGOPT11] en
attaque. Il est intéressant de remarquer que le preprint [CMT23] outre
le fait de proposer une attaque sur les systèmes de McEliece s'appuyant sur des codes de Goppa ou alternants de rendement très élévé distinguables
au sens de [FGOPT11] propose aussi un tout nouveau distingueur. Ce dernier, contrairement à celui proposé dans [FGOPT11}]permet de distinguer des codes de Goppa ou des codes alternants dans une plage de rendement beaucoup plus élevé, et notamment il permet de distinguer les codes de tous les schémas proposés au NIST.
Ceci ouvre la voie potentiellement vers de nouvelles attaques sur le schéma.
C'est précisément la voie que nous comptons explorer dans cette thèse.
{BMT22}
Magali Bardet, Rocco Mora, and Jean-Pierre Tillich, "Polynomial time key-recovery attack on high rate random alternant" codes, a paraitre dans
Transactions on Information Theory, 2023.
[CMT23]
Alain Couvreur, Rocco Mora, and Jean-Pierre Tillich, "A new approach based on quadratic forms to attack the Mceliece cryptosystem."
Asiacrypt, 2023.
[FGOPT11]
Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich, "A distinguisher for high rate {McEliece} cryptosystems",
in Proc. IEEE Inf. Theory Workshop- ITW~2011, pages 282--286, Paraty, Brasil, October 2011.
Doctorant.e: Lemoine Axel