×

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
PDFBibTeX XMLCite
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]; Paulo S.L.M. Barreto, Hae Yong Kim, Ben Lynn, Michael Scott, Efficient algorithms for pairing-based cryptosystems, in: CRYPTO 2002 [36] · 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]; Paulo S.L.M. Barreto, Michael Naehrig, Pairing-friendly elliptic curves of prime order, in: SAC 2005 [30] · 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]; Sanjit Chatterjee, Palash Sarkar, Rana Barua, Efficient computation of Tate pairing in projective coordinate over general characteristic fields, in: ICISC 2004 [28] · Zbl 1133.94310
[9] Cheng, Zhaohui; Nistazakis, Manos, Implementing pairing-based cryptosystems, (3rd International Workshop on Wireless Security Technologies IWWST-2005 (2005))
[10] (Chowdhury, Dipanwita Roy; Rijmen, Vincent; Das, Abhijit, Progress in Cryptology - INDOCRYPT 2008, Proc. of 9th International Conference on Cryptology in India. Progress in Cryptology - INDOCRYPT 2008, Proc. of 9th International Conference on Cryptology in India, Kharagpur, India, December 14-17, 2008. Progress in Cryptology - INDOCRYPT 2008, Proc. of 9th International Conference on Cryptology in India. Progress in Cryptology - INDOCRYPT 2008, Proc. of 9th International Conference on Cryptology in India, Kharagpur, India, December 14-17, 2008, Lecture Notes in Comput. Sci., vol. 5365 (2008), Springer: Springer Berlin) · Zbl 1154.94005
[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]; Craig Costello, Huseyin Hisil, Colin Boyd, Juan Manuel Gonzalez Nieto, Kenneth Koon-Ho Wong, Faster pairings on special Weierstrass curves, in: Pairing 2009 [31]
[12] Craig Costello, Tanja Lange, Michael Naehrig, Faster pairing computations on curves with high-degree twists, in: PKC 2010 [27]; Craig Costello, Tanja Lange, Michael Naehrig, Faster pairing computations on curves with high-degree twists, in: PKC 2010 [27] · Zbl 1279.94069
[13] M. Prem Laxman Das, Palash Sarkar, Pairing computation on twisted Edwards form elliptic curves, in: Pairing 2008 [19]; M. Prem Laxman Das, Palash Sarkar, Pairing computation on twisted Edwards form elliptic curves, in: Pairing 2008 [19] · 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]; Gerhard Frey, Tanja Lange, Background on Curves and Jacobians, Chapter 4 in [1] · 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] (Galbraith, Steven D.; Paterson, Kenneth G., Pairing-Based Cryptography - Pairing 2008, Proc. of Second International Conference. Pairing-Based Cryptography - Pairing 2008, Proc. of Second International Conference, Egham, UK, September 1-3, 2008. Pairing-Based Cryptography - Pairing 2008, Proc. of Second International Conference. Pairing-Based Cryptography - Pairing 2008, Proc. of Second International Conference, Egham, UK, September 1-3, 2008, Lecture Notes in Comput. Sci., vol. 5209 (2008), Springer: Springer Berlin) · Zbl 1155.94002
[20] Darrel Hankerson, Alfred J. Menezes, Michael Scott, Software implementation of pairings, in: Identity-Based Cryptography [23]; Darrel Hankerson, Alfred J. Menezes, Michael Scott, Software implementation of pairings, in: Identity-Based Cryptography [23] · Zbl 1159.68439
[21] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson, Twisted Edwards curves revisited, in: ASIACRYPT 2008 [29]; Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson, Twisted Edwards curves revisited, in: ASIACRYPT 2008 [29]
[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] (Joye, Marc; Neven, Gregory, Identity-Based Cryptography. Identity-Based Cryptography, Inf. Secur. Cryptography, vol. 2 (2009), IOS Press) · Zbl 1154.68016
[24] (Kurosawa, Kaoru, Advances in Cryptology - ASIACRYPT 2007. Advances in Cryptology - ASIACRYPT 2007, Lecture Notes in Comput. Sci., vol. 4833 (2007), Springer: Springer Berlin, Heidelberg) · Zbl 1135.94001
[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.; Francois Morain, Edwards curves and CM curves, technical report, arXiv, 2009.
[27] (Nguyen, Phong; Pointcheval, David, Proc. of 13th International Conference on Practice and Theory in Public-Key Cryptography. Proc. of 13th International Conference on Practice and Theory in Public-Key Cryptography, Paris, France, May 26-28, 2010. Proc. of 13th International Conference on Practice and Theory in Public-Key Cryptography. Proc. of 13th International Conference on Practice and Theory in Public-Key Cryptography, Paris, France, May 26-28, 2010, Lecture Notes in Comput. Sci., vol. 6056 (2009), Springer: Springer Berlin) · Zbl 1188.94010
[28] (Park, Choonsik; Chee, Seongtaek, Information Security and Cryptology - ICISC 2004, Proc. of 7th International Conference, Revised Selected Papers. Information Security and Cryptology - ICISC 2004, Proc. of 7th International Conference, Revised Selected Papers, Seoul, Korea, December 2-3, 2004. Information Security and Cryptology - ICISC 2004, Proc. of 7th International Conference, Revised Selected Papers. Information Security and Cryptology - ICISC 2004, Proc. of 7th International Conference, Revised Selected Papers, Seoul, Korea, December 2-3, 2004, Lecture Notes in Comput. Sci., vol. 3506 (2005), Springer) · Zbl 1131.68012
[29] (Pieprzyk, Josef, Advances in Cryptology - ASIACRYPT 2008, Proc. of 14th International Conference on the Theory and Application of Cryptology and Information Security. Advances in Cryptology - ASIACRYPT 2008, Proc. of 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Advances in Cryptology - ASIACRYPT 2008, Proc. of 14th International Conference on the Theory and Application of Cryptology and Information Security. Advances in Cryptology - ASIACRYPT 2008, Proc. of 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008, Lecture Notes in Comput. Sci., vol. 5350 (2008), Springer: Springer Berlin) · Zbl 1155.94008
[30] (Preneel, Bart; Tavares, Stafford E., Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Revised Selected Papers. Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Revised Selected Papers, Kingston, ON, Canada, August 11-12, 2005. Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Revised Selected Papers. Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Revised Selected Papers, Kingston, ON, Canada, August 11-12, 2005, Lecture Notes in Comput. Sci., vol. 3897 (2006), Springer) · Zbl 1120.94003
[31] (Schacham, Hovav; Waters, Brent, Pairing-Based Cryptography - Pairing 2009, Proc. of Third International Conference. Pairing-Based Cryptography - Pairing 2009, Proc. of Third International Conference, Palo Alto, CA, USA, August 12-14, 2009. Pairing-Based Cryptography - Pairing 2009, Proc. of Third International Conference. Pairing-Based Cryptography - Pairing 2009, Proc. of Third International Conference, Palo Alto, CA, USA, August 12-14, 2009, Lecture Notes in Comput. Sci., vol. 5671 (2009), Springer: Springer Berlin) · Zbl 1169.94002
[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; 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] (Vaudenay, Serge, Progress in Cryptology - AFRICACRYPT 2008, Proc. of First International Conference on Cryptology in Africa. Progress in Cryptology - AFRICACRYPT 2008, Proc. of First International Conference on Cryptology in Africa, Casablanca, Morocco, June 11-14, 2008. Progress in Cryptology - AFRICACRYPT 2008, Proc. of First International Conference on Cryptology in Africa. Progress in Cryptology - AFRICACRYPT 2008, Proc. of First International Conference on Cryptology in Africa, Casablanca, Morocco, June 11-14, 2008, Lecture Notes in Comput. Sci. (2008), Springer: Springer Berlin) · Zbl 1137.94002
[36] (Yung, Moti, Advances in Cryptology - CRYPTO 2002, Proc. of 22nd Annual International Cryptology Conference. Advances in Cryptology - CRYPTO 2002, Proc. of 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002. Advances in Cryptology - CRYPTO 2002, Proc. of 22nd Annual International Cryptology Conference. Advances in Cryptology - CRYPTO 2002, Proc. of 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Lecture Notes in Comput. Sci., vol. 2442 (2002), Springer) · Zbl 0997.00039
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.