Fast Bilinear Maps from the Tate-Lichtenbaum Pairing on Hyperelliptic Curves

Pairings on elliptic curves recently obtained a lot of attention not only as a means to attack curve based cryptography but also as a building block for cryptosystems with special properties like short signatures or identity based encryption. In this paper we consider the Tate pairing on hyperelliptic curves of genus g. We give mathematically sound arguments why it is possible to use particular representatives of the involved residue classes in the second argument that allow to compute the pairing much faster, where the speed-up grows with the size of g. Since the curve arithmetic takes about the same time for small g and constant group size, this implies that g>1 offers advantages for implementations. We give two examples of how to apply the modified setting in pairing based protocols such that all parties profit from the idea. We stress that our results apply also to non-supersingular curves, e.g. those constructed by complex multiplication, and do not need distortion maps. They are also applicable if the co-factor is nontrivial.