Summary
|
For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE. |
|
A Constant-Time Algorithm of CSIDH Keeping Two Points Hiroshi ONUKI Yusuke AIKAWA Tsutomu YAMAZAKI Tsuyoshi TAKAGI Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E103-A No.10 pp.1174-1182 Publication Date: 2020/10/01 Online ISSN: 1745-1337 DOI: 10.1587/transfun.2019DMP0008 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: cryptography Keyword: CSIDH, post-quantum cryptography, isogeny-based cryptography, constant-time implementation, supersingular elliptic curve isogenies, Full Text: FreePDF(1.6MB) Summary: 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 evaluate the costs of our implementation and that of Meyer et al. in terms of the number of operations on a finite prime field. Our evaluation shows that our constant-time implementation of CSIDH reduces the calculation cost by 28% compared with the implementation by Mayer et al. We also implemented our algorithm by extending the implementation in C of Meyer et al. (originally from Castryck et al.). Then our implementation achieved 152 million clock cycles, which is about 29% faster than that of Meyer et al. and confirms the above reduction ratio in our cost evaluation. | ||||||||||
| ||||||||||