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