POSTER: An Efficient Sieve Algorithm for Ideal Lattices

doi:10.1007/978-981-95-2961-2_30

2026-01-01

PRE

Yuntao Wang *

Toda, Kazutaka

DOI：10.1007/978-981-95-2961-2_30

原文链接

原文求助

摘要

En 中文

量子计算的兴起加剧了对广泛部署的密码学原语（包括RSA和椭圆曲线密码学）安全的担忧。这反过来又提高了对能够抵御量子攻击的下一代密码算法的需求，格基密码学作为加密和签名方案的主要候选者脱颖而出。格基密码学的安全性基于最短向量问题（SVP），尽管提出了许多旨在评估或攻击该问题的算法，但其难度仍未解决。在解决SVP的算法中，筛法家族以运行时间和空间复杂度之间的权衡为特征。在本文中，我们介绍了理想三筛法，它结合了元组闵可夫斯基筛的空间效率和理想高斯筛的旋转优势。该算法设计用于广泛适用性，特别是在素循环理想格上表现出卓越性能，优于理想高斯筛。因此，它产生的闵可夫斯基约简格向量质量显著高于高斯约简向量。同时，理想三筛法保持了与理想高斯筛相同的大O(1/n^{2(0.1887n+o(n))})渐近空间复杂度，其运行时间为O(n^{2(0.4812n+o(n)))}。此外，我们开发了一套利用理想格结构特性的技术，以进一步提高理想三筛法的效率。这些技术实现了范数和内积的更快评估，并消除了不必要的约简步骤，从而显著减少了执行时间。最后，我们展示了我们提案的实验结果，证明了与现有方法相比的效率。

Keyword:

Post-Quantum Cryptography

Ideal Lattice

SVP

Sieve Algorithms