TY - JOUR
T1 - On small characteristic algebraic tori in pairing based cryptography
AU - Granger, Rob
AU - Page, Daniel
AU - Stam, Martijn
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
M3 - Article
VL - 9
SP - 64
EP - 85
JO - LMS Journal of Computation and Mathematics
JF - LMS Journal of Computation and Mathematics
SN - 1461-1570
ER -