×

Faster addition and doubling on elliptic curves. (English) Zbl 1153.11342

Kurosawa, Kaoru (ed.), Advances in cryptology – ASIACRYPT 2007. 13th international conference on the theory and application of cryptology and information security, Kuching, Malaysia, December 2-6, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-76899-9/pbk). Lecture Notes in Computer Science 4833, 29-50 (2007).
Summary: H. M. Edwards [Bull. Am. Math. Soc., New Ser. 44, No. 3, 393–422 (2007; Zbl 1134.14308)] recently introduced a new normal form for elliptic curves. Every elliptic curve over a non-binary field is birationally equivalent to a curve in Edwards form over an extension of the field, and in many cases over the original field.
This paper presents fast explicit formulas (and register allocations) for group operations on an Edwards curve. The algorithm for doubling uses only 3M + 4S, i.e., 3 field multiplications and 4 field squarings. If curve parameters are chosen to be small then the algorithm for mixed addition uses only 9M + 1S and the algorithm for non-mixed addition uses only 10M + 1S. Arbitrary Edwards curves can be handled at the cost of just one extra multiplication by a curve parameter.
For comparison, the fastest algorithms known for the popular “\(a_{4}= - 3\) Jacobian” form use 3M + 5S for doubling; use 7M + 4S for mixed addition; use 11M + 5S for non-mixed addition; and use 10M + 4S for non-mixed addition when one input has been added before.
The explicit formulas for non-mixed addition on an Edwards curve can be used for doublings at no extra cost, simplifying protection against side-channel attacks. Even better, many elliptic curves (approximately 1/4 of all isomorphism classes of elliptic curves over a non-binary finite field) are birationally equivalent – over the original field – to Edwards curves where this addition algorithm works for all pairs of curve points, including inverses, the neutral element, etc.
This paper contains an extensive comparison of different forms of elliptic curves and different coordinate systems for the basic group operations (doubling, mixed addition, non-mixed addition, and unified addition) as well as higher-level operations such as multi-scalar multiplication.
For the entire collection see [Zbl 1135.94001].

MSC:

11G05 Elliptic curves over global fields
14H52 Elliptic curves
14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography

Citations:

Zbl 1134.14308
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antipa, A., Brown, D.R.L., Gallant, R.P., Lambert, R.J., Struik, R., Vanstone, S.A.: Accelerated verification of ECDSA signatures, in [43], pp. 307-318 (2006). MR 2007d:94044, www.cacr.math.uwaterloo.ca/techreports/2005/tech_reports2005.html (Cited in §7) · Zbl 1151.94595
[2] Avanzi, R.M.: The complexity of certain multi-exponentiation techniques in cryptography. Journal of Cryptology 18, 357-373 (2005). MR 2007f:94027, www.eprint.iacr.org/2002/154 (Cited in §6, §7) · Zbl 1096.94021
[3] Barbosa, M., Page, D.: On the automatic construction of indistinguishable operations (2005), www.eprint.iacr.org/2005/174 (Cited in §8) · Zbl 1122.94027
[4] Bellare, M., Garay, J.A., Rabin, T.: Batch verification with applications to cryptography and checking, in [35], pp. 170-191 (1998). MR 99h:94043. (Cited in §7)
[5] Bernstein, D.J.: A software implementation of NIST P-224 (2001), www.cr.yp.to/talks.html#2001.10.29 (Cited in §5)
[6] Bernstein, D.J.: Differential addition chains (2006), www.cr.yp.to/papers.html#diffchain (Cited in §7, §8)
[7] Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records, in [45], pp. 207-228 (2006), www.cr.yp.to/papers.html#curve25519 (Cited in §1, §2,§4, §5, §8) · Zbl 1151.94480
[8] Bernstein, D.J., Lange, T.: Explicit-formulas database (2007), www.hyperelliptic.org/EFD (Cited in §2, §3, §3,§5)
[9] Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis, in [26], pp. 34-42 (2003). MR 2005c:94045, www.eprint.iacr.org/2002/125 (Cited in §1, §5) · Zbl 1031.94510
[10] Blake, I.F., Seroussi, G., Smart, N.P. (eds.): Advances in elliptic curve cryptography. London Mathematical Society Lecture Note Series, 317. Cambridge University Press, Cambridge (2005), MR 2007g:94001. See [27] · Zbl 1089.94018
[11] Bosma, W., Lenstra Jr., H.W.: Complete systems of two addition laws for elliptic curves. Journal of Number Theory 53, 229-240 (1995), MR 96f:11079. (Cited in §3, §3) · Zbl 0841.14027
[12] Brier, É., Déchène, I., Joye, M.: Unified point addition formulae for elliptic curve cryptosystems, in [40], pp. 247-256 (2004) (Cited in §5)
[13] Brier, É., Joye, M.: Weierstrass elliptic curves and side-channel attacks, in [39], pp. 335-345 (2002), www.geocities.com/MarcJoye/publications.html (Cited in §5, §8) · Zbl 1055.94512
[14] Brown, D.R.L.: Multi-dimensional Montgomery ladders for elliptic curves (2006), www.eprint.iacr.org/2006/220 (Cited in §7, §8)
[15] Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. IEEE Transactions on Computers 53, 760-768 (2004), www.bcm.crypto.free.fr/pdf/CCJ04.pdf (Cited in §8) · Zbl 1300.94045
[16] Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Advances in Applied Mathematics 7, 385-434 (1986), MR 88h:11094. (Cited in §5) · Zbl 0614.10004
[17] Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. CRC Press, Boca Raton (2005), MR 2007f:14020. See [22], [24], [33]
[18] Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation using mixed coordinates, in [41], pp. 51-65 (1998), MR 1726152, www.math.u-bordeaux.fr/ cohen/asiacrypt98.dvi (Cited in §1, §5) · Zbl 0939.11039
[19] Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems, in [32], pp. 292-302 (1999) (Cited in §8, §8, §8) · Zbl 0955.94009
[20] de Rooij, P.: Efficient exponentiation using precomputation and vector addition chains, in [21], pp. 389-399 (1995), MR 1479665. (Cited in §7) · Zbl 0879.94026
[21] De Santis, A. (ed.): Advances in cryptology: EUROCRYPT 1994. LNCS, vol. 950. Springer, Heidelberg (1995), MR 98h:94001. See [20] · Zbl 0847.00061
[22] Doche, C.: Exponentiation, in [17], pp. 145-168 (2005) MR 2162725. (Cited in §6, §7)
[23] Doche, C., Icart, T., Kohel, D.R.: Efficient scalar multiplication by isogeny decompositions, in [45], pp. 191-206 (2006) (Cited in §1) · Zbl 1151.94506
[24] Doche, C., Lange, T.: Arithmetic of elliptic curves, in [17], pp. 267-302 (2005), MR 2162729. (Cited in §5)
[25] Edwards, H.M.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393-422 (2007), www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html (Cited in §1, §3) · Zbl 1134.14308
[26] Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.): Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. LNCS, vol. 2643. Springer, Heidelberg (2003). ISBN 3-540-40111-3. MR 2004j:94001. (Sec [9]) · Zbl 1019.00017
[27] Joye, M.: Defences against side-channel analysis, in [10], pp. 87-100 (2005) (Cited in §8)
[28] Joye, M., Quisquater, J.-J.: Hessian elliptic curves and side-channel attacks, in [31], pp. 402-410 (2001). MR 2003k:94032, www.geocities.com/MarcJoye/publications.html (Cited in §1, §5) · Zbl 1012.94547
[29] Joye, M., Yen, S.-M.: The Montgomery powering ladder, in [30], pp. 291-302 (2003), www.gemplus.com/smart/rd/publications/pdf/JY03mont.pdf (Cited in §8) · Zbl 1020.11500
[30] Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.): Cryptographic hardware and embedded systems-CHES 2002. LNCS, vol. 2523. Springer, Heidelberg (2003). ISBN 3-540-42521-7. See [29] · Zbl 1007.00053
[31] Koç, Ç.K., Naccache, D., Paar, C. (eds.): Cryptographic hardware and embedded systems-CHES 2001. LNCS, vol. 2162. Springer, Heidelberg (2001). ISBN 3-540-42521-7. MR 2003g:94002. See [28], [34], [42] · Zbl 0971.00042
[32] Koç, Ç.K., Paar, C. (eds.): Cryptographic hardware and embedded systems. In: first international workshop CHES 1999. LNCS, vol. 1717. Springer, Heidelberg (1999). ISBN 3-540-66646-X. See [19]
[33] Lange, T.: Mathematical countermeasures against side-channel attacks, in [17], pp. 687-714 (2005), MR 2163785. (Cited in §8, §8)
[34] Liardet, P.-Y., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form, in [31], pp. 391-401 (2001), MR 2003k:94033. (Cited in §1, §5, §8) · Zbl 1012.94552
[35] Lucchesi, C.L., Moura, A.V. (eds.): LATIN 1998: theoretical informatic. LNCS, vol. 1380. Springer, Heidelberg (1998). ISBN 3-540-64275-7. MR 99d:68007. See [4]
[36] Mangard, S., Oswald, E., Popp, T.: Power analysis attacks: revealing the secrets of smart cards. Springer, Heidelberg (2007) (Cited in §8, §8) · Zbl 1131.68449
[37] Miller, V.S.: Use of elliptic curves in cryptography, in [44], pp. 417-426 (1986) MR 88b:68040. (Cited in §1) · Zbl 0589.94005
[38] Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48, 243-264 (1987) MR 88e:11130, www.links.jstor.org/sici?sici=0025-5718 (Cited in §1, §6, §7) · Zbl 0608.10005
[39] Naccache, D., Paillier, P. (eds.): Public key cryptography. In: PKC 2002. LNCS, vol. 2274. Springer, Heidelberg (2002). ISBN 3-540-43168-3. MR 2005b:94044. See [13] · Zbl 0999.94523
[40] Nedjah, N., de Macedo Mourelle, L. (eds.): Embedded Cryptographic Hardware: Methodologies & Architectures, Nova Science Publishers (2004) ISBN 1-59454-012-8. See [12]
[41] Ohta, K., Pei, D. (eds.): Advances in cryptology-ASIACRYPT 1998. LNCS, vol. 1514. Springer, Berlin (1998). ISBN 3-540-65109-8. MR 2000h:94002. See [18]
[42] Oswald, E., Aigner, M.: Randomized addition-subtraction chains as a countermeasure against power attack, in [31], pp. 39-50 (2001) MR 2003m:94068. (Cited in §8) · Zbl 1012.94549
[43] Preneel, B., Tavares, S.E. (eds.): Selected Areas in Cryptography. In: SAC 2005. LNCS, vol. 3897, Springer, Heidelberg (2006). ISBN3-540-33108-5. MR 2007b:94002. See [1] · Zbl 1120.94003
[44] Williams, H.C. (ed.): CRYPTO 1985. LNCS, vol. 218. Springer, Berlin (1986). ISBN 3-540-16463-4. MR 87d:94002. See [37]
[45] Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.): 9th international conference on theory and practice in public-key cryptography. LNCS, vol. 3958. Springer, Heidelberg (2006). ISBN 978-3-540-33851-2. See [7], [23] · Zbl 1102.94003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.