Improved Torsion-Point Attacks on SIDH Variants
Improved Torsion-Point Attacks on SIDH Variants
复制标题
改进对 SIDH 变体的扭转点攻击
DOI：
10.1007/978-3-030-84252-9_15
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Stange, Katherine E.
中科院分区：
文献类型：
--
作者：
de Quehen, Victoria;Kutas, Péter;Leonardi, Chris;Martindale, Chloe;Panny, Lorenz;Petit, Christophe;Stange, Katherine E.
SIDH是一种后量子密钥交换算法，它基于超奇异椭圆曲线之间发现同构的假设困难。然而，SIDH和相关的密码系统也揭示了额外的信息：一个秘密的限制是曲线的一个子群（扭点信息）。Petit [31]是第一个证明扭点信息可以显著降低发现秘密同源性的难度的人。特别是，佩蒂特表明，SIDH的“过度拉伸”参数化可以在多项式时间内被打破。然而，这并不影响文献中提出的任何密码系统的安全性。本文的贡献是双重的：首先，我们通过利用来自对偶和Frobenius Issues的额外信息来加强[31]的技术。这大大扩展了扭点攻击的影响。特别是，我们的技术产生了一个经典攻击，完全打破了[2]的然后方组密钥交换，首先在[17]中引入GSIDH，对于6方或更多方，以及对3方或更多方的量子攻击，改进了最知名的渐近复杂度。我们还提供了一个岩浆实现我们的攻击为6方。我们给出了我们的攻击适用的全部参数。其次，我们构建了SIDH变体，这些变体被设计为对我们的攻击很弱;这包括起始曲线的后门选择，以及基域素数的后门选择。我们强调，我们的结果不会降低NIST提交的SIKE [20]的安全性或揭示其任何弱点。
SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of finding isogenies between supersingular elliptic curves. However, SIDH and related cryptosystems also reveal additional information: the restriction of a secret isogeny to a subgroup of the curve (torsion-point information). Petit [31] was the first to demonstrate that torsion-point information could noticeably lower the difficulty of finding secret isogenies. In particular, Petit showed that “overstretched” parameterizations of SIDH could be broken in polynomial time. However, this did not impact the security of any cryptosystems proposed in the literature. The contribution of this paper is twofold: First, we strengthen the techniques of [31] by exploiting additional information coming from a dual and a Frobenius isogeny. This extends the impact of torsion-point attacks considerably. In particular, our techniques yield a classical attack that completely breaks then-party group key exchange of [2], first introduced as GSIDH in [17], for 6 parties or more, and a quantum attack for 3 parties or more that improves on the best known asymptotic complexity. We also provide a Magma implementation of our attack for 6 parties. We give the full range of parameters for which our attacks apply. Second, we construct SIDH variants designed to be weak against our attacks; this includes backdoor choices of starting curve, as well as backdoor choices of base-field prime. We stress that our results do not degrade the security of, or reveal any weakness in, the NIST submission SIKE [20].