BKZ
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.
Keywords for this software
References in zbMATH (referenced in 66 articles , 1 standard article )
Showing results 1 to 20 of 66.
Sorted by year (- Cheon, Jung Hee; Son, Yongha; Yhee, Donggeon: Practical FHE parameters against lattice attacks (2022)
- Xu, Jun; Sarkar, Santanu; Hu, Lei: Revisiting orthogonal lattice attacks on approximate common divisor problems (2022)
- Albrecht, Martin R.; Bai, Shi; Li, Jianwei; Rowell, Joe: Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance (2021)
- Arunachalam, Srinivasan; Grilo, Alex Bredariol; Sundaram, Aarthi: Quantum hardness of learning shallow classical circuits (2021)
- Ducas, Léo; Yu, Yang: Learning strikes again: the case of the DRS signature scheme (2021)
- Kirchner, Paul; Espitau, Thomas; Fouque, Pierre-Alain: Towards faster polynomial-time lattice reduction (2021)
- Chillotti, Ilaria; Gama, Nicolas; Georgieva, Mariya; Izabachène, Malika: TFHE: fast fully homomorphic encryption over the torus (2020)
- Das, Dipayan; Hoffstein, Jeffrey; Pipher, Jill; Whyte, William; Zhang, Zhenfei: Modular lattice signatures, revisited (2020)
- Doröz, Yarkın; Sunar, Berk: Flattening NTRU for evaluation key free homomorphic encryption (2020)
- Ferradi, Houda; Géraud, Rémi; Guilley, Sylvain; Naccache, David; Tibouchi, Mehdi: Recovering secrets from prefix-dependent leakage (2020)
- Hoffstein, Jeffrey; Silverman, Joseph H.; Whyte, William; Zhang, Zhenfei: A signature scheme from the finite field isomorphism problem (2020)
- Kunihiro, Noboru; Takayasu, Atsushi: Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes (2020)
- Sun, Hong-Yu; Zhu, Xuan-Yong; Zheng, Qun-Xiong: Predicting truncated multiple recursive generators with unknown parameters (2020)
- Yasuda, Masaya: Self-dual DeepBKZ for finding short lattice vectors (2020)
- Yasuda, Masaya; Nakamura, Satoshi; Yamaguchi, Junpei: Analysis of DeepBKZ reduction for finding short lattice vectors (2020)
- Albrecht, Martin R.; Ducas, Léo; Herold, Gottfried; Kirshanova, Elena; Postlethwaite, Eamonn W.; Stevens, Marc: The general sieve kernel and new records in lattice reduction (2019)
- Bindel, Nina; Buchmann, Johannes; Göpfert, Florian; Schmidt, Markus: Estimation of the hardness of the learning with errors problem with a restricted number of samples (2019)
- Sipasseuth, Arnaud; Plantard, Thomas; Susilo, Willy: Enhancing Goldreich, Goldwasser and Halevi’s scheme with intersecting lattices (2019)
- Wunderer, Thomas: A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack (2019)
- Yasuda, Masaya; Yamaguchi, Junpei: A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths (2019)