Cryptology ePrint Archive: Report 2006/125

Fast computation of Tate pairing on general divisors of genus 3 hyperelliptic curves

Eunjeong Lee and Hyang-Sook Lee and Yoonjin Lee

Abstract: For the Tate pairing computation over hyperelliptic curves, there are developments by Duursma-Lee and Barreto et al., and those computations are focused on {\it degenerate} divisors. As divisors are not degenerate form in general, it is necessary to find algorithms on {\it general} divisors for the Tate pairing computation. In this paper, we present two efficient methods for computing the Tate pairing over divisor class groups of the hyperelliptic curves $y^2 = x^p - x + d, ~ d = \pm 1$ of genus 3. First, we provide the {\it pointwise} method, which is a generalization of the previous developments by Duursma-Lee and Barreto et al. In the second method, we use the {\it resultant} for the Tate pairing computation. According to our theoretical analysis of the complexity, the {\it resultant} method is $48.5 \%$ faster than the pointwise method in the best case and $15.3 \%$ faster in the worst case, and our implementation result shows that the {\it resultant} method is much faster than the pointwise method. These two methods are completely general in the sense that they work for general divisors with Mumford representation, and they provide very explicit algorithms.

Category / Keywords: Tate pairing; hyperelliptic curves; divisors; resultant; pairing-based cryptosystem

Date: received 26 Mar 2006, last revised 15 Jun 2006

Contact author: hsl at ewha ac kr

Available formats: PDF | BibTeX Citation

Version: 20060616:054425 (All versions of this report)

Discussion forum: Show discussion | Start new discussion