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

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.

References

1. V. Miller, “Use of elliptic curves in cryptography,” in CRYPTO’85, ser. LNCS, vol. 218. Springer, 1985, pp. 417–426.
2. N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203–209, January 1987.
3. P. Montgomery, “Speeding the Pollard and elliptic curve methods of factorization,” Mathematics of computation, vol. 48, no. 177, pp.243–264, 1987.
4. 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
5. 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
6. 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
7. 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.
8. 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.

9. 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.
10. ——, “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
11. 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.
12. P. Gaudry, “Fast genus 2 arithmetic based on Theta functions,” Journal of Mathematical Cryptology (JMC), vol. 1, no. 3, pp. 243–265, 2007.
13. 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
14. 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
15. 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
16. 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
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
18. 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
19. D. Bernstein and T. Lange, Montgomery Curves and the Montgomery Ladder. Cambridge University Press, 2017, pp. 82–115.
20. 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
21. 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.
22. 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.
23. 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
24. 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
25. 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.
26. 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