Isochronous Gaussian Sampling: From Inception to Implementation

James Howe, Thomas Prest, Thomas Ricosset, and Mélissa Rossi

Abstract

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)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.PQCrypto 2020
Keywords
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
History
2020-08-25: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/1411

CC BY

BibTeX

@misc{cryptoeprint:2019/1411,
author = {James Howe and Thomas Prest and Thomas Ricosset and Mélissa Rossi},
title = {Isochronous Gaussian Sampling: From Inception to Implementation},
howpublished = {Cryptology ePrint Archive, Paper 2019/1411},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1411}},
url = {https://eprint.iacr.org/2019/1411}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.