You are looking at a specific version 20071118:221550 of this paper. See the latest version.

Paper 2007/421

The role of help in Classical and Quantum Zero-Knowledge

André 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.

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

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptographyzero knowledge protocolshelp modelquantum
Contact author(s)
andre chailloux @ ens-lyon fr
History
2007-11-18: received
Short URL
https://ia.cr/2007/421
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.