Pseudorandomness of ring learning with errors

Question

My question is in Ring Learning with Errors, let $a(x)\in \mathbb{Z}_q(x)/(X^n+1)$ where $n$ is a power of $2$, be a random polynomial, $s(x),e(x)\in \mathbb{Z}_q(x)/(X^n+1)$ are the secret and error polynomial respectively with co-efficients sampled from a discrete Gaussian distribution $D_\sigma$. Now, the decisional hardness of RLWE says that the samples $a(x)\cdot s(x) + e(x)$ are indistinguishable from a random polynomial $u(x)\in \mathbb{Z}_q(x)/(X^n+1)$.

• Now, my question is whether the polynomial $a(x)\cdot s(x)$ $i.e$ the RLWE sample without error will be polynomially indistinguishable from a random string? As far as I can think, the error polynomial $e(x)$ is only used for the hardness of the problem. Does it also contribute to the polynomial indistinguishability of the samples?

The reason I am asking this question is that, recently I found a new problem LWR in these papers Banerjee et al., Alwen et al Bogdanov et al. which removes the error but introduces an error with rounding each co-efficient of $a(x)\cdot s(x)$, $\lfloor p/q(.)\rceil : \mathbb{Z}_q\rightarrow \mathbb{Z}_p$. They have gone great length to prove the computational indistinguishability of the LWR samples. The computational indistinguishability of RLWR is not proven yet. if $a(x)\cdot s(x)$ is computationally indistinguishable from a random polynomial in $\mathbb{Z}_q$ then can't we say $\lfloor p/q(a(x)\cdot s(x))\rceil$ is also computationally indistinguishable from a random polynomial in $\mathbb{Z}_p/(X^n+1)$ if $p|q$

Answer 1

Let $R$ be the ring $\mathbb{Z}_p[X]/(X^n+1)$, where $n$ is a power of 2. The Ring-LWE assumption says that for any randomly chosen, fixed $s\in R$, the distribution of $$((a_1,a_1s+e_1),\ldots,(a_k,a_ks+e_k))$$ is indistinguishable from the distribution $$((a_1,u_1),\ldots,(a_k,u_k)),$$ where $a_i,u_i$ are uniformly random in $R$ and $e_i$ are chosen from some distribution with small coefficients.

Of course, if one $only$ outputs $((a_1s+e_1),\ldots,(a_ks+e_k))$ without also revealing the $a_i$, then this distribution is trivially uniformly random (assuming that $s$ is invertible in $R$, but this is a minor issue) because the $a_i$ are uniformly random. This would be a pretty useless property.

The interesting part in Ring-LWE is that even when the $a_i$ are revealed, the distribution still looks uniform. Basically, the small additional entropy of the $e_i$ allows one to create a new uniform-looking element with larger entropy.