Another approach to pairing computation in Edwards coordinates. (English) Zbl 1203.94104

Roy Chowdhury, Dipanwita (ed.) et al., Progress in cryptology – INDOCRYPT 2008. 9th international conference on cryptology in India, Kharagpur, India, December 14–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-89753-8/pbk). Lecture Notes in Computer Science 5365, 400-413 (2008).
Summary: The recent introduction of Edwards curves has significantly reduced the cost of addition on elliptic curves. This paper presents new explicit formulae for pairing implementation in Edwards coordinates. We prove our method gives performances similar to those of Miller’s algorithm in Jacobian coordinates and is thus of cryptographic interest when one chooses Edwards curve implementations of protocols in elliptic curve cryptography. The method is faster than the recent proposal of Das and Sarkar for computing pairings on supersingular curves using Edwards coordinates.
For the entire collection see [Zbl 1154.94005].


94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)


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., Lange, T.: Explicit-formulas database (2007), http://hyperelliptic.org/EFD/
[3] 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
[4] Blake, I.F., Seroussi, G., Smart, N.P.: Advances in Elliptic Curve Cryptography. London Mathematical Society Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005) · Zbl 1089.94018 · doi:10.1017/CBO9780511546570
[5] Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001) · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_13
[6] Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001) · Zbl 1064.94554 · doi:10.1007/3-540-45682-1_30
[7] Boneh, D., Shacham, H.: Group signatures with verifier-local revocation. In: Atluri, V., Pfitzmann, B., McDaniel, P. (eds.) ACM CCS 2004: 11th Conference on Computer and Communications Security, pp. 168–177. ACM Press, New York (2004)
[8] Bosma, W.: Signed bits and fast exponentiation. J. de théorie des nombres de Bordeaux 13(1), 27–41 (2001) · Zbl 1060.11082 · doi:10.5802/jtnb.301
[9] Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptography 37(1), 133–141 (2005) · Zbl 1100.14517 · doi:10.1007/s10623-004-3808-4
[10] Chatterjee, S., Sarkar, P., Barua, R.: Efficient computation of Tate pairing in projective coordinate over general characteristic fields (2004) · Zbl 1133.94310
[11] Das, M.P.L., Sarkar, P.: Pairing computation on twisted Edwards form elliptic curves. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209. Springer, Heidelberg (2008) · doi:10.1007/978-3-540-79549-0
[12] Edwards, H.M.: A normal form for elliptic curves. Bull. AMS 44, 393–422 (2007) · Zbl 1134.14308 · doi:10.1090/S0273-0979-07-01153-6
[13] Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006), http://eprint.iacr.org/ · Zbl 1181.94094
[14] Granger, R., Hess, F., Oyono, R., Thériault, N., Vercauteren, F.: Ate pairing on hyperelliptic curves (2007)
[15] Granger, R., Page, D., Smart, N.P.: High security pairing-based cryptography revisited. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 480–494. Springer, Heidelberg (2006) · Zbl 1143.94349 · doi:10.1007/11792086_34
[16] Hartshorne, R.: Algebraic Geometry. Graduate texts in Mathematics, vol. 52. Springer, Heidelberg (1977) · Zbl 0367.14001 · doi:10.1007/978-1-4757-3849-0
[17] Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Transactions on Information Theory 52, 4595–4602 (2006) · Zbl 1189.11057 · doi:10.1109/TIT.2006.881709
[18] Ionica, S., Joux, A.: Another approach on pairing computation in Edwards coordinates. Cryptology ePrint Archive, Report 2008/292 (2008), http://eprint.iacr.org/ · Zbl 1203.94104
[19] Joux, A.: A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology 17(4), 263–276 (2004) · Zbl 1070.94007 · doi:10.1007/s00145-004-0312-y
[20] Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005) · Zbl 1122.94038 · doi:10.1007/11586821_2
[21] Miller, V.S.: The Weil pairing, and its efficient calculation. Journal of Cryptology 17(4), 235–261 (2004) · Zbl 1078.14043 · doi:10.1007/s00145-004-0315-8
[22] Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate texts in Mathematics, vol. 106. Springer, Heidelberg (1986) · Zbl 0585.14026 · doi:10.1007/978-1-4757-1920-8
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.