Paper 2026/1215

On the Cryptographic Structure Required for Verifying Qubits

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 𝑃₀, 𝑃₁ depending on the verifier's challenge bit 𝑐. 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 𝐷 over pairs (𝑥,𝑏) such that quantum circuits have advantage at most 𝛿 in predicting 𝑏 from 𝑥, there exists a sub-distribution 𝑀≼𝐷 of density 1-𝛿 on which 𝑏 is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most 𝛿 in guessing a private challenger bit 𝑏, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits 𝑏₁⊕𝑏₂ to at most 𝛿² + negl(𝜆).