Paper 2023/1162
Reduction of SearchLWE Problem to Integer Programming Problem
Abstract
Let $(A,t)$ be an instance of the searchLWE 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 LWEsearch 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.
Note: Typos are fixed. 1) At Eqs.(10), (11), (12), (13), w_{i,j} => w_{j,i} 2) In page 7 and at Eq.(13), Inequalities with respect to f_i had typos.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 LWE problemInteger programming problemLatticebased cryptographyLinear algebraFinite field
 Contact author(s)
 shirase @ fun ac jp
 History
 20230810: last of 2 revisions
 20230728: received
 See all versions
 Short URL
 https://ia.cr/2023/1162
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1162, author = {Masaaki Shirase}, title = {Reduction of Search{LWE} Problem to Integer Programming Problem}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1162}, year = {2023}, url = {https://eprint.iacr.org/2023/1162} }