# Decision to Search LWE when modulus $q=p^e$

I am reading Applebaum et al..

In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $$q=p^e$$ for prime $$p$$.

In the proof, they define the hybrid distribution $$A^i_{\mathbf{s},\chi}$$ and say "By a hybrid argument and standard amplification techniques, we can use an algorithm $$D$$ that distinguishes between $$A_{\mathbf{s},\chi}$$ and $$U$$ to solve for $$\mathbf{s^\prime}=\mathbf{s} \mod p$$".

I don't understand this step clearly.

Also, I cannot find the full version that includes the "entire proof".

In particular, how to use the "standard amplification techniques"?

• Did you contact the authors? Usually, they wrote an extended version of their papers. – kelalaka Feb 24 at 11:53
• @kelalaka I have sent an email to all authors of this paper on 26.2.2020, but I have not received any reply yet. – M.Z. Mar 1 at 7:41

First of all, it is a search to decision reduction: we are using an algorithm that distinguishes $$A_{\mathbf{s},\chi}$$ (the LWE distribution with secret $$\mathsf{s}\in \mathbb{Z}_q^n$$ and error distribution $$\chi$$) from $$U$$ (the uniform distribution on $$\mathbb{Z}_q^n\times\mathbb{Z}_q$$) in order to find the secret vector $$\mathbf{s}=(s_1,\cdots,s_n)$$. A decision to search reduction for LWE (like for most other problems) is trivial.

Let's see first how the reduction works when $$q$$ is prime [R, Lemma 4.2].

Prime $$q$$. Suppose we have a distinguisher $$\mathsf{D}$$ for LWE that works with overwhelming probability (i.e., $$1-\mathsf{negl}(n)$$) -- any distinguisher $$\mathsf{D}'$$ that works with probability that is bounded away from half by a non-negligible value can be turned into one that works with overwhelming probability using standard amplification techniques: i.e., carry out independent trials, take the majority and apply the Chernoff bound (see e.g., [AB, Lemma 7.9] to see how this is used for $$\mathbf{BPP}$$). We will use $$\mathsf{D}$$ to construct an algorithm $$\mathsf{F}$$ that finds $$\mathbf{s}$$ as follows. For $$k\in\mathbb{Z}_q$$ and $$l\leftarrow\mathbb{Z}_q$$ (where $$\leftarrow$$ denotes sampling uniformly at random), consider the transformation $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l,0,\cdots,0),b+lk).$$ If $$s_1$$ denotes the first entry of the secret vector $$\mathbf{s}$$ in the LWE distribution $$A_{\mathbf{s},\chi}$$, there are two cases:

1. $$k=s_1$$: here, the transformation maps $$A_{\mathbf{s},\chi}$$ to itself, as shown below $$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(l,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+ls_1\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e\right)=(\mathbf{a}',b'),$$ where $$\mathbf{a}'$$ denotes the vector $$\mathbf{a}+(l,0,\cdots,0)$$.

2. $$k\neq s_1$$: the transformation maps $$A_{\mathbf{s},\chi}$$ to the uniform distribution (as $$l$$ masks everything).

Now it is easy to recover $$s_1$$: $$\mathsf{F}$$ simply runs $$\mathsf{D}$$ over all $$k\in\mathbb{Z}_q$$ and outputs the $$k$$ for which $$\mathsf{D}$$ outputs $$0$$ (indicating "LWE"). Since the size of the modulus $$q\leq\mathsf{poly}(n)$$, this is still efficient. The remaining entries of $$\mathbf{s}$$ can be recovered by iterating the above procedure, shifting the $$(l,0,\cdots,0)$$ vector to the right in each iteration. $$\square$$

Note that the step in the proof which requires $$q$$ to be prime is the second case ($$k\neq s_1$$): if $$q$$ is composite then the map $$b\mapsto b+lk\bmod{q}$$ is not necessarily bijective and the distribution gets skewed away from uniform when $$l$$ is one of the factors of $$q$$. Extending this to the case when $$q=p^e$$ was sketched in [ACPS, Lemma 1]. The complete proof can be found in [MP, Theorem 3.1] (albeit phrased differently from below).

Prime power $$q=p^e$$. For simplicity, let's focus on $$e=2$$ as the argument can be easily extended for $$e>2$$. For $$i=0,1,2$$, consider the distributions $$A_{\mathbf{s},\chi}^i:=\left\{(\mathbf{a},b+r\cdot p^{2-i}\bmod{q}):(\mathbf{a},b)\leftarrow A_{\mathbf{s},\chi},r\leftarrow\mathbb{Z}_q\right\}.$$ Note that $$A_{\mathbf{s},\chi}^0$$ is identical to $$A_{\mathbf{s},\chi}$$ as $$r\cdot p^2=0 \bmod{p^2}$$. On the other hand, $$A_{\mathbf{s},\chi}^2$$ is identical to $$U$$, the uniform distribution on $$\mathbb{Z}_q^n\times\mathbb{Z}_q$$ as $$r$$ masks everything.

Step $$1$$. The first step is to use the distinguisher $$\mathsf{D}$$, which distinguishes $$A_{\mathbf{s},\chi}^0$$ from $$A_{\mathbf{s},\chi}^2$$ to extract $$\mathbf{s}'=\mathbf{s}\bmod{p}$$. By the hybrid argument, it is guaranteed that $$\mathsf{D}$$ distinguishes $$A_{\mathbf{s},\chi}^0$$ from $$A_{\mathbf{s},\chi}^1$$ or $$A_{\mathbf{s},\chi}^1$$ from $$A_{\mathbf{s},\chi}^2$$ with overwhelming probability. We show that in either of the cases it is possible to extract $$\mathbf{s}'=\mathbf{s}\bmod{p}$$ using the ideas we saw for the case when $$q$$ is prime. Let's focus on the first case as the second case is analogous, and the only difference is in the transformation.

Case $$1$$. We are given a distinguisher $$\mathsf{D}$$ that distinguishes $$A_{\mathbf{s},\chi}^0$$ from $$A_{\mathbf{s},\chi}^1$$ with overwhelming probability. The idea is to use a slightly different transform from the previous case. To be precise, we use $$(\mathbf{a},b)\mapsto(\mathbf{a}+(lp,0,\cdots,0),b+lkp),$$ where $$l\leftarrow\mathbb{Z}_q$$ (as before) and $$k\in\mathbb{Z}_p$$. If $$s_1=s_1'+s_1''p$$, there are two cases:

1. $$k=s_1'$$: the transformation maps $$A_{\mathbf{s},\chi}=A_{\mathbf{s},\chi}^2$$ to itself, as shown below $$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(lp,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+lps_1'\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e\right)=(\mathbf{a}',b').$$ Here, we use the fact that $$(a_1+lp)s_1=a_1s_1+lp(s_1'+s_1''p)=(a_1s_1+s_1'lp)\bmod{p^2}$$, where $$a_1$$ is the first component of $$\mathbf{a}$$.

2. $$k\neq s_1'$$: the transformation maps $$A_{\mathbf{s},\chi}$$ to $$A_{\mathbf{s},\chi}^1$$ as $$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(lp,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+lpk\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e+rp\right),$$ where $$r=lk\bmod{q}$$. Here, multiplying by $$k$$ preserves the distribution $$l\leftarrow\mathbb{Z}_q$$ since $$k$$ is coprime to $$p$$.

Now we recover $$s_1'=s_1\bmod{p}$$ as before: $$\mathsf{F}$$ simply runs $$\mathsf{D}$$ over all $$k\in\mathbb{Z}_p$$ and outputs the $$k$$ for which $$\mathsf{D}$$ outputs $$0$$ (indicating "LWE"). $$\mathbf{s}'=\mathbf{s}\bmod{p}$$ is obtained by the shifting trick.

Case $$2$$. Now, given a distinguisher $$\mathsf{D}$$ that distinguishes $$A_{\mathbf{s},\chi}^1$$ from $$A_{\mathbf{s},\chi}^2$$ with overwhelming probability, the only difference is in the transform, which is now $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l,0,\cdots,0),b+pr+lk),$$ for $$l$$, $$k$$ as above and $$r\leftarrow\mathbb{Z}_q$$. Note that when $$k=s_1'$$ the transformation maps $$A_{\mathbf{s},\chi}$$ to $$A_{\mathbf{s},\chi}^1$$ and when $$k\neq s_1'$$ it maps $$A_{\mathbf{s},\chi}$$ to $$A_{\mathbf{s},\chi}^2=U.$$

For general $$e>2$$, the hybrid distributions are defined as $$A_{\mathbf{s},\chi}^i:=\left\{(\mathbf{a},b+r\cdot p^{e-i}\bmod{q}):(\mathbf{a},b)\leftarrow A_{\mathbf{s},\chi},r\leftarrow\mathbb{Z}_q\right\}$$ and the $$i$$-th transformation is $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l\cdot p^{e-j},0,\cdots,0),b+(pr+lk)\cdot p^{e-j}).$$

Step $$2$$. Given $$\mathbf{s}'=\mathbf{s}\bmod{p}$$, $$\mathbf{s}$$ can be recoved as described in [ACPS]. $$\square$$

[AB]: Arora and Barak, Computational Complexity: A Modern Approach

[ACPS]: Applebaum et al., Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems, Crypto 2009

[MP]: Micciancio and Peikert, Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Eurocrypt 2012

[R]: Regev, On lattices, learning with errors, random linear codes, and cryptography, JACM 2009

• Excellent answer! – Chris Peikert Apr 7 at 2:21