The Entire Quantum Computer on a Classical Leash

Yael Tauman Kalai; Dakshita Khurana; Justin Raizes

Source-linked AI summary

The Entire Quantum Computer on a Classical Leash

Yael Tauman Kalai, Dakshita Khurana, Justin Raizes

arXiv:2610.31775v1Oct 22, 2026quant-phcs.CR

TL;DR

Classical clients lack quantum hardware, yet quantum protocols can require private state manipulation and memory across interactions. The paper constructs a secure classical-communication protocol for a classical client and an untrusted quantum server, assuming post-quantum LWE hardness. It applies this approach to negligible-error verification of quantum sampling and remote preparation of arbitrary efficiently preparable real states.

Problem
A classical client needs trusted-computer capabilities—including private state processing and persistent quantum memory—to participate in quantum protocols, but prior sampling verification had only inverse-repetition soundness.
Source: §1 · p. 4
Method
Assuming post-quantum LWE hardness, the authors construct a simulation-secure protocol for real quantum circuits between a classical client and a quantum server, with simulation error ϵ and protocol runtime independent of ϵ.
Source: §1.1 · pp. 6–7
Results
The protocol gives classical verification of a circuit’s output distribution with negligible additional verification error, while allowing the circuit’s sampling approximation error δ to remain non-negligible.
Source: §1.2 · p. 8
Takeaways & Limitations
The protocol supports remote preparation of arbitrary efficiently preparable real states with ϵ-simulation, enabling cryptographic applications with negligible security loss.
Source: §1.2 · p. 8
The main construction achieves ϵ-simulation rather than negligible simulation error; negligible error would require an input-preserving 2PC primitive with that guarantee.
Source: §2 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether a classical client can use one untrusted quantum server to obtain trusted-computer capabilities beyond decision problems, including state preparation, state processing, and persistent quantum memory. It presents a secure classical-communication protocol and applications to quantum sampling, remote state preparation, and other cryptographic tasks.

Remote State Preparation.

Remote state preparation lets a classical sender convey a state from an efficient circuit description while revealing no more than direct receipt of that state.Prior work covered restricted families with inverse-polynomial error; the paper targets arbitrary efficiently computable states with negligible error.Source: Remote State Preparation · pp. 4–5
A key challenge is verifying a quantum state without consuming it, so the client can keep using the same state and bind the server to each operation.Testing many candidate states leaves an inverse-polynomial chance of an incorrect state escaping inspection, with no generic way to combine moderately reliable outputs into a negligibly erroneous one.Source: Remote State Preparation · p. 5

1.1 Main Result

Assuming post-quantum LWE hardness, the authors give a classical-client/quantum-server protocol for secure computation of real quantum circuits with simulation-based security and abort.For every inverse-polynomial ϵ, an efficient simulator achieves distinguishing advantage ϵ, while the protocol and honest parties’ running times do not depend on ϵ.Source: §1.1 · pp. 6–7
Sequential composition lets the client retain authenticated private quantum memory on the server across polynomially many computations, including memory entangled with an external system.The client can process that memory with new quantum inputs, receive designated outputs, and retain the remaining state for later computations.Source: §1.1 · p. 7

1.2 Applications.

The protocol resolves the open question of classical verification of a prescribed quantum circuit’s output distribution with negligible additional verification error, assuming post-quantum LWE hardness.The sampler’s own statistical approximation error δ need not be negligible; the joint decision-and-output distinguishing error is at most δ+negl(λ).Source: §1.2 · pp. 7–8
Assuming post-quantum LWE hardness, the protocol provides ϵ-simulation remote state preparation for any efficiently preparable real state selected through the sender’s private classical description.Its cryptographic applications can retain negligible security loss; the authors give unclonable quantum ciphertext preparation as an example.Source: §1.2 · p. 8
The protocol also yields classical revocation for secure key-leasing schemes with efficient quantum verification, preserving security after revocation up to negligible loss.The parties evaluate verification on the lessee’s quantum input and the lessor’s private key, then discard the submitted key registers.Source: §1.2 · p. 9
Additional applications include unclonable encryption over a classical channel, public-key quantum money with a classical bank, improved extraction for quantum-knowledge arguments, no-intrusion proofs for key leasing, and interactive classical communication for quantum obfuscation.Source: §1.2 · p. 9

2 Technical Overview

The technical overview develops input-preserving classical–quantum computation and quantum-state commitments, including verification and remote preparation, and explains how the underlying 2PC supports private computations, authenticated outputs, and persistent memory. It also outlines applications of the broader result, including two open problems addressed by the paper.

2 Technical Overview

The client hides its decoding key in a witness-preserving 2PC for secret classical functions, avoiding the key-revealing approach of.The 2PC measures f on the server’s input, returns the residual state, and hides f except for information necessarily revealed by that state; constant-degree polynomials suffice because linear decoding composed with a constant-locality history-state Hamiltonian has constant degree.Source: §2 · p. 11
A new commitment to quantum states provides continual ideal binding, keeping the adversarial server bound to its residual state across decoding queries.After repeated tests, a state passing them must be negligibly far from a history state; the client can help the server recover it for coherent output. The construction uses remote state preparation for ’s coset-state authentication code, whose linear decoding fits the input-preserving 2PC.Source: §2 · pp. 11–12
For public computations, the server commits to a history state, the client repeatedly runs gentle validity tests, and the clock measurement determines whether to restart or produce output.For t < T, the client helps recover |ψt⟩ so the server can uncompute the preceding gates; at t = T, the server opens output register C and the client helps recover B, but not D.Source: §2 · p. 12
QFHE hides the circuit by having the server homomorphically evaluate an encrypted universal circuit; discarding D hides the evaluation ancillas needed for circuit privacy.For persistent memory, the client embeds an authentication key in U to authenticate its output and in V to verify and decode that state before use; quantum authentication also hides the intermediate state.Source: §2 · p. 13

2.1 Input-Preserving 2PC for Classical Constant-Degree Polynomials

For constant-degree polynomials, the 2PC reduces to linear functions by reversibly extending the server’s input with degree-c monomials, and it allows aborting on disallowed outputs.Output checking is useful for commitment openings: decoding applies a linear function and checks whether a post-fix of the output is 0.Source: §2.1 · pp. 13–14
The linear 2PC uses NTCFs with the adaptive hardcore bit property to commit to the server’s input, mask the client’s function, evaluate it, and recover the residual state.The input commitment preserves a superposition over preimages, while witness-preserving NP arguments establish knowledge and correct evaluation; the classical client is assumed honest-but-curious, whereas security holds against malicious quantum parties.Source: §2.1 · pp. 14–15
Evaluation measures only Lv, preserving the server’s input state conditioned on that output, but the protocol’s security needs additional encoding when L has multiple columns.A multi-column adversary can isolate individual columns using a phase variation of the honest computation.Source: §2.1 · pp. 16–17
A redundant randomized encoding masks individual matrix indices while allowing safe whole-row phases, supporting input-preserving 2PC for classical constant-degree polynomials.The construction’s ε-simulation relies on indistinguishable temporary extraction; the described extractor causes O(ε) statistical disturbance, and negligible simulation requires witness-preserving extraction with strict polynomial-time guarantees.Source: §2.1 · pp. 17–18

2.2 Classical Commitments to Quantum States with Continual Binding

The commitment scheme lets a quantum sender commit to a state, provide Hadamard- or computational-basis openings, and recover the residual state while preserving continual binding.It remotely prepares authenticated states under a key held by the classical receiver, reducing attacks on the commitment to attacks on the underlying authentication scheme, whose continual security was established in.Source: §2.2 · pp. 18–20

2.2.1 Remote State Preparation of Coset States.

The coset-state RSP construction aims to preserve all falsifiable security properties up to negligible loss, using simulation rather than preserving properties one at a time.Its simulator receives the intended masked coset state and membership-oracle access for S + x and S⊥ + z; these interfaces are compatible with the decoding and verification queries used for continual binding.Source: §2.2.1 · pp. 20–21

Construction.

The construction smoothly inserts a prescribed coset state into the receiver’s view without the protocol-dependent error caused by destructive observable tests.The simulator replaces the three 2PC functionalities with simulated ones and uses the prescribed state in place of the original measurements, with checks replaced by membership-oracle queries.Source: Construction · p. 23

2.3 Applications

The applications include negligible-loss classical verification of quantum sampling, remote preparation of arbitrary efficiently preparable states, and classical revocation of quantum certificates.The paper identifies the first two as well-known open problems and the third as a novel application.Source: §2.3 · p. 24
The 2PC yields samples computationally indistinguishable from the target distribution with negligible error, without choosing an approximation parameter for the circuit.The output is computationally close to the circuit’s distribution for every ϵ = 1/poly(λ).Source: §2.3 · p. 24
The 2PC lets a classical party replace a quantum-game participant sending a message, with negligible increase in an adversary’s winning probability.It supports any efficient state-preparation procedure, and the reduction’s 1/ϵ time blow-up is tunable independently of the resulting game [s10.p9#56b76d].Source: §2.3 · p. 25
Classical parties can use the 2PC to check and discard quantum revocation certificates, making the discarded state computationally disappear from the server’s view.For secure key leasing, this yields negligible post-revocation decryption advantage.Source: §2.3 · p. 25
The remote-state-preparation application enables classical clients to send quantum ciphertexts with negligible loss in cloning security, answering an open problem.Source: §2.3 · p. 25
Using the 2PC to send Zhandry-scheme banknotes yields public-key quantum money from iO and polynomially hard LWE.The cited prior construction required iO and subexponentially hard LWE.Source: §2.3 · pp. 25–26
The 2PC compiles publicly verifiable oracle-model key-leasing schemes into proofs of no-intrusion for decryption keys, returning the certificate coherently to the prover.Source: §2.3 · p. 26
Directly implementing a QMA verifier gives a classical argument of knowledge with zero copy error and extraction error set by extractor runtime.Any ϵ = 1/poly(λ) extraction error is achievable with extractor runtime 1/poly(ϵ); a prover with one witness copy passing QMA verification with probability α passes CVQC verification with probability α − negl(λ).Source: §2.3 · p. 26

2.4 AI Disclosure.

The authors report using ChatGPT 6.0 for proofreading, drafting starting text for the applications section, and identifying a bug and fix in the input-preserving 2PC for linear classical functions.The authors state that they checked the revised proof and take responsibility for the technical content.Source: §2.4 · p. 27

3 Preliminaries

This section establishes the paper’s quantum-computation conventions and reviews the cryptographic definitions and tools used in its protocols. It covers history-state tests, quantum fully homomorphic encryption, functional authentication, noisy trapdoor claw-free functions, witness-preserving arguments, indistinguishable extraction, and semi-quantum secure two-party computation.

3.1 Notation and Conventions

The notation defines quantum circuits with coherent, measured, and discarded outputs, QPT algorithms and adversaries, and computational indistinguishability with negligible or bounded distinguishing advantage.A QPT adversary may have non-uniform quantum advice, and distinguishing may involve auxiliary input entangled with that advice.Source: §3.1 · pp. 27–28

History States.

For circuits over GXZ, each history-state projector is diagonal in a constant-size product X/Z basis, and the test accepts every valid history state while rejecting states with inverse-polynomial probability proportional to their weight outside the history-state subspace.The soundness bound is M Tr(HHist(C)ρ) ≥ c M(T + 1)^2 Tr((I − G)ρ), where G projects onto the history-state subspace.Source: History States · pp. 30–31
Repeating the X/Z projection test r = M·(T+1)^2·λ times yields a residual state negligibly close to a valid history state whenever acceptance probability is at least 1/poly(λ).The test aborts on the second outcome of each sampled projection.Source: History States · p. 31

3.3 Quantum Fully Homomorphic Encryption

A QFHE scheme provides key generation, encryption, homomorphic evaluation, and decryption, with correctness, semantic security, and compact decryption; a circuit-private scheme with the stated encryption property exists under post-quantum LWE hardness.Compactness makes decryption runtime independent of the evaluated circuit’s size.Source: §3.3 · pp. 32–34

3.4.1 Definition

Functional authentication encodes states so unitaries can be homomorphically implemented, with classical evaluation-key generation, decoding, and verification algorithms.Correctness requires homomorphic measurement to match direct measurement followed by authentication of the residual state.Source: §3.4.1 · pp. 34–35
Functional authentication security requires that an adversary with an authenticated state and decoding-function oracles behave as if the state were absent and the oracles were direct measurements.The definition formalizes this ideal behavior for bounded-query algorithms.Source: §3.4.1 · pp. 35–36

3.4.2 Coset-state construction

For λ ≥ Ω(n), the coset authentication scheme of Bartusek, Brakerski, and Vaikuntanathan is a functional authentication scheme for UZX-Lin under Definition 4.Its decoding is also almost linear, as captured by the affine decoding lemma.Source: §3.4.2 · pp. 37–38

3.5 Noisy Trapdoor Claw-Free Functions

An NTCF family uses setup, evaluation, inversion, checking, and syndrome algorithms, with its randomized function defined over an efficiently verifiable and samplable domain.The supplied definition also imposes properties including a perfect matching between the two function branches and efficient range superposition.Source: §3.5 · pp. 39–40
An NTCF family exists assuming post-quantum LWE hardness, and the construction also satisfies the 2-query adaptive hardcore-bit property.This follows because its syndrome function is linear in d, which yields the two-query property for NTCFs satisfying the adaptive hardcore-bit property.Source: §3.5 · pp. 40, 42
The paper establishes collapsing with one leaked inner product for NTCFs and describes random-inner-product hiding and phase injection properties under stated syndrome and NTCF conditions.The hiding property requires Synd to be linear in d; the phase-injection variation applies to NTCFs satisfying the second property.Source: §3.5 · p. 40
The challenge measures R with a projector defined by Check, applies Z to its first qubit when p = 1, and returns R to the adversary.The measurement tests the condition Check(pp, b, rb, y) = 1.Source: §3.5 · p. 42
The leakage step sends (d, d · ∆), then uses a syndrome condition to send either (e · ∆) ⊕ p or a random bit before the adversary guesses p.Here ∆ is computed from trapdoor inversions of y, and the adversary wins if its output equals p.Source: §3.5 · p. 42

3.6 Witness-Preserving Arguments for NP

A witness-preserving argument for NP exists assuming dual-mode claw-free trapdoor functions with state recovery, constructible from post-quantum LWE hardness.[KKR26] introduced witness-preserving arguments, in which a quantum prover can convince a classical verifier without disturbing its witness superposition.Source: §3.6 · pp. 42–43

3.7 Quantum Extraction for Arguments of Classical Knowledge

Indistinguishable extraction temporarily exposes a coherent witness through a unitary extractor that can be inverted to return it, while simulating an indistinguishable prover view.The definition requires that the probability of an accepting transcript without successful witness extraction is negligible.Source: §3.7 · pp. 43–44
For any computationally or statistically collapsing commitment, committing to a witness and proving its opening via 3-coloring is statistically ε-indistinguishably-extractable.Combined with ’s construction, this yields an approximate indistinguishable-extraction witness-preserving argument for NP under dual-mode claw-free trapdoor functions with state recovery, constructible from post-quantum LWE hardness.Source: §3.7 · pp. 45–46

3.8 Semi-Quantum Secure 2-Party Computation

Semi-quantum 2PC defines a quantum input and classical input computation with a coherent quantum output and classical measurement result, requiring negligible-trace-distance correctness and security against malicious parties.The classical party’s adversaries are treated as honest-but-curious by default.Source: §3.8 · pp. 46–48
Honest-but-curious security for the classical party can be upgraded to malicious security with GMW compilation using quantum-secure classical subprotocols and zero-knowledge proofs for NP.The compilation commits to the input and randomness, then proves each message was honestly computed.Source: §3.8 · p. 48

4 Input-Preserving 2-PC for Classical Constant-Degree Functions with Post-Processed Abort

This section constructs input-preserving two-party computation for classical constant-degree functions with post-processed abort, building first on linear functionalities. It establishes correctness and security properties, including computational indistinguishability from ideal simulation against a malicious quantum server, statistical privacy against honest-but-curious classical parties, and the protocol’s LWE-based assumptions.

4 Input-Preserving 2-PC for Classical Constant-Degree Functions with Post-Processed Abort

Under post-quantum LWE hardness, an ε-simulateable input-preserving 2PC for classical linear functions with post-processed abort exists.With an indistinguishable extractable witness-preserving argument for NP, the protocol instead has negligible-loss security.Source: §4 · p. 49

4.1.1 Setup

The protocol setup uses noisy trapdoor claw-free functions with the adaptive two-query hardcore bit property and witness-preserving indistinguishably-extractable arguments for NP, both instantiable from LWE.Source: §4.1.1 · p. 49

4.1.2 Protocol

Protocol 1 encodes the quantum party’s input, uses entry-wise NTCF commitments and witness-preserving arguments, then measures a hidden linear function before conditional state recovery.The measurement yields a one-time-padded linear-function outcome; recovery runs only when C(u)=0.Source: §4.1.2 · pp. 50–53

4.2 Correctness of Protocol 1

For honest parties, Protocol 1’s joint output is negligibly close in trace distance to the specified ideal functionality, including its conditional abort behavior.When C(Lv)=1, the quantum party outputs ⊥ and the classical party outputs Lv; otherwise the quantum party’s residual state is recovered.Source: §4.2 · pp. 54–56

4.3 Security Against Malicious PQ

Theorem 9 establishes that Protocol 1 ε-securely realizes the linear functionality with post-processed abort against malicious quantum parties, under the stated NTCF and NP-argument assumptions.The assumptions are the two-query adaptive hardcore bit property for the NTCF family and witness-preserving indistinguishably-extractable arguments for NP.Source: §4.3 · p. 56
The real execution with a malicious quantum server is computationally indistinguishable from the ideal execution with the simulator.This establishes security against a malicious server.Source: §4.3 · pp. 58, 62
Less than 1/n trace distance is incurred by the two witness-preserving replacements, while the explicit abort measurement is indistinguishable by NTCF collapsing with 1-bit inner-product leakage.The collapse-based argument applies in the abort case; the hybrids are identical in the non-abort case.Source: §4.3 · pp. 58, 60

4.3.1 Replacement of the Encoded L

After measuring ℓ·v, an encoding of a can be indistinguishably replaced by an encoding of 0, enabling replacement of each encoded row of L′ with 0.The resulting distinguishing advantage is negligible.Source: §4.3.1 · pp. 62, 64, §4.3 · p. 62

4.3.2 Distinguishing Gap Transport Lemma

For arbitrary b, shifting both the encoding and phase by b changes the signed distinguishing gap negligibly.The general transport lemma follows by decomposing b into rows of G and composing the limited transport steps.Source: §4.3.2 · pp. 65, 67

4.4 Security Against Honest-But-Curious PC

Protocol 1 is statistically secure against any honest-but-curious classical party PC.The proof bounds the distance between views on inputs with the same ideal output distribution by 2√ε = negl(λ), using a simulator that selects an input matching the prescribed output.Source: §4.4 · pp. 68–69

4.5 Input-Preserving Classical 2PC for Constant Degree Functions

The linear 2-PC extends to all constant-degree functions under LWE-instantiable assumptions on the underlying primitives.The protocol lifts the quantum input to encode all monomials of degree at most d and linearizes the classical polynomial; the quantum party also proves its preimages have the required monomial form.Source: §4.5 · p. 70

5 Remote State Preparation of Coset States

This section constructs remote state preparation for coset states, where a classical sender chooses the subspace and the offsets are randomized, and defines security through simulation. It proves that the ideal functionality is indistinguishable from the real protocol for any QPT receiver, with distinguishing probability at most 1/n + negl(λ), using state-preserving 2PC and a sequence of identical-distribution or statistically close hybrids.

5.1 Definition

The classical sender chooses S and receives (S, x, z), while the quantum receiver obtains XxZz|S⟩; security compares their joint view with receiving the state and membership-oracle access.The stated oracle access is to S + x and S⊥ + z.Source: §5 · p. 70, §5.1 · p. 71

5.2 Construction

Three state-preserving 2PC rounds use random R ⊂ S and T ⊃ S to randomize z and x, while membership checks constrain the receiver’s influence over both offsets.The construction checks R⊥ before deriving z and T + xR before deriving x; R⊥ and T are described as sufficiently randomized to yield nearly uniform offsets.Source: §5.2 · p. 72
Protocol 2 is an ϵ-secure coset-state remote preparation protocol when its linear-function 2PC is ϵ-secure, for subspaces with dim(S) ∈ [2λ, d − 2λ + O(1)].The theorem also states the corresponding result for secure 2PC and secure remote state preparation.Source: §5.2 · p. 74
Correctness permits dim(S) up to d − 2λ + O(1), since the two abort cases have probability at most 2^-λ and 2^-λ·2^O(1), respectively.The stated bounds concern inputs in S⊥ relative to R⊥ and in S + xR relative to T + xR.Source: §5.2 · p. 74

5.3 Security

Measuring and discarding the coset representative for S is equivalent to applying Zz for uniform z ← S⊥, an equivalence used in the security proof.The passage explains that both operations preserve a basis coherence when x + y ∈ S and otherwise erase it.Source: §5.3 · pp. 74–75

5.3.1 The Simulator

The protocol applies CX from V1 to C, queries O_{S⊥+z} on V2 and applies CZ if it does not reject, then queries O_{S+x} on V3 and applies CX if it does not reject.Source: §5.3.1 · p. 75

5.3.2 Indistinguishability of the Simulator

The indistinguishability proof organizes hybrids into setup, forcing z, forcing x, and replacing ideal 2PC functionalities with prescribed CX and CZ operations.The supplied portion describes early hybrids that replace each 2PC with its simulator and begin forcing the Z key to a uniformly sampled canonical offset.Source: §5.3.2 · pp. 76–77
Any QPT receiver distinguishes Hyb0 from Ideal(Sim, 1λ) with probability at most 1/n + negl(λ).The bound follows from the three sequential 2PC invocations and the triangle inequality.Source: §5.3.2 · p. 78
Hyb1–Hyb3 are identically distributed, while Hyb3–Hyb5 are statistically close.These transitions are established in Claims 5–8.Source: §5.3.2 · pp. 78–79
Hyb5–Hyb6 are identically distributed, Hyb6–Hyb8 are statistically close, and Hyb8–Hyb9 are identically distributed.These transitions are established in Claims 9–12.Source: §5.3.2 · pp. 79–80
Hyb9–Hyb12 and Hyb12–Ideal(Sim, 1λ) are identically distributed.Claims 13–16 establish these final transitions, completing the hybrid argument.Source: §5.3.2 · pp. 81–82

6 Classical Commitments to Quantum States with Ideal Binding

This section develops classical commitments to quantum states with continual ideal binding for ZX-and-Linear measurements, including recovery of committed states. It also relates continual binding to functional authentication security and establishes security through real/ideal indistinguishability, including after measurement queries and recovery.

6 Classical Commitments to Quantum States with Ideal Binding

A single protocol achieves ε-indistinguishability from the ideal continual-binding world for every ε = 1/poly(λ), with a description independent of ε.Theorem 13 gives state recovery and ε-secure (or secure) continual ideal binding for ZX-and-linear measurements, assuming state-preserving 2PC for classical linear functions with post-processed abort; Corollary 6 derives such a scheme for {M[HθL]}θ∈{0,1}n,L from post-quantum LWE hardness.Source: §6 · pp. 83–84
Classical interaction lets a dishonest committer authenticate a state of its choice without learning the authentication key, enabling openings to ZX-and-linear measurements.The classical receiver can later help the committer recover the committed state, and recovery composes with continual binding so the sender can recover a partially measured state.Source: §6 · p. 84

6.1 Definition

The commitment syntax supports homomorphic measurement: the sender applies an evaluated unitary to its opening register, while the receiver uses classical evaluation keys to decode and verify openings.Correctness requires committing then homomorphically measuring to be equivalent to measuring first and then committing.Source: §6.1 · pp. 84–85

6.1.1 One-Shot Ideal Binding

One-shot ideal binding requires each real opening to match a measurement of the state declared at commitment in the ideal experiment.The definition compares real and ideal executions for computational indistinguishability.Source: §6.1.1 · pp. 87–88

6.1.2 Continual Ideal Binding

Continual ideal binding allows decoding queries to measure and change the committed state, but requires each later opening to match a measurement of its latest post-measurement state.The definition permits polynomially many queries; with recovery, the ideal simulator receives the recovered state and must produce an indistinguishable view.Source: §6.1.2 · pp. 88–89, §6.1.3 · pp. 89–90

6.1.3 Continual Binding with Recovery

Continual binding with recovery requires a simulator making the real and ideal experiments computationally indistinguishable across sequences of measurements and classical functions.The ε-secure definition uses uniform poly(λ, 1/ε)-size simulator circuits; partial recovery lets the simulator receive only register V1.Source: §6.1.3 · p. 90

6.1.4 Continual Binding for Authentication

Functional authentication security implies continual binding for quantum authentication.Source: §6.1.4 · p. 90

6.2 Construction

Constructions 2 and 3 achieve ε-secure continual ideal binding for ZX-and-Linear measurements, and the decoder is linear with post-processed abort.The construction uses the coset-based authentication scheme from.Source: §6.2 · pp. 91, 93

6.3 Construction with Recovery

Construction 4 and Construction 5 achieve ε-continual ideal binding with recovery for ZX-and-Linear measurements, with a linear decoder and post-processed abort.The construction compiles a commitment by teleporting the committed state into an uncommitted register; partial recovery is supported by revealing corrections only for the desired subregister.Source: §6.3 · pp. 94–96

Part III State-Preserving 2PC for General Quantum Functions

The section combines developed tools into a general 2PC for quantum functionalities, using verifiable commitment to a history state to verify public computations and adding privacy through quantum fully homomorphic encryption.

Part III State-Preserving 2PC for General Quantum Functions

The section combines developed tools into a general 2PC for quantum functionalities by abstracting verifiable commitment to a history state.Source: Part III State-Preserving 2PC for… · p. 96
Verifiable commitment to a history state makes it possible to verify any public computation.Source: Part III State-Preserving 2PC for… · p. 97
The section combines public-computation verification with quantum fully homomorphic encryption for privacy.Source: Part III State-Preserving 2PC for… · p. 97

7 Certified Commitment to History States

This section defines and implements a state-preserving certified commitment to history states that can later be opened or recovered, and analyzes the security of its protocols. It establishes security for CertCom, Open, and their composition using hybrid arguments and stateful simulation with one evolving ideal history register.

7 Certified Commitment to History States

The ideal functionality certifies a committed register by projecting it onto the history-state subspace, permits repeated admissible openings, and supports a later recovery request.The protocol realizes these steps with CertCom, Open(U, f), and Recover; Recover is invoked at most once.Source: §7 · pp. 97–98

7.1 Protocol CertCom

CertCom commits to the computed history state and repeats a history-state test r = M ·(T +1)2 ·λ times, rejecting when a test fails validation.The residual state is released only when the verification conditions pass.Source: §7.1 · p. 99

7.2 Protocol Open(U, f)

Open(U, f) verifies the requested transformed commitment, returns y = f(DeccomU(op)) to the classical party, and leaves the resulting residual state with the quantum party.The residual quantum state is released by the post-processed abort predicate only when verification succeeds.Source: §7.2 · p. 100

7.3 Analysis

For polynomial-length adaptive admissible openings followed by at most one recovery, sequential simulators make the real execution computationally indistinguishable from the ideal one.The analysis focuses on full recovery and also applies to partial recovery when the underlying commitment scheme’s partial-recovery counterpart is used.Source: §7.3 · pp. 100–101

7.3.1 Security of CertCom

The CertCom simulator emulates the tests, transfers the current ideal register to the history-state functionality for projection, and argues that inserting this projection changes the experiment only negligibly.The analysis treats aborting and non-aborting branches separately.Source: §7.3.1 · p. 103
The CertCom security proof concludes that its trace-distance error is negligible and combines the hybrids to obtain the claimed result for every polynomial n.The proof argues that inserting a global projection changes the experiment by only negligible statistical error.Source: §7.3.1 · p. 105

7.3.2 Security of Open

Theorem 18 establishes Open security against a malicious quantum party by replacing Step 3’s state-preserving classical 2PC with its ideal functionality.The security argument includes the adversary’s auxiliary and residual state E; operations before and after Step 3 are identical in the two experiments.Source: §7.3.2 · pp. 105–106

7.3.3 Security of the Composed Protocol

The composed protocol simulates every opening on the same evolving ideal register V, then uses its final residual state to emulate recovery.Replacing the commitment, opening, and recovery queries by this stateful simulation changes execution only negligibly; inserting the projection also incurs only negligible statistical error.Source: §7.3.3 · pp. 106–107

8 State-Preserving 2PC for General Quantum Functions

This section presents a state-preserving two-party computation protocol for general real quantum circuits, in which a classical party supplies an input and a quantum party supplies a state, yielding coherent and classical outputs with privacy and correctness guarantees. It analyzes the protocol’s security against malicious quantum parties and establishes statistical security against honest-but-curious classical parties.

8 State-Preserving 2PC for General Quantum Functions

Theorem 19 gives semi-quantum 2PC for general real quantum circuits from continual-binding quantum-state commitments, state-preserving 2PC for constant-degree classical functions, and circuit-private quantum FHE; these primitives have ε-security under post-quantum LWE.The protocol guarantees privacy for both parties and correct outputs, up to computational indistinguishability, or ⊥ regardless of the other party’s behavior.Source: §8 · p. 107

8.1 Construction

Protocol 5 evaluates the circuit on encrypted inputs with quantum FHE, certifies a history-state commitment, and uses clock measurements and recovery before opening outputs.At a terminal clock value, it opens the encrypted pads and measured output, partially recovers the evaluated ciphertext, and removes the quantum one-time pad for the coherent output.Source: §8.1 · pp. 108–111

8.2 Correctness

Theorem 20 establishes correctness: the protocol’s joint output is negligibly close to the ideal functionality’s output, with the coherent register reduced over measured and discarded registers.Clock measurements are repeated up to K = λ(T + 1) times to reach the terminal step; otherwise the parties output ⊥.Source: §8.1 · p. 110, §8.2 · p. 111

8.3 Security Against Malicious Quantum Parties

Theorem 21 gives a uniform sequence of QPT oracle-circuit simulators for every QPT adversary controlling the malicious quantum party.The proof’s simulator uses the ideal functionality’s returned coherent output to form the terminal ciphertext and simulates the protocol’s openings and recovery.Source: §8.3 · pp. 112–113
Circuit privacy makes the terminal-ciphertext substitutions computationally indistinguishable, including with external entanglement and the other registers.The proof applies circuit privacy to the simulated final ciphertext and to homomorphic evaluation of the identity circuit.Source: §8.3 · pp. 114–115
Semantic security permits replacing encryptions of the classical input and original pads with encryptions of zero while retaining the original values for the plaintext computation.The reduction uses the retained input and pads in the plaintext computation and the explicitly known inner Pauli keys for the terminal pad opening.Source: §8.3 · p. 115
Measuring the plaintext output before preparing its fresh terminal ciphertext gives the same outcome relation and post-measurement ciphertext as measuring afterward, up to negligible error.The X-pad changes the measured value by the corresponding pad bits, while the Z-pad contributes only an outcome-dependent global phase.Source: §8.3 · p. 116
The quantum one-time pad makes the masked output and discarded registers indistinguishable whether they contain the original states or fresh zero states.The unused sub-pads are independent of the rest of either hybrid experiment.Source: §8.3 · p. 117
The H6-to-H7 transition realizes the ideal G-functionality: both experiments yield the same private output and residual state, and later messages and abort decisions do not require the output or discarded register.The simulator sends the recovered input to the functionality, which measures the output, discards D, and returns B; it releases the stored outcome only after successful completion.Source: §8.3 · p. 117

8.4 Security Against Semi-Honest Classical Parties

Protocol 5 is statistically secure against honest-but-curious classical parties with the commitment and recovery protocols of Constructions 2, 4 and 5.The simulator can generate arbitrary openings under the classical party’s authentication key and replace the authenticated output blocks with an authentication of the simulated outcome.Source: §8.4 · p. 118
State-preserving recovery makes the classical view independent of the residual quantum state and its reference, allowing the remaining view to be generated from the authenticated dummy state.The argument applies after full recovery and, conditioned on the preceding view and measured outcome, after the prescribed projective measurement.Source: §8.4 · p. 118

9 2PC with Persistent Memory

The section extends secure 2PC for general real quantum circuits to polynomial-size reactive quantum functionalities. Persistent memory is authenticated so the quantum party can hold it between evaluations, while security is established against malicious quantum parties and semi-honest classical parties.

9 2PC with Persistent Memory

The functionality initializes memory and, across polynomially many evaluations, runs the client’s circuit on memory and the quantum party’s input, then retains its share of the coherent output.The adversary may abort at any time.Source: §9 · p. 119
A secure 2PC for general real quantum circuits yields a secure 2PC for polynomial-size reactive quantum functionalities.The theorem preserves the stated security level of the underlying protocol.Source: §9 · p. 119

9.1 Construction and Analysis

Memory persistence is enforced by authenticating the memory register under a key known only to the classical party, allowing the quantum party to hold it until the next evaluation.The paper states that such authentication schemes exist unconditionally.Source: §9.1 · p. 119
Correctness follows from the underlying 2PC and authentication scheme, and adding authentication encoding and decoding keeps the circuit polynomial-size.Source: §9.1 · p. 120
For polynomially many evaluations, security against malicious quantum parties follows by allocating error ϵ/T per evaluation and using memory authentication to match the ideal functionality, for total error ϵ.Here T is an upper bound on the number of evaluations.Source: §9.1 · p. 120
Security against semi-honest classical parties follows from the underlying 2PC because the classical party never sees the authenticated memory register.The underlying 2PC simulations already match the ideal functionality’s per-evaluation input and output behavior.Source: §9.1 · p. 120

10 Highlighted Applications

The section presents applications of the protocol to quantum sampling, remote state preparation, and classical handling of quantum certificates. Under the post-quantum hardness of LWE, it gives negligible-error sampling verification, secure preparation for efficiently preparable states, and classical revocation procedures.

10 Highlighted Applications

The applications include receiving, verifying, and holding a quantum certificate for secure key leasing, with revocation possible through classical interaction.The returned certificate ensures the quantum sender can no longer decrypt future ciphertexts.Source: §10 · p. 121

10.1 Classical Verification of Quantum Sampling

Every quantumly sampleable distribution admits complete, computationally sound classical verification under post-quantum LWE; for SampBQP, verification adds negligible error beyond the sampler’s approximation error.The verifier can also hide which distribution it requests, up to the size of the implemented circuit.Source: §10.1 · pp. 121–122

10.2 Remote State Preparation

Remote state preparation supports sender-chosen, efficiently preparable states with ε-security and negligible-loss falsifiable security under post-quantum LWE.The same protocol must satisfy every ε = 1/poly(λ); ε is a simulator parameter, not a protocol parameter.Source: §10.2 · pp. 123–124

Correctness.

In the secure key leasing application, the classical verifier receives the prescribed verification outcome while the residual quantum state is discarded.The submitted quantum key is consumed, as in the original verification experiment.Source: §10.3 · pp. 124, 126

10.3 Classical Revocation of Quantum Certificates

An efficient quantum verification procedure for a quantum certificate can be compiled into classical interaction, enabling classical revocation when successful verification certifies revocation.For secure key leasing, the compiled scheme preserves IND-KLA security under post-quantum LWE; the verification protocol itself is fixed while only its simulator depends on ε.Source: §10.3 · p. 124, Security · p. 127

Security.

Security is established by replacing each of the adversary’s polynomially many verification interactions with its ideal functionality, reducing any non-negligible attack to one against the original scheme.The proof chooses simulator error as a function of the adversary’s advantage and number of verification queries.Source: Security · pp. 126–127

11 Other Applications

The section applies state-preserving two-party computation to cryptographic tasks that use quantum communication or verification. These applications include classical encryption, banking, verification, revocation, and interactive obfuscation, with post-quantum LWE assumptions as specified for each result.

11 Other Applications

Across these examples, the reductions use ε-simulation for each ε = 1/poly(λ) to obtain negligible security loss for applications with falsifiable security properties.The argument replaces quantum-communication messages with simulations of the two-party computation implementing classical communication.Source: §11 · p. 127

11.1 Unclonable Encryption over a Classical Channel

A classical sender can remotely prepare an unclonable quantum ciphertext, yielding an unclonable encryption scheme with a classical encryptor under post-quantum LWE.The security argument simulates the preparation before the adversary splits the ciphertext.Source: §11.1 · pp. 127–128

11.2 Public-Key Quantum Money with a Classical Bank from Polynomial Hardness

A quantum bank can be made classical, with classical communication during minting, assuming post-quantum indistinguishability obfuscation and polynomial post-quantum hardness of LWE.The verification algorithm remains unchanged, and the approach applies to Zhandry’s subspace-based quantum money construction without the subexponential-LWE assumption used in.Source: §11.2 · p. 128

11.3 Improved Extraction for Classical Verification of QMA

Classical verification of QMA achieves negligible knowledge error, zero copy error, and additive extraction error Δ = ε for every ε = 1/poly(λ), with one witness copy.The same protocol supports a uniform sequence of extractors running in time poly(1/ε), and witnesses accepted with probability α remain convincing with probability α − negl(λ).Source: §11.3 · p. 129

11.4 Proofs of No-Intrusion for Decryption Keys

Key-leasing schemes secure against verification-oracle attacks that return the tested state admit proofs of no-intrusion with a classical verifier; leasing can also use classical communication.The construction retains the post-measurement state and simulates verification through state-preserving two-party computation.Source: §11.4 · p. 130

11.5 Quantum Obfuscation with Interactive Classical Communication

Any quantum-circuit indistinguishability obfuscator can be compiled into one whose obfuscation process uses interactive classical communication.The classically sent obfuscated program satisfies standard indistinguishability obfuscation; removing interaction to obtain truly classical obfuscation remains open.Source: §11.5 · p. 131

A.1 NTCF Collapsing with 1 Bit Leakage

This part establishes NTCF security under one-bit leakage, including collapsing security, the implication from linear Synd to the 2-query adaptive hardcore bit property, and phase-injection unpredictability.

A.1 NTCF Collapsing with 1 Bit Leakage

A measure–reflect–measure extraction uses a valid preimage measurement and a reflection of the adversary’s final computation to find an opposite-branch preimage, making any distinguishing gap negligible by claw-freeness.The reduction guesses the leaked bit; its extraction uses one copy of the adversary’s auxiliary input, with negligible correctness error absorbed in the bound.Source: §A.1 · pp. 136–138

A.2 2-Query Adaptive Hardcore Bit Property

Every NTCF family with linear Synd satisfies the 2-query adaptive hardcore bit property: every QPT adversary wins with probability at most 1/2 + negl(λ).The proof converts any non-negligible advantage in the two-query game into an adaptive-hardcore-bit prediction advantage.Source: §A.2 · pp. 138, 141

A.3 Phase Injection with 1 Bit Leakage

In the phase-injection game with one leaked inner-product bit, every QPT adversary wins with probability at most 1/2 + negl(λ).The proof uses collapsing with one bit of leakage and the adaptive hardcore bit properties to replace that leakage with randomness; computational-basis measurement destroys the phase distinction.Source: §A.3 · p. 142
A distinguisher between Hyb∗0 and Hyb∗1 yields an adaptive-hardcore-bit adversary by replacing the inner product with a random bit.The reduction measures R to obtain x and receives d from A, then outputs the resulting challenge and a bit derived from the random bit and the hybrid output.Source: §A.3 · p. 143
The reduction’s advantage comes from distinguishing a valid x with the correct inner product from a valid x with the incorrect inner product, violating the adaptive hardcore bit property.When d is not good, the distributions are identical; conditioned on invalid x, the adversary has no advantage.Source: §A.3 · p. 143
Combining Equations (15) and (16), A guesses 1 with almost the same probability in the p = 0 and p = 1 cases.Source: §A.3 · p. 143