Further results on independent Metropolis-Hastings-Klein sampling

Wang, Z; Ling, C

doi:https://www.dx.doi.org/10.1109/ISIT.2016.7541634

File(s)

bare_jrnl.pdf (253.16 KB)

Accepted version

Author(s)

Wang, Z

Ling, C

Type

Conference Paper

Abstract

Sampling from a lattice Gaussian distribution is emerging as an important problem in coding and cryptography. This paper gives a further analysis of the independent Metropolis-Hastings-Klein (MHK) algorithm we presented at ISIT 2015. We derive the exact spectral gap of the induced Markov chain, which dictates the convergence rate of the independent MHK algorithm. Then, we apply the independent MHK algorithm to lattice decoding and obtained the decoding complexity for solving the CVP as Õ(e∥Bx-c∥2 / mini ∥b̂i∥2). Finally, the tradeoff between decoding radius and complexity is also established.

Date Issued

2016-08-11

Date Acceptance

2016-04-03

Citation

IEEE International Symposium on Information Theory (ISIT), 2016

URI

http://hdl.handle.net/10044/1/40322

DOI

https://www.dx.doi.org/10.1109/ISIT.2016.7541634

ISSN

2157-8117

Publisher

IEEE

Journal / Book Title

IEEE International Symposium on Information Theory (ISIT)

Copyright Statement

© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Sponsor

Commission of the European Communities

Grant Number

317562

Source

ISIT 2016

Publication Status

Published

Start Date

2016-07-10

Finish Date

2016-07-15

Coverage Spatial

Barcelona, Spain