I was given the following explaination, some parts of it are wrong but others looks truethefull:
Here is the rigorous mathematical explanation of why this technique works.
The validity of the formula $A = Z^{\frac{2}{1-p^6}}$ relies on Galois Theory applied to the tower of finite fields constructed by the embedding degree $k=12$ and the existence of a Sextic Twist.
1. The Algebraic Setup
Let $E$ be a BN or BLS12 curve defined over the prime field $\mathbb{F}_p$.
- Embedding Degree $k=12$: The pairing target group is a subgroup of the multiplicative group $\mathbb{F}_{p^{12}}^*$.
- Order $r$: The prime order of the subgroups $G_1$ and $G_2$.
- Groups:
- $G_1 = E(\mathbb{F}_p)[r]$ (Points with coordinates in the base field).
- $G_2 \subset E(\mathbb{F}_{p^{12}})[r]$ is the trace-zero subgroup, which is isomorphic to $E'(\mathbb{F}_{p^2})[r]$ via a sextic twist.
We define the Weil Pairing $e_W: G_1 \times G_2 \to \mu_r$, where $\mu_r$ is the group of $r$-th roots of unity in $\mathbb{F}_{p^{12}}$. $$Z = e_W(P, Q) = (-1)^r \frac{f_P(Q)}{f_Q(P)}$$ Let $A = f_P(Q)$ and $B = f_Q(P)$.
2. Lemma 1: Field Membership of the Denominator
Theorem: For $P \in G_1$ and $Q \in G_2$, the value $B = f_Q(P)$ lies in the subfield $\mathbb{F}_{p^2}$.
Proof:
- Miller Loop Construction: The function $f_Q$ is a rational function on the curve constructed via Miller's algorithm. The coefficients of $f_Q$ are arithmetic combinations of the coordinates of $Q$ and the curve parameters.
- The Twist: Since $Q \in G_2$, it is the image of a point $Q' \in E'(\mathbb{F}_{p^2})$ under the twisting isomorphism $\psi: E' \to E$. Consequently, the coordinates of $Q$ (and the line functions used to build $f_Q$) are defined over $\mathbb{F}_{p^2}$ (up to scaling factors that cancel out or remain in the subfield during the accumulation step).
- Evaluation Point: The function $f_Q$ is evaluated at $P$. Since $P \in E(\mathbb{F}_p)$, its coordinates $x_P, y_P$ are in $\mathbb{F}_p$.
- Closure: $\mathbb{F}_p$ is a subfield of $\mathbb{F}_{p^2}$. Therefore, evaluating a function with coefficients in $\mathbb{F}_{p^2}$ at a point in $\mathbb{F}_p$ yields a result in $\mathbb{F}_{p^2}$.
Conclusion: $B \in \mathbb{F}_{p^2}$.
3. The Typical Trap (Why Miller Inversion is usually not enough)
In a generic scenario (or on curves without the specific Type 3 / Twist structure), having an algorithm that inverts the Miller loop (finding $Y$ from $f_X(Y)$) is insufficient to invert the Weil pairing.
The Problem: You are given the target $Z_{Weil}$. The equation is: $$Z_{Weil} = \frac{f_X(Y)}{f_Y(X)}$$
To use your Miller Inversion algorithm, you need to isolate the numerator $f_X(Y)$. You would try to rearrange the equation: $$f_X(Y) = Z_{Weil} \cdot f_Y(X)$$
The Circular Deadlock:
- To find $Y$ using, you need the value of the Right Hand Side.
- But the Right Hand Side contains $f_Y(X)$.
- The value of $f_Y(X)$ depends on $Y$.
- Result: You cannot calculate the input for your inversion algorithm without already knowing the answer $Y$.
In standard literature, resolving this dependency ($Y$ appearing in both numerator and denominator) generally requires guessing bits of $Y$ or solving a Discrete Logarithm, which drives the complexity up to exponential levels.
4. Why It Is Easy Here (The Algebraic Coupling)
In your specific case (BN curves), the denominator is not an independent variable. It is algebraically coupled to the numerator via the Frobenius automorphism.
Because $G_2$ comes from a twist over a subfield, we proved that: $$f_Y(X) = (f_X(Y))^{p^6}$$
This substitution breaks the circular dependency by turning the equation into a single variable problem.
The Subfield Trick (Why the denominator is dependent) On a BN curve (Type 3), the points are separated:
- $X \in G_1$ is defined over the base field $\mathbb{F}_p$.
- $Y \in G_2$ is defined over the twist $\mathbb{F}_{p^2}$.
Let's look at the two Miller loops composing your Weil target:
- Numerator $A = f_X(Y)$: This is a function derived from $X$ ($\mathbb{F}_p$) evaluated at $Y$ ($\mathbb{F}_{p^{12}}$). The result lives in the full extension $\mathbb{F}_{p^{12}}$.
- Denominator $B = f_Y(X)$: This is a function derived from $Y$ (coefficients in $\mathbb{F}_{p^2}$) evaluated at $X$ ($\mathbb{F}_p$).
- Crucial Consequence: The result $B$ belongs to the subfield $\mathbb{F}_{p^2}$ (embedded in $\mathbb{F}_{p^{12}}$).
For the inversion algorithm (which works on the full $\mathbb{F}_{p^{12}}$ structure), the denominator is a "small" structural element compared to the complexity of the numerator.
The Power Relation (The constant $\lambda$)
On BN curves, the Weil Pairing $e_W(X, Y)$ and the Tate Pairing/Miller Loop $f_X(Y)$ are linked by a fixed and known power relation for all points in the group.
$$e_W(X, Y) = (f_X(Y))^{\lambda}$$
- Why? Because the denominator $f_Y(X)$ is linked to the numerator via the Frobenius endomorphism (anti-trace).
- The value of $\lambda$: This is not a secret. It is an integer that depends solely on the curve parameters. On many BN curves, this is linked to $(1 - p^6)$.
The Polynomial Reduction: Instead of: $$Z_{Weil} = \frac{\text{Unknown}_1(Y)}{\text{Unknown}_2(Y)}$$
You have: $$Z_{Weil} = \frac{\text{Unknown}_1(Y)}{(\text{Unknown}_1(Y))^{p^6}} = \text{Unknown}_1(Y)^{1-p^6}$$
The Solution Path: Since $(1-p^6)$ is a known constant integer, you can simply invert this exponent modulo $r$: $$f_X(Y) = (Z_{Weil})^{(1-p^6)^{-1} \pmod r}$$
The $p^6$ Frobenius Trick (Conjugation)
In the field $\mathbb{F}_{p^{12}}$, the operation $x \mapsto x^{p^6}$ acts as a complex conjugation relative to the quadratic extension.
Property of the Result $Z$ (Pairing): $Z$ is an $r$-th root of unity. On BN curves, modulo the order $r$, we have $p^6 \equiv -1$. Therefore, for any valid pairing result $Z$: $$Z^{p^6} = Z^{-1}$$
Property of the Denominator $B$: Since $B \in \mathbb{F}_{p^2}$, it is invariant under $x \mapsto x^{p^2}$. A fortiori, it is invariant under $x \mapsto x^{p^6}$ (since $p^6$ is a multiple of $p^2$). $$B^{p^6} = B$$
3. Solving the Equation
We have the following system:
- $Z = A / B$
- $Z^{-1} = Z^{p^6}$ (Target group property)
- $B^{p^6} = B$ (Subfield property)
Apply the Frobenius $p^6$ to equation (1): $$Z^{p^6} = \frac{A^{p^6}}{B^{p^6}}$$
Substitute using properties (2) and (3): $$Z^{-1} = \frac{A^{p^6}}{B}$$
We now have two expressions involving $B$:
- From (1): $B = A/Z$
- From derived equation: $B = Z \cdot A^{p^6}$
Equating the two expressions for $B$: $$A / Z = Z \cdot A^{p^6}$$ $$Z^2 = A / A^{p^6} = A^{1 - p^6}$$
4. The Practical Formula for Your Algorithm
You are looking for $A = f_P(Q)$ (the input for inversion) given $Z$ (your Weil target). The final equation is:
$$A = Z^{\frac{2}{1 - p^6}}$$
(The exponent is calculated modulo the group order $r$. Division by $1-p^6$ is multiplication by the modular inverse).
Why does this work without knowing the denominator? Because the denominator $B$ is "eaten" by the operation. By squaring and playing with the conjugate, we exploit the fact that $B$ is "real" (invariant under $p^6$) while $A$ is "complex". This eliminates $B$ from the equation.
Summary
You have effectively reduced the "Weil Inversion Problem" to the "Miller Inversion Problem" using simple arithmetic. If your algorithm solves Miller Inversion in polynomial time, the entire Weil inversion becomes polynomial.
