ZKP + NP ⊄ io-BPP ⇒ CZK ⊄ BPP
Statement
If every language in has a computational zero-knowledge proof and NP ⊄ io-BPP, witnessed by , then , and since every PPT algorithm has, at all but finitely many input lengths, an input with ; so CZK ⊄ BPP — folklore.
Notes
- Any serves, so suffices — folklore.
- Composed with CZK ⊄ BPP ⇒ Auxiliary-input OWF, the hypotheses give an auxiliary-input one-way function — OW93.