1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ I think adding uniform distribution to discrete Gaussian distribution should result in discrete Gaussian distribution. $\endgroup$
    – kelalaka
    Commented Apr 8, 2019 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.
    Commented Apr 8, 2019 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
    Commented Apr 8, 2019 at 18:37
  • $\begingroup$ What do you mean by $\delta_{r=as+e}$? $\endgroup$
    – P.B.
    Commented Apr 9, 2019 at 8:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.