Cryptographie à base de codes
From Wikipedia, the free encyclopedia
La cryptographie à base de codes est une technique permettant de construire des primitives cryptographiques à clé publique à partir de codes correcteurs d'erreurs[1]. Il s'agit d'une des premières constructions de cryptographie asymétrique, et constitue l'une des directions de recherche explorées pour développer la cryptographie post-quantique[1],[2]. La sécurité de ces constructions repose sur le théorème que le décodage d'un code linéaire est NP-difficile en général[3].
En 1978, Elwyn Berlekamp, Robert McEliece et Henk von Tilborg démontrent que le problème consistant à décoder un code linéaire est en général NP-difficile[3]. McEliece en tire un cryptosystème à clé publique[4] à partir des codes algébriques binaires de Goppa, appelé cryptosystème de McEliece[5]. En 1986, Harald Niederreiter publie une construction similaire mais plus rapide, le cryptosystème de Niederreiter[6],[7], qui s'avère en fait équivalent (dual) à celui de McEliece[8]. À ce jour, la version de McEliece a résisté à la cryptanalyse, l'attaque la plus efficace connue étant le décodage par ensemble d'information[9], légèrement plus efficace sur un calculateur quantique, mais aisément contrecarrée en utilisant des paramètres assez grands[10].
Cependant, la taille prohibitive des clés et la complexité importante de l'algorithme de déchiffrement ont poussé au développement de variantes reposant sur d'autres codes. Ainsi il a été proposé de construire sur le même principe des cryptosystèmes à partir des codes de Reed-Solomon[11], de Reed-Muller[12], et plus récemment sur les codes LDPC ou MDPC quasi-cycliques[13],[14],[15]. Toutes ces variantes ont cela dit été rapidement cassées[10],[16],[14]. Il semble que le gain de structure, qui permet de compresser les clés publiques, facilite du même coup grandement le travail de l'attaquant.
Une autre solution consiste à considérer des codes correcteurs pour une autre métrique, en remplaçant par exemple la distance de Hamming par le rang. Si le problème du décodage est a priori plus difficile encodé dans ce contexte, en pratique une attaque due à Raphael Overbeck en 2008 a cassé toutes les propositions de ce type[17]. Des recherches se poursuivent sur la possibilité de contourner l'attaque[18].
Enfin, même l'utilisation d'un code de Goppa ne garantit pas la sécurité : si le taux approche 1 des attaques sont connues[19], de même si on considère un code -aire avec non premier[20].
