# Ring-LWE instance with errors also in the public polynomial

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?

• 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 5 '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 6 '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 8 '20 at 8:28