In their paper On the (In)security of the Fiat-Shamir Paradigm, Goldwasser and Tauman show that the Fiat-Shamir heuristic does not work with any hash function. From the paper:
The most important question however remained open: are the digital signatures produced by the Fiat-Shamir methodology secure? In this paper, we answer this question negatively.
However, they do state that it is secure in the random oracle model:
[Pointcheval and Stern] proved that for every 3-round public-coin identification protocol, which is zero-knowledge with respect to an honest verifier, the signature scheme, obtained by applying the Fiat-Shamir transformation, is secure in the Random Oracle Model.
I'm confused because it seems to me that they then (in my opinion) go on to show that the Fiat-Shamir heuristic is never secure, not even in the random oracle model.
From the paper:
Intuitively, the idea is to take any secure 3- round public-coin identification scheme (which is not necessarily zero-knowledge) and extend its verdict function so that the verifier also accepts views which convince him that the prover knows the verifier’s next message. Since the verifier chooses the next message at random, there is no way that the prover can guess the verifier’s next message during a real interaction, except with negligible probability, and therefore the scheme remains secure. However, when the identification scheme is converted into a signature scheme, by applying the Fiat-Shamir paradigm, the “verifier’s next message” is computed by a public function which is chosen at random from some function ensemble and is known in advance to everyone. A forger, who will now know in advance the “verifier’s next message” on any input, will be able to generate an accepting view for the verifier. This makes the signature scheme insecure regardless of which function ensemble is used to compute the “verifier’s next message” in the identification scheme.
Doesn't this also work in the random oracle model? It seems to me that this is attacking the very concept of replacing new randomness by anything (except pseudorandomness), be it hash obtained by evaluating a hash function, or actual randomness chosen by the random oracle (but available in advance, so not new randomness).
Instead of evaluating the hash function on the arguments relevant for the randomness substitute, the prover can ask the random oracle for the hash. Sure, this will be true randomness, but the verifier will get the same randomness from the random oracle in the next step, so the prover still knows in advance what "random" value the verifier will choose.