Twisted Edwards curves revisited. (English) Zbl 1206.94074

Pieprzyk, Josef (ed.), Advances in cryptology – ASIACRYPT 2008. 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-89254-0/pbk). Lecture Notes in Computer Science 5350, 326-343 (2008).
Summary: This paper introduces fast algorithms for performing group operations on twisted Edwards curves, pushing the recent speed limits of Elliptic Curve Cryptography (ECC) forward in a wide range of applications. Notably, the new addition algorithm uses \(8\mathbf{M}\) for suitably selected curve constants. In comparison, the fastest point addition algorithms for (twisted) Edwards curves stated in the literature use \(9\mathbf{M} + 1\mathbf{S}\). It is also shown that the new addition algorithm can be implemented with four processors dropping the effective cost to \(2\mathbf{M}\). This implies an effective speed increase by the full factor of 4 over the sequential case. Our results allow faster implementation of elliptic curve scalar multiplication. In addition, the new point addition algorithm can be used to provide a natural protection from side channel attacks based on simple power analysis (SPA).
For the entire collection see [Zbl 1155.94008].


94A60 Cryptography


Full Text: DOI


[1] 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) · Zbl 1142.94332 · doi:10.1007/978-3-540-68164-9_26
[2] Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: Optimizing double-base elliptic-curve single-scalar multiplication. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 167–182. Springer, Heidelberg (2007) · Zbl 1153.94350 · doi:10.1007/978-3-540-77026-8_13
[3] Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves. Cryptology ePrint Archive, Report 2008/016 (2008), http://eprint.iacr.org/ · Zbl 1322.11125
[4] Bernstein, D.J., Lange, T.: Explicit-formulas database (2007), http://www.hyperelliptic.org/EFD
[5] 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) · Zbl 1153.11342 · doi:10.1007/978-3-540-76900-2_3
[6] Bernstein, D.J., Lange, T.: Inverted Edwards coordinates. In: Boztaş, S., Lu, H.-F. (eds.) AAECC 2007. LNCS, vol. 4851, pp. 20–27. Springer, Heidelberg (2007) · Zbl 1195.14047 · doi:10.1007/978-3-540-77224-8_4
[7] Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 34–42. Springer, Heidelberg (2003) · Zbl 1031.94510 · doi:10.1007/3-540-44828-4_5
[8] Brier, E., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002) · Zbl 1055.94512 · doi:10.1007/3-540-45664-3_24
[9] Brier, E., Joye, M.: Fast point multiplication on elliptic curves through isogenies. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 43–50. Springer, Heidelberg (2003) · Zbl 1030.11027 · doi:10.1007/3-540-44828-4_6
[10] Cohen, H., Frey, G. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005) · Zbl 1082.94001
[11] 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) · Zbl 0939.11039 · doi:10.1007/3-540-49649-1_6
[12] Doche, C., Icart, T., Kohel, D.R.: Efficient scalar multiplication by isogeny decompositions. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 191–206. Springer, Heidelberg (2006) · Zbl 1151.94506 · doi:10.1007/11745853_13
[13] Edwards, H.M.: A normal form for elliptic curves. Bulletin of the AMS 44(3), 393–422 (2007) · Zbl 1134.14308 · doi:10.1090/S0273-0979-07-01153-6
[14] Eisenträger, K., Lauter, K., Montgomery, P.L.: Fast elliptic curve arithmetic and improved Weil pairing evaluation. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 343–354. Springer, Heidelberg (2003) · Zbl 1038.11079 · doi:10.1007/3-540-36563-X_24
[15] Fischer, W., Giraud, C., Knudsen, E.W., Seifert, J.P.: Parallel scalar multiplication on general elliptic curves over \(\mathbb{F}_p\) hedged against non-differential side-channel attacks. Cryptology ePrint Archive, Report 2002/007 (2002), http://eprint.iacr.org/
[16] Gaudry, P., Lubicz, D.: The arithmetic of characteristic 2 Kummer surfaces. Cryptology ePrint Archive, Report 2008/133 (2008), http://eprint.iacr.org/
[17] Hisil, H., Wong, K., Carter, G., Dawson, E.: Faster group operations on elliptic curves. Cryptology ePrint Archive, Report 2007/441 (2007), http://eprint.iacr.org/
[18] Izu, T., Takagi, T.: A fast parallel elliptic curve multiplication resistant against side channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 280–296. Springer, Heidelberg (2002) · Zbl 1055.94516 · doi:10.1007/3-540-45664-3_20
[19] Izu, T., Takagi, T.: Exceptional procedure attack on elliptic curve cryptosystems. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 224–239. Springer, Heidelberg (2003) · Zbl 1033.94529 · doi:10.1007/3-540-36288-6_17
[20] Joye, M., Quisquater, J.J.: Hessian elliptic curves and side-channel attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 402–410. Springer, Heidelberg (2001) · Zbl 1012.94547 · doi:10.1007/3-540-44709-1_33
[21] Joye, M., Yen, S.M.: The Montgomery powering ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003) · Zbl 1020.11500 · doi:10.1007/3-540-36400-5_22
[22] Liardet, P.Y., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 391–401. Springer, Heidelberg (2001) · Zbl 1012.94552 · doi:10.1007/3-540-44709-1_32
[23] Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48(177), 243–264 (1987) · Zbl 0608.10005 · doi:10.1090/S0025-5718-1987-0866113-7
[24] de Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 389–399. Springer, Heidelberg (1995) · Zbl 0879.94026 · doi:10.1007/BFb0053453
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.