Faster pairing computation on genus 2 hyperelliptic curves

In this paper, new efficient pairings on genus 2 hyperelliptic curves of the form C:y2=x5+axC:y2=x5+ax with embedding degree k   satisfying 4|k4|k are constructed, that is an improvement for the results of Fan et al. (2008) [10]. Then a variant of Millerʼs algorithm is given to compute our pairings. In this algorithm, we just need to evaluate the Miller function at two divisors for each loop iteration. However, Fan et al. had to compute the Miller function at four divisors. Moreover, compared with Fan et al.ʼs algorithm, the exponentiation calculation is simplified. We finally analyze the computational complexity of our pairings, which shows that our algorithm can save 2036m   operations in the base field or be 34.1%34.1% faster than Fan et al.ʼs algorithm. The experimental result shows that our pairing can achieve a better performance.

Research highlights
► New efficient pairings on genus 2 hyperelliptic curves are proposed.
► These pairings are an improvement for Fan et al.ʼs pairings.
► Our pairings have lower complexity and better performance than Fan et al.ʼs.