Paper 2023/1288

An erf Analog for Discrete Gaussian Sampling

Nicolas Gama, SandboxAQ
Anand Kumar Narayanan, SandboxAQ
Ryder LiuLin, SandboxAQ
Dongze Yue, SandboxAQ

Most of the current lattice-based cryptosystems rely on finding Gaussian Samples from a lattice that are close to a given target. To that end, two popular distributions have been historically defined and studied: the Rounded Gaussian distribution and the Discrete Gaussian distribution. The first one is nearly trivial to sample: simply round the coordinates of continuous Gaussian samples to their nearest integer. Unfortunately, the security of resulting cryptosystems are not as well understood. In the opposite, the second distribution is only implicitly defined by a restriction of the support of the continuous Gaussian distribution to the discrete lattice points. Thus, algorithms to achieve such distribution are more involved, even in dimension one. The justification for exerting this computational effort is that the resulting lattice-based cryptographic schemes are validated by rigorous security proofs, often by leveraging the fact that the distribution is radial and discrete Gaussians behave well under convolutions, enabling arithmetic between samples, as well as decomposition across dimensions. In this work, we unify both worlds. We construct out of infinite series, the cumulative density function of a new continuous distribution that acts as surrogate for the cumulative distribution of the discrete Gaussian. If $\mu$ is a center and $x$ a sample of this distribution, then rounding $\mu+x$ yields a faithful Discrete Gaussian sample. This new sampling algorithm naturally splits into a pre-processing/offline phase and a very efficient online phase. The online phase is simple and has a trivial constant time implementation. Modulo the offline phase, our algorithm offers both the efficiency of rounding and the security guarantees associated with discrete Gaussian sampling.

Available format(s)
Publication info
Published elsewhere. Mathcrypt 2023
Discrete Gaussian SamplingRounded Gaussianerf
Contact author(s)
nicolas gama @ sandboxaq com
anand kumar @ sandboxaq com
ryder liulin @ sandboxaq com
steven yue @ sandboxaq com
2023-08-29: approved
2023-08-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Gama and Anand Kumar Narayanan and Ryder LiuLin and Dongze Yue},
      title = {An erf Analog for Discrete Gaussian Sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1288},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.