Statistical Zero-Knowledge Arguments for NP from Any One-Way Function
Speaker: Shien Jin Ong , Harvard University
Date: May 19 2006
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva, Stata Ctr
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL:
We show that every language in NP has a statistical zero-knowledge
argument system under the (minimal) complexity assumption that
nonuniformly-secure 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 the 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).
Joint work with Minh-Huyen Nguyen and Salil Vadhan.
See other events that are part of Cryptography and Information Security Seminar Seminars 2005/2006
See other events happening in May 2006
