Paper 2001/063

Resettably-Sound Zero-Knowledge and its Applications

Boaz Barak and Oded Goldreich and Shafi Goldwasser and Yehuda Lindell

Abstract

Resettably-sound proofs and arguments maintain soundness even when the prover can reset the verifier to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge arguments for $\NP$ exist if collision-free hash functions exist. In contrast, resettably-sound zero-knowledge proofs are possible only for languages in $\P/\poly$. We present two applications of resettably-sound zero-knowledge arguments. First, we construct resettable zero-knowledge arguments of knowledge for $\NP$, using a natural relaxation of the definition of arguments (and proofs) of knowledge. We note that, under the standard definition of proof of knowledge, it is impossible to obtain resettable zero-knowledge arguments of knowledge for languages outside $\BPP$. Second, we construct a constant-round resettable zero-knowledge argument for $\NP$ in the public-key model, under the assumption that collision-free hash functions exist. This improves upon the sub-exponential hardness assumption required by previous constructions. We emphasize that our results use non-black-box zero-knowledge simulations. Indeed, we show that some of the results are {\em impossible} to achieve using black-box simulations. In particular, only languages in $\BPP$ have resettably-sound arguments that are zero-knowledge with respect to black-box simulation.