**Factor-4 and 6 Compression of Cyclotomic Subgroups**

*Koray Karabina*

**Abstract: **Bilinear pairings derived from supersingular elliptic curves of embedding degrees 4 and 6 over finite fields of characteristic two and three, respectively, have been used to implement pairing-based cryptographic protocols. The pairing values lie in certain prime-order subgroups of certain cyclotomic subgroups. It was previously known how to compress the pairing values over characteristic two fields by a factor of 2, and the pairing values over characteristic three fields by a factor of 6. In this paper, we show how the pairing values over characteristic two fields can be compressed by a factor of 4. Moreover, we present and compare several algorithms for performing exponentiation in the prime-order subgroups using the compressed representations. In particular, in the case where the base is fixed, we expect to gain at least a 54% speed up over the fastest previously known exponentiation algorithm that uses factor-6 compressed representations.

**Category / Keywords: **Finite field compression, cyclotomic subgroups, pairing-based cryptography

**Date: **received 23 Jun 2009, last revised 27 Apr 2010

**Contact author: **kkarabin at uwaterloo ca

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20100427:195835 (All versions of this report)

**Short URL: **ia.cr/2009/304

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]