1
$\begingroup$

In zero knowledge proofs, would it make a difference if the prover is deterministic or probabilistic?

As the verifier can simulate the prover's interaction with him, I assumed that the prover would need to be deterministic. Maybe this is a misunderstanding on my part?

$\endgroup$
7
$\begingroup$

In the general case of for auxiliary-input zero knowledge, it is impossible for the prover to be deterministic; see Definitions and properties of Zero-Knowledge proof systems by Goldreich and Oren. In the random oracle model, everything is different, so I don't want to go there. However, I will say that it is not true that the prover is deterministic is Fiat-Shamir. Fiat-Shamir is a way of converting some honest-verifier ZK protocols to fully malicious ones. Almost all honest-verifier ZK protocols considered have a probabilistic prover, so the Fiat-Shamir version also has a probabilistic prover.

$\endgroup$
1
$\begingroup$

No the verifier could easily simulate the prover, even it is a probabilistic one. And in many cases (in Groth-Sahai for example), if the prover is deterministic, then it will be no more secure (because it means that the randomness is publicly known, and then could be used to open commitments and find the witnesses).

As far as I know, when the prover is deterministic, the simulator has to use strong hypothesis (like the random oracle model) to simulate it. And in this case it's a little bit cheating because ROM could be seen informally as the fact to interpret a deterministic function as a random one.

$\endgroup$
  • $\begingroup$ This answer is incorrect. In general, the prover CANNOT be deterministic. So, it's not that this just "won't help". $\endgroup$ – Yehuda Lindell Aug 14 at 18:50
  • $\begingroup$ But Fiat-Shamir is deteministic (in the sense, that when you implement it, you will don't use any random string)... When you say "CANNOT", it seems to me that you are in a specific model (maybe Standard model). Are you? $\endgroup$ – Ievgeni Aug 16 at 8:04
  • $\begingroup$ The transform is deterministic, but not the zero knowledge proof. The honest-verifier zero knowledge proof that is used to start with is not deterministic. Thus, the entire proof overall is not deterministic. This is just wrong. (Indeed in the ROM, it is possible in some cases to get deterministic prover, but not in general, and there are caveats. However, it is certainly not the standard Fiat-Shamir proof.) $\endgroup$ – Yehuda Lindell Aug 18 at 4:58

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.