I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme.

The encryption goes as follows:

given a message $m \in R_2 $ and sampling a secret key $s$ from a distribution $\chi$, one samples $a$ from $R_q$ and $e \leftarrow \chi$, the ciphertext $c$ is a pair such that $c = ( c_0,c_1) = (a, as+2e+m)$.

To decrypt:

given $c=(c_0,c_1)$ one computes $c_0 + c_1s ~~mod~2$

Can someone please try and help me with that?

thanks in advance.

  • 3
    $\begingroup$ The message resides in $R_2$, not $R_q$. Does that resolve the question? $\endgroup$ – Chris Peikert Jun 19 '16 at 23:36
  • $\begingroup$ Thanks @ChrisPeikert , in fact he message resides in $R_2$ (it was a mistake) but I still can't still to come up with a proof. $\endgroup$ – HollowMan Jun 19 '16 at 23:46
  • 3
    $\begingroup$ Decryption should compute $c_1 - s c_0 \bmod q$, which yields $2e+m$, which we then reduce mod 2 to recover $m$. $\endgroup$ – Chris Peikert Jun 20 '16 at 0:26

I think your proof of correctness may be hampered by the fact that you are setting the ciphertext to $(c_0, c_1) = (a, as + 2e + m)$ when in fact the paper you cite sets the ciphertext to $(c_0, c_1) = (as + 2e + m, -a)$. You correctly state that decryption is then computed as $c_0 + c_1s \text{ (mod } 2)$. This reduces to $(as + 2e + m) + (-a)s \text{ (mod } 2)$, and you can then eliminate some terms ($as$ and $-as$) to get $2e + m \text{ (mod } 2)$. We note that $2e \equiv 0 \text{ (mod } 2)$ hence we are left with $m \text{ (mod } 2)$ and since $m \in R_2$ we have $m \text{ (mod } 2) = m$.

| improve this answer | |
  • 1
    $\begingroup$ It's important to note that 2e+m < q, otherwise you couldn't reduce mod 2 $\endgroup$ – Florian Bourse Jun 21 '16 at 8:48

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.