# Pseudorandomness of ring learning with errors

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$

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.
• Thank you for your answer. I understand that, but what I don't understand that according to the above logic the LWR samples look uniform too, if $p|q$, then why can't we claim that the LWR samples also look uniform? As I mentioned in the question the indistinuishibility of RLWR is an unsolved problem for a polynomial modulus. For superpolynomial modulus it is fine. – Rick Jun 16 '17 at 14:49
• To summarize, In the papers they try to make the RWLR samples look like LWE samples by reducing LWE to RLWE to RLWR. Because of the rounding we can divide $\mathbb{Z}_q$ in $p$ segments of length $q/p$ $round(as+e)$ becomes equal to $round(as)$ for all the values instead of for a small bound of values $-B,B$ for Gaussian we can take $B=12\cdot \sigma$. Now of $q$ is super polynomially large than $p$ this happens with nominal probability. Subsequent works removed super-polynomial condition. – Rick Jun 16 '17 at 14:56
• But, if $p|q$ can we say that RLWR samples are always uniform from the assumption on RLWE? – Rick Jun 16 '17 at 14:57
• Are you saying that even without $e(x)$ the samples will look random? – Rick Jun 16 '17 at 15:25
• Yes, just by itself $a_i s$ will actually be random (not just look random) because $a_i$ are random. But as I said, this is not actually interesting or useful for any cryptographic application. What you want is for the tuple $(a_i,a_is+e_i)$ to look random. Or in case of LWR, for $(a_i,round(a_is))$ to look random. – Vadim L. Jun 16 '17 at 21:49