proof of correctness Ring-LWE cryptosystem

Question

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.

Answer 1

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