## 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

Abstract:

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)