Interactive and Noninteractive
Zero Knowledge Coincide in the Help Model
Dragos Florin Ciocan
and
We show that a problem in AM has a interactive
zero-knowledge proof system if and only if it has a noninteractive zero
knowledge proof system in the `help model' of Ben-Or and Gutfreund (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.
Similar results have been independently discovered by Iordanis
Kerenidis and André Chailloux.