sampling ring polynomials in ring learning with errors - what's the trick?

Question

I'm trying to digest the "new hope" paper on post-quanum key exchange and understanding parts of Ring Learning with Errors, despite using every online resource I can find (including the references of 1). I'm sure regular Learning with Errors made some sense to me.

So let's start by with sampling. If you define a polynomial ring: $\mathcal{R}_q = \frac{\mathbb{Z}_q [x]}{x^n -1}$, and "sample from it", either uniformly or from a distribution, what do you actually get?

It seems to me you get a vector of coefficients $\mathbf{p}$ in the range [0, q]? The "polynomial" is then:

$p(x) = \frac{\displaystyle\sum_i \mathbf{p}_ix^i}{x^n - 1}$

Where $x$ has.. any domain for which the above operations make sense? So all you actually know after sampling are the coefficients of $\mathbf{p}$, $x$ is a free parameter, that doesn't even strictly seem to have a domain. It certainly doesn't seem to obtain a concrete value during key exchange, nowhere I can see does the paper sample $x$ from $X$.

And if you sample $\mathbf{p}, \mathbf{q}$, then similarly what you actually have is two vectors of coefficients? Which you can test for equality, add, and... multiply? But if I did that with two normal vectors, I would sense a great disturbance, as if a dozen former math and physics teachers and supervisors cried in out anquish, and were suddenly silenced.

So.. what gives? If we're never evaluating our "polynomials", which we don't seem to be, we're just messing around with vectors and a form of multiplication for which normal rules don't apply? Either that or I've misunderstood what sampling means.

Answer 1

If you sample from $\mathcal{R}_q$, you get a polynomial. Sure, you can represent it as a coefficient vector. But it is still a polynomial.

$p(x) = \frac{\displaystyle\sum_i \mathbf{p}_ix^i}{x^n - 1}$

Note that we are working modulo $x^n - 1$, not dividing by it. In some intuitive sense, you can imagine this as replacing all occurrences of $x^n$ simply with $1$.

It certainly doesn't seem to obtain a concrete value during key exchange

That's right, the objects of interest are the polynomials themselves.

Which you can test for equality, add, and... multiply?

As mentioned in a comment, multiplying polynomials is perfectly fine. For example, you have no objections to the classic $(x-1)(x+1)=x^2-1$. The same thing happens here (although still working modulo $x^n-1$. These aren't just "normal vectors".