Comment by GTP
4 days ago
I understand that this is the claim being made, but I think I'm still missing what is the attack's heart. From the article, it seems to boil down to "if you use a malicious program, then Fiat-Shamir is broken". But to me it seems more like that Fiat-Shamir would still give a correct proof of the program's output, it's just that the output itself was wrong from the start (I'm referring to the point in the article where they say such a malicious program behaves differently than intended when it detects its own hash being used). Is this attack actually letting you generate a valid proof for an output that the program doesn't generate under the given input?
As I understand the paper, the point is that Fiat-Shamir does *not* give a correct proof of the program's output.
They gave a (maliciously constructed) program whose outputs are pairs (a,b) where certainly a != b (instead the program is constructed such that a = b+1 always). But you can get the corresponding Fiat-Shamir protocol to accept the statement "I know a secret x such that Program(x) = (0,0)", which is clearly a false statement.
I haven't done a real review yet, but skimming it seems to relate to Arthur-Merlin[0] oracles and public fair coins.
If you view random numbers as normal numbers, they will seem to be algorithmically random, or at least exceed the complexity of any proof, or even practical proof.
Basically the work of Chatlin, where given the kolmogorov complexity of your verifier, you only have a limited number of bits in any L that you can prove anything.
Probably simpler to think about the challenges of proving a fair coins is fair.
They just have to produce an unfair coin that looks fair as a flawed analogy.
Fiat-Shamir depends on interactive proofs, which equals PSPACE, which seems huge, but it can be a hay in the haystack, and if you are using a magnet to reach into the haystack you will almost never pull out a piece of hay.
They are basically choosing the magnet for you.
[0] https://complexityzoo.net/Complexity_Zoo:A#am
The protocol is in charge of producing the proof. Fiat Shamir is a heuristic, some kind of rule of thumb, which consists in using a hash function as a source of randomness.
Cryptographic protocols often feature coin tosses. The idea is that if we replace a hash function in place of the protocol coin tosses, it should still be hard for a malicious prover to craft a false statement with an accepting proof - making the protocol unsound.
Roughly, the meat of the attack consists in baking in the statement being proven the ability for the prover to predict upfront how the hash function is going to behave - hereby breaking the Fiat Shamir heuristic and making the prover able to craft a false statement with an accepting proof.
That’s it, this is “How to Prove False Statements“!
Yes, I happened to study how the Fiat-Shamir transform works a couple years ago, but I only saw it in the context of using it to transform an interactive zero knowledge proof into a digital signature scheme.
So, if the prover can know beforehand how an hash function behaves, wouldn't this make it a more general attack on hash functions (so potentially even worse than how it is presented in the article) and the Fiat-Shamir transform is only broken as a consequence of it relying on an hash function? If not, why?
This is not an attack on hash functions in general. In this paper, the authors build a statement (or "circuit") which should, by construction, not have any accepting claim. Yet, they show that when using GKR along the FS transform, you can still get accepting proofs.
This has to do with "how an hash function behaves" in the sense that, in the context of a specific protocol (GKR), it is possible to bake in the circuit the ability to predict the randomness obtained from hashing the statement itself and the public values satisfying it.