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

This paper is superseded by Statistically
Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way
Function.

### Versions

*Electronic Colloquium on
Computational Complexity, *Technical Report TR06-075, June 2006. [official
ECCC page]

*Cryptology ePrint Archive, *Report 2006/185,* *June 2006.* *[official ePrint page]

[ps][pdf]
- In
*Proceedings of the 47th Annual IEEE Symposium on Foundations of
Computer Science (FOCS `06),* pages 3-14, Berkeley, CA, 22-24 October
2006. [ps][pdf][powerpoint show]

[ back to
Salil Vadhan's research]