Sampling from a lattice Gaussian distribution has emerged as a common theme in various areas such as coding and cryptography. The de facto sampling algorithm—Klein’s algorithm yields a distribution close to the lattice Gaussian only if the standard deviation is sufficiently large. This talk is concerned with a new method based on Markov chain Monte Carlo (MCMC) for lattice Gaussian sampling, which converges to the target lattice Gaussian distribution for any value of the standard deviation. A number of algorithms will be presented, such as Gibbs and Metropolis-Hastings. A problem of central importance is to determine the mixing time. It is proven that some of these Markov chains are geometrically ergodic, namely, the sampling algorithms converge to the stationary distribution exponentially fast. Finally, an application to trapdoor sampling based on NTRU is demonstrated, potentially outperforming the FALCON signature scheme.
Cong Ling is currently a Reader (equivalent to Professor/Associate Professor) in the Electrical and Electronic Engineering Department at Imperial College London. His research interest is focused on lattices and their applications to coding and cryptography.