Cryptology ePrint Archive: Report 2009/475

Double-Exponentiation in Factor-4 Groups and its Applications

Koray Karabina

Abstract: In previous work we showed how to compress certain prime-order subgroups of certain cyclotomic subgroups by a factor of 4. We also showed that single-exponentiation can be efficiently performed using compressed representations. In this paper we show that double-exponentiation can be efficiently performed using factor-4 compressed representation of elements. In addition to giving a considerable speed up to the previously known fastest single-exponentiation algorithm for general bases, double-exponentiation can be used to adapt our compression technique to ElGamal type signature schemes.

Category / Keywords: public-key cryptography / Finite field compression, cyclotomic subgroups, double-exponentiation

Date: received 25 Sep 2009

Contact author: kkarabin at uwaterloo ca

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

Version: 20090926:044920 (All versions of this report)

Short URL: ia.cr/2009/475

Discussion forum: Show discussion | Start new discussion