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
-
CC BY
BibTeX
@misc{cryptoeprint:2007/421,
author = {André Chailloux and Iordanis Kerenidis},
title = {The role of help in Classical and Quantum Zero-Knowledge},
howpublished = {Cryptology {ePrint} Archive, Paper 2007/421},
year = {2007},
url = {https://eprint.iacr.org/2007/421}
}
