Constructions and Lower Bounds

Revision as of 11:37, 15 July 2008; view current revision
←Older revision | Newer revision→

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

Constructions

Assuming the existence of one way function, the following hold true
- Any language in IP=PSPACE has Computational Zero Knowledge(CZK) proof system with polynomially many rounds
- Any language in AM has an $ω(1)$ -round CZK proof system
- Any language in NP has a $ω(1)$ -round CZK proof system where the honest verifier runs in polynomial time, given a NP-witness for the statement to be proved.
- Any language in NP has a 4 round CZK argument
Assuming existence of a two-round statistically-hiding commitment schemes, there exists a 5-round CZK proof system for any language in NP
Assuming existence of constant-round statistically hiding commitment schemes, there exists a constant-round CZK proof system for any language in MA

Suppose a language L has a unidirectional (single message from prover to verifier), then $L\in BPP$
Suppose a language L has an auxiliary -input zero-knowledge proof system in which the prover program is deterministic, then $L\in BPP$
If there exists zero-knowledge proofs for languages outside of BPP, then there exist collections of functions with one-way instances
If there exists zero-knowledge proofs for naguages that are hard to approximate, then there exist one-way functions.
2-Round CZK proofs exists only for languages in BPP
3-Round black box CZK proofs exist only for languages in BPP
4-Round black box CZK proofs exists only for languages in BPP
Deterministic prover/verifier CZK proofs exists only for languages in BPP