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

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 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\left(h \log _{2} h\right)$ hints, where $h$ denotes the Hamming weight of $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)=\left(2^{15}, 32\right)$, our method requires only 320 approximate/perfect hints to recover the secret key, compared to the 214 perfect/modular hints required by previous methods. For the OpenFHE library with $(n, h)=\left(2^{15}, 192\right)$, we heuristically confirm secret-key recovery via $O\left(h \log _{2} h\right)$ 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$.