International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Interactive and Noninteractive Zero Knowledge Coincide in the Help Model

Authors:
Dragos Florin Ciocan
Salil P. Vadhan
Download:
URL: http://eprint.iacr.org/2007/389
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13669,
  title={Interactive and Noninteractive Zero Knowledge Coincide in the Help Model},
  booktitle={IACR Eprint archive},
  keywords={foundations / cryptography, computational complexity, noninteractive},
  url={http://eprint.iacr.org/2007/389},
  note={ florin.ciocan@gmail.com 13790 received 3 Oct 2007},
  author={Dragos Florin Ciocan and Salil P. Vadhan},
  year=2007
}