A Study on Parallel Tuple Sieve Algorithm

doi:10.1007/978-981-95-0172-4_6

2026-01-01

PRE

Yuntao Wang *

K. Imai

Eiichiro Fujisaki

DOI：10.1007/978-981-95-0172-4_6

原文链接

原文求助

摘要

En 中文

随着大规模量子计算的发展持续推进，当前密码系统的安全性，如RSA和椭圆曲线密码学，已普遍被认为受到严重威胁。这些系统依赖于整数分解问题或椭圆曲线上的离散对数问题的难度，而这两者都易受量子攻击。为应对此挑战，基于格上最短向量问题（SVP）及其近似变体的格密码学已成为有前景的下一代解决方案。然而，格密码学的部署需要仔细的参数优化，并需借鉴攻击算法及大规模计算挑战的研究成果。筛算法是格攻击中最实用的算法之一。本研究提出了一种并行化的元组筛算法（Tuple Sieve），该近似SVP求解算法相较于Ishiguro等人于2014年PKC会议上提出的并行高斯筛算法，降低了内存使用。我们在多核CPU上实现了该算法并进行测试。在低维格上的评估，例如使用16核的42维格，表明相较于传统元组筛算法，实现了约31倍的加速，同时内存使用量较原始元组筛减少了43%，空间成本较并行高斯筛降低了67%。

Keyword:

Post-Quantum Cryptography

Lattice

Parallel Tuple Sieve Algorithm