Say that $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$ are cyclic groups of prime order $r$ over which the pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ is defined. It is well known that $\mathbb{G}_1 \subseteq E(\mathbb{F}_p)$ and $\mathbb{G}_2 \subseteq E(\mathbb{F}_{p^k})$ where $p$ is a prime number and $k$ is the embedding degree of the elliptic curve $E(\mathbb{F}_{p^k})$. It is also known that $E$ admits a twisted curve $E'(\mathbb{F}_{p^{k'}})$, that is, another curve which is isomorphic to $E$ that is defined over an extension field $\mathbb{F}_{p^{k'}}$ such that $1 \leq k' < k$, so working over $\mathbb{G}_2' \subseteq E'(\mathbb{F}_{p^k})$ and then mapping back to $\mathbb{G}_2$ has turned to be useful in practice.

What I am lacking to understand is how and when this twist is applied before, during and after the pairing computation. Say that we want to compute $e(P,Q)$, where $Q = aQ_1 + Q_2$ and $a \in \mathbb{F}_r$ (or any other more complex operation over the elliptic curve):

  1. Before. Should the sum $aQ_1 + Q_2$ occur over the curve $E(\mathbb{F}_{p^k})$ or the curve $E'(\mathbb{F}_{p^{k'}})$?
  2. During. Should the pairing computation $e(P,Q)$ occur with $Q \in E(\mathbb{F}_{p^k})$ or $E \in E'(\mathbb{F}_{p^{k'}})$? I think that elliptic curve operations inside the pairing can be over $E'(\mathbb{F}_{p^{k'}})$ for efficiency, while finite field operations should happen over $\mathbb{F}_{p^k}.$
  3. After. After the computation in 2, say we have to perform elliptic curve operations as part of a protocol. Should these operations happen over $E(\mathbb{F}_{p^k})$ or the curve $E'(\mathbb{F}_{p^{k'}})$?

1 Answer 1


The answer is During. To improve efficiency it's better to be as "lazy" as possible, that is, only map back to $E(\mathbb{F}_{p^k})$ when strictly needed, which happens inside the Miller loop in the pairing computation.

Each iteration of the Miller loop requires a point doubling and possibly a point addition (it's very similar to a point multiplication algorithm). These can be done in $E'(\mathbb{F}_{p^{k'}})$, which is much faster. Also, in each iteration, you need to evaluate a line function at that point. This is where you finally map the point back form the twist to the original curve, and use its coordinates as input to the line function.

  • $\begingroup$ Perfect! So I assume that in "before" and "after" you can operate over $E'(\mathbb{F}_{p^{k'}})$, since the twist is, in particular, a group homomorphism, right? $\endgroup$
    – Bean Guy
    Apr 20 at 10:12
  • 1
    $\begingroup$ @BeanGuy Exactly, and it's much more efficient to operate over it since the field is smaller. $\endgroup$
    – Conrado
    Apr 20 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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