[Resource Topic] 2006/185: Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

Welcome to the resource topic for 2006/185

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

Authors: Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan


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

ePrint: https://eprint.iacr.org/2006/185

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .