Fiat-Shamir Heuristic

# Fiat-Shamir Heuristic Three message IP: Prover    Verifier           $a$     ---------->          b (random)    <----------         ans    ----------> Replace verifier's answer b with hash of a, H(a). What is the security of this? The idea is that if only a few answers would make this insecure, then the prover would need a lot of brute force to try different a to find one where they could cheat. Random Oracle model: For each of infinitely many possible input strings $s$, choose $H(s)$ independently uniformly at random over $λ$ bit strings. Suppose that the original interactive protocol had failure probability p (e.g. in a proof of knowledge P can convince V of something they do not know). In the random oracle model, for each a the prover computes H(a) for, there is p probability the protocol fails. So if the prover can only compute m hashes, then the failure probability of the Fiat-Shmair transformed protocol is mp. Technicality: This turns a Proof of knowledge into an Argument of Knowledge. The latter is only statistically sound against a prover with bounded computuation. But hashes are not random oracles! In particular they are not black boxes. There are results [Barak01, Goldwasser-Kalai03] showing that Fiat-Shamir does not work in general. Argument similar to Goldwasser-Kalai03, any mistakes are my own: Consider a 2-round public coin IP that is a proof of knowledge of x: Prover     Verifier           $a$    ---------->           $b$ (random)     <----------         ans     ----------> Verifier accepts if $f(a,b,\textrm(ans)$ Then we modify this to be a proof of knowledge or clairvoyance: Prover   Verifier          $a$     ---------->          $b$ (random)    <----------        ans    ----------> Verifier accepts if f(a,b,ans) or H(a)=b This is a proof of knowledge with a slightly higher error probability. Insecure if we use H for Fiat-Shamir. We should use a different hash, one that doesn't appear in the protocol. But: Prover   Verifier    $a$,\<code C\>    ---------->       $b$ (random)    <----------       ans    ----------> Verifier accepts if $f(a,b,\textrm(ans))$ or ans is a STARK that verifies the execution trace of $C(a,\textrm{<code C>})=b$. This is an argument of knowledge for which Fiat-Shamir does not give an argument of knowledge for any hash. Conclusion: If Fiat Shamir works for STARKs, it does not work for all arguments of knowledge, even for 3 round ones. Counterargument: No non-contrived protocol transformed by Fiat-Shamir has been broken yet. Let's ignore that and assume the random oracle model. What about multi round public coin IPs? Interactive proof of knowledge of x: Prover   Verifier           $b_1$ (random)    ---------->           $a_1$    <----------           $b_2$ (random)    ---------->           .           .           .          $b_k$    <----------          $a_k$    ----------> General principle: Hash everything that we know at that point of the interactive protcol Non-interactive proof of knowledge of x: Prover   Verifier     $b_1=H(x)$    ---------->           $a_1$    <----------    $b_2=H(x,b_1,a_1)$    ---------->           .           .           .     $b_k = H(x,b_1,a_1,...,b_k-1,a_k-1)$    <----------           $a_k$    ----------> (The paper https://eprint.iacr.org/2016/116.pdf considers Interactive Oracle proofs.) What is the security of a non-iteractive version of a k-round public coin IP? Recall that with 1 round, we lost a factor of m, the number of hashes the prover could brute force. An example, suppose that to convince the verifier of something false, each reply by the verifier needs to be something that only happens with probability $p$ independently. Then the interactive proof is secure with probability $p^k$. But we can brute force the non-interactive proof round by round. It takes computing $1/p$ hashes in expectation to choose an $x$ so that $b_1$ is bad for the verifier then $1/p$ hashes to choose $a_1$ to make $b_2$ bad... So it takes $O(m/p)$ hashes to break the protocol with probability $1/2$. Thus the error has blown up by a factor of $(m/k)^k$ . Lemma 5.7+Theorem 7.1: The error probability for k-round IOPs blows up by a factor of at most ${m \choose k} (=O(m/k)^k)$ More precisely they show that error probabilities are bounded by the vulnerability of the interactive protocol to state restoration attacks, where the prover can rewind the verifier to an earlier state. Theroem 7.1: The non-interactive protcol with prover who can compute m hashes is at least as sound as the state-restoration interactive protocol where there are m rounds.