Cryptology ePrint Archive: Report 2019/1411

Isochronous Gaussian Sampling: From Inception to Implementation

James Howe and Thomas Prest and 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.

Category / Keywords: public-key cryptography / Lattice based cryptography, Gaussian Sampling, Isochrony, Statistical verification tools

Original Publication (with minor differences): PQCrypto 2020

Date: received 5 Dec 2019, last revised 3 Feb 2020

Contact author: james howe at pqshield com,thomas prest@pqshield com,thomas ricosset@thalesgroup com,melissa rossi@ens fr

Available format(s): PDF | BibTeX Citation

Version: 20200203:180947 (All versions of this report)

Short URL: ia.cr/2019/1411


[ Cryptology ePrint archive ]