## Resettably-Sound Zero-Knowledge and
its Applications

### Boaz Barak, Oded Goldreich, 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 *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.

Extended abstract:
Postscript, gzipped Postscript.

*Preliminary* full version:
Postscript, gzipped Postscript.

Back Home