Skip to Main content Skip to Navigation
Journal articles

A note on BDD problems with λ2-gap

Mingjie Liu 1 Xiaoyun Wang 1, 2 Guangwu Xu 1 Xuexin Zheng 1
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
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.
Document type :
Journal articles
Complete list of metadata
Contributor : Phong Q. Nguyen <>
Submitted on : Wednesday, December 25, 2013 - 10:56:27 AM
Last modification on : Wednesday, June 2, 2021 - 3:39:52 AM




Mingjie Liu, Xiaoyun Wang, Guangwu Xu, Xuexin Zheng. A note on BDD problems with λ2-gap. Information Processing Letters, Elsevier, 2014, 114 (1-2), pp.9-12. ⟨10.1016/j.ipl.2013.10.004⟩. ⟨hal-00922234⟩



Record views