Paper 2008/404

Pairing with Supersingular Trace Zero Varieties Revisited

Emanuele Cesena

Abstract

A Trace Zero Variety is a specific subgroup of the group of the divisor classes on a hyperelliptic curve $C/\F_q$, which are rational over a small degree extension $\F_{q^r}$ of the definition field. Trace Zero Varieties (\tzv) are interesting for cryptographic applications since they enjoy properties that can be exploited to achieve fast arithmetic and group construction. Furthermore, supersingular \tzv allows to achieve higher MOV security per bit than supersingular elliptic curves, thus making them interesting for applications in pairing-based cryptography. In this paper we survey algorithms in literature for computing bilinear pairings and we present a new algorithm for the Tate pairing over supersingular \tzv, which exploits the action of the $q$-Frobenius. We give explicit examples and provide experimental results for supersingular \tzv defined over fields of characteristic 2. Moreover, in the same settings, we propose a more efficient variant of the Silverberg's point compression algorithm.