Paper 2020/515

On a hybrid approach to solve binary-LWE

Thomas Espitau and Antoine Joux and Natalia Kharchenko

Abstract

In this paper,we investigate the security of binary secret LearningWithError (LWE). To do so, we improve the classical dual lattice attack. 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 secrets are binary vectors, we can perform the search step very efficiently by exploiting the re- cursive 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. As an ap- plication we revisit the security estimates of the Fast Fully Homomorphic Encryption scheme over the Torus (TFHE) which is one of the fastest homomorphic encryption schemes based on the LWE problem. We provide an estimate of the complexity of our method for various parameters under three different cost models for lattice reduction and show that security level of the TFHE scheme should be re-evaluated according to the proposed improvement. Our estimates show that the cur- rent security level of the TFHE scheme should be reduced by 10 bits for the parameters proposed in the latest version of the scheme and by 7 bits for the recent update of the parameters that are used in the implementation, available online.