Paper 2023/344
Quantum Search-to-Decision Reduction for the LWE Problem
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)
- 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
-
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} }