0

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?

Eri
  • 31
  • 3
  • 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? – Sam Jaques Jun 05 '20 at 10:24
  • 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. – Eri Jun 06 '20 at 13:30
  • 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. – Sam Jaques Jun 08 '20 at 08:28

0 Answers0