On Removing Interaction from Quantum Proofs

Authors

Abstract

An important challenge in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) Σ-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a Σ-protocol (which they call a Ξ-protocol) in which the prover’s first message is quantum, and show that HVZK Ξ-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat-Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic “Fiat–Shamir-like” transformations for quantum protocols exist in the QROM (with small constant completeness error) then NP ⊆ BQP.