In Regev - On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, chapter 5, Public Key Crypto System, it is stated that

The probability distribution function $\chi$ is taken to be $\Psi_{\alpha(n)}$ ... we can choose $\alpha(n)=1/(\sqrt n\ log^2n)$

The document states in §1 that the standard deviation is $p\alpha$

How does $\Psi_{\alpha(n)}$ look like ?

Should I take $\Psi_{\alpha(n)}(x)=\frac{1}{p\alpha(n)\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x}{p\alpha(n)})^2}$ or $e^{-\pi(\frac{x}{p\alpha(n)})^2}$?


The document also states that the curve is centered around 0 and that the probability of zero is roughly $\frac{1}{p\alpha(n)}$.

So starting from the generic probability density function $$ f(x|\mu,\sigma2)=\frac{1}{\sqrt{2\pi\sigma^2}}e^{\frac{-1}{2}(\frac{x-\mu}{\sigma})^2} $$ My best guess is that

$$ \Psi_{\alpha(n)}(x)=\frac{1}{p\alpha(n)}e^{-\frac{\pi x^2}{(p\alpha(n))^2}} $$

A confirmation would be much appreciated.

  • $\begingroup$ What is the exact context? Title of paper, book? If the chapter is just on generic public key cryptography, Gaussian distributions are not a natural choice. $\endgroup$
    – kodlu
    Oct 5 '18 at 5:20
  • $\begingroup$ @kodlu The paper is "Regev - On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". Link: cims.nyu.edu/~regev/papers/qcrypto.pdf $\endgroup$
    – BGR
    Oct 5 '18 at 14:54

Neither of the alternatives in your question is completely correct. The distribution $\Psi_{\beta}$ is as defined by equation (7) in Section 2 of your reference: $$\Psi_{\beta}(r) = \sum_{k = -\infty}^{\infty} \frac{1}{\beta}\,\exp\left(-\pi \left(\frac{r - k}{\beta}\right)^2\right),$$

for $r \in [0, 1)$. So $\beta$ is not the standard deviation of a normal distribution (instead, the standard deviation is $\beta / \sqrt{2\pi})$. Note that $\Psi_{\beta}$ is not a normal distribution though, but a "periodization" of normal distribution.

Also keep in mind that $\bar \Psi_\beta$ is a discretized version of $\Psi_\beta$, i.e. the distribution that you get after multiplying by $p$ and rounding to the nearest integer mod $p$. This is why the introduction mentions that $\bar\Psi_{\alpha}$ has (roughly) the shape of a normal distribution with standard deviation $p \alpha$.

  • $\begingroup$ Ahhh. Thank you (I had lazily skipped that figure thinking it was part of the proof to 2.1). You are right, I should have mentioned the part about discretization, which I had figured out. $\endgroup$
    – BGR
    Oct 7 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.