Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance
Lattice Reduction with Approximate Enumeration Oracles: Practical Algorithms and Concrete Performance
复制标题
DOI：
10.1007/978-3-030-84245-1_25
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Martin R. Albrecht;Shi Bai;Jianwei Li;Joe Rowell
中科院分区：
文献类型：
--
作者：
Martin R. Albrecht;Shi Bai;Jianwei Li;Joe Rowell
这项工作提供了一个系统的调查使用近似枚举预言BKZ，建立在最近的技术进步，加快格枚举：放宽（搜索半径）枚举和扩展预处理，预处理在一个更大的排名比枚举秩。首先，我们证明了放松枚举与某些极端修剪渐近达到指数加速达到相同的根埃尔米特因子（RHF）。其次，我们进行模拟/实验，以验证这一点和性能的放松枚举与数值优化修剪定期和扩展preprocessing.Upgrading BKZ与这样的近似枚举神谕产生我们的主要结果，即一个实用的和更快的（wrt。以前的工作）多项式空间格约简算法达到相同的RHF在实际和加密参数范围。我们评估其具体的时间/质量性能与广泛的模拟和实验。
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 andextended preprocessingwhich 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.