You are looking at a specific version 20201014:180158 of this paper. See the latest version.

Paper 2020/1260

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

Martin R. Albrecht and Shi Bai and 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 (compared to 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. As a consequence, we update the extrapolation of the crossover rank between a square-root cost estimate for quantum enumeration using our algorithm and the Core-SVP cost estimate for quantum sieving to 547.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.