ICS Theory Group

ICS 269, Spring 2006: Theory Seminar

Jun 2, 2006, in CS 243

Zero Knowledge with Efficient Provers

Authored by: Minh-Huyen Nguyen and Salil Vadhan

Presented by Nodari Sitchinava


The main result of the paper is the proof 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 and no such equivalence was known for statistical zero knowlege.

(from STOC 2006)