A Secure Algorithm for Rounded Gaussian Sampling

Séamus Brannigan*, Maire O’Neill, Ayesha Khalid, Ciara Rafferty

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Presented in this paper is a new Gaussian sampler targeted at lattice-based signatures. It is the first secure algorithm for implementing the Box-Muller Gaussian sampling algorithm, which produces continuous Gaussian samples. The samples can be made discrete by rounding and this method has recently been shown to suffice for the purpose of discrete Gaussian sampling for lattice-based signatures. Rounded Gaussians allow quick transformations from samples of low standard deviation to samples with a high standard deviation. This makes them well-suited to producing the wide distributions needed for the target primitives. Current state-of-the-art methods sample wide distributions with multiple samples from a narrow distribution, joined by a convolution algorithm, for each single sample. The number of required samples per output sample grows with the width of the distribution. The rounded Gaussian method allows sampling wide distributions with complexity which is constant with increasing standard deviation. The main contribution of the work is a novel, low-memory algorithm, based on the CORDIC family of algorithms, for the fixed-point and secure evaluation of the elementary functions necessary for the Box-Muller continuous sampling method. It is the first secure, continuous sampler for the production of rounded Gaussian distributions. A proof-of-concept implementation of the algorithm is used to demonstrate that Box-Muller sampling is a competitive alternative to sampling the discrete Gaussian distribution, for lattice-based signatures.

Original languageEnglish
Title of host publicationCryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14–16, 2020: Proceedings
EditorsStephan Krenn, Haya Shulman, Serge Vaudenay
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages20
ISBN (Print)9783030654108
Publication statusPublished - 09 Dec 2020
Event19th International Conference on Cryptology and Network Security, CANS 2020 - Vienna, Austria
Duration: 14 Dec 202016 Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12579 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Conference on Cryptology and Network Security, CANS 2020

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2020.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A Secure Algorithm for Rounded Gaussian Sampling'. Together they form a unique fingerprint.

Cite this