Abstract
We describe fast new algorithms to implement recent cryptosystems based on the Tate pairing. In particular, our techniques improve pairing evaluation speed by a factor of about 55 compared to previously known methods in characteristic 3, and attain performance comparable to that of RSA in larger characteristics.We also propose faster algorithms for scalar multiplication in characteristic 3 and square root extraction over Fp m, the latter technique being also useful in contexts other than that of pairing-based cryptography.
Chapter PDF
Similar content being viewed by others
References
I. Blake, G. Seroussi and N. Smart, “Elliptic Curves in Cryptography,” Cambridge University Press, 1999.
D. Boneh and M. Franklin, “Identity-based encryption from the Weil pairing,” Advances in Cryptology — Crypto’2001, Lecture Notes in Computer Science 2139, pp. 213–229, Springer-Verlag, 2001.
D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the Weil pairing,” Asiacrypt’2001, Lecture Notes in Computer Science 2248, pp. 514–532, Springer-Verlag, 2002.
H. Cohen, “A Course in Computational Algebraic Number Theory,” Springer-Verlag, 1993.
G. Frey, M. Müller, and H. Rück, “The Tate Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems,” IEEE Transactions on Information Theory 45(5), pp. 1717–1719, 1999.
S. Galbraith, “Supersingular curves in cryptography,” Asiacrypt’2001, Lecture Notes in Computer Science 2248, pp. 495–513, Springer-Verlag, 2002.
S. Galbraith, K. Harrison and D. Soldera, “Implementing the Tate pairing,” Algorithm Number Theory Symposium — ANTS V, Lecture Notes in Computer Science 2369, Springer-Verlag, to appear.
F. Hess, “Exponent Group Signature Schemes and Efficient Identity Based Signature Schemes Based on Pairings,” Cryptology ePrint Archive, Report 2002/012, available at http://www.eprint.iacr.org/2002/012/.
T. Itoh, O. Teechai and S. Tsujii, “A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases,” Information and Computation 78, pp. 171–177, 1988.
A. Joux, “A one-round protocol for tripartite Diffie-Hellman,” Algorithm Number Theory Symposium — ANTS IV, Lecture Notes in Computer Science 1838, pp. 385–394, Springer-Verlag, 2000.
A. Joux and K. Nguyen, “Separating Decision Diffie-Hellman from Diffie-Hellman in Cryptographic Groups,” Cryptology ePrint Archive, Report 2001/003, available at http://www.eprint.iacr.org/2001/003/.
N. Koblitz, “An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm,” Advances in Cryptology — Crypto’98, Lecture Notes in Computer Science 1462, pp. 327–337, Springer-Verlag, 1998.
R. Lidl and H. Niederreiter, “Finite Fields,” Encyclopedia of Mathematics and its Applications 20, 2nd Ed. Cambridge University Press, 1997.
B. Lynn, “Stanford IBE library,” available at http://www.crypto.stanford.edu/ibe/.
A.J. Menezes, “Elliptic Curve Public Key Cryptosystems,” Kluwer International Series in Engineering and Computer Science, 1993.
A.J. Menezes, T. Okamoto and S.A. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field,” IEEE Transactions on Information Theory 39, pp. 1639–1646, 1993.
A.J. Menezes, P.C. van Oorschot and S.A. Vanstone, “Handbook of Applied Cryptography,” CRC Press, 1997.
A.J. Menezes and S.A. Vanstone, “The implementation of elliptic curve cryptosystems,” Advances in Cryptology — Auscrypt’90, Lecture Notes in Computer Science 453, pp. 2–13, Springer-Verlag, 1990.
V. Miller, “Short Programs for Functions on Curves,” unpublished manuscript, 1986.
A. Miyaji, M. Nakabayashi, and S. Takano, “New explicit conditions of elliptic curve traces for FR-reduction,” IEICE Trans. Fundamentals, Vol. E84 A, no. 5, May 2001.
IEEE Std 2000-1363, “Standard Specifications for Public Key Cryptography,” 2000.
K.G. Paterson, “ID-based signatures from pairings on elliptic curves,” Cryptology ePrint Archive, Report 2002/004, available at http://www.eprint.iacr.org/2002/004/.
K. Rubin and A. Silverberg, “Supersingular abelian varieties in cryptology,” Advances in Cryptology — Crypto’2002, these proceedings.
R. Sakai, K. Ohgishi and M. Kasahara, “Cryptosystems based on pairing,” 2000 Symposium on Cryptography and Information Security (SCIS2000), Okinawa, Japan, Jan. 26—28, 2000.
R. Schroeppel, H. Orman, S. O'Malley, O. Spatscheck, “Fast Key Exchange with Elliptic Curve Systems,” Advances in Cryptology — Crypto’ 95, Lecture Notes in Computer Science 963, pp. 43–56, Springer-Verlag, 1995.
M. Scott, “Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL),” available at http://www.indigo.ie/~mscott/.
J.H. Silverman, “The Arithmetic of Elliptic Curves,” Graduate Texts in Mathematics, vol. 106, Springer-Verlag, 1986.
N.P. Smart, “The Algorithmic Resolution of Diophantine Equations,” London Mathematical Society Student Text 41, Cambridge University Press, 1998.
N.P. Smart, “An Identity Based Authenticated Key Agreement Protocol Based on the Weil Pairing,” Electronics Letters, to appear.
J. Solinas, “Generalized Mersenne numbers,” technical report CORR-39, Department of C&O, University of Waterloo, 1999, available at http://www.cacr.math.uwaterloo.ca/.
N. Tzanakis, “Solving elliptic diophantine equations by estimating linear forms in elliptic logarithms. The case of quartic equations,” Acta Arithmetica 75 (1996), pp. 165–190.
E. Verheul, “Evidence that XTR is more secure than supersingular elliptic curve cryptosystems,” Advances in Cryptology — Eurocrypt’2001, Lecture Notes in Computer Science 2045 (2001), pp. 195–210.
E. Verheul,“Self-blindable Credential Certificates from the Weil Pairing,”Asiacrypt’ 2001,Lecture Notes in Computer Science2248pp. 533–551,Springer-Verlag, 2002.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M. (2002). Efficient Algorithms for Pairing-Based Cryptosystems. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_23
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.