Fast Parallel Computation of Multi-Exponentiation for Public Key Cryptosystems

Chin Chen Chang*, Der Chyuan Lou

*Corresponding author for this work

Research output: Contribution to conferenceConference Paperpeer-review

3 Scopus citations

Abstract

Multi-exponentiation may be performed faster than the traditional multiple square and multiply method by rearranging the exponentiation in an efficient sequence. For a suitable choice of such sequences, the resulting multi-exponentiation reduces the expected number of non-squaring multiplications at the cost of a rearrangement. Rearrangement effort depends entirely on the exponent and can be kept down to the work saved in a single exponentiation. Some methods of fast exponentiation have been proposed in the past years to make the implementation of public key cryptosystems easier; however, there are only a few parallel mechanisms for evaluating the modular multi-exponentiation. In this paper, we propose a parallel algorithm for modular multi-exponentiation. A fast and efficient implementation for this new parallel algorithm is also sketched. Besides, our parallel algorithm can be employed with other existing methods for further speedup. Both hardware and software implementations of the multi-exponentiation can benefit from this algorithm.

Original languageEnglish
Pages955-958
Number of pages4
StatePublished - 2003
Externally publishedYes
EventParallel and Distributed Computing, Applications and Technologies, PDCAT 2003 Proceedings - Chengdu, China
Duration: 27 08 200329 08 2003

Conference

ConferenceParallel and Distributed Computing, Applications and Technologies, PDCAT 2003 Proceedings
Country/TerritoryChina
CityChengdu
Period27/08/0329/08/03

Keywords

  • Modular multi-exponentiation
  • Parallel processing
  • Public key cryptosystem

Fingerprint

Dive into the research topics of 'Fast Parallel Computation of Multi-Exponentiation for Public Key Cryptosystems'. Together they form a unique fingerprint.

Cite this