并行BKZ算法在高维格基规约中的效率提升与安全性评估

"这篇论文探讨了并行BKZ算法在格基规约中的应用，旨在解决随着维度增加导致的格基规约算法运行时间急剧增加的问题。论文提到了Schnorr-Euchner的BKZ算法是目前高维最佳的格基规约算法，而NTL则是其安全性的基础。近期的研究表明，BKZ和NTL的实现可能不是最优的，但对安全性影响的具体程度尚不清楚。论文提出了一种高效的并行算法，用于模拟块长度大于50的高维BKZ行为，以预测输出质量和运行时间，进而修正格安全的估计。该研究受到北京电子科技学院信息安全重点实验室开放基金资助，并由陈辉焱、刘乐和杨毅合作完成。" 本文关注的是格密码学中的一个关键问题——格基规约，特别是Schnorr-Euchner提出的BKZ算法。BKZ算法是实践中用于高维格基规约的首选方法，它对于评估和确保格密码体制的安全性至关重要。然而，随着处理的维度增加，算法的计算复杂度和执行时间显著上升，这成为了限制其应用的一个重要因素。 NTL（Number Theory Library）是实现BKZ算法的基础，用于进行数学计算，尤其是在数论领域。但最新的研究发现，现有的BKZ和NTL实现可能并不是效率最高的。这引发了对安全性估计准确性的质疑，因为算法效率的降低可能影响到对格密码系统安全性的判断。 为了解决这个问题，论文提出了并行BKZ算法。这种并行化的方法旨在减少高维情况下，尤其是块长度大于50时的格基约化算法的运行时间。通过并行计算，可以更有效地模拟和预测算法的输出质量和运行时间，从而为修正格安全性提供依据。这种方法有助于提高计算效率，同时对格密码系统的安全性评估进行更新，以适应更高维度的挑战。 作者团队由陈辉焱、刘乐和杨毅组成，他们的研究得到了北京电子科技学院信息安全重点实验室的支持。这项工作不仅在理论上有重要的贡献，而且对于优化格密码系统和提升其安全性能具有实践意义。通过并行技术改进现有算法，可以预期在未来的格密码学研究和应用中发挥重要作用。