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 format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060517:132259 (All versions of this report)

Short URL: ia.cr/2006/172

Discussion forum: Show discussion | Start new discussion