# proof of correctness Ring-LWE cryptosystem

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?

• The message resides in $R_2$, not $R_q$. Does that resolve the question? – Chris Peikert Jun 19 '16 at 23:36
• 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. – HollowMan Jun 19 '16 at 23:46
• Decryption should compute $c_1 - s c_0 \bmod q$, which yields $2e+m$, which we then reduce mod 2 to recover $m$. – 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$.