Faster pairing computation on genus 2 hyperelliptic curves

• Published in: Information processing letters 2011-04, Vol.111 (10), p.494-499
• Main Authors: Tang, Chunming, Xu, Maozhi, Qi, Yanfeng
• Format: Article
• Language: English
• Subjects: Algebra; Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Comparative analysis; Computation; Computer science; control theory; systems; Cryptography; Data encryption; Efficiently computable endomorphisms; Exact sciences and technology; Genus 2 hyperelliptic curves; Mathematical functions; Mathematics; Miscellaneous; Number theory; Pairing computation; Pairing-based cryptography; Sciences and techniques of general use; Studies; Theoretical computing
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2011.02.011

In this paper, new efficient pairings on genus 2 hyperelliptic curves of the form C : y 2 = x 5 + a x with embedding degree k satisfying 4 | 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 2036 m operations in the base field or be 34.1 % faster than Fan et al.ʼs algorithm. The experimental result shows that our pairing can achieve a better performance. ► 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.