The manuscript: pdf.

President: | Philippe GABORIT |

Reviewers: | Pierre-Alain FOUQUE |

Alexander MAY | |

Daniele MICCIANCIO | |

Examiners: | Caroline FONTAINE |

Damien Stehlé (PhD supervisor) |

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.

Our BKZ experiments were run using the fplll (version 5.2.0) and fpylll (version 0.4.0dev) open-source libraries. Our simulator, coded in Python, and the BKZ variants, coded in C++ are all freely available online: https://github.com/BKZsimulator under the GNU Lesser General Public License (either version 2.1 of the License or any later version).

Some data corresponding to the figures of this chapter:

fig5.1-5.2,

fig5.3, fig5.4, fig5.5, fig5.6, fig5.7, fig5.8 (a chain of block-sizes (movie)), fig5.9, fig5.10, fig5.11, fig5.12, fig5.13, fig5.14,

fig5.15-5.16, fig5.17-5.18, fig5.19-5.20 (full GSO norms (movie), first GSO norm (movie)), fig5.21, fig5.22, fig5.23, fig5.24, fig5.25,

fig5.26 (a process of pressed-BKZ