Paper 2023/777

Too Many Hints - When LLL Breaks LWE

Alexander May, Ruhr University Bochum
Julian Nowakowski, Ruhr University Bochum

All modern lattice-based schemes build on variants of the LWE problem. Information leakage of the LWE secret $\mathbf{s} \in \mathbb{Z}_q^n$ is usually modeled via so-called hints, i.e., inner products of $\mathbf{s}$ with some known vector. At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE security loss. We introduce a new methodology to integrate and combine an arbitrary number of perfect and modular in a single stroke. As opposed to DDGR's, our methodology is significantly more efficient in constructing lattice bases, and thus easily allows for a large number of hints up to cryptographic dimensions -- a regime that is currently impractical in DDGR's implementation. The efficiency of our method defines a large LWE parameter regime, in which we can fully carry out attacks faster than DDGR can solely estimate them. The benefits of our approach allow us to practically determine which number of hints is sufficient to efficiently break LWE-based lattice schemes in practice. E.g., for mod-$q$ hints, i.e., modular hints defined over $\mathbb{Z}_q$, we reconstruct \Kyber-512 secret keys via LLL reduction (only!) with an amount of $449$ hints. Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension $n$ roughly $n/2$ perfect hints. E.g., we reconstruct via LLL reduction \Kyber-512 keys with merely $234$ perfect hints. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints. For mod-$q$ hints our method is extremely efficient, e.g., taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512. For perfect hints in dimension 512, we require around 3 hours. Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in ASIACRYPT 2023
LWE with HintsPartial Key ExposurePQC Standards
Contact author(s)
alex may @ rub de
julian nowakowski @ rub de
2023-09-20: revised
2023-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander May and Julian Nowakowski},
      title = {Too Many Hints -  When LLL Breaks LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/777},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.