2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic $\endgroup$ – kelalaka Oct 7 at 17:17
  • $\begingroup$ @kelalaka, thank you for the link! Unfortunately, I'm still not sure why the cheating strategy I have elaborated in the question fails (or I have misunderstood the Fiat Shamir transform). In particular, the challenge space being so small (two choices only) seems to make it very weak? $\endgroup$ – user1936752 Oct 7 at 20:31
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ In short, OP's method proves bit-by-bit (linear time to break), secure method proves all-bits-together, (exponential time to break). $\endgroup$ – DannyNiu Oct 8 at 2:16
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the answer! However, I'm not sure I see why this statement "Since the input challenge for each round is the output of the previous round so the malicious prover can not cheat" is true. A dishonest prover that can only answer one of the challenges but not both is easy to construct. Assume he can always answer $c= 0$ but not $c = 1$. Now, if $c_i = 1$, he simply tries different $a_{i-1}$ until one of them satisfies $c_i = H(p_{i-1}, a_{i-1}) = 0$. He will find one quite fast since the range of $H$ is just $\{0,1\}$. $\endgroup$ – user1936752 Oct 7 at 22:40

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.