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 (13), 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 (8). The survey (20) covers most of these methods, with the exception of the most recent (8).

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

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. Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography
   (Aguilar-Melchor, Albrecht, Ricosset - ACNS 2017)

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

On Practical Discrete Gaussian Samplers for Lattice-Based Cryptography
(Howe, Khalid, Rafferty, Regazonni & O’Neill - IEEE Trans. Computers 2018)

Constant-Time Discrete Gaussian Sampling
(Karmakar, Roy, Reparaz, Vercauteren & Verbauwhede - IEEE Trans. Computers 2018)

CDT-Based Gaussian Sampling: From Multi to Double Precision
(Melchor & Ricosset - IEEE Trans. Computers 2018)

Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on Falcon
(Karmakar, Roy, Vercauteren & Verbauwhede - DAC 2019)

Additional references on 1-dimensional Gaussian Sampling include

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

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

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

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

Sampling n-dimensional Lattices

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

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

MCMC techniques have also been considered to sample discrete gaussians on lattices:

15. On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian Sampling
    (Wang & Ling - ISIT 2015, ISIT 2016)

16. Markov Chain Monte Carlo Algorithms for Lattice Gaussian Sampling
    (Wang, Ling & Hanrot - ISIT 2014)