Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes
Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes
复制标题
CSIDH 和普通同源方案的量子安全分析
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
André Schrottenloher
中科院分区：
文献类型：
--
作者：
X. Bonnetain;André Schrottenloher
. CSIDH是Castryck、Lange、Martindale、Panny和Renes最近提出的一个后量子非交互密钥交换方案。它在设计上类似于Couveignes，Rostovtsev和Stolbunov的方案，但它用超奇异椭圆曲线代替普通椭圆曲线，以便在时间和密钥长度上获得显着收益。基于同构的密钥交换可以通过查尔兹，Jao和Soukharev发现的量子次指数隐藏移位算法来实现。虽然CSIDH使用超奇异曲线，但它类似于普通曲线的情况，因此该算法适用。在该提案中，作者建议选择一个参数，以确保安全性。在本文中，我们表明这些安全参数过于乐观。我们的结果依赖于两个步骤：第一，我们给出了一个更精确的复杂性分析的隐移位算法在这种情况下，这大大减少了计算的群体行动的数量;第二，我们展示了如何有效地计算这个群体行动。例如，我们表明，只有2 35量子等价的密钥交换是足够的，以打破128位的经典，64位的量子安全参数的建议，而不是2 62。当与NIST后量子调用中定义的安全级别相比时，建议的参数需要增加以达到目标级别：在AES-128安全级别下，至少需要1024位的基本字段，而不是512位（即公钥大小为128字节）。最后，我们扩展我们的分析，以普通的isquilitary计算，并表明，由德费奥，Kie Fücher和史密斯提出的一个实例，并预计将超过56位的量子安全可以打破在2 38量子评估的密钥交换。我们的攻击代价更大
. CSIDH is a recent proposal by Castryck, Lange, Martindale, Panny and Renes for post-quantum non-interactive key-exchange. It is similar in design to a scheme by Couveignes, Rostovtsev and Stolbunov, but it replaces ordinary elliptic curves by supersingular elliptic curves, in order to make significant gains in time and key lengths. Isogeny-based key-exchange on ordinary elliptic curves can be targeted by a quantum subexponential hidden shift algorithm found by Childs, Jao and Soukharev. Although CSIDH uses supersingular curves, it is analog to the case of ordinary curves, hence this algorithm applies. In the proposal, the authors suggest a choice of parameters that should ensure security against this. In this paper, we show that those security parameters were too optimistic. Our result relies on two steps: first, we give a more precise complexity analysis of the hidden shift algorithm in this context, which greatly reduces the number of group actions to compute; second, we show how to compute efficiently this group action. For example, we show that only 2 35 quantum equivalents of a key-exchange are sufficient to break the 128-bit classical, 64-bit quantum security parameters proposed, instead of 2 62 . When compared against levels of security defined in the NIST post-quantum call, the parameters proposed need to be increased in order to reach the target levels: at the AES-128 security level, a base field of at least 1024 bits is necessary, instead of 512 bits (i.e public key sizes of 128 bytes). Finally, we extend our analysis to ordinary isogeny computations, and show that an instance proposed by De Feo, Kieffer and Smith and expected to offer 56 bits of quantum security can be broken in 2 38 quantum evaluations of a key exchange. our attack more costly.