ZKP + NP ⊄ io-BPP ⇒ CZK ⊄ BPP

Standard model · folklore · security loss: none: a PPT algorithm deciding the language contradicts NP ⊄ io-BPP unchanged

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