Welcome to the resource topic for 2023/1162
Title:
Reduction to Search-LWE Problem to Integer Programming Problem
Authors: Masaaki Shirase
Abstract:Let (A,t) be an instance of the search-LWE problem, where A is a matrix and t is a vector. This paper constructs an integer programming problem using A and t, and shows that it is possible to derive a solution of the instance (A,t) (perhaps with high probability) using its optimal solution or its tentative solution of small norm output by an integer programming solver. In other words, the LWE-search problem can be reduced to an integer programming problem. In the reduction, only basic linear algebra and finite field calculation are required. The computational complexity of the integer programming problem obtained is still unknown.
ePrint: https://eprint.iacr.org/2023/1162
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 .