Quantum proofs cannot be made noninteractive using standard methods
On Removing Interaction from Quantum Proofs
Cryptography and Security
Summary
The paper looks at a problem in quantum cryptography about making certain proofs noninteractive, meaning the prover and verifier don't need to talk back and forth. Classically, this is done using a method called the Fiat-Shamir transformation. The authors show that this method does not work when the proof messages are quantum instead of classical. Specifically, if such a method did work, it would imply an unlikely equality in computational power between two important classes, QMA and BQP. This suggests a fundamental obstacle to simplifying quantum proofs as we do with classical ones.
What this means in practice
- •For quantum cryptography developers: Recognize that standard Fiat-Shamir methods cannot yield noninteractive quantum proofs, guiding focus to alternative constructions in QMA proof systems.
- •For quantum software architects: Avoid attempts to simplify interactive quantum verification protocols through Fiat-Shamir-like compilers in quantum settings to prevent security failures.
A theory result. No direct application yet.
Authors
Nicholas Spooner, Max Tromanhauser
Abstract
An important open question 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" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.