Cryptology ePrint Archive: Report 2019/353

A Faster Constant-time Algorithm of CSIDH keeping Two Points

Hiroshi Onuki and Yusuke Aikawa and Tsutomu Yamazaki and Tsuyoshi Takagi

Abstract: 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 in 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.23% 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.8 million clock cycles, which is about 29.03% faster than that of Meyer et al. and confirms the above reduction ratio in our cost evaluation.

Category / Keywords: public-key cryptography / CSIDH, post-quantum cryptography, Isogeny-based cryptography, constant-time implementation, supersingular elliptic curve isogenies

Date: received 1 Apr 2019, last revised 5 Jun 2019

Contact author: onuki at mist i u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Note: This paper is a full version of the paper of the same name to appear at IWSEC 2019.

Version: 20190606:025404 (All versions of this report)

Short URL: ia.cr/2019/353


[ Cryptology ePrint archive ]