1
$\begingroup$

Define $$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$ and $$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$

Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is the following distribution over lattice points: probability of $v \in L$ equals:

$$ \mathbb{P}[v] = \frac{\rho_{s,c}(v)}{\rho_{s,c}(L)}$$

Some questions about this distribution:

  1. What are the properties? For instance, is it true that the sum of two discrete gaussians is equal to (stat. close to) another discrete gaussian (as in usual multivariate gaussians)?

  2. Why discrete gaussians? It is known that this distribution is NOT statistically close to usual normal with rounding. But when somebody start giving a motivation behind discrete gaussians, they usually refer to the fact that USUAL multivariate gaussian is statistically close to uniform modulo small parallelopipeds. But what makes discrete gaussian so attractive? Are there any properties that it "inherits" from usual gaussian?

    1. Is it possible to replace discrete gaussian with another spherical-symmetric "factorable" distribution, maybe something like multivariate binomial over "big enough" support? What would be broken? Would it leak some information about basis?
$\endgroup$
  • $\begingroup$ If you look at the NIST post-quantum standardization competition you will see that several submissions in fact use a different distribution that is easier to work with (binomial/fixed-weight/sparse/...). So the answer to 3 is yes, although it may depend a bit on who you're asking whether this is "safe". $\endgroup$ – TMM Sep 17 '19 at 21:09