Non-Interactive Quantum Statistical and Perfect Zero-Knowledge

Simple item page
dc.creatorKobayashi, Hirotada
dc.date2002-07-29
dc.date.accessioned2026-07-07T06:04:40Z
dc.date.available2026-07-07T06:04:40Z
dc.descriptionThis paper introduces quantum analogues of non-interactive perfect and statistical zero-knowledge proof systems. Similar to the classical cases, it is shown that sharing randomness or entanglement is necessary for non-trivial protocols of non-interactive quantum perfect and statistical zero-knowledge. It is also shown that, with sharing EPR pairs a priori, the class of languages having one-sided bounded error non-interactive quantum perfect zero-knowledge proof systems has a natural complete problem. Non-triviality of such a proof system is based on the fact proved in this paper that the Graph Non-Automorphism problem, which is not known in BQP, can be reduced to our complete problem. Our results may be the first non-trivial quantum zero-knowledge proofs secure even against dishonest quantum verifiers, since our protocols are non-interactive, and thus the zero-knowledge property does not depend on whether the verifier in the protocol is honest or not. A restricted version of our complete problem derives a natural complete problem for BQP.
dc.descriptionLaTeX2e, 12 pages
dc.identifierhttps://arxiv.org/abs/quant-ph/0207158
dc.identifierhttp://arxiv.org/abs/quant-ph/0207158
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/90381
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleNon-Interactive Quantum Statistical and Perfect Zero-Knowledge
dc.typetext

Files

Collections

arXiv