XiaoMi-AI文件搜索系统
World File Search SystemBKZ
针对LLL和BKZ的参数研究，并应用于最短矢量问题
摘要 - 在这项工作中，我们研究了最短矢量问题（SVP）在学习错误问题（LWES）方面产生的最短媒介问题（SVP）。lwes是模块环上方程式的线性系统，其中将扰动向量添加到右侧。这种类型的问题引起了人们的极大兴趣，因为必须解决LWES，以便能够破坏基于晶格的密码系统作为NIST在2024年发表的基于模块的键盘封装机制。由于这一事实，已经研究了几种基于经典和量子的算法来求解SVP。可用于简化给定SVP的两种著名算法是Lenstra-Lenstra-Lov´asz（LLL）算法和块Korkine-Zolotarev（bkz）算法。LLL和BKZ构造碱基可用于计算SVP的解决方案或近似解决方案。我们研究具有不同尺寸和模块化环的SVP的两种算法的性能。因此，如果LLL或BKZ在给定的SVP中的应用被认为是成功的，那么它们会产生包含SVP的溶液向量的碱基。
精确BKZ模拟的设计
BKZ仿真的主要作用着重于显示BKZ算法的高块大小的行为，因此，当前的晶格安全性分析（例如，对当前LWE/NTRU基于的基于LWE/NTRU的方案）的有效/安全参数 - 选择这些模拟的有效/安全参数集的选择）。本文声称，当前的BKZ模拟不一定足够准确，可以进行精确的晶格安全分析，因此，这项研究首次介绍了两种可证明的“更新GSO/系数/系数的仿真”和“ LLL功能的仿真”的工具，以用于设计准确的BKZ模拟。本文证明，对于典型的SVP求解器“ Z”（例如，GNR驱动，筛分，离散的修剪），如果对“ z_memulate”进行了模拟，可以证明“ z_memulate”可以模仿“ z”的实际运行行为，那么我们可以通过“模拟我们的bkz模拟”来模拟'svpsolver'= z____________________________________________________________________________________________________________________________________________________求解器“ z”。我们的BKZ模拟解决了以前的BKZ模拟中的不同问题和弱点。Our tests show that, altogether, the shape of GSO norms ∥ b ∗ i ∥ 2 , the root-Hermite factor of basis, estimated total-cost and the running-time in “Experimental Running of Original BKZ algorithm” are closer to the corresponding test results in “Our BKZ Simulation” than to the test results in “Chen-Nguyen's BKZ simulation”, “BKZ simulation by Shi Bai et al.”和其他一些BKZ模型和近似值。此外，更新Chen-Nguyen的BKZ模拟的GSO规范/系数的错误策略会导致晶格块中的许多GSO违规错误，另一方面，我们的测试结果验证了我们的BKZ模拟中所有这些错误自动消除了所有这些错误。