PaperlayerView exact revision on arXiv

Source-linked AI summary

On Removing Interaction from Quantum Proofs

Nicholas Spooner, Max Tromanhauser

arXiv:2609.38387v1quant-phcs.CR

TL;DR

Publicly verifiable non-interactive proofs for QMA remain an open construction problem, and existing QMA protocols with quantum prover messages complicate applying Fiat–Shamir. The paper formalizes quantum non-interactivity compilers and shows that straightline compilers with small errors would have the consequence QMA = BQP.

  • Problem

    It remains unclear how to use Fiat–Shamir to obtain publicly verifiable NIZKs or SNARGs for QMA, whose known public-coin protocols use quantum prover messages.

    Source: §1 · p. 1

  • Method

    The authors define quantum non-interactivity compilers (QNICs) and rule out straightline QNICs with small completeness and soundness error assuming quantum commitments.

    Source: §1.1 · p. 2

  • Results

    Under the stated assumptions, the result is QMA = BQP.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    Within this scope, the existence of a straightline compiler for removing interaction from quantum protocols has the complexity-theoretic consequence QMA = BQP.

    Source: §1.1 · p. 2

    Whether the impossibility result extends to compilers that are not straightline or have larger completeness and soundness error remains open.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

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) $\Sigma$-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a $\Sigma$-protocol (which they call a $\Xi$-protocol) in which the prover's first message is quantum, and show that HVZK $\Xi$-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.

1 Introduction

The paper asks whether quantum protocols can be generically made non-interactive, given that known QMA protocols either require private verifier state or use quantum prover messages. It formalizes a class of such compilers and shows that small-error straightline compilers, under quantum commitments, imply QMA = BQP.

1 Introduction

  • Known QMA protocols either use classical communication with private verifier state or public-coin quantum prover messages, leaving publicly verifiable NIZKs and SNARGs unresolved.Fully homomorphic encryption gives designated-verifier schemes for the former approach, while public verifiability remains unclear.Source: §1 · p. 1

1.1 Our Results

  • A QNIC is a black-box compiler from an interactive quantum-communication protocol to a publicly verifiable non-interactive quantum argument; straightline QNICs use one interaction.The classical Fiat–Shamir transformation is a straightline classical NIC.Source: §1.1 · p. 2
  • With quantum commitments and small-error straightline QNICs, the paper derives QMA = BQP; commitments exist unconditionally in the QROM and QHROM.The full result covers arbitrary unitary-oracle distributions, though the class-collapse implication is less straightforward in the general case.Source: §1.1 · p. 2

1.2 Related Work

  • Prior work proves classical Fiat–Shamir security in the QROM for classical Σ-protocols [DFMS19], while QMA proof approaches include designated-verifier systems [ACGH20] [BKL+22] [CVZ20] [MY22].Quantum-message interactive proofs for QMA include zero-knowledge proofs [BG20] and succinct arguments under the quantum PCP conjecture [GJMZ23].Source: §1.2 · p. 3

1.3 Technical Overview

  • Measuring a quantum first message to correlate it with a classical challenge may disturb it and compromise completeness, motivating the counterexample construction.The attack switches from the honest Real channel to Defer, then replaces the prover with a zero-knowledge simulator.Source: §1.3 · pp. 4–5
  • The counterexample encrypts the protocol’s first message under a key in the protocol description, then uses the compiler’s black-box behavior to construct a forgery attack.The resulting attack is used to build a decision algorithm for a QMA-complete language.Source: §1.3 · pp. 3–5
  • Retrospective security lets the authors prove Real and Defer indistinguishable by allowing the key and encryption randomness to be revealed after successful decryption.They derive this property from QCA security using continuity of Stinespring operators.Source: §1.3 · p. 6
  • The proof also addresses a malleability concern: changing a ciphertext’s encryption randomness could distinguish Real from Defer, but QCA-secure ciphertexts are shown not to be malleable in this way.The argument uses an operator-theoretic result.Source: §1.3 · p. 6

2 Preliminaries

The preliminaries establish notation and quantum-information tools, then define the commitment, proof-system, and encryption models used in the paper. These include Ξ-protocols and quantum ciphertext authentication security.

2 Preliminaries

  • The paper defines negligible functions, downward-closed sets, and the Jordan–Hahn decomposition used for Hermitian operators.The decomposition writes X = X+ − X− with positive, orthogonal parts.Source: §2 · p. 7

2.1 Quantum Information

  • Quantum states are density matrices, channels model general evolution, and the diamond norm measures channel distance with contraction under channel composition.The preliminaries also introduce Stinespring dilations and results used later on their continuity and completely positive maps.Source: §2.1 · pp. 7–9

2.2 Quantum Commitments

  • Quantum bit commitments are defined relative to an oracle distribution, with computational hiding and honest statistical binding as their security properties.The paper assumes quantum commitment schemes exist to allow post-quantum zero knowledge in a relativized model.Source: §2.2 · p. 9

2.3 Proof Systems

  • A Ξ-protocol represents the prover by an initial statement-dependent state and a channel responding to the verifier’s challenge, with special honest-verifier zero knowledge.The verifier’s challenge and acceptance are classical, though the verifier is modeled as a quantum channel.Source: §2.3 · pp. 9–10

2.4 Quantum Encryption Schemes

  • The encryption preliminaries define symmetric-key quantum encryption and QCA security by requiring the real effective attack map to be close to a simulated one.The definition permits a rejecting component in the simulated map.Source: §2.4 · pp. 10–11

3 Modelling Quantum Non-Interactivity Compilers (QNICs)

This section formalizes generic black-box compilers that turn quantum interactive proof systems into non-interactive arguments. It focuses on straightline compilers, which make one query to each of the prover and verifier oracles.

3 Modelling Quantum Non-Interactivity Compilers (QNICs)

  • A QNIC is a pair of quantum polynomial-time oracle algorithms that compiles a Ξ-protocol into a non-interactive argument.The compiler definition requires its properties to hold for all languages and Ξ-protocols.Source: §3 · p. 11
  • A straightline QNIC makes only one query to each of its prover and verifier oracles.This restriction concerns those interactions, not access to the global oracle.Source: §3 · p. 12
  • The single-query algorithms decompose into pre- and post-query channels, yielding a circuit representation of an honestly compiled argument.The representation is shown in Figure 5.Source: §3 · p. 12, Figure 5 · p. 12
  • Allowing inverse access to the prover may break zero knowledge, since a trivial compiler could extract and directly use a witness.For straightline QNICs, the paper instead treats prover and verifier access as channels; with one query, inverse access is not meaningful under the stated black-box assumption.Source: §3 · p. 12

4 Ciphertext Authentication & Retrospective Security

This section shows how QCA security enables randomness-preserving, retrospective decryption, allowing ciphertext authentication to defer message choice until after a man-in-the-middle acts. It justifies this deferral by removing Steps 4–5 in Hyb2 via Step 3 post-selection, accounting for tag-register cross terms, and combining Claims 4.1–4.3.

4.3 Deferral Lemma

  • Ciphertext authentication lets the prover defer choosing the encrypted message until after a man-in-the-middle acts, enabling the interaction reordering used in Section 5.The deferral property follows by comparing the real and deferred experiments through retrospective security and post-processing.Source: §4 · p. 13, §4.3 · p. 18

4 Ciphertext Authentication & Retrospective Security

  • For the deferral argument, randomness preservation ensures the real experiment’s output is indistinguishable from one restricted to ciphertexts using the original encryption randomness.Re-encryption in the deferred experiment reuses that randomness, so the restriction prevents a mismatch between the real and deferred outputs.Source: §4 · p. 13, §4.3 · p. 18

4.1 Randomness Preservation

  • QCA security makes the real acceptance branch negligibly close in diamond distance to one that accepts only ciphertexts encrypted with the original randomness.The proof uses a Bell-projection supermap and a retraction argument to establish this randomness-preservation property.Source: §4.1 · pp. 13–14

4.2 Retrospective Security

  • Every QCA-secure SKQES has retrospective security, allowing the encryption key and randomness to be revealed after successful decryption.This property supports data processing when the post-processing depends on the encryption randomness.Source: §4 · p. 13, §4.2 · p. 16

4.3 Deferral Lemma

  • Step 3 post-selection makes Steps 4–5 act as the identity in Hyb2, leaving only the comparison between projectors Πk,r and Πk.Source: §4.3 · p. 19
  • Because decryption traces out the tag register T, Corollary 4.1 does not cover the cross terms; the proof bounds them and the corresponding term as negligible.The proof invokes Hölder’s inequality, convexity of the trace norm, Jensen’s inequality, and the triangle inequality.Source: §4.3 · p. 20
  • Combining Claims 4.1–4.3 by the triangle inequality yields the result.Source: §4.3 · p. 20

5 Impossibility of Straightline QNICs

This section proves that a straightline QNIC with sufficiently small completeness and soundness error yields an efficient decision algorithm for a QMA-complete language, by constructing counterexample Ξ-protocols and combining subchannels for invalid and valid ciphertexts. In the valid-ciphertext case, the proof identifies experiment 3 with honest execution of the compiled argument using a randomly sampled protocol, giving an algorithm whose acceptance bounds differ on yes- and no-instances.

5 Impossibility of Straightline QNICs

  • If ε(n)+2δ(n)<κ*−κ, the decision algorithm accepts yes-instances with probability at least 2δ+κ−negl(n) and no-instances with probability below 2δ+negl(n).For κ≥1/poly(n) and an efficiently simulatable oracle distribution, this implies QMA = BQP.Source: §5 · p. 20

5.1 The Counterexample Protocol

  • The counterexample encrypts the Ξ-protocol’s first-message register under a secret key; its verifier decrypts and rejects invalid plaintexts before running the original verifier.It starts from a QMA-complete Ξ-protocol with negligible soundness, near-perfect completeness, and an SHVZK simulator, alongside a QCA-secure SKQES.Source: §5.1 · pp. 20–21

5.2 The Compiled Counterexample NIZK

  • The proof splits compiled acceptance into valid- and invalid-ciphertext contributions, builds one subchannel for each, and combines them as complementary branches of the decision algorithm.The subchannels post-select without renormalizing, so their acceptance probabilities are unconditional weights.Source: §5.2 · p. 22

5.3 Case 1: Invalid Ciphertexts

  • For invalid ciphertexts, QCA security relates the failed-authentication branch to rejection, while SHVZK permits replacing the honest proof with the simulator in the corresponding hybrid.The resulting invalid-ciphertext subchannel is bounded using compiled-argument soundness; its hybrids preserve acceptance up to negligible differences.Source: §5.3 · pp. 22–24

5.4 Case 2: Valid Ciphertexts

  • For valid ciphertexts, deferring the first message allows replacing the prover with the simulator, and the valid-ciphertext subchannel accepts no-instances with probability below δ(n).The proof derives the soundness bound by turning excessive acceptance into an efficiently prepared state that contradicts δ-soundness; SHVZK and the deferral result support the hybrids.Source: §5.4 · pp. 24–25
  • For x in L, experiment 3 has acceptance μx1 + μx2 and is equivalent to honest execution of the compiled argument with a randomly sampled protocol.This equivalence follows after combining Claims 5.3–5.5.Source: §5.4 · p. 26

5.5 Proof of Theorem 1

  • The efficient algorithm A combines complementary measurement outcomes without post-selection, so its two subchannels’ acceptance weights add exactly.A performs the shared preparation and measurement once, then continues according to the measurement outcome.Source: §5.5 · p. 26
  • 2δ + negl(n) bounds A’s acceptance probability when x /∈ L.Each subchannel contributes less than δ + negl(n).Source: §5.5 · p. 26
  • 2δ + κ − negl(n) lower-bounds A’s acceptance probability when x ∈ L.The bound uses the completeness bound and the hypothesis ε+2δ < κ*−κ.Source: §5.5 · p. 26
Loading 2609.38387v1…