According to Takakazu Satoh (an ex leading researcher in pairing inversion without solving discrete logarithms)
I have read the Akagi-Nogami paper again.
Let me clarify the Akagi-Nogami algorithm:
Let h_{n,A} denote the n-th Miller function at A.
Input:
p: a prime,
an irreducible polynomial of degree 12 over F_p (which is necessary to
realize F_{p^12}),
E: an elliptic curve defined over F_p, given by the Weierstrass equation,
r: a prime divisor of #E(F_p) whose embedding degree=12,
d: a multiple of r and a divisor of p^6+1 (d=r or d=p^6+1 is allowed),
A: trace zero element (i.e. Frob(A)=-A, where Frob is the p^6 power Frobenius
endomorphism) of order r,
z: value of h_{d,A}(Q) for some Q in E(F_p).
Output:
the X-coordinate of Q in E(F_p) satisfying h_{d,A}(Q)=z
or NIL if such point does not exist (i.e. the given value of z is bogus.)
In fact, it turned out that the algorithm described in Akagi-Nogami
paper has many inefficiencies. Even so, I believe that running time
under the raspberry pi zero (ARM V6, 1GHz, 512MiB memory) of a straightforward
implementation of the algorithm is less than one hour for the 381 bit
prime, probably something like 30 seconds if some of inefficiencies are
eliminated. They are my guess and don’t blame me if actual running time
is 100 times of the estimates. (But from a security point of view, 100 times
or even 1000 times does not matter. From a theoretical point of view,
the algorithm runs in probabilistic polynomial time in both log p and
the embedding degree.)
Returning to your case: an essential problem is to how to obtain
h_{d,A}(Q) from raw values of optimal the ate pairing or other values
appearing in zero knowledge protocols. This is not about algebraic
geometry but about lattice reduction and protocol analysis.
I have no idea about them. Perhaps, you have better to ask other person
in the area.
In Groth16 specifically, we are checking pairing relations, not trying to invert the pairing. That is, all of the input points are public. So pairing inversion problems in general are inapplicable to breaking Groth16 for either soundness or zero knowledge. (Note that this only considers the proof system itself, not the setup protocol. I’ll consider the setup protocol later and edit this comment accordingly. [Edit: I still haven’t had time to do so.])
I disagree about some implementation of Groth16. In some cases, it’s
matter of peforming a modular inverse in order to find a finite field’s element that will turn the verification equation to true (this part is computationally easy).
And then this is the matter of finding what pairing input generate such would be finite field’s element. This noramlly requires exponentiation inversion unless the Groth16 proving key is reused several times (then since exponentiation of all elements after multiplications is the same as exponentiation 1 by 1 you may find a finite field’s element value before final exponentation).
See https://eprint.iacr.org/2007/256.pdf for why pairing inversion is essentially equivalent to the pairing being completely broken for cryptographic use. In particular, if it were in fact the case that FAPI-i for i \in \{1,2\} could be solved in an hour (or any feasible time) on a pairing, then BDH-i would also be broken for that pairing. This is not protocol-specific.
Note that the paper you cited summarizes its contribution as:
This paper shows that the objective P is calculated if the correct (q − 1)–th root of Tate pairing is obtained.
But the latter was already known to be the hard part of the inversion problem in at least some cases. From https://eprint.iacr.org/2007/256.pdf :
On the other hand, we discuss in Section 6 cases where inverting Miller’s algorithm is easy. However, in these cases the final exponentiation is highly non-trivial (and is many-to-one). Hence, in these cases, the difficulty of pairing inversion is entirely due to the difficulty of finding the right pre-image of the final exponentiation.
Yes, but since exponentiation before or after multiplying the result of pairings is the same, it’s in my understanding that it’s possible to have a finite field element before final exponentiation in the case a proving key is reused.
I’m claiming that for some curves, it’s possible to perform Miller inversion in polynomial time (though it might not be for optimal ate pairings).
Is it dependent on not checking that the input points are in \mathbb{G}_1 and \mathbb{G}_2? An implementation that allows that is not implementing Groth16 as specified.
It’s not dependent on not checking G_1 and G_2. Use the second paper for exponentiation inversion and the first paper for Miller Inversion. The limitations is it’s only for determining G_1 points and doesn’t apply to optimal pairings.
Dear Laël Cellier,
I have modified my program which was originally written for verification
of my e-print 2019/385 to BLS-381. I have no idea whether it runs
faster than Akagi-Nogami algorithm but I’m quite certain that mine
is much easier to implement.
Result:
time to invert 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
th Miller
function on BLS-381 on Raspberry pi zero:
Minimal: 75.6 seconds, Maximal: 146.9 seconds
Number of samples: 50
The time is for one inversion.
The time does not include extension field generation, trace zero point
generation (this took about 10 minuts), and precomputation for sqrt computation.
If it doesn’t apply to optimal pairings then it doesn’t apply to Groth16 as used in Zcash, which uses the optimal ate pairing.
That aside, it would be of concern if this proposed attack applied to Groth16 (or other widely used proof systems) with any type of pairing — but I’m still not seeing how it could be used to break Groth16 knowledge soundness. Using the definition in the Zcash protocol specification (based on appendix C of the “Cycles of Elliptic Curves” paper [BCTV14b] ):
Knowledge Soundness: For any adversary \mathcal{A} able to find an x \in \mathsf{ZK.PrimaryInput} and proof \pi \in \mathsf{ZK.Proof} such that \mathsf{ZK.Verify_{vk}}(x, \pi) = 1, there is an efficient extractor \mathcal{E}_{\mathcal{A}} such that if \mathcal{E}_{\mathcal{A}}(\mathsf{vk}, \mathsf{pk}) returns w, then the probability that (x, w) \not\in \mathsf{ZK.SatisfyingInputs} is insignificant.
Can you exhibit any concrete attack against this property for Groth16 based on pairing inversion?
[Aside: For zero knowledge proof systems such as Groth16, the zk property ensures (intuitively) that a proof for a given instance yields no information other than that the prover knows a witness for that instance. This partly justifies formalizing the definition of Knowledge Soundness without explicitly giving the adversary an oracle allowing it to obtain proofs for other witnesses. To be honest I am not entirely happy with this; practical protocols such as Zcash will provide such an oracle. But for Groth16 in particular, given a technical condition on how circuits are compiled that I think is satisfied by the implementation in bellman, [BKSV2020] proves that we also have white-box weak simulation extractibility (see also this blog post by Andrija Novakovic and Kobi Gurkan). Intuitively that means that proofs are bound to instances, i.e. having proofs for one instance cannot be used to obtain proofs for another instance without knowing a witness for that other instance. Note that the proof of white-box weak simulation extractibility is in the Algebraic Group Model, and divergence of particular pairings from the AGM is exactly what is at issue in this thread. All this is just to say, a hypothetical attack using pairing inversion would still be interesting if it were against, say, Simulation Extractibility rather than Knowledge Soundness. So feel free to use an oracle that outputs proofs for other instances or witnesses if you need one to demonstrate an attack.]