You are looking at a specific version 20190605:134957 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 65, NO. 6, JUNE 2019
Keywords
lattice Gaussian samplingMarkov chain Monte Carlobounded distance decodingtrapdoor sampling
Contact author(s)
c ling @ imperial ac uk
History
2019-06-05: revised
2019-06-04: received
See all versions
Short URL
https://ia.cr/2019/660
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.