Décodage générique dans divers métriques – DECODE

Dans un espace métrique, décoder un point consiste à trouver le point le plus proche dans un sous-espace prédéfini appelé "code". Ce problème est difficile lorsque le code est très peu structuré. Mieux encore, il est supposé difficile même pour un calculateur quantique. Ainsi, en utilisant un code structuré pour lequel on sait décoder efficacement et en cachant astucieusement cette structure, il est possible de construire un cryptosystème à clé publique dit post-quantique ; c'est-à-dire résistant à un ordinateur quantique. Dans le projet DECODE, on s'intéresse à diverses instances du problème de décodage : sur des réseaux euclidiens (on parle alors plutôt du problème CVP pour Closest Vector Problem), dans des espaces de Hamming binaires ou non-binaires, en métrique rang ou encore en métrique de Lee. En outre, récemment, une signature propose de considérer le décodage à grande distance ; c'est-à-dire qu'au lieu de chercher un mot de code proche, on cherche plutôt un mot de code éloigné. En bref, le problème de décodage se décline de nombreuses façons et d'une instance à l'autre, on trouve des techniques parfois très différentes pour le résoudre. L'idée majeure du projet DECODE est de s'inspirer des techniques de décodage de l'une ou l'autre des instances pour étendre leurs champs d'action sur les autres. L'objectif étant de proposer le meilleur algorithme de décodage possible pour chacune de ces instances. Un autre objectif du projet est d'implémenter nos solutions sur des calculateurs haute-performances et de relever les challenges proposés par différentes communautés de cryptologues. Enfin, une étape intermédiaire mais pas des moindres consistera à fournir une librairie capable de paramétrer précisément les algorithmes de décodage. Un tel outil est d'une utilité capitale pour les designers de cryptosystèmes post-quantiques car il leur permettrait de calibrer leurs systèmes avec plus de précision.