2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 전소현 Sep 25 '19 at 12:13

Your Answer

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

Browse other questions tagged or ask your own question.