License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1744
URN: urn:nbn:de:0030-drops-17446
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1744/
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 Honest-Verifier Quantum
Statistical Zero Knowledge ($HVQSZK$) is equal to
Cheating-Verifier 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 non-unitary 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 Honest-Verifier 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 non-unitary operation is
equal to Quantum Zero-Knowledge 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
honest-but-curious 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 = {95--106},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-08-8},
ISSN = {1868-8969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1744},
URN = {urn:nbn:de:0030-drops-17446},
doi = {10.4230/LIPIcs.FSTTCS.2008.1744},
annote = {Keywords: Quantum cryptography, zero-knowledge protocols, honest-verifier, quantum semi-honest model, hiddenquantum cryptography, zero-knowledge protocols, }
}
|
Keywords: |
|
Quantum cryptography, zero-knowledge protocols, honest-verifier, quantum semi-honest model, hiddenquantum cryptography, zero-knowledge protocols, |
|
Freie Schlagwörter (englisch): |
|
honest-verifier, quantum semi-honest model, hidden-bits |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
05.12.2008 |
