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

Question

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?

Answer 1

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.