CryptoDB
Fast computation of Tate pairing on general divisors of genus 3 hyperelliptic curves
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2006-21618,
title={Fast computation of Tate pairing on general divisors of genus 3 hyperelliptic curves},
booktitle={IACR Eprint archive},
keywords={Tate pairing; hyperelliptic curves; divisors; resultant; pairing-based cryptosystem},
url={http://eprint.iacr.org/2006/125},
note={ hsl@ewha.ac.kr 13315 received 26 Mar 2006, last revised 15 Jun 2006},
author={Eunjeong Lee and Hyang-Sook Lee and Yoonjin Lee},
year=2006
}