cispa_all_3335.pdf (970.1 kB)

On a dual/hybrid approach to small secret LWE

Download (970.1 kB)
conference contribution
posted on 2023-11-29, 18:14 authored by Thomas Espitau, Antoine JouxAntoine Joux, Natalia Kharchenko
In this paper, we investigate the security of the Learning With Error (LWE) problem with small secrets by refining and improv- ing the so-called dual lattice attack. More precisely, we use the dual attack on a projected sublattice, which allows generating instances of the LWE problem with a slightly bigger noise that correspond to a frac- tion of the secret key. Then, we search for the fraction of the secret key by computing the corresponding noise for each candidate using the newly constructed LWE samples. As secrets are small, 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. Besides, we aim at providing a sound and non-asymptotic analysis of the techniques to enable its use for practical selection of se- curity parameters. As an application, we revisit the security estimates of some fully homomorphic encryption schemes, including the Fast Fully Homomorphic Encryption scheme over the Torus (TFHE) which is one of the fastest homomorphic encryption schemes based on the (Ring-)LWE problem. We provide an estimate of the complexity of our method for various parameters under three different cost models for lattice reduc- tion and show that the security level of the TFHE scheme should be re-evaluated according to the proposed improvement (for at least 7 bits for the most recent update of the parameters that are used in the imple- mentation).


Preferred Citation

Thomas Espitau, Antoine Joux and Natalia Kharchenko. On a dual/hybrid approach to small secret LWE. In: International Conference on Cryptology in India (Indocrypt). 2020.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on Cryptology in India (Indocrypt)

Legacy Posted Date


Open Access Type

  • Green


@inproceedings{cispa_all_3335, title = "On a dual/hybrid approach to small secret LWE", author = "Espitau, Thomas and Joux, Antoine and Kharchenko, Natalia", booktitle="{International Conference on Cryptology in India (Indocrypt)}", year="2020", }

Usage metrics


    No categories selected


    Ref. manager