Ph.D. Defense
Zero Knowledge and Efficient Provers
Minh-Huyen Nguyen, Harvard University
Place and Time: Monday 5/1, 9 AM. Maxwell Dworkin 119.
ABSTRACT
Zero-knowledge proofs are interactive proof systems in which the
prover
convinces the verifier that an assertion is true with the unusual
property
that the verifier learns nothing else than the fact that the assertion
is
true. In this thesis we consider the notion of efficient provers in
two
different settings.
In the first setting, we consider efficient honest provers.
We prove that every problem in NP that has a zero-knowledge proof also
has a
zero-knowledge proof where the prover can be implemented in
probabilistic
polynomial time given an NP witness. Moreover, if the original proof
system
is statistical zero knowledge, so is the resulting efficient-prover
proof
system. An equivalence of zero knowledge and efficient-prover zero
knowledge
was previously known only under the assumption that one-way functions
exist
[GMW91] (whereas our result is unconditional), and no such equivalence
was
known for statistical zero knowledge. Our results allow us to
translate the
many general results and characterizations known for zero knowledge
with
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
argument
system under the complexity assumption that regular 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 small probability. This partially answers
the
question posed by Naor, Ostrovsky, Venkatesan, and Yung [NOVY98] of
building
statistical zero-knowledge arguments on complexity assumptions that
are as
weak and general as possible.