Cryptology ePrint Archive: Report 2019/666

On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian Sampling

Zheng Wang and Cong Ling

Abstract: Sampling from the lattice Gaussian distribution has emerged as an important problem in coding, decoding and cryptography. In this paper, the classic Metropolis-Hastings (MH) algorithm in Markov chain Monte Carlo (MCMC) methods is adopted for lattice Gaussian sampling. Two MH-based algorithms are proposed, which overcome the limitation of Klein's algorithm. The first one, referred to as the independent Metropolis-Hastings-Klein (MHK) algorithm, establishes a Markov chain via an independent proposal distribution. We show that the Markov chain arising from this independent MHK algorithm is uniformly ergodic, namely, it converges to the stationary distribution exponentially fast regardless of the initial state. Moreover, the rate of convergence is analyzed in terms of the theta series, leading to predictable mixing time. A symmetric Metropolis-Klein (SMK) algorithm is also proposed, which is proven to be geometrically ergodic.

Category / Keywords: foundations / Lattice Gaussian sampling, MCMC methods, Metropolis-Hastings algorithm, closest vector problem.

Original Publication (in the same form): IEEE Trans. Inform. Theory, vol. 64, no. 2, pp. 738751, Feb. 2018.

Date: received 5 Jun 2019

Contact author: c ling at imperial ac uk

Available format(s): PDF | BibTeX Citation

Version: 20190606:113425 (All versions of this report)

Short URL: ia.cr/2019/666


[ Cryptology ePrint archive ]