BKZ 2.0: Better Lattice Security Estimates

Yuanmi Chen 1 Phong Q. Nguyen 1, 2
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : The best lattice reduction algorithm known in practice for high dimension is Schnorr-Euchner’s BKZ: all security estimates of lattice cryptosystems are based on NTL’s old implementation of BKZ. However, recent progress on lattice enumeration suggests that BKZ and its NTL implementation are no longer optimal, but the precise impact on security estimates was unclear. We assess this impact thanks to extensive experiments with BKZ 2.0, the first state-of-the-art implementation of BKZ incorporating recent improvements, such as Gama-Nguyen-Regev pruning. We propose an efficient simulation algorithm to model the behaviour of BKZ in high dimension with high blocksize ≥ 50, which can predict approximately both the output quality and the running time, thereby revising lattice security estimates. For instance, our simulation suggests that the smallest NTRUSign parameter set, which was claimed to provide at least 93-bit security against key-recovery lattice attacks, actually offers at most 65-bit security
Type de document :
Communication dans un congrès
Dong Hoon Lee; Xiaoyun Wang. ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2011, Seoul, South Korea. Springer, 7073, pp.1-20, 2011, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-25385-0_1〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01109961
Contributeur : Brigitte Briot <>
Soumis le : mardi 27 janvier 2015 - 11:34:21
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10

Identifiants

Collections

Citation

Yuanmi Chen, Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. Dong Hoon Lee; Xiaoyun Wang. ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2011, Seoul, South Korea. Springer, 7073, pp.1-20, 2011, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-25385-0_1〉. 〈hal-01109961〉

Partager

Métriques

Consultations de la notice

137