6
$\begingroup$

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".

Could anyone please tell me the details about this step?

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

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

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Excellent answer! $\endgroup$ – Chris Peikert Apr 7 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.