1
$\begingroup$

If there were a proof to show that P=BPP, how would this affect zero knowledge proofs and the fiat-shamir heuristic for Turing an interactive proof into a non-interactive proof?

$\endgroup$
6
$\begingroup$

It would not affect this at all. Note that under reasonable complexity hardness assumptions, it holds that P=BPP. So, even though we don't know how to prove this unconditionally (and in fact seem far away from doing so), it is what we assume to be correct.

I am not sure why you would think that this would affect the Fiat-Shamir heuristic. Even if P=BPP it doesn't mean that randomness has no role. In particular, you cannot sample a distribution deterministically. P=BPP relates to the ability to decide a language, not sample distributions. In particular, the necessity of randomness for zero knowledge holds, even if P=BPP.

$\endgroup$

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.