Citation:
Nguyen, Minh, and Salil Vadhan. “Zero knowledge with efficient provers.” In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC ‘06), 287-295. ACM, 2006.
STOC2006.pdf | 230 KB |
Abstract:
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.See also: A Unified Theory of Pseudorandomness (NSF CCF-0133096), ITR: Information Theoretic Secure Hyper-Encryption and Protocols (NSF CNS-0205423), New Complexity-Theoretic Techniques in Cryptography (NSF CNS-0430336), Pseudorandomness and Applications (ONR Young Investigator Award; ONR Grant N00014-04-1-0478)