LadderPrime: Exception-Free, Twist-Insensitive, and Constant-Time Ladder for Prime-Order Elliptic Curves

Year 2026, Volume: 15 Issue: 1, 48 - 65, 19.03.2026

Hüseyin Hışıl , Nuri Furkan Pala

https://doi.org/10.55859/ijiss.1867564

https://izlik.org/JA62UW49TJ

Abstract

We introduce LadderPrime, an exception-free scalar-point multiplication algorithm, which works on the Kummer line of an elliptic curve given by the equation B*y^2=x^3+A*x^2+ax+b. LadderPrime operates only on two coordinates and computes the correct output for all input points, all scalars, and all elliptic curves of characteristic > 2. This is achieved by an alternative set of differential-addition formulas which can handle not only generic points but also the problematic point (0 : Z) for Montgomery ladder. The main structure of LadderPrime is analogous to the scalar-point multiplication in Bernstein’s X25519 Diffie-Hellman key exchange (DH) specification. Unlike, X25519 which uses the non-prime order (h = 8) elliptic Curve25519, LadderPrime is able to work with prime order (h = 1) (and non-prime order) elliptic curves. When used with a prime order elliptic curve, LadderPrime does not need the initial raising of base point to a prime order subgroup. In other words, LadderPrime eliminates the need for masking lower bits of the scalar. LadderPrime also eliminates the need for Hamburg’s "Decaf" (CRYPTO 2015) and later refined "Ristretto" methods. Essential cryptographic protocols such as DH and qDSA can be instantiated over LadderPrime.

Keywords

elliptic curve cryptography , Diffie-Hellman key exchange , twist-secure curves , Montgomery ladder , Montgomery curves , Kummer line of elliptic curves , finite fields , SIMD computing

References

• V. S. Miller, “Use of elliptic curves in cryptography,” in CRYPTO’85, ser. LNCS, vol. 218. Springer, 1986, pp. 417– 426.
• N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, no. 177, pp. 203–209, January 1987. 61 INTERNATIONAL JOURNAL OF INFORMATION SECURITY SCIENCE N. Pala et al., Vol.15, No.1, pp. 48-65
• H. Cohen, A. Miyaji, and T. Ono, “Efficient elliptic curve exponentiation using mixed coordinates,” in Advances in Cryptology — ASIACRYPT’98, K. Ohta and D. Pei, Eds. Berlin, Heidelberg: Springer 1998, pp. 51–65.
• A. J. Menezes, P. C. V. Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography. Boca Raton, FL, USA: CRC Press, Inc., 1996.
• H. Cohen and G. Frey, Eds., Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.
• J.-S. Coron, “Resistance against differential power analysis for elliptic curve cryptosystems,” in CHES ’99, ser. LNCS, vol. 1717. Springer, 1999, pp. 292–302.
• P. C. Kocher, J. Jaffe, and B. Jun, “Differential power analysis,” in CRYPTO ’99, ser. LNCS, vol. 1666. Springer, 1999, pp. 388–397.
• D. J. Bernstein and T. Lange, “Faster addition and doubling on elliptic curves,” in ASIACRYPT 2007, ser. LNCS, vol. 4833. Springer, 2007, pp. 29–50.
• H. Hisil, K. K.-H. Wong, G. Carter, and E. Dawson, “Jacobi quartic curves revisited,” in Information Security and Privacy, C. Boyd and J. González Nieto, Eds. Berlin, Heidelberg: Springer, 2009, pp. 452–468.
• H. Hisil, “Elliptic curves, group law, and efficient computation,” Ph.D. dissertation, Queensland University of Technology, 2010.
• D. J. Bernstein, C. Chuengsatiansup, D. Kohel, and T. Lange, “Twisted hessian curves,” in Progress in Cryptology – LATINCRYPT 2015, K. Lauter and F. Rodríguez-Henríquez, Eds. Cham: Springer International Publishing, 2015, pp. 269– 294.
• J. Renes, C. Costello, and L. Batina, “Complete addition formulas for prime order elliptic curves,” in Proceedings, Part I, of the 35th Annual International Conference on Advances in Cryptology — EUROCRYPT 2016 - Volume 9665. Berlin, Heidelberg: Springer-Verlag, 2016, p. 403–428.
• D. J. Bernstein, “Curve25519: New Diffie-Hellman speed records,” in Public Key Cryptography - PKC 2006, M. Yung, Y. Dodis, A. Kiayias, and T. Malkin, Eds. Berlin, Heidelberg: Springer, 2006, pp. 207–228.
• P. Schwabe and A. Sprenkels, “The complete cost of cofactor h = 1,” in Progress in Cryptology – INDOCRYPT 2019: 20th International Conference on Cryptology in India, Hyderabad, India, December 15–18, 2019, Proceedings. Berlin, Heidelberg: Springer-Verlag, 2019, p. 375–397.
• C. Cremers and D. Jackson, “Prime, order please! revisiting small subgroup and invalid curve attacks on protocols using Diffie-Hellman,” in 2019 IEEE 32nd Computer Security Foundations Symposium (CSF). Los Alamitos, CA, USA: IEEE Computer Society, Jun 2019, pp. 78–93.
• J. Renes and B. Smith, “qDSA: Small and secure digital signatures with curve-based Diffie-Hellman key pairs,” in Advances in Cryptology - ASIACRYPT 2017 in Lecture Notes in Computer Science, T. Takagi and T. Peyrin, Eds., vol. 10625. Springer, 2017, pp. 273–302.
• É. Brier and M. Joye, “Weierstraß elliptic curves and side- channel attacks,” in Public Key Cryptography, D. Naccache and P. Paillier, Eds. Berlin, Heidelberg: Springer, 2002, pp. 335– 345.
• C. G. J. Jacobi, Fundamenta nova theoriae functionum ellipticarum. Sumtibus fratrumBorntraeger, Königsberg, 1829.
• P. L. Montgomery, “Speeding the Pollard and elliptic curve methods of factorization,” Mathematics of Computation, vol. 48, no. 177, pp. 243–264, 1987.
• P. Gaudry and D. Lubicz, “The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines,” Finite Fields Appl., vol. 15, no. 2, pp. 246–260, April 2009.
• S. Karati and P. Sarkar, “Kummer for genus one over prime order fields,” in Advances in Cryptology – ASIACRYPT 2017, T. Takagi and T. Peyrin, Eds. Cham: Springer International Publishing, 2017, pp. 3–32.
• D. J. Bernstein, “Elliptic vs. hyperelliptic, part I,” Talk at ECC, 2006. [Online]. Available: https://cr.yp.to/talks/2006.09. 20/slides.pdf.
• H. Hisil and J. Renes, “On Kummer lines with full rational 2-torsion and their usage in cryptography,” ACM Trans. Math. Softw., vol. 45, no. 4, December 2019.
• M. Stam, “Speeding up subgroup cryptosystems.” Ph.D. dissertation, Technische Universiteit Eindhoven, 2003.
• D. J. Bernstein, L. De Feo, A. Leroux, and B. Smith, “Faster computation of isogenies of large prime degree,” ser. The Open Book Series, vol. 4. Mathematical Sciences Publishers (MSP), 2020, pp. 39–55.
• G. B. Agnew, R. C. Mullin, and S. A. Vanstone, “An implementation of elliptic curve cryptosystems over F2155,” IEEE Journal on Selected areas in Communications, vol. 11, no. 5, pp. 804–813, 1993.
• S. Vanstone, R. Mullin, A. Antipa, and R. Gallant, “Accelerated finite field operations on an elliptic curve,” August 2004, uS Patent 6,782,100.
• J. López and R. Dahab, “Fast multiplication on elliptic curves over GF(2m) without precomputation,” in Cryptographic Hardware and Embedded Systems, Ç. K. Koç and C. Paar, Eds. Berlin, Heidelberg: Springer, 1999, pp. 316–327.
• M. Stam, “On Montgomery-like representations for elliptic curves over GF(2k),” in Public Key Cryptography — PKC 2003, Y. G. Desmedt, Ed. Berlin, Heidelberg: Springer, 2002, pp. 240–254.
• P. Barreto, “Tweet 2017,” [Online]. Available: https://twitter. com/pbarreto/status/869103226276134912
• H. Hisil, B. Egrice, and M. Yassi, “Fast 4 way vectorized ladder for the complete set of Montgomery curves,” International Journal of Information Security Science, vol. 11, no. 2, pp. 12– 24, 2022.
• K. Nath and P. Sarkar, “Efficient 4-way vectorizations of the Montgomery ladder,” IEEE Trans. Comput., vol. 71, no. 3, pp. 712–723, Mar. 2022. 62 INTERNATIONAL JOURNAL OF INFORMATION SECURITY SCIENCE N. Pala et al., Vol.15, No.1, pp. 48-65
• K. Nath and P. Sarkar, “Kummer versus Montgomery face-off over prime order fields,” vol. 48, no. 2, May 2022.
• M. Hamburg, “Faster Montgomery and double-add ladders for short Weierstrass curves,” Transactions on Cryptographic Hardware and Embedded Systems (TCHES), vol. 2020, no. 4, pp. 189–208, 2020.
• D. J. Bernstein and T. Lange, “Safecurves: choosing safe curves for elliptic-curve cryptography,” [Online]. Available: https://safecurves.cr.yp.to
• B. Egrice and H. Hisil, “p261: A Karatsuba-friendly prime for fast elliptic curve arithmetic,” in Information Security in a Connected World: Celebrating the Life and Work of Ed Dawson, C. Boyd, R. Safavi-Naini, and L. Simpson, Eds. Cham: Springer Nature Switzerland, 2025, pp. 109–123.
• C. Costello, “ECC2014 – Chennai, India – Invited Talk “Selecting elliptic curves for cryptography: an efficiency and security analysis”,” [Online]. Available: https://www.imsc.res. in/~ecc14/slides/costello.pdf
• W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
• M. Hamburg, “Decaf: Eliminating cofactors through point compression,” in Advances in Cryptology – CRYPTO 2015 Gennaro, R., Robshaw, M. (eds.), ser. LNCS, vol. 9215. Springer, 2015, pp. 705–723.
• H. de Valence, I. Lovecruft, and T. Arcieri, “The Ristretto group,” https://ristretto.group/ristretto.html, 2019.