Welcome to the resource topic for 2023/344
Title:
Quantum Search-to-Decision Reduction for the LWE Problem
Authors: Kyohei Sudo, Masayuki Tezuka, Keisuke Hara, Yusuke Yoshida
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.
ePrint: https://eprint.iacr.org/2023/344
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .