Welcome to the resource topic for 2023/777
Title:
Too Many Hints - When LLL Breaks LWE
Authors: Alexander May, Julian Nowakowski
Abstract: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 (random, but 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, 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 impractical in DDGR. 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. A key component of our new method is dimension reduction of \mathbf s, which significantly reduces LWE security.
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. 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. For Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we need 452, 622, 702 and 876 modular hints, respectively.
Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension n roughly n/2 perfect hints. Namely, we reconstruct via LLL reduction Kyber-512 keys with merely 234 perfect hints. For secret keys of Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we require 233, 332, 390 and 463 perfect hints, respectively. We find such a small amount of perfect hints quite remarkable. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints.
For mod-q hints our method is extremely efficient, taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512, 40 mins for dimensions 701 and 768, and less than 10 hours for dimension 1024. For perfect hints we require around 3 hours (dim 512), 11 hours (dim 701), 1 day (dim 768), and one week (dim 1024).
Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.
ePrint: https://eprint.iacr.org/2023/777
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .