Paper 2019/1011

COSAC: COmpact and Scalable Arbitrary-Centered Discrete Gaussian Sampling over Integers

Raymond K. Zhao, Ron Steinfeld, and Amin Sakzad

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 Renyi 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.

Note: 1. We add the missing factor \sqrt(2 \pi) when comparing \sigma with the smoothing parameter. 2. We update the link to the source code.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision.PQCrypto 2020
DOI
10.1007/978-3-030-44223-1_16
Keywords
Lattice-based cryptodiscrete Gaussian samplingimplementationefficiency
Contact author(s)
raymond zhao @ monash edu
History
2020-09-25: last of 4 revisions
2019-09-09: received
See all versions
Short URL
https://ia.cr/2019/1011
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1011,
      author = {Raymond K.  Zhao and Ron Steinfeld and Amin Sakzad},
      title = {COSAC: COmpact and Scalable Arbitrary-Centered Discrete Gaussian Sampling over Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1011},
      year = {2019},
      doi = {10.1007/978-3-030-44223-1_16},
      note = {\url{https://eprint.iacr.org/2019/1011}},
      url = {https://eprint.iacr.org/2019/1011}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.