Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
arXiv:2609.34996v1 [quant-ph] 28 Sep 2026
Mathias Boucher, Pierre-Alain Fouque, and Yixin Shen Univ Rennes, Inria, CNRS, IRISA, Rennes, France
Abstract. 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 = pt and L = t(p − 1). We work over Rq = Zq [ζp ] ∼ = 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 , . . . , π. For every fixed prime p and modulus q = pt , our algorithm solves the CCP in time and sample complexity 2Op (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 = 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 quasipolynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.
Keywords: Learning With Errors, Dihedral Coset Problem, Extrapolated Dihedral Coset Problem, Hidden Subgroup Problem, Cyclotomic Rings, Kuperberg’s algorithm.
1
Introduction
The Learning With Errors problem (LWE), introduced by Regev in [16], is a cornerstone of post-quantum cryptography. In its search form, LWE asks to recover a secret vector s ∈ Znq from noisy linear equations bi = ⟨ai , s⟩ + ei mod q,
where the vectors ai are uniform in Znq and the errors ei are sampled from a prescribed narrow distribution. The importance of LWE stems both from its versatility in cryptographic constructions and from quantum worst-case-toaverage-case reductions relating it to fundamental lattice problems [16,17]. Quantum coset problems provide another perspective on the complexity of lattice problems. In earlier work, Regev established a connection between unique shortest-vector problems and the Dihedral Hidden Subgroup Problem [13]. Its coset-state formulation, known as the Dihedral Coset Problem (DCP), asks to recover a secret s ∈ Znq from states of the form 1 √ (|0⟩ |x⟩ + |1⟩ |x + s⟩) , 2 where x ∈ Znq is uniformly random. DCP is particularly appealing because its input states are exact coset states of order-two subgroups of a generalized dihedral group. Childs and van Dam considered in [8] the generalized hidden shift problem. It consists in finding a hidden shift s ∈ Zq given quantum samples of the form M −1
1 X √ |j⟩ |xi + js⟩ M j=0 for randomly chosen xi ∈ Zq and an integer M . They provided an efficient quantum algorithm based on "pretty good measurement" when M is large with respect to q (M = q ϵ for a constant ϵ). Brakerski, Kirshanova, Stehlé, and Wen subsequently introduced the Extrapolated Dihedral Coset Problem (EDCP) [5]. In EDCP, the DCP state is replaced by X
f (j) |j⟩ |x + js⟩
j
for a prescribed amplitude function f . They proved that suitable Gaussian and uniform variants of EDCP are equivalent to LWE under quantum polynomial-time reductions, up to parameter losses. This equivalence provides a useful quantum formulation of the computational content of LWE. However, except in particular cases, the set of translations {(js, j) : j ∈ supp(f )} does not form a subgroup. General EDCP states therefore do not retain the exact hidden-subgroup structure of DCP. Closely related quantum formulations arise by encoding the LWE error distribution in the amplitudes of a quantum state. In the S |LWE⟩ problem introduced by Chen, Liu, and Zhandry [7], one is given uniformly random vectors ai ∈ Znq , together with quantum states of the following form 2
X
f (e) |⟨ai , s⟩ + e mod q⟩ ,
e∈Zq
and the objective is again to recover s. Applying a quantum Fourier transform moves the secret into a phase and produces states closely related to phase formulations of EDCP. Quantum sieving. DCP admits subexponential-time quantum algorithms due to Kuperberg [11,12,9] and Regev [15]. At a high level, these algorithms first √ ⟨y,s⟩ transform coset states into phase-states of the form 1/ 2(|0⟩ + ωq |1⟩), with a label y which is uniform and known. They then repeatedly combine phase-states whose labels agree on selected blocks, thereby producing new states with increasingly divisible labels. The process eventually isolates enough information to recover the secret. Recently, Bai, Jangir, Kirshanova, Ngo, and Youmans developed a quasipolynomial-time quantum algorithm for EDCP over power-of-two moduli [2] inspired by the "Simon-meets-Kuperberg" algorithm of Bonnetain and NayaPlasencia [4]. Their algorithm uses a quasi-polynomial number of quantum samples and polynomial quantum space. It also yields a quasi-polynomial-time algorithm for Gaussian-S |LWE⟩ over power-of-two moduli. The algorithm exploits the following sequence of ideals: Z2t ⊃ 2Z2t ⊃ · · · ⊃ 2t−1 Z2t , combining binary phase states to increase the regularity of their labels one level at a time. Chailloux and Hermouet [6] recovered the same result using a reduction from S |LWE⟩ to the Inhomogeneous Short Integer Solution problem (ISIS). Although using a different technique, they encountered the same bottleneck as in [2] when trying to generalize the result to other prime-power moduli. Hidden-shift problems such as DCP can be viewed as hidden-subgroup problems. Thus, in parallel with [2], Imran and Ivanyos [10] generalized the “Simonmeets-Kuperberg” algorithm [4] to a particular class of groups, namely nilpotent groups. These are groups for which there exists a subgroup chain allowing us to use the same sieving techniques as in the case where we have the 2-adic chain mentioned in the paragraph just above. However, Imran and Ivanyos’ result cannot be directly applied to EDCP, since it does not have the structure of a hidden subgroup; nor can it be applied to a DCP with parameters (n, q) for q that is not a power of two, as stated in the following exercise in Rotman [18, Exercise 5.41]: The dihedral group of order 2q is nilpotent if and only if q is a power of two. One might therefore ask whether there exists a specific nilpotent group that can be related to EDCP and DCP for any prime power q. This is what motivates the introduction of a new coset problem, which we have named the Cyclotomic Coset Problem. 3
We emphasize that our algorithms are not a direct application of Imran and Ivanyos [10]. The exact algorithm of Imran and Ivanyos assumes access to a unitary U implementing state preparation and to its inverse U −1 . In our model, the input consists only of independent quantum samples: neither the preparation circuit nor its inverse is available. Their exact theorem therefore does not apply directly. Moreover, the nilpotency class t(p − 1) of our cyclotomic group Gn,q,p := Rqn ⋊ Fp need not be constant. We instead use their zero-sum algorithm and describe the quantum state transformations explicitly, accounting for sample consumption and working space. 1.1
Cyclotomic Coset
Let p be a prime, let q = pt , and let ζp be a primitive p-th root of unity. We consider the cyclotomic ring Rq := Zq [ζp ]. Multiplication by ζp defines an action of the additive group Fp on Rq . This allows us to define the semidirect product Gn,q,p := Rqn ⋊ Fp with multiplication (x, j)(y, k) = x + ζpj y, j + k . Consequently, for every s ∈ Rqn , the set Hs := {(λj s, j) : j ∈ Fp },
with λj =
j−1 X
ζpi ,
i=0
is a subgroup of Gn,q,p . Equivalently, it is the cyclic subgroup generated by (s, 1). The subgroup order follows from the identity λp = 1 + ζp + · · · + ζpp−1 = 0 shows that Hs has order p. A left coset of Hs gives rise to the quantum state 1 X |ϕx,s ⟩ = √ |j⟩ |x + λj s⟩ , p j∈Fp
where x ∈ Rqn is uniformly random. We define the Cyclotomic Coset Problem (CCP) as the problem of recovering s from independent states of this form. When p = 2, we have ζ2 = −1,
λ0 = 0,
λ1 = 1,
and Rq = Zq . Hence CCP specializes exactly to DCP. We show that Gn,q,p is a nilpotent group, in Lemma 2 and the associated hidden subgroup problem is close to a generalized hidden-shift problem. Note that our version of (CCP) assumes that the secret s is contained in Znq , a restricted subset of Rqn . This choice is justified by the introduction of a cyclotomic version of LWE (CyLWE), which also requires a restricted secret. 4
1.2
Organization and contributions
Our work makes several contributions towards the study of coset problems over cyclotomic rings and their quantum algorithms. – We first introduce new computational problems over cyclotomic rings, namely CyLWE and CCP, which can be viewed as analogues of LWE and DCP, respectively. We establish equivalences between these problems when p is constant. – We define a quantum Fourier transform over cyclotomic rings, which allows us to give a rigorous definition of phase-state samples over such rings, in analogy with Kuperberg’s phase states. – We construct a sieving algorithm for CCP that exploits these new phase-state samples. Our algorithm can be viewed as a specific instance of the framework introduced by Imran and Ivanyos [10]. – We show that, for a certain range of parameters, our algorithm solves uniform EDCP and S |LWE⟩ in quasi-polynomial time, given a quasi-polynomial number of samples. This generalizes the results of [2] from power-of-two moduli to a broader setting.
LWEn,q,α
[5]
Proposition 4 CyLWEn,q,p,α
DCPn,q
[2] for q = 2t
Proposition 5 CCPn,q,p
Algorithm 1, quasi-polynomial
Fig. 1. Overview representing the different contributions of the paper. Note that we are considering an n-dimensional version of DCP. Moreover, [2] shows that there exists a reduction from EDCPn,q,M to DCPn,q .
2
Preliminaries
Asymptotic notations. We define the notations O(·), Ω(·), poly(·) in the standard way, with respect to the dimension n of the lattice and the security parameter κ. We say a function f : N → (0, 1] is negligible if for all positive polynomials p(·) there exists an integer N such that, ∀n > N, f (n) < 1/p(n). We c say a positive function is quasipolynomial if it is upper bounded by 2O(log n) for some constant c ≥ 1. 2.1
Cyclotomic ring
We introduce the notation and definitions associated with the cyclotomic ring used throughout the paper. Let p be a prime number and let q = pt with t ≥ 1. 5
We denote by ζp a primitive p-th root of unity, and define the cyclotomic field K = Q[ζp ] as an extension of Q generated by ζp . Equivalently, the cyclotomic field can be viewed as the quotient Q[X]/(Φp (X)) where Φp (X) := 1 + X + · · · + X p−1 is the p-th cyclotomic polynomial. Hence we denote R := Z[ζp ] the ring of integers of K. We write Rq = R/qR. We can view Rq as Zq [ζp ] = Zq [X]/(Φp (X)), a cyclotomic extension of Zq . This allows us to represent elements of Rq by their coefficients with respect to the basis (1, ζp , . . . , ζpp−2 ), ι : Zp−1 → Rq , q
(x0 , . . . , xp−2 ) 7→
p−2 X
xi ζpi
i=0
and we can state that ι is an isomorphism of Zq -modules. Using the same arguments as in the previous paragraph, one can show that R := Z[ζp ] and Zp−1 are isomorphic as Z-modules. This directly induces a notion of distance on the cyclotomic ring. Indeed, for e ∈ Z[ζp ], we use the slight abuse of notation ∥e∥2 to denote the ℓ2 -norm of its representation in Zp−1 with respect to the basis (1, ζp , . . . , ζpp−2 ). Finally, we denote by ⟨·, ·⟩ the symmetric bilinear form on Rqn such that, for x = (x1 , . . . , xn ) and y = (y1 , . . . , yn ) in Rqn , we have ⟨x, y⟩ :=
n X
xi yi .
i=1
π-decomposition. The element π = ζp − 1 is a prime element of R, and there exists u0 ∈ R× invertible such that p = u0 π p−1 , and therefore q = ut0 π L with L = t(p − 1), we say that p is ramified. Consequently, the two quotient rings are canonically isomorphic: Rq = R/qR ∼ = R/π L R. For this reason, we will sometimes use the abusive notation RL to talk about RπL . We have |Rk | = pk : multiplication by π k−1 identifies R/πR with π k−1 R/π k R, so each successive quotient has p elements. This will allow us to consider intermediate quotient rings that would be difficult to represent without the π-decomposition: Rq = RL → RL−1 → · · · → R1 = Fp . Field trace. The field trace corresponds to the linear map Tr : K → Q. More precisely, suppose K/Q is a Galois extension and let x be an element of K. Then the trace of x is the sum of all Galois conjugates of x: X Tr(x) = σ(x). σ∈Gal(K/Q)
6
Let K = Q(ζp ) be a cyclotomic extension of Q. The trace is the linear map from K to Q such that Tr(ζpk ) = −1
Tr(1) = p − 1,
for all 1 ≤ k ≤ p − 1.
This follows from the fact that Gal(K/Q) = {σu ∈ Aut(K) : σu (ζp ) = ζpu , u ∈ F× p }. We immediately see that Tr(1) = p − 1. For 1 ≤ k ≤ p − 1, we obtain Tr(ζpk ) =
X
σu (ζpk ) = ζp + · · · + ζpp−1 = −1.
u∈F× p
2.2
Lattices and cyclotomic lattices
Discrete gaussian distribution. For any r > 0 and p > 2, we define the Gaussian function ρr (x) := exp −π∥x∥22 /r2 for x ∈ Rn . For x ∈ Rqn , we also use the abusive notation ρr (x) to denote the quantity ρr (ι(x)) with ι(x) ∈ Rn(p−1) . For an n-dimensional lattice Λ, we write DΛ,r for the discrete Gaussian distribution over Λ with density proportional to ρr (·). For the coefficient lattice Zn(p−1) , the Gaussian weight factors over coordinates, so the resulting distribution is a product of independent one-dimensional discrete Gaussians [1]. This factorization is not asserted for arbitrary lattices. We also extend the definition of Gaussian distribution to Rn by considering its injection in Rn(p−1) related to the basis (1, ζp , . . . , ζpp−2 ). The tails of a Gaussian distribution are negligible compared to its central mass. Lemma 1 ([3], Lemma 1.5). For any n-dimensional lattice Λ and r > 0, √ ρr Λ \ Bn (0, n r) < 2−Ω(n) ρr (Λ). Note that this result holds for cyclotomic using their coefficient embedding in Rn(p−1) . 2.3
sublattices
of
Rn
The cyclotomic group
Let p be a prime number and q = pt a power of p. We call ζp a primitive p-th root of unity and denote the cyclotomic ring by Rq := Zq [ζp ], and we fix a dimension n ≥ 1. We are interested here in the group Gn,q,p = Rqn ⋊ Fp . This is the group (Rqn ⋊ Fp , ⋆) where the product ⋆ satisfies: (x1 , j1 ) ⋆ (x2 , j2 ) := (x1 + ζpj1 x2 , j1 + j2 ), for x1 , x2 ∈ Rqn and j1 , j2 ∈ Zp One can verify that the internal composition law ⋆ indeed defines a group structure on Gn,q,p . 7
Nilpotent group. Let G be a group. Let A and B be two subgroups of G; we denote by [A, B] the subgroup generated by the commutator [a, b] := aba−1 b−1 with a in A and b in B. We call the lower central series the sequence of subgroups C k (G) defined for every positive integer k by C 1 (G) = G and C k+1 (G) = [G, C k (G)]. We say that G is nilpotent if there exists an integer k such that C k (G) = {e} (the trivial group). Moreover, the nilpotency class of G is the smallest integer k such that C k+1 (G) = {e}. The lemma below allows us to state that the cyclotomic group is a nilpotent group. Lemma 2. Let p be a prime, q = pt with t ≥ 1, and let n ≥ 1 be a dimension. The cyclotomic group Gn,q,p is a nilpotent group, of nilpotency class t(p − 1). Proof. Let G = Rqn ⋊ Fp and L = t(p − 1). We shall show by induction that, for every integer k ≥ 2, C k (G) = π k−1 Rqn ⋊ {0}. In the case k = 2, we have for (x1 , j1 ), (x2 , j2 ) ∈ G: [(x1 , j1 ), (x2 , j2 )] = (1 − ζpj2 )x1 + (ζpj1 − 1)x2 , 0 . Since 1 − ζpj = −π(1 + ζp + · · · + ζpj−1 ), we obtain C 2 (G) ⊆ πRqn ⋊ {0}. Conversely, for every x ∈ Rqn , [(0, 1), (x, 0)] = (πx, 0), (1) hence C 2 (G) = πRqn ⋊ {0}. Now suppose that, for some k ≥ 2, C k (G) = π k−1 Rqn ⋊ {0}. Commuting an element of this subgroup with any element of G multiplies its vector by ζpj − 1, so C k+1 (G) ⊆ π k Rqn ⋊ {0}. Equation (1), applied to x ∈ π k−1 Rqn , proves the reverse inclusion. Finally, (q) = (π L ) gives π L Rqn = 0 and π L−1 Rqn ̸= 0. Therefore C L+1 (G) = {e} and, for L ≥ 2, C L (G) ̸= {e}. If L = 1, G is nontrivial and abelian. In both cases its nilpotency class is exactly L = t(p − 1). ⊔ ⊓ 2.4
Computational problems
Learning with errors problems. We introduce a variable κ to relate all the parameters involved in the definition below. Indeed, n, q, p are functions of κ, but we omit the variable κ for clarity. Definition 1 (Search LWE, [16]). Let p be a prime, q = pt , n be a positive integer, and α > 0. Fix a secret s ∈ Znq . Given ℓ samples of the form (a, b = ⟨a, s⟩ + e mod q) , with a ← U(Znq ) and e ← DZ, αq , denoted by LWEℓn,q,α ,the search LWE problem, asks to recover s ∈ Znq . We now introduce a version of LWE on the cyclotomic ring called CyLWE. The rational-secret restriction and the coefficient error distribution distinguish this problem from the usual Ring-LWE (RLWE) setting discussed in [19]. For fixed p, the ring degree is the constant p − 1, and n is an independent vector dimension. In common RLWE parameter families, the ring degree grows with the security parameter. 8
Definition 2 (Cyclotomic LWE). Let p be a prime, q = pt , n be a positive integer, and α > 0. Fix a secret s ∈ Znq . Consider ℓ samples of the form (a, b = ⟨a, s⟩ + e mod q) , with a ← U(Rqn ) and e ← DR, αq . The cyclotomic LWE problem, denoted by CyLWEℓn,q,p,α , asks to recover s ∈ Znq , given ℓ samples. Hidden subgroup problem. Definition 3 (Hidden Subgroup Problem). Let G be a finite group and X a finite set. Fix H a hidden subgroup of G. Given a function f : G → X that hides H (i.e., f (g) = f (g′) if and only if gH = g′H), provided by means of an oracle using O(log |G| + log |X|) bits, the Hidden Subgroup Problem (HSP) asks to recover a generating set of H. In practice, the oracle used in the HSP is assumed to be the existence of a quantum gate Uf such that |g⟩ |0⟩ 7→ |g⟩ |f (g)⟩. A quantum use of this gate is as follows. First, this consists of generating a quantum superposition of the elements of G and computing f in a second register by means of Uf . 1 X 1 X p |g⟩ |0⟩ → p |g⟩ |f (g)⟩ . |G| g∈G |G| g∈G The second register is then measured. By the hiding promise, the preimage of an output x ∈ X of f can be viewed as a left coset of H, i.e., there exists g0 ∈ G such that f −1 {x} = g0 H. The resulting state is therefore 1 X p |g0 h⟩ . |H| h∈H Thus, a quantum instance that is solved in place of the classical instance of the HSP is stated as follows. Definition 4 (Coset Problem). Let G be a group and H a hidden subgroup. Consider samples of the form 1 X p |gi h⟩ , |H| h∈H with the gi drawn independently and uniformly from G. Given a certain number of samples from G, the Coset Problem asks to recover a subset generating H. For hidden subgroups generated by (s, 1), this gives the dihedral coset problem over Znq ⋊−1 Z2 , and the cyclotomic coset problem over Gn,q,p , respectively. 9
Coset problems. We now introduce two quantum hidden-shift problems over finite rings, namely the Dihedral Coset Problem and its cyclotomic generalization. Initially, the dihedral coset problem was stated over Zq , but [9] discusses the DCP over Znq . We have therefore chosen to state it directly over Znq too. Definition 5 (Dihedral Coset Problem). Let p be a prime, q = pt with t ≥ 1, and n ≥ 1. Fix a secret s ∈ Znq . Consider quantum samples {|ϕk ⟩}ℓ−1 k=0 of the form 1 |ϕk ⟩ = √ (|0⟩ |xk ⟩ + |1⟩ |xk + s⟩) , 2 where the xk are independent uniform elements of Znq . The Dihedral Coset Problem over Znq , denoted by DCPℓn,q,p , asks to recover s ∈ Znq , given ℓ samples. Definition 6 (Cyclotomic Coset Problem). Let p be a prime, q = pt with t ≥ 1, and n ≥ 1. Fix a secret s ∈ Znq . We identify s ∈ Znq with its coordinatewise constant embedding in Rqn . Consider quantum samples {|ϕk ⟩}ℓ−1 k=0 of the form 1 X |ϕk ⟩ = √ |j⟩ |xk + λj s mod q⟩ , p j∈Fp
Pj−1 where λ0 = 0, λj = i=0 ζpi for 1 ≤ j < p, and the xk are independent uniform elements of Rqn . The Cyclotomic Coset Problem, denoted by CCPℓn,q,p , asks to recover s ∈ Znq , given ℓ samples. These problems are closely related to the EDCP introduced in [5]; for p = 2, CCP is DCP and hence uniform EDCP with two branches. Furthermore, it is clear that these two problems are specific variants of the Coset Problem. For DCP, the ambient group is the generalized dihedral group, while CCP uses Gn,q,p . Indeed, λj+k = λj + ζpj λk (indices modulo p), so (s, 1)j = (λj s, j) and Hs = ⟨(s, 1)⟩ has order p. The left coset (x, 0)Hs gives exactly the stated CCP state after swapping registers. 2.5
Quantum Fourier Transform
We briefly recall the definition of the Quantum Fourier Transform and its efficient implementation as a quantum circuit. Definition 7 (Quantum Fourier Transform). Let N ≥ 1 be an integer and let HN be the N -dimensional Hilbert space spanned by the computational basis |0⟩ , . . . , |N − 1⟩. The Quantum Fourier Transform (QFT) over ZN is the unitary operator QFTN defined on the computational basis states by N −1
1 X 2πixy/N QFTN (|x⟩) = √ e |y⟩ , N y=0 and extended to arbitrary states by linearity. 10
∀x ∈ {0, . . . , N − 1},
Lemma 3 ([20], Implementation of the QFT). Let N ≥ 2 and 0 < ε < 1. The quantum Fourier transform QFTN admits a circuit approximation with operator-norm error at most ε using poly(log N, log(1/ε)) elementary gates from a fixed universal gate set. When N is a power of a fixed prime, its ideal radix expansion uses O(log2 N ) constant-dimensional Fourier and controlled-phase gates.
3
Quantum Fourier Transform over cyclotomic rings
In this section, we define the quantum Fourier transform (QFT) on RL = R/π L R and provide an efficient construction of it. We then introduce phase-states, which are quantum states directly obtained from CCP samples using the QFT and which will be useful for designing a sieving algorithm. 3.1
The duality in RL
In this part, we provide an explicit description of the dual of RL and its characters, using the field trace. The characters are indexed by the elements of RL and satisfy several useful properties. Lemma 4. Fix K = Q(ζp ) and let L be a positive integer. The map xy BL : RL × RL → Q/Z, BL (x, y) := Tr mod Z pπ L−1 is a non-degenerate symmetric Z-bilinear form. Proof. Let (ζpi )0≤i≤p−2 be the canonical basis of R. We can show that the family (ej )0≤j≤p−2 of R defined by ej :=
p−j−2 X ζpp−j − ζp = ζp ζpk , π
0 ≤ j ≤ p − 2,
k=0
is also a basis of R: e0 = −1, and ej − ej+1 = ζpp−j−1 for 0 ≤ j < p − 2, so these elements generate the basis 1, ζp , . . . , ζpp−2 . For 0 ≤ i, j ≤ p − 2 we have Tr πp ζpi ej = δi,j . In other words, ((π/p)ej )0≤j≤p−2 is the trace-dual basis of (ζpi )0≤i≤p−2 . This allows us to show, for x, y ∈ R, that Tr
xy pπ L−1
∈ Z for all y ∈ R ⇐⇒ x ∈ π L R,
(2)
because the trace-dual lattice is R∨ = (π/p)R, and the left-hand condition is equivalent to x/(pπ L−1 ) ∈ R∨ . The map BL is well defined: changing either lift by an element of π L R changes the trace by an element of Tr((π/p)R) ⊆ Z. It is symmetric and Z-bilinear, and non-degeneracy follows from (2). ⊓ ⊔ 11
Thanks to this lemma, one can easily define the dual of RL , by indexing the characters by the elements of RL . Proposition 1 (Duality). The map below is an isomorphism: ΦL : R/π L R → Hom (R/π L R, +), C× ,
y 7→ χy ,
where χy : x 7→ exp 2iπ Tr pπxy . For y ∈ R/π L R, we call character of L−1 (RL , +), the map χy : RL → C× . Proof. Since the field trace is linear, ΦL is a group homomorphism. It remains to show that ΦL is a bijection. Because BL from Lemma 4 is non-degenerate, ΦL is injective. Moreover, (RL , +) is a finite group, so it has the same cardinality as its dual. In other words, |RL | = | Hom((RL , +), C× )|. Hence, ΦL is an injection between groups of the same cardinality, so it is an isomorphism. ⊔ ⊓ Several useful properties of characters follow from this definition. Proposition 2 (Properties of the Characters). Let x, y, a, b be elements of RL , let λ ∈ R, and let σu ∈ Gal(K/Q) with u ∈ F× p . The characters of (RL , +) have the properties listed below. 1. (Group homomorphism) χy (a + b) = χy (a)χy (b); 2. (Symmetry) χy (λx) = χ1 (λxy) = χx (λy); 3. (Orthogonality of characters) X 1 χy (x) = δ0,x ; L p L y∈R/π R
4. (Stability under the Galois group) We have χy (x) = χσu (y) π L−1 σu (x/π L−1 ) , where π L−1 σu (x/π L−1 ) ≡ u1−L x (mod πR); 5. (Characters of RL−1 ) For L ≥ 2, the character χπy : RL → C× induces a character on RL−1 . Proof. We prove the above properties one by one. – Properties 1 and 2 follow directly from the definition of ΦL in Proposition 1. 12
– The orthogonality of characters holds trivially when x = 0. Suppose x is not zero. Then there exists z ∈ RL such that χz (x) ̸= 1. Reindexing the character sum gives 1 X 1 X χy (x) = L χy+z (x) L p p y∈RL y∈RL X 1 χy (x) , = χz (x) L p y∈RL
which shows that the sum is zero. – The stability under Galois automorphisms follows from the corresponding stability of the field trace. Let x, y ∈ RL . Since Tr ◦σ = Tr for every σ ∈ Gal(K/Q), the exponent of the character satisfies xy xy = Tr σu Tr pπ L−1 pπ L−1 1 h L−1 x i π σu L−1 σu (y) . = Tr pπ L−1 π Moreover, we note that σu (π)/π ≡ u (mod πR), hence (π/σu (π))L−1 ≡ u1−L (mod πR) and σu (x) ≡ x (mod πR), which concludes the proof of this property. – Finally, the definition of ΦL in Proposition 1 gives xy xπy = exp 2iπ Tr , χπy (x) = exp 2iπ Tr pπ L−1 pπ L−2 which corresponds to the image of a character of RL−1 .
⊓ ⊔
In particular, the concept of characters allows us to define the Fourier transform on RL and thus to correctly define its quantum Fourier transform. 3.2
Construction of the Quantum Fourier Transform
For odd p, the Fourier transform over Galois rings in [21] does not directly cover the present ramified ring. Indeed, Φp (X) = (X − 1)p−1
(mod p).
We therefore use the trace-dual pairing above. Its Fourier transform can be implemented using ordinary abelian Fourier transforms and a change of coordinates. Definition 8 (Quantum Fourier Transform over RL ). Let p be a prime and L ≥ 1. We define the quantum Fourier transform (QFT) over RL as the linear operator specified by 1 X QFTRL (|x⟩) := p χy (x) |y⟩ . pL y∈RL 13
for each x ∈ RL , and extend to all quantum states by linearity. Orthogonality of characters proves that this map is unitary. n We extend this quantum Fourier transform to RL by performing the unitary n QFTRL coordinatewise. In other words, we can consider characters on RL such n that for x, y ∈ RL we have, n Y ⟨x, y⟩ χy (x) = χyi (xi ) = exp 2iπ Tr . pπ L−1 i=1
Note that when L = 1, we have R1 ∼ = Fp , and B1 (x, y) = −xy/p mod Z. Thus this QFT is the inverse of the positive-sign quantum Fourier transform over Fp introduced in Section 2.5. Proposition 3. For fixed p and L = t(p − 1), the quantum Fourier transform over RL admits an implementation to error ε in time polyp (t, log(1/ε)). Proof. We first recall that RL = Rq when L = (p − 1)t, and that Rq ∼ . = Zp−1 q p−1 Hence, if we let ι : Zq → Rq denote such an isomorphism, the map B L : Zp−1 × Zp−1 → Q/Z, q q
B L (x, y) := BL (ι(x), ι(y)),
is a non-degenerate symmetric bilinear form. Consequently, there exists a matrix (p−1)×(p−1) D ∈ Zq such that B L (x, y) =
1 T (x Dy), q
for all x, y ∈ Zp−1 . q
In the power basis we take Dij = qBL (ζpi , ζpj ) mod q; these entries are integers modulo q since qRL = 0. They are computable by rational arithmetic in K in polynomial time in t for fixed p. Non-degeneracy makes D invertible, and symmetry gives DT = D. Therefore, the unitary UD : |x⟩ 7→ |Dx⟩ admits an efficient implementation, as does the quantum Fourier transform over Zp−1 . The q resulting composition acts as follows: QFTZp−1 ◦ UD (|x⟩) = QFTZp−1 (|Dx⟩) q q X 1 2iπ T =p exp x Dy |y⟩ q q p−1 p−1 y∈Zq
= QFTRL (|x⟩), ⊔ ⊓
which concludes the proof. 3.3
Phase-state Problem
In the spirit of Kuperberg’s algorithm, the quantum Fourier transform on the ring RL allows us to transform a CCP sample into a quantum state in which the information about the secret is encoded in the phase of the state. We therefore define a new problem, the phase-state problem (PSP), which consists in recovering the secret s from such phase-state samples. 14
Definition 9 (Phase-States Problem). Let n and L be positive integers, and n let p be a prime. Fix a secret s ∈ RL . Suppose we are given ℓ phase-state samples of the form (yi , |ψyi ⟩), where n yi ← U RL ,
1 X |ψyi ⟩ = √ χyi (λj s) |j⟩ . p j∈Fp
The labels yi are independent. The phase-state problem, denoted PSPℓn,L,p , asks to recover the secret s. Lemma 5. Let n be a positive integer, let p be a prime, and let q = pt be a power of p. Fix L := t(p − 1). Then CCPn,q,p reduces to PSPn,L,p . Proof. It is enough to show that one can build a phase-state sample from a CCP sample involving the same secret s. A phase-state sample (yi , |ψyi ⟩) with n yi ← U RL is obtained from a CCP state |ϕx ⟩ by applying a quantum Fourier n transform over Rqn ∼ to the second register. Indeed, = RL X X −(Ln+1)/2 idFp ⊗ QFT⊗n |j⟩ χy (x + λj s) |y⟩ Rq (|ϕx ⟩) = p j∈Fp
n y∈RL
X
= p−(Ln+1)/2
n y∈RL
= p−Ln/2
X
χy (x)
X
χy (λj s) |j⟩ |y⟩
j∈Fp
χy (x) |ψy ⟩ |y⟩ .
n y∈RL
Measuring the second register yields each y with probability p−Ln , independently of x. Its remaining factor χy (x) is a global phase. Independent input samples therefore give independent uniform labels. ⊓ ⊔
4
A practical algorithm for solving the CCP
In 2023, Imran and Ivanyos [10] showed that there exists a quantum algorithm solving the hidden subgroup problem for nilpotent groups. They further point out that solving the hidden-shift problem via the "Simon-meets-Kuperberg" algorithm [4] is a special case of their algorithm applied to the dihedral group. Theorem 1 ([10], Theorem 1.). Let G be a nilpotent group of bounded nilpotency class such that the prime factors of |G| are constant. Assuming there exists a black box allowing a unique encoding of the elements via ℓ-bit strings, there exists an exact quantum algorithm that solves the hidden-shift problem for G using poly(ℓ) operations and poly(log |G|) calls to the hidden subgroup problem oracle. Since, by Lemma 2, the cyclotomic group Gn,q,p is nilpotent, its nilpotency class is bounded by log(q)(p − 1), and its cardinality is a power of p, Theorem 1 15
highlights an algorithm for solving the HSP for the cyclotomic group, i.e., a potential algorithm for solving CCP. Nevertheless, some points need to be qualified. For applications in public key cryptography, we are interested in asymptotic results with respect to the dimension n and the modulus q of the problem. In this setting, the nilpotency class of the cyclotomic group is no longer constant. Moreover, the complexity studied is not a complexity tied to the number of oracle calls, but rather a time and space complexity. Indeed, the exact algorithm of Imran and Ivanyos assumes access to a unitary U implementing state preparation and to its inverse U −1 . In our model, the input consists only of independent quantum samples: neither the preparation circuit nor its inverse is available. For these reasons, we have decided to present the algorithm of Imran and Ivanyos [10] within the framework of CCP. It is worth mentioning that this connection was not immediately apparent to us. During our work on CCP, we independently arrived at an approach closely related to the algorithm of Imran and Ivanyos, before becoming aware of their work. The algorithm we had been developing can be viewed as an instance of their more general framework. We therefore present it here not as a new algorithm, but as a reformulation and specialization of their result to the cyclotomic setting, with particular emphasis on its concrete time and space complexity. In this section, we present an algorithm for solving CCP in quasi-polynomial time using a quasi-polynomial number of samples. Combined with Proposition 5, this yields a quasi-polynomial-time algorithm for DCP with arbitrary prime-power moduli. Our result generalizes the result of [2].
CCPn,q,p
Prop 5
PSPn,L,p
Lemma 6
PSPn,1,p
Solver Section 4.3
Fig. 2. Overview of the CCP solver. The core idea is to reduce CCP to a phase-state problem and then perform sieving steps iteratively in order to obtain phase states from which information about the secret can be extracted.
4.1
Solver for the easy instance of PSPn,1,p
Suppose we have a phase-state sample (y, |ψy ⟩) for an instance of PSPn,1,p such that y ̸= 0. Since R1 = Fp , we have j ∈ R1 , and the quantum state has the form 1 X 1 X χy (λj s) |j⟩ = √ χs (λj y) |j⟩ √ p p j∈Fp
j∈Fp
1 X =√ χj ⟨y, s⟩ |j⟩ p j∈R1
= QFTR1 |⟨y, s⟩ mod p⟩ . 16
By measuring the phase state in its Fourier basis, we can recover ⟨y, s⟩. Hence, if we have access to n phase-state samples (yi , |ψyi ⟩), with constant probability the yi are linearly independent, we can then recover s mod p. Hence, the goal is to reduce to this simple case using Lemma 6. 4.2
Sieving step
Lemma 6 (from PSPn,L,p to PSPn,L−1,p ). Let n and L be positive integers, with L ≥ 2. There exists a quantum algorithm which, given Prr samples r n from PSPn,L,p denoted by (yi , |ψyi ⟩)i=1 with yi in RL satisfying i=1 yi = 0 mod πR, is able to produce a sample from PSPn,L−1,p . Proof. Suppose that we have access to r samples from PSPn,L,p , which we denote r by (yi , |ψyi ⟩)i=1 . The following operations reduce the level by one. 1. We begin with the tensor product of the input states: ! r r O X X 1 |ψyi ⟩ = √ r χs yi λji |j1 ⟩ . . . |jr ⟩ . p r i=1 i=1 (j1 ,...,jr )∈Fp
2. For every i ≥ 2, we perform the label change ji 7→ ji −j1 in order to introduce a dependence on j1 in each register. This gives explicitly the following state: ! r X X 1 √ r χs yi λji |j1 ⟩ |j2 − j1 ⟩ . . . |jr − j1 ⟩ p r i=1 (j1 ,...,jr )∈Fp
3. We then measure the last r − 1 registers. Suppose that the output of the i-th register is xi ∈ Fp . Fix x1 = 0 and denote the free variable j1 by j. In this case, the remaining state is: ! r X 1 X χs yi λxi +j |j⟩ . √ p i=1 j∈Fp
Using the property λxi +j = λxi + ζpxi λj , it follows that the remaining state is proportional to the state ! r X 1 X χs yi ζpxi λj |j⟩ . √ p i=1 j∈Fp
We claim that the resulting state indeed corresponds to a PSPn,L−1,p . To this end, it suffices to observe that: r X
yi ζpxi =
i=1
r X
yi
mod πRn = 0
mod πRn .
i=1
Pr n Therefore, there exists y ∈ RL−1 such that i=1 yi ζpxi = πy′ . The resulting state is thus of the form (y′ , |ψy′ ⟩), a sample from PSPn,L−1,p . ⊔ ⊓ ′
17
In order to properly use the above lemma, it is necessary to efficiently find such a sequence yi of vectors whose sum is zero modulo πRn . The following theorem provides the required zero-sum search algorithm: Theorem 2 ([10], Theorem 2). There exists a deterministic algorithm which, 2 given a sequence of size S(n, p) = pO(p log p) nO(p log p) of vectors in Fnp , is able to find a subsequence whose sum is zero in time poly(S(n, p)). Observing that R1n = Fnp , it suffices to apply the theorem to a sequence of size S(n, p) of yi corresponding to the reduction modulo π of the labels of the PSPn,L,p samples of the form (yi , |ψyi ⟩). Lemma 7 (Uniform output labels). Let S = S(n, p) ≥ 2 be an integer n threshold for Theorem 2. Given S independent uniform labels in RL , select the nonempty zero-sum subsequence using only their residues modulo π, and apply n Lemma 6. The output label is uniform in RL−1 . Proof. Condition on the residues of all labels, choose fixed lifts ri , and write n yi = ri + πzi . The vectors zi are independent and uniform in RL−1 . The selected index set I is now fixed. The measured differences xi are independent of the full labels by the preceding proof, so conditioning on them does not change the distribution of the zi . The output label is P X ζpxi ri ′ xi n y =c+ ζp zi , c = i∈I ∈ RL−1 . π i∈I
The division is well defined because the numerator is divisible by π. Since I is nonempty and every ζpxi is a unit, conditioning also on all but one of the zi leaves y′ uniform. ⊔ ⊓ 4.3
Description of the sieving algorithm
The sieving algorithm introduces lists L0 , . . . , LL−1 such that, for every i, Li contains samples associated with PSPn,L−i,p . The main idea is to move from one level to the next by grouping in buckets of size S(n, p), then applying the algorithm from Theorem 2 to find a zero-sum sequence, and doing the procedure described in Lemma 6. Once the final stage is reached, we obtain a list LL−1 consisting of samples from PSPn,1,p , from which we can easily recover s0 = s (mod p). Once the secret modulo p has been recovered, we can reduce CCPn,q,p to an instance of CCPn,q/p,p with secret (s − s0 )/p and repeat the same procedure until s is fully recovered. The algorithm is presented as follows. The analysis of Algorithm 1 shows that it runs in quasi-polynomial time when q = poly(n). This can be summarized by the following theorem. Theorem 3 (Quasi-Polynomial Algorithm for CCP). Let n and ℓ be non-negative integers, let p be a prime, and let q be a power of p. When ℓ = 2Ω(log n log q) , Algorithm 1 solves CCPℓn,q,p with constant success probability in time 2O(log n log q) using poly(n) quantum space. 18
Algorithm 1 CCP solver Input: ℓ CCP samples of a secret s ∈ Zn q Output: The secret s ∈ Zn q of the CCP instance 1: Build ℓ phase-state samples from the ℓ CCP samples, involving the same secret s ∈ Zn q. 2: Regroup the phase-state samples into families of S(n, p) elements and apply the algorithm from Theorem 2 to each to get zero-sum sequences. 1 3: Apply Lemma 6 to obtain, on average, ℓ′ ≥ ℓ · S(n,p) phase-state samples associated L−1 with PSPn,L−1,p with secret s mod π R. 1 4: Repeat Step 2 until obtaining, on average, ℓ · ( S(n,p) )L−1 samples of PSPn,1,p . 5: Deduce s mod p from this easy instance of PSPn,1,p . 6: Repeat the previous steps for an instance of CCP1,q/p,p with secret s0 = s mod (q/p), until the entire secret s ∈ Zn q is recovered.
Proof. The first round (Steps 1–2–3–4) of the algorithm dominates the subsequent ones, and a total of log(q) rounds are performed. The overall complexity is therefore determined by the complexity of the first round. The goal is to find a lower bound on the size of the first list L0 that ensures we have enough elements at level LL−1 to allow us to recover s mod p. To do this, we note that at each reduction step, we obtain |Li+1 | ≤ S(n, p)−1 |Li | By applying this inequality L − 1 times, we obtain |LL−1 | ≤ S(n, p)−L+1 |L0 |. On the other hand, we must ensure that there are sufficiently many elements at the final level to recover s (mod p). By Section 7.1, we know that O(n) phase-states from PSPn,1,p are sufficient to recover s mod p. |LL−1 | ≥ poly(n) Combining these conditions on |LL−1 |, we obtain poly(n) ≥ S(n, p)−L+1 |L0 | ⇒ |L0 | ≥ (S(n, p))L poly(n). Thus, this justifies that the number of samples required is ℓ = 2Ω(log n log q) , and it follows directly that the algorithm runs in 2O(log n log q) time. The quantum space follows Regev’s construction [14]. ⊔ ⊓
5
Equivalences between classical and cyclotomic problems
5.1
Between LWE and CyLWE
The following proposition establishes a correspondence between search LWEn,q,α and cyclotomic CyLWEn,q,p,α . Indeed, by showing that one can efficiently construct a sample of one problem from samples of the other, and vice versa, we can directly justify the equivalence between the two problems. 19
Proposition 4. Let p be a prime number, q be a power of p, α > 0 be a scalar, and n be an integer. There exists an algorithm that, given p − 1 samples of LWEn,q,α , produces a sample of CyLWEn,q,p,α involving the same secret s ∈ Znq . Conversely, given a sample of CyLWEn,q,p,α , there exists an algorithm that outputs p − 1 samples of LWEn,q,α . Proof. We first establish the forward direction. Suppose we are given an instance of classical LWEn,q,α with secret s ∈ Znq . Take (p − 1) LWE samples {(ai , bi )}p−2 i=0 and form the following coefficient expansions: a′ :=
p−2 X
b′ :=
ai ζpi ,
i=0
p−2 X
bi ζpi
(mod q) = ⟨a′ , s⟩ + e′
(mod q)
i=0
The pair (a′ , b′ ) is an instance of CyLWE with secret s0 ∈ Znq and error e′ = Pp−2 i i=0 ei ζp , where ei denotes the error term in the sample (ai , bi ). This error follows a distribution over Rn proportional to p−2 Y
ραq (ei ) = ραq ((e0 , . . . , ep−2 )) = ραq (e′ ),
i=0
since the Gaussian weight factorize over coordinates, DZ[ζp ],α coincides with the product of p − 1 independent one-dimensional discrete Gaussian. Conversely, suppose we have a sample of CyLWEn,q,p,α noted (a, b). We can decompose a and b into the basis (1, ζp , . . . , ζpp−2 ) such that a=
p−2 X i=0
ai ζpi ,
b=
p−2 X
bi ζpi
(mod q) =
i=0
p−2 X
(⟨ai , s⟩ + ei )ζpi
(mod q),
i=0
where bi = ⟨ai , s⟩ + ei (mod q) with ei ← DZ,αq . This yields (p − 1) samples of LWE with secret s. ⊔ ⊓ The introduction of CyLWE in the paper and its connection to LWE is extremely important to us, because it is what allowed us to fully understand how to link a classical problem to a problem on cyclotomic rings. Among other things, this is what enabled us to establish that the CCP secret must indeed be contained within the restricted space Znq and not within Rqn . All other reductions, like P roposition 5 and Lemma 10, are inspired by the philosophy of the proof described above, which considers the group isomorphism Zp−1 to Rq . q 5.2
Between DCP and CCP
The proof of the equivalence between DCP and CCP follows the same approach as the one used for the equivalence between LWE and CyLWE. Namely, we show that samples associated with one problem can be efficiently constructed from samples of the other problem, while preserving the same secret. 20
Proposition 5. Given (p − 1) samples of DCPn,q,p , there exists a quantum algorithm that produces a CCPn,q,p sample with probability p/2p−1 . Conversely, given a sample of CCPn,q,p , there exists a quantum algorithm that outputs a DCPn,q sample with probability 2/p. Both direction involving the same secret. n×(p−1)
→ Rqn denote the bijection defined, for a matrix X = n×(p−1) (x0 | · · · | xp−2 ) ∈ Zq , by Proof. Let f : Zq
f (X) :=
p−2 X
xi ζpi .
i=0
We begin the first reduction by collecting (p − 1) samples of DCPn,q,p of the form X |ϕi ⟩ ∝ |j⟩ |xi + js mod q⟩ . j∈{0,1}
Taking their tensor product and rearranging the registers gives the following expression for their joint state: p−2 O
X
|ϕi ⟩ =
i=0
|j0 ⟩ |x0 + j0 s⟩ · · · |jp−2 ⟩ |xp−2 + jp−2 s⟩
(j0 ,...,jp−2 )∈Fp−1 2
=
X
|J⟩ |X + MJ,s ⟩ ,
J∈Fp−1 2 n×(p−1)
n×(p−1)
with X = (x0 | · · · | xp−2 ) ∈ Zq and MJ,s = (j0 s | · · · | jp−2 s) ∈ Zq We then apply f to the second register, obtaining X X X |J⟩ |x + ζpi s⟩ , |J⟩ |f (X + MJ,s )⟩ = J∈Fp−1 2
J∈Fp−1 2
.
i∈supp(J)
Pp−2 where x = i=0 xi ζpi and supp(J) = {0 ≤ i ≤ p − 2 | Ji = ̸ 0}. This state is close to a CCPn,q,p state. Indeed, a CCPn,q,p state corresponds to the uniform superposition indexed by vectors J in the subset S = {Jj ∈ Fp−1 | j ∈ Fp , (Jj )i = 1{0,...,j−1} (i)}. 2 Hence, by computing in an auxiliary register J 7→ 1S (J) and measuring it, we obtain the output 1 with probability p/2p−1 . The remaining state corresponds to a superposition over S from which we can convert to a CCPn,q,p state: X Jj ∈S
|Jj ⟩ |x +
j−1 X
ζpi s⟩ →
i=0
X j∈Fp
|j⟩ |x +
j−1 X
ζpi s⟩ .
i=0
Conversely, suppose we are given a CCPn,q,p sample and we want to compute a DCPn,q sample. We measure the two outcome projector onto the first register 21
subspace spanned by |0⟩ and |1⟩ and its orthogonal complement. With probability 2/p, we get: 1 √ |0⟩ |x⟩ + |1⟩ |x + s⟩ . 2 Pp−2 i We write x = i=0 xi ζp and apply the coefficient bijection f −1 to the second register. Since s ∈ Rqn has only a constant coefficient (it’s the coordinatewise constant embedding of an element of Znq in Rqn ), the state factors exactly as |0⟩ |x0 ⟩ + |1⟩ |x0 + s⟩ √ ⊗ |x1 , · · · , xp−2 ⟩ 2 We can discard the last registers and get a DCP state. 5.3
⊓ ⊔
A potential direct reduction from CyLWE to CCP?
We believe it is possible to construct a direct reduction from CyLWE to CCP, analogous to Regev’s reduction from LWE to DCP [14]. Informally, the idea is that given a CyLWE (A, b = As + e) ∈ Rqm×n × Rqm , for a secret s ∈ Znq , we consider a superposition on the q-ary cyclotomic lattice: Λq (A) = {y ∈ Rm | y = Ax
mod q, x ∈ Rqn },
which is shifted by a vector λj e, where j is in Fp . Given assumptions about the minimum distance of the q-ary lattice, the shift is very small compared to the minimum distance, and we can remove the error using cube-separation or ball-intersection techniques, as in [5]. However, for all of this to work, we obviously need results on the topology of random q-ary lattice, which we do not claim to have. Furthermore, such a reduction would improve only very slightly upon a reduction consisting of moving from CyLWE to LWE, then from LWE to DCP via [14], and finally from DCP to CCP.
6
Impact and discussions
In this section, we discuss the impact of Algorithm 1 on other, more extensively studied computational problems such as EDCP or S |LWE⟩. This allows us to conclude that a quasi-polynomial-time algorithm exists when q is a power of a fixed prime p. 6.1
On the Extrapolated Dihedral Coset Problem.
Definition 10 (Search Extrapolated Dihedral Coset Problem [5]). Let a parameter n be a dimension, q ≥ 2 be a modulus and M, ℓ be positive integers. The uniform search Extrapolated Dihedral Coset Problem (U-EDCPℓn,q,M ) consists of ℓ input states of the form M −1
1 X √ |j⟩ |xi + js M j=0
mod q⟩ ,
22
for i = 0 . . . ℓ,
where xi ∈ Znq are sampled uniformly, and asks to recover the secret s ∈ Znq . Lemma 8 ([9], Lemma 10). Let n, q, ℓ, M, M ′ be integers greater ′ than 1 and M ≥ M . There exists a probabilistic polynomial-time quantum reduction from U-EDCPℓn,q,M to U-EDCPℓn,q,M ′ that succeeds with a constant success probability. Theorem 4. Let n, q, ℓ, M , be integers greater than 1 and q be any prime-power. There exists a quantum algorithm that solves U-EDCPℓn,q,M in time 2O(log n log q) using poly(n) quantum space, when ℓ = 2Ω(log n log q) . ′
Proof. The proof follows Lemma 8 in order to get U-EDCPℓn,q,2 with ℓ′ = O(ℓ), ′
) then apply Proposition 5 to reduce to a CCPO(ℓ n,q,p and use the CCP solver in Algorithm 1. ⊔ ⊓
6.2
An algorithm for Gaussian S |LWE⟩
In this section, we present a quasi-polynomial-time algorithm that solves the Gaussian S |LWE⟩ problem, based on the algorithm for solving CCP in Section 4. We thus generalize the procedure in [2] for this problem to any modulus q = pt , where p is a constant prime. To do this, we first provide a definition of the Gaussian S |LWE⟩ problem and of U-EDCP. This second problem will allow us to bridge the gap between S |LWE⟩ and PSP, defined in Section 3, to which we will be able to apply the procedure in Algorithm 1. Definition 11 (Gaussian S |LWE⟩). Given parameters ℓ, n, q and a scalar r > 0, Gaussian S |LWE⟩ consists of ℓ samples (ai , |φi ⟩) such that: ai ← U(Znq ),
|φi ⟩ ∝
X
ρr (e) |⟨ai , s⟩ + e⟩ ,
e∈Z
and asks to recover the secret s ∈ Znq . Definition 12 (U-EDCP). Let a parameter n be a dimension, q ≥ 2 be a modulus and M, ℓ be positive integers. The U-EDCP consists of ℓ samples of the following form: M −1
yk ← U(Znq ),
with ωq = exp
√
2 −1π q
1 X j⟨yk , s⟩ |ψyk ⟩ = √ ωq |j⟩ , M j=0
and asks to recover the secret s ∈ Znq .
Next, we recall in Lemma 9 the reduction that allows us to obtain O(ℓ) U-EDCPn,q,M samples from Gaussian S |LWE⟩ samples. 23
Lemma 9 (from S |LWE⟩ to U-EDCP, [2], Lemma 15 and 16). Let κ be the security √ parameter, ℓ =√ω(κ) and n, q = poly(κ) be positive integers. Let r = Ω( κ) and q/r = Ω( κ). There exists a quantum polynomial-time O(ℓ)
ℓ
reduction from S |LWE⟩n,q,r to U-EDCPn,q,M , where M = c · r for some constant c, and succeeds with overwhelming probability. The next lemma converts these inputs into cyclotomic phase states. Lemma 10 (from U-EDCP to PSP). Let n, q, M, p be integers greater than 1, with p prime and q = pt . There exists a quantum algorithm that given a constant number of samples U-EDCPn,q,q , outputs PSPn,L,p samples, with L = (p−1) log q, involving the same secret s ∈ Znq with constant probability. Proof. We describe the successive steps that allow us to obtain phase-state samples from states of the following form. We omit normalization factors in the intermediate expressions below. X |ϕi ⟩ ∝ ωqxi ⟨yi , s⟩ |xi ⟩ , for i = 0 . . . p − 2, xi ∈Zq
with known labels yi . 1. We begin by entangling the p − 1 states to obtain the following state: Pp−2 p−2 O X xi ⟨yi , s⟩ |ϕi ⟩ = ωq i=0 |x1 ⟩ . . . |xp−2 ⟩ i=0
(x0 ,...,xp−2 )∈{0,...,M −1}p−1
=
X
T
ωqx v |x⟩ ,
x∈{0,...,M −1}p−1
where v ∈ Zp−1 is such that its i-th coordinate is vi = ⟨yi , s⟩. q (p−1)×(p−1) 2. Let D ∈ Zq be the invertible matrix associated with the bilinear form BL from Proposition 3 with L = t(p − 1). By noting v′ = D−1 v, in ′ ′ other words there exists (yi′ )p−2 i=0 such that vi = ⟨yi , s⟩ for 0 ≤ i ≤ p − 2. We have X X T ′ ωqx Dv |x⟩ = χx (ι(v′ )) |x⟩ x∈{0,...,M −1}p−1
x∈ι({0,...,M −1}p−1 )
where ι : Zp−1 → Rq is the injection with respect to the basis (1, ζp , . . . , ζpp−2 ). q Pp−2 Pp−2 Moreover, ι(v′ ) = i=0 ζpi ⟨yi′ , s⟩ = ⟨y′ , s⟩, where y′ = i=0 ζpi yi′ . Note that y′ follows a uniform distribution on ι({0, . . . , M − 1}p−1 ) by invertibility of the coordinate transformation. We obtain ⟨xy′ , s⟩ χx (ι(v)) = exp 2iπ Tr = χs (xy′ ). pπ L−1 The resulting state at the end of this operation is therefore X χs (xy′ ) |x⟩ . x∈ι({0,...,M −1}p−1 )
24
3. The idea is now to move from a superposition over x ∈ ι {0, . . . , M − 1}p−1 to a superposition over E := {λj }j∈Fp and thereby obtain a PSP sample. To this end, we will use the intermediate superposition ι({0, 1}p−1 ). We therefore compute in an auxiliary register the function x 7→ ⌊ι−1 (x)/2⌋, which we measure directly. Let k ∈ Zp−1 denote the output, and suppose q that k ∈ {0, . . . , (M − 1)/2}p−1 this happens with probability bounded below by a positive constant when M is large (otherwise, we discard the resulting state and restart from the beginning). The remaining state has support in the following translated set: ι(k) + ι({0, 1}p−1 ) ⊂ ι({0, . . . , M − 1}p−1 ), that is, X
χs ((x − ι(k))y′ ) |x⟩ ∝
x∈ι({0,1}p−1 )
X
χs (xy′ ) |x⟩ .
x∈ι({0,1}p−1 )
4. Finally, it suffices to compute the function x 7→ 1E (x) in a new auxiliary register. After measurement, there is a constant probability p/2p−1 of obtaining the desired output 1 and thus obtaining a PSP state with label y′ and with respect to the same secret s ∈ Zp−1 . ⊔ ⊓ q Observe that this lemma provides an alternative way to prove the existence of a quasi-polynomial-time algorithm for uniform EDCP without having to resort to a reduction to DCP. Theorem 5. Let κ be the security parameter and n, q √= poly(κ) be integers, √ where q = pt is a power of a fixed prime p. Let r = Ω( κ) and q/r = Ω( κ). 2 ℓ There exists a quantum algorithm that solves S |LWE⟩n,q,r in time 2O(log n) using 2
poly(n) quantum space, when ℓ = 2Ω(log n) . Proof. Start by applying Lemma 9 to obtain O(ℓ) U-EDCP samples, then applying Lemma 10 to get O(ℓ) phase-state sample involving the same secret s ∈ Znq . Then it remains to apply the procedure from Algorithm 1 to recover s from a quasi-polynomial number of phase-state samples. ⊔ ⊓ Note that the Lemma 10, which is used to prove the existence of an algorithm for the Gaussian S |LWE⟩, is specific to our paper. Indeed, to the best of our knowledge, S |LWE⟩ is not a hidden subgroup problem. We therefore would not have been able to obtain such an algorithm had we not defined a quantum Fourier transform on Rq and had we not explicitly specified the phase-state samples. Non-impact on Learning with Errors. Since this result generalizes the algorithm in [2], we obtain the same conclusion regarding the security of LWE. Indeed, the sieving algorithm requires too many CCP samples, and the reduction from LWE to DCP places an upper bound on the number of samples that is smaller than the number of samples required to solve the problem. 25
References 1. Aggarwal, D., Regev, O.: A Note on Discrete Gaussian Combinations of Lattice Vectors (Aug 2013), https://arxiv.org/abs/1308.2405v2 2. Bai, S., Jangir, H., Kirshanova, E., Ngo, T., Youmans, W.: A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem over Power-of-Two Moduli. In: Kalai, Y.T., Kamara, S.F. (eds.) Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II. pp. 416–448. Lecture Notes in Computer Science, Springer (2025). https://doi.org/10.1007/978-3-032-01878-6_14, https: //doi.org/10.1007/978-3-032-01878-6_14 3. Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(1), 625–635 (Dec 1993). https://doi.org/ 10.1007/BF01445125, https://doi.org/10.1007/BF01445125 4. Bonnetain, X., Naya-Plasencia, M.: Hidden Shift Quantum Cryptanalysis and Implications (2018), https://eprint.iacr.org/2018/432, publication info: Preprint. MINOR revision. 5. Brakerski, Z., Kirshanova, E., Stehlé, D., Wen, W.: Learning with Errors and Extrapolated Dihedral Cosets. In: Abdalla, M., Dahab, R. (eds.) Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 2529, 2018, Proceedings, Part II. pp. 702–727. Lecture Notes in Computer Science, Springer (2018). https://doi.org/10.1007/978-3-319-76581-5_24, https: //doi.org/10.1007/978-3-319-76581-5_24 6. Chailloux, A., Hermouet, P.: On the quantum equivalence between s|LWE〉 and ISIS. Cryptology ePrint Archive, Paper 2025/1857 (2025), https://eprint.iacr. org/2025/1857 7. Chen, Y., Liu, Q., Zhandry, M.: Quantum algorithms for variants of average-case lattice problems via filtering. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III. Lecture Notes in Computer Science, vol. 13277, pp. 372–401. Springer (2022). https://doi.org/10.1007/978-3-031-07082-2_14, https://doi.org/10.1007/978-3-031-07082-2_14 8. Childs, A.M., van Dam, W.: Quantum algorithm for a generalized hidden shift problem. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1225–1232. SODA ’07, Society for Industrial and Applied Mathematics, USA (2007) 9. Doliskani, J.: Efficient Quantum Public-Key Encryption From Learning With Errors (2020), https://eprint.iacr.org/2020/1557, publication info: Preprint. MINOR revision. 10. Imran, M., Ivanyos, G.: Zero sum subsequences and hidden subgroups. Quant. Inf. Proc. 23(1), 14 (2024). https://doi.org/10.1007/s11128-023-04228-2 11. Kuperberg, G.: A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. SIAM Journal on Computing 35(1), 170– 188 (2005). https://doi.org/10.1137/S0097539703436345, https://doi.org/10. 1137/S0097539703436345, _eprint: https://doi.org/10.1137/S0097539703436345 12. Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Severini, S., Brandão, F.G.S.L. (eds.) 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC
26
2013, Guelph, Canada, May 21-23, 2013. LIPIcs, vol. 22, pp. 20–34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013). https://doi.org/10.4230/LIPICS.TQC. 2013.20, https://doi.org/10.4230/LIPIcs.TQC.2013.20 13. Regev, O.: Quantum computation and lattice problems. In: 43rd Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, Proceedings. pp. 520–529. IEEE Computer Society (2002). https: //doi.org/10.1109/SFCS.2002.1181976, https://doi.org/10.1109/SFCS.2002. 1181976 14. Regev, O.: Quantum Computation and Lattice Problems. SIAM J. Comput. 33(3), 738–760 (2004). https://doi.org/10.1137/S0097539703440678, https: //doi.org/10.1137/S0097539703440678 15. Regev, O.: A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space (Jun 2004), https://arxiv.org/abs/quant-ph/ 0406151v1 16. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005. pp. 84–93. ACM (2005). https://doi.org/10.1145/1060590.1060603, https://doi.org/10.1145/ 1060590.1060603 17. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1–34:40 (2009). https://doi.org/10.1145/1568318.1568324, https://doi.org/10.1145/1568318.1568324 18. Rotman, J.: An Introduction to the Theory of Groups. Graduate Texts in Mathematics, Springer New York (1999), https://books.google.fr/books?id= vb9kUfHqQigC 19. Wen, W., Zheng, J.: Module Learning With Errors and Structured Extrapolated Dihedral Cosets (2026), https://eprint.iacr.org/2026/155, publication info: Preprint. 20. de Wolf, R.: Quantum computing: Lecture notes (2026), https://arxiv.org/abs/ 1907.09415 21. Zhang, Y.: Quantum Fourier Transform Over Galois Rings (Apr 2009). https: //doi.org/10.48550/arXiv.0904.2560, http://arxiv.org/abs/0904.2560, arXiv:0904.2560 [quant-ph]
27