Computational zero-knowledge
Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don’t have to be statistically close. The “two distributions” are
- the distribution over the verifier’s view of their interaction with the prover, conditioned on the verifier’s random coins, and
- the distribution over views that the verifier can simulate without the prover’s help.
See the complexity zoo entry here.
Notable problems
- 3-coloring — assuming OWFs exist
Known relationships
- Unlike SZK, it is not known if CZK is closed under complement
- CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions — Vad06
- Assuming OWFs exist, CZK contains NP — GMW91
- Contains SZK
Limits of zero-knowledge
- OWFs are necessary for non-trivial CZK: if a language outside BPP has a CZK proof system, then one-way functions exist — Ost91
- Informally: any ZK proof that convinces a verifier of something hard must “hide” information in a computationally meaningful way, which requires a one-way function
- Constant-round ZK for NP is impossible with black-box simulation: any constant-round proof system for an NP-complete language with black-box zero-knowledge simulation implies NP ⊆ BPP — GK96
- This explains why practical ZK protocols (e.g., Sigma protocols) require a super-constant number of rounds or use non-black-box techniques
- Parallel composition breaks ZK: repeating a ZK protocol in parallel to reduce soundness error may destroy the zero-knowledge property — GK96