Abstract
CSIDH is a recent post-quantum key establishment protocol based on constructing isogenies between supersingular elliptic curves. Several recent works give constant-time implementations of CSIDH along with some optimizations of the ideal class group action evaluation algorithm, including the SIMBA technique of Meyer et al. and the “two-point method” of Onuki et al. A recent work of Cervantes-Vázquez et al. details a number of improvements to the works of Meyer et al. and Onuki et al. Several of these optimizations—in particular, the choice of ordering of the primes, the choice of SIMBA partition and strategies, and the choice of bound vector which defines the secret keyspace—have been made in an ad hoc fashion, and so while they yield performance improvements it has not been clear whether these choices could be improved upon, or how to do so. In this work we present a framework for improving these optimizations using (respectively) linear programming, dynamic programming, and convex programming techniques. Our framework is applicable to any CSIDH security level, to all currently-proposed paradigms for computing the class group action, and to any choice of model for the underlying curves. Using our framework we find improved parameter sets for the two major methods of computing the group action: in the case of the implementation of Meyer et al. we obtain a 13.04% speedup without applying the further optimizations proposed by Cervantes-Vázquez et al., while for that of Cervantes-Vázquez et al. under the two-point method we obtain a speedup of 5.23%, giving the fastest constant-time implementation of CSIDH to date.
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
References
Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Meth. Softw. 24(4–5), 597–634 (2009)
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
Cervantes-Vázquez, D., Chenu, M., Chi-Domínguez, J.-J., De Feo, L., Rodríguez-Henríquez, F., Smith, B.: Stronger and faster side-channel protections for CSIDH. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 173–193. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30530-7_9
Cohen, H., Lenstra, H.W.: Heuristics on class groups of number fields. In: Jager, H. (ed.) Number Theory Noordwijkerhout 1983. LNM, vol. 1068, pp. 33–62. Springer, Heidelberg (1984). https://doi.org/10.1007/BFb0099440
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
Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291
Czyzyk, J., Mesnier, M.P., Moré, J.J.: The NEOS server. IEEE J. Comput. Sci. Eng. 5(3), 68–75 (1998)
De Feo, L., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Crypt. 8(3), 209–247 (2014)
Dolan, E.D.: The NEOS server 4.0 administrative guide. Technical Memorandum ANL/MCS-TM-250, Mathematics and Computer Science Division, Argonne National Laboratory (2001)
Gropp, W., Moré, J.J.: Optimization environments and the NEOS server. In: Buhman, M.D., Iserles, A., (eds.) Approximation Theory and Optimization, pp. 167–182. Cambridge University Press, New York (1997)
Hutchinson, A., Karabina, K.: Constructing canonical strategies for parallel implementation of isogeny based cryptography. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 169–189. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_10
Hutchinson, A., LeGrow, J., Koziel, B., Azarderakhsh, R.: Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors. Cryptology ePrint Archive, Report 2019/1121 (2019). https://eprint.iacr.org/2019/1121
Jalali, A., Azarderakhsh, R., Kermani, M.M., Jao, D.: Towards optimized and constant-time CSIDH on embedded devices. Cryptology ePrint Archive, Report 2019/297 (2019). https://eprint.iacr.org/2019/297
Meyer, M., Campos, F., Reith, S.: On lions and elligators: an efficient constant-time implementation of CSIDH. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 307–325. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_17
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
Moriya, T., Onuki, H., Takagi, T.: How to construct CSIDH on edwards curves. Cryptology ePrint Archive, Report 2019/843 (2019). https://eprint.iacr.org/2019/843
Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: (Short Paper) a faster constant-time algorithm of CSIDH keeping two points. In: Attrapadung, N., Yagi, T. (eds.) IWSEC 2019. LNCS, vol. 11689, pp. 23–33. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26834-3_2
Peikert, C.: He gives C-Sieves on the CSIDH. Cryptology ePrint Archive, Report 2019/725 (2019). https://eprint.iacr.org/2019/725
Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). https://eprint.iacr.org/2006/145
Acknowledgements
The authors would like to thank the reviewers for their helpful comments. This work is supported in parts by NSF CNS-1801341, NSF GRFP-1939266, and NIST-60NANB17D184.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Hutchinson, A., LeGrow, J., Koziel, B., Azarderakhsh, R. (2020). Further Optimizations of CSIDH: A Systematic Approach to Efficient Strategies, Permutations, and Bound Vectors. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds) Applied Cryptography and Network Security. ACNS 2020. Lecture Notes in Computer Science(), vol 12146. Springer, Cham. https://doi.org/10.1007/978-3-030-57808-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-030-57808-4_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57807-7
Online ISBN: 978-3-030-57808-4
eBook Packages: Computer ScienceComputer Science (R0)