Zero Knowledge and Efficient Provers
Minh-Huyen Nguyen, Harvard University
Place and Time: Monday 5/1, 9 AM. Maxwell Dworkin 119.
Zero-knowledge proofs are interactive proof systems in which the
convinces the verifier that an assertion is true with the unusual
that the verifier learns nothing else than the fact that the assertion
true. In this thesis we consider the notion of efficient provers in
In the first setting, we consider efficient honest provers.
We prove that every problem in NP that has a zero-knowledge proof also
zero-knowledge proof where the prover can be implemented in
polynomial time given an NP witness. Moreover, if the original proof
is statistical zero knowledge, so is the resulting efficient-prover
system. An equivalence of zero knowledge and efficient-prover zero
was previously known only under the assumption that one-way functions
[GMW91] (whereas our result is unconditional), and no such equivalence
known for statistical zero knowledge. Our results allow us to
many general results and characterizations known for zero knowledge
inefficient provers to zero knowledge with efficient provers.
In the second setting, we consider efficient cheating provers.
We show that every language in NP has a statistical zero-knowledge
system under the complexity assumption that regular one-way functions
In such protocols, even a computationally unbounded verifier cannot
anything other than the fact that the assertion being proven is true,
whereas a polynomial-time prover cannot convince the verifier to
false assertion except with small probability. This partially answers
question posed by Naor, Ostrovsky, Venkatesan, and Yung [NOVY98] of
statistical zero-knowledge arguments on complexity assumptions that
weak and general as possible.