Description
Date depot: 6 février 2020
Titre: cryptanalyse quantique de schémas post-quantiques à base de codes et de réseaux
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 : Calcul arithmétique et formel, codage et cryptologie
Resumé:
Contexte et enjeux.
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.
De fait, à la fin de l'année 2017, le NIST a lancé une compétition ayant pour but de sélectionner les algorithmes cryptographiques à clé publique pouvant résister à un ordinateur quantique.
Les schémas qui viennent de passer au deuxième tour de la compétition font appel
à diverses hypothèses de sécurité. Plus de la moitié de ces propositions se fondent sur la difficulté
de résoudre soit le problème de décodage pour un code ou un réseau.
Ces problèmes ont été longuement étudiés face à des algorithmes
fonctionnant sur un ordinateur classique. La sécurité de ces problèmes par rapport
à des algorithmes quantiques est en revanche bien moins comprise alors que c'est un point fondamental à élucider pour bâtir notre confiance en ces nouvelles primitives.
Travail envisagé
Il est envisagé dans cette thèse de s'attaquer d'abord au problème de décodage d'un code linéaire par un ordinateur quantique et d'étudier l'apport des techniques algorithmiques plus sophistiquées que l'algorithme de Grover couplées avec des avancées récentespour améliorer l'exposant asymptotique de la complexité dans le cadre classique.
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 ou de recherche du point du réseau le plus proche dans le cas d'un code ou réseau structuré. Il apparait notamment que lorsque la structure du réseau est trop forte, des attaques quantiques assez dévastatrices sont possibles comme cela a été le cas pour SOLILOQUY par exemple.
On étudiera dans cette thèse en quoi la structure que l'on a rajouté au code ou réseau permet de résoudre le problème de décodage ou de recherche du point du réseau le plus proche de manière plus efficace.
Doctorant.e: Remaud Maxime