Paper 2001/063

Resettably-Sound Zero-Knowledge and its Applications

Boaz Barak, Oded Goldreich, Shafi Goldwasser, and Yehuda Lindell

Abstract

Resettably-sound proofs and arguments remain sound even when the prover can reset the verifier, and so force it to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge {\em arguments} for NP exist if collision-resistant hash functions exist. In contrast, resettably-sound zero-knowledge {\em 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 proofs 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-resistant 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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. To appear in 42nd FOCS, 2001.
Keywords
zero-knowledgeresettable zero-knowledgeresettable soundnessproofs of knowledgepublic-key model
Contact author(s)
lindell @ cs biu ac il
History
2006-03-30: last of 2 revisions
2001-08-13: received
See all versions
Short URL
https://ia.cr/2001/063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/063,
      author = {Boaz Barak and Oded Goldreich and Shafi Goldwasser and Yehuda Lindell},
      title = {Resettably-Sound Zero-Knowledge and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2001/063},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/063}},
      url = {https://eprint.iacr.org/2001/063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.