On the security of OSIDH
On the security of OSIDH
复制标题
论OSIDH的安全性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
L. D. Feo
中科院分区：
文献类型：
--
作者：
Pierrick Dartois;L. D. Feo
定向超奇异同源 Diffie-Hellman 是 Colò 和 Kohel 最近提出的后量子密钥交换方案。它基于二次虚数阶理想类群在超奇异椭圆曲线子集上的群作用，从这个意义上说，它可以被视为流行的基于同源密钥交换 CSIDH 的推广。然而，从算法的角度来看，OSIDH 与 CSIDH 有很大不同。从某种意义上说，OSIDH 使用的类组比 CSIDH 中的结构化程度更高，这造成了 Colò 和 Kohel 已经认识到的潜在弱点。为了规避这个弱点，他们提出了一种巧妙的方法来实现密钥交换，通过交换类组在公共曲线附近如何行为的部分信息，并推测这些附加信息不会影响安全性。在这项工作中，我们在 Onuki 之前的工作的基础上提出了一种新的攻击，重新审视了 OSIDH 的安全性。我们的攻击具有指数级的复杂性，但与 Onuki 的攻击不同，它实际上打破了 Colò 和 Kohel 的参数。我们还讨论了攻击的对策，并从效率和功能的角度分析了它们对 OSIDH 的影响。
The Oriented Supersingular Isogeny Diffie–Hellman is a postquantum key exchange scheme recently introduced by Colò and Kohel. It is based on the group action of an ideal class group of a quadratic imaginary order on a subset of supersingular elliptic curves, and in this sense it can be viewed as a generalization of the popular isogeny based key exchange CSIDH. From an algorithmic standpoint, however, OSIDH is quite different from CSIDH. In a sense, OSIDH uses class groups which are more structured than in CSIDH, creating a potential weakness that was already recognized by Colò and Kohel. To circumvent the weakness, they proposed an ingenious way to realize a key exchange by exchanging partial information on how the class group acts in the neighborhood of the public curves, and conjectured that this additional information would not impact security. In this work we revisit the security of OSIDH by presenting a new attack, building upon previous work of Onuki. Our attack has exponential complexity, but it practically breaks Colò and Kohel’s parameters unlike Onuki’s attack. We also discuss countermeasures to our attack, and analyze their impact on OSIDH, both from an efficiency and a functionality point of view.