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.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2014, 114 (1-2), pp.9-12. 〈10.1016/j.ipl.2013.10.004〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922234
Contributeur : Phong Q. Nguyen <>
Soumis le : mercredi 25 décembre 2013 - 10:56:27
Dernière modification le : vendredi 25 mai 2018 - 12:02:06

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

265