KHARCHENKO Natalia

PhD student at Sorbonne University
Team : ALMASTY
https://lip6.fr/Natalia.Kharchenko

Supervision : Antoine JOUX

Lattice algorithms and lattice-based cryptography

Lattice-based cryptography is an area of research that studies the construction of tools and protocols for secure communication based on hard lattice problems. Lattice-based cryptography is one of the most promising candidates for post-quantum secure communication due to its conjectured security against quantum attacks and algorithmic efficiency. Another attractive feature of lattice-based cryptography is a wide range of available constructions which includes even Fully Homomorphic Encryption (FHE) schemes. This thesis studies algorithms for solving hard lattice problems and their application to evaluating security of lattice-based cryptographic constructions. This thesis has two parts.

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.


Phd defence : 05/27/2020

Jury members :

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

Departure date : 05/29/2020

2020 Publications