Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Lattice-based cryptographyLWE with HintsPrimal Lattice Reduction Attack
- Contact author(s)
-
luqian @ amss ac cn
fengyansong @ amss ac cn
panyanbin @ amss ac cn - History
- 2025-06-17: revised
- 2025-06-15: received
- See all versions
- Short URL
- https://ia.cr/2025/1128
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1128,
author = {Qian Lu and Yansong Feng and Yanbin Pan},
title = {Solving {LWE} with Independent Hints about Secret and Errors},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1128},
year = {2025},
url = {https://eprint.iacr.org/2025/1128}
}
