1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think you can find the answer here, crypto.stackexchange.com/questions/74873/… $\endgroup$ – Mahdi Oct 14 at 14:44
  • 1
    $\begingroup$ @MahdiSedaghat that question answers why the Fiat Shamir heuristic requires a transformation of the challenge space into a larger one. Here, the question is about why there is the requirement of the random oracle for security guarantees although in practice, using hash functions is good enough $\endgroup$ – user1936752 Oct 14 at 16:11
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the very detailed answer! A couple of basic follow up questions (sorry if these are naive) 1) Who is the attacker in the case where we replace the random oracle with a hash function? Is it the prover (who now proves false statements) or the verifier who is trying to violate the zero knowledge-ness of the protocol? 2) I wasn't sure what the secret key/signature corresponded to? The ROM theorems are talking about using two identical signatures from different sources of randomness but I'm not sure how it is connected to the zero knowledge setting I am thinking about. $\endgroup$ – user1936752 Oct 14 at 19:01
  • 1
    $\begingroup$ 1. If we're talking about a $\Sigma$-protocol, an adversary is either a verifier trying to learn the prover's secret, or a prover trying to fool the verifier. If we're talking about a signature scheme, an adversary is a forger—a random algorithm with oracle access to a signer; the forger wins if they can find a signature on any message not sent to the signing oracle. 2. A signature in a scheme derived by the Fiat–Shamir heuristic is a transcript of a commitment and proof; the challenge is derived as a hash of the commitment (and, usually, of a message too). The key is the prover's secret. $\endgroup$ – Squeamish Ossifrage Oct 14 at 19:13
  • $\begingroup$ Thank you for such a quick response! I think I see now - so the thing that fails in a non-interactive zero knowledge proof setting when we use hash functions instead of a random oracle is that the verifier could, in theory, learn the prover's secret thereby making the scheme no longer a zero knowledge one? $\endgroup$ – user1936752 Oct 14 at 19:24
  • 1
    $\begingroup$ @user1936752 More or less. But, of course, the Goldwasser–Kalai result only says that there exists a signature scheme where that is the case, and they specifically construct it so it has a back door that can be unlocked when you instantiate it with any particular hash function, but not with a random oracle. It would, in contrast, be quite astonishing if that were the case for, e.g., Schnorr signatures over an elliptic curve with SHA-512, like Ed25519. $\endgroup$ – Squeamish Ossifrage Oct 14 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.