Welcome to the resource topic for 2023/1162
Reduction to Search-LWE Problem to Integer Programming Problem
Authors: Masaaki ShiraseAbstract:
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.
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 .