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 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The code by Meyer et al. is available for download at https://zenon.cs.hs-rm.de/pqcrypto/constant-csidh-c-implementation. The commit ID of the version we used is 7fc2abdd, the latest version on 15 Feb, 2019.
References
Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. In: Proceedings of the 2013 ACM Conference on Computer and Communications Security, pp. 967–980 (2013)
Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. IACR Cryuptography ePrint Archive 2018/1059. https://eprint.iacr.org/2018/1059 (to appear at Eurocrypt 2019)
Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 395–427. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15
Cohen, H., Lenstra Jr., H.W.: Heuristics on class groups of number fields. Number Theory Noordwijkerhout 1983, 33–62 (1984)
Costello, C., Hisil, H.: A simple and compact algorithm for SIDH with arbitrary degree isogenies. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 303–329. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_11
Costello, C., Longa, P., Naehrig, M.: Efficient algorithms for supersingular isogeny Diffie-Hellman. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 572–601. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_21
Costello, C., Smith, B.: Montgomery curves and their arithmetic. J. Crypt. Eng. 8(3), 227–240 (2018)
Couveigne, J.-M.: Hard homogeneous spaces. IACR Cryptology ePrint Archive 2006/291. https://eprint.iacr.org/2006/291
De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 365–394. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_14
Delfs, C., Galbraith, S.D.: Computing isogenies between supersingulrar elliptic curves over \({\mathbb{F}}_{p}\). Des. Codes Crypt. 78(2), 425–440 (2016)
Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_3
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2
Jalali, A., Azarderakhsh, R., Kermani, M.M., Jao, D.: Towards optimized and constant-time CSIDH on embedded devices. In: Polian, I., Stöttinger, M. (eds.) COSADE 2019. LNCS, vol. 11421, pp. 215–231. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16350-1_12. https://eprint.iacr.org/2019/297
Jao, D., et al.: Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Cryptography Standardization project. https://sike.org
Meyer, M., Campos, F., Reith, S.: On Lions and Elligators: an efficient constatn-time implementation of CSIDH. IACR Cryptology ePrint Archive 2018/1198. https://eprint.iacr.org/2018/1198 (to appear at PQCrypto 2019)
Meyer, M., Reith, S.: A faster way to the CSIDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 137–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_8
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 24–264 (1987)
National Institute of Standards and Technology (NIST): NIST Post-Quantum Cryptography Standardization (2016). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: A faster constant-time algorithm of CSIDH keeping two points IACR Cryuptography ePrint Archive 2019/353. https://eprint.iacr.org/2019/353
Petit, C.: Faster algorithms for isogeny problems using torsion point images. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 330–353. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_12
Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. IACR Cryptology ePrint Archive 2006/145. https://eprint.iacr.org/2006/145
Siegel, C.: Über die Classenzahl quadratischer Zahlkörper. Acta Arith. 1(1), 83–86 (1935)
Stolbunov, A.: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. Math. Commun. 4(2), 215–235 (2010)
Acknowledgment
This work was supported by JST CREST Grant Number JPMJCR14D6, Japan.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T. (2019). (Short Paper) A Faster Constant-Time Algorithm of CSIDH Keeping Two Points. In: Attrapadung, N., Yagi, T. (eds) Advances in Information and Computer Security. IWSEC 2019. Lecture Notes in Computer Science(), vol 11689. Springer, Cham. https://doi.org/10.1007/978-3-030-26834-3_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-26834-3_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26833-6
Online ISBN: 978-3-030-26834-3
eBook Packages: Computer ScienceComputer Science (R0)