# How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>

In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the meaning value and \sigam is the standard deviation, and we sample e \gets D_{u,\sigma}, then how to get the bound of e, i.e., |e|? Similarly, if \sf{e} is an n-dimension vector, what it the bound of \sf{e}, i.e., |\sf{e}|? I am confusing how to use the meaning value u here?

• Do you mean a continuous or a discrete Gaussian? Apr 1, 2020 at 13:55
• discrete Gaussian, I want to know how to measure the bound of the element sampled from Gaussian distribution
– Z.P.
Apr 3, 2020 at 3:36

The point $$u$$ here means that instead of sampling a point from the lattice $$\Lambda$$, you're sampling a point from the coset of the lattice $$u + \Lambda$$. This is a "shifted copy" of the lattice (shifted by precisely $$u$$).
For any $$n$$-dimensional lattice $$\Lambda$$ and $$s > 0$$, a point sampled from $$D_{\Lambda, s}$$ has Euclidean norm at most $$s\sqrt{n}$$ except with probability at most $$2^{-2n}$$.
This citation/statement of the lemma come from another paper (so may not be exact), as I don't have institutional access to download Banaszczyk's work. If you want to see a derivation, you could look at a generalization of this bound, for example this one, which is on eprint. This includes the coset bound you want, which is stated as: $$\sum_{\substack{\lambda\in\Lambda\\\|\lambda + u\|_2\geq r}}\exp(-\pi \|\lambda + u\|_2^2) \leq (2\pi en^{-1}r^2)^{n/2}\sum_{\lambda\in\Lambda}\exp(-\pi\|\lambda\|_2^2)$$ The left-hand side is the gaussian mass in the tail of the coset, which is upper bounded by the gaussian mass on the lattice. This doesn't directly turn into the tail bound yet (for example, it doesn't include the standard deviation at all), but I imagine transforming the above inequality into a tail bound would be a quite reasonable exercise to do.