KHARCHENKO Natalia
Supervision : Antoine JOUX
Lattice algorithms and latticebased cryptography
Latticebased cryptography is an area of research that studies the construction of tools and protocols for secure communication based on hard lattice problems. Latticebased cryptography is one of the most promising candidates
for postquantum secure communication due to its conjectured security against quantum attacks and algorithmic efficiency. Another attractive feature of latticebased 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 latticebased 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 ndimensional 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 tradeoff 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 reevaluated according to the proposed improvement.
Defence : 05/27/2020
Jury members :
M. JeanClaude Bajard Prof., Sorbonne Université, IMJ
M. PierreAlain 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
2020 Publications

2020
 N. Kharchenko : “Algorithmes de réseau et cryptographie basée sur les réseaux”, thesis, phd defence 05/27/2020, supervision Joux, Antoine (2020)
 Th. Espitau, A. Joux, N. Kharchenko : “On a Dual/Hybrid Approach to Small Secret LWE”, Progress in Cryptology – INDOCRYPT 2020, vol. 12578, Lecture Notes in Computer Science, Bangalore, India, pp. 440462, (Springer), (ISBN: 9783030652777) (2020)