betaFeedback

WorksPhysics and Astronomy

The Entire Quantum Computer on a Classical Leash

Abstract

We show that a classical client with no quantum hardware can use a single untrusted and potentially malicious quantum server as if it were its own trusted quantum computer. Through the server, the client can privately choose and run quantum computations, prepare quantum states, and process quantum states supplied by other parties. It can also keep quantum memory on the server, hidden from the server itself, and use that memory in later computations so its quantum state persists across rounds of interaction. Together, these capabilities let a purely classical party act as a quantum party in a variety of interactive protocols. We expect this virtual quantum computer to be a broadly useful tool. As immediate applications, we resolve two known open problems: (1) classical verification of quantum sampling with negligible computational soundness error, and (2) remote state preparation of arbitrary efficiently preparable quantum states. Underlying all of these results is a general-purpose, maliciously secure two-party computation protocol between a classical client and a quantum server, which we construct assuming only the post-quantum hardness of learning with errors.

Introduction

Can a classical party use an adversary’s quantum computer as its own trusted quantum device?

Mahadev’s breakthrough [33] demonstrated that a classical party can verify quantum decision problems, even when the quantum computation is performed by an untrusted prover. A quantum computer, however, provides much more than answers to decision problems. It can sample from distributions, prepare quantum states for other parties, process quantum states received from them, and retain quantum information across successive computations. These capabilities are central to quantum cryptography, where security can depend on information being encoded in a quantum state rather than revealed through a classical description. Participating in such a protocol may require a party to keep private quantum memory, manipulate it in response to incoming messages, and release only selected outputs. This raises a broader question:

Can a classical client obtain the capabilities of a trusted quantum computer through classical interaction with a single untrusted quantum server?

Even restricted versions of this goal remain unresolved as we discuss below.

SampBQP Verification. A natural first step beyond decision problems is to ask a quantum server to sample the classical output of a prescribed quantum circuit. This task, known as classical verification of SampBQP, requires the client to verify the distribution of the output, rather than a single decision bit. Prior work [CLLW22] makes progress on this question, but is limited to soundness error that is inversely proportional to the number of repetitions, leaving the following question open.

Can classical verification of SampBQP be achieved with negligible error?

Remote State Preparation. Quantum outputs introduce a further challenge: correctness alone may not capture the desired cryptographic guarantee. Consider, for example, a classical party that wishes to give a quantum adversary an unclonable quantum ciphertext. The classical party may know how to prepare the ciphertext, but sending these instructions to the quantum device would defeat the purpose: the adversary could generate as many ciphertexts as it likes. Asking the adversary to prove that it prepared the correct state does not resolve this problem either, since correctness alone says nothing about the additional copies or information it may have retained. We would like the adversary to learn only what it could have learned from receiving a single quantum ciphertext, even though it performs every quantum operation involved in preparing that ciphertext!

The example above is a special case of what is known as (verifiable) remote state preparation (RSP) in the literature [24]. RSP allows a classical party to “send” a quantum state ∣ψ⟩|\psi\rangle to a quantum party, as long as it knows a classical description of a quantum circuit that efficiently prepares the state. The goal is for the quantum party to receive no more information than if it had directly received ∣ψ⟩|\psi\rangle.

There has been meaningful progress on building RSP for restricted state families with inverse-polynomial error [24, 20]. For cryptography, such a loss can overwhelm the security guarantee altogether: in the case of the unclonable encryption example discussed earlier, this leaves room for an adversary to succeed with inverse-polynomial probability where the ideal quantum protocol permits only negligible success. Thus, seven years after its introduction, the main question about RSP has remained open:

Can remote state preparation be obtained for arbitrary efficiently computable states with negligible error?

Stateful Multi-Round Protocols, Beyond RSP. A key motivation for the introduction of RSP was to allow a classical client to effectively assume the role of a quantum party in an interactive protocol. But enabling this requires an even stronger form of classical control: we want the classical device to be able to direct the quantum device through multiple rounds of interaction, with assured privacy and a guarantee that any deviations will be detected.

Let us explain what we are looking for in more detail. Imagine a classical client with a trusted quantum computer of its own. The client could privately choose a computation, apply it to a quantum state received from another party, and return a quantum output. It could then keep part of the state as private memory, and use it in a later computation to return another output, and so on. We would like to faithfully reproduce this entire interaction when all of the quantum hardware is instead controlled by another party, who may be malicious. The client should communicate only classically, yet retain the privacy and control that its own quantum computer would have provided.

The Obstacle: Testing Destroys the Output. A central obstacle is that checking a quantum computation can destroy the very state we wanted to use. This is relatively harmless when the goal is to learn a decision: after obtaining enough evidence for the answer, we can discard the computation. It becomes a serious problem when the goal is to obtain a sample or continue computing on a quantum output. Evidence that a state was correct is of little use if producing that evidence consumes the state.

One natural approach is to ask the server for many candidate states, test most of them, and retain an untested state for use. This approach underlies the classical verification of SampBQP [CLLW22]. However, testing polynomially many candidates leaves an inverse-polynomial opportunity for an incorrect state to escape inspection. For decision computations, independent repetition and majority can reduce a bounded error to negligible. For general sampling tasks and quantum outputs, there is no analogous generic operation that combines several moderately reliable outputs into one negligibly erroneous output.

There is a further difficulty. Even if a test preserves an honest server’s state, what prevents a malicious server from replacing its state after passing the test? To support a sequence of computations, the client needs a guarantee about the same evolving quantum state throughout the interaction. It must be possible to test that state without destroying it, continue using the state, and keep the server bound to the result of each operation.

Obtaining this guarantee through classical communication is the central technical challenge addressed by our work.

Main Result

Our main construction is a two-party computation protocol between a classical client and a quantum server for general real quantum circuits.

  • The client supplies a private classical input which may specify a classical description of (1) the desired quantum circuit CC and (2) an efficient preparation procedure for an initial state ∣ψC⟩\lvert\psi_C \rangle.

  • The server supplies an arbitrary quantum input, possibly entangled with an external reference.

  • The computation returns designated classical outputs to the client and prescribed quantum outputs to the server. The parties may choose to discard some output wires so their state/value is returned to neither party.

Figure 1 illustrates the ideal functionality.

Figure 1. The ideal quantum two-party functionality (abort omitted). The client’s private input ww specifies UwU_w, which acts on the server’s input register SS and zero-initialized ancillas AA. It returns BB to the server, measures CC in the computational basis to produce the client’s output yy, and discards DD. The possibly entangled external reference EE is untouched. Our protocol realizes this functionality using only classical communication.

Theorem 1 (Informal). Assuming the post-quantum hardness of LWE, there exists an interactive protocol for secure quantum computation of real quantum circuits between a classical client and a quantum server which achieves simulation-based security with abort with an ϵ\epsilon-simulator.

Here, ε\varepsilon-simulation means that, for every inverse-polynomial ε>0\varepsilon> 0, there is a simulator running in time polynomial in the security parameter, the computation size, and 1/ε1/\varepsilon, whose ideal execution is indistinguishable from the real execution up to computational advantage ε\varepsilon. Crucially, the protocol itself and the honest parties’ running times are independent of ε\varepsilon. This guarantee suffices to preserve negligible security loss in any efficiently testable cryptographic game: any inverse-polynomial violation would yield an attack on the ideal functionality by choosing ε\varepsilon sufficiently smaller than the violating advantage. We highlight some example applications below where we get the standard (negligible-error) indistinguishability-based security.

Remark 1. At the end of § 2.1, we isolate a particular primitive whose construction with negligible security would generically lift our results to negligible-loss simulation.1

The restriction to real gates is inherent to any classical-communication protocol and is not overly restrictive. It is well-established that any quantum circuit with complex gates can be generically converted into one with real gates, with a specific input-encoding [BV93]. Moreover, many of the example applications we mention below natively use real quantum circuits.

Private Quantum Memory Across Computations. The sequential composition of our protocol also allows the classical client to maintain private quantum memory on the server across a polynomial number of sequential computations. At each stage, the client can privately choose the next computation, process the stored memory together with newly supplied quantum inputs, and obtain designated outputs while retaining the remaining state for future use. The quantum server is prevented from tampering with the persistent memory by authenticating it between each computation. The resulting interaction admits ε\varepsilon-simulation with abort, including when the memory is entangled with an external system. This gives the client the capabilities of a trusted quantum computer whose state persists across interactions. We describe this extension in § 7.

Applications.

We highlight a few consequences and applications of our main result below.

Verification of quantum sampling. Chung, Lee, Lin, and Wu [CLLW22] gave classical verification of SampBQP with inverse-polynomial computational soundness error and explicitly asked whether negligible soundness error is possible. We resolve this question for verification of the output distribution of a prescribed quantum circuit.

Corollary 1 (Verification of Quantum Sampling, Informal). Let CC be an efficient quantum circuit with classical output distribution DD.

Assuming the post-quantum hardness of LWE, there exists a classical verification of quantum sampling protocol where the classical client’s output distribution is computationally indistinguishable from DD (conditioned on the quantum server not causing an abort).

The negligible error here is the additional error introduced by verification. It is separate from the statistical approximation allowed in the definition of SampBQP: if CC samples from DD with ∥D−D∗∥TV≤δ\lVert D-D^*\rVert_{\mathrm{TV}}\le\delta for a target distribution D∗D^*, then the corresponding joint decision-and-output distribution has computational distinguishing error at most δ+negl⁡(λ)\delta+\operatorname{negl}(\lambda) relative to ideal sampling from D∗D^*. Our result does not require the quantum sampler’s approximation error δ\delta itself to be negligible. See § 8.1.1.

Remote state preparation. Prior RSP protocols prepare states from restricted families with security error scaling inversely with the protocol length TT [24, 20]. When the time TT protocol is used to replace a round of quantum communication in a falsifiable game GQG_Q to obtain GCG_C, the error permits an inverse polynomial increase in the maximum winning probability of any QPT adversary adv\mathit{adv}:

max⁡QPT advPr⁡[win⁡GC]≤max⁡QPT advPr⁡[win⁡GQ]+1poly⁡(T)\max_{\mathrm{QPT}\ \mathit{adv}}\Pr[\operatorname{win}G_C]\le\max_{\mathrm{QPT}\ \mathit{adv}}\Pr[\operatorname{win}G_Q]+\frac{1}{\operatorname{poly}(T)}

Gheorghiu, Metger, and Poremba explicitly ask how to obtain negligible security error in the cryptographic applications of RSP. Our construction addresses this question through ϵ\epsilon-simulation and also supports arbitrary (real) efficiently preparable states chosen by the sender.

Corollary 2 (Remote State Preparation, Informal). Let ∣ψ⟩|\psi\rangle be any state which can be efficiently prepared by a real circuit.

Assuming the post-quantum hardness of LWE, there exists a remote state preparation protocol with ϵ\epsilon-simulation for ∣ψ⟩|\psi\rangle. As a result, it has standard (negligible error) falsifiable security:

max⁡QPT advPr⁡[win⁡GC]≤max⁡QPT advPr⁡[win⁡GQ]+negl⁡(λ)\max_{\mathrm{QPT}\ \mathit{adv}}\Pr[\operatorname{win}G_C]\le\max_{\mathrm{QPT}\ \mathit{adv}}\Pr[\operatorname{win}G_Q]+\operatorname{negl}(\lambda)

Here, arbitrary means any efficiently preparable state chosen through the sender’s private classical description—not an unknown state supplied to the classical sender.

This is an ϵ\epsilon-simulation guarantee but its cryptographic applications can nevertheless have negligible security loss. For example, the client can remotely prepare an unclonable quantum ciphertext without revealing its preparation procedure. Replacing quantum transmission by this protocol preserves the original unclonability game’s security bound up to a negligible additive term: any inverse-polynomial excess winning probability would contradict the original scheme’s security by choosing ϵ\epsilon sufficiently smaller than that excess. Thus the receiver’s participation in preparing the ciphertext does not give it a non-negligible advantage in producing two usable ciphertexts. See § 8.1.2 and § 9.

Classical revocation of leased quantum keys. Secure key leasing allows a user to borrow a quantum decryption key, with the guarantee that returning a key that passes verification removes the user’s ability to decrypt, as formalized by the scheme’s security game [3]. In the quantum-return formulation, revocation requires the lessor to receive and verify a quantum key. A classical revocation protocol removes that requirement, allowing the lessor to verify surrender of the decryption capability through classical interaction alone.

Corollary 3 (Classical Revocation of Quantum States, Informal). Assuming the post-quantum hardness of LWE, every secure key leasing scheme with efficient quantum verification admits an interactive revocation protocol using only classical communication. The compiled scheme preserves security after revocation up to negligible loss.

The parties securely evaluate the scheme’s verification procedure on the lessee’s quantum input and the lessor’s private verification key, return the verification decision to the lessor, and discard the submitted key registers. This application illustrates the ability to process and consume a quantum input already held by an adversary.

Other Applications. § 9 develops the following additional applications:

  • Unclonable encryption over a classical channel (§ 9.1).

  • Public-key quantum money with a classical bank from polynomial hardness (§ 9.1.1).

  • Improved extraction for classical-verifier arguments of quantum knowledge (§ 9.1.2).

  • Secure key leasing with proofs of no-intrusion (§ 9.1.3).

  • Quantum obfuscation with interactive classical communication (§ 9.1.4).

We provide more details about these applications in § 2.3.

Technical Overview

We begin with an overview of our approach for a slightly less ambitious task: verifying a single general quantum computation where the circuit U=UT∘⋯∘U1U = U_T \circ\cdots\circ U_1 is public. After computing UU, the classical party’s output register CC is measured in the computational basis and the discarded register DD is traced out.

History State Verification. Feynman’s famed clock construction succinctly encodes the entirety of any quantum computation as a single quantum state: the “history” state. As computation progresses, the initial input and ancillas ∣ψ0⟩=∣in⟩⊗∣0⟩|\psi_0\rangle= |{\rm in}\rangle\otimes|0\rangle evolves into ∣ψ1⟩=U1∣ψ0⟩|\psi_1\rangle= U_1|\psi_0\rangle, then into ∣ψ2⟩=U2∣ψ1⟩|\psi_2\rangle= U_2|\psi_1\rangle, and so on. The history state encodes all steps of the evolution in superposition over the timestep tt:

∑t=1T∣t⟩⊗∣ψt⟩\sum_{t=1}^{T} |t\rangle\otimes|\psi_t\rangle

Now measure the clock register, and get a time tt. If tt is maximal at t=Tt = T, then the residual state is the output of the computation: ∣ψT⟩\lvert\psi_T\rangle. Moreover, a history state can be tested via a series of projective measurements [29].

This suggests a general template for enforcing delegated computation for any publicly known circuit. Suppose the client had a trusted measurement device which could hold a state and perform simple measurements on it. Then:

  1. The server sends a history state of the computation to the trusted measurement device.

  1. The measurement device tests the received state by measuring whether it violates any history state invariants.

  1. The measurement device measures the clock to get a time tt.

    • If t<Tt < T: send ∣ψt⟩\lvert\psi_t\rangle back to the server for another try.

    • If t=Tt = T, measure register C\mathcal{C} and discard register D\mathcal{D}.

Implementing the Trusted Measurement Device. Mahadev [33] took the first step towards implementing this template for a classical client. Following her approach, we will replace the trusted measurement device with a commitment which can be opened to measurement results of the committed state:

  1. The server commits to a history state.

  1. The client picks a measurement test and asks the server to give an opening for that measurement. It repeats this multiple times to amplify soundness.

  1. The client asks the server to open the clock register in the computational basis to get the time tt. If t=Tt = T, the server is committed to ∣ψT⟩\lvert\psi_T\rangle and can open to a measurement of it.

The limitation of Mahadev’s commitment is that it only supports a complete measurement of the committed state (in either the computational or Hadamard basis). This destroys the state completely, preventing amplification and ruining the output step. Still, the collected statistics from one test are sufficient for deciding decision problems like BQP or QMA.

[CLLW22] opened the approach to verifying quantum sampling tasks (SampBQP) by committing to many states, then testing all-but-one of them. The remaining untested state is likely to be a history state, except with ≈1/N\approx1/N probability where NN is the number of states committed to. So, it can be measured to get the output sample in step 3.

Non-Destructive Testing. To transcend the 1/N1/N limit, the client must test a state, then use the same tested state for output. This requires, at a minimum, that the test not destroy the committed history state.

[27] gave a general approach to making classical verification of QMA non-destructive. In the context of Mahadev’s protocol, an important part of their approach is to avoid directly measuring the commitment openings. Instead, the prover proves the existence of openings which the verifier would accept in a special NP argument which avoids collapsing superpositions over NP witnesses. When paired with a high-completeness ZX Hamiltonian [34], the prover’s opening register is entirely supported on openings which the verifier would accept, and so is not disturbed by the witness-preserving argument.

We adopt a similar approach, but with a few important modifications. [27]’s NP argument requires that the prover knows the statement it is proving – which requires revealing the decoding key for the commitment. Once the key is revealed, the tested state is no longer bound by the original commitment.2 A malicious server can swap it out before the next test or output step.

Safely Verifying Openings. We insulate the client’s decoding key by designing a witness-preserving argument for NP where the precise statement being proven is hidden from the prover. In other words: a secure two-party computation (2PC) for classical functionalities which preserves the quantum party’s input. In its most general form, the goal is to measure some secret classical function ff on the quantum party’s input, then return the residual state:

  1. Input: The classical client inputs a classical function ff. The quantum server inputs a superposition ∣ψ⟩=∑vαv∣v⟩|\psi\rangle= \sum_v \alpha_v |v\rangle.

  1. Output: Measure y=f(v)y = f(v) on the quantum party’s input. Send yy to the classical party and return the residual quantum state ∣ψy⟩∝∑v:f(v)=yαv∣v⟩|\psi_y\rangle\propto\sum_{v:f(v)=y} \alpha_v |v\rangle to the quantum party.

Importantly, the 2PC hides ff, up to whatever is necessarily revealed by the residual state ∣ψy⟩|\psi_y\rangle. Now the client can input its decoding key as part of a function ff which checks for accepting openings, and be assured that the decoding key is hidden.

Constructing such a 2PC for general ff is difficult. Instead, we construct a 2PC for constant-degree multilinear polynomials. This suffices for testing committed history states because we use a commitment with linear decoding and the history state Hamiltonian has constant locality, so their composition is a constant degree multilinear polynomial. See § 2.1 for more details.

Ensuring Commitment Continuity. Simply hiding the decoding key does not ensure binding after a decoding query, though. The adversary can potentially learn enough to break binding through its residual state ∣ψy⟩|\psi_y\rangle, or even through the client’s decision of whether to continue or abort.

We define and construct a new classical commitment to quantum states with continual ideal binding.

  • Ideal binding refers to a strong, simulation-based definition wherein there is a well-defined quantum state which the adversarial committer can open to. Notably, the

committed state is defined with overwhelming probability whenever the commitment phase passes; prior works allow an adversary to cause a δ\sqrt{\delta} extraction error by giving invalid openings with probability δ\delta [19].

  • Continual refers to the preservation of ideal binding even after making multiple queries to a decoding oracle. Decoding queries allow the adversary to modify the committed state by measuring the decoding results. Continual binding requires that the adversarial committer is still bound to the post-measurement state after each measurement.

Together, these two properties allow us to reason about the residual committed state after doing multiple measurement tests. If the adversary passes all of the tests, the residual committed state must be negligibly far from a history state. We also show how the client can help the server to recover the committed state after testing it, which allows a coherent output in the overall protocol.

Our construction leverages a close connection between authentication and commitments. Essentially, we build a remote state preparation protocol for [4]’s coset-state authentication code. The client can help the server to remotely authenticate any state of the server’s choice, under the client’s key. Moreover, [4]’s authentication code has linear decoding, so it is compatible with our linear input-preserving 2PC. See § 2.2 for more details.

Summary of the Approach for Public Computations. Putting everything together, our approach for verifying public computations is as follows.

  1. The server commits to a history state.

  1. The client repeatedly runs gentle tests on the committed state by using the state-preserving 2PC for classical (linear) functions. The server inputs an opening, and the state-preserving 2PC measures only whether the opening corresponds to a valid history state.

  1. The client asks the server to open the clock register to a time tt.

    • If t<Tt < T, the client helps the server recover the whole ∣ψt⟩\lvert\psi_t\rangle. Then, the server uncomputes Ut∘⋯∘U1U_t \circ\cdots\circ U_1 and they restart the protocol.

    • If t=Tt = T, the server sends the client’s output by opening the classical register CC in the computational basis. Then, the client helps the server recover its output register BB from the commitment. Register DD is not recovered.

Wrapping Up: Privacy and Persistent Memory. So far, we have only addressed computations where the server knows the description U=(U1,…,UT)U = (U_1,\ldots,U_T) and can choose the input. How can the client hide UU from the server? And if it wants to do a follow-up computation V=(V1,…,VT′)V = (V_1,\ldots,V_{T'}), how can it ensure that UU’s output ∣ψT⟩\lvert\psi_T\rangle is used as the input to VV?

The first question can be addressed using quantum fully-homomorphic encryption (QFHE). Instead of directly telling the server the classical description of UU, the client encrypts it under a QFHE as U~\widetilde{U} and asks the server to homomorphically evaluate the universal circuit on U~\widetilde{U} and the input. If the QFHE is circuit-private, the (honestly) evaluated output ∣ψT~⟩\lvert\widetilde{\psi_T}\rangle is statistically independent of U~\widetilde{U} and can be safely decrypted. There is a crucial technical subtlety for circuit privacy: the public computation needs to hide the ancillas used for QFHE evaluation. This is implemented in the 2PC by discarding register D\mathcal{D}.

Next, we use private computation to implement persistent memory. Suppose that the client wants to perform a computation UU, save some memory, and later use that memory for another computation VV. Since UU is hidden, the client may safely embed an authentication key kk into it. The modified U′U' performs the original UU, then authenticates the output ∣ψT⟩\lvert\psi_T\rangle under kk. This also ensures hiding of ∣ψT⟩\lvert\psi_T\rangle between computations since quantum authentication is necessarily hiding [5]. Then, the client embeds kk into VV so that V′V' first verifies and decodes the authenticated ∣ψT⟩\lvert\psi_T\rangle before using it.

Simulation Error. Our construction ultimately achieves ϵ\epsilon-simulation, meaning that for every ϵ=1/poly⁡(λ)\epsilon= 1/\operatorname{poly}(\lambda), there is 1/ϵ1/\epsilon-time simulator that is indistinguishable from the real execution except with probability ϵ\epsilon. This arises from the input-preserving linear 2PC and propagates through the rest of the primitives we construct. If one could achieve negligible simulation error input-preserving 2PC, then it would immediately improve the main result to also have negligible simulation error. We discuss this point further at the end of § 2.1.

Input-Preserving 2PC for Classical Constant-Degree Polynomials

The first step to our solution is a input-preserving 2PC for classical functions ff which are constant degree multilinear polynomials over F2\mathbb{F}_2. We also extend the behavior slightly to allow the classical party to abort if f(v)f(\mathbf{v}) is not an allowed output. This addition is useful for checking the openings of our commitments: decoding applies a linear function, then checks whether a post-fix of the output is 0\mathbf{0}. In case it is not, the 2PC has measured more than is strictly necessary for decoding and so it might not be safe to return the post-measurement state. Output-checking can be easily added to our construction since the classical party gets its output before the recovery process begins for the quantum party’s output.

Simplifications. We make two simplifications for this task. First, it suffices to construct an input-preserving 2PC only for linear ff. To upgrade to a polynomial with maximum degree cc, the quantum party may reversibly extend its input to include all degree-cc monomials. If cc is constant, this is a polynomial blow-up. Then, the classical party uses the linearized version of ff whose coefficients are all the monomials of ff. The goal is thus to realize the following functionality:

  1. Input: The classical client inputs a classical linear function L∈F2ℓ×mL \in\mathbb{F}_2^{\ell\times m}. The quantum server inputs a superposition ∣ψ⟩=∑vαv∣v⟩\lvert\psi\rangle= \sum_{\mathbf{v}} \alpha_{\mathbf{v}}\lvert\mathbf{v}\rangle.

  1. Output: Measure u=Lv\mathbf{u}=L\mathbf{v} on the quantum party’s input. Send u\mathbf{u} to the classical party. Then, if u\mathbf{u} is an allowed output, return the residual quantum state ∣ψu⟩∝∑v:Lv=uαv∣v⟩|\psi_{\mathbf{u}}\rangle\propto\sum_{\mathbf{v}:L\mathbf{v}=\mathbf{u}}\alpha_{\mathbf{v}}|\mathbf{v}\rangle to the quantum party.

Second, we show security against arbitrary malicious quantum parties, but only against honest-but-curious classical parties. An honest-but-curious party follows the protocol exactly, but may nevertheless be a QPT algorithm. Upgrading security for the classical party can be done generically [22, 25]: the classical party proves in zero-knowledge for NP that each message is correctly computed. The same transformation does not work against the quantum party because the correctness of its messages are not necessarily even QMA statements. Security against a semi-honest classical party is more straightforward, so for the purposes of this overview we just describe security against a malicious quantum party.

Protocol. For the purposes of the overview, we focus on L∈F21×mL\in\mathbb{F}_2^{1\times m} which only contain 1 row. The main tool we use is a noisy trapdoor claw-free function (NTCF) with the adaptive hardcore bit property [BCM+18]. Roughly, this is a 2→12\to1 function which can be inverted using a secret trapdoor. Moreover, the adaptive hardcore bit property guarantees that it is hard to find inner products with the difference between collisions (x0⊕x1)⋅d(x_0\oplus x_1)\cdot\mathbf{d}, even if d\mathbf{d} is chosen by the adversary. The protocol can be broadly separated into 4 phases.

  1. Input Commitment. The classical party samples mm NTCF public parameters and trapdoors (ppi,tdi)(\mathsf{pp}_i,\mathsf{td}_i). The quantum party now commits to each bit viv_i of their input v\mathbf{v} by coherently evaluating the NTCF ppi\mathsf{pp}_i on viv_i and measuring the output yiy_i. This leaves them with the state

∑vαv∣v⟩⨂i=1m∣xi,vi⟩\sum_{\mathbf{v}}\alpha_{\mathbf{v}}|\mathbf{v}\rangle\bigotimes_{i=1}^{m}|x_{i,v_i}\rangle

References

  1. [1]Scott Aaronson. Limitations of quantum advice and one-way communication. In 19th IEEE Annual Conference on Computational Complexity (CCC 2004), pages 320–332. IEEE, 2004.
  2. [2]Mark Adcock and Richard Cleve. A quantum Goldreich-Levin theorem with cryptographic applications. In Helmut Alt and Afonso Ferreira, editors, STACS 2002, volume 2285 of Lecture Notes in Computer Science, pages 323–334, Berlin, Heidelberg, 2002. Springer.
  3. [3]Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa. Public key encryption with secure key leasing. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 581–610. Springer, Cham, April 2023.arxiv.org/abs/2302.11663
  4. [4]James Bartusek, Zvika Brakerski, and Vinod Vaikuntanathan. Quantum state obfuscation from classical oracles. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 1009–1017. ACM Press, June 2024.arxiv.org/abs/2401.10200
  5. [5]Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. Authentication of quantum messages. In 43rd FOCS, pages 449–458. IEEE Computer Society Press, November 2002.
  6. [6]James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. On the round complexity of secure quantum computation. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 406–435, Virtual Event, August 2021. Springer, Cham.arxiv.org/abs/2011.11212
  7. [8]James Bartusek, Aparna Gupte, Saachi Mutreja, and Omri Shmueli. Classical obfuscation of quantum circuits via publicly-verifiable QFHE. In 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026). IEEE, 2026. To appear. Full version: https://arxiv.org/abs/2510.08400.
  8. [9]Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 609–629. Springer, Berlin, Heidelberg, August 2015.
  9. [10]James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, and Lisa Yang. Succinct classical verification of quantum computation. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 195–211. Springer, Cham, August 2022.arxiv.org/abs/2206.14929
  10. [11]Anne Broadbent and Sébastien Lord. Uncloneable quantum encryption via oracles. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.DOI
  11. [12]Zvika Brakerski. Quantum FHE (almost) as secure as classical. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 67–95. Springer, Cham, August 2018.DOI
  12. [14]Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, and Takashi Yamakawa. On the impossibility of post-quantum black-box zero-knowledge in constant round. In 62nd FOCS, pages 59–67. IEEE Computer Society Press, February 2022.DOI
  13. [16]Libor Caha, Zeph Landau, and Daniel Nagaj. Clocks in feynman’s computer and kitaev’s local hamiltonian: Bias, gaps, idling, and pulse tuning. Physical Review A, 97(6):062306, 2018.DOI
  14. [17]Shujiao Cao and Rui Xue. The gap is sensitive to size of preimages: Collapsing property doesn’t go beyond quantum collision-resistance for preimages bounded hash functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part III, volume 13509 of LNCS, pages 564–595. Springer, Cham, August 2022.DOI
  15. [18]Joseph F. Fitzsimons, Michal Hajdušek, and Tomoyuki Morimae. Post hoc verification of quantum computation. Physical Review Letters, 120(4):040501, 2018.DOI
  16. [19]Sam Gunn, Yael Tauman Kalai, Anand Natarajan, and Agi Villanyi. Classical commitments to quantum states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025). ACM, 2025.DOI
  17. [20]Alexandru Gheorghiu, Tony Metger, and Alexander Poremba. Quantum cryptography with classical communication: Parallel remote state preparation for copy-protection, verification, and more. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, ICALP 2023, volume 261 of LIPIcs, pages 67:1–67:17. Schloss Dagstuhl, July 2023.
  18. [21]Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In 27th FOCS, pages 174–187. IEEE Computer Society Press, October 1986.
  19. [22]Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218–229. ACM Press, May 1987.
  20. [23]Vipul Goyal and Justin Raizes. Proofs of no intrusion. In Joan Daemen and Emmanuel Thomé, editors, EUROCRYPT 2026, Part I, volume 16541 of LNCS, pages 510–540. Springer, Cham, May 2026.arxiv.org/abs/2510.06432
  21. [24]Alexandru Gheorghiu and Thomas Vidick. Computationally-secure and composable remote state preparation. In David Zuckerman, editor, 60th FOCS, pages 1024–1033. IEEE Computer Society Press, November 2019.arxiv.org/abs/1904.06320
  22. [25]Sean Hallgren, Adam Smith, and Fang Song. Classical cryptographic protocols in a quantum world. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 411–428. Springer, Berlin, Heidelberg, August 2011.
  23. [26]Mi-Ying Miryam Huang and Er-Cheng Tang. Obfuscation of unitary quantum programs. In 66th FOCS, pages 1665–1671. IEEE Computer Society Press, October 2025.arxiv.org/abs/2507.11970
  24. [27]Yael Tauman Kalai, Dakshita Khurana, and Justin Raizes. How to classically verify a quantum cat without killing it. IACR Cryptol. ePrint Arch., 2026:210, 2026.arxiv.org/abs/2602.09282
  25. [28]Yael Tauman Kalai and Justin Raizes. Semi-quantum cryptography with certified deletion, 2026.arxiv.org/abs/2609.38915
  26. [29]Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002.
  27. [30]Alex Lombardi, Fermi Ma, and Nicholas Spooner. Post-quantum zero knowledge, revisited or: How to do quantum rewinding undetectably. In 63rd FOCS, pages 851–859. IEEE Computer Society Press, October / November 2022.arxiv.org/abs/2111.12257
  28. [31]Zhengnan Lai, Nicholas Spooner, and Max Tromanhauser. How to define expected quantum polynomial-time zero knowledge simulation. In Theory of Cryptography – TCC 2026. Springer, 2026. To appear. Full version: https://eprint.iacr.org/2026/1500.DOI
  29. [32]Urmila Mahadev. Classical homomorphic encryption for quantum circuits. In Mikkel Thorup, editor, 59th FOCS, pages 332–338. IEEE Computer Society Press, October 2018.arxiv.org/abs/1708.02130
  30. [33]Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267, Paris, France, 2018. IEEE.
  31. [34]Henry Ma and Anand Natarajan. Two bases suffice for qma₁-completeness. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics, pages 101:1–101:22, 2026.arxiv.org/abs/2509.24390
  32. [35]Omri Shmueli. Public-key quantum money with a classical bank. In Stefano Leonardi and Anupam Gupta, editors, 54th ACM STOC, pages 790–803. ACM Press, June 2022.
  33. [36]Omri Shmueli and Mark Zhandry. On one-shot signatures, quantum vs. classical binding, and obfuscating permutations. In Yael Tauman Kalai and Seny F. Kamara, editors, CRYPTO 2025, Part II, volume 16001 of LNCS, pages 350–383. Springer, Cham, August 2025.arxiv.org/abs/2507.12456
  34. [37]Thomas Vidick and Tina Zhang. Classical proofs of quantum knowledge. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, volume 12697 of Lecture Notes in Computer Science, pages 630–660, Cham, 2021. Springer.arxiv.org/abs/2005.01691
  35. [38]Andreas Winter. Coding theorem and strong converse for quantum channels. IEEE Transactions on Information Theory, 45(7):2481–2485, 1999.DOI
  36. [39]Mark Zhandry. Quantum lightning never strikes the same state twice. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 408–438. Springer, Cham, May 2019.arxiv.org/abs/1711.02276
  37. [40]Mark Zhandry. New constructions of collapsing hashes. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part III, volume 13509 of LNCS, pages 596–624. Springer, Cham, August 2022.DOI

Paper details

vlnc:W_hp7uqjv3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

ChatGPT 6.0

View statement
Looking for related papers…
Contents