License
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://drops.dagstuhl.de/opus/volltexte/2008/1744/
Go to the corresponding LIPIcs Volume Portal


Chailloux, Andre ; Kerenidis, Iordanis

Increasing the power of the verifier in Quantum Zero Knowledge

pdf-format:
Document 1.pdf (419 KB)


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 =		{http://dx.doi.org/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
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2008
Date of publication: 05.12.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI