A zap is a two-round witness indistinguishable interactive proof system for
language membership in which the first round, consisting of a message from the
verifier to the prover, 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 introduce and construct verifiable pseudo-random
bit generators (VPRGs), and give a complete
existential characterization of both noninteractive
zero-knowledge proofs and zaps in terms of approximate VPRGs.
We present several applications for zaps:
- In the timing model of Dwork, Naor and Sahai (STOC 1998), we obtain
3-round concurrent zero knowledge and 2-round deniable authentication.
- In the standard model we obtain 2-round oblivious transfer
using public keys (3-round otherwise).
- We note that any zap yields 2-round witness-indistinguishability in the
resettable model of Canetti et al. (STOC 2000), and obtain a 3-round
timing-based resettable zero-knowledge argument system
for any language in NP.