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$


1 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.

  • $\begingroup$ 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. $\endgroup$
    – Rick
    Commented Jun 16, 2017 at 14:49
  • $\begingroup$ 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. $\endgroup$
    – Rick
    Commented Jun 16, 2017 at 14:56
  • $\begingroup$ But, if $p|q$ can we say that RLWR samples are always uniform from the assumption on RLWE? $\endgroup$
    – Rick
    Commented Jun 16, 2017 at 14:57
  • $\begingroup$ Are you saying that even without $e(x)$ the samples will look random? $\endgroup$
    – Rick
    Commented Jun 16, 2017 at 15:25
  • $\begingroup$ 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. $\endgroup$
    – Vadim L.
    Commented Jun 16, 2017 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.