International Association for Cryptologic Research

International Association
for Cryptologic Research


On Computing Products of Pairings

R Granger
Nigel P. Smart
Search ePrint
Search Google
Abstract: In many pairing-based protocols often the evaluation of the product of many pairing evaluations is required. In this paper we consider methods to compute such products efficiently. Focusing on pairing-friendly fields in particular, we evaluate methods for the Weil, Tate and Ate pairing algorithms for ordinary elliptic curves at various security levels. Our operation counts indicate that the minimal cost of each additional pairing relative to the cost of one is $\approx 0.61$, $0.45$, and $0.43$, for each of these pairings respectively at the 128-bit security level. For larger security levels the Ate pairing can have a relative additional cost of as low as $0.13$ for each additional pairing. These estimates allow implementors to make optimal algorithm choices for given scenarios, in which the number of pairings in the product, the security level, and the embedding degree are factors under consideration.
  title={On Computing Products of Pairings},
  booktitle={IACR Eprint archive},
  keywords={implementation / pairings},
  note={ 13285 received 17 May 2006, last revised 17 May 2006},
  author={R Granger and Nigel P. Smart},