On small characteristic algebraic tori in pairing based cryptography

The output of the Tate pairing on an elliptic curve over a finitefield is an element in the multiplicative group of an extensionfield modulo a particular subgroup. One ordinarily powers thiselement to obtain a unique representative for the output coset,and performs any further necessary arithmetic in the extensionfield. Rather than an obstruction, we show to the contrary thatone can exploit this quotient group to eliminate the finalpowering, to speed up exponentiations and to obtain a simplecompression of pairing values which is useful during interactiveidentity-based cryptographic protocols. Specifically wedemonstrate that methods available for fast point multiplicationon elliptic curves such as mixed addition, signed digitrepresentations and Frobenius expansions, all transfer easily tothe quotient group, and provide a significant improvement over thearithmetic of the extension field. We also show that the naturalembedding of this group into the extension field may beinterpreted as a special representation of an algebraic torus,which for supersingular curves in characteristic three with MOVembedding degree six, permits a higher compression factor than ispossible in the quotient group. To illustrate the efficacy of ourmethods, we apply them to the basic arithmetic required inpairing-based cryptography using these curves.