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