← Back to papers
Oracle Separations Between Quantum and Non-interactive Zero-Knowledge Classes
B. Morrison, Adam Groce·July 6, 2019·DOI: 10.1016/j.ipl.2019.105864
MathematicsComputer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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 $\mathrm{SZK}^A \not\subseteq \mathrm{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 $\mathrm{NIPZK}^A \not\subseteq \mathrm{BQP}^A$.