Let’s I have the following :
- 2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their embedding degree with $p$ being a large prime Integer. So a construction that is suitable for the optimal ate pairing.
- $I$ : a very large precomputed set of random $a$ points $∈G_1$
- $J$ : a very large precomputed set of random $b$ points $∈G_2$
- $U$ : a very large precomputed set of random $c$ points $∈G_1$
- $V$ : a very large precomputed set of random $d$ points $∈G_2$
- Each points from $I$ ; $J$ ; $U$ ; $V$ are sampled completely independently so that it’s impossible to determine discrete logarithm relations if some exists in polynomial time.
Then the problem is computing a pair of $O∈G_1$ and $P∈G_2$ among the set of $a$ and $b$ in order to find at least 2 occurrences of $Miller’s(c,d)×Miller’s(a,b)×Miller’s(O,P) == F_p^{12}.1$ (the 1 number in the finite field’s). Where the Miller function is the version used for the optimal Ate pairing defined in https://cryptojedi.org/papers/dclxvi-20100714.pdf and implemented in https://go.googlesource.com/crypto/+/master/bn256/optate.go#189. So without the final exponentiation (beside any power of 1 is 1 of course).
While there might be no solution a would be easy case can be :
- rise $Miller’s(u,v)×Miller’s(a,b)$ to the power of the finite field element’s order−1
- find O and P such as $Miller’s(O,P)$ equal the value computed in 1. Which entirely depends on reversing the Miller inversion problem.
The only algorithm I found is polynomial in time if the curve is pairing friendly and it’s Frobenius trace is low. But most pairing friendly curves have high trace : this means the complexity is exponential with $trace^2$ operations.
Since that time, most of the research focused on reversing pairing directly through bringing down the pairing inversion problem to the exponentiation inversion as it was shown pairing inversion is equivalent and that creating in theory a polynomial time algorithm is possible but this isn’t helpful for my case.
And the problem studied is often restricted to FAPI where one point of the pairing to be reversed is fixed whereas in my case it’s possible to set points O and P to arbitrary values.
So beside physical and discrete logarithm cases, is it in theory possible in create a sub‑exponential algorithm for the parameters of usual/commonly used pairing friendly curves ? I also suspect that finding only 2 pair of solutions within the large precomputed set of possible $a$ ; $b$ ; $c$ ; $d$ can make things easier (through an algorithm that take advantage of this by reusing computations in different cases instead of simply treating each instance completely separately).
Having approximations for solving the equation instead of the real solution is possible too.
