Discrete Gaussian Samping

Sampling the integers

All methods to sample the Gaussian distribution on an n-dimensional lattice use as a building block a procedure to sample the 1-dimensional Gaussian distribution on the integers. Algorithms for 1-dimensional discrete gaussian sampling include the inverse method (12), the discrete ziggurat (3), lazy rejection sampling (2), the exact method (4), the binary method (1), the Knuth-Yao algorithm used in (5,6), and the convolution method (7). The survey (18) covers most of these methods, with the exception of the most recent (7).

  1. Lattice Signatures and Bimodal Gaussians
    (Ducas, Durmus, Lepoint & Lyubashevsky - Crypto 2013)
    Binary gaussian sampler with probabilities proportional to exp(-ln(2) x2)

  2. Faster Gaussian Lattice Sampling Using Lazy Floating-Point Arithmetic
    (Ducas & Nguyen Asiacrypt 2012
    Lazy Rejection Sampling

  3. Discrete Ziggurat: A Time-Memory Trade-Off for Sampling from a Gaussian Distribution over the Integers
    (Buchmann, Cabarcas, Gopfert, Hulsing & Weiden - SAC 2013)
    “For large standard deviations, the Ziggurat algorithm outperforms all existing methods”

  4. Sampling Exactly from the Normal Distribution
    (Karney - ToMS 2016)
    “It can easily be adapted to sample exactly from the discrete normal distribution”

  5. High Precision Discrete Gaussian Sampling on FPGAs
    (Roy, Vercauteren & Verbauwhede - SAC 2013) Employs the Knuth-Yao algorithm.

  6. Sampling from discrete Gaussians for lattice-based cryptography on a constrained device
    (Dwarakanath & Galbraith - AAECC 2014)

  7. Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time
    (Micciancio & Walter - CRYPTO 2017)

Additional references on 1-dimensional Gaussian Sampling include

  1. Gaussian Sampling Precision in Lattice Cryptography
    Saarinen - ePrint 2015/953

  2. Towards efficient discrete Gaussian sampling for lattice-based cryptography (Du & Bai - FLP 2015)

  3. Discrete Gaussian sampling for low-power devices
    (More & Katti - PACRIM 2015)

  4. Compact and Side Channel Secure Discrete Gaussian Sampling
    (Roy, Reparaz, Vercauteren & Verbauwhede - ePrint 2014/591)

Sampling n-dimensional Lattices

  1. An Efficient and Parallel Gaussian Sampler for Lattices
    (Peikert - Crypto 2010)
    Uses inverse method to sample the discrete gaussian

  2. Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus
    (Genise & Micciancio - )

Speeding up Gaussiann sampling on ideal lattices

  1. Fast Fourier Orthogonalization
    (Ducas & Prest - ePrint 2015/1014)

  2. Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices
    (Lyubashevsky & Prest - Eurocrypt 2015)

  3. A Hybrid Gaussian Sampler for Lattices over Rings
    (Ducas & Prest - ePrint 2015/660) Superseded by FFO

Other distributions

  1. Simple Lattice Trapdoor Sampling from a Broad Class of Distributions
    (Lyubashevsky & Wichs - PKC)

Surveys, Implementations and Testing

  1. Gaussian Sampling in Lattice Based Cryptography
    (Follath - TMMP 2014)

  2. GLITCH: A Discrete Gaussian Testing Suite For Lattice-Based Cryptography
    (Howe & O’Neill - SECRYPT 2017)

  3. An Investigation of Sources of Randomness Within Discrete Gaussian Sampling
    (Brannigan, Smyth, Oder, Valencia, O’Sullivan, Güneysu & Regazzoni - )

  4. Implementation and Evaluation of Improved Gaussian Sampling for Lattice Trapdoors
    (Gür, Polyakov, Rohloff, Ryan & Savaş - )