Fast 4 way vectorized ladder for the complete set of Montgomery curves

Year 2022, Volume: 11 Issue: 2, 12 - 24, 30.06.2022

Hüseyin Hışıl , Berkan Eğrice , Mert Yassı

Abstract

This paper introduces 4 way vectorization of Montgomery ladder on any Montgomery form elliptic curve. Our algorithm takes 2M^4+1S^4 (M^4: A vector of four field multiplications, S^4: A vector of four field squarings) per ladder step for variable-scalar variable-point multiplication. This paper also introduces new formulas for doing arithmetic over GF(2^255-19).

Keywords

Montgomery ladder, elliptic curves, genus 1, Kummer lines, Diffie-Hellman key exchange, public key cryptography.

Supporting Institution

Yasar University

Project Number

SRP-057

Thanks

We thank Erdem Alkım, Sedat Akleylek, and members of the Cyber Security and Cryptology Laboratory, Ondokuz Mayis University, for providing us access to OMU-i9, a Skylake i9-7900X machine. We developed the AVX-512 implementation on OMU-i9. The measurements relating to were both taken on OMU-i9.

References

• V. Miller, “Use of elliptic curves in cryptography,” in CRYPTO’85, ser. LNCS, vol. 218. Springer, 1985, pp. 417–426.
• N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203–209, January 1987.
• P. Montgomery, “Speeding the Pollard and elliptic curve methods of factorization,” Mathematics of computation, vol. 48, no. 177, pp.243–264, 1987.
• D. Bernstein, “Curve25519: New Diffie-Hellman speed records,” in Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, ser. Lecture Notes in Computer Science, M. Yung, Y. Dodis, A. Kiayias, and T. Malkin, Eds., vol. 3958. Springer, 2006, pp. 207–228. [Online]. Available: https://doi.org/10.1007/11745853 14
• E. Brier and M. Joye, “Weierstraß elliptic curves and side-channel attacks,” in Public Key Cryptography, 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, Paris, France, February 12-14, 2002, Proceedings, ser. Lecture Notes in Computer Science, D. Naccache and P. Paillier, Eds., vol. 2274. Springer, 2002, pp. 335–345. [Online]. Available: https://doi.org/10.1007/3-540-45664-3 24
• J. López and R. Dahab, “Fast multiplication on elliptic curves over GF(2m ) without precomputation,” in Cryptographic Hardware and Embedded Systems, First International Workshop, CHES’99, Worcester, MA, USA, August 12-13, 1999, Proceedings, ser. Lecture Notes in Computer Science, Ç. Koç and C. Paar, Eds., vol. 1717. Springer, 1999, pp. 316–327. [Online]. Available: https://doi.org/10.1007/3-540-48059-5 27
• W. Castryck, S. Galbraith, and R. R. Farashahi, “Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation,” Cryptology ePrint Archive, Report 2008/218, 2008, https://eprint.iacr.org/2008/218.
• D. J. Bernstein, T. Lange, and R. Rezaeian Farashahi, “Binary Edwards curves,” in Cryptographic Hardware and Embedded Systems – CHES 2008, E. Oswald and P. Rohatgi, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 244–265.
• R. Rezaeian Farashahi and S. G. Hosseini, “Differential addition on binary elliptic curves,” in Arithmetic of Finite Fields, S. Duquesne and S. Petkova-Nikova, Eds. Cham: Springer International Publishing, 2016, pp. 21–35.
• ——, “Differential addition on twisted Edwards curves,” in Information Security and Privacy - 22nd Australasian Conference, ACISP 2017, Auckland, New Zealand, July 3-5, 2017, Proceedings, Part II, ser. Lecture Notes in Computer Science, J. Pieprzyk and S. Suriadi, Eds., vol. 10343. Springer, 2017, pp. 366–378. [Online]. Available: https://doi.org/10.1007/978-3-319-59870-3 21
• D. Chudnovsky and G. Chudnovsky, “Sequences of numbers generated by addition in formal groups and new primality and factorization tests,” Advances in Applied Mathematics, vol. 7, no. 4, pp. 385–434, 1986.
• P. Gaudry, “Fast genus 2 arithmetic based on Theta functions,” Journal of Mathematical Cryptology (JMC), vol. 1, no. 3, pp. 243–265, 2007.
• P. Gaudry and D. Lubicz, “The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines,” Finite Fields and Their Applications, vol. 15, no. 2, pp. 246 – 260, 2009. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1071579708000804
• J. Renes and B. Smith, “qDSA: small and secure digital signatures with curve-based Diffie-Hellman key pairs,” in Advances in Cryptology - ASIACRYPT 2017, ser. Lecture Notes in Computer Science, T. Takagi and T. Peyrin, Eds., vol. 10625. Springer, 2017, pp. 273–302. [Online]. Available: https://doi.org/10.1007/978-3-319-70697-9 10
• P. Gaudry and E. Schost, “Genus 2 point counting over prime fields,” J. Symb. Comput., vol. 47, no. 4, pp. 368–400, 2012. [Online]. Available: http://dx.doi.org/10.1016/j.jsc.2011.09.003
• D. Bernstein, C. Chuengsatiansup, T. Lange, and P. Schwabe, “Kummer strikes back: New DH speed records,” in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, ser. Lecture Notes in Computer Science, P. Sarkar and T. Iwata, Eds., vol. 8873. Springer, 2014, pp. 317–337. [Online]. Available: https://doi.org/10.1007/978-3-662-45611-8 17
• T. Chou, “Sandy2x: New Curve25519 speed records,” in Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, ser. Lecture Notes in Computer Science, O. Dunkelman and L. Keliher, Eds., vol. 9566. Springer, 2015, pp. 145–160. [Online]. Available: https://doi.org/10.1007/978-3-319-31301-6
• S. Karati and P. Sarkar, “Kummer for genus one over prime order fields,” in Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II, ser. Lecture Notes in Computer Science, T. Takagi and T. Peyrin, Eds., vol. 10625. Springer, 2017, pp.3–32. [Online]. Available: https://doi.org/10.1007/978-3-319-70697-9 1
• D. Bernstein and T. Lange, Montgomery Curves and the Montgomery Ladder. Cambridge University Press, 2017, pp. 82–115.
• C. Costello and B. Smith, “Montgomery curves and their arithmetic - The case of large characteristic fields,” J. Cryptographic Engineering, vol. 8, no. 3, pp. 227–240, 2018. [Online]. Available: https://doi.org/10.1007/s13389-017-0157-6
• D. Bernstein and P. Schwabe, “NEON crypto,” in Cryptographic Hardware and Embedded Systems – CHES 2012, ser. Lecture Notes in Computer Science, E. Prouff and P. Schaumont, Eds., vol. 7428. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 320–339.
• K. Nath and P. Sarkar, “Efficient arithmetic in (pseudo-)mersenne prime order fields,” Cryptology ePrint Archive, Report 2018/985, 2018, https://eprint.iacr.org/2018/985.
• T. Oliveira, J. López, H. Hışıl, A. Faz-Hernández, and F. Rodrı́guez-Henrı́quez, “How to (pre–)compute a ladder – improving the performance of X25519 and X448,” in Selected Areas in Cryptography - SAC 2017 - 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers, ser. Lecture Notes in Computer Science, C. Adams and J. Camenisch, Eds., vol. 10719. Springer, 2017, pp. 172–191. [Online]. Available: https://doi.org/10.1007/978-3-319-72565-9 9
• A. Faz-Hernández, J. López, and R. Dahab, “High-performance implementation of elliptic curve cryptography using vector instructions,” ACM Trans. Math. Softw., vol. 45, no. 3, Jul. 2019. [Online]. Available: https://doi.org/10.1145/3309759
• K. Nath and P. Sarkar, “Efficient 4-way vectorizations of the Montgomery ladder,” Cryptology ePrint Archive, Report 2020/378, 2020, https://eprint.iacr.org/2020/378.
• T. Takagi and T. Peyrin, Eds., Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II, ser. Lecture otes in Computer Science, vol. 10625. Springer, 2017. [Online]. Available: https://doi.org/10.1007/978-3-319-70697-9