Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Minh-Huyen Nguyen:

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 >>>

ISSN 1433-8092 | Imprint