3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ In these 3 round public coin protocols, the idea is that you take the first message of the prover and send it to an entity which is the random oracle, and it gives you a random string, and then it distributes the same (uniformly random) as the challenge string from the verifier. We obviously don't have random oracle in real life, so we replace them with hash functions, and the reason it's "good enough" is that in these 3 round protocols, if the prover lacks the witness, it needs exponential time to "find" a first message and last message such that the challenge would fit the verification. $\endgroup$
    – yacovm
    Mar 15, 2020 at 11:36

1 Answer 1

Reset to default
3
$\begingroup$

The paper by Goldwasser and Tauman is another paper in the series of the failure of the random oracle model; its novelty is applying this principle to the Fiat-Shamir paradigm and interactive protocols. However, an easier place to start is the seminal paper of Canetti, Goldreich and Halevi, called The Random Oracle Methodology, Revisited. This paper shows that there exist signature and encryption schemes that are secure in the random oracle model, but fail for every concrete instantiation, for any hash function. They prove this by carefully constructing a scheme that will fail for any hash function instantiation. Their proof does not work in the random-oracle model (as with Goldwasser and Tauman) since the description of the hash function does not exist when it's a random oracle (it's certainly not polynomial size).

It's important to understand what this actually proves. The theorem proven shows that it is impossible to generically replace the random oracle with a hash function. That is, there does not exist any hash function that can be used to replace the random oracle in every construction, in order to get a proof in the standard model. Furthermore, there exist constructions that cannot be proven secure in the standard model at all, for any hash function. Thus, the random oracle model is not "sound" in the sense that it cannot always be a stepping stone to a standard-model proof.

What this does not say is that there are no random-oracle constructions that can be proven secure in the standard model. Since my previous double-negative sentence will surely be confusing, I'll explain. There may exist schemes that are proven secure in the random oracle and can be instantiated with a concrete hash function. These proofs do not state that this is impossible. Thus, it is theoretically possible that a hash function can be found to instantiate RSA-OAEP to be secure in the standard model, and it is theoretically possible that a hash function can be found to instantiate Fiat-Shamir on Schnorr's protocol specifically so that the result is a secure signature scheme in the standard model (I may be wrong, but I don't think that this has been proven to be impossible). To be honest, it is very unlikely that this is the case (at least in my opinion), but this hasn't been ruled out.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I think you did not answer my question but a different one. I know that certain signature and encryption schemes are secure in the ROM but not in the standard model. You can just dump the secret key into the signature or ciphertext if the message is the hash algorithm. My question is why the construction in the paper does not imply that Fiat-Shamir is insecure in the ROM because you can just pull the same trick when using the ROM. $\endgroup$
    – UTF-8
    Mar 15, 2020 at 17:57
  • $\begingroup$ Ah, I think I just figured out why you wrote that answer. It's about my wording, isn't it? I just used the same wording in my comment. Let me put it differently: Why is the argument made by Goldwasser and Tauman not transferable to the ROM? It does not depend on the way the randomness substitute is learned, just that both parties get the same randomness substitute. It might as well be a call to the RO, not a function evaluation. $\endgroup$
    – UTF-8
    Mar 15, 2020 at 18:07
  • $\begingroup$ @UTF-8 the argument does not transfer to the ROM, because the RO is not efficiently describable. So, e.g. , a polynomial length message can't be the hash function. $\endgroup$
    – Maeher
    Mar 15, 2020 at 20:32
  • $\begingroup$ @Maeher I see how this applies to the thing where you need to show that you're able to provide the code of the hash function to get the secret key in a signature or encryption scheme. But how is it relevant in the Fiat-Shamir setting where the party that is supplying the last part of the input to the RO / hash function needs to predict the outcome? They don't need every decision the RO will ever make. They only need that one decision. And they can just ask the RO. The verifier then asks the RO and gets the same back. But the prover had everything he needed to make that RO query first. $\endgroup$
    – UTF-8
    Mar 15, 2020 at 20:47
  • $\begingroup$ At the end of the first paragraph, I wrote the following sentence: Their proof does not work in the random-oracle model (as with Goldwasser and Tauman) since the description of the hash function does not exist when it's a random oracle (it's certainly not polynomial size). This answers that point. $\endgroup$
    – Yehuda Lindell
    Mar 16, 2020 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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