Efficient computation of pairings on Jacobi quartic elliptic curves (Q490338): Difference between revisions

The article is devoted to describe and analyze an algorithm for the computation of pairings on the Jacobi quartic elliptic curve \(E_d\) defined by \(Y^2=dX^4+Z^4\) over a finite field \(\mathbb{F}_q\) of characteristic \(p\geq 5\) not congruent to 3 modulo 4. Let \(E\) be an elliptic curve defined over \(\mathbb{F}_q\) and denote by \(E(\mathbb{F}_q)\) the group of \(\mathbb{F}_q\)-rational points of \(E\). Let \(r\) be a prime divisor of the group order \(\#E(\mathbb{F}_q)\) and \(k\) the embedding degree of \(E\) with respect to \(r\), that is, the smallest integer for which \(r\) divides \(q^k-1\). The set of \(r\)-torsion points \(E(\overline{\mathbb{F}}_q)[r]\) with coordinates in an algebraic closure \(\overline{\mathbb{F}}_q\) of \(\mathbb{F}_q\) is contained in \(E(\mathbb{F}_{q^k})\). The reduced pairing \(e_r:E(\mathbb{F}_q)[r]\times E(\mathbb{F}_{q^k})[r]\to\mu_r\) is a bilinear and non-degenerate map on the group \(\mu_r\) of \(r\)th roots of unity in \(\mathbb{F}^*_{q^k}\). The paper under review is concerned with the computation of the Tate pairing \(e_r\), as well as Ate, twisted Ate and optimal pairings, on the Jacobi quartic elliptic curve \(E_d\). For this purpose, the authors consider the Miller algorithm, an efficient method which requires the computation of addition and doubling in \(E(\mathbb{F}_{q^k})[r]\) ([\textit{V. Miller}, \url{http://crypto.stanford.edu/miller/miller.pdf}]). In [Chin. J. Electronics 20, No. 4, 655--661 (2011), \url{http://eprint.iacr.org/2010/475.pdf}], H. Wang et al. presented a geometric interpretation of the group law on Jacobi quartic curves which leads to an improvement of Miller's algorithm for this kind of curves. In the article under review a further interpretation of the group law is obtained, which is based on the birational equivalence between Jacobi quartic curves and Weierstrass curves. This allows the authors to improve the results of H. Wang et al. [loc. cit.], for the case of the curves \(E_d\). The authors describe the formulas for the group law obtained with their interpretation, as well as those for the Ate pairing, twisted Ate pairing and optimal pairing, and analyze the cost of the resulting algorithm. They also compare their algorithm for the different pairings under consideration with those on Weierstrass elliptic curves with quartic twists. Finally, the authors provide an explicit example of optimal pairing on a family of Jacobi quartic curves with embedding degree 8.