Faster computation of the Tate pairing (Q2430985)

The paper proposes some improvements in the computation of the Tate pairing on elliptic curves \(E\),\, both in Weierstrass form and in Edwards form, curves defined over a non-binary finite field \(F_q\)\, and with even embedding degree (for a prime \(n|\sharp(E)\)\, the embedding degree \(k\),\, with respect to \(n\),\, is the multiplicative degree of \(q\)\, modulo \(n\)). For \(E\)\, in Weierstrass form, Miller's algorithm computes efficiently the Tate pairing, using the chord-and-tangent method for the addition and doubling of points. Section 3 presents new formulas for the addition and doubling steps in Miller's algorithm. Those formulas use a representation of the points of \(E\)\, in Jacobian coordinates \((X:Y:Z:T)\), \(T^2=Z\), and the paper gives its cost in term of the costs \(m,s,M,S\) of multiplication and squaring in \(\mathbb F_q\) and \(\mathbb F_{q^k}\). A twisted Edwards curve, introduced by \textit{D. J. Bernstein} et al. [in: AFRICACRYPT 2008. Casablanca, Morocco, 2008. Lect. Notes Comput. Sci. 5023, 389--405 (2008; Zbl 1142.94332)], is a curve giving by an equation: \(E_{\text{ad}}: ax^2+y^2=1+dx^2y^2\), whose (affine) points have efficient addition formulas. Since the equation of \(E_{\text{ad}}\) has degree four the chord-and-tangent geometric interpretation of the addition is not more valid, but section 4 of the paper gives (theorem 2) a new geometric interpretation of the addition law for \(E_{\text{ad}}\), and with this tool section 5 shows how to compute Tate pairing on twisted Edwards curves. Section 6 gives the comparison of the proposed formulas with others in the literature, as the paper of \textit{S. Ionica} and \textit{A. Joux} [in: INDOCRYPT 2008. Kharagpur, India, 2008. Lect. Notes Comput. Sci. 5365, 400--413 (2008; Zbl 1203.94104)], concluding that `` ... our new formulas for Edwards curves solidly beat all previous formulas published for Tate computation on Edwards curves'' and `` Our new formulas for pairings on arbitrary Edwards curves are faster than all formulas previously known for Weierstrass curves except for the very special curves with \(a_4=0\).''. Finally, sections 7 and 8 present construction and numerical examples (with embedding degree \(k=6,8,10,22\)) of pairing-friendly Edwards curves, examples covering the most common security levels.