Zaps and Their Applications

Cynthia Dwork and Moni Naor


An interactive proof system is witness-independent if it is infeasible to determine which of two or more witnesses is used in performing the proof.  This paper introduces the notion of a zap. A zap is a  a two-round -- one message from the verifier and a response from the prover -- witness-indistinguishable protocol,  where the verifier's message can be fixed ``once-and-for-all" and applied to any instance.  We present a zap for every language in NP,  based on the existence of non-interactive zero-knowledge proofs in the shared random string model.  The zap is in the standard model, and hence requires no common random string.

We also introduce and construct  verifiable pseudo-random bit generators (VPRGs), and give a complete existential characterization of both non-interactive zero-knowledge proofs and zaps in terms of approximate VPRGs.

Several applications of zaps are discussed.

Paper: PDF, Postscript , gzipped Postscript . Slides: ppt

Back to On-Line Publications

Back Home