Contributions to the hardness foundations of lattice-based cryptography / Weiqiang Wen ; sous la direction de Damien Stehlé

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Catalogue Worldcat

Cryptographie

Stehlé, Damien (1981-....) (Directeur de thèse / thesis advisor)

Gaborit, Philippe (1969-....) (Président du jury de soutenance / praeses)

Fouque, Pierre-Alain (1974-....) (Rapporteur de la thèse / thesis reporter)

May, Alexander (Rapporteur de la thèse / thesis reporter)

Micciancio, Daniele (Rapporteur de la thèse / thesis reporter)

Fontaine, Caroline (19..-.... ; chercheuse en informatique) (Membre du jury / opponent)

Université de Lyon (2015-....) (Organisme de soutenance / degree-grantor)

École doctorale en Informatique et Mathématiques de Lyon (Ecole doctorale associée à la thèse / doctoral school)

École normale supérieure de Lyon (Autre partenaire associé à la thèse / thesis associated third party)

Laboratoire de l'informatique du parallélisme (Lyon) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : 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.

Résumé / Abstract : 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.