ECCC-Report TR06-075https://eccc.weizmann.ac.il/report/2006/075Comments and Revisions published for TR06-075en-usMon, 19 Jun 2006 20:42:10 +0300
Paper TR06-075
| Statistical Zero-Knowledge Arguments for NP from Any One-Way Function |
Minh-Huyen Nguyen,
Shien Jin Ong,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2006/075We 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 the verifier to accept a false assertion except with
negligible probability. This resolves an open question posed by Naor,
Ostrovsky, Venkatesan, and Yung (CRYPTO `92, J. Cryptology `98).
Departing from previous works on this problem, we do not construct
standard statistically hiding commitments from any one-way function.
Instead, we construct a relaxed variant of commitment schemes called
"1-out-of-2-binding commitments," recently introduced by Nguyen and
Vadhan (STOC `06).
Mon, 19 Jun 2006 20:42:10 +0300https://eccc.weizmann.ac.il/report/2006/075