Contributions to the hardness foundations of lattice-based cryptography - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Thèse Année : 2018

Contributions to the hardness foundations of lattice-based cryptography

Contributions aux fondements de complexité de la cryptographie sur réseaux

Résumé

Lattice-based cryptography is one of the most competitive candidates for protecting privacy, both in current applications and post quantum period. The central problem that serves as the hardness foundation of lattice-based cryptography is called the Learning with Errors (LWE). It asks to solve a noisy equation system, which is linear and over-determined modulo q. Normally, we call LWE problem as an average-case problem as all the coefficients in the equation system are randomly chosen modulo q. The LWE problem is conjectured to be hard even wtih a large scale quantum computer. It is at least as hard as standard problems defined in the lattices, such as Bounded Distance Decoding (BDD) and unique Shortest Vector Problem (uSVP). Finally, the best known algorithm for solving these problems is BKZ, which is very expensive. In this thesis, we study the quantum hardness of LWE, the hardness relations between the underlying problems BDD and uSVP, and the practical performance of the BKZ algorithm. First, we give a strong evidence of quantum hardness of LWE. Concretely, we consider a relaxed version of the quantum version of dihedral coset problem and show an computational equivalence between LWE and this problem. Second, we tighten the hardness relation between BDD and uSVP. More precisely, We improve the reduction from BDD to uSVP by a factor √2, compared to the one by Lyubashevsky and Micciancio. Third, we propose a more precise simulator for BKZ. In the last work, we propose the first probabilistic simulotor for BKZ, which can pridict the practical behavior of BKZ very precisely.
La cryptographie sur les réseaux est l’une des approches les plus compétitives 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 à résoudre un système d’équations bruité, linéaire et surdé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 apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. 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 nouveau simulateur 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.
Fichier principal
Vignette du fichier
WEN_Weiqiang_2018LYSEN070_These.pdf (2.97 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)
Loading...

Dates et versions

tel-01949339 , version 1 (10-12-2018)
tel-01949339 , version 2 (04-02-2019)

Identifiants

  • HAL Id : tel-01949339 , version 2

Citer

Weiqiang Wen. Contributions to the hardness foundations of lattice-based cryptography. Computational Complexity [cs.CC]. Université de Lyon, 2018. English. ⟨NNT : 2018LYSEN070⟩. ⟨tel-01949339v2⟩
369 Consultations
466 Téléchargements

Partager

Gmail Facebook X LinkedIn More