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.

References in zbMATH (referenced in 66 articles , 1 standard article )

Showing results 21 to 40 of 66.
Sorted by year (citations)
  1. Bagheri, Khadijeh; Sadeghi, Mohammad-Reza; Panario, Daniel: A non-commutative cryptosystem based on quaternion algebras (2018)
  2. Marcos del Blanco, David Yeregui; Panizo Alonso, Luis; Hermida Alonso, Jose Angel: Review of cryptographic schemes applied to remote electronic voting systems: remaining challenges and the upcoming post-quantum paradigm (2018)
  3. Montanaro, Ashley: Quantum-walk speedup of backtracking algorithms (2018)
  4. Wang, Yuntao; Aono, Yoshinori; Takagi, Tsuyoshi: An experimental study of Kannan’s embedding technique for the search LWE problem (2018)
  5. Yu, Yang; Xiao, Dianyan: Improved broadcast attacks against subset sum problems via lattice oracle (2018)
  6. Albrecht, Martin R.: On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL (2017)
  7. Aono, Yoshinori; Nguyen, Phong Q.: Random sampling revisited: lattice enumeration with discrete pruning (2017)
  8. Bachlechner, Thomas C.; Eckerle, Kate; Janssen, Oliver; Kleban, Matthew: Systematics of aligned axions (2017)
  9. Boneh, Dan; Ishai, Yuval; Sahai, Amit; Wu, David J.: Lattice-based SNARGs and their application to more efficient obfuscation (2017)
  10. Hoffstein, Jeff; Pipher, Jill; Schanck, John M.; Silverman, Joseph H.; Whyte, William; Zhang, Zhenfei: Choosing parameters for NTRUEncrypt (2017)
  11. Kim, Jeongsu; Park, Suyong; Kim, Seonggeun; Jang, Busik; Hahn, Sang Geun; Jung, Sangim; Roh, Dongyoung: Analysis of error terms of signatures based on learning with errors (2017)
  12. Kirchner, Paul; Fouque, Pierre-Alain: Revisiting lattice attacks on overstretched NTRU parameters (2017)
  13. Lyubashevsky, Vadim; Neven, Gregory: One-shot verifiable encryption from lattices (2017)
  14. Stebila, Douglas; Mosca, Michele: Post-quantum key exchange for the Internet and the open quantum safe project (2017)
  15. Yang, Shang-Yi; Kuo, Po-Chun; Yang, Bo-Yin; Cheng, Chen-Mou: Gauss sieve algorithm on GPUs (2017)
  16. Albrecht, Martin; Bai, Shi; Ducas, Léo: A subfield lattice attack on overstretched NTRU assumptions. Cryptanalysis of some FHE and graded encoding schemes (2016)
  17. Buchmann, Johannes A.; Butin, Denis; Göpfert, Florian; Petzoldt, Albrecht: Post-quantum cryptography: state of the art (2016)
  18. Chillotti, Ilaria; Gama, Nicolas; Georgieva, Mariya; Izabachène, Malika: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds (2016)
  19. Chung, Kyungmi; Lee, Hyang-Sook; Lim, Seongan: An efficient lattice reduction using reuse technique blockwisely on NTRU (2016)
  20. Doröz, Yarkın; Hu, Yin; Sunar, Berk: Homomorphic AES evaluation using the modified LTV scheme (2016)