Consider the ring $R_q = \mathbb{Z}_q[X]/(X^d+1)$, the Ring-Learning-With-Error assumption states that the distribution of $(a, as + e)$ is close to uniformly random, where $s \in R_q$, $a$ is uniform in $R_q$ and $e$ has small norm (say $\|e\|_\infty \leq \beta$).

How pseudorandom is $(a+e', as+e'')$, where $e', e''$ have bounded norm say strictly less than $\beta$?

How about the general case where there are multiple instances?

  • $\begingroup$ If $e''$ is chosen in the same way as $e$, then your new distribution should be more random than the original R-LWE distribution, since it's the same as an R-LWE distribution but with extra noise added. Did you have a precise measure in mind for how pseudorandom something is? $\endgroup$ – Sam Jaques Jun 5 '20 at 10:24
  • $\begingroup$ If the bound on $e''$ is greater than or equal to $\beta$, apparently the distribution will be more pseudorandom. So the point here is that both $e'$ and $e''$ have bounds strictly less than $\beta$ (say $\|e''\|_\infty \leq \beta/2$), as stated in my original question. $\endgroup$ – Eri Jun 6 '20 at 13:30
  • $\begingroup$ Oh sorry, I should have read more carefully. If you define $a'=a+e'$ then $a'$ should be uniform in $R_q$ as well, and then $(a+e',as+e'')=(a',a's-e's+e'')$, which is an LWE instance with a new error of $-e's+e''$. I don't know how to quantify the randomness/norm of $-e's+e''$, though. $\endgroup$ – Sam Jaques Jun 8 '20 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.