A Prime-Order Group with Complete Formulas from Even-Order Elliptic Curves
Authors
Thomas Pornin
Thomas Pornin
NCC Group, Canada
thomas dot pornin at nccgroup dot com
thomas dot pornin at nccgroup dot com
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.
[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.
[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.
[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.
[ALdV]
Tony Arcieri, Isis Lovecruft, and Henry de Valence.
The Ristretto group.
[Atk92]
A. Oliver L. Atkin.
Probabilistic primality testing (summary by F. Morain).
1992.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[CGN20]
Konstantinos Chalkias, François Garillot, and Valeria Nikolaenko.
Taming the many EdDSAs.
2020.
[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.
[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.
[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.
[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.
[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.
[dVGH+23]
Henry de Valence, Jack Grigg, Mike Hamburg, Isis Lovecruft, George Tankersley, and Filippo Valsorda.
The ristretto255 and decaf448 Groups.
2023.
[ECD23]
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[Jac29]
Carl Gustav Jacob Jacobi.
Fundamenta nova theoriae functionum ellipticarum.
1829.
[Knu69]
Donald E. Knuth.
The Art of Computer Programming, volume 2: Seminumerical Algorithms.
Addison-Wesley, first edition, 1969.
[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.
[NIS23]
Recommendations for discrete-logarithm based cryptography: elliptic curve domain parameters.
February 2023.
https://doi.org/10.6028/NIST.SP.800-186.
[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.
[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.
[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.
[Por20a]
Thomas Pornin.
Optimized binary GCD for modular inversion.
2020.
[Por20b]
Thomas Pornin.
Optimized lattice basis reduction in dimension 2, and fast schnorr and EdDSA signature verification.
2020.
[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.
[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.
[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.
[Was08]
Lawrence C. Washington.
Elliptic Curves: Number Theory and Cryptography.
Chapman & Hall, second edition, 2008.
[WW27]
Edmund T. Whittaker and George N. Watson.
A Course of Modern Analysis.
Cambridge University Press, fourth edition, 1927.
[x2523]
PDF
History
Submitted: 2024-01-05
Accepted: 2024-03-05
Published: 2024-04-09
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.
Citations
There is at least one citation.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.