Fiat Shamir transformation of zero knowledge proof

Question

Consider the following three stage interactive zero knowledge proof

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

Each round can be won with probability $\frac{1}{2}$ by a malicious prover and so we must play this for $k$ rounds till $\frac{1}{2^k}$ is sufficiently small.

The Fiat Shamir transformation replaces the challenge generation with a random oracle that generates $c$ instead. Let $i$ be the round number (we play $k$ rounds). Typically, one can use a hash function $c_i = H(p_{i-1}, a_{i-1})$ for this purpose, where $p_{i-1}$ is some input generated from prior rounds and $a_{i-1}$ is the previous round's commitment. The prover then generates a transcript of the following form after many rounds

$$T = \{a_i, c_i = H(p_{i-1}, a_{i-1}), r_i\}$$

It is not clear to me why this is secure. In each round, the dishonest prover can simply keep trying different $a_{i-1}$ until $H(p_{i-1}, a_{i-1})$ is the challenge he is prepared to meet. Since $c\in\{0,1\}$ (i.e. the range of $H$ is just $\{0,1\}$), this does not take him many tries. The prover will only include such challanges (which he is prepared to meet) in the transcript.

What exactly is the correct Fiat Shamir transformation that prevents this attack by a dishonest prover?

Answer 1

You are correct about the attack, given the way you have defined the Fiat-Shamir-transformed protocol.

Since Fiat-Shamir is subtle for multi-round protocols, the standard way to resolve this is to use parallel instead of sequential composition. Start with a protocol that has soundness error 1/2, and run it $k$ times in parallel (not in sequence) to amplify its soundness error to $1/2^k$.

Then apply Fiat-Shamir to the resulting protocol, which just has one round. All the challenge bits are generated from a single call to $H$ as $c_1 \cdots c_k = H(a_1 \cdots a_k)$. Note that if the prover is proving a false statement, then for any first protocol message $a_1 \cdots a_k$ there is at most one $c_1 \cdots c_k$ for which she can generate a totally convincing response. With $q$ queries to $H$, an adversary can find such a valid first message with probability only $q/2^k$.

Answer 2

The main idea behind the Fiat-Shamir heuristic is to eliminate the interaction in public coin protocols. In the interactive model, the randomly selected challenges by the verifier force a malicious prover to provide a wrong proof. As you mention, it is negligible for a malicious prover to convince the verifier after $k$ round.

To make this scheme non-interactive we have to provide a hash function as a Random Oracle model (the output is not distinguishable from a truly random string) to be unpredictable. It means the prover is not able to predict the output of this hash function in each iteration. Since the input challenge for each round is the output of the previous round so the malicious prover can not cheat. To the best of my knowledge, there is no Hash function to be as a ROM.