Source-linked AI summary
Succinct Arguments for QMA from Collapsing Hash Functions
James Bartusek, Giulio Malavolta
TL;DR
Known succinct arguments for QMA rely on public-key-style assumptions, unlike classical succinct arguments based on unstructured cryptography. This work uses quantum-succinct claw-state generation and blind delegation to obtain a QMA argument from collapsing hash functions. Its stated construction has polynomial communication and verifier runtime proportional to the statement length times a security-parameter polynomial.
Problem
Known succinct arguments for QMA require public-key-style assumptions, whereas classical succinct arguments can use unstructured cryptography.
Source: §1 · p. 2Method
The authors use quantum-succinct claw-state generation and connect it to blind delegation and communication compression.
Source: §1.2 · p. 4, §5 · p. 19Results
Assuming collapsing hash functions, the QMA argument has completeness 1 − negl(λ), soundness error negl(λ), total communication poly(λ), and verifier runtime |x| · poly(λ).
Source: §1.1 · p. 2Takeaways & Limitations
Succinct arguments for QMA exist in Minicrypt assuming only collapsing hash functions.
Source: §1 · p. 2, §1.1 · p. 3The protocol uses quantum communication, and its non-black-box use of collapsing hashes does not automatically yield a QROM-secure succinct argument.
Source: §1.1 · pp. 2–3
Abstract
from arXiv · showhide
We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state generation} protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.
1 Introduction
The paper addresses the gap between classical succinct arguments, which use unstructured cryptography, and known succinct arguments for QMA, which require public-key-style assumptions. It establishes QMA succinct arguments from collapsing hash functions and outlines a quantum-succinct claw-state protocol as the route to that result.
1 Introduction
- The paper targets the gap between classical succinct arguments from unstructured cryptography and known QMA succinct arguments requiring public-key-style assumptions.The existing QMA construction described here uses collapsing hashes and oblivious state preparation, while the classical NP setting needs collision-resistant hashes.Source: §1 · p. 2
1.1 Results
- Assuming collapsing hash functions, the QMA argument has completeness 1 − negl(λ), soundness error negl(λ), total communication poly(λ), and verifier runtime |x| · poly(λ), without the quantum PCP conjecture.The stated verifier runtime does not depend on witness length or the original verifier’s runtime.Source: §1.1 · pp. 2–3
1.2 Technical Outline
- The authors relax blind delegation to allow fixed polynomial client quantum work, then connect claw-state generation to blind delegation and communication compression.This provides a route from the claw-state protocol to succinct arguments for QMA.Source: §1.2 · p. 4, Putting Things Together · p. 7
- Compared with Zhang [Zha21], the claw-generation approach is simpler, targets round efficiency, and avoids relying on the quantum random-oracle model.Zhang’s protocol is described as having round complexity polynomial in T and security proved in the quantum random-oracle model.Source: §1.2 · p. 5
- Sequential repetition for quantum search games uses QSVT rewinding to condition on later successes and derive exponentially decreasing combined success.The reduction handles arbitrary retained quantum memory and postponed predictions; the stated combined-claw guessing bound is 4^-λ + negl(λ).Source: §1.2 · pp. 6–7
- Using quantum-secure one-way functions, their claw-state protocol supports any polynomial T with poly(λ)-round interaction and client quantum preparation cost poly(λ, log T).The communication is quantum only from client to server, and the client’s circuits are fixed before interaction.Source: §1.2 · p. 5, Putting Things Together · p. 7
1.3 Concurrent work
- Concurrent work also constructs succinct arguments for QMA in Minicrypt, but uses a different approach and does not claim a plain-model construction.It compiles a quantum IOP and proves security in the quantum random-oracle model.Source: §1.3 · p. 7
1.4 AI usage
- The authors report that AI tools assisted with protocol refinement, technical proofs, exposition, and reference checking, while the overall architecture and proof strategy were developed without AI.Source: §1.4 · p. 7
2 Preliminaries
This section fixes the paper’s security and notation conventions, defines succinct arguments for QMA and claw states, and specifies the pseudorandom functions used in the construction.
2 Preliminaries
- The preliminaries fix security against non-uniform QPT adversaries with auxiliary states independent of fresh honest randomness, and define the paper’s register and norm notation.Succinctness-bound polynomials are fixed independently of the original verification time and witness size.Source: §2 · p. 8
2.1 Succinct Arguments for QMA
- Succinct arguments for QMA require correctness and soundness while limiting communication to poly(λ) and verifier complexity to |x| · poly(λ).The verifier bound is independent of the witness length and the time required to run the original QMA verifier.Source: §2.1 · p. 8
2.2 Claw States
- A uniformly sampled claw state is hard to guess: any adversary’s success probability is at most 2^(1−n).The experiment gives the adversary the claw state for random x0, x1 and asks it to return both strings.Source: §2.2 · p. 9
2.3 Pseudorandom Functions
- The paper assumes a target-entry pseudorandomness property for functions with polynomial-size domains, implied by the standard pseudorandom-function definition.Such functions can be constructed from quantum-secure one-way functions.Source: §2.3 · pp. 9–10
3 Claw-State Generation Protocol
The protocol uses a client-server interaction to generate claw states, with the client’s quantum work restricted to a poly(log T, n, λ) runtime. Its analysis bounds a server’s probability of passing the checks and guessing a randomly targeted claw by 1/4 plus a negligible term.
3.1 Protocol Description
- The client’s quantum runtime is poly(log T, n, λ), while its classical runtime and the server’s total runtime are poly(T, n, λ).The protocol returns a list of output pairs when the client’s checks succeed.Source: §3.1 · p. 11
- The honest server passes the protocol except with probability at most (log T)2^−n.The protocol’s checks use the server’s Hadamard-basis measurement outcomes.Source: §3.1 · p. 11
3.2 Analysis
- When n = Ω(λ), assuming quantum-secure one-way functions, every QPT server’s probability of returning the target pair and passing the client’s checks is at most 1/4 + µ(λ), for negligible µ.Source: §3.2 · p. 11
4 Sequential Repetition
This section presents a sequential repetition theorem for quantum interactive search games, where an adversary may retain quantum memory across copies. The proof reduces repeated-game success to a single-game bound through a recurrence on suffix success probabilities.
4 Sequential Repetition
- A quantum interactive search game is an interactive protocol in which the prover’s goal is to guess a secret string and the verifier accepts or rejects.In sequential copies, the adversary can preserve arbitrary quantum memory and postpone predictions until all interactions end.Source: §4 · p. 15
- Theorem 4.4 gives a generic sequential repetition bound for any quantum interactive search game when every QPT adversary’s single-game success is at most ε(λ) plus negligible.The repeated game uses fresh verifier randomness and workspace for each copy, while the adversary may delay its predictions until the interactions finish.Source: §4 · p. 16
- The proof tracks q_j, the maximum probability of guessing all targets from copy j onward, and derives q_1 ≤ ε^ℓ + ℓ·negl(λ).The argument establishes a recurrence between adjacent suffix probabilities and uses uniform singular value amplification in one case.Source: §4 · pp. 16–17
5 Succinct Arguments for QMA
Section 5 builds a quantum-succinct, history-independent claw-state protocol, transforms it into blind delegation, and combines blind delegation with communication compression to obtain succinct arguments for QMA.
5 Succinct Arguments for QMA
- The client’s quantum messages are prepared before interaction and are independent of the protocol transcript, making the claw-state protocol quantum-succinct and history-independent.Its preparation circuits use a short sampled key and efficient PRF evaluation.Source: §5 · p. 19
- Honest execution produces the claimed server state and client string pairs except with negligible probability.The abort probability across the λ weak-protocol copies is at most λ(log T)2^-n = negl(λ).Source: §5 · pp. 19–20
- Even given all other string pairs, a quantum polynomial-time server has negligible probability of returning a target pair without client abort, assuming quantum-secure one-way functions.The protocol also makes recovery of any pair hard without being given the other strings.Source: §5 · p. 20
5.1 Blind Delegation
- Assuming quantum-secure one-way functions, the construction yields quantum-succinct, history-independent blind delegation for polynomial-size circuits with poly(λ, δ) rounds.The construction transforms claw-state correlations into BB84 correlations and then into blind delegation; the transformations use classical communication and preserve quantum-succinctness and history-independence.Source: §5.1 · pp. 21–22
5.2 Putting Things Together
- A blind delegation protocol with poly(λ, δ) rounds gives a QMA argument with negligible completeness loss, constant soundness, and a fixed polynomial number of rounds.When the blind delegation protocol is quantum-succinct and history-independent, the resulting argument retains those properties.Source: §5.2 · p. 22
- Assuming collapsing hash functions, the compiled QMA argument has completeness 1−negl(λ), constant soundness, polynomial communication, and verifier runtime |x| · poly(λ).Sequential repetition yields the paper’s main result, Theorem 1.1.Source: §5.2 · pp. 23–24