Eta pairing computation on general divisors over hyperelliptic curves \(y^2=x^p - x+d\) (Q932799)

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 (Table 1) showing that the second is significantly faster and Section 6 provides experimental results that support the theoretical analysis of Section 5. Section 7 studies the curves \(y^2=x^5-x+d, d=1,2\), gives an algorithm for the Eta pairing computation (Algorithm 3) and does a similar study of its complexity.