Abstract
Since Edwards curves were introduced in elliptic curve cryptography, they have attracted a lot of attention. The twisted Edwards curves are defined by the equation \(E_{a,d}: ax^2 + y^2 = 1 + d x^2y^2\). Twisted Edwards curve is the state-of-the-art for \(a=-1\), and even for \(a \ne -1\). E448 and Edwards448 are NIST standard curve in 2023 and TLS 1.3 standard curve in 2018. They both can be converted to \(d=-1\), but can not be converted to \(a=-1\) through isomorphism. The motivation of using a curve with \(d=-1\) is that we want to improve the efficiency of E448, and Edwards448, especially to achieve a great saving in terms of the number of field multiplications (\({{\textbf {M}}}\)) and field squarings (\({{\textbf {S}}}\)). We propose new explicit formulas for point operations on these curves. Our full point addition only requires \(8 {{\textbf {M}}}\), and mixed addition requires \(7 {{\textbf {M}}}\). Our results applied on the Edward448 and E448 yield a clean and simple implementation and achieve a brand new speed record. The scalar multiplication on Edwards448 and E448 have the same cost of \({{\textbf {M}}}\) and \({{\textbf {S}}}\) as that on Edwards25519 per bit.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_26
Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves. Math. Comput. 82, 1139–1179 (2013)
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76900-2_3
Bernstein, D.J., Lange, T.: Inverted Edwards coordinates. In: Boztaş, S., Lu, H.-F.F. (eds.) AAECC 2007. LNCS, vol. 4851, pp. 20–27. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77224-8_4
Bernstein, D.J., Lange, T.: A complete set of addition laws for incomplete Edwards curves. J. Number Theory 131(5), 858–872 (2011). https://doi.org/10.1016/j.jnt.2010.06.015, https://www.sciencedirect.com/science/article/pii/S0022314X10002155. Elliptic Curve Cryptography
Bouvier, C., Imbert, L.: Faster cofactorization with ECM using mixed representations. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 483–504. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_17
Chen, L., Moody, D., Regenscheid, A., Randall, K.: NIST special publication 800-186, recommendations for discrete logarithm-based cryptography: elliptic curve domain parameters. Technical report (2023). https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186.pdf
Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation using mixed coordinates. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1_6
Cremers, C., Jackson, D.: Prime, order please! Revisiting small subgroup and invalid curve attacks on protocols using Diffie-Hellman. In: 2019 IEEE 32nd Computer Security Foundations Symposium (CSF), pp. 78–7815. IEEE (2019)
Edwards, H.M.: A normal form for elliptic curves. Bull. Am. Math. Soc. 44, 393–423 (2007). https://doi.org/10.1090/S0273-0979-07-01153-6
Euler, L.: Observationes de comparatione arcuum curvarum irrectificibilium. Novi commentarii academiae scientiarum Petropolitanae 58–84 (1761)
Farashahi, R.R., Hosseini, S.G.: Differential addition on twisted Edwards curves. In: Pieprzyk, J., Suriadi, S. (eds.) ACISP 2017. LNCS, vol. 10343, pp. 366–378. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59870-3_21
Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_30
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_11
Hamburg, M.: Decaf: eliminating cofactors through point compression. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 705–723. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_34
Hamburg, M.: Ed448-goldilocks, a new elliptic curve. Cryptology ePrint Archive, Report 2015/625 (2015). https://eprint.iacr.org/2015/625
de Valence, H., Grigg, J., Tankersley, G., Valsorda, F., Lovecruft, I.: The ristretto255 group. Technical report, IETF CFRG Internet Draft (2019)
Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_20
Josefsson, S., Liusvaara, I.: Edwards-curve digital signature algorithm (EdDSA). RFC 8032 (2017). https://doi.org/10.17487/RFC8032, https://www.rfc-editor.org/info/rfc8032
Kohel, D.: Addition law structure of elliptic curves. J. Number Theory 131(5), 894–919 (2011). https://doi.org/10.1016/j.jnt.2010.12.001
Miniero, L., Murillo, S.G., Pascual, V.: Guidelines for end-to-end support of the RTP control protocol (RTCP) in back-to-back user agents (B2BUAs). RFC 8079 (2017). https://doi.org/10.17487/RFC8079, https://www.rfc-editor.org/info/rfc8079
National Institute of Standards and Technology (NIST): Federal information processing standard (FIPS) 186-5, digital signature standard (DSS)
Sedlacek, V., Chi-Domínguez, J.-J., Jancar, J., Brumley, B.B.: A formula for disaster: a unified approach to elliptic curve special-point-based attacks. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13090, pp. 130–159. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_5
Yu, W., Musa, S.A., Li, B.: Double-base chains for scalar multiplications on elliptic curves. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 538–565. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_18
Yu, W., Xu, G.: Pre-computation scheme of window \(\tau \)NAF for koblitz curves revisited. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 187–218. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_7
Acknowledgments
The authors would like to thank the anonymous reviewers for many helpful comments and their helpful suggestions. This work was supported by the National Key R &D Program of China (Grant No. 2023YFB4503203), the National Natural Science Foundation of China (Grant No. 62272453 and 62272186), the Key Research Program of the Chinese Academy of Sciences (Grant No. ZDRW-XX-2022-1), and the Innovation Project of Jinyinhu Laboratory (Grant No. 2023JYH010103).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Li, L., Yu, W., Xu, P. (2024). Fast and Simple Point Operations on Edwards448 and E448. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14604. Springer, Cham. https://doi.org/10.1007/978-3-031-57728-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-57728-4_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57727-7
Online ISBN: 978-3-031-57728-4
eBook Packages: Computer ScienceComputer Science (R0)