×

Faster computation of the Tate pairing. (English) Zbl 1222.14069

The paper proposes some improvements in the computation of the Tate pairing on elliptic curves \(E\), both in Weierstrass form and in Edwards form, curves defined over a non-binary finite field \(F_q\) and with even embedding degree (for a prime \(n|\sharp(E)\) the embedding degree \(k\), with respect to \(n\), is the multiplicative degree of \(q\) modulo \(n\)).
For \(E\) in Weierstrass form, Miller’s algorithm computes efficiently the Tate pairing, using the chord-and-tangent method for the addition and doubling of points. Section 3 presents new formulas for the addition and doubling steps in Miller’s algorithm. Those formulas use a representation of the points of \(E\) in Jacobian coordinates \((X:Y:Z:T)\), \(T^2=Z\), and the paper gives its cost in term of the costs \(m,s,M,S\) of multiplication and squaring in \(\mathbb F_q\) and \(\mathbb F_{q^k}\).
A twisted Edwards curve, introduced by D. J. Bernstein et al. [in: AFRICACRYPT 2008. Casablanca, Morocco, 2008. Lect. Notes Comput. Sci. 5023, 389–405 (2008; Zbl 1142.94332)], is a curve giving by an equation: \(E_{\text{ad}}: ax^2+y^2=1+dx^2y^2\), whose (affine) points have efficient addition formulas. Since the equation of \(E_{\text{ad}}\) has degree four the chord-and-tangent geometric interpretation of the addition is not more valid, but section 4 of the paper gives (theorem 2) a new geometric interpretation of the addition law for \(E_{\text{ad}}\), and with this tool section 5 shows how to compute Tate pairing on twisted Edwards curves.
Section 6 gives the comparison of the proposed formulas with others in the literature, as the paper of S. Ionica and A. Joux [in: INDOCRYPT 2008. Kharagpur, India, 2008. Lect. Notes Comput. Sci. 5365, 400–413 (2008; Zbl 1203.94104)], concluding that “ ... our new formulas for Edwards curves solidly beat all previous formulas published for Tate computation on Edwards curves” and “ Our new formulas for pairings on arbitrary Edwards curves are faster than all formulas previously known for Weierstrass curves except for the very special curves with \(a_4=0\).”.
Finally, sections 7 and 8 present construction and numerical examples (with embedding degree \(k=6,8,10,22\)) of pairing-friendly Edwards curves, examples covering the most common security levels.

MSC:

11Y16 Number-theoretic algorithms; complexity
11G20 Curves over finite and local fields
14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography

Software:

EFD; SageMath
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Avanzi, Roberto M.; Cohen, Henri; Doche, Christophe; Frey, Gerhard; Lange, Tanja; Nguyen, Kim; Vercauteren, Frederik, The handbook of elliptic and hyperelliptic curve cryptography, (2005), CRC · Zbl 1082.94001
[2] Paulo S.L.M. Barreto, Hae Yong Kim, Ben Lynn, Michael Scott, Efficient algorithms for pairing-based cryptosystems, in: CRYPTO 2002 [36], 2002, pp. 354-368. · Zbl 1026.94520
[3] Barreto, Paulo S.L.M.; Lynn, Ben; Scott, Michael, Efficient implementation of pairing-based cryptosystems, J. cryptology, 17, 321-334, (2004) · Zbl 1123.94334
[4] Paulo S.L.M. Barreto, Michael Naehrig, Pairing-friendly elliptic curves of prime order, in: SAC 2005 [30], 2006, pp. 319-331. · Zbl 1151.94479
[5] Bernstein, Daniel J.; Birkner, Peter; Joye, Marc; Lange, Tanja; Peters, Christiane, Twisted edwards curves, in: Africacrypt [35], 2008, pp. 389-405 · Zbl 1142.94332
[6] Bernstein, Daniel J.; Lange, Tanja, Explicit-formulas database
[7] Bernstein, Daniel J.; Lange, Tanja, Faster addition and doubling on elliptic curves, in: ASIACRYPT 2007 [24], 2007, pp. 29-50 · Zbl 1153.11342
[8] Sanjit Chatterjee, Palash Sarkar, Rana Barua, Efficient computation of Tate pairing in projective coordinate over general characteristic fields, in: ICISC 2004 [28], 2005, pp. 168-181. · Zbl 1133.94310
[9] Cheng, Zhaohui; Nistazakis, Manos, Implementing pairing-based cryptosystems, ()
[10] ()
[11] Craig Costello, Huseyin Hisil, Colin Boyd, Juan Manuel Gonzalez Nieto, Kenneth Koon-Ho Wong, Faster pairings on special Weierstrass curves, in: Pairing 2009 [31], 2009, pp. 89-101.
[12] Craig Costello, Tanja Lange, Michael Naehrig, Faster pairing computations on curves with high-degree twists, in: PKC 2010 [27], 2010, pp. 224-242. · Zbl 1279.94069
[13] M. Prem Laxman Das, Palash Sarkar, Pairing computation on twisted Edwards form elliptic curves, in: Pairing 2008 [19], 2008, pp. 192-210. · Zbl 1186.94433
[14] Edwards, Harold M., A normal form for elliptic curves, Bull. amer. math. soc., 44, 393-422, (2007) · Zbl 1134.14308
[15] Freeman, David; Scott, Michael; Teske, Edlyn, A taxonomy of pairing-friendly elliptic curves, J. cryptology, 23, 2, 224-280, (2010), Cryptology ePrint Archive, Report 2006/372, 2006, update 2008 · Zbl 1181.94094
[16] Gerhard Frey, Tanja Lange, Background on Curves and Jacobians, Chapter 4 in [1], 2005, pp. 45-85. · Zbl 1155.11361
[17] Fulton, William, Algebraic curves, (1969), W.A. Benjamin, Inc. · Zbl 0181.23901
[18] Galbraith, Steven D.; McKee, James F.; Valença, Paula C., Ordinary abelian varieties having small embedding degree, Finite fields appl., 13, 800-814, (2007) · Zbl 1161.11017
[19] ()
[20] Darrel Hankerson, Alfred J. Menezes, Michael Scott, Software implementation of pairings, in: Identity-Based Cryptography [23], 2009, pp. 188-206. · Zbl 1159.68439
[21] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson, Twisted Edwards curves revisited, in: ASIACRYPT 2008 [29], 2008, pp. 326-343.
[22] Ionica, Sorina; Joux, Antoine, Another approach to pairing computation in edwards coordinates, in: INDOCRYPT 2008 [10], 2008, pp. 400-413 · Zbl 1203.94104
[23] ()
[24] ()
[25] Miller, Victor S., The Weil pairing, and its efficient calculation, J. cryptology, 17, 4, 235-261, (2004) · Zbl 1078.14043
[26] Francois Morain, Edwards curves and CM curves, technical report, arXiv, 2009.
[27] ()
[28] ()
[29] ()
[30] ()
[31] ()
[32] Silverman, Joseph H., The arithmetic of elliptic curves, Grad. texts in math., vol. 106, (1986), Springer-Verlag · Zbl 0585.14026
[33] Nigel Smart (Ed.), ECRYPT2 yearly report on algorithms and keysizes (2008-2009), technical report, ECRYPT II - European Network of Excellence in Cryptology, EU FP7, ICT-2007-216676, 2009, published as deliverable D.SPA.7, http://www.ecrypt.eu.org/documents/D.SPA.7.pdf.
[34] Stein, William, Sage mathematics software, (2008), (version 2.8.12). The Sage Group
[35] ()
[36] ()
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.