Why does the Fiat-Shamir heuristic not work without a random oracle?

Question

Consider the following three stage interactive zero knowledge proof in round $i$

1. The prover sends some commitment $a_i$ to the verifier.
2. The verifier picks a challenge $c_i\in \{0 ,1\}$
3. Depending on the challenge, the prover responds with $r_i(c_i)$ that convinces the verifier of his knowledge.

The Fiat-Shamir heuristic converts this into a non-interactive game by using a random oracle to generate a string $c$ whose bits are then used to decide each $c_i$. However, under the assumption that such oracles don't exist, we instead use a one way function on all the commitments to generate $c = f(a_1, a_2,\dotsc,a_n)$. This is known to be insecure. I've tried to read the paper in the Wikipedia page but still do not quite see the issue.

I assume the weakness is that the prover can somehow choose $a_i$ in a manipulative way so that the challenges $c_i$ are controlled by the prover but the argument for how the prover can do this is not very clear to me.

Why exactly is the Fiat-Shamir heuristic insecure in the absence of a random oracle or some other trusted source of randomness?

Answer 1

Background: The Fiat–Shamir heuristic converts a certain class of interactive zero-knowledge proof systems—$\Sigma$-protocols, where prover proposes random commitment, verifier responds with random challenge, and prover answers with proof—into signature schemes using a random oracle to determine the challenge from the commitment.

• Using a random oracle means that everyone has access to the same independent random challenge as a function of the prover's commitment.
• The signer can pretend to have been given an independent random challenge in a simulated interactive zero-knowledge proof.
• Everyone else can reproduce the interaction given the message and commitment with the same challenge, in order to verify the resulting transcript as a signature.

The ROM theorems of Pointcheval & Stern exploit $\Sigma$-protocols in which the proofs for two different challenges for the same commitment leak the secret key with high probability, and use that to show that a ROM forger can be used to leak the secret key. The basic idea is the forking lemma:

• If you have a forger as a Turing machine, you can pause it just before it queries the random oracle, duplicate the state of the machine (‘fork’ it, in the parlance of our times), and then run it forward twice with two different random oracles.

• If the forger makes $q$ queries to the oracle, and you pick one of the $q$ queries uniformly at random to fork the machine, there's about a $1/q$ chance that you picked the query to the random oracle to choose the challenge—and hence about a $1/q$ chance that you got two different signatures with the same commitments but different challenges, leaking the key.

  (The forger could also return a forgery without using the random oracle to determine the challenge, of course—but there is a negligible probability they will guess the challenge the random oracle would have returned, and if their guess is wrong, whatever they return won't agree with the challenge that all the verifiers will be using.)

The random oracle model is essentially a model for how forgers are designed. That is, a ROM theorem is a statement of the form: If a forger is designed generically in terms of a hash function, then there is a way to break some underlying problem, using that forger as a subroutine. The proof shows how to use that forger as a subroutine, by passing it specially crafted random oracles that have the correct distribution on outputs but also do nefarious things behind the scenes to exfiltrate the goods from the forger.

What Goldwasser & Kalai showed about Fiat–Shamir—much like Canetti, Goldreich, & Halevi showed about signatures in general—is that there exists a $\Sigma$-protocol such that there is a forger for the signature scheme obtained by using Fiat–Shamir heuristic with any particular hash function even if it is secure in the random oracle model, using a series of complexity-theoretic tricks to make $\Sigma$-protocols that throw tantrums when the challenges have certain forms, which a forger can exploit to forge signatures in a Fiat–Shamir scheme that uses any particular hash function. Of course, the forger, in this case, is not written generically in terms of a hash function; although there exists a forger for any hash function, each forger itself depends intimately on the details of the hash function.

The tricks are elaborate and I won't go into details here, but the point is not that (e.g.) the Schnorr signature scheme is insecure—rather, it's that the Fiat–Shamir heuristic does not always produce a secure signature scheme given a secure $\Sigma$-protocol even if the signature scheme would be secure in the random oracle model. So you can't formally draw the implication that a ROM theorem of Schnorr signature security guarantees a Schnorr signature forger can be used to compute discrete logs—but it would be rather surprising if Schnorr's identification scheme interacted with (e.g.) SHAKE128 to break the security of the signature scheme derived by Fiat–Shamir.