This questions builds up on [1]. I've got a problem to evaluate a pairing, I don't get, on which field which operation operates.
Lets have a look on the optimal Ate pairing, as presented in [1] (cpy-pst for instance)
Optimal Ate Pairing
Consider the curve $\newcommand{\F}{\mathbb F}E(\F_p):\ y^2=x^3+x$ and its quartic twist $E'(\F_{p^4}):\ y^2= x^3+2^{1/4}x$. For computing the optimal Ate pairing $$e_{opt}:\ E(\F_p)[r]\times E'(\F_{p^4})[r]\cap Ker(\pi_p-p) \to \F_{p^{16}}\cap \mu_r\\ (P,Q) \mapsto \left( (f_{u,Q}(P)\cdot l_{uQ,pQ}(P) )^{p^3} \cdot l_{Q,Q}(P) \right)^{\frac{p^{16}-1}{r}}$$ where $p$ is parameterized as a polynomial and evaluated at "$u$" as a prime. Furthermore, $E[r]$ describes all points P on E, with $rP=\mathcal O$. $Ker(\pi_p-p)$ is just a Eigenspace of $\pi_p$, the p-Frobenius. [1, Proposition 2]
Computing the optimale Ate pairing
I describe the parts, where I am sure, how to deal with.
For computing the optimal Ate, we use in the first step the Miller-Loop, which outputs $f_{u,Q}(P)$. I guess: This is an element of $\F_{p^{16}}$.
As a side result of that Miller-function, we also get the point $A=uQ$. $B=pQ$ is derived from the Curve-p-Frobenius with $p\cdot (x,y) = (x^p,y^p)$. Since $Q\in E'$, we need to use the $p$-Frob. over $\F_{p^4}$. Now we need to evaluate the line through $A, B\in E'$ in a point $P\in E$. The output of that evaluation is $l_{A,B}(P)$. I guess: This is an element of $\F_{p^{16}}$. If not, how to define the multiplication? When I take a look on the values, that got multiplied, there is no way to reach the finite field of $p^{16}$ elements.
To compute the power $p^3$ we need to compute the product $f_{u,Q}(P)l_{A,B}(P)$ over $\F_{p^{16}}$ and apply the $p^3$-Frobenius. Lets define this output with $FL_p$.
Now we need to evaluate $P$ at the tangent line. This time, we have $A=B=Q$. The same problem appears.
The final step of pre-calculations is done, by computing the product $FL_p\cdot l_{Q,Q}(P)$.
The final exponentiation is clearly done over $\F_{p^{16}}$.
Question
- As you can see, my problems are really basically. Could someone clear me up?
- $E'(\F_{p^4})$ is a twist of $E(\F_{p^{16}})$? Am I allowed to do $\F_{p^4}=\F_p[x]/(x^4-2)$ and in the same meaning, but no touching point $\F_{p^{16}}=\F_p[t]/(t^{16}-2)$? I do not see any point, that would be critical.
- While the Miller-loop I have to do lots of scalar multiplications. In which bit-order do those $k$ appear? As I can see, I only will need 32-bit as a boundary.
$\newcommand{\F}[1]{\mathbb F_{p^{#1}}}$It is because of the twist.
So if we specify a pairing $e:\ G_1 \times G_2 \to G_T$, then we have $G_1 = E(\F{})[r] \cap ker(\pi_p-1)$, $G_2 = E(\F{16})[r]\cap ker(\pi_p-p)$ and $G_T = \F{16}^*\cap \mu_r$, where $\mu_r$ is the field of r-th roots of unity.
So the given curve is of $E: y^2=x^3+ax$ style, therefore, we have a quartic twist given by the isomorphism $\psi: G_2 \to G_2'$, where $G_2' = E'(\F{4})[r]\cap \ker (\pi_p-p)$. The inverse is given by $\psi^{-1}:\ G'_2\to G_2$. The image of a point is given by: $\psi: (x_p,y_p) \mapsto (x'_p\cdot \xi^{1/2}, y'_p\cdot \xi^{3/4})$. (in affine coordinates..)
The line evaluation is done, by applying $\psi_{proj}$ first (you could take a similar definition of $\psi_{proj}$ on projective coordinates) evaluate the line, and apply $\psi_{proj}^{-1}$ again.
Example
Lets consider $(x_q,y_q,z_q)=Q\in G_2$ and $(x_p,y_p,z_p)=P\in G_1$. The line evaluation is done, by $$l_{Q,Q}(P) = -2(3x_q^2z_q + az_q^3)x_p + (4y_qz_q)y_p + 2(x_q^3-az_q^2x_q)$$ where $a$ comes from the curve definition.
So lets have a closer look on each summand. The used $x_q,y_q,z_q\in\F{4}$ and $x_p,y_p\in \F{}$ So the product hast to be interpreted over $\F{4}$. If we consider a computer language and their syntax, we need to lift $P$. Since $P=( [0,0,0,P.x^0], [0,0,0,P.y^0] )$, whereas $Q=([Q.x^3, ..., Q.x^0],[Q.y^3,...,Q.y^0])$. When we have computed each summand, we may use $\psi^{-1}$ to twist backwards and compute the sums. So we get a $\F{16}$ element.
Still unsure:
Am I right to lift the coordinate of $P$ to elements of $\F{4}$? Well $\F{}\subset \F{4}$, and I guess (!), that the multiplication is inherited from $\F4$.