Double-Exponentiation in Factor-4 Groups and Its Applications

摘要

In previous work we showed how to compress certain prime-order subgroups of the cyclotomic subgroups of orders 2~(2m) + 1 of the multiplicative groups of (F_(2~(4m)))~* 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.