# Trying to Understand Ring Learning With Error Encryption

I'm trying to understand the following RLWE encryption scheme from this Chris Peikert's paper

Say i choose $$q = 97$$, $$n=8$$ and the polynomial $$a = 96 x^8+30 x^7+76 x^6+12 x^5+57 x^4+77 x^3+70 x^2+49 x+83$$

secret key $$s = 8 x^8+7 x^7+6 x^6+5 x^5+4 x^4+3 x^3+2 x^2+x$$

and error $$e = x^6+x^4+x^2+1$$

then $$b = a \cdot s +e \mod 97 = 19 x^7+84 x^6+35 x^5+40 x^4+94 x^3+69 x^2+59 x+63$$

Suppose i want to encrypt the message $$z =1010101 = x^6+x^4+x^2+1$$

I choose $$r = x^6+x^4+x^2+1$$

$$e1 = x^6+x^4+x^2+1$$

$$e2 = x^6+x^4+x^2+1$$

then we have $$u = a \cdot r + e1 = 71 x^7+94 x^6+11 x^5+39 x^4+84 x^3+22 x^2+27 x+76$$

and $$v = b \cdot r + e2 + q/2 \cdot z = (13 x^7+63 x^6+72 x^5+89 x^4+2 x^3+9 x^2+8 x+65) + (49 x^6+49 x^4+49 x^2+49) = 13 x^7+15 x^6+72 x^5+41 x^4+2 x^3+58 x^2+8 x+17$$

to decrypt i compute $$v-u \cdot s = (13 x^7+14 x^6+72 x^5+40 x^4+2 x^3+57 x^2+8 x+16) - (29 x^7+62 x^6+74 x^5+78 x^4+91 x^3+89 x^2+91 x+46) = -16 x^7-47 x^6-2 x^5-37 x^4-89 x^3-31 x^2-83 x-29$$

rounding each coefficient with respect to $$(-q/4, q/4)$$ gives 11111010

what am I doing wrong?

• do you know what is $\lfloor q/2 \rceil$ Feb 26 '20 at 9:09
• yes, rounding to nearest integer; however rounding to 49 instead of 48 does not change the result. Feb 27 '20 at 4:11
• Are you performing the reductions modulo $q$ using the centered representation, i.e., reducing everything into $-q/2, ..., q/2$? Moreover, are you really computing $u - s\cdot v$ instead of $v - s\cdot u$ in the decryption step or it is just a typo? Feb 27 '20 at 8:19
• yes, it's a typo. I just reduced every coefficient mod q. I only rounded to $(-q/2...q/2)$ in the last step. Do i need to mod $(-q/2...q/2)$ for every calculation? The paper only says $mod q$. Feb 28 '20 at 0:26

convert $$v-u \cdot s$$ to centered representation as described here seems to work