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 (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.