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]