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)
Copyright. All Rights Reserved.