Cryptology ePrint Archive: Report 2003/242

Improved Weil and Tate pairings for elliptic and hyperelliptic curves

Kirsten Eisentraeger and Kristin Lauter and Peter L. Montgomery

Abstract: We present algorithms for computing the {\it squared} Weil and Tate pairings on an elliptic curve and the {\it squared} Tate pairing for hyperelliptic curves. The squared pairings introduced in this paper have the advantage that our algorithms for evaluating them are deterministic and do not depend on a random choice of points. Our pairings save about 20-30\% over the usual pairings.

Category / Keywords: implementation / pairing-based cryptography

Publication Info: to appear in the proceedings of ANTS-6 (Algorithmic Number Theory Symposium)

Date: received 21 Nov 2003, last revised 4 Mar 2004

Contact author: klauter at microsoft com

Available formats: PDF | BibTeX Citation

Note: version revised for publication, references added

Version: 20040304:230118 (All versions of this report)

Discussion forum: Show discussion | Start new discussion