Constant-Space Zero-Knowledge Proofs Systems with One-Way Quantum Verifiers (Preliminary Report)

摘要

We discuss the notion of quantum zero-knowledge proof systems whose memory-limited verifiers receive a stream of classical input symbols. We model such verifiers as one-way quantum finite automata working on input strings. Our proof systems require the recognition zero-knowledge property of Dwork and Stockmeyer [JACM, 1992]. Here, we report a preliminary set of fundamental properties of such proof systems. With the use of one-way quantum finite automata as verifiers, all proofs of the properties do not rely on any unproven complexity-theoretical assumptions.