Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with zero-knowledge argument systems:
TR06-075 | 19th June 2006
Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

We show that every language in NP has a *statistical* zero-knowledge
argument system under the (minimal) complexity assumption that
one-way functions exist. In such protocols, even a computationally
unbounded verifier cannot learn anything other than the fact that the
assertion being proven is true, whereas a polynomial-time prover
cannot convince ... more >>>

TR06-139 | 14th November 2006
Shien Jin Ong, Salil Vadhan

Zero Knowledge and Soundness are Symmetric

Revisions: 1

We 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. ... more >>>

ISSN 1433-8092 | Imprint