Cryptographie à base de codes

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[4]. McEliece en tire un cryptosystème à clé publique[5] à partir des codes algébriques binaires de Goppa, appelé cryptosystème de McEliece[6]. En 1986, Harald Niederreiter publie une construction similaire mais plus rapide, le cryptosystème de Niederreiter[7] - [8], qui s'avère en fait équivalent (dual) à celui de McEliece[9]. À 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[10], légèrement plus efficace sur un calculateur quantique, mais aisément contrecarrée en utilisant des paramètres assez grands[11].

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[12], de Reed-Muller[13], et plus récemment sur les codes LDPC ou MDPC quasi-cycliques[14] - [15] - [16]. Toutes ces variantes ont cela dit été rapidement cassées[11] - [17] - [15]. 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 encode dans ce contexte, en pratique une attaque due à Raphael Overbeck en 2008 a cassé toutes les propositions de ce type[18]. Des recherches se poursuivent sur la possibilité de contourner l'attaque[19].

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[20], de même si on considère un code ${\displaystyle q}$-aire avec ${\displaystyle q}$ non premier[21].

La cryptographie à base de codes s'appuie sur la notion qu'un code linéaire peut être décrit par une matrice génératrice (ou une matrice de parité), qui sera donc la clé publique. Le chiffrement d'un message consiste simplement à appliquer le code correcteur correspondant, c'est-à-dire à effectuer le produit matrice vecteur, puis ajouter un aléa de poids de Hamming faible ${\displaystyle \leq t}$. Le déchiffrement consiste à appliquer l'algorithme de décodage du code correcteur.

Le code retenu pour cette construction est choisi de sorte qu'étant donnée la matrice génératrice du code, il est difficile d'en déduire un algorithme de décodage corrigeant jusqu'à ${\displaystyle t}$ erreurs. Ainsi, alors que le destinataire légitime du message bénéficie d'un algorithme efficace car spécialisé, un adversaire sera contraint d'appliquer des méthodes génériques, bien moins efficaces. En choisissant les paramètres du code de manière appropriée, on peut rendre le travail de l'adversaire arbitrairement difficile, tout en gardant le travail du destinataire légitime sous contrôle.

Pour éviter que l'adversaire ne « reconnaisse » le code à partir de sa matrice génératrice, on choisit le code parmi une famille assez large pour que la matrice semble aléatoire. On peut combiner cela avec des permutations afin de dissimuler la matrice davantage, au prix d'opérations supplémentaires pour le déchiffrement. Toutefois, l'apport concret de ces variations sur la sécurité du schéma semble mineure[22].

Construit ainsi, un chiffrement à base de codes correcteurs est vulnérable à toute une famille d'attaques classiques. Cela peut toutefois être évité de manière générique en appliquant une transformation due à Kazukuni Kobara et Hideki Imai[23] qui dote le cryptosystème d'une résistance aux attaques adaptatives par chiffrés choisis (IND-CCA2) pratiquement sans augmenter la bande passante par rapport à l'original.

Schémas de chiffrement :

• Chiffrement de McEliece
• Chiffrement de Niederreiter
• McBits[24]

Schémas de signature[25] :

• CFS[26]
• Cayrel-Gaborit-Prouff[27]
• KKS[28] (cassés en 2011[29])