Paper 2020/1260

Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance

Martin R. Albrecht, Shi Bai, Jianwei Li, and Joe Rowell


This work provides a systematic investigation of the use of approximate enumeration oracles in BKZ, building on recent technical progress on speeding-up lattice enumeration: relaxing (the search radius of) enumeration and extended preprocessing which preprocesses in a larger rank than the enumeration rank. First, we heuristically justify that relaxing enumeration with certain extreme pruning asymptotically achieves an exponential speed-up for reaching the same root Hermite factor (RHF). Second, we perform simulations/experiments to validate this and the performance for relaxed enumeration with numerically optimised pruning for both regular and extended preprocessing. Upgrading BKZ with such approximate enumeration oracles gives rise to our main result, namely a practical and faster (wrt. previous work) polynomial-space lattice reduction algorithm for reaching the same RHF in practical and cryptographic parameter ranges. We assess its concrete time/quality performance with extensive simulations and experiments.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Lattice ReductionBKZEnumerationand (H)SVP.
Contact author(s)
martin albrecht @ royalholloway ac uk
sbai @ fau edu
lijianweisk @ sina com
joe rowell @ rhul ac uk
2021-06-18: revised
2020-10-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R.  Albrecht and Shi Bai and Jianwei Li and Joe Rowell},
      title = {Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1260},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.