1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\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$ Commented 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$ Commented 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$ Commented Nov 26, 2016 at 17:11
  • $\begingroup$ Isnt it wrong to take absolute value of elements within field $F_q$? $\endgroup$ Commented 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$ Commented Nov 26, 2016 at 21:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.