Paper 2006/185

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

Minh-Huyen Nguyen, Shien Jin Ong, and Salil Vadhan

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

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
one-way functionszero knowledgebit commitmentcomplexity theory
Contact author(s)
salil @ eecs harvard edu
History
2006-06-19: received
Short URL
https://ia.cr/2006/185
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/185,
      author = {Minh-Huyen Nguyen and Shien Jin Ong and Salil Vadhan},
      title = {Statistical Zero-Knowledge Arguments for NP from Any One-Way Function},
      howpublished = {Cryptology ePrint Archive, Paper 2006/185},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/185}},
      url = {https://eprint.iacr.org/2006/185}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.