Reduction of Search-LWE Problem to Integer Programming Problem

Masaaki Shirase

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 problem Integer programming problem Lattice-based cryptography Linear algebra Finite 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: 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},
      note = {\url{https://eprint.iacr.org/2023/1162}},
      url = {https://eprint.iacr.org/2023/1162}
}