Paper 2019/1411
Isochronous Gaussian Sampling: From Inception to Implementation
James Howe, Thomas Prest, Thomas Ricosset, and Mé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.
Metadata
- Available format(s)
-
PDF
- 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
- 2019-12-06: received
- See all versions
- Short URL
- https://ia.cr/2019/1411
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1411,
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},
url = {https://eprint.iacr.org/2019/1411}
}
