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.
Versions
-
IEEE Foundations of Computer Science (FOCS) 2001
-
Cryptology e-print archive
-
ECCC
-
Preliminary full version
[postscript]
home | research | links | cv | pictures
|