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.


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.