Paper 2026/1081

From Perfect to Approximate Hints: Efficient LWE Secret Recovery Leveraging Low Hamming Weight

Abstract

The Learning With Errors (LWE) problem is a cornerstone of lattice-based cryptography and underpins the security of numerous cryptographic schemes. To enhance efficiency, practitioners often employ sparse secrets in LWE, where the secret vector $\mathbf{s}$ has a significantly lower Hamming weight than its dimension $n$. While this approach improves performance, it raises security concerns, particularly against side-channel attacks that can leak partial information, or “hints,” about the secret key. In this paper, we revisit the LWE with side information framework on sparse ternary secrets, focusing on approximate/perfect hints of the form $(\mathbf{v}, l)$ satisfying $l = \langle \mathbf{v}, \mathbf{s} \rangle + e$, where $e$ is a small error term, or $l = \langle \mathbf{v}, \mathbf{s} \rangle$. While previous results needed about $n/2$ perfect or modular hints to break LWE in polynomial time, we show empirically, supported by a conservative lower-bound analysis under the Gaussian Approximation Assumption (GAA), that the task can be accomplished with only $O(h \log_2 h)$ hints, where $h$ denotes the Hamming weight of $\mathbf{s}$. We demonstrate the effectiveness of our algorithm on practical parameter sets used in Fully Homomorphic Encryption (FHE) schemes. For instance, for a sparse-secret FHE bootstrapping regime with $(n, h) = (2^{15}, 32)$, our method requires only 320 approximate/perfect hints to recover the secret key, compared to the $2^{14}$ perfect/modular hints required by previous methods. For the OpenFHE library with $(n, h) = (2^{15}, 192)$, we heuristically confirm secret-key recovery via $O(h \log_2 h)$ perfect hints; approximate hints have not yet been validated in this setting. After collecting the necessary hints, our algorithm recovers the secret key in polynomial time in dimension $n$.