@conference {643250,
	title = {Zero knowledge and soundness are symmetric},
	booktitle = {Advances in Cryptology{\textendash}EUROCRYPT {\textquoteright}07},
	volume = {4515},
	year = {2007},
	pages = {187-209},
	publisher = {Springer Verlag, Lecture Notes in Computer Science, M. Naor, ed.},
	organization = {Springer Verlag, Lecture Notes in Computer Science, M. Naor, ed.},
	address = {Barcelona, Spain},
	abstract = {
	Version History:\&nbsp;Recipient of Best Paper Award. Preliminary version posted on ECCC as TR06-139, November 2006.



	We give a complexity-theoretic characterization of the class of problems in\&nbsp;NP\&nbsp;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\&nbsp;NP\&nbsp;\(\bigcap\)\&nbsp;coNP\&nbsp;having zero-knowledge arguments is closed under complement. Furthermore, we show that a problem in\&nbsp;NP\&nbsp;has a\&nbsp;statistical\&nbsp;zero-knowledge argument \(\)system if and only if its complement has a computational zero-knowledge\&nbsp;proof\&nbsp;system. What is novel about these results is that they are\&nbsp;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\&nbsp;NP\&nbsp;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\&nbsp;proof systems, or under the assumption that one-way functions exist for zero-knowledge argument systems.

},
	url = {https://link.springer.com/chapter/10.1007/978-3-540-72540-4_11},
	author = {Shien Jin Ong and Salil Vadhan}
}
