# Probability distribution function in Regev Cryptosystem

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}$$?

EDIT

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.

• 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. – kodlu Oct 5 '18 at 5:20
• @kodlu The paper is "Regev - On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". Link: cims.nyu.edu/~regev/papers/qcrypto.pdf – 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$$.