| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6874275 | Information Processing Letters | 2014 | 4 Pages |
Abstract
In CRYPTO 2009, Lyubashevsky and Micciancio presented reductions BDD1/2γ (Bounded Distance Decoding Problem) ⩽ uSVPγ (Unique Shortest Vector Problem) ⩽ BDD1/γ, and posed an open problem whether the reduction gap can be closed. This paper concerns bounded distance decoding (BDD) problems for lattices with large λ2-gap. In the presence of larger λ2-gap, better reductions from BDD to uSVP and exact SVP are obtained. Some result can be regarded as a partial solution to the open problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mingjie Liu, Xiaoyun Wang, Guangwu Xu, Xuexin Zheng,