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?).


  • $\begingroup$ I think adding uniform distribution to discrete Gaussian distribution should result in discrete Gaussian distribution. $\endgroup$ – kelalaka Apr 8 '19 at 17:41
  • $\begingroup$ 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 $\endgroup$ – P.B. Apr 8 '19 at 18:28
  • 2
    $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Apr 8 '19 at 18:37
  • $\begingroup$ What do you mean by $\delta_{r=as+e}$? $\endgroup$ – P.B. Apr 9 '19 at 8:21

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.