Description
Date depot: 1 janvier 1900
Titre: algorithmes quantiques pour le décodage de codes linéaires
Directeur de thèse:
Jean-Pierre TILLICH (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Contexte.
Shor a montré en 1994 que les deux principaux algorithmes de chiffrement à clé publique que sont RSA et les schémas
fondés sur la difficulté de résoudre le problème du logarithme discret peuvent être cassés à l'aide d'un ordinateur quantique.
Cela se révèle très problématique pour tous les systèmes cryptographiques à clé publique
utilisés en pratique. La sécurité de ces derniers repose en effet justement sur la difficulté
de la factorisation ou du calcul du logarithme discret.
De fait, début janvier 2016, le NIST a lancé un appel international pour normaliser des algorithmes cryptographiques à clé publique
pouvant résister à un ordinateur quantique.
Parmi les problèmes dont on a de bonnes raisons de penser qu'ils ne pourront pas être résolus en temps polynomial
par des algorithmes quantiques figure le décodage d'un code linéaire pour diverses métriques. Il s'agit ici, étant donné un code linéaire
défini sur un corps fini et un mot à distance au plus t
d'un mot de code, de retrouver le mot de code en question.
La cryptographie à base de codes correcteurs s'appuie sur la difficulté de ce problème quand la métrique considérée est la métrique
de Hamming (voire parfois la métrique rang), alors que la cryptographie à base de réseaux s'appuie très souvent elle aussi sur la difficulté de ce problème, mais la métrique utilisée dans ce cas là est la métrique euclidienne.
Il y a eu très peu de recherche effectuée jusqu'à présent pour essayer de trouver les algorithmes quantiques les plus performants
pour résoudre ce problème. Cela sera pourtant un élément important pour juger la sécurité des propositions qui seront faites au NIST
s'appuyant soit sur les codes, soit sur les réseaux. Le but de cette thèse est d'améliorer les algorithmes quantiques existants pour ce
problème.
Travail envisagé.
Pour l'instant, l'algorithme quantique le plus efficace pour résoudre le problème du décodage en métrique de Hamming ou en métrique
rang consiste en une simple utilisation de l'algorithme quantique de Grover pour améliorer l'algorithme de décodage basique par
ensemble d'information. Il s'agira dans cette thèse d'étudier plus en détail l'impact de l'utilisation d'outils d'algorithmique quantique plus sophistiqués tels que les marches aléatoires quantiques ou les 'learning graphs' conjointement avec des
algorithmes classiques plus sophistiqués. Il apparaît très probable que l'exposant asymptotique de la complexité puisse être diminué quelque peu avec ces approches plus avancées, comme cela a été le cas pour la complexité quantique du problème de subset-sum par
exemple.
Par ailleurs, la quasi-totalité des schémas cryptographiques fondés sur les codes ou les réseaux proposés ces dernières années s'appuient sur des codes et des réseaux structurés. La raison en est que la structure du réseau permet de représenter les clés publiques de ces schémas de manière beaucoup plus compacte. Dans ce cas, la sécurité du schéma repose sur la difficulté
supposée de résoudre le problème du décodage dans le cas d'un code structuré. Il apparait que lorsque la structure du code est trop forte
des attaques quantiques en temps polynomial sont possibles comme cela a été le cas pour le schéma fondé sur les réseaux comme SOLILOQUY, un
système proposé par l'organisme gouvernemental britannique CESG, ou le schéma de chiffrement homomorphe de Smart et Vancauteren.
On étudiera dans cette thèse en quoi la structure que l'on a rajouté au code permet de résoudre le problème de décodage de manière plus efficace.
Doctorant.e: Debris Thomas