Paper 2023/344

Quantum Search-to-Decision Reduction for the LWE Problem

Kyohei Sudo, Osaka University
Masayuki Tezuka, National Institute of Technology
Keisuke Hara, National Institute of Advanced Industrial Science and Technology
Yusuke Yoshida, Tokyo Institute of Technology
Abstract

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only $2$ times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction works with fewer LWE samples compared to the classical reduction that has a high success probability. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over $\mathbb{Z}_q$ where $q$ is prime. In short, this theorem states that, if a hardcore predicate $a\cdot s \pmod q$ can be predicted with probability distinctly greater than $1/q$ with respect to a uniformly random $a\in\mathbb{Z}_q^n$, then it is possible to determine $s\in\mathbb{Z}_q^n$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Learning with errorsSearch-to-decision reductionGoldreich-Levin theorem
Contact author(s)
u358338c @ ecs osaka-u ac jp
tezuka m @ tsuruoka-nct ac jp
hara-keisuke @ aist go jp
yoshida y aw @ m titech ac jp
History
2023-07-16: last of 2 revisions
2023-03-09: received
See all versions
Short URL
https://ia.cr/2023/344
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/344,
      author = {Kyohei Sudo and Masayuki Tezuka and Keisuke Hara and Yusuke Yoshida},
      title = {Quantum Search-to-Decision Reduction for the {LWE} Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/344},
      year = {2023},
      url = {https://eprint.iacr.org/2023/344}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.