Cryptology ePrint Archive: Report 2002/008

Efficient Algorithms for Pairing-Based Cryptosystems

Paulo S.L.M. Barreto and Hae Y. Kim and 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.

Category / Keywords: implementation/elliptic curve cryptosystem, Tate pairing, pairing-based cryptosystem

Publication Info: Accepted for Crypto'2002

Date: received 10 Jan 2002, last revised 10 Aug 2002

Contact author: pbarreto at larc usp br

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Version: 20020810:215047 (All versions of this report)

Short URL: ia.cr/2002/008

Discussion forum: Show discussion | Start new discussion