Quantum Search-to-Decision Reduction for the LWE Problem
Open Access
- 1 February 2025
- journal article
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- Vol. E108.A (2) , 104-116
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. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. 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 is incomparable to the classical reduction in terms of sample complexity and query complexity. 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 ℤq where q is a prime. In short, this theorem states that, if a hardcore predicate a · s (mod q) can be predicted with probability distinctly greater than 1/q with respect to a uniformly random a ∈ ℤnq, then it is possible to determine s ∈ ℤnq.Keywords
This publication has 23 references indexed in Scilit:
- Quantum Search-to-Decision Reduction for the LWE Problem2023
- Constructive Post-Quantum Reductions2022
- Public-Key Encryption Schemes with Auxiliary Inputs2010
- Efficient Lattice (H)IBE in the Standard Model2010
- Bonsai Trees, or How to Delegate a Lattice Basis2010
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems2009
- A Framework for Efficient and Composable Oblivious Transfer2008
- Cryptography with Constant Input Locality2007
- Parallel and Concurrent Security of the HB and HB + Protocols2006
- A Quantum Goldreich-Levin Theorem with Cryptographic Applications2002