CryptoDB
Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | CRYPTO 2021 |
| 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. |
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31111,
title={Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84245-1_25},
author={Martin Albrecht and Shi Bai and Jianwei Li and Joe Rowell},
year=2021
}