COSAC: compact and scalable arbitrary-centered discrete Gaussian sampling over integers

Raymond K. Zhao, Ron Steinfeld, Amin Sakzad

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

The arbitrary-centered discrete Gaussian sampler is a fundamental subroutine in implementing lattice trapdoor sampling algorithms. However, existing approaches typically rely on either a fast implementation of another discrete Gaussian sampler or pre-computations with regards to some specific discrete Gaussian distributions with fixed centers and standard deviations. These approaches may only support sampling from standard deviations within a limited range, or cannot efficiently sample from arbitrary standard deviations determined on-the-fly at run-time. In this paper, we propose a compact and scalable rejection sampling algorithm by sampling from a continuous normal distribution and performing rejection sampling on rounded samples. Our scheme does not require pre-computations related to any specific discrete Gaussian distributions. Our scheme can sample from both arbitrary centers and arbitrary standard deviations determined on-the-fly at run-time. In addition, we show that our scheme only requires a low number of trials close to 2 per sample on average, and our scheme maintains good performance when scaling up the standard deviation. We also provide a concrete error analysis of our scheme based on the Rényi divergence. We implement our sampler and analyse its performance in terms of storage and speed compared to previous results. Our sampler’s running time is center-independent and is therefore applicable to implementation of convolution-style lattice trapdoor sampling and identity-based encryption resistant against timing side-channel attacks.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography
Subtitle of host publication11th International Conference, PQCrypto 2020 Paris, France, April 15–17, 2020 Proceedings
EditorsJintai Ding, Jean-Pierre Tillich
Place of PublicationCham Switzerland
PublisherSpringer
Pages284-303
Number of pages20
ISBN (Print)9783030442224, 9783030442231
DOIs
Publication statusPublished - 2020
Event11th International Conference on Post-Quantum Cryptography, PQCrypto 2020 - Paris, France
Duration: 15 Apr 202017 Apr 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12100
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Post-Quantum Cryptography, PQCrypto 2020
CountryFrance
CityParis
Period15/04/2017/04/20

Keywords

  • Discrete Gaussian sampling
  • Efficiency
  • Implementation
  • Lattice-based crypto

Cite this

Zhao, R. K., Steinfeld, R., & Sakzad, A. (2020). COSAC: compact and scalable arbitrary-centered discrete Gaussian sampling over integers. In J. Ding, & J-P. Tillich (Eds.), Post-Quantum Cryptography : 11th International Conference, PQCrypto 2020 Paris, France, April 15–17, 2020 Proceedings (pp. 284-303). (Lecture Notes in Computer Science ; Vol. 12100 ). Springer. https://doi.org/10.1007/978-3-030-44223-1_16