Cryptology ePrint Archive: Report 2010/559

Optimal Eta Pairing on Supersingular Genus-2 Binary Hyperelliptic Curves

Diego F. Aranha and Jean-Luc Beuchat and Jérémie Detrey and Nicolas Estibals

Abstract: This article presents a novel pairing algorithm over supersingular genus-$2$ binary hyperelliptic curves. Starting from Vercauteren's work on optimal pairings, we describe how to exploit the action of the $2^{3m}$-th power Verschiebung in order to reduce the loop length of Miller's algorithm even further than the genus-$2$ $\eta_T$ approach. As a proof of concept, we detail an optimized software implementation and an FPGA accelerator for computing the proposed optimal Eta pairing on a genus-$2$ hyperelliptic curve over $\mathbb{F}_{2^{367}}$, which satisfies the recommended security level of $128$ bits. These designs achieve favourable performance in comparison with the best known implementations of $128$-bit-security Type-1 pairings from the literature.

Category / Keywords: public-key cryptography / Optimal Eta pairing, supersingular genus-2 curve, software implementation, FPGA implementation

Date: received 2 Nov 2010, last revised 23 Nov 2011

Contact author: Jeremie Detrey at loria fr

Available format(s): PDF | BibTeX Citation

Note: Updated version, incorporating remarks and comments from anonymous Eurocrypt and CT-RSA reviewers.

Version: 20111123:201430 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]