Cryptology ePrint Archive: Report 2004/375

Efficient Pairing Computation on Supersingular Abelian Varieties

Paulo S. L. M. Barreto and Steven Galbraith and Colm O hEigeartaigh and Michael Scott

Abstract: We present a general technique for the efficient computation of pairings on supersingular Abelian varieties. This formulation, which we call the eta pairing, generalises results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic three.

We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma-Lee method.

These ideas are then used for elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.

Category / Keywords: public-key cryptography / Tate pairing, supersingular curves, pairing-based cryptosystem, efficient algorithms

Date: received 1 Jan 2005, last revised 5 Sep 2005

Contact author: pbarreto at larc usp br

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Improved presentation of all algorithms to compute the eta_T pairing.

Version: 20050905:142955 (All versions of this report)

Short URL: ia.cr/2004/375

Discussion forum: Show discussion | Start new discussion