Chailloux, Andre ;
Kerenidis, Iordanis
Increasing the power of the verifier in Quantum Zero Knowledge
Abstract
In quantum zero knowledge, the assumption was made that the
verifier is only using unitary operations. Under this assumption,
many nice properties have been shown about quantum zero
knowledge, including the fact that HonestVerifier Quantum
Statistical Zero Knowledge ($HVQSZK$) is equal to
CheatingVerifier Quantum Statistical Zero Knowledge ($QSZK$)
(see ~\cite{Wat02,Wat06}).
In this paper, we study what happens when we allow an honest
verifier to flip some coins in addition to using unitary
operations. Flipping a coin is a nonunitary operation but
doesn\'t seem at first to enhance the cheating possibilities of
the verifier since a classical honest verifier can flip coins. In
this setting, we show an unexpected result: any classical
Interactive Proof has an HonestVerifier Quantum Statistical Zero
Knowledge proof with coins. Note that in the classical case,
honest verifier $SZK$ is no more powerful than $SZK$ and hence it
is not believed to contain even $NP$. On the other hand, in the
case of cheating verifiers, we show that Quantum Statistical Zero
Knowledge where the verifier applies any nonunitary operation is
equal to Quantum ZeroKnowledge where the verifier uses only
unitaries.
One can think of our results in two complementary ways. If we
would like to use the honest verifier model as a means to study
the general model by taking advantage of their equivalence, then
it is imperative to use the unitary definition without coins,
since with the general one this equivalence is most probably not
true. On the other hand, if we would like to use quantum zero
knowledge protocols in a cryptographic scenario where the
honestbutcurious model is sufficient, then adding the unitary
constraint severely decreases the power of quantum zero knowledge
protocols.
BibTeX  Entry
@InProceedings{chailloux_et_al:LIPIcs:2008:1744,
author = {Andre Chailloux and Iordanis Kerenidis},
title = {{Increasing the power of the verifier in Quantum Zero Knowledge}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {95106},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897088},
ISSN = {18688969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1744},
URN = {urn:nbn:de:0030drops17446},
doi = {10.4230/LIPIcs.FSTTCS.2008.1744},
annote = {Keywords: Quantum cryptography, zeroknowledge protocols, honestverifier, quantum semihonest model, hiddenquantum cryptography, zeroknowledge protocols, }
}
05.12.2008
Keywords: 

Quantum cryptography, zeroknowledge protocols, honestverifier, quantum semihonest model, hiddenquantum cryptography, zeroknowledge protocols, 
Freie Schlagwörter (englisch): 

honestverifier, quantum semihonest model, hiddenbits 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Issue date: 

2008 
Date of publication: 

05.12.2008 