Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering

We show polynomial-time quantum algorithms for the following problems:
() Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant.
() Extrapolated dihedral coset problem (EDCP) with certain parameters.
(*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions.
The SIS, EDCP, and LWE problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for those variants.
Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contributions are introducing a filtering technique and solving LWE given LWE-like quantum states with interesting parameters.

Related papers

Yuehua Chen, Qipeng Liu, Mark Zhandry

We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.

arXiv:2108.11015Aug 25, 20215 citations

Efficient Quantum Public-Key Encryption From Learning With Errors

Javad Doliskani

Our main result is a quantum public-key encryption scheme based on the Extrapolated Dihedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For polynomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size $\tilde{O}(n)$ qubits. The key generation and decryption algorithms require $\tilde{O}(n)$ qubit operations while the encryption algorithm takes $O(1)$ qubit operations.Our main result is a quantum public-key encryption scheme based on the Extrapolated Dihedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For polynomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size $\tilde{O}(n)$ qubits. The key generation and decryption algorithms require $\tilde{O}(n)$ qubit operations while the encryption algorithm takes $O(1)$ qubit operations.

arXiv:2105.12790May 26, 20212 citations

A reduction from LWE problem to dihedral coset problem

Fada Li, Wan‐Su Bao, Xiang-Qun Fu +2 more

Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.

arXiv:1305.3769May 16, 20130 citations

Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$ -th root of unity, let $π=ζ_p-1$ , and write $q=p^t$ and $L=t(p-1)$ . We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$ , where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$ . We exploit the resulting $π$ -adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$ . For every fixed prime $p$ and modulus $q=p^t$ , our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$ , using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$ . This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.

quant-pharXiv:2609.34996Sep 29, 20260 citations

A subexponential-time quantum algorithm for LWE problem

Fada Li, Wan‐Su Bao, Xiang-Qun Fu +2 more

May 16, 20130 citations

The quantum decoding problem : achievability bounds and applications to finding short codewords

Agathe Blanvillain

This thesis lies within the framework of post-quantum cryptography, whose goal is to conceive cryptosystems that resist classical and quantum attacks. Our focus here is on the Decoding Problem (DP) and the Short Codeword Problem (SCP) in code-based cryptography. We study here how quantum algorithms can exploit the structure of these problems. In a first part, we generalized the information-theoretic achievability threshold for the Quantum Decoding Problem (QDP) to all memoryless noise models. By combining this result with Regev's reduction, we obtain a quantum algorithm that samples dual codewords whose weight approaches the minimum at the achievability threshold. In a second part, we formulate a general framework for adapting to coding theory the lattice reduction from Learning With Errors (LWE) to the Extrapolated Dihedral Coset Problem (EDCP). We study this framework in the binary Hamming case and show that the resulting parameter regime can already be decoded classically in polynomial time.This thesis lies within the framework of post-quantum cryptography, whose goal is to conceive cryptosystems that resist classical and quantum attacks. Our focus here is on the Decoding Problem (DP) and the Short Codeword Problem (SCP) in code-based cryptography. We study here how quantum algorithms can exploit the structure of these problems. In a first part, we generalized the information-theoretic achievability threshold for the Quantum Decoding Problem (QDP) to all memoryless noise models. By combining this result with Regev's reduction, we obtain a quantum algorithm that samples dual codewords whose weight approaches the minimum at the achievability threshold. In a second part, we formulate a general framework for adapting to coding theory the lattice reduction from Learning With Errors (LWE) to the Extrapolated Dihedral Coset Problem (EDCP). We study this framework in the binary Hamming case and show that the resulting parameter regime can already be decoded classically in polynomial time.

Sep 24, 20260 citations

\tilde{O}(n)

qubits. The key generation and decryption algorithms require

\tilde{O}(n)

qubit operations while the encryption algorithm takes

O(1)

qubit operations.

ζ_p

be a primitive

p

-th root of unity, let

π=ζ_p-1

, and write

q=p^t

and

L=t(p-1)

. We work over

R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)

, where the isomorphism follows from the total ramification identity

(p)=(π)^{p-1}

. We exploit the resulting

π

-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo

π^{L},π^{L-1},\ldots,π

. For every fixed prime

p

and modulus

q=p^t

, our algorithm solves the CCP in time and sample complexity

2^{O_p(\log n\log q)}

, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when

q=\text{poly}(n)

. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.