| Description | La cryptographie a connu une révolution dans la seconde moitié des années 1970 avec l'invention des systèmes dits asymétriques (ou encore, à clé publique), qui ont permis son utilisation à très grande échelle, telle qu'on la connaît de nos jours.
En 1994 cependant, les travaux de Shor ont montré que les cryptosystèmes asymétriques déployés actuellement, sur lesquels repose la sécurité de toutes nos communications, seraient vulnérables à l'arrivée de l'ordinateur quantique.
Que l'on croie ou non à la mise au point prochaine d'un ordinateur quantique suffisamment grand et stable pour exécuter l'algorithme de Shor ou ses variantes, les enjeux sont tels qu'il convient de s'en prémunir dès maintenant.
De nombreux cryptosystèmes dits post-quantiques (c'est-à-dire, résistant à l'ordinateur quantique tout en pouvant fonctionner sur les infrastructures actuelles) ont été proposés et sont à l'étude en vue d'une éventuelle standardisation, parmi lesquels un candidat directement dérivé du cryptosystème de McEliece.
Le cryptosystème de McEliece, présenté en 1978, est l'un des plus anciens systèmes à clé publique, précédé seulement par ceux de Diffie-Hellman, RSA, et Merkle-Hellman.
Sa sécurité repose sur la difficulté supposée de décoder un mot bruité dans un code correcteur d'erreur d'un type particulier fondé sur l'algèbre, dit code de Goppa binaire, lorsque la structure de ce code a été masquée (et l'on conjecture que l'ordinateur quantique ne permettrait pas de résoudre ce problème de façon significativement plus efficace que par des méthodes classiques).
Deux questions se sont alors posées naturellement :
Afin de se procurer la plus grande assurance possible, il est souhaitable de prouver que la sécurité d'un cryptosystème se ramène à la difficulté d'un problème classique et très étudié, de portée très générale en mathématiques ou en informatique théorique, pas uniquement restreint au champ de la communauté cryptographique. Est-ce possible dans le cas de McEliece ?
A des fins d'efficacité, plusieurs variantes du système de McEliece ont été proposées, dans lesquelles le code de Goppa est remplacé par un autre type de code algébrique. Cependant, presque toutes ces propositions ont été cassées. Y a-t-il une propriété particulière des codes de Goppa qui permette d'expliquer a priori pourquoi, contrairement aux autres, la version originelle de McEliece résiste encore ?
Une réponse très naturelle à ces deux questions est de faire l'hypothèse que les codes de Goppa, après masquage, sont indistinguables calculatoirement de codes aléatoires.
D'une part (point 1.), cela ramènerait la sécurité de McEliece au problème du décodage d'un code aléatoire, qui est un problème fondamental en informatique théorique. D'autre part (point 2.), cela fournirait une propriété des codes de Goppa que n'ont pas les autres codes algébriques.
Ce problème du distingueur (c'est-à-dire, produire un algorithme capable de ditinguer un code de Goppa masqué d'un code aléatoire) a été étudié par Faugère et al. en 2010, puis par Couvreur-Mora-Tillich en 2023.
Cependant, les résultats de ces auteurs restent partiels : ils s'appliquent uniquement à des codes ayant une classe très restreinte de paramètres.
Dans un travail récompensé lors de la conférence Eurocrypt 2025 à Madrid, j'améliore ces résultats en proposant un distingueur qui s'affranchit de toutes ces restrictions, et dont la complexité asymptotique (c'est-à-dire, lorsque la taille du code tend vers l'infini) est meilleure que celle des attaques contre lesquelles le système a été dimensionné.
Ce résultat repose principalement sur deux ingrédients :
l'utilisation de notions sophistiquées issues de la géométrie algébrique, les espaces de syzygies supérieurs, ou de façon équivalente, les nombres de Betti gradués d'un ensemble de points dans l'espace projectif
l'observation que le dual d'un code de Goppa peut être "raccourci" un nombre exceptionnellement grand de fois, tout en continuant à posséder des propriétés algébriques que n'ont pas les codes aléatoires.
Si ce travail constitue une avancée importante dans la compréhension des fondements de la sécurité de McEliece, il convient d'en signaler aussi les limites.
Tout d'abord, s'il est vrai que l'hypothèse d'indistinguabilité aurait renforcé l'assurance de sécurité du système, d'un point de vue purement formel on peut encore concevoir que McEliece reste sûr en l'absence de cette hypothèse. L'existence d'un distingueur ne fournit pas une attaque contre le système.
Par ailleurs, le gain en complexité du distingueur est seulement asymptotique. Lorsqu'on l'applique aux systèmes proposés dans le cadre du processus de standardisation en cours, cette complexité se situe encore bien au-delà des niveaux de sécurité requis.
Au final, ce travail place l'état de l'art en matière de sécurité de McEliece dans un entre-deux inconfortable. D'une part, la sécurité du système subsiste jusqu'à présent, d'un point de vue purement empirique, dans la mesure où aucune attaque connue ne remet en cause la difficulté du problème sous-jacent très particulier. Mais de l'autre, il y a maintenant peu d'espoir que cette sécurité puisse se ramener théoriquement à la difficulté d'un problème plus général et plus étudié. Cette situation a peut-être contribué à la décision récente du NIST de ne pas retenir, au moins dans un premier temps, le système de McEliece pour la standardisation post-quantique.
On peut aussi enfin se demander si les outils introduits dans la conception de ce distingueur ne pourront pas servir, un jour, combinés avec d'autres arguments, pour mettre au point une véritable attaque contre le système. |