We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018). We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work). Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE.
We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018). We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work). Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE.
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.
We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work of Mahadev (FOCS '18), Bartusek et al. (CRYPTo ‘22) also constructed a succinct classical argument system for Q M A. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC '23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP * = R E in Quantum complexity.
Properties of quantum mechanics such as entanglement and the no-cloning theorem enable new forms of cryptography that are unattainable in classical models of computation. Quantum information, however, is harder to process, store, and transmit than classical information. As such, it is desirable to construct semi-quantum cryptographic protocols where only a subset of the parties have quantum capabilities while the rest operate classically. In this dissertation, we analyze the security of semi-quantum protocols based on two approaches: (i) nonlocality-based techniques and (ii) the hardness of the Learning with Errors (LWE) problem. In the first part of the dissertation, we leverage a form of Bell test to construct a quantum position verification (QPV) protocol. Initial QPV protocols required verifiers to prepare and send quantum states to an honest prover to achieve security against adversaries with bounded memory or entanglement. Later work constructed QPV protocols with classical verifiers but required additional assumptions such as the hardness of LWE or of random circuit sampling. We construct a variant of QPV where classical verifiers verify the spatial locations of two provers. We use the nonlocal correlations produced by the two provers to show security against adversaries with bounded quantum memory without making any computational intractability assumptions. In the second part of the dissertation, we use trapdoor claw-free functions (TCFs) to construct semi-quantum cryptographic protocols. TCFs, which are constructible from the hardness of LWE, have been shown to be immensely valuable in the construction of classically verifiable quantum cryptographic protocols. As opposed to previous work where the server is asked to prepare a claw state and perform Pauli-X and Z measurements, we use a technique that leverages the entire range of qubit measurements on the XY-plane. We use this technique to construct three protocols: (i) a one-round blind remote state preparation protocol that delegates the preparation of an arbitrary state on the XY-plane up to a Pauli-X correction; (ii) a two-round proof of quantumness whose security is directly in terms of the hardness of LWE and only requires the prover to prepare and measure a single claw state; and (iii) a 1-of-2 Puzzle with a single qubit auxiliary state.
A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probability. A protocol claiming to classically verify QMA should offer the same guarantee: any witness that would convince a quantum verifier should also suffice to convince a classical verifier. Unfortunately, existing classical verification of quantum computation (CVQC) protocols behave quite differently from the original QMA verifier: they require many copies of the witness and destroy every one, effectively demanding that the prover solve the hard problem of witness duplication before verification can begin.
We build a protocol to classically verify QMA languages that uses a single copy of the prover's QMA witness. Whenever the original QMA verifier accepts that witness with overwhelming probability, our protocol has negligible completeness and soundness errors and returns the witness negligibly disturbed after interaction with an honest verifier. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption.
As an intermediate step of independent interest, we introduce witness-preserving classical arguments for NP which enable provers that start out with a superposition over NP witnesses to convince a verifier without disturbing their superposition.
We consider a new model for the testing of untrusted quantum devices, consisting of a single polynomial time bounded quantum device interacting with a classical polynomial time verifier. In this model, we propose solutions to two tasks—a protocol for efficient classical verification that the untrusted device is “truly quantum” and a protocol for producing certifiable randomness from a single untrusted quantum device. Our solution relies on the existence of a new cryptographic primitive for constraining the power of an untrusted quantum device: post-quantum secure trapdoor claw-free functions that must satisfy an adaptive hardcore bit property. We show how to construct this primitive based on the hardness of the learning with errors (LWE) problem.
We obtain the first constant-round post-quantum multi-party computation protocol for general classical functionalities in the plain model, with security against malicious corruptions. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption. Along the way, we also construct the following protocols that may be of independent interest.
(1) Constant-round zero-knowledge against parallel quantum verifiers from quantum polynomial assumptions.
Here, we develop a novel parallel no-cloning non-black-box simulation technique. This uses as a starting point the recently introduced no-cloning technique of Bitansky and Shmueli (STOC 2020) and Ananth and La Placa (ePrint 2019), which in turns builds on the classical non-black-box technique of Bitansky, Khurana and Paneth (STOC 2019). Our approach relies on a new technical tool, spooky encryption for relations computable by quantum circuits, that we also construct.
(2) Constant-round post-quantum non-malleable commitments from mildly super-polynomial quantum hardness of LWE.
This is the first construction of post-quantum non-malleable commitments in the plain model, and is obtained by transforming the construction of Khurana and Sahai (FOCS 2017) to obtain post-quantum security.
We achieve quantum security by building a new straight-line non-black-box simulator against parallel verifiers that does not clone the adversary's state. This technique may also be relevant to the classical setting.