CryptoDB
Refined Attack on LWE with Hints: Constructing Lattice via Gaussian Elimination
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | This work presents an improved attack on LWE with hints. Our attack follows a generic and efficient framework that converts an arbitrary number of perfect hints, modular hints, and approximate hints into a problem on lattice. Based on the approach, we give a complexity estimator for solving LWE with hints, and exploit the ``too many hints'' regime with a new method of converting this phenomenon to lattice. The essential component of our work is an improved hint integration method, which decomposes LWE with hints into the SIS part and the LWE part. This new perspective on LWE with hints offers an insight on how hints help us solve the problem, and motivates us to efficiently reduce its dimension via Gaussian elimination instead of LLL reduction. We demonstrate the performance of our attack on LWE instances up to cryptographic dimensions. Experiments show that our method runs significantly faster than the method proposed by May and Nowakowski at Asiacrypt 2023. For example, given 200 perfect hints about CRYSTALS-KYBER 512, our method reduces the running time from 7 hours to 1 hour. When we use our method to solve NTRU, we achieve a 10 times acceleration given 200-350 perfect hints. Furthermore, our method requires fewer hints to carry out successful attacks in the too many hints regime. These results stresses the importance to protect post-quantum cryptography schemes against leakage. |
BibTeX
@inproceedings{crypto-2025-35557,
title={Refined Attack on LWE with Hints: Constructing Lattice via Gaussian Elimination},
publisher={Springer-Verlag},
author={Jinzheng Cao and Haodong Jiang and Qingfeng Cheng},
year=2025
}