Paper 2007/389

Interactive and Noninteractive Zero Knowledge Coincide in the Help Model

Dragos Florin Ciocan and Salil Vadhan

Abstract

We show that a problem in $\AM$ has a interactive zero-knowledge proof system {\em if and only if} it has a noninteractive zero knowledge proof system in the `help model' of Ben-Or and Gutfreund ({\em J. Cryptology}, 2003). In this model, the shared reference string is generated by a probabilistic polynomial-time dealer who is given access to the statement to be proven. Our result holds for both computational zero knowledge and statistical zero knowledge, and does not rely on any unproven complexity assumptions. We also show that help does not add power to interactive computational zero-knowledge proofs, paralleling a result of Ben-Or and Gutfreund for the case of statistical zero knowledge.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptographycomputational complexitynoninteractive
Contact author(s)
florin ciocan @ gmail com
History
2007-10-04: received
Short URL
https://ia.cr/2007/389
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/389,
      author = {Dragos Florin Ciocan and Salil Vadhan},
      title = {Interactive and Noninteractive Zero Knowledge Coincide in the Help Model},
      howpublished = {Cryptology ePrint Archive, Paper 2007/389},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/389}},
      url = {https://eprint.iacr.org/2007/389}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.