Efficient algorithms for pairing-based cryptosystems
Barreto, Paulo S.L.M., Kim, Hae Y., Lynn, Ben and Scott, Michael
(2002)
Efficient algorithms for pairing-based cryptosystems.
In: Crypto 2002, 18-22 August 2002, Santa Barbara, California, USA.
ISBN 978-3-540-44050-5
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 Fpm, the latter technique being also useful in contexts other than that of pairing-based cryptography.