Prove that decryption in LWE based PK cryptosystem works correctly except with negligible probability

Question

The LWE cryptosystem is defined as follows:

Key Generation:
Secret key: random vector $s \in F_q^n$.

Public key: $\{c_i\}_{i=1}^m$, where $c_i = (\textbf{a}_i, \textbf{a}_i \cdot \textbf{s} + e_i)$, where $\textbf{a}_i$ are uniformly random, and the $e_i$ are chosen according to $D_e$.

Encryption: Message is a bit $w$. Choose random bits $b_1,\ldots,b_m$ and then the ciphertext is $\sum_{i=1}^m b_ic_i+(0,\lceil q/2 \rceil w)$.

Decryption: To decrypt $(u,v)$, compute $v-\textbf{s}\cdot \textbf{u}$, and output $0$ if this value is closer to $0$ than it is to $\lceil q/2 \rceil$. Otherwise, output $1$.

The distribution $D_e$ is defined as follows:

$D_e$ satisfies $\sum_{i=1}^{m}e_i < q/4$ for $e_i$ chosen according to $D_e$. Here, $e_i$ are small numbers, and $q$ is some positive integer.

Now, $\textbf{v}-\textbf{s}\cdot \textbf{u} = (\sum_{i=1}^m b_ic_i + \lceil q/2 \rceil w) - (\textbf{s}\cdot \sum_{i=1}^m b_ic_i)= ...$, but then I'm stuck.

Can someone help me out?

Answer 1

Denote the public key as $({\bf a}_i, a'_i)_{i=1}^m,$ with each "sample" in $\mathbb{F}_q^n \times \mathbb{F}_q,$ where $a'_i = \langle {\bf a}_i, {\bf s}\rangle + e_i$ with each $e_i \leftarrow D_e$ i.i.d. (guaranteed that $\sum_{i=1}^m e_i < q/4$ with overwhelming probability).

Consider an encryption of 0 given by $\mathsf{ct} = ({\bf u}, v)$ over the private random coins $(b_i)_{i=1}^m,$ where ${\bf u} = \sum_{i=1}^m b_i{\bf a}_i \in \mathbb{F}_q^n$ and $v = \sum_{i=1}^m b_ia'_i \in \mathbb{F}_q$

(You can consider the case of an encryption of 1, by just adding $\lceil q/2\rceil$ to $v,$ of course.)

The decryption algorithm applied to $\mathsf{ct} = ({\bf u}, v)$ will output 0, correctly, so long as $v - \langle {\bf u}, {\bf s}\rangle$ is closer to 0 than $q/2$; that is, if $|v - \langle {\bf u}, {\bf s}\rangle| < q/4.$

And $$v - \langle {\bf u}, {\bf s}\rangle = \sum_{i=1}^m b_ia'_i - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$ and since $a'_i = \langle {\bf a}_i, {\bf s}\rangle + e_i,$ we get that the above is then $$... = \sum_{i=1}^m b_i\left(\langle {\bf a}_i, {\bf s}\rangle + e_i\right) - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$ $$= \sum_{i=1}^m b_i\langle {\bf a}_i, {\bf s}\rangle + \sum_{i=1}^m b_ie_i - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$ $$= \sum_{i=1}^m b_ie_i.$$

Since we are guaranteed (except with $\mathsf{negl}(n)$ probability..) that $\sum_{i=1}^m e_i < q/4,$ we conclude that $|v - \langle {\bf u}, {\bf s}\rangle| < q/4$ implying correctness of decrypting 0-bits. The proof for 1-bits is the same -- but you'd end up with $\sum_{i=1}^m b_ie_i + \lceil q/2\rceil$ at the end, so the result would be closer to $q/2$ than 0, again by the upper bound w.h.p. on sums of $m$ small errors that you started with.