1
$\begingroup$

The security proof basically comes down to the following based on this paper.

We want to show that two distributions are statistically indistinguishable.

Say we have that $a,a′,x,x′$ are drawn from an ($n$-dimensional) discrete Gaussian distribution $D_{\mathbb{Z}^n,r}$ with standard deviation $r$ and that $b$ is drawn from a discrete Gaussian distribution $D_{\mathbb{Z}^n,r'}$ with standard deviation $r′≥2^{ω(\log n)}r$. I want to show that

$$b\approx b+ax+a′x′$$

Supposedly it is enough to know that the euclidean norm of a vector drawn from $D_{\mathbb{Z}^n,r}$ is less than $r\sqrt{n}$ with probability $1−2^{−n+1}$ and that the statistical difference between two Gaussian distributions with same standard deviation $r$ is proportional to $Δ/r$, where $Δ$ is the distance between their means.

What makes this difficult to me is that $ax$ and $a′x′$ are products of discrete Gaussians, and therefore the distribution is not Gaussian. The difficulty here is maybe proving that they are sub-Gaussian in some way, but I do not know how, or if that is even true.

$\endgroup$

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.