并行BKZ算法  

Parallel BKZ algorithm

作　　者：陈辉焱[1,2] 刘乐[2] 杨毅[1] 

机构地区：[1]北京电子科技学院,北京100070 [2]西安电子科技大学通信工程学院,西安710071

出　　处：《计算机应用研究》2017年第10期2946-2949,共4页Application Research of Computers

基　　金：北京电子科技学院信息安全重点实验室开放基金资助项目(2014KF-chy)

摘　　要：实践中对于高维的最佳格基规约算法是Schnorr-Euchner的BKZ。格密码体制的所有安全估计都是基于BKZ的NTL来实现的,但随着维数的增加,格基规约算法的运行时间会急剧增加。最近关于格计数的进展表明,BKZ和NTL的实现不再是最优的,但对于安全性估计的确切影响还不清楚。用BKZ的并行技术来评估这种影响是一种比较好的方法。为了降低格基约化算法的运行时间,提出了一种高效的并行算法来模拟高维情况下块长度≥50的BKZ行为,这可以近似预测输出质量及其运行时间,从而修正格安全的估计。The best lattice basis reduction algorithm known in practice for high dimensions is Schnorr-Euchner＇ s BKZ. All security estimates of lattice cryptosystems are based on NTL＇ s implementation of BKZ. With the increase of dimension, the time cost of lattice basis reduction algorithms will increase rapidly. Recent progress on lattice enumeration suggests that BKZ and NTL implementation are no longer optimal, but the precise impact on security estimates is unclear. To evaluate the effect with the parallel technology of BKZ is a better method. In order to reduce the running time of lattice basis reduction, this pa- per proposed an efficient parallel algorithm to simulate the behavior of BKZ in high dimension with high block size≥50, which could predict approximately both the output quality and the running time.

关 键 词：格基规约 BKZ NTL 并行技术 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]