Lattice Gaussian Sampling by Markov Chain Monte Carlo: Bounded Distance Decoding and Trapdoor Sampling
arXiv:1704.02673
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.
arXiv commentsubmitted to Transaction on Information Theory
References in corpus (9)
- Massive MIMO for Next Generation Wireless Systems
- Semantically Secure Lattice Codes for the Gaussian Wiretap Channel
- Decoding by Sampling: A Randomized Lattice Algorithm for Bounded Distance Decoding
- Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: an Analysis of Stationary Distribution and Mixing Time
- Classical Hardness of Learning with Errors
- Decoding by Embedding: Correct Decoding Radius and DMT Optimality
- Decoding by Sampling - Part II: Derandomization and Soft-output Decoding
- Issues in the Multiple Try Metropolis mixing
- On the Closest Vector Problem with a Distance Guarantee