Do Weil, Tate, and Ate pairings exist on all elliptic curves?

I don't know much about the math behind elliptic curves. Do Weil, Tate and Ate pairings exist on all elliptic curves? If the answer is negative, then what pairings do MNT, BN and SS curves have?

When we say that an elliptic curve has an embedding degree of $$k$$, do all these pairings map $$E(GF(p))$$ to $$GF(p^k)$$? Furthermore, when we speak of embedding degree, are we assuming a specific pairing?

Which of the Weil, Tate and Ate pairings is more efficient? Are there any security trade-offs between these pairings?

• comparing efficiency of various pairings on elliptic curves is not always easy. This recent taxonomy paper might contain some insights: eprint.iacr.org/2019/485 May 25, 2019 at 8:14

1 Answer

Yes. In fact, you can write the Weil and Ate pairings in terms of the Tate pairing.

Let $$E$$ be a curve over $$\mathbb{F}_p$$ of embedding degree $$k$$ and prime order $$r$$. The Weil pairing is related to the Tate pairing as $$e(P,Q)^\frac{p^k - 1}{r} = \frac{t(P, Q)}{t(Q, P)}\,,$$ where $$t(\cdot,\cdot)$$ is the Tate pairing. Likewise, we have $$a(Q, P)^{kp^{k-1} } = t(P, Q)^\frac{((t-1)^k - 1)}{r}\,,$$ where $$a$$ is the Ate pairing, and $$t$$ is the trace of Frobenius, i.e., $$t = p + 1 - \#E$$.

So for all common pairing-friendly curves, all of these pairings exist and are well-defined. The optimal Ate pairing is the most common, since it involves the shortest Miller loop and is often the fastest. But this is not necessarily the case, depending on field sizes, available parallelism, etc.

• That's a great response! What is Miller group? May 26, 2019 at 0:56
• Is optimal ate pairing the one that is implemented in all the pairing libraries like PBC, Relic and Miracl? May 26, 2019 at 0:57
• When we consider asymmetric pairings, then how can $t(P, Q)$ and $t(Q, P)$ exist at the same time? $P$ belongs to $G1$ and $Q$ belongs to $G2$ right? May 26, 2019 at 1:16
• Yes, the groups are switched in the definition of the (original) Ate pairing, i.e., the first element is in $G2$ and the second in $G1$. The Ate pairing also assumes that $P$ and $Q$ are in specific subgroups, so it is a little more specific than Tate, but this does not matter for the question at hand. May 26, 2019 at 1:32