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 F pm, the latter
technique being also useful in contexts other than that of pairing-based cryptography.

Pairings were first introduced to elliptic curve cryptography for “destructive” methods like the
MOV reduction [MOV93]. With the help of the Weil pairing, Menezes, Okamoto and Vanstone
showed a way to reduce the discrete logarithm problem on supersingular elliptic curves to
the discrete logarithm problem of an extension of the underlying finite field. Later Frey,
Müller and Rück extended this attack to more general elliptic curves with the Tate pairing
[FMR99]. But the Weil and Tate pairing can also be used as a constructive tool for …