Abstract:
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.