# Probability of an RLWE sample

Let $$R_q=\mathbb{Z}_q[x]/(x^n+1)$$ as usual in the RLWE assumption.

Suppoes that I choose a sample of the RLWE distribution, that is, I compute $$(a,y=as+e)$$ where $$a$$ is uniform in $$R_q$$ and $$s,e\leftarrow\chi_\alpha$$ are sampled from the error distribution (discrete Gaussian distribution with parameter $$\alpha$$).

Question: I want to know the probability $$Pr(y=r)$$ for some $$r\in R_q$$. Note that, in this case, I know the secret $$s$$ and error $$e$$. Hence, I believe I cannot use the indistinguishability of RLWE samples from uniform samples to conclude that $$Pr(y=r)$$ is close to uniform, say $$1/q^n+negl$$ (or can I?).

Thanks

• I think adding uniform distribution to discrete Gaussian distribution should result in discrete Gaussian distribution. – kelalaka Apr 8 '19 at 17:41
• Shouldn't it be uniform? Summing uniform and another thing should results in uniform, no? And if we consider q to be prime, then $as$ is uniform – P.B. Apr 8 '19 at 18:28
• Are you asking about $\Pr[y = r \mid a, s, e]$, or $\Pr[y = r \mid a, s]$, or $\Pr[y = r \mid s, e]$, etc.? The answer is different in every case. From your perspective, you know $a$, $s$, and $e$, so $\Pr[y = r \mid a, s, e] = \delta_{r = as + e}$; from the adversary's perspective, $s$ and $e$ are unknown, so presumably $\Pr[y = r \mid a]$ is of interest. – Squeamish Ossifrage Apr 8 '19 at 18:37
• What do you mean by $\delta_{r=as+e}$? – P.B. Apr 9 '19 at 8:21