pith. sign in

arxiv: 2606.10408 · v1 · pith:YY2C53SAnew · submitted 2026-06-03 · 🪐 quant-ph · cs.CC· cs.CR

A Modular Approach to Succinct Arguments for QMA

James Bartusek , Jiahui Liu , Giulio Malavolta This is my paper

Pith reviewed 2026-06-28 05:26 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.CR
keywords succinct argumentsQMAoblivious state preparationcollapsing hash functionstrapdoor claw-free functionsclassically verifiable proofsquantum interactive proofs
0
0 comments X

The pith

Succinct classically verifiable arguments for QMA exist from trapdoor claw-free functions plus collapsing hashes, without LWE.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs the first succinct argument system for QMA that is classically verifiable and does not rely on the learning-with-errors assumption. It proceeds by first building a round-efficient interactive protocol solely from an oblivious state preparation primitive, then applying a new compression compiler that uses collapsing hash functions to bound total communication by the number of rounds times a fixed polynomial in the security parameter. A sympathetic reader cares because this broadens the cryptographic foundations of quantum proof systems beyond highly structured assumptions to ones closer to those sufficient for classical NP.

Core claim

The authors show that the combination of an oblivious state preparation protocol (constructible from plain trapdoor claw-free functions) and collapsing hash functions is sufficient to obtain a succinct classically-verifiable argument system for QMA. The construction first yields a round-efficient protocol from OSP alone and then invokes a generalized communication-compression compiler to reduce message sizes.

What carries the argument

The oblivious state preparation (OSP) protocol, which prepares a quantum state without revealing the basis, combined with a generalized communication compression compiler that reduces any T-round protocol to communication size T times a fixed polynomial using collapsing hash functions.

If this is right

  • Any future improvement to OSP security or efficiency immediately yields a corresponding improvement to succinct QMA arguments.
  • The compression compiler applies to any T-round interactive protocol, not just the QMA one constructed here.
  • Round efficiency and communication compression are separated into independent modular steps.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If plain trapdoor claw-free functions can be instantiated from assumptions weaker than LWE, the entire argument system would inherit that weakness.
  • The same modular split may allow succinct arguments for other quantum complexity classes once suitable state-preparation primitives are identified.

Load-bearing premise

An oblivious state preparation protocol exists and can be built from plain trapdoor claw-free functions.

What would settle it

An explicit attack on the OSP protocol that allows a malicious prover to pass verification for a false QMA statement while the verifier remains classical and efficient.

read the original abstract

Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92) established that any probabilistically checkable proof for NP can be transformed into a succinct argument system for NP using only collision-resistant hash functions. In the quantum setting, recent works have established the feasibility of (classically-verifiable) succinct arguments for QMA, capturing statements that require *quantum* proofs. However, known constructions all rely on the highly structured assumption of learning with errors (LWE), which stands in stark contrast with the unstructured assumptions that suffice for NP. In this work, we develop a new framework that broadens the cryptographic foundations of succinct arguments for QMA. We assume the existence of (i) an oblivious state preparation (OSP) protocol, which in turn can be constructed from *plain* trapdoor claw-free functions, and (ii) collapsing hash functions, the quantum analogue of collision-resistance. In particular, we obtain the first succinct, classically-verifiable argument system for QMA which does not rely on the hardness of LWE. Our construction proceeds in two steps. First, we design a *round-efficient* classically-verifiable argument system for QMA based only on the assumption of OSP. Second, we introduce a *generalized communication compression compiler*, which, assuming collapsing hash functions, transforms any $T$-round interactive protocol into one in which the communication size is bounded by $T \cdot \poly(\secp)$ for some fixed $\poly$ independent of the original size of each message. Our compiler extends a quantum rigidity-based communication compression technique of Zhang (QCrypt 25), and may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to construct the first succinct classically-verifiable argument system for QMA that avoids LWE, by assuming (i) an oblivious state preparation (OSP) protocol constructible from plain trapdoor claw-free functions and (ii) collapsing hash functions. The two-step approach first builds a round-efficient interactive argument from OSP alone, then applies a generalized communication compression compiler (extending Zhang QCrypt 25) that bounds total communication by T · poly(λ) under collapsing hashes.

Significance. If the OSP protocol exists and is secure under only plain TCF (without LWE or structured assumptions), the result would meaningfully broaden the assumption landscape for quantum succinct arguments beyond the LWE-based constructions in prior work. The modular separation and the compression compiler are potentially reusable; the paper explicitly credits the two-step structure and the extension of rigidity-based compression.

major comments (2)
  1. [Construction section, first paragraph] Construction section, first paragraph: the central LWE-free claim rests on the existence of an OSP protocol 'which in turn can be constructed from plain trapdoor claw-free functions.' The manuscript must supply (or give a precise citation to) a full security reduction establishing that the required OSP properties hold under the plain TCF assumption alone; any implicit use of LWE-style structure for quantum security or obliviousness would invalidate the separation from LWE.
  2. [round-efficient argument section] § on the round-efficient argument (the first step): the security definition and the exact interface required from the OSP protocol are not stated with sufficient precision to verify that the reduction to OSP is tight and that no additional assumptions are introduced when composing with the subsequent compiler.
minor comments (2)
  1. [Abstract] Abstract: 'crytpography' is a typo.
  2. Notation for security parameter and message sizes should be introduced once and used consistently across the two steps and the compiler.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and valuable feedback on our manuscript. We address each major comment below and will revise the paper to improve precision and clarity.

read point-by-point responses

  1. Referee: [Construction section, first paragraph] Construction section, first paragraph: the central LWE-free claim rests on the existence of an OSP protocol 'which in turn can be constructed from plain trapdoor claw-free functions.' The manuscript must supply (or give a precise citation to) a full security reduction establishing that the required OSP properties hold under the plain TCF assumption alone; any implicit use of LWE-style structure for quantum security or obliviousness would invalidate the separation from LWE.

    Authors: We appreciate the referee's emphasis on making the LWE-free claim fully rigorous. The OSP construction from plain trapdoor claw-free functions follows from the standard quantum-secure reduction in the TCF literature (without LWE or structured assumptions). We will add an explicit citation to the relevant prior work establishing this reduction and include a brief outline of how the required OSP properties (correctness, obliviousness) are obtained directly from plain TCF to ensure the separation is self-contained. revision: yes

  2. Referee: [round-efficient argument section] § on the round-efficient argument (the first step): the security definition and the exact interface required from the OSP protocol are not stated with sufficient precision to verify that the reduction to OSP is tight and that no additional assumptions are introduced when composing with the subsequent compiler.

    Authors: We agree that the OSP interface and security definition merit a more formal treatment. In the revision we will state the precise OSP functionality (including the exact security properties of state preparation, obliviousness, and soundness) and provide a detailed, tight reduction from the round-efficient argument to the OSP assumption. We will also explicitly confirm that the subsequent composition with the generalized communication compression compiler introduces no further assumptions. revision: yes

Circularity Check

0 steps flagged

No circularity; modular reduction to external primitives

full rationale

The paper's derivation explicitly assumes the existence of an OSP protocol (constructible from plain trapdoor claw-free functions) and collapsing hash functions as inputs, then builds a round-efficient argument and applies a generalized compression compiler extending Zhang (QCrypt 25). No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided text. The central claim of an LWE-free succinct QMA argument is conditioned on these external assumptions rather than reducing to them by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on two standard cryptographic assumptions treated as black boxes; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • domain assumption Existence of oblivious state preparation (OSP) protocol constructible from plain trapdoor claw-free functions
    Used as the sole assumption for the round-efficient interactive argument (abstract, construction overview).
  • domain assumption Existence of collapsing hash functions
    Used to realize the generalized communication compression compiler (abstract, second step).

pith-pipeline@v0.9.1-grok · 5854 in / 1232 out tokens · 22739 ms · 2026-06-28T05:26:26.026383+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 11 canonical work pages

  1. [1]

    Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    Optimal algorithms and inapproximability results for every CSP? , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

  2. [2]

    Positive polynomial , note =

  3. [3]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    On learning mixtures of well-separated gaussians , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  4. [4]

    arXiv preprint quant-ph/0206070 , year=

    A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities , author=. arXiv preprint quant-ph/0206070 , year=

    Pith/arXiv arXiv

  5. [5]

    Physical review letters , volume=

    Simple unified form for the major no-hidden-variables theorems , author=. Physical review letters , volume=. 1990 , publisher=

    1990

  6. [6]

    Physics Letters A , volume=

    Incompatible results of quantum measurements , author=. Physics Letters A , volume=. 1990 , publisher=

    1990

  7. [7]

    arXiv preprint arXiv:2402.17301 , year=

    A computational tsirelson's theorem for the value of compiled XOR games , author=. arXiv preprint arXiv:2402.17301 , year=

    arXiv

  8. [8]

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  9. [9]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Quantum advantage from any non-local game , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  10. [10]

    Annual International Cryptology Conference , pages=

    On the power of oblivious state preparation , author=. Annual International Cryptology Conference , pages=. 2025 , organization=

    2025

  11. [11]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Succinct arguments for QMA from standard assumptions via compiled nonlocal games , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

    2024

  12. [12]

    Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=

    Constant-round blind classical verification of quantum sampling , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2022 , organization=

    2022

  13. [13]

    and Porat, Eitan and Vidick, Thomas

    Zvika and Gheorghiu, Alexandru and Kahanamoku-Meyer, Gregory D. and Porat, Eitan and Vidick, Thomas. Simple Tests of Quantumness Also Certify Qubits. Advances in Cryptology -- CRYPTO 2023. 2023

    2023

  14. [14]

    Conference on Learning Theory , pages=

    Learning multivariate log-concave distributions , author=. Conference on Learning Theory , pages=. 2017 , organization=

    2017

  15. [15]

    arXiv preprint arXiv:1711.07465 , year=

    Better agnostic clustering via relaxed tensor norms , author=. arXiv preprint arXiv:1711.07465 , year=

    Pith/arXiv arXiv

  16. [16]

    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Mixture models, robustness, and sum of squares proofs , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  17. [17]

    and Porat, Eitan and Vidick, Thomas

    Brakerski, Zvika and Gheorghiu, Alexandru and Kahanamoku-Meyer, Gregory D. and Porat, Eitan and Vidick, Thomas. Simple Tests of Quantumness Also Certify Qubits. Advances in Cryptology -- CRYPTO 2023. 2023

    2023

  18. [18]

    A New Framework for Quantum Oblivious Transfer

    Agarwal, Amit and Bartusek, James and Khurana, Dakshita and Kumar, Nishant. A New Framework for Quantum Oblivious Transfer. Advances in Cryptology -- EUROCRYPT 2023. 2023

    2023

  19. [19]

    2023 , url =

    Jiayu Zhang , title =. 2023 , url =

    2023

  20. [20]

    2024 , url =

    James Bartusek and Dakshita Khurana , title =. 2024 , url =

    2024

  21. [21]

    2025 , eprint=

    Formulations and Constructions of Remote State Preparation with Verifiability, with Applications , author=. 2025 , eprint=

    2025

  22. [22]

    Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC) , pages =

    Joe Kilian , title =. Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 1992 , doi =

    1992

  23. [23]

    Advances in Cryptology -- CRYPTO 2022, Lecture Notes in Computer Science , series =

    James Bartusek and Yael Tauman Kalai and Alex Lombardi and Fermi Ma and Giulio Malavolta and Vinod Vaikuntanathan and Thomas Vidick and Lisa Yang , title =. Advances in Cryptology -- CRYPTO 2022, Lecture Notes in Computer Science , series =. 2022 , publisher =. doi:10.1007/978-3-031-15979-4_7 , url =

    work page doi:10.1007/978-3-031-15979-4_7 2022

  24. [24]

    In: Proceedings of the ACM Symposium on Theory of Computing (STOC)

    Gunn, Sam and Tauman Kalai, Yael and Natarajan, Anand and Vill\'. Classical Commitments to Quantum States , year =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =. doi:10.1145/3717823.3718264 , abstract =

    work page doi:10.1145/3717823.3718264

  25. [25]

    Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu and Szegedy, Mario , title =. J. ACM , month = may, pages =. 1998 , issue_date =. doi:10.1145/278298.278306 , abstract =

    work page doi:10.1145/278298.278306 1998

  26. [26]

    Arora, Sanjeev and Safra, Shmuel , title =. J. ACM , month = jan, pages =. 1998 , issue_date =. doi:10.1145/273865.273901 , abstract =

    work page doi:10.1145/273865.273901 1998

  27. [27]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    Gunn, Sam and Ju, Nathan and Ma, Fermi and Zhandry, Mark , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =. 2023 , isbn =. doi:10.1145/3564246.3585198 , abstract =

    work page doi:10.1145/3564246.3585198 2023

  28. [28]

    2013 , eprint=

    The Quantum PCP Conjecture , author=. 2013 , eprint=

    2013

  29. [29]

    Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS 2018) , pages =

    Urmila Mahadev , title =. Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS 2018) , pages =. 2018 , publisher =. doi:10.1109/FOCS.2018.00040 , url =

    work page doi:10.1109/focs.2018.00040 2018

  30. [30]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Urmila Mahadev , title =. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2018 , publisher =. doi:10.1109/FOCS.2018.00038 , url =

    work page doi:10.1109/focs.2018.00038 2018

  31. [31]

    Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part II , pages =

    Bacho, Kaniuar and Kulpe, Alexander and Malavolta, Giulio and Schmidt, Simon and Walter, Michael , title =. Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part II , pages =. 2025 , isbn =. doi:10.1007/978-3-032-01878-6_21 , abstract =

    work page doi:10.1007/978-3-032-01878-6_21 2025

  32. [32]

    A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device , year=

    Brakerski, Zvika and Christiano, Paul and Mahadev, Urmila and Vazirani, Umesh and Vidick, Thomas , booktitle=. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device , year=

  33. [33]

    Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I , pages =

    Alamati, Navid and Malavolta, Giulio and Rahimi, Ahmadreza , title =. Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I , pages =. 2022 , isbn =. doi:10.1007/978-3-031-22318-1_10 , abstract =

    work page doi:10.1007/978-3-031-22318-1_10 2022

  34. [34]

    2025 , url =

    Pedro Branco and Giulio Malavolta and Zayd Maradni , title =. 2025 , url =

    2025

  35. [35]

    Advances in Cryptology --

    Dominique Unruh , title =. Advances in Cryptology --. 2016 , doi =

    2016

  36. [36]

    2022 , volume =

    Chiesa, Alessandro and Ma, Fermi and Spooner, Nicholas and Zhandry, Mark , booktitle =. 2022 , volume =. doi:10.1109/FOCS52979.2021.00014 , url =

    work page doi:10.1109/focs52979.2021.00014 2022

  37. [37]

    Annual International Cryptology Conference , pages=

    New constructions of collapsing hashes , author=. Annual International Cryptology Conference , pages=. 2022 , organization=

    2022

  38. [38]

    Annual International Cryptology Conference , pages=

    Robust quantum public-key encryption with applications to quantum key distribution , author=. Annual International Cryptology Conference , pages=. 2024 , organization=

    2024

  39. [39]

    Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=

    From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2023 , organization=

    2023

  40. [40]

    arXiv preprint arXiv:2009.07450 , year=

    On the hardness of detecting macroscopic superpositions , author=. arXiv preprint arXiv:2009.07450 , year=

    arXiv 2009

  41. [41]

    27th annual symposium on foundations of computer science (Sfcs 1986) , pages=

    How to generate and exchange secrets , author=. 27th annual symposium on foundations of computer science (Sfcs 1986) , pages=. 1986 , organization=

    1986

  42. [42]

    2018 , publisher=

    The theory of quantum information , author=. 2018 , publisher=

    2018

  43. [43]

    2010 , publisher=

    Quantum computation and quantum information , author=. 2010 , publisher=

    2010

  44. [44]

    Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=

    Computationally binding quantum commitments , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2016 , organization=

    2016

  45. [45]

    2020 , note=

    Interactions with Quantum Devices (Course) , author=. 2020 , note=

    2020

  46. [46]

    and Grilo, Alex B

    Alagic, Gorjan and Childs, Andrew M. and Grilo, Alex B. and Hung, Shih-Han , title =. Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part III , pages =. 2020 , isbn =. doi:10.1007/978-3-030-64381-2_6 , abstract =

    work page doi:10.1007/978-3-030-64381-2_6 2020

  47. [47]

    On the Communication Complexity of Secure Function Evaluation with Long Output , booktitle =

    Pavel Hub. On the Communication Complexity of Secure Function Evaluation with Long Output , booktitle =. 2015 , doi =

    2015

  48. [48]

    2022 , organization=

    Lombardi, Alex and Ma, Fermi and Spooner, Nicholas , booktitle=. 2022 , organization=

    2022

  49. [49]

    Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666 , pages =

    Unruh, Dominique , title =. Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666 , pages =. 2016 , isbn =

    2016

  50. [50]

    How to Construct Quantum FHE, Generically

    Gupte, Aparna and Vaikuntanathan, Vinod. How to Construct Quantum FHE, Generically. Advances in Cryptology -- CRYPTO 2024. 2024

    2024

  51. [51]

    Bartusek, James and Liu, Jiahui and Malavolta, Giulio , title =