Computing bilinear pairings on elliptic curves with automorphisms (Q629880)

The paper proposes a new pairing, easier to compute, defined on some particular elliptic curves. Due to their use in Pairing-based Cryptography bilinear pairings are today an important tool in cryptographic protocols. The classical Weil and Tate pairings can be efficiently computed using Miller's algorithm, see [\textit{H. Cohen} et al., Handbook of elliptic and hyperelliptic curve cryptography. Discrete Mathematics and its Applications. Boca Raton, FL: Chapman \& Hall/CRC. (2006; Zbl 1082.94001)]. The desire to shorten the loop length in Miller's algorithm has motivated the recent proposal of new variants of pairings (eta, ate, R-ate, etc). Based on a previous work of \textit{M. Scott} [Progress in cryptology -- INDOCRYPT 2005. 6th international conference on cryptology in India, Bangalore, India, December 10--12, 2005, Proceedings. Berlin: Springer. Lecture Notes in Computer Science 3797, 258--269 (2005; Zbl 1153.94429)], who constructed a bilinear pairing on pairing-friendly curves with embedding degree 2, the present paper introduces a new variant, the omega pairing, defined on elliptic curves with non-trivial automorphisms and low embedding degree, in fact the families of curves with \(j\)-invariant 0, \(E_1: y^2= x^3+B\), defined over \(\mathbb{F}_p,\,\, p \equiv 1 \bmod 3\) and \(j\)-invariant 1728, \(E_2:y^2=x^3+Ax\), defined over \(\mathbb{F}_p,\,\, p \equiv 1 \bmod 4\). Section 3 presents details of the omega pairing (for embedding degree 2) and gives an algorithm allowing its computation. This algorithm requires the simple final exponentiation and short loop length in Miller's algorithm. Section 4 compares the implementation of the omega and Scott pairings, concluding that ``experimental results indicate that the omega pairing is about \(22\%\) faster and \(19\%\) faster that the previous fastest pairing in affine coordinate systems and projective coordinate systems, respectively.''