A Constant-Time Algorithm of CSIDH Keeping Two Points

Hiroshi ONUKI; Yusuke AIKAWA; Tsutomu YAMAZAKI; Tsuyoshi TAKAGI

doi:10.1587/transfun.2019DMP0008

IEICE TRANSACTIONS on Fundamentals

Open Access
A Constant-Time Algorithm of CSIDH Keeping Two Points

Hiroshi ONUKI, Yusuke AIKAWA, Tsutomu YAMAZAKI, Tsuyoshi TAKAGI

Full Text Views

42

Cite this

Free PDF (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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.10 pp.1174-1182

Publication Date: 2020/10/01

Publicized

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

Authors

Hiroshi ONUKI
  The University of Tokyo
Yusuke AIKAWA
  the Mitsubishi Electric Corporation
Tsutomu YAMAZAKI
  Kyushu University
Tsuyoshi TAKAGI
  The University of Tokyo

Keyword

CSIDH, post-quantum cryptography, isogeny-based cryptography, constant-time implementation, supersingular elliptic curve isogenies

Cite this

Copy

Hiroshi ONUKI, Yusuke AIKAWA, Tsutomu YAMAZAKI, Tsuyoshi TAKAGI, "A Constant-Time Algorithm of CSIDH Keeping Two Points" in IEICE TRANSACTIONS on Fundamentals, vol. E103-A, no. 10, pp. 1174-1182, October 2020, doi: 10.1587/transfun.2019DMP0008.
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019DMP0008/_p

Copy

@ARTICLE{e103-a_10_1174,
author={Hiroshi ONUKI, Yusuke AIKAWA, Tsutomu YAMAZAKI, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Constant-Time Algorithm of CSIDH Keeping Two Points},
year={2020},
volume={E103-A},
number={10},
pages={1174-1182},
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 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.},
keywords={},
doi={10.1587/transfun.2019DMP0008},
ISSN={1745-1337},
month={October},}

Copy

TY - JOUR
TI - A Constant-Time Algorithm of CSIDH Keeping Two Points
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1174
EP - 1182
AU - Hiroshi ONUKI
AU - Yusuke AIKAWA
AU - Tsutomu YAMAZAKI
AU - Tsuyoshi TAKAGI
PY - 2020
DO - 10.1587/transfun.2019DMP0008
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2020
AB - 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.
ER -

IEICE TRANSACTIONS on Fundamentals