## CryptoDB

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

Authors: Minh-Huyen Nguyen Shien Jin Ong Salil P. Vadhan URL: http://eprint.iacr.org/2006/185 Search ePrint Search Google 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).
##### BibTeX
@misc{eprint-2006-21678,
title={Statistical Zero-Knowledge Arguments for NP from Any One-Way Function},
booktitle={IACR Eprint archive},
keywords={foundations / one-way functions, zero knowledge, bit commitment, complexity theory},
url={http://eprint.iacr.org/2006/185},
note={ salil@eecs.harvard.edu 13318 received 19 Jun 2006, last revised 19 Jun 2006},
author={Minh-Huyen Nguyen and Shien Jin Ong and Salil P. Vadhan},
year=2006
}
`