Clarification of Decoding in Ring-LWE

Question

In the paper "A Toolkit for Ring-LWE Cryptography", the proposed public key system has (ignoring subtleties of the dual) Alice generate $a$ uniformly and $s,e$ from a discrete Gaussian, then output $(a,as+e)\in R_q\times R_q$. Bob generates $s_b,e_b$ from a discrete Gaussian, has $m\in\{0,1\}^n$, and outputs $(as_b+e_b,s_b(as+e)+m\lfloor q/2\rceil)$. Then Alice calculates: $$s_b(as+e)+m\lfloor q/2\rceil - s(as_b+e_b)=s_be-se_b+m\lfloor q/2\rceil$$ Then Alice can decode away the $s_be-se_b$, since they are small, and recover $m$.

Since Eve has just as much knowledge of the ring as Alice does, Eve ought to have just as much decoding capability (she could generate the decoding basis, for example). So as far as I can tell, the reason Alice can decode the final message but Eve cannot decode $as+e$ to $as$ is that in the latter case, Eve isn't really decoding over a lattice at all, since $as+e$ is still in the lattice given by the ring (or its dual). But for Alice, she's decoding a vector in $R$ to a point in the lattice given by $qR$. So the Gaussian error is small enough that Alice can decode the final message, but large enough that Eve cannot "decode" $as+e$.

Is this a correct description of what's going on?

Answer 1

Just so we are on the same page, I recall that the LWE problem assumes that for a secret (and usually small) vector s, it is hard to distinguish (A,b = As+e) from a random (A,b), where A is a random matrix of $\mathbb{Z}_q^{m\times n}$ and e is small. (Considerations about the required parameters and the error distribution are irrelevant for our argument, so I skip them for simplicity.)

With hypotheses for the polynomials $s,a_i,e_i$ that are similar to the ones we had for s, A, e, Ring-LWE assumes that it is hard to distinguish $(a_i,b_i = a_i\cdot s+e_i)$, which we call R-LWE samples, from random $(a_i,b_i)$.

Now, there are at least two (closely related) ways to answer your question :

• The public key of Alice is $(a, b = a\cdot s+e)$, and Bob sends her an encrypted message $$(u,v) = (a\cdot s_b + e_b, b \cdot s_b + e_b' + m \lfloor q/2 \rceil).$$ $(a,b)$ is a R-LWE sample for the secret $s$ so it is indistinguishable from random for Eve. Similarly, if Bob sent $m=0$ to Alice, then $(a,u) = (a, a\cdot s_b + e_b)$ and $(b,v) = (b, b \cdot s_b + e_b')$ are R-LWE samples for the secret $s_b$ so everything looks completely random to Eve and she wouldn't be able to distinguish whether Bob sent $m=0$ or random stuff to Alice. To send $m\neq 0$, Bob adds $m \lfloor q/2 \rceil$ to $v$ and it will still look random to Eve.
• I also like this more "lattice" approach. This is my interpretation and abusive notations ensue, so feel free to disagree: $$\binom{u}{v} = \binom{a}{b}s_b + \binom{e_b}{e_b'} + \binom{0}{m \lfloor q/2 \rceil}$$ So $(u,v)$ = [point of the lattice generated by $(a,b)$] + [a small error] + [the message]. The error is chosen big enough so that Eve is unable to decode [lattice point] + [error], let alone [lattice point] + [error] + [message]. However, Alice can perform a "dot product" of $(u,v)$ with the secret vector $(-s,1)$, which is small and almost orthogonal to $(a,b)$: $$\binom{u}{v} \cdot \binom{-s}{1} = e\cdot s_b + (e_b'-s\cdot e_b) + m \lfloor q/2 \rceil$$ At which point Alice can easily remove the remaining errors and recover m.