International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Minh-Huyen Nguyen
Shien Jin Ong
Salil P. Vadhan
Download:
URL: http://eprint.iacr.org/2006/185
Search ePrint
Search Google
Abstract: 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
}