Faster computation of the Tate pairing

Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50) Cryptography (94A60)

Abstract: This paper proposes new explicit formulas for the doubling and addition step in Miller's algorithm to compute the Tate pairing. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in the addition and doubling. Computing the coefficients of the functions and the sum or double of the points is faster than with all previously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also speed up pairing computation on Weierstrass curves in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.

Review text

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.

Recommendations

Cites work

Cited in

(45)

Describes a project that uses

Uses Software

This page was built for publication: Faster computation of the Tate pairing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2430985)