Cryptology ePrint Archive: Report 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.
Category / Keywords: public-key cryptography / Lattice Reduction, BKZ, Enumeration, and (H)SVP.
Date: received 11 Oct 2020, last revised 11 Oct 2020
Contact author: martin albrecht at royalholloway ac uk, sbai@fau edu, lijianweisk@sina com, joe rowell@rhul ac uk
Available format(s): PDF | BibTeX Citation
Version: 20201014:180158 (All versions of this report)
Short URL: ia.cr/2020/1260
[ Cryptology ePrint archive ]