Paper 2002/008

Efficient Algorithms for Pairing-Based Cryptosystems

Paulo S. L. M. Barreto, Hae Y. Kim, Ben Lynn, and Michael Scott

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 $\GF{p^m}$, the latter technique being also useful in contexts other than that of pairing-based cryptography.

Note: Fixed the proof of Lemma 1 (incorrect in the Crypto'2002 Proceedings version).

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Accepted for Crypto'2002
Keywords
elliptic curve cryptosystemTate pairingpairing-based cryptosystem
Contact author(s)
pbarreto @ larc usp br
History
2002-08-10: last of 5 revisions
2002-01-11: received
See all versions
Short URL
https://ia.cr/2002/008
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/008,
      author = {Paulo S. L. M.  Barreto and Hae Y.  Kim and Ben Lynn and Michael Scott},
      title = {Efficient Algorithms for Pairing-Based Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2002/008},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/008}},
      url = {https://eprint.iacr.org/2002/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.