×

BKZ

swMATH ID: 10242
Software Authors: Chen, Yuanmi; Nguyen, Phong Q.
Description: BKZ 2.0: Better lattice security estimates. 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 \(geq 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.
Homepage: http://link.springer.com/chapter/10.1007/978-3-642-25385-0_1
Related Software: NTRU; NTL; GitHub; G6K; fpLLL; BLISS; FHEW; SageMath; NTRUSign; HElib; fhe; SWIFFT; PotLLL; DeepLLL; FrodoKEM; fpylll; TFHE; ring-LWE; Magma; FFTW
Referenced in: 71 Publications

Standard Articles

1 Publication describing the Software, including 1 Publication in zbMATH Year
BKZ 2.0: Better lattice security estimates. Zbl 1227.94037
Chen, Yuanmi; Nguyen, Phong Q.
2011
all top 5

Referenced by 163 Authors

7 Yasuda, Masaya
5 Albrecht, Martin R.
5 Zhang, Zhenfei
3 Bai, Shi
3 Ducas, Léo
3 Fouque, Pierre-Alain
3 Hoffstein, Jeffrey
3 Kirchner, Paul
3 Mosca, Michele
3 Nakamura, Satoshi
3 Nguyen, Phong Q.
3 Plantard, Thomas
3 Susilo, Willy
3 van de Pol, Joop
3 Whyte, William
2 Aono, Yoshinori
2 Buchmann, Johannes A.
2 Chen, Yuanmi
2 Chillotti, Ilaria
2 Doröz, Yarkın
2 Gama, Nicolas
2 Georgieva, Mariya
2 Göpfert, Florian
2 Izabachène, Malika
2 Kirshanova, Elena
2 Kogure, Jun
2 Laarhoven, Thijs
2 Li, Shuaigang
2 Lu, Xianhui
2 Lyubashevsky, Vadim
2 Micciancio, Daniele
2 Naehrig, Michael
2 Peikert, Chris
2 Pipher, Jill Catherine
2 Shimoyama, Takeshi
2 Silverman, Joseph Hillel
2 Smart, Nigel P.
2 Sunar, Berk
2 Takagi, Tsuyoshi
2 Yamaguchi, Junpei
2 Yang, Bo-Yin
2 Yu, Yang
1 Arunachalam, Srinivasan
1 Bachlechner, Thomas C.
1 Bagheri, Khadijeh
1 Bay, Asli
1 Bi, Lei
1 Bindel, Nina
1 Boneh, Dan
1 Bos, Joppe W.
1 Boureanu, Ioana
1 Butin, Denis
1 Cao, Weiqiong
1 Chen, Hua
1 Chen, Jiazhe
1 Cheng, Chen-Mou
1 Cheon, Jung Hee
1 Chung, Kyungmi
1 Cid, Carlos Frederico
1 Damgård, Ivan Bjerre
1 Das, Dipayan
1 Eckerle, Kate
1 Espitau, Thomas
1 Fan, Limin
1 Fan, Shuqin
1 Faugère, Jean-Charles
1 Ferradi, Houda
1 Fitzpatrick, Robert
1 Fontein, Felix
1 Fujisawa, Katsuki
1 Fukushima, Kazuhide
1 Galbraith, Steven D.
1 Géraud, Rémi
1 Grilo, Alex Bredariol
1 Guilley, Sylvain
1 Güneysu, Tim
1 Guo, Qian
1 Ha, Jincheol
1 Hahn, Sang Geun
1 Hermida Alonso, José Angel
1 Herold, Gottfried
1 Hu, Lei
1 Hu, Yin
1 Huang, Yun-Ju
1 Ikematsu, Yasuhiko
1 Ishai, Yuval
1 Jang, Busik
1 Janssen, Oliver
1 Jarvis, Katherine
1 Johansson, Thomas
1 Jung, Sangim
1 Kim, Jeongsu
1 Kim, Seonggeun
1 Kim, Seongkwang
1 Kiyomoto, Shinsaku
1 Kleban, Matthew B.
1 Koshiba, Takeshi
1 Kudo, Momonari
1 Kunihiro, Noboru
1 Kuo, Po-Chun
...and 63 more Authors

Referencing Publications by Year