Cryptology ePrint Archive: Report 2007/421

The role of help in Classical and Quantum Zero-Knowledge

Andr\'e Chailloux and Iordanis Kerenidis

Abstract: We study the role of help in Non-Interactive Zero-Knowledge protocols and its relation to the standard interactive model. In the classical case, we show that help and interaction are equivalent, answering an open question of Ben-Or and Gutfreund (\cite{BG03}). This implies a new complete problem for the class SZK, the Image Intersection Density. For this problem, we also prove a polarization lemma which is stronger than the previously known one.

In the quantum setting, we define the notion of quantum help and show in a more direct way that help and interaction are again equivalent. Moreover, we define quantum Non-Interactive Zero-Knowledge with classical help and prove that it is equal to the class of languages that have classical honest-Verifier Zero Knowledge protocols secure against quantum Verifiers (\cite{Wat06, HKSZ07}). Last, we provide new complete problems for all these quantum classes.

Similar results were independently discovered by Dragos Florin Ciocan and Salil Vadhan.

Category / Keywords: cryptographic protocols / cryptography, zero knowledge protocols, help model, quantum

Date: received 9 Nov 2007

Contact author: andre chailloux at ens-lyon fr

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: This article will be shortly superseeded by some joint work with Dragos Florin Ciocan and Salil Vadhan

Version: 20071118:221550 (All versions of this report)

Discussion forum: Show discussion | Start new discussion