Oracle Separations Between Quantum and Non-interactive Zero-Knowledge Classes
share
We study the relationship between problems solvable by quantum algorithms in polynomial time and those for which zero-knowledge proofs exist. In prior work, Aaronson [arxiv:quant-ph/0111102] showed an oracle separation between BQP and SZK, i.e. an oracle A such that SZK^A ⊈BQP^A. In this paper we give a simple extension of Aaronson's result to non-interactive zero-knowledge proofs with perfect security. This class, NIPZK, is the most restrictive zero-knowledge class. We show that even for this class we can construct an A with NIPZK^A ⊈BQP^A.
READ FULL TEXT