Cryptology ePrint Archive: Report 2019/1011

Compact and Scalable Arbitrary-centered Discrete Gaussian Sampling over Integers

Raymond K. Zhao and 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.

Category / Keywords: implementation / Lattice-based crypto, discrete Gaussian sampling, implementation, efficiency

Date: received 7 Sep 2019, last revised 14 Oct 2019

Contact author: raymond zhao at monash edu

Available format(s): PDF | BibTeX Citation

Note: Fix typos.

Version: 20191015:050856 (All versions of this report)

Short URL: ia.cr/2019/1011


[ Cryptology ePrint archive ]