Paper 2019/1411

Isochronous Gaussian Sampling: From Inception to Implementation

James Howe, Thomas Prest, Thomas Ricosset, and Mélissa Rossi


Gaussian sampling over the integers is a crucial tool in lattice-based cryptography, but has proven over the recent years to be surprisingly challenging to perform in a generic, efficient and provable secure manner. In this work, we present a modular framework for generating discrete Gaussians with arbitrary center and standard deviation. Our framework is extremely simple, and it is precisely this simplicity that allowed us to make it easy to implement, provably secure, portable, efficient, and provably resistant against timing attacks. Our sampler is a good candidate for any trapdoor sampling and it is actually the one that has been recently implemented in the Falcon signature scheme. Our second contribution aims at systematizing the detection of implementation errors in Gaussian samplers. We provide a statistical testing suite for discrete Gaussians called SAGA (Statistically Acceptable GAussian). In a nutshell, our two contributions take a step towards trustable and robust Gaussian sampling real-world implementations.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2020
Lattice based cryptographyGaussian SamplingIsochronyStatistical verification tools
Contact author(s)
james howe @ pqshield com
thomas prest @ pqshield com
thomas ricosset @ thalesgroup com
melissa rossi @ ens fr
2020-08-25: last of 2 revisions
2019-12-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {James Howe and Thomas Prest and Thomas Ricosset and Mélissa Rossi},
      title = {Isochronous Gaussian Sampling: From Inception to Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1411},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.