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.


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

Showing results 41 to 60 of 60.
Sorted by year (citations)
  1. Plantard, Thomas; Susilo, Willy; Zhang, Zhenfei: LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi’s FHE scheme (2015)
  2. Yasuda, Masaya; Shimoyama, Takeshi; Kogure, Jun; Yokoyama, Kazuhiro; Koshiba, Takeshi: Secure statistical analysis using RLWE-based homomorphic encryption (2015)
  3. Bai, Shi; Galbraith, Steven D.: An improved compression technique for signatures based on learning with errors (2014)
  4. Fontein, Felix; Schneider, Michael; Wagner, Urs: PotLLL: a polynomial time version of LLL with deep insertions (2014)
  5. Lepoint, Tancrède; Naehrig, Michael: A comparison of the homomorphic encryption schemes FV and YASHE (2014)
  6. Rohloff, Kurt; Cousins, David Bruce: A scalable implementation of fully homomorphic encryption built on NTRU (2014) ioport
  7. Yasuda, Masaya; Shimoyama, Takeshi; Kogure, Jun: Secret computation of purchase history data using somewhat homomorphic encryption (2014)
  8. Bay, Aslı; Boureanu, Ioana; Mitrokotsa, Aikaterini; Spulber, Iosif; Vaudenay, Serge: The Bussard-Bagga and other distance-bounding protocols under attacks (2013)
  9. Bos, Joppe W.; Lauter, Kristin; Loftus, Jake; Naehrig, Michael: Improved security for a ring-based fully homomorphic encryption scheme (2013)
  10. Laarhoven, Thijs; Mosca, Michele; van de Pol, Joop: Solving the shortest vector problem in lattices faster using quantum search (2013)
  11. Micciancio, Daniele; Peikert, Chris: Hardness of SIS and LWE with small parameters (2013)
  12. Plantard, Thomas; Susilo, Willy; Zhang, Zhenfei: Lattice reduction for modular knapsack (2013)
  13. van de Pol, Joop; Smart, Nigel P.: Estimating key sizes for high dimensional lattice-based systems (2013)
  14. Yan, Jianhua; Wang, Licheng; Wang, Lihua; Yang, Yixian; Yao, Wenbin: Efficient lattice-based signcryption in standard model (2013) ioport
  15. Chen, Yuanmi; Nguyen, Phong Q.: Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers (2012)
  16. Damgård, Ivan; Pastro, Valerio; Smart, Nigel; Zakarias, Sarah: Multiparty computation from somewhat homomorphic encryption (2012)
  17. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas: Practical lattice-based cryptography: a signature scheme for embedded systems (2012)
  18. Huang, Yun-Ju; Liu, Feng-Hao; Yang, Bo-Yin: Public-key cryptography from new multivariate quadratic assumptions (2012)
  19. Micciancio, Daniele; Peikert, Chris: Trapdoors for lattices: simpler, tighter, faster, smaller (2012)
  20. Chen, Yuanmi; Nguyen, Phong Q.: BKZ 2.0: Better lattice security estimates (2011)