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

#### Shien Jin OngHarvard UniversityComputer 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.

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