LWE ⇒ PKE

Fully-black-box reduction · standard model · Reg05 · security loss: tight up to a factor 2: one run of the CPA adversary on the LWE samples as public key, whose advantage is at most twice the LWE advantage plus a statistical leftover-hash term

Statement

If LWE is hard with polynomial modulus-to-noise ratio, then Regev’s scheme is an IND-CPA-secure PKE for one-bit messages: the public key is $m$ LWE samples, and a bit $\mu$ is encrypted as a random subset-sum of them plus $\mu \lfloor q/2\rfloor$ — Reg05. Reg05 take a prime $q\in [n^2,2n^2]$, $m=(1+\epsilon )(n+1)\log q$ for a constant $\epsilon >0$, and as noise a Gaussian of width $\alpha q$ rounded to the nearest integer, with noise rate $\alpha =o(1/(\sqrt{n}\log n))$, for instance $\alpha =1/(\sqrt{n}{\log }^{2}n)$; they prove that for every $m\ge (1+\epsilon )(n+1)\log q$ an efficient adversary distinguishing encryptions of $0$ and $1$ gives an efficient distinguisher between the $m$ LWE samples of the public key and uniform — Reg05. That reduction does not use the noise distribution, so with discrete Gaussian noise of width $\alpha q$ at $\alpha =1/n$, which lies in this range and has $\alpha q\ge n\ge 2\sqrt{n}$ for $n\ge 4$, the scheme is correct except with negligible probability and IND-CPA-secure under the polynomial-ratio assumption at $c=1$ — standard.

Sketch

$\mathsf{KeyGen}$ outputs $\mathsf{pk}=(\mathbf{A},\mathbf{b}=\mathbf{As}+\mathbf{e})$ and $\mathsf{sk}=\mathbf{s}$; $\mathsf{Enc}(\mathsf{pk},\mu )$ samples $\mathbf{r}\stackrel{\$}{\leftarrow }\{0,1{\}}^m$ and outputs $({\mathbf{r}}^{\top }\mathbf{A},{\mathbf{r}}^{\top }\mathbf{b}+\mu \lfloor q/2\rfloor )$, and $\mathsf{Dec}(\mathsf{sk},({\mathbf{c}}_1,c_2))$ rounds $c_2-⟨{\mathbf{c}}_1,\mathbf{s}⟩={\mathbf{r}}^{\top }\mathbf{e}+\mu \lfloor q/2\rfloor$ to whichever of $0$ and $\lfloor q/2\rfloor$ is closer modulo $q$, which is correct when $|{\mathbf{r}}^{\top }\mathbf{e}|<\lfloor q/2\rfloor /2$. With $\mathbf{e}$ discrete Gaussian of width $\alpha q$, ${\mathbf{r}}^{\top }\mathbf{e}$ is subgaussian with parameter $\alpha q\sqrt{m}$, and $\lfloor q/2\rfloor /2\ge q/5$ for $q\ge 5$, so decryption fails with probability at most $2e^{-\pi /(25{\alpha }^{2}m)}$, which is negligible at $\alpha =1/n$ since $m=O(n\log n)$ — standard. Decision LWE replaces $(\mathbf{A},\mathbf{b})$ by uniform, after which $({\mathbf{r}}^{\top }\mathbf{A},{\mathbf{r}}^{\top }\mathbf{b})$ is statistically close to uniform by the leftover hash lemma, since $m\ge (1+\epsilon )(n+1)\log q$, so the ciphertext hides $\mu$.

Notes

• Efficiency: the public key has $m(n+1)=\tilde{O}(n^2)$ elements of ${\mathbb{Z}}_q$, and a one-bit ciphertext has $n+1$ of them, so encryption expands messages by a factor $\tilde{O}(n)$ — Reg05. Over rings, a ciphertext is two ring elements, about $2n\log q$ bits, carrying $n$ packed message bits, so for polynomial $q$ the expansion is $O(\log q)=\tilde{O}(1)$ for $n$-bit messages but $O(n\log q)$ for a single bit; keys shrink to $\tilde{O}(n)$ bits — LPR10.