A zap is a two-round, witness-indistinguishable protocol 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,
and where the verifier does not use any private coins.
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 guaranteed random string.

We present several applications for zaps, including
3-round concurrent zero knowledge and 2-round concurrent deniable
authentication, in the timing model of Dwork, Naor and Sahai, using moderately hard functions.