Cryptology ePrint Archive: Report 2007/429

On compressible pairings and their computation

Michael Naehrig and Paulo S. L. M. Barreto and Peter Schwabe

Abstract: In this paper we provide explicit formul\ae\ to compute bilinear pairings in compressed form. We indicate families of curves where the proposed compressed computation method can be applied and where particularly generalized versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. Our approach introduces more flexibility when trading off computation speed and memory requirement. Furthermore, compressed computation of reduced pairings can be done without any finite field inversions. We also give a performance evaluation and compare the new method with conventional pairing algorithms.

Category / Keywords: public-key cryptography / pairing-based cryptography, compressible pairings, algebraic tori, Tate pairing, Eta pairing, Ate pairing, twists

Date: received 16 Nov 2007, last revised 14 Mar 2008

Contact author: mnaehrig at ti rwth-aachen de

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

Note: Included implementation and timing results.

Version: 20080314:155727 (All versions of this report)

Short URL: ia.cr/2007/429