Team : ALMASTY

Localisation :

Boîte courrier 169

Couloir 24-25, Étage 4, Bureau 413

4 place Jussieu

75252 PARIS CEDEX 05

FRANCE

In the first part, we introduce a new family of lattice sieving algorithms called cylindrical sieving. Heuristic sieving is currently the fastest approach for solving central lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). In this thesis, we propose a new sieving algorithm for solving SVP and CVP, that works with lattice vectors of different geometry compared to usual sieving algorithms. Cylindrical sieving works by generating a list of lattice vectors inside a long and narrow hypercylinder and then it iteratively sieves vectors from the list in order to obtain a new list of vectors inside of much shorter but slightly wider hypercylinder. We show that this approach can be very efficient for solving certain variations of CVP and SVP. First, cylindrical sieving improves asymptotical time complexity for solving SVP on lattices whose volume is a relatively small prime number. For example, it allows to solve SVP for n-dimensional lattice of prime volume about 2^n in time 2^(0.229n). Second, it allows to achieve the polynomial time complexity of one query for solving the Closest Vector Problem with Preprocessing (CVPP), at the cost of spending 2^(0.531n) time and 2^(n/2) memory on the preprocessing for an arbitrary lattice.

In the second part, we study the security of the Fast Fully Homomorphic Encryption scheme over the Torus (TFHE). TFHE is one of the fastest FHE schemes based on the (ring-)Learning with Errors (LWE) problem. In this thesis, we improve the dual lattice attack used in the original security estimate of the scheme. More precisely, we use the dual attack on a projected sublattice, which allows to generate instances of the LWE problem with a slightly bigger noise that correspond to a fraction of the secret key. Then, we search for the fraction of the secret key by computing the corresponding noise for each candidate using the constructed LWE samples. As the TFHE keys are binary vectors, we can perform the search step very efficiently by exploiting the recursive structure of the search space. This approach offers a trade-off between the cost of lattice reduction and the complexity of the search part which allows to speed up the attack. We implement a script that estimates the complexity of the original dual attack and of our hybrid method for various parameters under three different cost models for lattice reduction and show that current (as of March 2020) security level of the TFHE scheme should be re-evaluated according to the proposed improvement.

M. Jean-Claude Bajard Prof., Sorbonne Université, IMJ

M. Pierre-Alain Fouque Prof., Université de Rennes (rapporteur)

M. Louis Gobin Prof., UVSQ

M. Antoine Joux Tenured Research Faculty, CISPA Helmholtz Center (directeur de thèse)

M. David Naccache Prof., ENS (rapporteur)

Mme. Annick Valibouze Prof., Sorbonne Université, LIP6

Mme. Brigitte Vallée DR, Université Caen, GREYC