编辑推荐:
Eker?和G?rtner提出的一种算法,受Regev因子分解算法启发,计算素数域乘法群中的离散对数。渐近地,它具有与Shor算法相同的量子比特和门复杂度,但将计算分成d个独立的并行运行。该参数的最优值为d~√n,其中n为密码群的比特大小。研究人员提出将该算法
Eker?和G?rtner提出的一种算法,受Regev因子分解算法启发,计算素数域乘法群中的离散对数。渐近地,它具有与Shor算法相同的量子比特和门复杂度,但将计算分成d个独立的并行运行。该参数的最优值为d~√n,其中n为密码群的比特大小。研究人员提出将该算法扩展到超椭圆曲线。对于亏格g~√n的曲线(此类曲线不用于密码学),研究人员无条件证明了并行运行的最优数量d~√n仍然可以达到。对于亏格二曲线,研究人员提出一种启发式算法。虽然其运行时间加速在一般情况下难以量化,但研究人员表明,对于与密码学相关的特定曲线,包括GLV友好曲线(GLV-friendly curves)和配对友好曲线(pairing-friendly curves),可以预期使用多达d=8个并行运行。
量子计算对传统公钥密码系统构成严峻挑战。Shor算法能够在量子计算机上高效求解整数分解和离散对数问题,因此对基于离散对数困难性的密码方案构成威胁。Eker?和G?rtner受Regev因子分解算法的启发,提出了一种在素数域乘法群上计算离散对数的算法。该算法在渐近意义上具有与Shor算法相同的量子比特和门复杂度,但其独特之处在于将整个计算分解为d个相互独立、并行的运行。这一参数d的最优取值与密码群的比特大小n有关,即d~√n。然而,该算法原本仅适用于素数域乘法群,尚未被推广到超椭圆曲线这一更一般的密码学载体。由于超椭圆曲线密码系统具有较短的操作数长度和较小的带宽需求,在资源受限的场景中具有应用前景,因此评估此类系统在量子攻击下的实际安全性具有重要的理论与现实意义。
针对上述问题,研究人员提出了一个将Eker?–G?rtner离散对数算法扩展到超椭圆曲线的框架。对于亏格为g~√n的曲线,这类曲线在传统密码学中通常不被使用,但研究人员在理论上无条件证明了最优并行运行数量d~√n仍然可以实现。对于更为常见的亏格二曲线,研究人员提出一种启发式算法,并利用特定密码学相关曲线进行了评估,表明其可以预期使用最多d=8个并行运行。这些结论有助于更全面地理解超椭圆曲线密码系统在量子环境下的安全性边界。该论文发表在《Cryptography》期刊上。
为开展此项研究,研究人员主要运用了以下关键技术方法。首先,基于Regev因子分解算法的核心思想,将Eker?–G?rtner离散对数算法中的并行化参数d进行扩展。其次,利用超椭圆曲线上的离散对数问题结构,将该问题归约到素数域乘法群离散对数的框架中,从而复用原有算法的资源复杂度分析。最后,针对亏格二曲线,通过启发式复杂度分析和针对GLV友好曲线(GLV-friendly curves)与配对友好曲线(pairing-friendly curves)的具体实例评估,量化并行运行数量对运行时间加速的影响。
研究结果包含两个主要方面。
第一方面:亏格g~√n曲线的无条件证明。研究人员通过严格的理论推导,证明在亏格g~√n的情况下,即使曲线不用于密码学,该扩展算法仍然能够达到与素数域情形相同的渐近并行参数d~√n。这从理论上确认了并行化策略在超椭圆曲线上的适用性。
第二方面:亏格二曲线的启发式算法。研究人员针对实际密码学中常见的亏格二曲线提出了启发式算法。虽然该算法的运行时间加速在一般情况下难以从理论上精确量化,但对于密码学中具有特殊结构的曲线,包括GLV友好曲线和配对友好曲线,研究人员通过分析表明,算法可以预期使用多达d=8个并行运行。这意味着在特定曲线实例上,该启发式方法能够以较高并行度运行,从而可能提高攻击效率。
在讨论部分,研究人员指出,该扩展算法的实际效果高度依赖于曲线的亏格和代数结构。对于高亏格曲线,虽然理论结果无条件成立,但此类曲线在密码学中不常使用;而对于亏格二曲线,启发式算法在特定结构曲线上具有实用潜力。此外,并行参数d的选择需要在量子比特资源、门复杂度和运行时间之间进行权衡,具体最优值可能因曲线类型而异。
研究结论部分翻译如下:对于亏格g~√n的曲线,研究人员无条件证明了最优并行运行数量d~√n仍然可以达到。对于亏格二曲线,研究人员提出一种启发式算法,并表明虽然其运行时间加速在一般情况下难以量化,但对于与密码学相关的特定曲线,包括GLV友好曲线和配对友好曲线,可以预期使用多达d=8个并行运行。