On Small Characteristic Algebraic Tori in Pairing Based CryptographyRobert Granger, Dan Page, Martijn Stam, On Small Characteristic Algebraic Tori in Pairing Based Cryptography. LMS Journal of Computation and Mathematics, 9, pp. 64–85. March 2006. No electronic version available.
The output of the Tate pairing on an elliptic curve over a finite field is an element in the multiplicative group of an extension field modulo a particular subgroup. One ordinarily powers this element to obtain a unique representative for the output coset, and performs any further necessary arithmetic in the extension field. Rather than an obstruction, we show to the contrary that one can exploit this quotient group to eliminate the final powering, to speed up exponentiations and to obtain a simple compression of pairing values which is useful during interactive identity-based cryptographic protocols. Specifically we demonstrate that methods available for fast point multiplication on elliptic curves such as mixed addition, signed digit representations and Frobenius expansions, all transfer easily to the quotient group, and provide a significant improvement over the arithmetic of the extension field. We also show that the natural embedding of this group into the extension field may be interpreted as a special representation of an algebraic torus, which for supersingular curves in characteristic three with MOV embedding degree six, permits a higher compression factor than is possible in the quotient group. To illustrate the efficacy of our methods, we apply them to the basic arithmetic required in pairing-based cryptography using these curves.