Cryptology ePrint Archive: Report 2019/660

Lattice Gaussian Sampling by Markov Chain Monte Carlo: Bounded Distance Decoding and Trapdoor Sampling

Zheng Wang and Cong Ling

Abstract: Sampling from the lattice Gaussian distribution plays an important role in various research fields. In this paper, the Markov chain Monte Carlo (MCMC)-based sampling technique is advanced in several fronts. Firstly, the spectral gap for the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, which is then extended to Peikert's algorithm and rejection sampling; we show that independent MHK exhibits faster convergence. Then, the performance of bounded distance decoding using MCMC is analyzed, revealing a flexible trade-off between the decoding radius and complexity. MCMC is further applied to trapdoor sampling, again offering a trade-off between security and complexity. Finally, the independent multiple-try Metropolis-Klein (MTMK) algorithm is proposed to enhance the convergence rate. The proposed algorithms allow parallel implementation, which is beneficial for practical applications.

Category / Keywords: foundations / lattice Gaussian sampling, Markov chain Monte Carlo, bounded distance decoding, trapdoor sampling

Original Publication (in the same form): IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 65, NO. 6, JUNE 2019

Date: received 4 Jun 2019, last revised 5 Jun 2019

Contact author: c ling at imperial ac uk

Available format(s): PDF | BibTeX Citation

Version: 20190605:134957 (All versions of this report)

Short URL: ia.cr/2019/660


[ Cryptology ePrint archive ]