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.
|Title of host publication||Cryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14–16, 2020: Proceedings|
|Editors||Stephan Krenn, Haya Shulman, Serge Vaudenay|
|Publisher||Springer Science and Business Media Deutschland GmbH|
|Number of pages||20|
|Publication status||Published - 09 Dec 2020|
|Event||19th International Conference on Cryptology and Network Security, CANS 2020 - Vienna, Austria|
Duration: 14 Dec 2020 → 16 Dec 2020
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||19th International Conference on Cryptology and Network Security, CANS 2020|
|Period||14/12/2020 → 16/12/2020|
Bibliographical notePublisher Copyright:
© Springer Nature Switzerland AG 2020.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
FingerprintDive into the research topics of 'A Secure Algorithm for Rounded Gaussian Sampling'. Together they form a unique fingerprint.
Secure Gaussian sampling for lattice-based signatures: New directions for reaching high standard deviationAuthor: Brannigan, S., Dec 2021
Supervisor: Khalid, A. (Supervisor) & O'Neill, M. (Supervisor)
Student thesis: Doctoral Thesis › Doctor of PhilosophyFile