On the Cryptographic Structure Required for Verifying Qubits
Pith reviewed 2026-06-28 01:47 UTC · model grok-4.3
The pith
Tests of non-commutation imply classical key agreement, and with one-way functions imply oblivious transfer.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For a broad range of parameters, a test of non-commutation (an interactive protocol in which the prover measures one of two anti-commuting observables P0 or P1 according to the verifier's challenge bit) implies classical-communication key agreement; when combined with one-way functions it also implies oblivious transfer. The paper further proves a post-quantum hard-core measure theorem and a post-quantum interactive XOR lemma that amplify hardness for these primitives.
What carries the argument
The ToNC protocol, in which the prover's final response is obtained by measuring one of two anti-commuting binary observables chosen by the verifier's challenge bit.
If this is right
- ToNC yields post-quantum key agreement using only classical communication.
- ToNC plus one-way functions yields post-quantum oblivious transfer.
- The hard-core measure theorem extracts a large sub-distribution on which the bit is nearly optimally hard for quantum predictors.
- Two sequential repetitions of any classically interactive protocol reduce quantum advantage on the XOR of challenge bits to roughly the square of the original advantage.
Where Pith is reading between the lines
- Quantum verification protocols that rely on anti-commutation tests carry enough structure to support cryptographic key agreement.
- Weakening the anti-commutation requirement in a verification test would likely remove the ability to base key agreement on the test alone.
- The new amplification lemmas may apply to other post-quantum two-party primitives whose security is defined via classical interaction.
Load-bearing premise
The prover's response must come from measuring one of two anti-commuting observables selected by the challenge bit.
What would settle it
An explicit ToNC protocol together with a quantum strategy that passes the test yet allows a quantum adversary to predict the challenge bit with non-negligible advantage, breaking the implied key agreement.
Figures
read the original abstract
Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computation. While such tests can be based on cryptographic assumptions, known constructions rely on highly structured assumptions, e.g. trapdoor claw-free functions. In this work, we seek to explain this state of affairs by constructing strong cryptography from (certain forms of) classical tests of anti-commutation. In particular, we formulate the notion of a test of non-commutation (ToNC), an interactive protocol between a quantum prover and classical verifier in which the prover's final-round response is obtained by measuring one of two binary observables $P_0,P_1$ depending on the verifier's challenge bit $c$. We prove that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA), and ToNC combined with one-way functions implies oblivious transfer (OT). Along the way, we develop tools for and provide the first known results on hardness amplification for post-quantum KA and OT, where communication is classical but adversaries may be quantum. In particular, we prove the following results of independent interest. - Post-quantum hard-core measure theorem: For any efficiently sampleable high-min-entropy distribution $D$ over pairs $(x,b)$ such that quantum circuits have advantage at most $\delta$ in predicting $b$ from $x$, there exists a sub-distribution $M\preceq D$ of density $(1-\delta)$ on which $b$ is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most $\delta$ in guessing a private challenger bit $b$, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits $b_1\oplus b_2$ to at most $\delta^2+\rm{negl}(\lambda)$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces the notion of a test of non-commutation (ToNC): an interactive protocol in which a quantum prover responds to a classical verifier's challenge bit c by measuring one of two anti-commuting binary observables P0 or P1. It proves that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA) and, when combined with one-way functions, implies oblivious transfer (OT). The paper also establishes two results of independent interest: a post-quantum hard-core measure theorem (any high-min-entropy distribution D with quantum advantage at most δ admits a sub-distribution M of density 1-δ on which b is nearly optimally hard to predict) and a post-quantum interactive XOR lemma (two sequential repetitions reduce advantage in guessing the XOR of challenger bits to at most δ² + negl(λ)).
Significance. If the stated reductions hold, the work supplies a concrete explanation for the necessity of structured assumptions (such as trapdoor claw-free functions) in classical verification of quantum computation: even the minimal anti-commutation test already yields KA and OT. The hardness-amplification tools are the first explicit results for post-quantum KA/OT with classical communication and quantum adversaries; they rest on the anti-commutation property for unpredictability and on standard post-quantum assumptions rather than fitted parameters or circular reductions.
minor comments (1)
- §2: the precise parameter ranges for which the KA implication holds are stated only in the theorem statements; a consolidated table or corollary summarizing the admissible (δ, ε, λ) regimes would improve readability.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and for recommending acceptance. We appreciate the recognition of the significance of deriving key agreement and oblivious transfer from tests of non-commutation, as well as the value of the post-quantum hardness amplification results.
Circularity Check
No significant circularity; derivation self-contained
full rationale
The paper defines ToNC via an interactive protocol using anti-commuting binary observables P0 and P1 chosen by challenge bit c, then proves implications to classical-communication KA (via post-quantum hard-core measure theorem and interactive XOR lemma) and to OT (when combined with OWFs). These steps are constructed from the protocol definition plus standard assumptions and newly proven amplification results; no step reduces by construction to a fitted parameter, self-citation chain, or renamed input. The hardness amplification theorems are presented as independent of the target implications and do not rely on the final KA/OT statements.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Quantum mechanics allows measurement of binary observables that may anti-commute
Reference graph
Works this paper leans on
-
[1]
On the impossibility of key agreements from quantum random oracles
[ACC+22] Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody. On the impossibility of key agreements from quantum random oracles. InAdvances in Cryptology – CRYPTO 2022: 42nd Annual International Cryptology Con- ference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part II, page 165–194, Berlin, H...
2022
-
[2]
Kahanamoku-Meyer, Eitan Po- rat, and Thomas Vidick
[BGKM+23] Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Po- rat, and Thomas Vidick. Simple tests of quantumness also certify qubits. In Helena Handschuh and Anna Lysyanskaya, editors,Advances in Cryptology – CRYPTO 2023, pages 162–191, Cham,
2023
-
[3]
[BK25] James Bartusek and Dakshita Khurana
Springer Nature Switzerland. [BK25] James Bartusek and Dakshita Khurana. On the power of oblivious state preparation. InAdvances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Con- ference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part II, page 575–607, Berlin, Heidelberg,
2025
-
[4]
[BMM25] Pedro Branco, Giulio Malavolta, and Zayd Maradni
Springer-Verlag. [BMM25] Pedro Branco, Giulio Malavolta, and Zayd Maradni. Fully-homomorphic encryption from lattice isomorphism. InTheory of Cryptography: 23rd International Conference, TCC 2025, Aarhus, Denmark, December 1–5, 2025, Proceedings, Part I, page 220–252, Berlin, Heidelberg,
2025
-
[5]
[BQSY24] John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen
Springer-Verlag. [BQSY24] John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen. An efficient quan- tum parallel repetition theorem and applications. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1478–1487, New York, NY, USA,
2024
-
[6]
[CMM+26] David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, and Tina Zhang
Springer Berlin Heidelberg. [CMM+26] David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, and Tina Zhang. A Computational Tsirelson’s The- orem for the Value of Compiled XOR Games.Quantum, 10:1987, January
1987
-
[7]
Secure two-party quantum evaluation of unitaries against specious adversaries
71 [DNS10] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Secure two-party quantum evaluation of unitaries against specious adversaries. In Tal Rabin, editor,Advances in Cryptology – CRYPTO 2010, pages 685–706, Berlin, Heidelberg,
2010
-
[8]
Computationally-secure and compos- able remote state preparation.2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1024–1033,
[GV19] Alexandru Gheorghiu and Thomas Vidick. Computationally-secure and compos- able remote state preparation.2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1024–1033,
2019
-
[9]
Parallel repetition for post-quantum argu- ments
[HK25] Andrew Huang and Yael Tauman Kalai. Parallel repetition for post-quantum argu- ments. Cryptology ePrint Archive, Paper 2025/1027,
2025
-
[10]
72 [KLVY23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang
Association for Computing Machinery. 72 [KLVY23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advan- tage from any non-local game. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1617–1628, New York, NY, USA,
2023
-
[11]
Commitments from quantum one-wayness
[KT24] Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 968–978, New York, NY, USA,
2024
-
[12]
[LLLL25] Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu
Association for Computing Machinery. [LLLL25] Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Cryptomania v.s. Minicrypt in a Quantum World. Cryptology ePrint Archive, Paper 2025/639,
2025
-
[13]
[MV21] Tony Metger and Thomas Vidick
Asso- ciation for Computing Machinery. [MV21] Tony Metger and Thomas Vidick. Self-Testing of a Single Quantum Device Under Computational Assumptions. In James R. Lee, editor,12th Innovations in Theoreti- cal Computer Science Conference (ITCS 2021), volume 185 ofLeibniz International Pro- ceedings in Informatics (LIPIcs), pages 19:1–19:12, Dagstuhl, Germany,
2021
-
[14]
A quantum approach for reducing communications in classical secure computations with long outputs
[Zha23] Jiayu Zhang. A quantum approach for reducing communications in classical secure computations with long outputs. Cryptology ePrint Archive, Paper 2023/1492,
2023
-
[15]
Formulations and Constructions of Remote State Preparation with Verifiability, with Applications
[Zha25] Jiayu Zhang. Formulations and Constructions of Remote State Preparation with Verifiability, with Applications. In Raghu Meka, editor,16th Innovations in Theoreti- cal Computer Science Conference (ITCS 2025), volume 325 ofLeibniz International Pro- ceedings in Informatics (LIPIcs), pages 96:1–96:19, Dagstuhl, Germany,
2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.