Paper 2025/1128 Original: eprint.iacr.org/2025/1128 ↗

Solving LWE with Independent Hints about Secret and Errors

Abstract

At CRYPTO 2020, Dachman-Soled et al. introduced a framework for to analyze the security loss of Learning with Errors ($\text{LWE}$), which enables the incremental integration of leaked hints into lattice-based attacks. Later Nowakowski and May at ASIACRYPT 2023 proposed a novel method capable of integrating and combining an arbitrary number of both perfect and modular hints for the LWE secret within a unified framework, which achieves better efficiency in constructing the lattice basis and makes the attacks more practical. In this paper, we first consider solving LWE with independent hints about both the secret and errors. Firstly, we introduce a novel approach to embed the hints for secret into the $\text{LWE}$ lattice by just matrix multiplication instead of the LLL reduction as in Nowakowski and May's attack, which further reduces the time complexity to construct the lattice basis. For example, given 234 perfect hints about CRYSTALS-KYBER 512, our method reduces the running time from 2.16 hours to 0.35 hours. Secondly, we show how to embed the hints about errors into the obtained lattice basis.