ECCC-Report TR06-139https://eccc.weizmann.ac.il/report/2006/139Comments and Revisions published for TR06-139en-usMon, 09 Apr 2007 00:00:00 +0300
Revision 1
| Zero Knowledge and Soundness are Symmetric |
Shien Jin Ong,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2006/139#revision1We 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 intersect 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.
Mon, 09 Apr 2007 00:00:00 +0300https://eccc.weizmann.ac.il/report/2006/139#revision1
Paper TR06-139
| Zero Knowledge and Soundness are Symmetric |
Shien Jin Ong,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2006/139We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect 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.
Wed, 15 Nov 2006 16:01:07 +0200https://eccc.weizmann.ac.il/report/2006/139