Grinding in the Fiat-Shamir heuristic

The Fiat-Shamir heuristic is assumed to substitute public-coin messages from the verifier by hashes of the prover's messages until this point, i.e.: $$H(\alpha_1) = \beta_1, \\ H(\alpha_1, \alpha_2) = \beta_2,\\H(\alpha_1, \alpha_2, \alpha_3) = \beta_3,\\\vdots$$ where the $$\alpha_i$$'s are the prover's messages.

I understand why the Fiat-Shamir heuristic is proven to be secure in the ROM, however, in practise, the hash function $$H$$ is NOT an oracle, so what avoids the prover to grind over his messages to be able to forge a fake proof?

For instance, in a $$\Sigma$$-protocol there is only one message from the verifier $$\beta_1 = H(\alpha_1)$$. What if the prover grinds over some $$\alpha_1'$$ until he finds some input to the hash function such that $$\beta_1$$ lets him to obtain some advantage?

Why do we hash ALL the previous prover's messages to obtain the next non-interactive verifier message? Which is the problem of performing, for instance, $$H(\alpha_i) = \beta_i$$? Even worse, what if the prover can hash anything that he wants?

1 Answer

What avoids the prover to grind over his messages to be able to forge a fake proof?

We could ask exactly the same question with respect to a random oracle as well! What prevents the prover to grind over his messages until he can forge a fake proof? What you suggest can totally be done with a RO.

And the answer is: there should be a very small number of messages $$\alpha_1$$ such that $$\beta_1 = H(\alpha_1)$$ lets the prover have an advantage. In a typical $$\Sigma$$-protocol, for example, when the statement is not in the language (hence the prover is cheating), there is on average one $$\alpha_1$$ that allows the prover to cheat. (Exercise: show that this is the case for the $$\Sigma$$-protocol for DDH tuples, where the word is $$(X,Y)$$ and the witness is $$x\in\mathbb{Z}_p$$ such that $$X = g^x$$ and $$Y = h^x$$). Hence, if there are $$2^c$$ possible values $$\beta_1$$ (that's the challenge space), the malicious prover will have to compute $$O(2^c)$$ hashes to forge a fake proof. Now make $$c$$ big enough, and you get computational security.

Note that the grinding attack is still an important consideration: $$\Sigma$$-protocols have unconditional security, but at soon as you compile them in the ROM with Fiat-Shamir, they only have computational soundness. This means that the security parameter for soundness (the challenge space) must be adjusted accordingly: a 40-bit challenge space is fine for a $$\Sigma$$-protocol (since it gives a malicious prover a $$2^{-40}$$ statistical probability of successfully breaking soundness, which can be acceptable in practice), but broken for Fiat-Shamir (since breaking the compiled protocol requires $$2^{40}$$ operations, which is trivial to perform). Typically, we will use a challenge space about $$2^{128}$$ when using Fiat-Shamir.

• "In a typical Σ-protocol..not in the language, there is on average one 𝛼1 that allows the prover to cheat." This holds for verifying prover responses like following liner algebra. Maybe not so typical, one might verify power-two coefficient (considering the challenge as a free variable) combining three responses like Pythagoras theorem, doubling chances to cheat in this case. Dec 20, 2021 at 9:30
• Mmmm, that is what I thought. Anyways, the possibility of a "grinding" attack should be considered every time one intends to construct a protocol, right? I assume that it is not proven (in the general case) that the probability of a successful grinding attack is negligible. Dec 20, 2021 at 14:54
• @Vadym right, it would have been more accurate to say that it is for linear languages, or to simply say that the average number will be a negligible fraction of the challenge space in general. Dec 20, 2021 at 20:18
• @Geoffroy probably this "powers of challenge" idea was exaggerated on my part, and most of Σ-protocols published are "linear" anyway. My point is, there was some progress designing this kind of Σ-protocols for proving polynomial relations before R1CS/snark days. Dec 20, 2021 at 21:57