0
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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

Generically though, you're looking for tail bounds of gaussian mass on lattices. You can find these a variety of places in the literature. They originate with Banaszczyk's New bounds in some transference theorems in the geometry of numbers, where Lemma 1.5(i) states:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.