Direction de recherche : Antoine JOUX

Algorithmes de réseau et cryptographie basée sur les réseaux

La cryptographie basée sur les réseaux est un domaine de recherche qui étudie la construction d’outils et de protocoles pour une communication sécurisée basée sur des problèmes de réseau difficiles. La cryptographie basée sur les réseaux est l’un des candidats les plus prometteurs pour la communication sécurisée post-quantique en raison de sa sécurité conjecturée contre les attaques quantiques et de son efficacité algorithmique. Une autre caractéristique intéressante de la cryptographie basée sur les réseaux est un large éventail de constructions disponibles qui incluent même des schémas de chiffrement totalement homomorphes (Fully Homomorphic Encryption ou FHE en anglais). Cette thèse étudie les algorithmes pour résoudre les problèmes de réseau difficiles et leur application à l’évaluation de la sécurité des constructions cryptographiques basées sur les réseau. Cette thèse comporte deux parties.

Dans la première partie, on introduit une nouvelle famille d’algorithmes de sieving appelé sieiving cylindrique. Le sieving heuristique est actuellement l’approche la plus rapide pour résoudre les problèmes de réseau central, le problème de vecteur le plus court (Shortest Vector Problem ou SVP en anglais) et le problème de vecteur le plus proche (Closest Vector Problem ou CVP en anglais). Dans cette thèse, on propose un nouvel algorithme de sieving pour résoudre SVP et CVP, qui fonctionne avec des vecteurs de réseau de géomérie différente par rapport aux algorithmes de sieving habituels. Le sieving cylindrique fonctionne en générant une liste de vecteurs de réseau `a l’intérieur d’un hypercylindre long et étroit, puis il tamise de manière itérative les vecteurs de la liste afin d’obtenir une nouvelle liste de vecteurs `a l’intérieur d’un hypercylindre beaucoup plus court mais légèrement plus large. On montre que cette approche peut être très efficace pour résoudre certaines variations de CVP et SVP. Premièrement, le sieving cylindrique améliore la complexité temporelle asymptotique pour la résolution de SVP sur des réseaux dont le volume est un nombre premier relativement petit. Par exemple, il permet de résoudre SVP pour un réseau de dimension n de volume premier d’environ 2^n dans le temps 2^(0.229n). Deuxièmement, il permet d’obtenir la complexité temporelle polynomiale d’une requête pour résoudre le problème de vecteur le plus proche avec prétraitement (Closest Vector Problem ou CVPP en anglais), pour un coût en temps de 2^(0.531n) et en memoire 2^(n/2) lors de la phase de prétraitement pour un réseau arbitraire.

Dans la deuxième partie, on étudie la sécurité de Fast Fully Homomorphic Encryption scheme over Torus (TFHE). TFHE est l’un des schémas de chiffrement totalement homomorphe les plus rapides basé sur le problème (ring-)Learning with Errors (LWE). Dans cette thèse, on améliore l’attaque à base de réseau dual utilisée dans l’estimation de sécurité initiale du schéma. Plus précisément, on réalise l’attaque duale sur des sous-réseaux projetés, qui permet de générer des instances du problème LWE avec un bruit légèrement plus grand qui correspond à une fraction de la clé secrète. Ensuite, on recherche la fraction de la clé secrète en calculant le bruit correspondant pour chaque candidat en utilisant les échantillons LWE construits. Comme les clés de TFHE sont des vecteurs binaires, on peut effectuer l’étape de recherche très efficacement en exploitant la structure récursive de l’espace de recherche. Cette approche offre un compromis entre le coût de la réduction du réseau et la complexité de la partie recherche qui permet d’accélérer l’attaque. On implémente un script qui estime la complexité de l’attaque duale d’origine et de notre méthode hybride pour divers paramètres sous trois modèles de coûts différents pour la réduction du réseau et montre que le niveau de sécurité actuel (en mars 2020) de TFHE devrait être réévalué selon l’amélioration proposée.

Soutenance : 27/05/2020

Membres du jury :

M. Jean-Claude Bajard Prof., Sorbonne Université, IMJ
M. Pierre-Alain Fouque Prof., Université de Rennes (rapporteur)
M. Louis Gobin Prof., UVSQ
M. Antoine Joux Tenured Research Faculty, CISPA Helmholtz Center (directeur de thèse)
M. David Naccache Prof., ENS (rapporteur)
Mme. Annick Valibouze Prof., Sorbonne Université, LIP6
Mme. Brigitte Vallée DR, Université Caen, GREYC

Publications 2020

• 2020
  • N. Kharchenko : “Algorithmes de réseau et cryptographie basée sur les réseaux”, soutenance de thèse, soutenance 27/05/2020, direction de recherche Joux, Antoine (2020)
  • Th. Espitau, A. Joux, N. Kharchenko : “On a Dual/Hybrid Approach to Small Secret LWE”, Progress in Cryptology – INDOCRYPT 2020, vol. 12578, Lecture Notes in Computer Science, Bangalore, India, pp. 440-462, (Springer), (ISBN: 978-3-030-65277-7) (2020)