A new attack against search-LWE using Diophantine approximations

Robin Frot; Daniel Zentai

Paper 2024/787

A new attack against search-LWE using Diophantine approximations

Robin Frot

, xtendr

Daniel Zentai

, xtendr

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.

Note: V 1.0

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: FHE LWE Lattices
Contact author(s): robin frot @ xtendr io
daniel zentai @ xtendr io
History: 2024-05-24: approved; 2024-05-22: received; See all versions
Short URL: https://ia.cr/2024/787
License: CC BY

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},
      note = {\url{https://eprint.iacr.org/2024/787}},
      url = {https://eprint.iacr.org/2024/787}
}