Zero Knowledge and Soundness Are Symmetric

We give a complexity-theoretic characterization of the class of problems in

NP

having zero-knowledge argument systems. This characterization is symmetric in its treatment of the zero knowledge and the soundness conditions, and thus we deduce that the class of problems in

NP

 ∩ 

coNP

having zero-knowledge arguments is closed under complement. Furthermore, we show that a problem in

NP

has a

statistical

zero-knowledge argument system if and only if its complement has a computational zero-knowledge

proof

system. What is novel about these results is that they are

unconditional

, i.e., do not rely on unproven complexity assumptions such as the existence of one-way functions.

Our characterization of zero-knowledge arguments also enables us to prove a variety of other unconditional results about the class of problems in

NP

having zero-knowledge arguments, such as equivalences between honest-verifier and malicious-verifier zero knowledge, private coins and public coins, inefficient provers and efficient provers, and non-black-box simulation and black-box simulation. Previously, such results were only known unconditionally for zero-knowledge

proof systems

, or under the assumption that one-way functions exist for zero-knowledge argument systems.