实践中对于高维的最佳格基规约算法是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 paper 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.
展开▼
