1
$\begingroup$

I understand that there are non-interactive (static) ZK proofs for every language in BPP, but I am not sure I fully understand this.

Can someone give an example of a Zero Knowledge Proof in BPP?

$\endgroup$
6
$\begingroup$

A zero-knowledge proof for a language in BPP is trivial: a statement in BPP can be verified in probabilistic polynomial time (by definition). So, for any language $L$ in BPP, and any $x \in L$, here is a trivial proof that $x\in L$: the prover sends nothing, and the verifier checks whether $x\in L$ (this takes polynomial time) and output yes iff this holds. Correctness is trivial, soundness too (the prover cannot cheat as he does not send anything at all), and zero-knowledge as well (it requires simulating an empty transcript...).

Here is an example: consider the language of prime numbers. Given a number $n$, the prover wants to convince the verifier that $n$ (which they both know) is prime. To do so, he comfortably stays at home and watches a movie, while the verifier checks by herself that $n$ is prime, using any polytime primality test of her choice. When she's done, she can just tell the prover "ok, you convinced me".

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