Paper 2023/1162

Reduction of Search-LWE Problem to Integer Programming Problem

Masaaki Shirase, Future University Hakodate
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.

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)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
LWE problemInteger programming problemLattice-based cryptographyLinear algebraFinite field
Contact author(s)
shirase @ fun ac jp
History
2023-08-10: last of 2 revisions
2023-07-28: received
See all versions
Short URL
https://ia.cr/2023/1162
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.