I have a prover and verifier. They are engaged in a zero-knowledge proof protocol. A verifier sends a challenge $c$ to the prover so he can compute a proof using the value $c$. How to use Fiat Shamir so that a prover can compute that challenge $c$ from some public parameters without interacting with the verifier?


The challenge is generated by hashing the public parameteres in order of their usage in the proof generation. Consider a hypothetical ZKP proof generation that takes 7 steps.
$ P \to V: x$ means prover sent $x$ to verifier.
$P \leftarrow V: y$ means verifier sent $y$ to prover.

  1. $P \to V: P_1$
  2. $P \leftarrow V: c_1$
  3. $P \to V: P_2$
  4. $P \leftarrow V: c_2$
  5. $P \to V: P_3$
  6. $P \leftarrow V: c_3$
  7. $P \to V: \text{Proof}$

The prover sends $P_1$ to verifier in step 1 and verifier replies with challenge $c_1$ in step 2. Then the prover sends $P_2$ and verifier sends another challenge $c_2$ and then prover sends $P_3$ and verifier sends another challenge $c_3$. The prover finally sends the proof in step 7. Here $P_1$, $P_2$ and $P_3$ are commitments to some data. The list of exchanged messages between prover and verifier is called the transcript. $[P_1, c_1, P_2, c_2, P_3, c_3, \text{Proof}]$ is transcript of the protocol. Now if the prover wanted to make it non-interactive, he could generate challenge by hashing the transcript till that moment. Thus challenges are generated as

$c_1 = \operatorname{hash}(\text{any public data}+P_1)$
$c_2 = \operatorname{hash}(\text{any public data}+P_1+P_2)$
$c_3 = \operatorname{hash}(\text{any public data}+P_1+P_2+P_3)$


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.