Paper 2006/125

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

Eunjeong Lee, 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Tate pairinghyperelliptic curvesdivisorsresultantpairing-based cryptosystem
Contact author(s)
hsl @ ewha ac kr
History
2006-06-16: last of 3 revisions
2006-03-30: received
See all versions
Short URL
https://ia.cr/2006/125
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/125,
      author = {Eunjeong Lee and Hyang-Sook Lee and Yoonjin Lee},
      title = {Fast computation of Tate pairing on general divisors of genus 3 hyperelliptic curves},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/125},
      year = {2006},
      url = {https://eprint.iacr.org/2006/125}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.