Pairings on Hyperelliptic Curves of Genus 2 at High Security Levels

Masahiro Ishii (1361001)


Pairings on hyperelliptic curves including elliptic curves have been applied to many cryptographic schemes (e.g., functional encryption and its varieties), and the various optimization methods that increase the speed of pairing computations have been exploited. In contrast to pairings on elliptic curves, hyperelliptic curves are not considered to be more efficient than elliptic curves for constructing general pairings. However, the extent of the difference between pairings on elliptic curves and pairings on genus 2 hyperelliptic curves has not been clarified.

In this presentation, constructions of efficient pairings on genus 2 curves for the high (i.e., 192- and 256-bit) security level are clarified. Specifically, several methods and the requirements for constructing a fast pairing with a pairing-friendly curve are organized in order to facilitate the selection of appropriate curves. We then showed that the Kawazoe-Takahashi families of curves are an optimum choice for an effective pairing at the high security levels. Various constructions of the pairings is analyzed carefully. We can see that the twisted Ate pairing for the curves is the best choice and offer the detailed computation cost. We will also report the results of implementation of our pairings with mcl which is a library to generate optimized code for performing arithmetic in finite fields and of elliptic curve.

Furthermore, a new variant of Weil pairing with an automorphism is proposed, and I also introduce an effective calculation method of it. This is the first detailed evaluation of pairings on genus 2 hyperelliptic curves at the high security levels.