(Short Paper) A Faster Constant-Time Algorithm of CSIDH Keeping Two Points
(Short Paper) A Faster Constant-Time Algorithm of CSIDH Keeping Two Points
复制标题
（短论文）一种更快的保持两点的CSIDH恒定时间算法
DOI：
10.1007/978-3-030-26834-3_2
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
T. Takagi
中科院分区：
文献类型：
--
作者：
Hiroshi Onuki;Yusuke Aikawa;T. Yamazaki;T. Takagi
在2018年的ASIACRYPT上，Castryck，Lange，Martindale，Panny和Renes提出了CSIDH，这是一种基于椭圆曲线之间同源性的密钥交换协议，是后量子密码学的候选者。然而，Castryck等人的实现不是恒定时间的。具体地说，一部分秘密密钥可以通过侧信道攻击恢复。最近，Meyer，Campos和Reith提出了一种CSIDH的恒定时间实现，通过引入伪同构并仅从非负整数的区间中获取秘密指数。它们的非负区间使得它们实现CSIDH的计算成本是标准（可变时间）实现CSIDH的最坏情况的两倍。在本文中，我们提出了一个更有效的常数时间算法，需要秘密指数从对称的零的间隔。为了使用这些区间，我们需要在椭圆曲线上保持两个扭点，并计算这些点。我们通过扩展Meyer等人的C语言实现了我们的算法（最初来自Castryck等人）。然后，我们的实现实现了1.528亿个时钟周期，这比Meyer等人的实现快了29.03%。
At ASIACRYPT 2018, Castryck, Lange, Martindale, Panny and Renes proposed CSIDH, which is a key-exchange protocol based on isogenies between elliptic curves, and a candidate for post-quantum cryptography. However, the implementation by Castryck et al. is not constant-time. Specifically, a part of the secret key could be recovered by the side-channel attacks. Recently, Meyer, Campos, and Reith proposed a constant-time implementation of CSIDH by introducing dummy isogenies and taking secret exponents only from intervals of non-negative integers. Their non-negative intervals make the calculation cost of their implementation of CSIDH twice that of the worst case of the standard (variable-time) implementation of CSIDH. In this paper, we propose a more efficient constant-time algorithm that takes secret exponents from intervals symmetric with respect to the zero. For using these intervals, we need to keep two torsion points on an elliptic curve and calculation for these points. We implemented our algorithm by extending the implementation in C of Meyer et al. (originally from Castryck et al.). Then our implementation achieved 152.8 million clock cycles, which is about 29.03% faster than that of Meyer et al.