Liens transverses ENS de Lyon

Agenda de l'ENS de Lyon

Contributions to the hardness foundations of lattice-based cryptography

Date
mar 06 nov 2018
Horaires

14h00

Intervenant(s)

Soutenance de thèse de M. Weiqiang du LIP, sous la direction de M Damien STEHLE

Langue(s) des interventions

Description générale

La cryptographie sur les réseaux est l'une des approches les plus compétitifs pour protéger la confidentialité, dans les applications actuelles et l'ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à ésoudre un système d'équations bruité, qui est linéaire et sur déterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les  réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux.
Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l'algorithme BKZ. Tout d'abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d'un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, nous donnons une  nouvelle preuve de la difficulté quantique de LWE. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un simulateur plus précis pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet  de prévoir le comportement pratique de BKZ très précisément.

Gratuit
Mots clés
Disciplines