Defense information

The defense is scheduled for Tuesday, November 26th 2024 at 2pm (French time).

It will take place at Salle Condorcet (ENS de Lyon Site Monod) : here and online here.

The manuscript can be found here.

Jury

Reviewers

• Wouter CASTRYCK, Research Expert at KU Leuven.
• Emmanuel THOME, Directeur de Recherche at INRIA Nancy Grand Est.

Examinators

• Katharina BOUDGOUST, Chargée de Recherche CNRS at LIRMM.
• Elena KIRSHANOVA, Lead Cryptanalyst at Technology Innovation Institute.

Supervisors

• Bruno SALVY, Directeur de Recherche at INRIA Lyon.
• Damien STEHLE, Chercheur at CryptoLab.
• Guillaume HANROT, Chercheur at CryptoLab.

Title and Abstract

Hardness of Structured Lattice Problems for Post-Quantum Cryptography.

The security of cryptographic protocols is based on the presumed difficulty of algorithmic problems. Among those identified so far, some of the best problems to serve as a foundation for quantum-proof cryptography come from lattices. Lattices are a mathematical structure defined as a set of space vectors generated by integer combinations of a finite number of linearly independent real vectors (its basis). A typical example of a related security problem is the Shortest Vector Problem (SVP). Given a base of an n-dimensional lattice, find a non-zero short vector. For efficiency reasons, these problems are restricted to lattices arising from number theory, known as structured lattices. As the security assumptions for these particular lattices are different from those for unstructured lattices, it is necessary to study them specifically, which is the aim of this thesis.

We have studied the case of NTRU and uSVP modules in rank 2, proving that the SVP problem is equivalent on these two families of lattices. We also show a worst-case to average-case reduction for rank-2 uSVP lattices. Then we show that solving SVP on a prime ideal of small norm is no easier than solving SVP on any ideal.