论文研究并行BKZ算法.pdf

实践中对于高维的最佳格基规约算法是Schnorr-Euchner的BKZ。格密码体制的所有安全估计都是基于BKZ的NTL来实现的，但随着维数的增加，格基规约算法的运行时间会急剧增加。最近关于格计数的进展表明，BKZ和NTL的实现不再是最优的，但对于安全性估计的确切影响还不清楚。用BKZ的并行技术来评估这种影响是一种比较好的方法。为了降低格基约化算法的运行时间，提出了一种高效的并行算法来模拟高维情况下块长度≥50的BKZ行为，这可以近似预测输出质量及其运行时间，从而修正格安全的估计。