Please implement pairing inversion for some curves

[ytrezq]

https://pdfupload.io/docs/8453308d#%5B%7B%22num%22%3A2790%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22FitH%22%7D%2C343%5D shows how certain type of pairings can be inverted in subexponential time.

I’m also interested in the case where exponention inversion is already done (so just miller inversion).

[bkomuves]

• This is out of scope for this library. We are interested in constructing ZK proofs, not breaking them
• I know essentially nothing about pairing inversions, and don't have bandwidth to learn about them
• It seems to me from a quick glance at the linked paper and also some quick searches that this problem should be still practically infeasible for the curves we implement. So I'm not sure it makes sense to implement these algorithms (it's not even clear from the linked reference if these are actual algorithms? and not just reduction to another hard problem)

[ytrezq]

@bkomuves Bn254 is a Bn curve the paper is supposed to work for. Also I thought that since you were writing about Zkp you were interested in providing the tooling for breaking Zkps.

See also the appendixes

[bkomuves]

Well of course in that sense we are interested in breaking too, but this is not the kind of break I'm really worried about at the moment; on the other hand I have extremely limited bandwidth, so cannot look into everything.

The paper talks about the BN family of curves in general. I don't see it anywhere suggesting that this attack may be practical for a \~250 bit curve like BN254.

The idea of the reduction from (q^k − 1)/Φ_k(q) to q−1 is applicable for various pairing–friendly curves of even embedding degree such as BN curve. The reduced EI problem is still difficult even though the reduction is a significant achievement.

To me it seems that this is a significant improvement to previous attacks, but even the authors do not seem to suggest that it is a practical attack.

If you believe otherwise, you are free to try and implement it (or just point at something more explicit, with actual estimates of attack cost).

[ytrezq]

@bkomuves For example, Groth16 has some of it s pairing fully user controlled. So if you can perform pairing inversions, you can fake proofs.

I don t understand fully the paper myself, hence why I m requesting help. But according to the world pairing inversion researcher (Satoh) this what I m looking for,

[bkomuves]

Sure, I mean, if you can do pairing inversions, that looks like a very serious problem. I have to admit I never thought about this attack surface before.

However, I'm sceptical that this is a realistic attack on widely used curves. And I have no knowledge about this area and no time to learn it (probably takes years to really learn it...).

So maybe ask Satoh what is the time complexity of this kind of attack?

[ytrezq]

@bkomuves he told me the Miller Inversion part can be done in probabilitic polynomial time. In Groth16, if a proving key is reused several time, you can reuse a pre image of an old proof to avoid exponentiation inversion.

[bkomuves]

"Polynomial time" in itself doesn't mean anything. It could still take 1 second or a million years. I would need something concrete before spending time on this. Actual running time estimates, some prototype implementation eg. in Sage, etc.

Proving keys are most definitely reused a lot of times, a single-time Groth16 (or any other ZK proof) makes absolute no sense (as the verifier has to check, at the first time, that they are really verifying the given claim and not something else. And this takes a lot of time, not only computer time, but also humans actually looking at things time...).

However if this (hypothetically) breaks Groth16, why are you asking these questions on this totally unknown forum, monitored by nobody else? Especially as that, as I pointed out above, I'm very much not an expert on this.

The linked publication is from 2014, older than Groth16 itself. Groth16 is widely used. Where are all the breaking attempts?

he told me the Miller Inversion part can be done in probabilitic polynomial time.

If you are in contact with an actual researcher in the field, then he is a much better person to talk about this. If there would be say a Sage prototype implementation, which indicates that this is something to worry about, then maybe it would make sense to spend time and energy on this. Until that, I'll leave it to the experts to work it out.