Zaps and Their Applications

Abstract:

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.

• In the timing model of Dwork, Naor and Sahai (STOC'98, see link) and using moderately hard functions (see DN and BN), we obtain a 3-round concurrent zero knowledge and 2-round concurrent deniable authentication.
• In the resettable setting of Canetti, Goldreich, Goldwasser and Micali  (STOC'2000),  we obtain a 2-round witness-indistinguishability and  a 3-round timing-based resettable zero-knowledge argument system for any language in NP.
• In the standard model we obtain a 2-round oblivious transfer using public keys (3-round otherwise). See also link

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

Back to On-Line Publications

Back Home