Optimal TNFS-secure pairings on elliptic curves with even embedding degree

In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible 128-bit TNFS-secure families of elliptic curves computed by Fotiadis and Konstantinou; we compute the optimal choice for each family together with the fastest curve shape/pairing combination. Comparing the nine best choices from the nine families gives a optimal choice of elliptic curve, shape and pairing (given current knowledge of TNFS-secure families). We also present a proof-of-concept MAGMA implementation for each case. Additionally, we give the first analysis, to our knowledge, of the use of quadratic twists of both Jacobi Quartic and Edwards curves for pairings on $\mathbb{G}_2 \times \mathbb{G}_1$, and of the use of sextic twists on Jacobi Quartic curves on $\mathbb{G}_1 \times \mathbb{G}_2$.