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?

  • $\begingroup$ 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 $\endgroup$ – Geoffroy Couteau May 25 '19 at 8:14

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.

  • $\begingroup$ That's a great response! What is Miller group? $\endgroup$ – satya May 26 '19 at 0:56
  • $\begingroup$ Is optimal ate pairing the one that is implemented in all the pairing libraries like PBC, Relic and Miracl? $\endgroup$ – satya May 26 '19 at 0:57
  • $\begingroup$ 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? $\endgroup$ – satya May 26 '19 at 1:16
  • $\begingroup$ 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. $\endgroup$ – Samuel Neves May 26 '19 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.