A word on my PhD supervision

My official (as seen on theses.fr and on paperwork) PhD advisor is Bruno Salvy, but I need to comment on my PhD’s supervisory context.

I started my PhD in late 2021 under the supervision of Damien Stehlé. He left the ENS de Lyon for CryptoLab in early 2023, a little more than a year after. At this stage, Guillaume Hanrot took over my supervision. When Guillaume also left for CryptoLab in late 2023, the official PhD advisor became Bruno Salvy.

Bruno Salvy did provide an administrative supervision (and precious advices) but all the scientific one was done by Damien and Guillaume even after they left for Cryptolab. In the scientific sense, my PhD advisors are Damien Stehlé and Guillaume Hanrot, even if they are not noted as such on the front page of the manuscript for administrative reasons.

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 fforeword rom 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.