Probability distribution function in Regev Cryptosystem

Question

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.

Answer 1

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$.