Paper 2024/787 Original: eprint.iacr.org/2024/787 ↗
A new attack against search-LWE using Diophantine approximations
Abstract
In this paper, we present a new attack against search-LWE instances with a small secret key. The method consists of lifting the public key to $\mathbb Z$ and finding a good Diophantine approximation of the public key divided by the modulus $a$. This is done using lattice reduction algorithms. The lattice considered, and the approximation quality needed is similar to known decision-LWE attacks for small keys. However, we do not require an in-depth analysis of the reduction algorithm (any reduction algorithm giving small enough vectors is enough for us), and our method solves the search problem directly, which is harder than the decision problem.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2024-05-22: last updated
- 2024-05-22: published
- Short URL
- https://ia.cr/2024/787
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2024/787,
author = {Robin Frot and Daniel Zentai},
title = {A new attack against search-LWE using Diophantine approximations},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/787},
year = {2024},
url = {https://eprint.iacr.org/2024/787}
}