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

Available format(s)
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
Short URL
https://ia.cr/2006/185

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.