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?


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

  • $\begingroup$ Thanks for your answer! The text I'm reading is a bit ambigious, I think. Do you ignore that $c_i = (\textbf{a}_i, \textbf{a}_i \cdot \textbf{s} + e_i)$ and instead write $c_i = \textbf{a}_i \cdot \textbf{s} + e_i$? Also, I see that $\textbf{a}_i$ are scalars, but in the text $e_i$ is previously mentioned as scalars. Here they are vectors, or? $\endgroup$
    – Shuzheng
    Nov 26, 2016 at 16:55
  • $\begingroup$ There are multiple, equivalent ways to write them.. You should read $c_i = ({\bf a}_i, {\bf a}_i\cdot {\bf s} + e_i)$ as a 2-tuple composed of a vector of length $n$ and a scalar. ...Or, you could just as well have written it as a vector of length $n+1.$ Etc... For my answer, I tried to separate these as ${\bf bold for vectors}$ and $not bold for scalars$ $\endgroup$ Nov 26, 2016 at 17:06
  • 1
    $\begingroup$ Ahh, thanks.-The $c_i$'s have really confused me. Didn't realize it was an $n+1$ vector before now.... The operations makes sense now. $\endgroup$
    – Shuzheng
    Nov 26, 2016 at 17:11
  • $\begingroup$ Isnt it wrong to take absolute value of elements within field $F_q$? $\endgroup$
    – Shuzheng
    Nov 26, 2016 at 18:58
  • $\begingroup$ In a general context, yes.. But we need a way to say that the element $q-1$ is "closer to 0 than not," and again, there are multiple, 'consistent' ways to write things. For instance, I may choose to sample errors $e$ from some $B$-bounded Gaussian over the integers centered at 0 ($B \ll q$). The arithmetic actually ends up being simpler to write this way overall, but you certainly don't want $-1\mod q$ to be treated as "large." Anyway, the point is that the magnitude of all accumulated error -- at the point of decryption -- is bounded sufficiently short of the public modulus $q.$ $\endgroup$ Nov 26, 2016 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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