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

Shien Jin Ong
Harvard University
Computer Science

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), who gave a construction based on one-way permutations. Constructions were also known under collision-resistant hashing and ``approximable preimage size'' one-way functions. The existence of one-way functions is implied by all these assumptions, and is essentially the minimal assumption needed for nontrivial zero knowledge.

A key tool in our construction is the notion of 1-out-of-2-binding commitments, recently introduced by Nguyen and Vadhan (STOC `06).

This is a joint work with Minh-Huyen Nguyen and Salil Vadhan.

Audio (MP3 File, Podcast Ready) Presentation (PowerPoint File)

Back to Workshop III: Foundations of secure multi-party computation and zero-knowledge and its applications