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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
- $P \to V: P_1$
- $P \leftarrow V: c_1$
- $P \to V: P_2$
- $P \leftarrow V: c_2$
- $P \to V: P_3$
- $P \leftarrow V: c_3$
- $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)$
