Welcome to the resource topic for 2024/787
Title:
A new attack against search-LWE using Diophantine approximations
Authors: Robin Frot, Daniel Zentai
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.
ePrint: https://eprint.iacr.org/2024/787
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .