Meet-LWE with Hints: Solving Ternary LWE with Information Leakage

The Learning with Errors (LWE) problem is a cornerstone of post-quantum cryptography, and its hardness has been extensively studied via various cryptanalytic approaches. At CRYPTO 2021, May introduced the Meet-LWE attack targeting ternary LWE—a variant increasingly adopted in lattice-based cryptographic designs. This attack leverages the small-norm property of ternary secrets to launch efficient combinatorial attacks. In this work, we enhance the Meet-LWE attack by incorporating side-channel leakage, a critical concern in real-world cryptanalysis. Our approach draws inspiration from the work of Dachman-Soled et al., which models LWE-related leakage as “hints”. Specifically, we reconstruct the Meet-LWE search tree using a novel hint-based filtering mechanism. Unlike the original filtering approach, which requires explicit guessing of r unknown coordinates of the error vector, the hint-based technique achieves a speedup of approximately \(3^{r/2}\) times. Our complexity analysis indicates a reduction of approximately 10 bits in the time cost. Building on the hint-based tree structure, we further improve other Meet-LWE variants: ternary Meet-LWE search tree with hints and quantum Meet-LWE with hints. Overall, our results highlight the versatility of hints as a tool for both lattice-based and combinatorial cryptanalysis, motivating further research into hint-augmented attack strategies.