Interactive and Noninteractive Zero Knowledge
Are Equivalent in the Help Model

André Chailloux, Iordanis Kerenidis, Dragos Florin Ciocan, Salil Vadhan

---

Abstract

We show that interactive and noninteractive zero-knowledge are equivalent 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 results do not rely on any unproven complexity assumptions and hold for statistical zero knowledge, for computational zero knowledge restricted to AM, and for quantum zero knowledge when the help is a pure quantum state.

---

Versions

• Preliminary versions on Cryptology ePrint Archive, as Reports 2007/389 (by Ciocan and Vadhan) and 2007/421 (by Chailloux and Kerenidis).
• Full version on Cryptology ePrint Archive, Report 2007/389, October 2007. [ePrint version][pdf]
• Extended abstract in Proceedings of the Third Theory of Cryptography Conference (TCC `08), volume 4948 of Lecture Notes in Computer Science, pages 501-534. Springer-Verlag, 19-21 March 2008. [Springer version]

---

 [ back to Salil Vadhan's research]