# How do exactly twists interact with pairing and non-pairing computations?

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'}})$$?

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.
• 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? Commented Apr 20, 2023 at 10:12