A note on BDD problems with lambda(2)-gap

作者：Liu, Mingjie; Wang, Xiaoyun^*; Xu, Guangwu; Zheng, Xuexin

来源：Information Processing Letters, 2014, 114(1-2): 9-12.

DOI：10.1016/j.ipl.2013.10.004

• Cryptography
• Lattice
• BDD
• uSVP
• Successive minima

In CRYPTO 2009, Lyubashevsky and Micciancio presented reductions BDD1/2 gamma (Bounded Distance Decoding Problem) <= uSVP(gamma) (Unique Shortest Vector Problem) <= BDD1/gamma, and posed an open problem whether the reduction gap can be closed. This paper concerns bounded distance decoding (BDD) problems for lattices with large lambda(2)-gap. In the presence of larger lambda(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.

• 出版日期2014-2
• 单位清华大学; 山东大学; 北京大学