Cryptology ePrint Archive: Report 2006/172
On Computing Products of Pairings
R Granger and N.P. Smart
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.
Category / Keywords: implementation / pairings
Date: received 17 May 2006, last revised 17 May 2006
Contact author: nigel at cs bris ac uk
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20060517:132259 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]