Eta pairing computation on general divisors over hyperelliptic curves \(y^2=x^p - x+d\)
type: Item
instance of: scholarly article
title: Eta pairing computation on general divisors over hyperelliptic curves \(y^2=x^p - x+d\)
zbMATH Open document ID: 1143.14020
author: Hyang-Sook Lee
author: Eunjeong Lee
author: Yoonjin Lee
published in: Journal of Symbolic Computation
publication date: 2008-07-11T00:00:00Z
review text: This paper provides some new methods to compute the Eta pairing over supersingular hyperelliptic curves of genus 2 and 3. The Tate pairing on elliptic and hyperelliptic curves is a central tool in pairing-based cryptography [see \textit{H. Cohen} et al., Handbook of elliptic and hyperelliptic curve cryptography, Chapman and Hall/CRC (2006; Zbl 1082.94001)]. Given the Jacobian \(J_H\) of an hyperelliptic curve \(H\) defined over a finite field \(\mathbb{F}_q\) and \(l\) a divisor of \(\sharp J_H(\mathbb{F}_q)\) (in cryptographic applications \(l\) is usually a large prime) with embedding degree \(k\) the Tate pairing is a bilinear map \(\tau_l\): \(J_H[l]\times J_H(\mathbb{F}_{q^k})/lJ_H(\mathbb{F}_{q^k}) \rightarrow \mathbb{F}^*_{q^k}/(\mathbb{F}^*_{q^k})^l\), \(\tau_l<D,E>=f_{l,D}(E')\), where \(f_{l,D}\) is a rational function and \(E'\sim E\). For \(H\) supersingular, \textit{P. S. L. M. Barreto} et al. [Des. Codes Cryptogr. 42(3), 239--271 (2007; Zbl 1142.14307)] defined the Eta pairing, which is very useful for the computation of the Tate pairing, to be \(\eta_T(D,E)=f_{T,D}(\psi(E))\), with \(T\in \mathbb{Z}\) and \(\mathbb{\psi}\) a \textit{distortion map}. The present paper deals with the Eta pairing computation over hyperelliptic curves \(y^2=x^p-x+d\), where \(p\) is an odd prime, defined over \(\mathbb{F}_{p^n}\) of genus 2 and 3 (therefore \(p=5,7\)). Section 2 gives an overview of Tate and Eta pairings and generalizes the Eta pairing approach to the case \(p\equiv 1 \bmod 4\) (in Barreto et al. only the case \(p\equiv 3 \bmod 4\) is considered). Sections 3 to 6 deal with the curves \(y^2=x^7-x\pm 1\). Section 3 describes a first algorithm (Algorithm 1) for the Eta pairing computation, generalization for general divisors \(D,E\) of the pointwise method of Barreto et al. (who only consider \textit{degenerate} divisors), while Section 4 presents a second method (Algorithm 2) using Resultants. Section 5 compares the computational cost of both algorithms (Ta…
Mathematics Subject Classification ID: 14G15
Mathematics Subject Classification ID: 14H40
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 5300760
zbMATH Keywords: Tate pairing
zbMATH Keywords: hyperelliptic curves
zbMATH Keywords: divisors
zbMATH Keywords: resultant
zbMATH Keywords: pairing-based cryptography
reviewed by: Juan Tena Ayuso
describes a project that uses: SINGULAR
describes a project that uses: NTL
MaRDI profile type: Publication
full work available at URL: j.jsc.2007.07.010
OpenAlex ID: W1975344255
cites work: Q4409129
cites work: Efficient pairing computation on supersingular abelian varieties
cites work: Factoring Polynomials Over Large Finite Fields
cites work: Q4783728
cites work: An Identity-Based Signature from Gap Diffie-Hellman Groups
cites work: Information Security and Cryptology - ICISC 2003
cites work: Advances in Cryptology - ASIACRYPT 2003
cites work: Q4485860
cites work: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
cites work: Q4737495
cites work: Ate Pairing on Hyperelliptic Curves
cites work: The Eta Pairing Revisited
cites work: Q5585020
cites work: Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
cites work: Cryptography and Coding
cites work: Formulae for arithmetic on genus 2 hyperelliptic curves
cites work: Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura
cites work: Selected Areas in Cryptography
cites work: Q4250782
cites work: Identity-based authenticated key agreement protocol based on Weil pairing
cites work: Q4953977
DOI: 10.1016/J.JSC.2007.07.010
Recommended article: Eta Pairing Computation on General Divisors over Hyperelliptic Curves y 2 = x 7 − x ±1
Recommended article: TATE PAIRING COMPUTATION ON THE DIVISORS OF HYPERELLIPTIC CURVES OF GENUS 2
Recommended article: Advances in Cryptology - ASIACRYPT 2003
Recommended article: Optimal Eta Pairing on Supersingular Genus-2 Binary Hyperelliptic Curves
Recommended article: Pairings on hyperelliptic curves
Recommended article: On the analogue of the division polynomials for hyperelliptic curves.
Recommended article: Formulae for Computation of Tate Pairing on Hyperelliptic Curve Using Hyperelliptic Nets
Recommended article: Ate Pairing on Hyperelliptic Curves
Recommended article: Computing local \(p\)-adic height pairings on hyperelliptic curves
Recommended article: Improved divisor arithmetic on generic hyperelliptic curves
description: scientific article; zbMATH DE number 5300760