Discrete Gaussians and the smoothing parameter

The discrete Gaussian is the distribution on a lattice that gives each point mass proportional to the Gaussian function ; above the smoothing parameter the lattice’s discrete structure is invisible to a Gaussian of width — MR07.

Definitions

For and , let , with , and for a countable set . For a full-rank lattice , the discrete Gaussian is

and on a coset is defined in the same way. The dual lattice is , and is the smallest such that contains linearly independent vectors of length at most .

For , the smoothing parameter is

— MR07.

Properties

  • Bound by . For every , ; in particular , so for every there is a negligible with — MR07.
  • Smoothing. For and every , a continuous Gaussian of width centered at , reduced modulo , is within statistical distance of the uniform distribution on — MR07.
  • Tail bound. For , and every , , a consequence of Banaszczyk’s transference lemma — MR07.
  • Sampling. Given any basis of , a randomized variant of Babai’s nearest-plane algorithm, due to Kle00, samples a distribution statistically close to for every , where is the length of the longest Gram–Schmidt vector of — GPV08. Its output distribution is statistically close to one that depends only on , and , so samples leak only negligible information about , which is what makes a short basis usable as a lattice trapdoor.
  • Uniform syndromes. Let be prime, and . Except for an exponentially small fraction of , the lattice satisfies, for every , for some negligible , and for the syndrome of is within statistical distance of uniform on — GPV08.