Communications in Cryptology IACR CiC

A Prime-Order Group with Complete Formulas from Even-Order Elliptic Curves

Authors

Thomas Pornin
Thomas Pornin ORCID
NCC Group, Canada
thomas dot pornin at nccgroup dot com
Keywords: elliptic curves complete formulas double-odd curves

Abstract

This paper describes a generic methodology for obtaining unified, and then complete formulas for a prime-order group abstraction homomorphic to a subgroup of an elliptic curve with even order. The method is applicable to any curve with even order, in finite fields of both even and odd characteristic; it is most efficient on curves with order equal to 2 modulo 4, dubbed "double-odd curves". In large characteristic fields, we obtain doubling formulas with cost as low as 1M + 5S, and the resulting group allows building schemes such as signatures that outperform existing fast solutions, e.g. Ed25519. In binary fields, the obtained formulas are not only complete but also faster than previously known incomplete formulas; we can sign and verify in as low as 18k and 27k cycles on x86 CPUs, respectively.

References

[AA22]
Marius A. Aardal and Diego F. Aranha. 2D-GLS: faster and exception-free scalar multiplication in the GLS254 binary curve. 2022.
Google Scholar ePrint
[ABG+06]
Adrian Antipa, Daniel R. L. Brown, Robert Gallant, Rob Lambert, René Struik, and Scott A. Vanstone. Accelerated verification of ECDSA signatures. In Bart Preneel and Stafford Tavares, editors, SAC 2005, volume 3897 of LNCS, 307–318. August 2006. Springer, Heidelberg. https://doi.org/10.1007/11693383_21.
Google Scholar ePrint
[AHST23]
Diego F. Aranha, Benjamin Salling Hvass, Bas Spitters, and Mehdi Tibouchi. Faster constant-time evaluation of the Kronecker symbol with application to elliptic curve hashing. In ACM CCS 2023, 3228–3238. November 2023. ACM Press. https://doi.org/10.1145/3576915.3616597.
Google Scholar ePrint
[AKR12]
Christophe Arene, David Kohel, and Christophe Ritzenthaler. Complete addition laws on abelian varieties. LMS Journal of Computation and Mathematics, 15:308–316, 2012. https://doi.org/10.1112/S1461157012001027.
Google Scholar ePrint
[ALdV]
Tony Arcieri, Isis Lovecruft, and Henry de Valence. The Ristretto group.
Google Scholar ePrint
[Atk92]
A. Oliver L. Atkin. Probabilistic primality testing (summary by F. Morain). 1992.
Google Scholar ePrint
[BBJ+08]
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. Twisted Edwards curves. In Serge Vaudenay, editor, AFRICACRYPT 08, volume 5023 of LNCS, 389–405. June 2008. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-68164-9_26.
Google Scholar ePrint
[BDL+11]
Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. In Bart Preneel and Tsuyoshi Takagi, editors, CHES 2011, volume 6917 of LNCS, 124–142. September / October 2011. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-23951-9_9.
Google Scholar ePrint
[BJ03]
Olivier Billet and Marc Joye. The Jacobi model of an elliptic curve and side-channel analysis. In Marc Fossorier, Tom Høholdt, and Alain Poli, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 2643 of LNCS, 34–42. April 2003. Springer, Heidelberg. https://doi.org/10.1007/3-540-44828-4_5.
Google Scholar ePrint
[BL07]
Daniel J. Bernstein and Tanja Lange. Faster addition and doubling on elliptic curves. In Kaoru Kurosawa, editor, ASIACRYPT 2007, volume 4833 of LNCS, 29–50. December 2007. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_3.
Google Scholar ePrint
[BY19]
Daniel J. Bernstein and Bo-Yin Yang. Fast constant-time gcd computation and modular inversion. IACR TCHES, 2019(3):340–398, 2019. https://doi.org/10.13154/tches.v2019.i3.340-398.
Google Scholar ePrint
[CC86]
David V. Chudnovsky and Gregory V. Chudnovsky. Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Advances in Applied Mathematics, 7(4):385–434, 1986. https://doi.org/10.1016/0196-8858(86)90023-0.
Google Scholar ePrint
[CD20]
Wouter Castryck and Thomas Decru. CSIDH on the surface. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, 111–129. June 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-44223-1_7.
Google Scholar ePrint
[CGN20]
Konstantinos Chalkias, François Garillot, and Valeria Nikolaenko. Taming the many EdDSAs. 2020.
Google Scholar ePrint
[CJ19]
Cas Cremers and Dennis Jackson. Prime, order please! Revisiting small subgroup and invalid curve attacks on protocols using Diffie-Hellman. In Stephanie Delaune and Limin Jia, editors, CSF 2019 Computer Security Foundations Symposium, 78–93. June 2019. IEEE Computer Society Press. https://doi.org/10.1109/CSF.2019.00013.
Google Scholar ePrint
[CLM+18]
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: an efficient post-quantum commutative group action. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part III, volume 11274 of LNCS, 395–427. December 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-03332-3_15.
Google Scholar ePrint
[DH76]
Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. https://doi.org/10.1109/TIT.1976.1055638.
Google Scholar ePrint
[DIK06]
Christophe Doche, Thomas Icart, and David R. Kohel. Efficient scalar multiplication by isogeny decompositions. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, PKC 2006, volume 3958 of LNCS, 191–206. April 2006. Springer, Heidelberg. https://doi.org/10.1007/11745853_13.
Google Scholar ePrint
[Duq07]
Sylvain Duquesne. Improving the arithmetic of elliptic curves in the Jacobi model. Information Processing Letters, 104(3):101–105, 2007. https://doi.org/10.1016/j.ipl.2007.05.012.
Google Scholar ePrint
[dVGH+23]
Henry de Valence, Jack Grigg, Mike Hamburg, Isis Lovecruft, George Tankersley, and Filippo Valsorda. The ristretto255 and decaf448 Groups. 2023.
Google Scholar ePrint
[ECD23]
Digital Signature Standard (DSS). February 2023. https://doi.org/10.6028/NIST.FIPS.186-5.
Google Scholar ePrint
[GHS02]
Pierrick Gaudry, Florian Hess, and Nigel P. Smart. Constructive and destructive facets of Weil descent on elliptic curves. Journal of Cryptology, 15(1):19–46, January 2002. https://doi.org/10.1007/s00145-001-0011-x.
Google Scholar ePrint
[GLS09]
Steven D. Galbraith, Xibin Lin, and Michael Scott. Endomorphisms for faster elliptic curve cryptography on a large class of curves. In Antoine Joux, editor, EUROCRYPT 2009, volume 5479 of LNCS, 518–535. April 2009. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-01001-9_30.
Google Scholar ePrint
[GLV01]
Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, 190–200. August 2001. Springer, Heidelberg. https://doi.org/10.1007/3-540-44647-8_11.
Google Scholar ePrint
[Ham15]
Mike Hamburg. Decaf: eliminating cofactors through point compression. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, 705–723. August 2015. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-47989-6_34.
Google Scholar ePrint
[HKM09]
Darrel Hankerson, Koray Karabina, and Alfred Menezes. Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields. IEEE Transactions on Computers, 58(10):1411–1420, 2009. https://doi.org/10.1109/TC.2009.61.
Google Scholar ePrint
[HWCD08]
Hüseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards curves revisited. In Josef Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, 326–343. December 2008. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-89255-7_20.
Google Scholar ePrint
[HWCD09]
Hüseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Jacobi quartic curves revisited. In Colin Boyd and Juan Manuel González Nieto, editors, ACISP 09, volume 5594 of LNCS, 452–468. July 2009. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-02620-1_31.
Google Scholar ePrint
[IT88]
Toshiya Itoh and Shigeo Tsujii. A fast algorithm for computing multiplicative inverses in GF($2^m$) using normal bases. Inf. Comput., 78(3):171–177, 1988. https://doi.org/10.1016/0890-5401(88)90024-7.
Google Scholar ePrint
[Jac29]
Carl Gustav Jacob Jacobi. Fundamenta nova theoriae functionum ellipticarum. 1829.
Google Scholar ePrint
[Knu69]
Donald E. Knuth. The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, first edition, 1969.
Google Scholar ePrint
[Knu99]
Erik Woodward Knudsen. Elliptic scalar multiplication using point halving. In Kwok-Yan Lam, Eiji Okamoto, and Chaoping Xing, editors, ASIACRYPT'99, volume 1716 of LNCS, 135–149. November 1999. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-48000-6_12.
Google Scholar ePrint
[NIS23]
Recommendations for discrete-logarithm based cryptography: elliptic curve domain parameters. February 2023. https://doi.org/10.6028/NIST.SP.800-186.
Google Scholar ePrint
[NSW09]
Gregory Neven, Nigel P. Smart, and Bogdan Warinschi. Hash function requirements for Schnorr signatures. J. Math. Cryptol., 3(1):69–87, 2009. https://doi.org/10.1515/JMC.2009.004.
Google Scholar ePrint
[OLAR13]
Thomaz Oliveira, Julio Cesar López-Hernández, Diego F. Aranha, and Francisco Rodríguez-Henríquez. Lambda coordinates for binary elliptic curves. In Guido Bertoni and Jean-Sébastien Coron, editors, CHES 2013, volume 8086 of LNCS, 311–330. August 2013. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-40349-1_18.
Google Scholar ePrint
[OLAR14]
Thomaz Oliveira, Julio Cesar López-Hernández, Diego F. Aranha, and Francisco Rodríguez-Henríquez. Two is the fastest prime: lambda coordinates for binary elliptic curves. Journal of Cryptographic Engineering, 4(1):3–17, April 2014. https://doi.org/10.1007/s13389-013-0069-z.
Google Scholar ePrint
[Por20a]
Thomas Pornin. Optimized binary GCD for modular inversion. 2020.
Google Scholar ePrint
[Por20b]
Thomas Pornin. Optimized lattice basis reduction in dimension 2, and fast schnorr and EdDSA signature verification. 2020.
Google Scholar ePrint
[RCB16]
Joost Renes, Craig Costello, and Lejla Batina. Complete addition formulas for prime order elliptic curves. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, 403–428. May 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-49890-3_16.
Google Scholar ePrint
[Sch90]
Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, 239–252. August 1990. Springer, Heidelberg. https://doi.org/10.1007/0-387-34805-0_22.
Google Scholar ePrint
[V\'71]
Jacques Vélu. Isogénies entre courbes elliptiques. Comptes Rendus de l'Académie des Sciences, Série A, 273(4):238–241, 1971.
Google Scholar ePrint
[Was08]
Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography. Chapman & Hall, second edition, 2008.
Google Scholar ePrint
[WW27]
Edmund T. Whittaker and George N. Watson. A Course of Modern Analysis. Cambridge University Press, fourth edition, 1927.
Google Scholar ePrint
[x2523]
libx25519, version 2023.06.30. 2023.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/akmp-4c2h
History
Submitted: 2024-01-05
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Thomas Pornin, A Prime-Order Group with Complete Formulas from Even-Order Elliptic Curves. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/akmp-4c2h.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.