Zero knowledge and efficient provers

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 [11] (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 [23] of building statistical zero-knowledge arguments on complexity assumptions that are as weak and general as possible.