Paper 2020/1260
Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance
Martin R. Albrecht, Shi Bai, Jianwei Li, and Joe Rowell
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in CRYPTO 2021
- Keywords
- Lattice ReductionBKZEnumerationand (H)SVP.
- Contact author(s)
-
martin albrecht @ royalholloway ac uk
sbai @ fau edu
lijianweisk @ sina com
joe rowell @ rhul ac uk - History
- 2021-06-18: revised
- 2020-10-14: received
- See all versions
- Short URL
- https://ia.cr/2020/1260
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1260, 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{https://eprint.iacr.org/2020/1260}}, url = {https://eprint.iacr.org/2020/1260} }