Cryptology ePrint Archive: Report 2010/123

Delaying Mismatched Field Multiplications in Pairing Computations

Craig Costello and Colin Boyd and Juan Manuel Gonzalez Nieto and Kenneth Koon-Ho Wong

Abstract: Miller's algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field $\mathbb{F}_{p^k}$ are multiplied by elements contained in proper subfields $\mathbb{F}_{p^{k/d}}$, and by elements in the base field $\mathbb{F}_{p}$. We show that significant speedups in pairing computations can be achieved by delaying these ``mismatched'' multiplications for an optimal number of iterations. Importantly, we show that our technique can be easily integrated into traditional pairing algorithms; implementers can exploit the computational savings herein by applying only minor changes to existing pairing code.

Category / Keywords: Pairings, Miller’s algorithm, finite field arithmetic, Tate pairing, ate pairing.

Date: received 5 Mar 2010, last revised 7 Apr 2010

Contact author: craig costello at qut edu au

Available formats: PDF | BibTeX Citation

Version: 20100408:010042 (All versions of this report)

Discussion forum: Show discussion | Start new discussion