Learning With Errors and Extrapolated Dihedral Cosets

The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal. We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev's famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS'02). We also discuss a connection between eDCP and Childs and Van Dam's algorithm for generalized hidden shift problems (SODA'07). Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier.


Introduction
The Learning With Errors problem LWE n,q,α with parameters n, q ∈ Z and α ∈ (0, 1) consists in finding a vector s ∈ Z n q from arbitrarily many samples (a i , a i , s + e i ) ∈ Z n q × Z q , where a i is uniformly sampled in Z n q and e i is sampled from D Z,αq , the discrete Gaussian distribution of standard deviation parameter αq (i.e., the distribution such that D Z,αq (k) ∼ exp(−πk 2 /(αq) 2 ) for all k ∈ Z). Since its introduction by Regev [27,28], LWE has served as a security foundation for numerous cryptographic primitives (see e.g. an overview in [23]). The cryptographic attractiveness of LWE stems from two particularly desirable properties. First, its algebraic simplicity enables the design of primitives with advanced functionalities, such as fully homomorphic encryption [7], attribute-based encryption for all circuits [13] and (single key) functional encryption [12]. Second, LWE is conjectured hard even in the context of quantum computations, making it one of the most appealing candidate security foundations for post-quantum cryptography [5]. Current quantum algorithms for LWE do not outperform classical ones, but it is not clear whether this is inherent (for example, it is known that LWE is easier than the Dihedral Coset Problem under polynomial-time reductions, see below). In this work, we characterize the quantum hardness of LWE under polynomial-time reductions and show that it is computationally equivalent (up to small parameter losses) to a quantum problem closely related to the aforementioned Dihedral Coset Problem.
LWE, Lattices and the Dihedral Coset Problem. LWE is tightly connected to worst-case approximation problems over Euclidean lattices. In particular, LWE is an (average-case) instance of the Bounded Distance Decoding problem (BDD) (see, e.g., [20,Section 5.4]), but is also known to be as hard as worst-case BDD (with some polynomial loss in parameters) [28]. BDD is the problem of finding the closest lattice vector to a given target point which is promised to be very close to the lattice (formally, closer than λ 1 /γ where λ 1 is the length of the shortest non-zero vector). Classical and quantum connections between BDD and other problems such as SIVP, GapSVP, uSVP are also known [6,19,22,28].
Regev [24,26] showed that uSVP, and therefore also BDD and LWE, are no harder to solve than the quantumly-defined Dihedral Coset Problem (DCP). An instance of DCP N,ℓ , for integer parameters N and ℓ, consists of ℓ quantum registers in superposition |0, x k + |1, x k + s , with a common s ∈ Z N and random and independent x k ∈ Z N for k ∈ [ℓ]. The goal is to find s (information theoretically ℓ = O(log N ) is sufficient for this task [9]). We note that Regev considered a variant with unbounded number of registers, but where a fraction of them is faulty (a faulty state is of the form |b, x k for arbitrary b ∈ {0, 1}, x k ∈ Z N ). In our work, we assume a non-faulty formulation of DCP. Still, it is quite possible that DCP is in fact much harder to solve than LWE. The best known algorithm for DCP, due to Kuperberg [16], runs in time 2 O(log ℓ+log N/ log ℓ) which does not improve upon classical methods for solving LWE. Other variants of the problem were explored in [9,10], and of particular relevance to this work is a "vector" variant of the problem where Z N is replaced with Z n q (i.e. s and x k are now vectors). These problems behave similarly to DCP with N = q n .
Finally, Regev showed that DCP can be solved given efficient algorithms for the subset-sum problem (which is classically defined), however in a regime of parameters that appears harder to solve than LWE itself.
Extrapolated DCP. The focus of this work is a generalization of the DCP problem, i.e. rather than considering registers containing |0, x k +|1, x k + s , we allow (1) x i 's and s be n-dimensional vectors, and (2) other than non-uniform distribution for amplitudes. We name this problem Extrapolated DCP (EDCP) as its in-put registers has more extrapolated states. To be more precise, EDCP ℓ n,N,f , with parameters three integers n, N, ℓ and a function f : Z → C with j∈Z j·|f (j)| 2 < +∞, consists in recovering s ∈ Z n N from the following ℓ states over Z × Z n N : where the x k 's are arbitrary in Z n N . 1 Note that DCP is the special case of EDCP for n = 1 and f being the indicator function of {0, 1}.
In [8], Childs and van Dam consider a special case of EDCP where f is the indicator function of {0, . . . , M − 1} for some integer M , which we will refer to as uniform EDCP (or, U-EDCP ℓ n,N,M ).
Our Main Result. We show that up to polynomial loss in parameters, U-EDCP is equivalent to LWE. Thus we provide a formulation of the hardness assumption underlying lattice-based cryptography in terms of the (generalized) Dihedral Coset Problem.
Theorem 1 (Informal). There exists a quantum polynomial-time reduction from LWE n,q,α to U-EDCP ℓ n,N,M , with N = q, ℓ = poly(n log q) and M = poly(n log q) α . Conversely, there exists a polynomial-time reduction from U-EDCP to LWE with the same parameter relationships, up to poly(n log q) factors.
Our proof crucially relies on a special case of EDCP where f is a Gaussian weight function with standard deviation parameter r. We call this problem Gaussian EDCP (G-EDCP). We show that G-EDCP and U-EDCP are equivalent up to small parameter losses.
EDCP is analogous to LWE in many aspects. The decisional version of LWE (dLWE) asks to distinguish between LWE samples and random samples of the form (a, b) ∈ Z n q × Z q where both components are chosen uniformly at random. Similarly, we also consider the decisional version of EDCP, denoted by dEDCP. In dEDCP n,N,f , we are asked to distinguish between an EDCP state and a state of the form |j |x mod N , where j is distributed according to the function |f | 2 , and x ∈ Z n N is uniformly chosen. EDCP enjoys a reduction between its search and decisional variants via LWE.
Related work. In [8], Childs and van Dam show that U-EDCP ℓ 1,N,M reduces to the problem of finding all the solutions b ∈ {0, . . . , M − 1} k to the equation b, x = w mod N , where x and w are given and uniformly random modulo N . They interpret this as an integer linear program and use lattice reduction, within Lenstra's algorithm [18], to solve it. This leads to a polynomial-time algorithm for U-EDCP ℓ 1,N,M when M = ⌊N 1/k ⌋ and ℓ ≥ k, for any k ≥ 3. Interestingly, finding small solutions to the equation b, x = w mod N is a special case of the Inhomogeneous Small Integer Solution problem [11] (ISIS), which consists in finding a small-norm x such that Bx = w mod q, with B ∈ Z n×m q and w ∈ Z n q uniform (where q, n, m are integer parameters). A reduction from the homogeneous SIS (i.e., with w = 0 and x = 0) to LWE was provided in [30]. It does not seem possible to derive from it a reduction from EDCP to LWE via the Childs and van Dam variant of ISIS, most notably because the reduction from [30] does not provide a way to compute all ISIS solutions within a box {0, 1, . . . , M − 1} k .
It is not hard to see that, at least so long as M is polynomial, a solution to DCP implies a solution to EDCP ℓ n,N,M . Therefore our result implies [24] as a special case. On the other extreme, our result also subsumes [8] since the LLL algorithm [17] can be used to solve LWE n,q,α in polynomial time when 1/α and q are 2 Θ(n) , which implies a polynomial-time algorithm for EDCP for M = 2 Θ( √ n log N ) , significantly improving Childs and van Dam's M = 2 εn log N . Finally, we observe that the LWE to U-EDCP reduction (and the uSVP to DCP reduction from [26]) can be adapted to a uSVP to U-EDCP reduction, as explained below. Combining this adaptation with the reduction from U-EDCP to LWE (via G-EDCP) provides a novel quantum reduction from worst-case lattice problems to LWE. However, it does not seem to have advantages compared to [28].

Technical overview
As mentioned above, the hardness of LWE is essentially invariant so long as n log q is preserved, and therefore we restrict our attention in this overview to the one-dimensional setting. A crucial ingredient in our reduction is a weighted version of EDCP, denoted by G-EDCP and quantified by a Gaussian weight function f r (j) =ρ r (j) = exp(−πj 2 /r 2 ), for some standard deviation parameter r. We refer to this problem as Gaussian EDCP (G-EDCP).
Reducing G-EDCP to LWE. Given an G-EDCP state as input, our reduction efficiently transforms it into a classical LWE sample with constant success probability. Thus, making only one query to the LWE oracle, we are able to solve G-EDCP. More precisely, the reduction input consists of a normalized state corresponding to j∈ZN ρ r (j) |j |x + j · s mod N , for some integers r ≪ N . One can think of N as the LWE modulus and of r as the standard deviation parameter of the LWE error.
Our first step is to apply a quantum Fourier transform over Z N to the second register. This gives us a quantum superposition of the form:  where ω N = exp(2iπ/N ). We then measure the second register and obtain a value a ∈ Z N . This leaves us with the state: Note that a is uniformly random over Z N , which at the end serves as the first component of LWE sample. The exponent of relative phase in current state has a form similar to the second component of LWE sample but without noise. Now we can benefit from the first register, which stores a superposition corresponding to a Gaussian distribution over Z N with standard deviation r. Applying a second quantum Fourier transform over Z N to the first register gives us a quantum superposition of the form: Now the second component of the LWE sample a · s + b is stored in the phase (up to a factor j). Omitting the exponentially small Gaussian tail, we assume the summation for j is taken over the integers. An application of the Poisson summation formula transfers a · s + b into a shift of the Gaussian distribution defined over Z. In other words, the received state is exponentially close to the superposition: Once we measure the state above, we obtain a value − a·s+e, where e ←֓ D Z,N/r . Together with already known a, this gives us an LWE sample: (− a, − a · s + e) .
In case the input state is of the form |j |x mod N , where j is distributed according to the function ρ 2 r , and x ∈ Z N is uniformly chosen (the decisional case), the reduction outlined above outputs a uniform random pair (a, b) from Z N ×Z N . This gives a reduction from decisional version of G-EDCP to decisional version of LWE.
Reducing LWE to G-EDCP. Our reduction from LWE to G-EDCP follows the general design of Regev's reduction from uSVP to DCP [26], with several twists that enable simplifications and improvements. We note that this reduction is folklore, 2 although we could not find it described explicitly.
First, the use of LWE rather than uSVP allows us to avoid Regev's initial subreduction from uSVP to BDD, as LWE is a randomized variant of BDD. Indeed, if we consider m samples (a i , a i · s + e i ) from LWE n,q,α , then we have a BDD instance for the lattice Λ = AZ q + qZ m and the target vector t = b + e ∈ Z m with b ∈ Λ satisfying b = A · s mod q.
As Regev's, our reduction proceeds by subdividing the ambient space R m with a coarse grid, setting the cell width between e and λ 1 (Λ). We map each point y ∈ R m to a cell φ(y). By choice of the cell width, we have φ(c 1 ) = φ(c 2 ) for any c 1 = c 2 in Λ. Also for any c ∈ R m , the vectors c and c + e are most likely mapped to the same cell, as e is short. This intuition fails if a border between two cells falls close to c. This (rare but non-negligibly so) event is the source of the limitation on the number ℓ of DCP/EDCP states produced by the reduction. The space subdivision by a grid is illustrated in Figure 2. Regev's reduction and ours differ in the way the grid is used to create the DCP/EDCP states. Let us first briefly recall the core of Regev's reduction. Let B = (b 1 , . . . , b m ) be a basis of Λ and subtract an appropriate combination of the b i 's from t to get t ′ so that the coordinates x ′ of the closest vector b ′ ∈ Λ to t ′ with respect to the b i 's are ≤ 2 m (this may be achieved using LLL [17] and Babai's nearest plane algorithm [1]). The first step is the creation of a superposition where the equality holds by a change of variable. By measuring the last register, with overwhelming probability this collapses to |0 |x k + |1 |x k + x ′ , which corresponds to an m-dimensional DCP input state with modulus 2 O(m) . The whole process can be repeated multiple times using the same input vector t, and results in different x k 's but a common x ′ . Each iteration may fail because of an illplaced cell delimitation, or if x k + x ′ has a coordinate whose magnitude is larger than 2 2m . This leads to a bounded number of correct DCP input states. Finally, m-dimensional DCP can be reduced to 1-dimensional DCP, with a significant modulus increase: the resulting modulus N is 2 O(m 2 ) . Instead of using a superposition based on the coordinates with respect to a basis, we exploit the special form of Λ = aZ q + qZ m (w.l.o.g., assume 1dimensional LWE, [6]). We start with the following superposition: We then measure the last register (classically known and omitted) and hopefully obtain a superposition |0 |x + |1 |x + s . This approach has several notable advantages. First, by using a grid over the torus R m /qR m , the only source of failure is the position of the cell delimitation (coordinates cannot spill over, they wrap around). Second, we directly end up with a DCP state, not a vectorial variant thereof. Third, and most importantly, the DCP modulus N is only q and not 2 O(m 2 ) . Note that m should be set as Ω(log q) for s to be uniquely determined by the LWE samples. This improvement results in a much tighter reduction.
The improvement stems from the use of a small modulus q rather than large integer coordinates. It is possible to obtain such a small DCP modulus while starting from BDD (rather than LWE), by modifying Regev's reduction as follows. One may first reduce BDD to a variant thereof that asks to find the coordinates of the BDD solution modulo a small modulus q rather than over the integers. Such a reduction is presented in [28,Lemma 3.5]. One may then reduce this BDD variant to DCP as we proceed for LWE. Note that this transformation makes the BDD to DCP reduction from [26] iterative: the DCP oracle is called several times, and the input of an oracle call depends on the output of the previous oracle calls. This is akin to the phenomenon described in the open questions paragraph from [6].
A further difference between our reduction and the one from [26] is that we consider larger multiples of s in the input superposition to obtain a state of the form j ρ r (j) |j |x + js , with r ≈ 1/α (up to polynomial factors). This does not lead to any extra complication, but leads us to G-EDCP rather than DCP, which we crucially need to allow for a converse reduction. We conjecture that G-EDCP is strictly easier than DCP.
As Regev [25], we can also improve the resulting deviation parameter r of G-EDCP by a factor of √ m using balls' intersections rather than cube separation. We consider intersections of balls drawn around a · s and its noisy shifts. The radius R of each ball is set to be the largest value such that the balls arising from different s (and their shifts) do not intersect. We are interested in the intersection area the balls drawn around ±s, ±2s, etc. Following Regev [25], this area is large enough to guarantee that once we measure, we hit a point from the intersection of all the balls (see grey areas in Figure 3). Fig. 3: A visualization of the balls' intersections. The lattice points (black dots) are of distance first minimum of lattice aZ q + qZ to each other. The distance between the two furtherst shifts je (red dots) has an upper bound, denoted by d. Each ball has a radius R chosen to be (approximately) λ 1 (Λ q (a))/2, where Λ q (a) = aZ q + qZ. Note that once the shaded gray area is measured, the reduction succeeds in outputting an G-EDCP sample. For the reduction to work with a constant success probability, the shaded area has to have a large enough proportion compared to the volume of the balls.
The same algorithm provides a reduction from dLWE to dG-EDCP. Given a random sample (a, b) ∈ Z m q × Z m q , it suffices to show that all the balls centered at as + jb for s ∈ Z q and j ∈ Z, do not intersect with each other. All the points considered above form the lattice (a|b)Z q + qZ, We argue analogously using the upper-bound on the minima of this lattice. As a result, the superposition collapses exactly to one of the balls, which gives a random sample of dG-EDCP.

Open problems
Towards an alternative reduction from EDCP to LWE. In [8], Childs and van Dam obtain a state of the form for some uniform y ∈ Z ℓ N . Note the uniform distribution of weights for j. To recover s, the authors use the Pretty Good Measurement technique from [15] as was done in [2,3] for similar problems. Implementing this general technique to this particular setup requires the construction of a POVM with operators corresponding to superpositions of all the j's in {0, . . . , M −1} ℓ such that j, y = a mod N . As we already mentioned, a unitary operator that realizes such a POVM, uses a lattice-reduction technique as its main subroutine and, hence, works efficiently only for large values of M .
The question we do not address here is the interpretation of the POVM technique (and, possibly, a different reduction to LWE) for Gaussian-weighted superpositions. It might be simpler to obtain Gaussian j's rather than uniform from a cube, and hence it is possible that such a technique may lead to an improved reduction to LWE.
Hardness of EDCP with more input states. We show in this work that LWE and U-EDCP are computationally equivalent up to small parameter losses, when the number of U-EDCP states ℓ is polynomial. In these reductions, the U-EDCP bound M is within a polynomial factor of the LWE noise rate 1/α. When more states are available, U-EDCP is likely to become easier. For instance, with M = 2, the best known algorithms when ℓ is polynomially bounded are exponential. Oppositely, Kuperberg's algorithm [16] . This suggests that there may be a U-EDCP self-reduction allowing to trade ℓ for M : Is it possible to reduce EDCP N,ℓ,M to EDCP N,ℓ ′ ,M ′ with ℓ ′ ≤ ℓ, while allowing for M ′ ≥ M ?

Prerequisites
Notations. We use lower case bold letters to denote vectors and upper case bold to denote matrices. For a vector x, we let x ∞ denote its ℓ ∞ norm and x denote its ℓ 2 norm. We let Z N denote the cyclic group {0, 1, · · · , N − 1} with addition modulo N . We assume we can compute with real numbers. All the arguments are valid if a sufficiently accurate approximation is used instead. For a distribution D, the notation x ←֓ D means that x is sampled from D. For a set S, we let x ←֓ S denote that x is a uniformly random element from S.
For any r > 0, we let ρ r (x) denote exp(−π x 2 /r 2 ), where x ∈ R n for a positive integer n. We let D Z,r denote a Gaussian distribution over the integers with density function proportional to ρ r (·). We let D Λ,r,c denote the Gaussian distribution over the n-dimensional lattice Λ (for a positive integer n), with standard deviation parameter r ∈ R and center c ∈ R n . If c = 0, we omit it. We let B n (c, R) denote the n-dimensional Euclidean ball of radius R centered at c ∈ R n and B n denotes the n-dimensional Euclidean unit ball centered at 0. We use ω N as a short-hand for exp(2πi/N ).
For a lattice Λ with a basis B, the parallelepiped P(B) = {Bx : 0 ≤ x i ≤ 1} is a fundamental domain of Λ. We let λ 1 (Λ) (resp. λ ∞ 1 (Λ)) denote the ℓ 2 -norm (ℓ ∞ -norm) of a shortest vector of Λ. We let Λ ⋆ = {y ∈ R n : ∀x ∈ Λ, x, y ∈ Z} denote the dual of a lattice Λ. We define the smoothing parameter η ε (Λ) as be . We assume all the parameters n (the dimension), q (the modulus) and r are functions of a common parameter κ. The most relevant choice of such a relation one can keep in mind is when n, ℓ, q and r are poly(κ). One can trace the losses in the parameters (with respect to the number of samples ℓ and to r) once we move from one problem to another. Notice that some reductions may be performed in two ways. For example, using the self-reducibility property of EDCP (Lemma 10), we can bypass Gaussian EDCP and have a more sampleefficient reduction from EDCP with large r to an EDCP with smaller r. Similarly, Gaussian EDCP can be reduced to DCP either directly (Lemma 11) or via uniform EDCP.
The two central reductions that show equivalence between LWE and EDCP problems are on the vertical line. As for EDCP, the LWE parameters n, q, and α are functions of κ. We present two reductions from LWE to EDCP, the stronger one gives a tighter result for the error-parameter by a factor of √ m.
We introduce a variable κ to relate all the parameters involved in the definitions below. Namely, n, q, etc. are actually functions in κ: n(κ), q(κ). We omit the variable κ for clarity.
Definition 1 (Search LWE). Given a parameter κ, the input to the search LWE m n,q,χ with dimension n ≥ 1, modulus q ≥ 2 and distribution χ over Z, consists of m ≥ n many samples of the form (a, b) ∈ Z n q × Z q , with a ←֓ Z n q , b = a, s +e and e ←֓ χ, where s ∈ Z n q is uniformly chosen. We say that an algorithm solves the search LWE m n,q,χ if it outputs s with probability poly(1/(n log q)) in time poly(n log q).
Definition 2 (Decision LWE). Given a parameter κ, the decisional LWE m n,q,χ with dimension n ≥ 1, modulus q ≥ 2 and distribution χ over Z, asks to distinguish between m ≥ n many LWE samples and random samples of the form (a, b) ∈ Z n q ×Z q , with a ←֓ Z n q , b ←֓ Z q . We say that an algorithm solves the decisional LWE m n,q,χ if it succeeds in distinguishing with probability poly(1/(n log q)) in time poly(n log q).
We let LWE m n,q,α (resp. dLWE m n,q,α ) denote search (resp. decisional) LWE problem with m samples of dimension n, modulus q, error distributed as D Z,αq .
Definition 3 (Dihedral Coset Problem). Given a parameter κ, the input to the DCP ℓ N with modulus N consists of ℓ states. Each state is of the form (normalization is omitted) stored on 1 + ⌈log 2 N ⌉ qubits, where x ∈ Z N is arbitrary and s ∈ Z N is fixed throughout all the states. We say that an algorithm solves DCP ℓ N if it outputs s with probability poly(1/ log N ) in time poly(log N ).
Note that Regev in [24] defines the Dihedral Coset problem slightly differently. Namely, he introduces a failure parameter f (κ), and with probability ≤ 1/(log N (κ) f (κ) ), we have a state of the form |b |x for arbitrary b ∈ {0, 1} n and x ∈ Z N . Such a state does not contain any information on s. Our definition takes 0 for the failure parameter. Conversely, Regev's definition is our Def. 3 with a reduced number of input states. Now we define the problem which can be viewed as an extension of DCP. Analogous to LWE, it has two versions: search and decisional.
Definition 4 (Search Extrapolated Dihedral Coset Problem). Given a parameter κ, the input to the search Extrapolated Dihedral Coset Problem (EDCP ℓ n,N,D ) with dimension n, modulus N and a discrete distribution D, consists of ℓ input states of the form (normalization is omitted) where x ∈ Z n N is arbitrary and s ∈ Z n N is fixed for all ℓ states. We say that an algorithm solves search EDCP ℓ n,N,D if it outputs s with probability poly(1/(n log N )) in time poly(n log N ).
Definition 5 (Decisional Extrapolated Dihedral Coset Problem). Given a parameter κ, the decisional Extrapolated Dihedral Coset Problem (dEDCP ℓ n,N,D ) with modulus N and a discrete distribution D, asks to distinguish between ℓ many EDCP samples and ℓ many random samples of the form where j k ←֓ D 2 and x k ∈ Z n N is uniformly chosen for 1 ≤ k ≤ ℓ. We say that an algorithm solves dEDCP ℓ n,N,D if it distinguishes the two cases with probability poly(1/(n log N )) in time poly(n log N ).
Different choices of D give rise to different instantiations of EDCP. The two interesting ones are: (1) D is uniform over Z M for some M ∈ Z, which we further denote as U-EDCP ℓ n,N,M and (2) D is Gaussian D Z,r , which we further denote as G-EDCP ℓ n,N,r . The former, named the generalized hidden shift problem, was already considered in [8]. The latter is central in our reductions. Correspondingly, we call the decisional version of G-EDCP by dG-EDCP.
Gaussian distribution on lattices. In the following, we recall some important properties of discrete Gaussian distribution. For the sake of completeness, we include the proof in Appendix A.1. From Lemma 1, we can see that the tail of Gaussian distribution has only negligible proportion compared to the whole sum. We use this fact within a quantum superposition state. For a quantum superposition state with Gaussian amplitudes, the superposition corresponding to Gaussian distribution over full lattice and the one without Gaussian tail have exponentially small ℓ 2 distance.

Lemma 3 (Poisson Summation Formula).
For any n-dimensional lattice Λ and vector u ∈ R n , it holds that The following Lemma is originally due to Grover-Rudolph [14] and was adapted to Gaussian distribution in [28].
Lemma 4 (Adapted from [28,Lemma 3.12]). Given a parameter κ and an integer r, there exists an efficient quantum algorithm that outputs a state that is within ℓ 2 distance 2 −Ω(κ) of the normalized state corresponding to x∈Z ρ r (x) |x .
The following two lemmata are well-known facts about lower-bounds on minimum of q-ary lattices.
Lemma 5. Given a uniformly chosen matrix A ∈ Z m×n q for some positive integers q, m and n such that m ≥ n, then we have λ ∞ 1 (Λ q (A)) ≥ q (m−n)/m /2 and λ ∞ 1 (Λ ⊥ q (A)) ≥ q n/m /2 both with probability 1 − 2 −m . Lemma 6. Given a uniformly chosen matrix A ∈ Z m×n q for some positive integer q, m and n such that m ≥ n, then we have λ 1 (Λ q (A)) ≥ min{q, Reductions between EDCP variants. In the following, we show that the EDCP problem is analogue to the LWE problem in many aspects: (1) Gaussian-EDCP (G-EDCP ℓ ′ n,N,r ) and uniform-EDCP (U-EDCP ℓ n,N,M ) are equivalent, up to small parameter losses; (2) EDCP enjoys the self-reduction property as we show in Lemma 10. The main ingredient in both proofs is quantum rejection sampling due to Ozols et al. [21].
for some p k ≤ π k , with probability p 2 = n k=1 p 2 k . Lemma 8 (G-EDCP ≤ U-EDCP). Let N, n and ℓ be integers greater than 1, r be any real number, and let M = c · r for some constant c such that M is an integer. Then there is a probabilistic reduction with run-time polynomial in κ, from G-EDCP ℓ n,N,r to U-EDCP Proof. We are given as input G-EDCP ℓ n,N,r states: Our aim is to find s, given access to a U-EDCP O(ℓ/κ) n,N,cr oracle for some constant c. For each G-EDCP n,N,r sample, we proceed as follows. We let sign(x) to denote the sign of x, its output is either 1 (for ' + ') or 0 (for ' − '). We first compute the sign of the first register and store it in a new register: Second, we measure the third register. Note that we observe 1 with probability at least 1/2, independently over all k's. If the observed value is 0, we discard the state. From states with the observed value 1, we obtain (up to normalization): |j |(x + j · s) mod N with probability Ω(M ρ 2 r (c · r)/r) = Ω(1). We repeat the above procedure until we obtain O(ℓ/κ) many U-EDCP n,N,M states, which happens with probability ≥ 1 − 2 −Ω(κ) . We call the U-EDCP O(ℓ/κ) n,N,M oracle to recover the secret s as the solution for the input G-EDCP ℓ n,N,r instance. Proof. We are given as input ℓ many U-EDCP ℓ n,N,M states: Our aim is to find s, given access to a G-EDCP Using rejection sampling (Lemma 7), with probability Ω(r/M ) = Ω(1/ √ κ) we transform each U-EDCP n,N,⌈ M −1 2 ⌉ state into a G-EDCP n,N,r state: According to Lemma 1, the latter is within the ℓ 2 distance of 2 −Ω(κ) away from the state We repeat the above procedure until we obtain O(ℓ/κ 1.5 ) many G-EDCP n,N,r states, which happens with probability ≥ 1 − 2 −Ω(κ) . Then we can use the G-EDCP O(ℓ/κ 1.5 ) n,N,r oracle to recover the secret s as the solution to U-EDCP ℓ n,N,M . Next, we show the self-reducibility property for EDCP. We refer the reader to Appendix A.2 for the proof.
Lemma 10 (EDCP self-reduction). Let N, n, and ℓ be integers greater than 1, r 1 and r 2 be such that r 1 > r 2 and r 1 /r 2 = O(κ c ) for any constant c. Then there is a probabilistic reduction with run-time polynomial in κ, from G-EDCP ℓ n,N,r1 ).
In the following, we give a reduction from Gaussian-EDCP to DCP. Thus uniform-EDCP can also be reduced to DCP in two ways: either via self-reduction, or via Gaussian-EDCP as the next lemma shows. This result is especially interesting when the parameter r (or M for the uniform-EDCP) is super-polynomially large, as in this case, Lemma 10 cannot be applied. Lemma below works with 1-dimensional EDCP. This is without loss of generality as we can combine our main result (equivalence of LWE and EDCP) with the result of Brakerski et al. [6] (equivalence of LWE n,q,α and LWE 1,q n ,α ). Proof. We are given as input ℓ many G-EDCP 1,N,r states: We show how to find s if we are given access to a DCP wherex k = x k − M · s. We measure the third register and denote the observed value by v k . We make use of the two well-known facts from number theory. For proofs, the reader may consult [29,Chapter 5]. First, there exist more than M/ log M many primes that are smaller than M . Second, N has at most 2 log N/ log log N prime factors. Thus there are at least M/ log M − 2 log N/ log log N many numbers smaller than M that are co-prime with all prime factors of N .
From the above, with probability Ω(1/ log M ) = Ω(1/ log r), the observed value v k is non-zero and co-prime with N . If this is not the case, we discard the state. Otherwise, we obtain (up to normalization): We multiply the value in the second register by v −1 k mod N : Rewrite the above state as: |−v k |x k + |v k |(x k +s) mod N .
As we know v k classically, we uncompute the first register and obtain a DCP state: |0 |x k + |1 |(x k +s) mod N .
• Case that r < 3 log N .
The first steps are identical to the proof for the case r ≥ 3 log N : Compute the absolute value of the first register to get a state as in (4) and measure the third register. Denote the observed value by v k . Now we keep only those states, for which v k = 1 was observed. Otherwise, we do not use the state. In case v k = 1, we can easily transform the result to the state given in (5) analogously to the proof for r ≥ 3 log N . Now we show that v k = 1 occurs with probability Ω(1/r) independently over all k's. Indeed, We repeat the above procedure until we obtain O(ℓ/(r · κ)) many DCP N states, which happens with probability ≥ 1 − 2 −Ω(κ) . In both cases considered in this lemma, we can use the DCP O(ℓ/(r·κ)) N oracle and get the secrets. There are at most 2 possible values s such thats = 2s mod N : if there are 2 possibilities, we uniformly choose either, which decreases the success probability by at most a factor of 2.

Reduction from LWE to EDCP
In this section, we reduce LWE m n,q,α to G-EDCP ℓ n,q,r , where r ≈ 1/α up to a factor of poly(n log q). Analogous to Regev's reductions from uSVP to DCP, we present two versions of the reduction from LWE to G-EDCP. The second one is tighter with respect to the parameter losses. At the end of the section we show that using the same algorithm, one can reduce the decisional version of LWE to the decisional version of EDCP (see Def. 5).

First reduction: using cube separation
The main result of this section is the following theorem.
Theorem 2 (LWE ≤ EDCP). Let (n, q, α) be LWE parameters and (n, q, r) be EDCP parameters. Given m = n log q = Ω(κ) many LWE n,q,α samples, there exists a probabilistic quantum reduction, with run-time polynomial in κ, from LWE m n,q,α to G-EDCP ℓ n,q,r , where r < 1/(32mκαℓq n/m ). The main step of our reduction is to partition the ambient space R m with an appropriately chosen grid (cubes). This is analogous to Regev's reduction from uSVP to DCP [24]. Lemma 12 shows how we choose the width of the cell in our grid. Figure 2 gives a 2-dimensional example of such a grid.
Proof. • Proof for the first claim. Write u = Ax + e 1 mod q and v = Ax + e 2 mod q for some x ∈ Z n q and e 1 ∞ , e 2 ∞ ≤ λ ∞ 1 (Λ q (A))/(2ck). Fig. 5: Quantum circuit for our reduction LWE ≤ EDCP. All the global phases are omitted. The input registers are assumed to have the required number of qubits. Function f is defined as U f |j |s |0 → |j |s |As − jb mod q . Function U g is the embedding of function g described in Lemma 12, i.e. U g |x |0 → |x |⌊x/z − w modq⌋ for appropriately chosen z, w,q.
We use Lemma 4 to obtain a state within ℓ 2 distance of 2 −Ω(κ) away from s∈Z n q j∈Z ρ r (j) |j |s |0 .
We evaluate the function f (j, s) → As − j · b mod q and store the result in the third register. The next equality follows from a change of variable on s ρ r (j) |j |s + js 0 |As − je 0 .
For x ∈ Z m q , we define whereq = q/z = c. We evaluate the function g on the third register and store the result on a new register. We obtain ρ r (j) |j |s + j · s 0 |As − j · e 0 |g(As − j · e 0 ) .
Finally, we evaluate the function (j, s, b) → b − As + j · b 0 on the first three registers, which gives 0. Discarding this 0-register, the state is of the form According to Lemma 1, the above state is within ℓ 2 distance of 2 −Ω(κ) away from j∈Z ρ r (j) |j |s + j · s 0 .
We repeat the above procedure ℓ times, and with probability (1 − 1 k ) mℓ , we obtain ℓ many G-EDCP ℓ n,q,r states   where x k ∈ Z n q . Now we can call the G-EDCP ℓ n,q,r oracle with the above states as input and obtain s 0 as output of the oracle.

An improved reduction: using balls' intersection
Here we give an improved reduction from LWE to EDCP. Following the idea of Regev ([24][Section 3.3]), instead of separating the ambient space Z m by cubes, we consider intersections of balls drawn around the points As and its shifts. Note that with this reduction we improve the upper-bound on r essentially by the factor of √ m.
We give an intuitive idea of how the reduction works. All the necessary lemmata and the full proof are given in Appendix B.
Informally, the reduction works as follows. Given an LWE instance (A, b = As 0 + e 0 ) ∈ Z m×n q × Z m q , for each s ∈ Z n q , we consider (in a superposition over all such s) a lattice point As together with its small shifts of As − je 0 , where j's are drawn from a small interval symmetric around 0. So far this is exactly what we did in the first (weaker) reduction. Note that we receive a configuration of points in Z m q as depicted in Figure 3. Note that contrary to Regev's reduction, where there is only one shift (i.e., the DCP case), our extrapolated version considers poly(κ) shifts thus leading us to the EDCP case.
Let us fix some As together with its shifts. Draw a ball around each shift of a maximal radius R such that there is no intersection between the shifts coming from different lattice points, i.e. there is no j, j ′ s.t. B(As − je 0 , R) ∩ B(As ′ − j ′ e 0 , R) = ∅ for any two s, s ′ such that s = s ′ . To satisfy this condition, we can take R almost as large as the first minimum of the lattice Λ q (A) (again, see Figure 3). With such an R, due to the fact that the shifts are small, the intersection of the balls drawn around the shifts is large enough (see Lemma 13 in Appendix B). Hence, once we measure the register that 'stores' our balls, the resulting state collapses (with large enough probability) to a superposition of some As for one s and all its shifts. Informally, the higher this probability is, the tighter the parameters achieved by the reduction.

Reduction from dLWE to dEDCP
As a corollary to the above theorem, we show that the decisional LWE can be reduced to decisional EDCP. In fact, to establish the reduction, we use the same algorithm as for Theorem 3 (a weaker reduction given in Theorem 2 will work as well). Recall that in the proof, starting from an EDCP sample, we obtain an LWE sample with non-negligible probability. Corollary 1 below shows that in case we are given a tuple (A, b) drawn uniformly at random from Z m×n q × Z m q , the procedure described in Theorem 3 outputs a state of the form |j |x mod N , a uniform counterpart to EDCP in the sense of Definition 5. The proof of the following corollary is given in Appendix B.

Reduction from EDCP to LWE
In this section, we reduce G-EDCP ℓ n,N,r to LWE ℓ n,N,α , where r ≈ 1/α up to a factor of poly(n log N ). Combined with the result of the previous section, this gives us equivalence between the two problems: LWE and EDCP, for both search and decisional variants. .
Our aim is to find s 0 given access to an LWE ℓ n,N,α oracle. For each input state, the quantum Fourier transform over Z n N is applied to the second register, which yields (without loss of generality, consider the k th sample) Then we measure the second register and let a k denote the observed value. Note that each element of Z n N is measured with probability 1/N n and that the distributions for different k's are independent. Omitting the global phase of each state, we obtain j∈Z ω j· s0,a k N · ρ r (j) |j |a k .
We omit the second register as we know each a k classically. Since N ≫ r, from Lemma 1 it follows that the resulting state is within ℓ 2 distance of 2 −Ω(κ) away from the state j∈ZN ω j· a k ,s0 N · ρ r (j) |j .
For each such an input state, the quantum Fourier transform over Z N yields b∈ZN j∈ZN ω j·( a k ,s0 +b) N · ρ r (j) |b .
Once again we use Lemma 1 to argue that the state above is within ℓ 2 distance of 2 −Ω(κ) away from the state b∈ZN j∈Z ω j·( a k ,s0 +b) N · ρ r (j) |b .
Using the Poisson summation formula (Lemma 3) and changing the summation variable to e ← N · j + a k , s 0 + b, the above state can be rewritten as b∈ZN j∈Z where a ′ k = −a k mod N . Since r = Ω( √ κ), we can apply Lemma 1 to the above state (for a scaled Z-lattice), and instead of the above state, consider the state that is within a 2 −Ω(κ) ℓ 2 -distance from it, namely: Once we measure the state above, we obtain an LWE sample where e k ←֓ D Z,N/r . Now we can call the LWE n,N,α oracle for α = 1/r with the above states as input and obtain s 0 as output of the oracle.

Reduction from dEDCP to dLWE
Similar to the previous section where as a corollary we show that dLWE can be reduced to dEDCP, we finish this section by a reverse reduction. Again we use exactly the same reduction algorithm as for the search versions (see Figure 6). Thus it remains to show that we can obtain a uniform random sample (a, b) ∈ Z n N × Z N given as input a state of the form |j |x mod N . Corollary 2 (dEDCP ≤ dLWE). Let (n, N, r) be valid dG-EDCP parameters and (n, N, α) be valid dLWE parameters. Given ℓ = Ω(κ) many EDCP n,N,r samples, there exists a quantum reduction, with run-time polynomial in κ, from dG-EDCP ℓ n,N,r to dLWE ℓ n,N,α , where α = 1/r. Proof. Assume we are given ℓ many samples of EDCP n,N,r either of the form or of the form where j k ←֓ D 2 Z,r and x k ∈ Z n N is uniform. Our aim is to distinguish between the above two forms given access to a dLWE n,N,α oracle.
As explained above, we assume that random samples of EDCP are given. For each input state, after the quantum Fourier transform over Z n N on the second register, we obtain Then we measure the second register and let a k denote the observed value. Note that each element of Z n N is measured with probability 1/N n and that the distributions for different k's are independent. Up to a global phase, we have |j k |a k .
We omit the second register which is known to us. According to Lemma 1, with probability 1 − 2 −Ω(κ) , the value stored in the first register is in the range [−⌊N/2⌋, ⌈N/2⌉ − 1]. Applying QFT over Z N to the first register, we obtain b∈ZN ω j k ·b N |b .
Once we measure the state above and let b k denote the observed value. Note that each element of Z N is measured with probability 1/N and that the distributions for different k's are independent. We obtain a sample where (a k , b k ) are uniformly random from Z n N × Z N .
The same arguments apply to the uniform EDCP: from U-EDCP N,ℓ,r1 to U-EDCP N,O(ℓ/κ c+1 ),r2 In this case, via quantum rejection sampling, we transform a wide uniform distribution into a narrow uniform distribution.

B.1 Proof of Theorem 3
We need two lemmata to establish a proof of Theorem 3. The first lemma due to Regev (see [24,Corollary 3.9]) shows how large the intersection of two shifted balls is. Note that a quantum state we work with is a discretized ball 1 L Z n ∩ B n (0, R). The difference between Regev's lemma and the one we present below is that we consider intersections of the balls taken mod q.
Lemma 13 (Adapted from [24,Corollary 3.9]). Let L = 2 n and consider the scaled integer grid 1 L Z n . For any R ≥ 1, letB n (0, R) = B n (0, R) +d for some vectord such that R/poly(n) ≤ d ≤ R. Then, for an integer q > 2R +d we have The following technical lemma is again due to Regev [24]. It shows that while we cannot create a quantum state that perfectly corresponds to a uniform superposition of x ∈ 1 L Z n ∩ B n (0, R) (i.e., a ball), we can have a good approximation to this state. This fact will only increase the running time of the reduction by a factor of poly(κ).
Lemma 14 ([24, Lemma 3.11]). For any 1 ≤ R ≤ 2 poly(n) , let |x be the uniform superposition on grid points inside a ball of radius R around the origin where L = 2 n . Then, for any c > 0, a state |η whose trace distance from |η is at most 1/n c can be efficiently computed.
Now we are ready to give the proof of Theorem 3.
Proof (of Theorem 3). Assume we are given an LWE n,q,α instance (A, b 0 ) ∈ Z m×n q × Z m q , with b 0 = As 0 + e 0 mod q. Our aim is to find s 0 given access to a G-EDCP ℓ n,q,r oracle.
We first prepare a necessary number of registers in the state |0 and transform it to the state of the form (normalization omitted) s∈Z n q |0 |s |0 .
We use Lemma 4 to obtain a state within ℓ 2 distance of 2 −Ω(κ) away from s∈Z n q j∈Z ρ r (j) |j |s |0 .
We evaluate the function f (j, s) → As − j · b mod q and store the result in the third register. A change of variable on s yields ρ r (j) |j |s + js 0 |As − je 0 .
We take an auxiliary register |0 . We set L = 2 m as a discretization parameter and R = Θ( √ mq (m−n)/m ). As the LWE problem is well defined with m = Θ(n) many samples, it suffices to satisfy √ mq (m−n)/m /(3 √ 2πe) ≤ q. Thus according to Lemma 6, we also have R ≤ λ 1 (Λ q (A))/3, where the inequality holds with probability 2 −m = 2 −Ω(κ) for some appropriate choice of constants. Using Lemma 14, we prepare a state which is at most 1/n c away from |η = x∈ 1 L Z m ∩Bm(0,R) |x for any constant c > 0. We set c such that it satisfies (1 − 1/n c ) > (1 − 1/κ) to have the success probability claimed at the end of the reduction. We pretend we work with the state |η , which we tensor with our current state, and obtain ρ r (j) |j |s + j · s 0 |A · s − j · e 0 |x .
We apply the function g(x, y) = (x, x + y mod q) on the third and fourth registers (note that the mod q operation is done over rational numbers). The state becomes a superposition over the balls of radius R centered at all lattice points As and their shifts defined by j. Formally, we obtain ρ r (j) |j |s + j · s 0 |As − j · e 0 |As − j · e 0 + x mod q .
Note that due to the minimal distance of Λ q (A), the balls emerging from two different lattice points (or their shifts) do no intersect. Hence, the measurement yields ρ r (j) |j |s + j · s 0 |As − j · e 0 for some s ∈ Z n q , with probability O(1 − 1/ℓ) taken over the uniform distribution defined on B m (0, R).
Finally, we evaluate the function (j, s, b) → b − As + j · b 0 on the first three registers. Discarding the last register, the state is of the form ρ r (j) |j |s + j · s 0 .
We repeat the above procedure ℓ times, and with non-negligible probability (1 − 1/ℓ) ℓ , we obtain ℓ many G-EDCP n,q,r states    j∈Z ρ r (j) |j |x k + j · s 0    k≤ℓ , where x k ∈ Z n q . Now we can call the G-EDCP m n,q,r oracle with the above states as input and obtain s 0 as the output of the oracle.
Proof (of Corollary 1). We are given m many samples from Z m×n q × Z m q either of the form (A, As 0 + e 0 ), or of the form (A, b), where A ∈ Z m×n q is uniformly chosen, s 0 ∈ Z n q is fixed, e 0 ∈ D Z m ,αq and b ∈ Z m q is uniformly chosen and independent from a. Our aim is to distinguish between the above two cases given access to a dG-EDCP ℓ n,q,r oracle. We follow the procedure of the reduction algorithm used in the proof of Theorem 3 except that now we set R = Θ( √ mq (m−n−1)/m ). As the LWE problem is well defined with m = Θ(n) many samples, we can guarantee (for an appropriate choice of constants) that √ mq (m−n)/m /(3 √ 2πe) ≤ q. Thus, we also have R ≤ λ 1 (Λ q (A|b))/3, where the inequality holds with probability 2 −m = 2 −Ω(κ) (see Lemma 6). We run the algorithm described in the proof of Theorem 3 until we obtain a state of the form ρ r (j) |j |s |As − j · b |As − j · b + x .
We measure the fourth register and ignore it from now on. Due to the bound on r, we have q ≥ 2 √ κr. Thus all the balls created with centers over the lattice points As and their shifts As − jb, do not intersect with each other. Therefore, with probability 1 − O(1/ℓ) we obtain |j k |s k |As k − j k · b for some j k ∈ Z is distributed as D 2 Z,r and some uniform s k ∈ Z n q . Finally, we evaluate the function (j, s, b) → b − As + j · b 0 on the first three registers. This zeroizes the last register, which we can safely discard. Now the state is of the form |j k |s k , where j k ←֓ D 2 Z,r and s k ∈ Z n q is uniformly chosen. We repeat the above procedure ℓ times, and with probability (1 − O(1/ℓ)) ℓ , we obtain ℓ many random samples of the form where s k is chosen uniformly at random from Z n q . This is exactly an input to dEDCP with respect to of Definition 5.