La cryptographie basée sur les codes correcteurs d’erreur est une des approches prometteuses pour obtenir des primitives cryptographiques qui résistent à l’ordinateur quantique. Un tiers des algorithmes proposés pour la standardisations post-quantique sont basés sur cette famille de problèmes.
Les cryptosystèmes à base de code reposent majoritairement sur le principe suivant. On choisit un code correcteur qui possède une certaine structure algébrique, qui permet de corriger beaucoup d’erreurs. Pour chiffrer un message, on l’encode puis on ajoute des erreurs. Une personne qui ne connaît pas la structure du code ne peut pas corriger les erreurs, donc ne peut pas déchiffrer le message. La clé publique est donc la donnée du code, mais sous une forme qui ne révèle pas sa structure. La clé privée est la donnée du code sous sa forme structurée, pour permettre le décodage.
Pour attaquer un tel système de chiffrement, deux approches sont possibles. Soit l’attaquant arrive à retrouver la structure algébrique cachée du code, puis corrige les erreurs comme s’il avait la clé privée. Dans ce cas, cela signifie qu’il arrive à distinguer le code de la clé publique d’un code aléatoire. Soit l’attaquant ne cherche pas à retrouver la structure du code, considère qu’il s’agit d’un code totalement aléatoire, et essaie simplement de corriger toutes les erreurs avec ce code. On parle alors d’attaques génériques (car elle ne dépendent pas de la famille de codes choisie).
On s’intéresse ici au second cas. Pour juger le niveau de sécurité d’un cryptosystème, il est important de comprendre la complexité du problème de décodage générique. Depuis plusieurs décennies, une série de travaux propose des algorithmes de plus en plus performants pour essayer de réduire la complexité de ce problème. Mais les études de complexité s’intéressent principalement à l’exposant asymptotique et ces algorithmes ont rarement été implémentés. Pour mieux comprendre la sécurité de ce problème en pratique, nous avons lancé en août 2019 un site internet « Decoding Challenge » qui propose des instances de difficulté croissante du problème de décodage générique.
Dans cet exposé, on expliquera les principales approches pour résoudre ce problème et l’état actuel des connaissances sur la complexité du problème de décodage générique en pratique.

Le site internet : http://decodingchallenge.org/

Cet exposé était initialement prévu le 12 décembre 2019 mais a été annulé suite aux grèves de transport.