# Why round off vector sampling from continuous Gaussian distribution not directly sample from discrete Gaussian distribution

For any vector $$\mathbf{c}$$, real $$s > 0$$, and lattice $$\Lambda$$, define the probability distribution $$D_{\Lambda, s,\mathbf{c}}$$ over $$\Lambda$$ by $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})=\frac{D_{s,\mathbf{c}}(\mathbf{x})}{D_{s,\mathbf{c}}(\Lambda)}=\frac{\rho_{s, \mathbf{c}}(\mathbf{x})}{\rho_{s, \mathbf{c}}(\Lambda)}, \forall \mathbf{x} \in \Lambda$$ where $$\rho_{s, \mathbf{c}}(\Lambda)=\sum_{\mathbf{x} \in \Lambda}\rho_{s, \mathbf{c}}(\mathbf{x})$$.

We refer to $$D_{\Lambda, s,\mathbf{c}}$$ as a discrete Gaussian distribution.

Many algorithms sample a vector from continuous Gaussian distribution $$D_{s,\mathbf{c}}$$ and round off(then the sampling vector is distributed by discrete Gaussian distribution), instead of sampling vector directly from $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})$$ by computing $$\frac{\rho_{s, \mathbf{c}}(\mathbf{x})}{\rho_{s, \mathbf{c}}(\Lambda)}$$.

I think that the reason why a vector is not sampled directly computing $$\frac{\rho_{s, \mathbf{c}}(\mathbf{x})}{\rho_{s, \mathbf{c}}(\Lambda)}$$ is that computing $$\rho_{s, \mathbf{c}}(\Lambda)=\sum_{\mathbf{x} \in \Lambda}\rho_{s, \mathbf{c}}(\mathbf{x})$$ costs expensive. Because a lattice $$\Lambda$$ has many vector.(for example, the lattice $$\mathbb{Z}^n$$ where error is sampled in LWE). Whereas $$D_{s,\mathbf{c}}$$ costs not expensive.(because $$\rho_{s,\mathbf{c}}(\mathbb{R}^n)=s^n$$, so $$D_{s,\mathbf{c}}=\frac{\rho_{s,\mathbf{c}}(\mathbf{x})}{\rho_{s,\mathbf{c}}(\mathbb{R}^n)}=\frac{\rho_{s,\mathbf{c}}(\mathbf{x})}{s^n}$$)

If it isn't, in order to get samples from discrete Gaussian distribution, why many algorithm sample from continuous Gaussian distribution then round off?

• For anybody who wonder same thing, I write what I studied after. Sampling directly from $D_{\Lambda,s,\mathbf{c}}$ is not difficult. Distribution just should have probability that is proportional to $\rho_{s,\mathbf{c}}$. GPV's sampling algorithm did this. Now, I'm wondering that why round off vector even though sampling directly is possible. I guess because rounding just samples nearby vectors from center and we just need small vector. – 전소현 Sep 25 '19 at 12:13