Robust and leakage-resilient device-independent oblivious transfer in MiniQCryp

Robust and Leakage-Resilient Device-Independent Oblivious Transfer in MiniQCrypt

arXiv:2610.01421v1 [quant-ph] 1 Oct 2026

Zhili Chen1

Rahul Jain1,2,3

YaoNan Zhang1

1 Centre for Quantum Technologies, Singapore

2 Department of Computer Science, National University of Singapore 3 MajuLab, UMI 3654, Singapore

Abstract Assuming post-quantum one-way functions, we construct device-independent (DI) oblivious transfer (OT) and bit commitment: honest parties use only trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and behave non-IID. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. One protocol skeleton serves both, in two regimes. With isolated laboratories and coordinate-local measurements in the honest receiver’s device, it tolerates a constant rate of honest-device faults. With polylogarithmically many qubits of adaptive leakage between the laboratories and arbitrary joint measurements, it tolerates an inverse-polylogarithmic rate. Each elementary DI call uses a fresh, isolated batch of polylogarithmically many device coordinates, and total device use in the compiled OT protocol is polynomial. The commitment has efficient simulators against both parties and yields DI coin tossing with abort. Because OT is complete for secure computation, the construction yields a DI protocol, with abort, for every efficiently computable classical functionality on a fixed number of parties, secure against static corruption of any proper subset of them. The commitment’s extractor changes a public parity relation through classical equivocation and leaves the device execution, hence its leakage, unchanged. A commit-and-prove functionality, disjoint audits, and an affine consistency check link the certified correlations to ideal OT. Sender security rests on a selector-aware parallel-repetition bound for the Magic Square game, which we derive from the two-round threshold theorem of Kundu and Tan. Keywords: Device-independent cryptography; oblivious transfer; multiparty computation; bit commitment; one-way functions; leakage resilience.

Contents 1 Introduction

1

2 Cryptographic preliminaries and security definitions

12

3 Device-independent oblivious transfer from commit-and-prove

20

4 Commit-and-prove from extractable bit commitment via a classical reduction

42

5 Device-independent bit commitment from qOWFs

43

6 The complete construction and secure computation

62

7 Proofs of the repetition theorem and the hidden-string lemma

65

Acknowledgements

71

AI use disclosure

71

A Useful facts

72

B Feasibility of the common parameter schedule

74

C Proof of the BC-to-CP compiler theorem

74

D Proof of efficient sequential composition

80

E Detailed comparison with earlier work

82

References

84

i

1

Introduction

Bit commitment (BC) and oblivious transfer (OT) are foundational primitives of two-party cryptography. A commitment lets Alice fix a bit while hiding it until a later opening. Kilian showed that OT is complete for secure computation [Kil88]: in one-out-of-two OT, Alice holds (S0 , S1 ), Bob holds a choice bit D, and Bob learns SD and nothing about S1−D , while Alice learns nothing about D. Classically, OT is not known to follow from one-way functions, and Impagliazzo and Rudich rule out black-box constructions [IR89]. With quantum communication, it does follow: Grilo, Lin, Song, and Vaikuntanathan [GLSV21] and Bartusek, Coladangelo, Khurana, and Ma [BCKM21] independently construct simulation-secure OT from post-quantum one-way functions (qOWFs). This places OT in MiniQCrypt, the world in which qOWFs exist and quantum computation and communication are available. These protocols trust the quantum hardware. The sender must prepare BB84 states exactly, and the receiver must measure them as prescribed, and their security proofs use this. Device independence. Devices obtained from a potentially colluding vendor need not implement advertised quantum operations, and a proof that assumes exact state preparation or measurement then guarantees nothing. In the device-independent (DI) model, security instead uses only observed correlations, here those of the Magic Square game of Mermin and Peres [Mer90, Per90]. Honest users have trusted classical computation, communication, and private storage; they send prescribed classical questions to untrusted devices and receive classical answers. All quantum operations are performed by the untrusted devices, which may share arbitrary prior entanglement and act non-IID across coordinates. Unlike trusted-quantum protocols, the honest implementation is constrained only through this classical interface. In our protocols the two devices play L Magic Square games in parallel, one per coordinate, in a single use that we call the device window. The question. Device independence has so far been reached for OT only under further restrictions: earlier DI protocols assume bounded quantum storage (Broadbent and Yuen [BY23]; Batra, Chakraborty, Jain, and Kapshikar [BCJK25]), restrict the attack to be sequential (Kaniewski and Wehner [KW16]), or achieve constant cheating bounds (Kundu, Sikora, and Tan [KST22]); to our knowledge, none obtains simulation-secure OT from one-way functions alone. We therefore ask: Do post-quantum one-way functions suffice for oblivious transfer, and hence for secure computation, when the quantum devices are untrusted, faulty, and imperfectly isolated? The answer. We show that they do. We construct DI OT and DI bit commitment (BC) with simulation security against quantum polynomial-time (QPT) adversaries. Both tolerate faulty honest devices and bounded communication between the laboratories, compose sequentially with efficient simulators, and use polylogarithmically many device coordinates per elementary DI call. The fully compiled OT has polynomial total device use. OT completeness extends the guarantees to every efficiently computable classical functionality (Corollary 2); the commitment has simulators against both parties and gives DI coin tossing. Robustness and leakage resilience. Two of these properties decide whether a DI protocol can be used at all, and we require them of every layer of the construction. Robustness. Honest manufacturing, preparation, or measurement faults violate some Magic Square constraints. A protocol that certifies perfect correlations aborts on real devices, and a noiseless-only commitment would defeat the robustness of the OT built on it. Our protocols tolerate

1

a fixed fraction of such faults, in the commitment and in the OT alike. Independent honest faults govern correctness only; security holds against non-IID devices. Leakage resilience. DI security rests on the devices in the two laboratories not communicating, and a colluding vendor’s devices may communicate through hidden side channels. This is the key concern about device independence, and a founder of the field has voiced it. Charles Bennett contrasts DI-QKD with measurement-device-independent QKD, where the untrusted device stays outside the users’ enclosures: in DI-QKD “they must trust Eve not to have deliberately created side channels” from the untrusted devices to herself [XMZ+ 20, Box VI.B.2]. Our protocols address precisely this concern. They are leakage resilient: the vendor may have built the side channel deliberately, and security holds as long as it carries at most ℓ qubits of adaptive, bidirectional communication. All questions and answers of an invocation form one parallel batch, used in a single window, so the devices face this budget once; it is shared by all blocks and never reset. A sequential implementation would give the devices a window per round, and a per-window bound would then say nothing about the total. For two-party primitives, the alternative Bennett points to does not exist, since the adversary is one of the parties, so leakage resilience is the only available answer. The bound is a total per batch; a device that leaks at a constant rate per coordinate is outside the model, and each batch is used once (Section 1.1). The trade-off. The two properties trade off (Table 1): constant fault tolerance needs isolation and a coordinate-local receiver, and leakage or joint measurements cost an inverse-polylogarithmic fault rate. The construction is a chain of three reductions (Figure 1, which also shows the two trustedquantum chains it replaces), where CP is a commit-and-prove functionality: committed strings with partial openings and certified predicates. [GLSV21]

qOWFs

weak selectiveopening BC

weak parallel OT

weak vCDS

simulated selectiveopening BC

OT

[BCKM21]

qOWFs or EFI

statistically binding BC

equivocal BC

extractable BC

extractable and equivocal BC

OT

this work

qOWFs

post-quantum DI DI BC qOWFs CP Protocol 4 Protocol 3 equivocal BC Section 5.2

Section 5

Section 4

DI

DI OT Protocol 1 Section 3

MPC Section 6

Figure 1: Reduction chains. The two earlier chains use trusted quantum communication and place no condition on devices; “weak” permits inefficient simulation, vCDS is verifiable conditional disclosure of secrets, and the chain of [BCKM21] also runs from EFI pairs [BCQ23], which need that quantum communication. Ours removes the trusted quantum operations; in exchange, its two DI arrows require fresh isolated batches with bounded leakage (fresh isolated batches, bounded leakage). Its boxes name the protocol and the section that proves each step; the middle arrow is classical outside its BC calls, OT completeness gives MPC, and the commitment also yields coin tossing (Section 5.5). The two DI arrows use one protocol skeleton with shared parameters; the commitment and OT protocols agree step for step through the selectors and differ afterwards in three specified places (Table 5).

2

1.1

The model, and what each assumption is for

We assume qOWFs and a possibly nonuniform QPT adversary with polynomial-size quantum advice. Corruption is static. In a two-party protocol, at most one party is corrupt; in the multiparty corollary, the corrupted set is an arbitrary proper subset, which acts as one adversary. The vendor of all devices may collude with it. Nothing is assumed about the states or measurements of the devices beyond the items below: no IID structure, no restriction on entanglement or quantum memory beyond the QPT model, and no trusted preparation or measurement. Initial states and reached invocation boundaries, including in simulation hybrids, satisfy Definitions 2 and 4. Trusted classical control. The trusted classical controller of the DI model has no leakage interface. Without it, an honest party has nothing with which to test a device. Bounded communication between the laboratories. A batch is used in parallel, in a single window, and during that window the two laboratories exchange at most ℓ qubits (Definition 8). The parallel use is what makes the bound meaningful: every additional window in which the devices are active is an additional opportunity to leak, so the protocol gives them one. Some bound is unavoidable: Magic Square correlations certify nothing if the devices can exchange their questions, and a receiver’s device that reports its questions reveals the receiver’s choice bit. The standard DI assumption is ℓ = 0; we make the bound explicit and charge it in the entropy analysis. Isolation can be replaced by a computational assumption: the compiler of Kalai, Lombardi, Vaikuntanathan, and Yang turns a nonlocal game into a single-prover protocol whose soundness rests on quantum homomorphic encryption, and its quantum value is now bounded for every twoplayer game [KLVY23, NZ23, KMP+ 25]. That route needs encryption schemes based on structured assumptions such as learning with errors, and a prover that runs the encrypted game. We keep isolation, with an explicit leakage budget, and assume only one-way functions. Fresh, isolated batches. Every invocation of Protocol 4 or Protocol 1 uses its own device batch, once, and a batch exchanges no information with a retired or pending one, also within one laboratory (Definition 13). This excludes the memory attacks of Barrett, Colbeck, and Kent [BCK13], in which a reused device releases earlier private data through later public outputs. The attack is concrete here: the BC calls that follow the OT device window publish tested device answers, and a device that had learned the OT questions could encode them there. The compiled protocol uses polynomially many batches of polylogarithmic size. Each batch shares one leakage budget across its blocks, and classical subprotocols run outside its window. Published device outputs also disclose information. Bob’s published test answers and the resulting accept/abort decision carry at most 3tA + 1 bits from his device to Alice; Alice’s audit openings similarly disclose information to Bob. These prescribed classical disclosures occur outside the device window and are charged separately from its ℓ-qubit communication budget: against the selector entropy on Alice’s side and the pad entropy on Bob’s side (Section 3.6.4 and Table 4). The hidden test set is revealed only after the answer records are fixed, so the device must produce the tested and untested answers before it learns which coordinates will be tested. Bob’s questions are uniform coordinatewise; he chooses the question class and opens its selector afterwards. A coordinate-local honest receiver, in the isolated regime only. With one block, the receiver’s label is a single bit β, and the tested answers that Bob publishes come from the same measurement as the untested ones. A joint measurement could encode the untested questions in 3

the tested answers, and one block has no entropy with which to pay for that. The isolated regime therefore assumes that the measurement producing honest Bob’s answers acts separately on each coordinate (Definition 5), as for a device built from L separate boxes; compare the memoryless devices of Ribeiro, Thinh, Kaniewski, Helsen, and Wehner [RTK+ 18]. This is an assumption about an untrusted device, and the constant fault tolerance rests on it. The general regime removes it: it permits arbitrary joint measurements, and pays with m = ω(log λ) blocks and an inverse-polylogarithmic fault rate. The ideal experiment keeps the honest party’s device share. The honest party’s device is supplied by the adversary and may be entangled with the adversary’s workspace. No simulator can fabricate it. The ideal experiment therefore gives the simulator the same share, through the interface that the honest party has: the prescribed classical questions, once, with no reset and no copy (Definition 3). The simulator receives no honest input. Security then says that whatever the adversary obtains from the real execution, it could obtain from the ideal functionality together with a party that operates the honest device as prescribed and holds no private input. Because every batch is used once and then retired, this notion composes sequentially (Theorem 5). Honest faults. Honest-device faults are independent across coordinates (7). This is used for correctness only.

1.2

Our results

In this model, each DI reduction uses one protocol with parameters determined by the leakage budget and receiver architecture. Table 1 gives their guarantees. Here λ is the security parameter and m counts logical blocks in one device batch; all security and correctness errors are negl(λ). Write BCext for BC with efficient committer-side simulation and ordinary receiver hiding; this is what Protocol 4 realizes and what the compiler needs. A second equivocation layer (Section 5.4, Protocol 6) gives DI BC with QPT simulators for both parties, at the cost of O(log2 λ) calls of Protocol 4 per bit. As an application, it gives DI coin tossing with abort and negligible error. The layer is the equivocality compiler of Bartusek, Coladangelo, Khurana, and Ma with one forced change: their equivocator rewinds across the base commitments, which here would mean rewinding an honest party’s single-use device, so the receiver commits to its challenges first, and the simulator extracts them. The outer protocol uses a commit-and-prove functionality (CP), supporting partial openings and predicate certification on immutable committed strings. Section 1.3 explains this interface and its construction. Theorem 1 (Device-independent OT from qOWFs, informal). Under qOWFs and the model of Section 1.1, let ΠOT be Protocol 1, instantiated by Protocols 4 and 11. For both regimes in Table 1, ΠOT is sequentially composable for either corruption, and satisfies ∀A ∈ QPT

∃Sim ∈ QPT

R ∀ηadm :

R R RealΠOT ,A (ηadm ) ≈c IdealOT,Sim (ηadm ). R Here ηadm ranges over admissible inputs and extensions; εcorr = negl(λ), and total computation, communication, and device use are poly(λ) (Theorem 23).

Here ≈c includes the adversary’s quantum side information. For OT and CP, one QPT simulator per adversary works for every admissible input; BC supplies committer simulation and receiver hiding. OT completeness upgrades this OT construction to general secure computation. 4

Table 1: Common parameter guarantees for both DI reductions: qOWFs ⇒ BCext and CP ⇒ OT. Device counts are per invocation; the full compilation has polynomial overhead. Regime

Device window and honest Robustness and device receiver coordinates Isolated, one Zero cross-laboratory Constant independent honest-fault block (m = 1) communication; coordinate-local tolerance; Θ(log2 λ) coordinates output measurement Inverse-polylogarithmic independent General blocks One window with bounded honest-fault tolerance and adaptive bidirectional leakage; polylogarithmic coordinates for arbitrary joint output polylogarithmic leakage measurement, including at zero leakage At λ = 128: isolated, one block of 50C coordinates; general with ℓ = 10, m = 146 blocks of about 3 × 106 C coordinates. These illustrate growth rates, not a concrete security guarantee (Section 2.4). Corollary 2 (Device-independent multiparty computation). Assume qOWFs, private authenticated classical channels, and that every reached call in every replacement hybrid satisfies the model of Section 1.1 (formally, Definitions 4 and 13), honest–honest calls also satisfying the corresponding correctness conditions. For every fixed p ≥ 2 and classical PPT functionality F on p parties, with public input/output lengths and corrupt-output-first, adversarially suppressible honest delivery, there is a DI protocol ΠF with security with abort against static corruption of any proper subset C ⊊ [p]: ∀A ∈ QPT

∃Sim ∈ QPT

R ∀ηadm :

R R RealΠF ,A (ηadm ) ≈c IdealF ,Sim (ηadm ).

ΠF uses poly(λ) sequential pairwise DI OT calls and poly(λ) total resources, and it inherits either regime of Table 1 with εcorr = negl(λ). The ideal experiment retains the declared device resources of the security definition, and an absorbing abort suppresses future outputs, not outputs already delivered. Theorem 3 (Device-independent commitment and coin tossing, informal). Under qOWFs and the model of Section 1.1, in both regimes of Table 1: Protocol 4 is a DI bit commitment with an efficient simulator against a corrupt committer, which extracts the committed bit at the end of the commitment phase, and with computational hiding against a corrupt receiver (Theorem 14). Protocol 6, which uses O(log2 λ) calls of Protocol 4, has efficient simulators against both parties (Theorem 15), and Protocol 8 realizes coin tossing with abort (Corollary 16). Each uses polylogarithmically many device coordinates. The proof in Section 6.1 uses the classical OT-to-MPC reduction of Ishai, Prabhakaran, and Sahai [IPS08] and Unruh’s quantum lifting theorem [Unr10]. Only trusted classical operations occur outside DI OT. The corrupted set is arbitrary. In a call with one corrupted endpoint, the coalition plays that endpoint, which is the two-party setting of the OT theorem; a call between two corrupted parties is internal to the adversary. Composition and efficiency. Definition 3 and Theorem 5 permit polynomially many adaptive, non-overlapping calls, each replaced with its caller, continuation, corrupt state, honest input– output interface, reference, and abort branches retained; the BC contract also preserves pending 5

records across delayed openings. An OT batch of L coordinates stores O(L) bits and performs one polynomial-time predicate check, and Theorems 12 and 14 give polynomial total computation, communication, and device use. Significance. What can now be done that could not before: every efficient classical functionality can be computed securely by parties who trust only their classical computers, assuming nothing beyond post-quantum one-way functions, with efficient simulators, and with devices that are faulty and imperfectly isolated. The strongest alternative routes each give up one of these. The trusted-quantum constructions give the same assumption and security notion but need exact state preparation and measurement. Bounded-storage DI OT needs no computational assumption but assumes a limit on the adversary’s quantum memory, and its receiver privacy rests on that limit. Compiled nonlocal games remove the isolation between the laboratories, but need structured assumptions such as learning with errors and a prover that runs the encrypted game. The price paid here is the model of Section 1.1: isolated laboratories with an explicit leakage budget, a fresh single-use batch per elementary call, and, in the leakage regime, an inverse-polylogarithmic fault rate. Limitations and open problems. The leakage bound is a total of polylogarithmically many qubits per batch, not a rate. The two regimes do not combine: constant fault tolerance needs isolation and a coordinate-local honest receiver. Every invocation needs a fresh, isolated device batch, and the compiled protocol uses polynomially many of them. Composition is sequential, and corruption is static. Achieving a constant leakage rate, constant fault tolerance under joint measurements, reusable batches, or concurrent composition remains open; as far as we know, each is a limitation of the present analysis and not of the approach.

1.3

Protocol and proof overview

We now explain how the three reductions fit together. The technical sections develop the arrows of the chain above from right to left, so that each section states the interface that the next one must realize: Section 3 gives OT from ideal CP, Section 4 gives CP from a commitment contract, and Section 5 realizes that contract with untrusted devices. Commit-and-prove. The functionality ideal(CP) stores an immutable string M ; its commitment receipt contains only the record identifier, roles, and length. Only the owner may authorize a predicate check P (M, y). A partial opening publishes (S, z) and certifies πS (M ) = z; all later checks concern that same stored M (Definition 6). The OT entropy arguments use this ideal interface. Alice commits to her entire block table MA before the audit masks open. One global PAY predicate (Definition 9) checks that one bit satisfies the syndrome and payload equations in every block. Evaluating both alternatives takes polynomial time. The OT protocol in words. A few coordinates are tested openly. The others are split into m blocks of N coordinates, and in each block a hidden subset is audited. In each block the receiver privately picks a label bit βi , one of two question classes, and the unaudited coordinates of the block on which he asked that class form his selector J i . The answers on the selector are the raw material: error-correcting syndromes reconcile the two parties’ answers, and a seeded hash turns them into one-time pads. Hiding the labels protects the receiver; hiding the sender’s answers for the other class protects the sender. 6

Alice is the sender, with bits (S0 , S1 ); Bob is the receiver, with choice D. Their devices play L parallel Magic Square games: Alice’s device receives a row question and returns a row of three bits, Bob’s receives a column question and returns a column, and a winning pair agrees at the intersection. Below, every commitment is made through the CP functionality, the parties alternate, and the item numbers are the step numbers of Protocol 1. 1. Alice commits to a small hidden test set of tA coordinates. 2. Bob commits to uniformly random question offsets. 3. Alice queries her device on every coordinate and sends her own offsets. 4. Bob queries his device with the sum of the two offsets and commits to all answers. 5. Alice opens the test set and sends a random partition of the other coordinates into m blocks of N coordinates. 6. Bob picks, in each block, a hidden audit set and a private bit βi , and commits to the audit set and to the selector J i : the unaudited coordinates of the block on which his question was βi . 7. Alice erases an independent constant fraction of her records and commits to the resulting table. 8. Bob opens the audit sets and his records on the test set. 9. Alice runs the Magic Square test on the test set and opens her table on the audit sets. 10. Bob checks those entries against his answers and opens the selectors. 11. Alice checks that the selectors are well formed and announces whether she continues. 12. Bob sends a fresh seed r and χ = D ⊕ ⟨r, β⟩. 13. Alice opens her questions and erasure flags on the selectors. For each block and each branch b ∈ {0, 1} she sends a syndrome of the column-b bits of her rows on J i and a one-bit payload masked by a seeded hash of those bits. The payloads are XOR shares chosen so that the branches β add up to SD , and through CP she proves that they have this form for her committed table. 14. Bob corrects his intersection bits with the branch-βi syndromes, unmasks those payloads, and outputs their XOR. The two offsets of Steps 2–4 implement a coin toss into the well: Bob’s question is uniform, since Alice’s part is fresh, and hidden from Alice, since Bob’s part stays committed. A coin toss that both parties learn cannot be used here, because Bob’s questions on the selectors are what Alice must not learn. Each property rests on one idea. • Correctness. On J i , Bob’s question is βi , so his intersection bits equal column βi of Alice’s rows up to device faults, which the syndrome corrects. • Receiver security. Alice sees J i but not which question class it is, and the two classes are exchangeable; hence β is hidden from her, and χ hides D. The CP proof lets the simulator read both effective sender inputs off her committed table. • Sender security. Bob’s answers and selectors are committed before he learns Alice’s questions on them. The repetition bound then leaves, in every block, linear min-entropy in the bits of one branch, whose payload the hash therefore hides. The simulator reads that branch, and hence Bob’s effective choice, off his committed records.

7

The commitment protocol in words. Alice commits to a bit b. Steps 1–11 are those above, with inner classical commitments in place of CP commitments. The protocol then continues as follows; the item numbers are the step numbers of Protocol 4. 12. Bob sends a fresh seed r and χ = ⟨r, β⟩, and proves in zero knowledge that χ and the selectors are consistent with his committed question offsets. 13. Alice verifies the proof and opens her questions and erasure flags on the selectors. For each block and each branch t ∈ {0, 1} she sends a syndrome, a seed, and a one-bit payload masked by the seeded hash. The payloads are chosen so that the two branches of block i differ by ri b and the branch-0 payloads add up to χb. 14. Bob checks the openings, issues a receipt, and discards his questions, answers, and labels. 15. Alice, to open, sends b and opens her whole table. 16. Bob recomputes the syndromes and pads from the table and accepts b if both payload relations hold. • Correctness. Up to Step 11 it is that of OT; the opening checks hold by construction, since Alice computes everything from her own table. • Committer simulation. The branches β add up to (χ ⊕ ⟨r, β⟩)b, which is 0 for the honest χ. The simulator sends χ ⊕ 1, with a valid alternative witness obtained from equivocal commitments. The branches β then add up to b, which the simulator decodes from its genuine device answers as Bob does in OT. Alice cannot tell, because β is hidden from her, and the device execution is untouched. No efficient extractor for the inner commitment is assumed, and zero knowledge is not used as a proof of knowledge. • Receiver hiding. The bit b enters only through the branches 1 − βi , whose pads are uniform by the repetition bound, as in sender security of OT. • Simulation for both parties. A second equivocation layer adds a simulator against a corrupt receiver (Section 5.4), and with it coin tossing (Section 5.5). Figure 2 shows the order of commitments and disclosures on which these arguments depend. Notation for the selectors. Write Ii for block i, TBi ⊂ Ii for Bob’s audit set, and Yj for his question in coordinate j. On the unaudited coordinates, he forms J i = Jβi i ,

Jti = {j ∈ Ii \ TBi : Yj = t},

t ∈ {0, 1}.

Bob commits to both characteristic vectors, opens J i only after the audit, and keeps βi private; Alice then certifies projections of her questions and erasure flags on J i while keeping the answer fields hidden. Choice masking and affine output pairing. Bob sends only (r, χ), with e = ⟨r, β⟩ and χ = D ⊕ e, after every earlier accept-or-abort decision is fixed. At m = 1 the label symmetry makes e = β exactly uniform. Otherwise β keeps min-entropy m − 2ℓ − 3tA − O(1) given Alice’s view: m bits, less two per leaked qubit and three per tested answer. Then the parity hash makes e uniform L (Fact 9). Write u = i Pi0 and δi = Pi0 ⊕ Pi1 for Alice’s effective payloads, so that Bob’s output is u ⊕ ⟨δ, β⟩. The PAY certificate enforces δ = r∆∗ for one bit ∆∗ , hence OB = u ⊕ e∆∗ . The simulator submits (u ⊕ χ∆∗ , u ⊕ (χ ⊕ 1)∆∗ ), whose Dth component is Bob’s real output. The hash controls the joint distribution of choice and abort, and PAY pairs the two outputs (Protocol 2). Against 8

Steps 1–4

Alice Bob Commits the test set; sends offsets; Commits offsets; queries his device; queries her device commits his answers Answer cut: the answers are frozen before the test set and the partition are revealed. 5–6 Opens the test set; sends the partition Commits audit sets and selectors Selector cut: answers and selectors are frozen before the erasures are sampled. 7 Samples the erasures; commits her table Table cut: the table is frozen before any audit set is opened. 8–11 Runs the test; opens her table on the Opens audit sets and test records; audit sets; checks the selectors audits; opens the selectors Seed cut: every earlier accept or abort decision is fixed before r is sampled. 12–14 Opens the questions on the selectors; Sends (r, χ), with the mode proof in sends syndromes and masked payloads BC; decodes in OT, issues the receipt in BC Figure 2: Order of commitments and disclosures in Protocol 1 and Protocol 4, which share these step numbers. A commitment is an inner commitment in BC and a CP commitment in OT. Everything above a cut is frozen before anything below it is revealed. a cheating receiver, the simulator is the one described in the sender-security item above, and the comparison extends through the PAY check because both endpoint encodings satisfy the predicate on their stored tables (Lemma 10). Contributions, each against the closest earlier work. 1. DI OT and secure computation from qOWFs. The constructions of Grilo, Lin, Song, and Vaikuntanathan and of Bartusek, Coladangelo, Khurana, and Ma [GLSV21, BCKM21] need trusted preparation and measurement of BB84 states, and earlier DI protocols rest on other restrictions (Table 2). 2. An extractable DI commitment whose extractor leaves the devices untouched. The extractor of Bartusek, Coladangelo, Khurana, and Ma defers the receiver’s quantum measurements, which a party operating an untrusted device cannot do. 3. A selector-aware repetition theorem for the Magic Square game. The threshold theorem of Kundu and Tan [KT23] bounds wins over all copies; sender security needs a bound on a subset that the adversary chooses, together with a bound on its losses. The lift is not routine: the selector must be scored without conditioning on the adversary’s wins, and the erasures must be sampled after the selector is frozen, which is what keeps the lifted game product-anchored. 4. Robustness and leakage resilience in every layer. The bounded-storage protocol of Batra, Chakraborty, Jain, and Kapshikar [BCJK25] is robust; here robustness must also survive the commitment and the compiler, and the simulation must carry the devices’ leakage unchanged. 5. DI commitment with simulators for both parties, and DI coin tossing with negligible error. The information-theoretic DI protocols of Silman, Chailloux, Aharon, Kerenidis, Pironio, and Massar [SCA+ 11] and of Aharon, Chailloux, Kerenidis, Massar, Pironio, and Silman [ACK+ 14] have constant cheating probability and bias.

9

Two obstacles and how we meet them. Contributions 2 and 3 answer the two steps of the trusted-device constructions that fail for untrusted devices; the construction above supplies the vocabulary. Extraction without touching the physics. In the construction of Bartusek, Coladangelo, Khurana, and Ma, the extractor defers the receiver’s measurements until the sender has revealed her bases. A simulator that operates an untrusted device cannot do this: it may only ask the prescribed questions, once, and any change in the physical execution could also change what the devices leak. Our extractor changes a public parity bit, and justifies it with an alternative witness obtained from post-quantum equivocal commitments. The questions, measurements, and leakage are exactly those of the real execution (Section 5.3). Leakage, accounted for. The transcript-guessing bound (Fact 11) charges each leaked qubit two bits of the Θ(N ) bits certified per block, so ℓ = Θ(N ) is a ceiling for the sender-entropy bound alone; the selector entropy imposes the block-count constraint of the technical core below, and ℓ = polylog(λ) is what the parameter schedule (Section 2.4) affords with polylogarithmic device use. Entropy against non-IID devices. Sender security needs min-entropy in Alice’s device answers, on a set of coordinates that a cheating receiver chooses, when the devices are arbitrary and entangled, and the receiver may measure jointly and late. No existing repetition theorem bounds this; the selector-aware bound of the next subsection does.

1.4

The technical core: repetition with a receiver-chosen selector

Sender security of OT and hiding of the commitment both reduce to one statement about n parallel Magic Square games. Charlie receives row questions and returns rows. Dave receives column questions and fixes his answers B together with a selector J ⊆ [n] of his choice. Only then is each coordinate erased, independently with a fixed probability δ∗ , and Dave receives Charlie’s questions on the coordinates that were not erased. Dave must output Charlie’s rows on J; an erased coordinate counts as correct. Let L be the number of unerased coordinates on which the Magic Square condition fails, and Q the number of selected coordinates on which Dave is correct. ∗ For every selector density ρ and every γ > 1+δ 2 ρ there is β > 0 such that Pr[L ≤ βn ∧ |J| ≤ ρn ∧ Q ≥ γn] ≤ 2−Ω(n) , for every strategy with arbitrary entanglement and quantum memory, and with no lower bound on |J| (Theorem 4).

The bound has to be parallel. An honest party may use its device one coordinate at a time, but a corrupt receiver holds its device and may measure all coordinates jointly and as late as it likes, so sequential analyses such as entropy accumulation do not describe it. For one copy, Fu and Miller [FM18] show that a Dave who wins the Magic Square game with probability 1 − ε guesses √ a second bit of Charlie’s row with probability at most 12 + O( ε); this is why the game is Magic Square and not CHSH, in which Dave’s answer and both questions determine Charlie’s winning answer and leave nothing to hide (Section 2.1). To handle a selector, we mix the Magic Square test with a row-guess test in which an unselected coordinate is completed by a fair coin. The mixture is a two-round product-anchored game of value below one, and the threshold theorem of Kundu and Tan applies to it. The erasures play the role of the anchor; because they are sampled after (B, J) is frozen, they are independent of the selector, and concentration needs no conditioning on Dave’s wins. Under leakage, the label vector is what a corrupt sender attacks, and the leaked qubits may correlate all of its bits at once; the receiver argument therefore bounds the entropy of the whole vector and hashes it, and assumes no independence across blocks. The protocols use the theorem 10

through one lemma (Lemma 1). From Dave’s frozen record, let H be the question class in the minority on J. A guess of Alice’s column-H bits on J, together with Dave’s frozen answers and row parity, yields her whole row on at least half of J. The theorem forbids this, so those bits have min-entropy Ω(n) given everything Dave holds. Table 4, in Section 3, matches the game to the protocol steps listed above and charges, item by item, what the protocols disclose beyond the game; the pad entropy that remains is the raw entropy minus its last column.

1.5

Previous work and technical contributions

The contributions listed in Section 1 are stated against the closest works; this subsection adds the comparison of reduction chains, the credits for the ingredients, and the other DI protocols. Earlier reduction chains. Figure 1 sets the plain-model constructions of Grilo, Lin, Song, and Vaikuntanathan [GLSV21] and Bartusek, Coladangelo, Khurana, and Ma [BCKM21] against ours. Selective-opening BC permits opening chosen positions of a committed string; vCDS releases a secret on a valid NP witness and certifies input–output consistency. Auxiliary classical tools come from the same qOWF assumption. In the trusted-quantum setting, the assumption weakens to EFI pairs, which are equivalent to commitments with quantum communication [BCQ23] and suffice for the chain of [BCKM21]. They do not apply here (Figure 1): an EFI-based commitment sends quantum states between the parties, and the DI model provides no quantum channel. The inner commitment must have classical messages, for which qOWFs are the minimal known assumption. Grilo, Lin, Song, and Vaikuntanathan [GLSV21] first combine Naor commitments with postquantum ZK; the resulting BB84 OT has an inefficient receiver simulator. Parallel composition, garbling, commitments, and ZK yield weak vCDS. A simulated trapdoor then lets an efficient CDS receiver recover the committed secret; consistency proofs bind it to later openings. The final commitment is substituted back into OT for efficient simulation on both sides [GLSV21, Sections 3–4, Figure 6]. Bartusek, Coladangelo, Khurana, and Ma [BCKM21] first make Naor’s commitment equivocal. Trusted BB84 states and delayed-measurement simulation then supply extraction. Applying the equivocation compiler again preserves extraction and gives the commitments used in the final BB84 OT [BCKM21, Sections 2.2–2.5, Theorems 4.1, 5.1, and 6.2]. More generally, black-box access to statistically binding, quantum-computationally hiding commitment suffices for their stand-alone simulation-secure OT in the trusted quantum-communication model [BCKM21, Corollary 6.5]; EFI pairs therefore suffice [Yan22, BCQ23]. This implication permits prescribed quantum operations and communication. Our construction uses classical control of untrusted devices, with the robustness and leakage bounds stated here. Our NP relations, like the proof machinery of [GLSV21], use classical algorithms inside NP statements. Efficient simulation and sequential composition already hold in both works. Device independence, robustness, and leakage introduce the additional proof obligations below. Credits for the ingredients. The repetition bound is derived from the two-round threshold theorem of Kundu and Tan and the single-copy bound of Fu and Miller. The inner equivocal commitments are those of Bartusek, Coladangelo, Khurana, and Ma [BCKM21, Theorem 4.1]. Grilo, Lin, Song, and Vaikuntanathan [GLSV21] likewise use consistency proofs to bind extracted values to openings; our audits and fixed syndromes make this binding compatible with DI certification and honest faults. Syndrome-based noisy extraction also appears in the trusted protocol of Diamanti, Grilo, Innocenzi, Lefebvre, Yacoub, and Yángüez [DGI+ 26, Section 1.2]; the affine sharing uses the S-Reduce and XOR-combiner ideas of [DKS99, HKN+ 05], and Section E gives further provenance. 11

Leakage in DI protocols. The nearest treatment is that of Zapatero and Curty [ZC26], who model partial leakage of the inputs as a noisy channel in CHSH-based key distribution. Here the leakage is adaptive, bidirectional quantum communication between the laboratories, the adversary is a party rather than an eavesdropper, and the simulator must reproduce the leaked transcript unchanged. Table 2: Device-independent two-party protocols: what security rests on beyond isolated laboratories, and what is guaranteed. Our row gives up unconditional security and the freedom to reuse devices; it gains negligible error and simulation security against general devices. Work [SCA+ 11, ACK+ 14] [KST22] [KW16] [BY23, BCJK25]

This work

Task commitment, coin flipping XOR OT, one copy two-party tasks

Security rests on nothing beyond isolation nothing beyond isolation

attacks restricted to be sequential OT bounded quantum storage, in [BY23] together with computational assumptions and IID devices OT, commitment, qOWFs; isolated single-use coin tossing, MPC batches; leakage at most ℓ

Guarantee constant cheating probability and bias constant cheating bounds security against sequential attacks OT in that model; [BCJK25] is robust and composable

simulation-based, sequentially composable, negligible error, robust

Relation to earlier DI work. Table 2 lists the earlier DI two-party protocols with what each rests on and guarantees. The closest is that of Batra, Chakraborty, Jain, and Kapshikar [BCJK25], where Magic Square games, repetition, and seeded extraction already appear; the differences in assumptions and security notions are part of the comparison. Organization. Figure 1 gives the map: preliminaries (Section 2); the three reductions from the main result down (Sections 3 to 5), each with its complete proofs; the assembly (Section 6); the repetition theorem (Section 7); and appendices with imported facts, parameter feasibility, the compiler proof, composition, and comparison. The informal statements of Section 1.2 are Theorems 14, 15 and 23 and Corollaries 2 and 16; the model of Section 1.1 is Definitions 2 to 5, 8 and 13; and the game-to-protocol accounting is Table 4.

2

Cryptographic preliminaries and security definitions

The proofs need two interfaces: a physical experiment that certifies entropy, and classical records that preserve it until transfer. We first fix the game and simulation convention, then state the repetition input and commitment interfaces. Standard entropy, hashing, and concentration tools are collected in Section A. The conventions that govern every proof are in Section 2.5.

12

Leakage and coding tools. The proofs use transcript guessing to account for bounded interactive communication and binary linear codes to reconcile honest faults. The common syndrome interface uses a constant-redundancy high-rate code at m = 1 and the vanishing-redundancy BCH family at m > 1; Section 2.4 specifies both choices. Precise statements appear in Section A.3. For trits, + and − denote addition and subtraction in Z3 , applied coordinatewise to trit strings. The symbol ⊕ denotes bitwise XOR. Definition 1 (Magic Square predicate). For x, y ∈ {0, 1, 2} and a, b ∈ {0, 1}3 , define  

2 M



j=0

MS(x, y, a, b) := I ay = bx ,

aj = 0,

2 M

 

bj = 1 . 

j=0

Set MS = 0 on malformed inputs. Every MS check includes all three conditions. All logarithms are base two. Write ρ ≈ε σ if 12 ∥ρ − σ∥1 ≤ ε; ≈c denotes quantum-computational indistinguishability. Reading the procedures. Each numbered step names the acting party. Consecutive local actions within one turn are grouped together; opposite-party actions have separate steps. A commitment or proof invocation runs its specified interactive subprotocol to completion, with the other party in the receiver or verifier role. Device actions identified as sharing a window are concurrent local instructions, not extra message rounds. Every committed string uses a fixed canonical bit encoding: In source BC, fields opened separately have separate commitment handles. In outer OT, certified projections may refer to one shared CP record; previously certified entries are reused, and overlapping projections must agree. Simulator boxes give chronological actions at the corresponding message cuts; the corrupted party continues its given strategy throughout.

2.1

Selector-aware repetition with late erasures

in In Gsel 1 the verifier sends independent uniform trits X , Y to Charlie and Dave. Charlie returns in an even row A ; Dave’s Y -controlled instrument freezes F = (B, J), where B is an odd column and J ∈ {0, 1}, and retains arbitrary quantum memory. Only then does the verifier sample b = X in if C = 1, and X b = ∗ otherwise. Dave returns A[0, b 1]; C ← Bern(1 − δ∗ ) and send Dave X late maps preserve F and its inaccessible classical copy. Put

1, C = 0, in in in b I{A [0, 1] = A[0, 1]}MS(X , Y, A , B), C = 1,

(

W =

Q = JW,

L = C(1 − MS(X in , Y, Ain , B)).

The parallel game uses product questions and fresh independent Ci , with arbitrary entanglement and joint operations across coordinates. Theorem 4 (Selector-aware constant-threshold repetition). For every δ∗ ∈ (0, 1), ρ ∈ (0, 1], and γsel ∈ (((1 + δ∗ )/2)ρ, ρ), there exist ηsel , csel > 0 and n0 ∈ N such that ∀S allowed and ∀n ≥ n0 , Pr S

" n X i=1

Ji ≤ ρn,

n X

Li ≤ ηsel n,

i=1

n X

#

Ji Wi ≥ γsel n ≤ 2−csel n .

i=1

The allowed strategies are those defined above; no lower bound on 13

P

i Ji is assumed.

(1)

Section 1.4 gives the idea of the proof, and Section 7 the proof. Honest Alice always queries Xjin and records Ain j before using Cj . Her committed table has (Xj , Aj ) = (Xjin , Ain ) on active coordinates and (X j , Aj ) = (0, 000) on anchors. Raw anchor j questions are absent from subsequent controller messages; C does not reach either device. Thus the protocol supplies precisely this late-erasure interface. Private presampling of unused C is equivalent for the sparse-test argument. Why the Magic Square game and not CHSH. CHSH is far easier to implement, and it certifies entropy in the usual DI protocols, but it does not survive the two-round structure above. CHSH is a projection game: once Dave holds his answer b and learns both questions, Charlie’s winning answer is determined, a = b ⊕ xy. A strategy that wins therefore leaves no randomness in Charlie’s answer given Dave’s, and the hidden string, which is what a guessing Dave must fail to produce after learning X in , would have no entropy at all. Magic Square is not a projection game: Charlie’s row has two free bits, Dave’s column fixes only the entry at the intersection, and Fu and Miller [FM18] show that the other entry stays close to uniform in every strategy that wins with probability close to one. That second bit is the hidden string. The proof uses the game through this one-copy bound (Lemma 18) and, in the hidden-string lemma, through the row parity that reconstructs the third entry. A replacement game therefore needs both a comparable residual-guessing bound and a reconstruction rule with the same role in the hidden-string argument. The hidden raw string. Both protocols apply the game to one block, and what must stay hidden is a string of Alice’s answers. For a strategy of the game with a nonempty frozen selector J, define Nb = |{j ∈ J : Yj = b}|,

H = arg min Nb ,

(2)

|K| ≥ |J|/2.

(3)

b∈{0,1}

breaking ties in favor of zero, and put K = {j ∈ J : Yj ̸= H},

Both H and K are functions of Dave’s early record (Y, B, J). In the protocols J is a block selector and H is the branch that the receiver must not learn; for an honest selector, H = 1 − βi . Lemma 1 (Hidden raw string from the frozen record). Fix δ∗ ∈ (0, 1) and constants 0 < ρmin ≤ ρmax ≤ 1. Let S be a strategy of Theorem 4 with frozen J satisfying ρmin n ≤ |J| ≤ ρmax n. Put raw ZH = (Ain j [H])j∈J ,

can ZH = (Cj Ain j [H])j∈J ,

Good =

n nX

o

Lj ≤ ηn .

j=1

There exist η, c > 0 and n0 , depending only on the fixed parameters, such that for either ZH ∈ raw , Z can }, every late map G, which receives Dave’s entire residual state and the late questions, {ZH H and every n ≥ n0 , Pr [Good ∧ G outputs ZH ] ≤ 2−cn . (4) S,G

Section 1.4 gives the idea, and Section 7.1 the proof.

2.2

Simulation and sequential composition

Simulator-based security compares real and ideal executions. We first specify their admissible initial states, then define this comparison. 14

Definition 2 (Admissible initial extension). Fix classical party inputs and one corruption. Write IH , WH , KH for honest trusted input, blank workspace, and fresh coins; DA , DB for the outer device laboratories; and P, R for corrupt workspace and inaccessible reference. (i) State. An admissible initial extension has η IH WH DA DB P R = |iH ⟩⟨iH | ⊗ |0⟩⟨0|WH ⊗ η DA DB P R , η KH DA DB P R = τKH ⊗ η DA DB P R , where η DA DB P R is arbitrary, subject to the fixed corrupt input. (ii) Computation. Active instruments are nonuniform QPT on polynomial-size registers, and no operation accesses R. (iii) Trusted storage. Honest trusted storage has no physical leakage interface. Its only outputs are prescribed classical messages and device inputs. (iv) Communication and subprotocols. Inter-laboratory communication is exactly Definition 8. CP and ZK operations never access DA , DB , R and introduce no outer device communication. They occur outside the outer input–output window; only saved records persist within it. Compiled calls use separate batches satisfying Definition 13. We use the standard auxiliary-input-uniform quantifier order ∀ P∗ ∃ Sim ∀ η R , where one simulator chosen from the adversary works for every admissible extension, uniformly also over the fixed honest input values. All simulators are QPT, with a polynomial bound on every branch. Definition 3 (Computational augmented security). (i) Compared states. RealPf ,P∗ (η R ) retains (corrupt final cq-state, honest input/output, public transcript, R), tracing out only honest call-local workspace irrevocably discarded at return; Idealf,Sim (η R ) retains the same systems. (ii) Requirement. Computational augmented security means ∀ P∗ ∈ QPT ∃ SimP∗ ∈ QPT ∀ η R : RealPf ,P∗ (η R ) ≈c Idealf,SimP∗ (η R ). For each nonuniform QPT test, its negligible advantage bound is uniform over admissible η R and fixed honest inputs. (iii) The device resource. Both experiments use the same initial call-local honest device share DH . In the ideal experiment, a declared interface DevH allows SIM only the prescribed honest classical device operations and leakage window on that share, preserving its correlations with the corrupt workspace and R. No reset, copying, or re-preparation of DH is allowed. (iv) What SIM receives. SIM receives the corrupt initial workspace, including its device share, and ideal releases, but no honest trusted input or protected pending state; it acts as Sim ⊗ idR . All realization claims, including the notation Idealf,Sim , are relative to these declared device resources. 15

Throughout, a statement that one functionality is realized or reduced to another includes this efficient-simulation requirement: every efficient corrupted strategy has an auxiliary-input-uniform QPT simulator. The BC-to-CP compiler uses the continuing-state contract in Definition 10, realized by our DI BC protocol. The ideal functionalities themselves are interfaces; security is a property of the protocols realizing them. Definition 4 (Invocation boundary). Calls have distinct labels and disjoint execution intervals. (i) Admissible state and fresh coins. At every reached call in every replacement hybrid, and for every classical input i with Pr[I = i] > 0, ρ|I=i ∈ Adm,

ρK,rest|I=i = τK ⊗ ρrest|I=i ,

where Adm comprises Definition 2 and the subroutine’s device conditions, and K denotes fresh honest call coins. (ii) Reference. The reference contains all untouched honest outer, scheduler, channel, and future-call registers. (iii) Return interface. It retains honest input/output and the entire corrupt state, including transcript, leakage, and device residuals. Only irrevocably discarded honest scratch and continuation-inaccessible devices are traced out. (iv) Devices. Only the current batch is accessible, through its declared device interface; future batches remain protected. At return, the current interface closes, and its retired honest share is discarded in both experiments. (v) Aborts. Abort branches are included in the real–ideal comparison. On such branches, the honest parties make no further calls. Theorem 5 (Efficient sequential composition). Let QPT protocols Pf and Pgf realize f and g as in Definition 3. Under at most one static corruption, replace q(λ) ≤ poly(λ) completed ideal-f calls by Pf . If every reached boundary in every replacement hybrid satisfies Definition 4, then P

Pg f realizes g,

Adv ≤ νg + qνf , cor εcor ≤ εcor g + qεf .

Simulation is auxiliary-input-uniform QPT. Here νg , νf are uniform negligible bounds for the induced QPT tests, and the correctness bound assumes joint output–reference trace-distance errors at most cor εcor f at each reached honest call and εg for the outer protocol. Proof outline. Replace calls one at a time, retaining all continuation registers. The common suffix and final distinguisher form a QPT test, so call security bounds each replacement. Weight reached branches by their probability and sum; then apply the outer simulator. Section D proves uniformity, efficiency, abort preservation, and correctness in full. This theorem composes completed OT calls. Pending CP records and openings within a call use the separate continuing-state contract below. The isolated one-block parameter choice also uses the following measurement condition. Definition 5 (Coordinate-local honest-receiver architecture). The honest receiver instrument producing the committed B is coordinate-local if HBb =

n O i=1

HBb , i

∀y :

MyB =

n O i=1

16

(i),y

MBi i .

Initial inter-coordinate entanglement, retained quantum side information, and subsequent joint postprocessing are unrestricted. This condition applies to receiver privacy; sender security against corrupt Bob permits Theorem 4’s joint instruments. Fact 1 (Local no-signalling [Wil17]). For every ρABR and CPTP map N : B → B ′ , TrB ′ [(idAR ⊗ N )(ρ)] = ρAR . (i),yi

For B = B1 · · · Bn and local instruments {Mbi

}bi , define

"

σbAR := S |y

X

TrB ′

!

idAR ⊗

O

(i),y Mb i i

#

(ρ) .

i

bS̄

Then yS = yS′ implies σbAR = σbAR ′ for every S ⊆ [n] and bS . S |y S |y

2.3

Commit-and-prove functionality

The outer OT uses a commit-and-prove functionality to store immutable strings and certify ownerauthorized predicates on them. Theorem 12 realizes this functionality from qOWFs and the source commitment of Definition 10. Definition 6 (Commit-and-prove functionality). ideal(CP) is a classical functionality that maintains polynomially many immutable bit strings of prescribed public polynomial lengths. Each record has a unique session and record identifier, a designated owner, and a designated verifier. Identifiers and roles are part of every command and transcript and are left implicit in the notation. (i) Commitment. On the owner’s first (commit, M ) command, check that M is a bit string of the prescribed public length; otherwise abort the session without creating a record. On success, store M and issue a receipt consisting of the identifier, the roles, and the length. (ii) Predicate certification. Only the owner may issue (check, P, y) for a record, where P is a Boolean circuit within a public polynomial size bound and y is a string. Publish the request identifier, P , and y. If P (M, y) = 1, issue a success certificate subject to the delivery rule below; otherwise abort the session. (iii) Selective opening. Open(MS ) is the request (check, PS , (S, z)) with PS (M ; S, z) = [πS (M ) = z], where πS (M ) is the substring of M at the positions in S. Any two successfully certified openings must agree on all positions common to their requested sets. (iv) Rejections. Wrong-role, cross-session, duplicate-commitment, malformed, and out-of-schedule commands cause session abort. Apart from receipts, only the contents of an owner-authorized public request and its success or ⊥ are released. No record is ever updated. (v) Delivery with abort. The adversary schedules the delivery of receipts, certificates, and ⊥, and receives its own releases first. It may send ⊥ at any time. On abort, every honest party receives ⊥, and the session terminates; no further operation on any record in that session is permitted. No fairness is required [Gol04, Chapter 7]. Four consequences are used repeatedly. A receipt is no function of the contents of M . A failed check does not certify that the predicate is false, and success is impossible when P (M, y) = 0. An opening request makes (S, z) public even if the session aborts, and only a successful certificate authenticates z; no opening randomness and no unselected entry is revealed. The verifier learns nothing about an 17

honest owner’s record without an owner-initiated request, and predicate checks remain available after successful projections. Honest OT controllers authorize only the requests that the protocol prescribes, and the functionality never acts on a device register or on the reference. Write Commit(M ) for commitment and Check(M ; P, y) for an owner-authorized check on that same record. The identifier, not the hidden contents, locates a record. A simulator may log a corrupted owner’s classical commitment inputs; there is no public read or extraction command for an honest owner’s record. The commitment and predicate simulators must preserve the complete corrupted continuation and untouched reference, uniformly over all admissible inputs. All records of one OT call, including opposite-owner records and delayed projections, belong to one CP session and share the stateful simulation contract proved in Lemma 23. The externally compared continuation excludes an honest record’s internal commitment seeds and proof coins. They remain encapsulated behind the prescribed operations; protected outer state and other pending honest sessions remain part of the continuing reference. Fact 2 (Post-quantum commitments from one-way functions). Post-quantum one-way functions give Naor’s commitment, which has classical messages [Nao91], via the pseudorandom-generator reduction of Håstad, Impagliazzo, Levin, and Luby [HILL99]; the post-quantum instantiation is discussed in [BCKM21, Section 3.1.1 and Footnote 6]. The compiler and ordinary ZK proofs use this commitment. For a quantum-secure PRG G : {0, 1}λ → {0, 1}3λ , the receiver sends a ∈ {0, 1}3λ and the honest sender, on bit b, samples fresh s and sends d = G(s) ⊕ ba. Opening reveals (b, s). Hiding holds for any receiver-chosen a, also with quantum auxiliary input independent of the fresh seed. For uniform a, failure of setup-wide unique-bit binding has probability at most 2−λ : two openings imply a = G(s0 ) ⊕ G(s1 ), a set of size at most 22λ . The CP protocol of Protocol 11 uses a receiver-chosen string a for each record and keeps its commitment seeds private during certified projections. Fact 3 (Post-quantum zero knowledge for NP, GMW and Watrous [GMW91, Wat09]). Every NP relation has a classical-message sequential proof with perfect completeness, negligible statistical soundness, and quantum-computational zero knowledge, assuming a statistically binding, quantumcomputationally hiding commitment. For every nonuniform QPT verifier there is one QPT simulator, fixed from the verifier independently of its auxiliary state, whose output channel is computationally indistinguishable from the real verifier channel uniformly on arbitrary quantum auxiliary inputs entangled with an inaccessible reference. Polynomially many sequential invocations preserve this guarantee. This is the GMW proof for NP with the quantum-verifier analysis of Watrous [Wat09, Sections 3 and 6.2]. The DI BC mode relation uses the ordinary GMW–Watrous proof. Its commitments are internal to that proof; no external CP call occurs inside a rewound segment. The outer OT uses ideal(CP) certificates, implemented from source BC by the challenge-first arguments of Protocol 9. Their witness-free simulator and its false-instance extension are established in Lemma 22.

2.4

A common parameter schedule

Both DI reductions use one batch of L = mN + tA coordinates: a hidden size-tA test and m blocks of size N . The same messages and simulators are used for every m ≥ 1. The choice of m depends on the leakage budget and, at zero leakage, on the honest-receiver architecture. We distinguish parameter regimes, not protocols. 3/2 Put tA = ⌈log2 (λ + 2)⌉ and sλ = ⌈log22 (λ + 2)⌉. One sufficient schedule is (

m=

1, ℓ = 0 and honest Bob is coordinate-local, ⌈2ℓ + 4tA + sλ ⌉, otherwise, 18

(5)

Choose N = ⌈C max{sλ , m3 }⌉, where C > 0 is a sufficiently large fixed constant. For OT, ℓ bounds both corruption-specific budgets. The second line also covers zero leakage with an arbitrary joint honest-Bob instrument. For a fixed coordinate-local architecture this is a function of (λ, ℓ) whose zero-leakage value is one block. Choose small positive constants caud , cEC and use audit rate caud /m and code redundancy at most cEC /m. They obey the entropy budgets in Equations (11) and (49). Choose the selector window with 0 < ρmin < (1 − caud )/3 < 1/3 < ρmax < 1. For m = 1, use the high-rate code of Fact 12 with a fixed positive decoding radius τ0 . For m > 1, use Fact 13. Thus (

τEC (m, N ) =

τ0 > 0, Θ((m log N )−1 ),

m = 1, m > 1.

(6)

Audit thresholds and tolerated honest-fault rates are fixed small multiples of this radius, with the multiplicative slack specified in each reduction. Code selection changes a public parameter, not the syndrome interface or the protocol steps. One instance. At λ = 128 the schedule gives tA = 19 tested coordinates and sλ = 50. In the isolated regime this is one block of N = ⌈50C⌉ coordinates, with the constant decoding radius τ0 . In the general regime with ℓ = 10 leaked qubits, m = 2ℓ + 4tA + sλ = 146 blocks of N = ⌈Cm3 ⌉ ≈ 3 × 106 C coordinates each, and the tolerated fault rate is Θ((m log N )−1 ). These values illustrate the schedule only: the proof does not specify concrete constants or a numerical security level at λ = 128. The cubic dependence of N on m comes from the sampling requirement N/(m2 log N ) = ω(log λ) and is the cost of leakage and joint measurements; this is related to the leakage-rate limitation discussed in Section 1.2. Lemma 2 (Feasibility in both regimes). For every ℓ = polylog(λ), there exist fixed constants in Section 2.4 satisfying all BC/OT pad, sampling, and correctness inequalities. In particular, m=1 m>1 selector privacy exact symmetry both selector-entropy budgets honest-fault tolerance Θ(1) Θ((m log N )−1 ) 2 coordinates per invocation Θ(log λ) mN + tA Both columns have negligible error; the first assumes isolation, ℓ = 0, and coordinate-local honest Bob. The proof, in Section B, checks each budget against the schedule: the selector margin against the block count, the audit and code rates against the raw entropy, and the honest fault rate against the decoding radius. The security parameter still governs the number of coordinates within the single isolated block. Moreover, the positive-leakage line retains an additive security margin and a test debit: this proof does not establish m = O(ℓ + 1) uniformly in λ.

2.5

Proof conventions

Three conventions hold in every proof. (i) Subnormalized branches. For an event E, ρE denotes its subnormalized branch, of trace Pr(E). Error, entropy, and hashing bounds are stated for such branches; they are therefore absolute and hold at every acceptance probability. Abort branches are retained, and renormalization is stated explicitly where it occurs. (ii) Fixed statistical hybrids. Every information-theoretic step takes place inside one fixed experiment: the ideal CP execution for OT, 19

and the equivocal-commitment executions EA , EB of Section 5.6 for BC. Inside such an experiment, the unique value of a statistically binding commitment may be assigned by an unbounded function of the classical transcript. This value is an analysis register: no algorithm reads it, and it never enters a computational comparison. Only the final efficient real/ideal comparison is transferred to the concrete implementation; computational errors are added to the statistical bound and are never multiplied by a guessing factor. (iii) Totalization. A variable undefined on a stopped branch receives a fixed default in a private analysis register; the compared views contain only the actual stopped transcript.

2.6

Glossary of recurring terms

Table 3 collects the terms that the proofs use as shorthand.

3

Device-independent oblivious transfer from commit-and-prove

This section contains the whole OT construction in the CP-hybrid model: a warm-up instance, the security notion and the physical interface, the payload predicate, the protocol, its theorem, and one paragraph for each property. The commitment section, Section 5, follows the same order. The same block protocol serves both parameter regimes of Section 2.4: its isolated instance has m = 1 and r = 1, and increasing m supplies the entropy needed for bounded leakage or joint honest-receiver measurements. Sections 4 and 5 realize CP, and Section 6 assembles the three reductions.

3.1

Warm-up: one block, perfect devices, isolated laboratories

The simplest instance of the protocol described in Section 1.3 has m = 1, r = 1, ℓ = 0, and devices that win every Magic Square game. Then no syndrome is needed, β is a single bit, χ = D ⊕ β, and Alice’s two payloads are P b = Sχ⊕b , masked by the pads ⟨Z b , Rb ⟩. Bob knows Z β and outputs P β = Sχ⊕β = SD . Against Alice, the simulator sends a uniform χ, reads P 0 , P 1 off her committed table, and submits (P χ , P χ⊕1 ); a real Bob with choice d has β = χ ⊕ d and outputs the dth component. Against Bob, the simulator computes the minority class H from his committed records, obtains Sχ⊕(1−H) , and uses it for both payloads; only the padded branch H differs from the real execution. The general protocol adds three things. Faulty devices need thresholds in the test and audit, and syndromes to reconcile Z β . Leakage and joint measurements need m blocks: β becomes a vector, a fresh seed r hashes it to one bit e = ⟨r, β⟩, and the two payload branches of block i differ by ri ∆, which the PAY certificate enforces for one bit ∆. Finally, every disclosure beyond the game is charged against the entropy, as listed in Table 4. The entropy budgets.

The pad budget of one block is

kpad = γrep N − 2ℓ − 2ρmax m rEC N − 6mδaud N − O(m log N ), with audit rate δaud = caud /m and code redundancy rEC = cEC /m. Thus the syndrome and audit charges are 2ρmax cEC N and 6caud N , independent of m. The block count still enters through the O(m log N ) term and the selector margin m − 2ℓ − 3tA − O(1), which must be ω(log λ) for negligible receiver-privacy error in the general regime. The schedule supplies this additive margin; it does not require m = ω(ℓ). Its redundancy rEC = cEC /m gives inverse-polylogarithmic fault tolerance.

20

Table 3: Recurring terms. Step numbers refer to Protocol 1 and, up to Step 13, to Protocol 4. Term coordinate, batch device window block Ii , test set TA , audit set TBi label βi , selector J i erased coordinate (anchor) hidden branch Hi source, source-dependent receipt, certified projection mode pre-r post-selector view other-coordinate registers good audit

independent-mask experiment call-local totalized

3.2

Meaning One Magic Square game; the devices of one invocation, used once. The single interval in which a batch receives its questions and returns its answers (Definition 8). One of the m groups of N untested coordinates; the coordinates Alice tests openly; the hidden coordinates of block i that Bob audits. Bob’s private bit for block i; the unaudited coordinates of the block on which his question was βi . A coordinate with Cj = 0, whose record Alice replaces by (0, 000). The question class in the minority on J i , computed from Bob’s committed records (2); for an honest Bob, Hi = 1 − βi . Alice’s raw device answers; depending on them. CP’s acknowledgement of a commitment, containing only identifier, roles, and length; a selective opening (S, z) together with its success certificate (Definition 6). Which parity relation χ satisfies in the commitment protocol: χ = ⟨r, β⟩ in a real execution, χ = ⟨r, β⟩ ⊕ 1 in the simulation. Before Bob sends the seed r in Step 12; the pre-r decisions are the accept-or-abort decisions of Steps 1–11. Alice’s view after the selectors are opened in Step 10. The quantum systems of the coordinates outside the block under analysis. The audit was accepted and, in every block, Alice’s committed table disagrees with Bob’s answers on at most ηaud N coordinates (26), which is within the decoding radius on J i . The experiment in which χ is a uniform bit independent of everything else. Belonging to one invocation and discarded when it returns. Extended by fixed default values on branches where the protocol has stopped (convention (iii) of Section 2.5).

Security notion and physical interface

We first fix what the protocol must realize, then the physical interface through which the untrusted devices may leak. Definition 7 (Ideal functionality for oblivious transfer). For an ordered sender/receiver pair, ideal(OT) has IS = {0, 1}2 , IR = {0, 1}, ((S0 , S1 ), D) 7−→ (∅, SD ). ⊥ is not an input. The simulator may issue a global abort at any time before honest delivery, including before corrupt input; then every honest party receives ⊥ and the call terminates. After valid inputs, release the corrupt prescribed output to the simulator first. For the honest-party set 21

H, subsequently deliver (

outH =

⊥H , (∅, SD )|H ,

abort, otherwise.

Thus a corrupt receiver may learn SD before suppressing the sender’s empty output. Alice is the OT sender below. For a finite set I, S ← Subp (I) includes each element independently with probability p. Restrictions retain coordinate order; AI (b) = (Aj [b])j∈I and AI [0, 1] = AI (0)AI (1). The total syndrome decoder SyndDec⊤ returns its decoded error vector, or the all-zero vector on failure. For a binary string of length n, Synn is its code syndrome and Extn (z; s) = ⟨z, s⟩ for a uniform n-bit seed s. Canonical syntax means valid trits, active row parity, and (Xj , Aj ) = (0, 000) on erased coordinates. All final checks validate both branches before honest Bob selects an output. We use CP commitment, owner-authorized certified projections, and predicate checks from Protocol 3. This classical layer does not act on an outer device register. A global abort returns ⊥ to every honest party. At delivery or abort, an honest party retires all call-local devices and discards private call-local scratch, retaining its input–output interface and public transcript; untouched outer state remains protected. A corrupted receiver may request abort after learning its selected bit; the simulator relays it before honest-sender delivery under Definition 7. Otherwise Alice outputs ∅. Honest-device faults. Honest controllers encode an active row as (a0 , a1 , a0 ⊕ a1 ) and a column as (b0 , b1 , 1 ⊕ b0 ⊕ b1 ) from the two recorded bits. The active honest coordinate implementations are independent, though they need not be identical. Normalization preserves every winning MagicSquare record. The fault rate concerns the resulting parity-correct records: for every question pair, Pr[MS(x, y, Ai , Bi ) = 0 | Xi = x, Yi = y, Ci = 1] ≤ qdev . (7) Classical computation, communication, storage, commitments, and postprocessing have their ordinary correctness guarantees. Anchors contribute the known bit zero. Independence is used only for honest correctness; security permits the stated arbitrary entangled attacks. One parallel leakage window. Definition 8 (Admissible blockwise OT leakage). Fix a corruption experiment. (i) Window and budget. From the instant the first Magic Square input is supplied until all outputs in the complete block batch have been collected, the laboratories may exchange arbitrary adaptive, bidirectional quantum messages of total cost at most ℓ qubits, correlated across blocks and with arbitrary private memory. The budget is global, not renewed per block. The interface then closes permanently. (ii) Accounting. Classical bits count as computational-basis qubits. Every adaptive control symbol, including direction, routing, message length, continuation, and stopping, is encoded in a selfdelimiting classical transcript and charged to the same budget; only a fixed public communication schedule is free. All delivered systems and classical transcript copies enter the corrupted party’s side information. (iii) Exclusion. The interface cannot read honest Bob’s trusted input D. We write ℓA for the budget in the experiment with corrupted Alice and ℓB for the budget with corrupted Bob. 22

The exclusion is necessary: an interface that could read D could transmit it, and receiver privacy would be impossible. Later selectors, fresh seeds, CP operations, certified projections, audits, the transfer, and the predicate-proof messages run outside the window; source-dependent disclosures are charged explicitly in the entropy proof.

3.3

The payload-consistency predicate

Alice’s last message is accompanied by a CP certificate that her payloads are affine in the branch. The predicate below is the only statement about Alice’s private table that the protocol ever certifies. Alice commits to the entire canonically encoded table MA = enc((X i , Ai , C i )i∈[m] ) in Step 7 of Protocol 1, before any audit mask is opened. After the audit, (r, χ) and Mfin = ((Fi0 , Fi1 , Ri0 , Ri1 , Wi0 , Wi1 ))i∈[m] are public. Definition 9 (Payload-consistency predicate on the committed table). Put xpay = (J, r, Mfin ). For candidate answer tables (Ai )i and a bit ∆, define ΦPAY (xpay ; (Ai )i , ∆) = 1 ⇐⇒ ∀i ∈ [m], b ∈ {0, 1} : Zib := AiJ i (b), Wib = Syn|J i | (Zib ), Pib := Fib ⊕ Ext|J i | (Zib ; Rib ), Pi0 ⊕ Pi1 = ri ∆.

(8)

and Ppay (MA , xpay ) = ΦPAY (xpay ; A(MA ), 0) ∨ ΦPAY (xpay ; A(MA ), 1).

(9)

Here A(MA ) denotes the answer fields of the committed string, and malformed public seeds, syndromes, or ciphertexts make the predicate false. Πpay denotes Alice’s owner-authorized Check(MA ; Ppay , xpay ) operation together with Bob’s verification of its correctly routed success certificate. The predicate is polynomial time, because it evaluates the relation for both values of ∆, and a single value must satisfy all block equations. In the ideal CP execution, a successful certificate therefore enforces (8) on the actual stored table exactly, for some ∆∗ ∈ {0, 1}. Honest Alice’s payloads satisfy the predicate with ∆ = S0 ⊕ S1 . At m = 1, where r = 1 and P1b = Sχ⊕b , every pair of payloads defines ∆∗ = P10 ⊕ P11 , so the affine clause restricts nothing and the certificate only binds the syndrome and payload equations to the committed table. Table fields undergo the audit and projection checks of Protocol 1, and Bob checks the prescribed projections and their public syntax before the request. The concrete argument and its transcript are supplied by Theorem 12, outside the outer device window. To prove security of this payload layer, we must account for the information released before the fresh hash seed. The post-output partition is fresh against corrupt Bob; against corrupt Alice, it may be arbitrary, but Bob’s labels are sampled afterward. Guessing test answers at their first public projection permits whole-laboratory no-signalling for a joint Bob measurement; ideal commitment receipts disclose none of these answers. The leakage reduction of Fact 11 gives Pr[E]no leak ≥ 2−2ℓ Pr[E]leak for every event E, while preserving the prescribed causal order.

23

(10)

3.4

The transfer protocol

The window fixes one shared leakage budget. The block parameters must therefore pay for the public disclosures of the entire batch. Fix 0 < ρmin < 1/3 < ρmax < 1. The causal reduction and selector-aware repetition theorem supply a constant raw-entropy rate γrep > 0 per target block. Choose positive public-audit and code constants caud , cEC so that 2ρmax cEC + 6caud <

γrep , 2

(11)

and fix αpad > 0 below the resulting constant-rate entropy margin. The two left-hand terms charge, respectively, both syndromes and the opened answer bits on every allowed audit coordinate across all blocks. Use m, N, tA from Section 2.4. The general regime satisfies m = ω(log λ),

tA = ω(log λ) = o(m),

N/(m2 log N ) = ω(log λ).

(12)

At the isolated endpoint, only m = 1 and tA , N = ω(log λ) with tA = o(N ) are needed. In both regimes, put L = mN + tA , ctest = 3tA . (13) Here ctest counts the tested answer bits in the general selector proof; the isolated symmetry proof pays no such debit. Use δaud = caud /m,

rEC = cEC /m,

qdev + ν < min{κtest , κaud /2},

τEC = τEC (m, N ),

(14) ηaud , ν = Θ(τEC ).

κaud < ηaud < ρmin τEC ,

(15)

The inequalities have fixed multiplicative slack. Use radius (6), constants satisfying (11), and fixed κtest > 0 below the repetition-loss threshold. At m = 1 all rates are fixed positive constants. Superscript i restricts a table to block Ii , one of the m size-N blocks formed after the sparse test set is opened. In block i, Bob samples TBi ← Subδaud (Ii ) and forms Jbi := {j ∈ Ii \ TBi : Yj = b},

b ∈ {0, 1}.

(16)

After a symmetric size check he samples βi ←U {0, 1} and sets J i = Jβi i . Both masks are committed before Alice’s table; audit masks open first and selectors only after global audit acceptance. Hence βi = b

⇐⇒

J i = Jbi

⇐⇒

i

YJii = b|J | .

(17)

Put β = (β1 , . . . , βm ). Throughout, Synn is the public syndrome map and Extn (z; R) = ⟨z, R⟩. Inputs: Alice has (S0 , S1 ) ∈ {0, 1}2 ; Bob has D ∈ {0, 1}. Public L = mN + tA , δ∗ , δaud , ρmin , ρmax , κtest , κaud are as above. All record operations use ideal(CP); openings are certified projections. Trit arithmetic is coordinatewise modulo three. SyndDec⊤ n returns an error vector, or 0n on failure. No new device use occurs after Step 12. 1. Alice. Sample X in , Y A ←U {0, 1, 2}L and a uniform tA -subset TA ⊆ [L]. Commit to tA = 1TA as a length-L record. 2. Bob. Sample Y B ←U {0, 1, 2}L and commit to each trit YjB in its fixed two-bit encoding. 3. Alice. Send Y A . In the window shared with the next step, input every Xjin and record the 24

parity-correct row Ain j . 4. Bob. Set Y = Y A + Y B , input Y , and record the parity-correct columns B. After both complete answer batches have been collected, close the total-ℓ-qubit leakage window. Commit to every three-bit Bj . 5. Alice. Open tA , sample and send a fresh uniform ordering π of [L] \ TA . Its consecutive groups of N entries define I1 , . . . , Im . 6. Bob. Verify that opening, |TA | = tA and π. Independently include each j ∈ Ii in TBi with probability δaud , and put Jbi = {j ∈ Ii \ TBi : Yj = b}, b = 0, 1. Abort unless both sizes are in [ρmin N, ρmax N ]. Sample independent fair βi , set J i = Jβi i , and commit to tB,i = 1T i and B j i = 1J i as length-N records for all i. 7. Alice. Sample independent Cj ← Bern(1 − δ∗ ) for j ∈ [L]. Set (Xj , Aj ) = (Xjin , Ain j ) if Cj = 1 and (0, 000) otherwise; discard erased raw controller records. Commit to MA = enc((X i , Ai , C i )i∈[m] ) as one length-6mN record. 8. Bob. Open all tB,i and the YjB , Bj records for j ∈ TA . 9. Alice. Verify these openings, trit syntax, TBi ⊆ Ii and |TBi | ≤ 2δaud N . Set tst = 1 iff the checks pass and fewer than κtest tA test coordinates fail Cj = 0 or MS(Xj , YjA + YjB , Aj , Bj ) = 1. Send tst; globally abort on zero. Otherwise open (Xj , Aj , Cj ) on all TBi . 10. Bob. Verify all audit openings, valid trits and bits, active row parity, and (Xj , Aj ) = (0, 000) P on anchors. Require j∈T i Cj 1{Aj [Yj ] ̸= Bj [Xj ]} < κaud |TBi | in each nonempty audit; B empty audits pass this rate check. Set aud = 1 iff these checks and tst = 1 hold. Send aud; abort on zero, otherwise open all j i . 11. Alice. Require aud = 1. Verify the selector openings, J i ⊆ Ii \ TBi and |J i | ∈ [ρmin N, ρmax N ]. Send sel = 1 iff every check accepts; abort on zero. 12. Bob. Require sel = 1. Sample r ←U {0, 1}m \ {0m }, put e = ⟨r, β⟩, and send (r, χ) with χ = D ⊕ e. 13. Alice. Verify r ∈ {0, 1}m \ {0m } and χ ∈ {0, 1}. Set ∆ = S0 ⊕ S1 and sample Q ←U {q ∈ L {0, 1}m : i qi = Sχ }. For every i and b ∈ {0, 1}, put ni = |J i |, sample fresh independent Rib ←U {0, 1}ni and compute Zib = (Aj [b])j∈J i , Wib = Synni (Zib ), Pib = Qi ⊕ ri b∆,

Fib = Pib ⊕ Extni (Zib ; Rib ).

Open (Xj , Cj ) on all J i and send Mfin = ((Fi0 , Fi1 , Ri0 , Ri1 , Wi0 , Wi1 ))i∈[m] . Request Πpay = Check(MA ; Ppay , xpay ) for the exact public tuple, as in Definition 9. Bob performs the syntax checks of Step 14 before processing this request. 14. Bob. Before entering the proof, verify the prescribed tuple lengths, all prescribed openings, their trit and bit syntax, and Xj = 0 whenever Cj = 0. Require the successful Πpay certificate on Alice’s committed MA and this exact xpay ; globally abort on any rejection. For each ′ = 0 when C = 0 and R′ = B [X ] otherwise. Compute j ∈ J i , set Ri,j j j j i,j βi ′ Zbi = Ri′ ⊕ SyndDec⊤ ni Synni (Ri ) ⊕ Wi ,

Pbi = Fiβi ⊕ Extni (Zbi ; Riβi ).

Output OB = i Pbi and signal completion. Decoder failure causes no additional public flag or abort. A corrupt Bob may instead signal global abort after learning this bit, as allowed by Definition 7. L

25

15. Alice. Output ∅ on completion, or ⊥ on global abort. Where each step is used. Steps 1–2: Definition 6, causal cut Lemma 3. Steps 3–4: uniform questions and frozen record, Lemma 4. Steps 5–6: selectors (16), Lemma 1. Step 7: late erasures, Theorem 4; table cut, Definition 9. Steps 8–9: sparse test Claim 2, audit Claim 3. Steps 10–11: selector disclosure, Lemma 6. Step 12: choice masking, Corollary 8, exact at m = 1 by Lemma 5. Step 13: syndromes and payloads, Lemma 9, Lemma 8; correctness Claim 1. Step 14: PAY, Definition 9, Corollary 7, Lemma 10. Protocol 1: Unified DI OT: records, tests, audits, choice masking, payload proof, decoding, and delivery. Invalid syntax or failed required openings cause global abort. For reference, the protocol’s definitions give

M

Zib = AiJ i (b),

abi = Ext|J i | (Zib ; Rib ),

(18)

e = ⟨r, β⟩,

χ = D ⊕ e,

(19)

Qi = Sχ ,

(20)

i

Pib = Qi ⊕ ri b∆,

Fib = Pib ⊕ abi .

(21)

Here r = 1 at m = 1; otherwise, excluding the zero seed costs at most 2−m in the entropy comparison. L On completion, Bob outputs i Pbi . For honest parties on the good-decoding event, OB =

M

Piβi = Sχ ⊕ e∆ = SD .

(22)

i

Rejected prescribed checks cause global abort; decoder failure has only the totalized behavior specified in Step 14. Correctness and the three causal/sampling reductions used below are stated and proved in Section 3.6.

3.5

The theorem and its three properties

The main statement of this section follows; its three parts are proved in Section 3.6, in the order of the proof map after it. Theorem 6 (DI reduction from CP to OT). Under Theorem 4, the protocol POT of Protocol 1 satisfies ∀ admissible QPT P∗ ∃ QPT SimP∗ ∀ η R : RealP ideal(CP) ,P∗ (η R ) ≈c IdealOT,SimP∗ (η R ). OT

Security is computationally augmented and auxiliary-input-uniform (Definition 3), with one device batch of L = mN + tA coordinates and interface Definition 8. Either regime of Section 2.4 suffices. More generally, require the audit/correctness conditions and γrep N − 2ℓB − 2ρmax mrEC N − 6mδaud N − O(m log N ) ≥ αpad N. The selector alternatives are m = 1, ℓA = ℓB = 0, coordinate-local honest Bob; m − 2ℓA − 3tA − O(1) = ω(log λ), joint honest Bob; general scales. 26

(23)

Under (5), the isolated regime has L = Θ(log2 λ) and constant honest-fault tolerance; the general regime has tolerance Θ((m log N )−1 ) with fixed slack and permits adaptive bidirectional cross-block leakage. Errors are negligible uniformly over non-IID devices. Efficient sequential composition holds at the boundaries of Definition 4 and Theorem 5. The three properties were described in words in Section 1.3; the simulators are Protocol 2, and the proof below assembles the argument. Common rule: SIM runs the honest role of Protocol 1 and the ideal CP interfaces. It logs the corrupted party’s submitted classical records, preserving its quantum workspace and the untouched reference. Every public rejection is relayed asan ideal global abort before honest delivery. Corrupt Alice; SIM plays Bob. 1. SIM (records and tests). Run Bob’s physical questions, measurements, commitments, tests, and masks exactly as prescribed. Keep the actual Y, B, β until the pre-r decisions are fixed, and log Alice’s immutable tables (X i,∗ , Ai,∗ , C i,∗ ). 2. SIM (choice mask). After sel = 1, sample the prescribed nonzero r and independent uniform χ ∈ {0, 1}. Send (r, χ), verify all public projection claims, and process the owner-authorized Πpay request on the logged table. Do not append private Y, B, β to the compared output state. 3. SIM (ideal pair). On accepted messages and proof, set Pib,∗ = Fib ⊕ Ext|J i | (Ai,∗ (b); Rib ), Ji

u∗ =

M

Pi0,∗ .

i

Choose k with rk = 1 and put ∆∗ = Pk0,∗ ⊕ Pk1,∗ . Verify all syndrome and affine equalities in PAY; failure rejects the ideal predicate exactly. No witness is extracted from a proof transcript. Submit (u∗ ⊕ χ∆∗ , u∗ ⊕ (χ ⊕ 1)∆∗ ) to ideal OT. Retain Alice’s continuing state and the public transcript. Corrupt Bob; SIM plays Alice. 1. SIM (records and tests). Run Alice’s prescribed physical and classical actions. Log Bob’s submitted Y B,∗ , B ∗ and masks tB,i,∗ , j i,∗ . Verify every certified projection against these records. 2. SIM (ideal choice). After valid (r, χ), put J i = supp(j i,∗ ) and let Y ∗ be the effective question string defined before (2), with invalid encodings mapped to zero only for the simulation calculation. Let Hi minimize |{j ∈ J i : Yj∗ = b}| over b = 0, 1, breaking ties toward zero; set γi = 1 − Hi . Submit Deff = χ ⊕ ⟨r, γ⟩ to ideal OT and receive only SDeff . 3. SIM (payloads and delivery). Sample Q ←U {q ∈ {0, 1}m : i qi = SDeff } and set Pi0 = Pi1 = Qi . Form the genuine syndromes, seeds, openings, and pad-masked ciphertexts with these payloads. Authorize the genuine Πpay request; its predicate is true on the stored table with ∆∗ = 0. Deliver its certificate subject to Bob’s actual scheduling and abort decisions. Relay Bob’s final abort, or allow Alice’s empty output. L

Where each step is used. Corrupt Alice, Steps 1–3: Theorem 10, by Corollary 8 and Lemma 8. Corrupt Bob, Steps 4–6: Theorem 11, by Lemma 9 and Lemma 10. Protocol 2: QPT simulators for the OT protocol. The complete joint-state proofs are Lemma 8 and Theorems 10 and 11. Proof. The theorem has a correctness part and one simulation for each corruption. All three are proved below in the ideal CP execution; Figure 3 shows how the statements depend on one another. 27

Correctness is Claim 1. Corrupt Alice. The simulator is the first half of Protocol 2. First, in the real experiment, replace Bob’s output by the Dth component of the transcript-defined pair that the simulator submits. Except on the negligible bad-audit event, they agree on e = χ ⊕ D and Lemma 8: the audit (Claim 3) makes the decoder agree with Alice’s table, and the PAY certificate gives the affine form. Then replace χ = D ⊕ e by an independent uniform bit and apply the same transcript-to-output map. This is undetectable because e = ⟨r, β⟩ is uniform given Alice’s view (Corollary 8): exactly at the isolated endpoint, by Lemma 5, and otherwise by the label entropy of Lemma 6 and the parity hash. Theorem 10 combines the two hybrids. Corrupt Bob. The simulator is the second half of Protocol 2. The hybrids replace the m hidden ciphertexts with uniform bits, switch Alice’s payloads to equal branches for SDeff , and replace the ciphertexts back. Each replacement is Lemma 9, which rests on the sparse test (Claim 2), the causal cut (Lemmas 3 and 4), and the hidden-string lemma (Lemma 1). Lemma 10 extends the comparison through the PAY check. Theorem 11 combines these steps. Parameters and composition. Lemma 2 verifies that every error term is negligible and that (23) holds in both regimes. Sequential composition is Theorem 5 at the admissible boundaries. Part of Theorem 6 Correctness

Proved by Claim 1

Corrupt Alice: χ hides D Corrupt Alice: outputs agree Corrupt Bob: hidden pads Corrupt Bob: through PAY

Corollary 8

Which rests on Fact 6 and the code facts of Section A.3 Lemma 5 at m = 1; Lemma 6 and Fact 9 otherwise Claim 3, Lemma 7, Corollary 7

Lemma 8 Lemma 9

Claim 2, Lemmas 3 and 4, Lemma 1, Table 4 Definition 6

Lemma 10

Figure 3: Proof map of Section 3. A reader can check one row without the others; only the first Corrupt-Alice row depends on the regime.

3.6

Proof of the CP-to-OT reduction

For Theorem 6, we first establish correctness and the causal and sampling reductions. We then use selector entropy and affine reconstruction against Alice, and ordered hidden pads against Bob. 3.6.1

The CP operations of the protocol

Alice’s complete block table occupies one fixed-length record: MA = enc((X i , Ai , C i )i∈[m] ),

|MA | = 6mN.

(24)

Each coordinate has two question-encoding bits, three answer bits, and one erasure flag. Audits and later projections check trit syntax, parity, and canonical erasures at the steps specified in Protocol 1. In Protocol 1, Bob commits to his question, answer, and mask records in Steps 2, 4, and 6, respectively. 28

Roles: Alice owns M , Bob verifies; roles may be exchanged. Identifiers are implicit, and requests are owner-authorized. 1. Commitment. Alice commits to M at the prescribed length; Bob records the correctly routed metadata-only receipt. 2. Projection. Alice publishes (S, z) and requests [πS (M ) = z]. Bob checks indices, syntax, and the certificate; previously certified entries are reused, and overlaps must agree. 3. Payload. Alice requests Check(MA ; Ppay , xpay ) from Definition 9. Bob requires success for the same record, prescribed predicate, and exact public tuple. Where each step is used. Steps 1–3: Definition 6; realized by Theorem 12 and substituted into a call by Lemma 23; Step 3’s predicate is Definition 9. Protocol 3: Outer CP operations. Projection claims are public before certification, including on rejection. Corollary 7 (Certificates concern the same stored string). By Definition 6, success on a record storing M ∗ implies P (M ∗ , y) = 1 exactly. Thus certified projections and successful PAY checks concern that same record; PAY supplies one common bit for every block by its two-witness disjunction. 3.6.2

Correctness, the causal cut, and the sparse test

We begin with correctness, then establish the two facts on which both simulations rest: that CP commitments preserve the causal order of the game, and that the sparse test bounds the losses in every block. Claim 1 (Correctness of the OT protocol). Under (7), either regime of Section 2.4, and (15), ∀(S0 , S1 , D) ∈ {0, 1}3 :

Pr[(OA , OB ) ̸= (∅, SD )] ≤ negl(λ)

for honest parties, including the probability of global abort. Full proof of Claim 1. The test has tA = ω(log λ) independent honest coordinates and a fixed threshold, so by Fact 6 its rejection probability is exp[−Ω(tA )]. For each block, the candidate sizes concentrate around (1 − δaud )N/3. The selector window of Section 2.4 contains these expectations with constant slack for every m ≥ 1. Audit sizes concentrate around δaud N = Θ(N/m). Conditional on the sampled questions and sets, the honest-fault bound and multiplicative slack give audit and decoding errors at most exp[−Ω(δaud κaud N )] and exp[−Ω(τEC N )], respectively. Their union over all blocks is negligible by Lemma 2; at m = 1 the exponents are Ω(N ). The selected strings retain anchors, which contribute the known bit zero rather than a decoding error. Thus every selected raw string and payload is recovered correctly. The honestly committed tables satisfy PAY, so proof completeness adds only negligible rejection probability. Finally, M β Pi i = Sχ ⊕ ⟨r, β⟩(S0 ⊕ S1 ) = SD . i

For m = 1, this is the same calculation with r = 1 and P1t = Sχ⊕t . All later processing is trusted classical computation and introduces no further device faults. Lemma 3 (CP records preserve the causal cut). Before Alice commits to MA , Bob’s accepted commitment inputs immutably fix his question, answer, selector, and audit-mask values. His entire computation up to this cut is part of Dave’s early instrument in the restricted-order game. Later certified projections reveal those same values and never act on Alice’s device registers or the reference. 29

Proof. Log Bob’s actual classical commitment inputs and retain an inaccessible immutable copy for the game. The commitment step returns content-independent metadata. Its response is locally simulatable from Bob’s input syntax; it supplies no Alice-side source to Bob. No Alice-owned predicate is requested before the authorized disclosures. Bob’s values may be arbitrary correlated outcomes of his joint instrument; no honest sampling law is imposed. Subsequent certificates authenticate projections of the fixed records. Rejected commands are totalized with fixed defaults without conditioning on success. Fix a block index i and a no-extra-communication strategy obtained from a cheating-Bob leakage strategy by the transcript-guessing reduction of Fact 11, with the guessed leakage transcript hardwired. Retain a valid opening of TA and the fresh public permutation π as classical registers; honest Alice samples π after Bob’s complete answer record is immutable. Restrict the answer record and later questions to Ii , retaining every other coordinate and the untouched reference as auxiliary systems, and guess the later source-dependent messages as in Lemma 9. Lemma 4 (Causal restriction after transcript guessing). The resulting target-block strategy obeys the restricted-order causal interface of Theorem 4: its answer record and selector are fixed through CP inputs before the target block’s late (C, X) table information, while the selector’s public opening is delayed until after the audit. The statement concerns this hardwired zero-communication strategy, not the original leaked strategy. Proof. Let U be Bob’s effective committed masked-question string, mapping an invalid two-bit trit encoding to zero for analysis only, and let V = Y A . Its private sampling may be deferred until P after the record is fixed. Before sampling V , write ρU Q = u |u⟩⟨u| ⊗ ρQ u , where Q includes both laboratories, the original record, and R. Fresh uniform V gives ρY U Q = 3−L

X

UQ |v + u⟩⟨v + u| ⊗ |u⟩⟨u| ⊗ ρQ . u = τY ⊗ ρ

v,u

Together with independent X in this is the product question law. Dave recovers V = Y − U from his question and stored U and follows his original circuit; Alice’s physical instrument uses only X in . Actual projection and syntax checks still reject invalid encodings. On invalid-selector branches define a fixed legal selector and exclude that branch from the target event; do not condition the input law on selector validity. After the leakage transcript has been guessed and hardwired, there is no remaining device-window communication. The later audit-answer messages and the test flag are removed by the guessing step of Lemma 9. The complete device-output batch and Bob’s CP input for B precede Alice’s sampling of π. Conditional on the valid TA record, the ordering of its complement is exactly uniform and independent of Bob’s frozen answer record and continuing state. Revealing the partition can only relabel and restrict already frozen coordinates; it cannot create an operation depending on a target late question. For this reduction, sample the independent partition, all other-coordinate questions, and all other-coordinate erasure coins as shared randomness independent of the target questions. The target erasure coins remain fresh until after its selector is frozen. Each party follows its original circuit and ignores this extra knowledge until the prescribed use. Other-coordinate outputs and residual states are produced by those circuits; they are not included in the shared randomness. The other-coordinate registers remain on their original sides: Alice’s registers belong to Charlie, and Bob’s to Dave. They are not transferred to Dave as source-dependent initial advice. The repetition theorem allows this entangled auxiliary state; actual late disclosures are handled by the explicit guessing debits below. Fixing the independent partition preserves the prescribed 30

question law and causal order. All block selectors freeze before any Cj is sampled. Consequently the target erasure mask is independent of the entire early instrument, including all other blocks. Only canonical (C, X) values are freely supplied later; raw anchor questions stay on Alice’s side. After the partition, Bob’s CP inputs for (tB,i , j i ) jointly fix the audit mask and selector before Alice’s target-block table commitment; their later openings do not change the frozen values. The trusted erasure coins may equivalently be sampled privately before the raw device execution and left unused until the table turn. In the ideal CP execution, the canonical loss set is therefore a function of the raw records and independent erasure coins, independent of the hidden test mask. This rearrangement gives the next sampling argument; it never supplies the coins to either device. Claim 2 (Sparse global test certifies every random block). Against a cheating Bob, let (Y B,∗ , B ∗ ) be the immutable values in his global CP inputs, and use the effective-question convention before (2). Define the global loss set Lose := {j ∈ [L] : Cj = 1 and MS(Xj , Yj∗ , Aj , Bj∗ ) = 0}. There are constants κtest < η0 < η1 compatible with the selected-win threshold such that, except with probability exp(−Ω(tA )) + m exp(−Ω(N )) + negl(λ), global test acceptance and valid partition opening imply for every i ∈ [m].

|Lose ∩ Ii | ≤ η1 N

(25)

Proof. Work in the ideal CP execution. Before the projection of Alice’s test mask, its receipt exposes only its fixed length and label. All honest questions, device operations, and earlier controller messages are independent of that mask. Privately presample the unused erasure coins, so at Bob’s completed answer-commitment cut, the raw records, these coins, and his immutable inputs define the entire loss set. That set is independent of the honest uniform TA . By Fact 6 (hypergeometric case), a loss set of density above η0 passes the size-tA test with probability exp[−Ω(tA )]. Every certified Bob projection agrees with his stored record; a missing or invalid certificate only prevents acceptance. Outside this bad event, the complement loss density is at most η0 + o(1). The fresh uniform permutation gives a uniform partition of the complement. Fact 6 (hypergeometric case) and a union bound imply the per-block statement, with error m exp[−Ω(N )]. Intersecting with any subsequent acceptance or abort decisions cannot enlarge these bad-event probabilities. The extra negligible term in the statement may be taken as zero in this ideal CP argument; compilation is accounted for separately. Claim 3 (Block audits at either rate). For a cheating Alice, let BadiA contain invalid table syntax, noncanonical anchors, and active coordinates where A∗j [Yj ] ̸= Bj [Xj∗ ] in her immutable table. Except with negligible probability, audit acceptance in every block implies |BadiA | ≤ ηaud N

and hence

ηaud |BadiA ∩ J i | ≤ < τEC |J i | ρmin

∀i ∈ [m].

(26)

Proof. For analysis, defer Bob’s early candidate-size abort until after Alice commits to MA , retaining the original size flags privately and using a fixed continuation on already stopped branches. This extension agrees with every actually reached table cut. Before restricting to those flags, mask commitments expose only metadata, so the stored table, jointly with (Y, B), is independent of Bob’s Bernoulli audit masks. This is an exact statement in the ideal CP experiment. 31

Each audit has size Θ(N/m) except with probability exp[−Ω(N/m)] and, conditional on its size, is a uniform subset. For a fixed table with bad-set density above ηaud = Θ(τEC ), passing the syntax and mismatch checks has probability exp[−Ω(δaud ηaud N )] by Fact 6. Syntax-invalid sampled entries cause immediate rejection; otherwise bad entries are precisely the counted mismatches. The mismatch denominator is the entire audit size, as in the protocol. The exponent is Ω(N ) at m = 1 and Ω(N/(m2 log N )) otherwise. A block union bound is negligible. Every successful projection is from the same stored MA . Intersecting with the original reach flags gives the actual bound. The selector-size check gives the displayed distance bound. 3.6.3

Exact selector symmetry in the isolated one-block regime

This subsection is needed only for the isolated regime; a reader checking the general regime can skip it. The common protocol has a sharper analysis at its isolated one-block endpoint. This lemma is used both to change the BC mode and to mask the OT choice. It uses local no-signalling (Fact 1) and the classical commitment hybrids. Lemma 5 (Isolated one-block selector symmetry). Set m = 1 and ℓ = 0 and assume Definition 5. Consider either the BC experiment EB of Section 5.6.5, in which a corrupt Alice faces an honest Bob whose commitments are replaced by their equivocation simulation and whose mode proof is simulated, or the ideal CP OT experiment. In it, let V contain Alice’s entire pre-r state and public transcript, the untouched reference, and, for OT, the classical log of her submitted CP values. Exclude Bob’s private questions, answers, selector label, and inner-sender witnesses. On the accepted substate before r, apart from negligible inner failure events, ρbβV = U1 ⊗ ρbV .

(27)

The accepted substate includes the audit flag, the symmetric size checks, and Alice’s selective continuation. Consequently, the only nonzero seed r = 1 gives e = β exactly uniform in this hybrid. Proof. Step 1: the audit set can be sampled early. The test mask fixes TA before Bob’s fresh hidden questions. In BC, statistical binding fixes its unique possible value for analysis; in OT it is Alice’s immutable commitment input. Invalid openings only stop the protocol. The one-block permutation orders the complement of TA without changing its elements. An independent uniform physical audit set can therefore be sampled privately before the question commitments and mapped through the later permutation. For OT, the same statement holds for independent Bernoulli sampling. No audit information is disclosed earlier by this rearrangement. Step 2: the unused questions are uniform. Write S = TA ∪ TB and W = [L] \ S. In BC, the EB commitment phases do not use Bob’s question or answer values. His uniform physical questions may be sampled after Alice’s offset. In OT, CP receipts contain only metadata independent of the stored values. Retain the actual (YS , BS ) privately for this analysis. The test and audit projections and the committed mask records have their actual values. In both cases, unused masked questions on W remain uniform even if Alice chooses her offset adaptively from the preceding view. Step 3: Alice’s marginal depends on YS only. Apply Fact 1, retaining (YS , BS ) for analysis and summing over the private outcomes on W . Alice’s joint marginal, including any previous local processing and the reference, depends on Bob’s inputs only through YS . Arbitrary initial crosscoordinate entanglement is allowed. The remaining protocol messages before r use this marginal, Alice’s operations, the test and audit data, and the selected incidence mask; they do not use an unrecorded outcome on W .

32

Step 4: label exchange. Exchange labels 0 and 1 in YW and flip β. The uniform question law is invariant, and Jβ (YW ) = J1−β (swap0,1 (YW )). The physical audit set, its questions and outcomes, the test record, and both candidate-size checks are unchanged. Couple the selector-record operations and all other controller coins on the two sides. Alice then receives the same selector receipt, test and audit interaction, global audit bit, and selector opening. Her table inputs, later local operations, and decision to continue have the same joint law. The argument also covers the earlier symmetric size stop in OT; it is invariant under the same exchange. Step 5: conclusion. The two label branches are thus equal as subnormalized states, including their acceptance weight. This proves (27). The actual test and audit registers were retained under the symmetry, so neither is charged. The OT statement includes the commitment-input log because Alice’s same local channel produces it on both sides. Locality is essential to this argument. With an arbitrary joint honest-Bob instrument, a disclosed tested outcome may depend on questions outside the test. Zero physical leakage alone, therefore does not justify (27); that architecture uses the entropy-based parameter line of (5), even when ℓ = 0. 3.6.4

Leakage from Bob’s laboratory: entropy after the selectors

All statements in this section first concern the ideal(CP) execution. Concrete CP transcripts are substituted only after the outer OT simulation has been proved. Commitment receipts disclose only metadata. Against a cheating Alice, totalize the analysis as follows. At her test-mask commitment cut, fix her mask if its syntax and weight are valid; otherwise use a fixed size-tA mask. A later invalid projection retains that same analysis mask and its actual rejection flag. Use her partition when valid and a fixed partition of that complement otherwise. Irrespective of earlier flags, sample all audit masks and independent fair labels βi , and commit to J i = Jβi i on the same metadata-only schedule. Keep Bob’s size flags private until Alice’s table is fixed. Complete the test, audit, and selector steps, retaining only their prescribed global public decisions and flags determined by Alice’s submitted values and public messages; do not append Bob’s private per-block outcomes. Let VeApost-J contain Alice’s complete post-selector state, public requests and certificates, her append-only commitment-input log, and untouched R. It excludes Bob’s private questions, answers, labels, audit outcomes, and the private contents of his ideal records. Bob’s per-block private flags are not added. The tilde denotes the totalized post-selector analysis state. Its restriction to actual valid pre-r continuation is VbApre-r ; the two agree there exactly. There is no copy of a resumed quantum state. Aborts in the implemented protocol remain absorbing. Lemma 6 (Leakage-robust post-selector entropy). For the totalized ideal CP experiment just defined, at most ℓA leakage qubits imply pguess (β | VeApost-J ) ≤ 22ℓA +ctest +1−m .

(28)

For a classical event E of probability p > 0, normalized conditioning consequently gives Hmin (β | VeApost-J , E) ≥ m − 2ℓA − ctest − log(1/p) − O(1). Both bounds are uniform over the admissible entangled states. 33

(29)

Proof. We bound the probability that Alice guesses the label vector β from her complete view after the selectors are opened. Alice sees which coordinates form each selector but not which of the two question classes it is, and the two classes are exchangeable, so without side information each βi is a fair coin. Her side information about Bob’s questions has two sources: the leakage, and the tested answers that Bob publishes, which come from a joint measurement. Step 1 removes both by guessing, Step 2 shows that the remaining questions are then uniform given her view, and Step 3 exchanges the labels and undoes the guesses. Step 1: remove the leakage and guess the tested answers. We eliminate the device-window communication using Fact 11, which costs a factor 22ℓA in the probability of any guessing event. All further reductions stay inside this fixed statistical experiment. Ideal receipts transmit no outcome of Bob, and no answer-dependent commitment string precedes the first disclosure of his answers, which is the release of the 3tA tested answer bits in Step 8. At that point we replace them by an independent uniform guess g and retain the actual outcomes privately. The guessed continuation agrees with the real one on the event g = BTA , which has pointwise weight 2−3tA . On the other branches we use the totalized transcript channels; this is a reduction between probabilities and not a claim that the functionality accepts a false projection. Step 2: the untested questions are uniform given Alice’s view. In the resulting experiment there is no communication and all of Bob’s actual outcomes stay private, so whole-laboratory no-signalling (Fact 1) makes Alice’s state, jointly with R, independent of Bob’s undisclosed uniform questions. The questions on the test set may be given to her at the start: conditional on them and on the already fixed test set, the remaining questions stay uniform. Alice’s permutation, which may be malicious, is chosen before the tested answers are released and depends only on her preceding state and the allowed public data. The guessed continuation may depend on g but not on any actual undisclosed outcome. Step 3: label symmetry, then undo the guesses. We condition on the preceding record, on (TA , π, TB ), and on the guessed message. On Ii \ TBi we exchange the question labels 0 and 1 and flip βi . This map preserves the law of the questions, the selected incidence mask, and the symmetric two-candidate size flag; commitment receipts and certified mask values are unchanged. Since the labels are independent fair coins, before Bob’s single global audit bit, we have (0)

(0)

ρeβJTB VA = Um ⊗ ρeJTB VA .

(30)

Alice’s committed table, projection claims, and other messages are channels of her preceding state, so including her input log preserves this identity. Appending Bob’s audit bit costs at most a factor of two in guessing probability, and her remaining decisions and the certified selector release are channels of the same view. Hence in this experiment guessing succeeds with probability at most 21−m . Undoing the two guesses multiplies this by 23tA and 22ℓA , which is the first inequality. The ordinary rule for normalized conditioning gives the second. In the simulation below we instead restrict to accepted substates without normalizing. Corollary 8 (The extracted choice mask is uniform). Let Accpre-r collect the valid test-mask projection and partition, both candidate-size checks, audit and selector projections, tst = aud = sel = 1, and all other prescribed continuation checks before r. In the general regime, assume ksel := m − 2ℓA − ctest − 1 = ω(log λ).

(31)

Alternatively, use the isolated one-block conditions of Lemma 5. On the accepted subnormalized ideal CP state, the fresh nonzero seed obeys (r, ⟨r, β⟩, VbApre-r ) ≈negl(λ) (r, U1 , VbApre-r ). 34

(32)

At the isolated endpoint, the equality is exact. Hence χ = D ⊕ ⟨r, β⟩ hides D in this hybrid. Every subsequent public check is a channel of the complete Alice view, including her stored-table input log, and the public (r, χ): the PAY certificate evaluates that logged table and the received tuple. Proof. At m = 1, use the exact symmetry lemma with r = 1. In the general regime, restrict the positive totalized state to Accpre-r without normalizing. Its absolute guessing probability cannot increase, so its min-entropy is at least k√ sel . The event is fixed before the fresh seed. Fact 9 gives 1 absolute trace-distance error at most 2 21−ksel ; conditioning the seed on nonzero adds at most 2−m . XOR with D and the same efficient continuation preserve this bound. Actual abort branches are retained unchanged. The statement conditions on J: the balanced symmetry was proved given J, so opening J is not charged. Leakage need not reveal coordinate projections of Y ; it may be an arbitrary interactive quantum function of the entire device execution. 3.6.5

Receiver simulation from the classical transcript

The entropy bound hides Bob’s choice. Full simulation also needs sender inputs whose selected value has Bob’s joint output distribution. For a cheating Alice, log her single table-commitment input MA and its block projections. They supply one immutable classical record τcl∗ := (Y i , B i , βi , X i,∗ , Ai,∗ , C i,∗ , J i )i∈[m] , r, χ, Mfin , Trpay ,

(33)

where Mfin contains both branch ciphertexts, both syndromes, all seeds, and the accepted openings in every block, and Trpay is the public predicate request and its certificate or rejection, including any withholding decision. The following reconstruction uses the same immutable committed table. Lemma 7 (Blockwise transcript reconstruction). Except on an event of negligible joint probability with Accpre-r , arising from the bad-audit event, Bob’s post-r global-abort/output record is the efficient deterministic classical function OB = G(τcl∗ ) (34) as follows: G returns the global abort symbol on a complete-message syntax, projection-certificate, or proof rejection, while on certification success Corollary 7 makes the same record determine all 2m counterfactual values Pib,∗ . The map does not measure or otherwise access Alice’s residual quantum register. Proof. If the public syntax, a certified projection, or Πpay rejects, the transcript itself fixes Bob’s output as one global abort. Otherwise, the ideal PAY certificate implies, exactly for the block projections of the same immutable MA , Wib = Syn|J i | (Ai,∗ (b)) Ji

(i ∈ [m], b ∈ {0, 1}).

Define every counterfactual value directly by Pib,∗ := Fib ⊕ Ext|J i | (Ai,∗ (b); Rib ). Ji For the actual branch b = βi , the good-audit bound (26) places Bob’s reconstruction word inside the unique-decoding radius of Ai,∗ (βi ). The displayed syndrome equality therefore makes his totalized Ji decoder return the correct error, and hence precisely that word, so his computed Pbi is Piβi ,∗ . XORing these actual-branch values gives G(τcl∗ ). Counterfactual values are read directly from the same classical record and do not require applying the decoder to a branch whose selector was not sent. 35

Put e = ⟨r, β⟩. The consistency proof removes every dependence of Bob’s accepted output on the full vector β beyond this one bit. The independent-mask experiment. Fix a cheating Alice. In the independent-mask experiment, χ is sampled uniformly and independently after all pre-r decisions are fixed on continuing branches. Let V ∗ contain the public transcript, Alice’s immutable CP input log, and every validity, continuation, and rejection flag determined by these data and her messages. It contains neither Bob’s private Y, B, β, e nor any register from which β can be reconstructed; Alice’s residual quantum state and the reference are untouched, and Bob’s private work registers are omitted after the pre-r L cut. Unlike the analytical record τcl∗ , this is the record exposed in simulation. Let Pib,∗ , u∗ = i Pi0,∗ , and ∆∗ be the bits that the simulator of Protocol 2 computes from Alice’s logged table. Let AbSim (V ∗ ) be the single global rejection flag collecting every pre-r test, audit, selectoropening, and continuation check together with the later complete-message, projection-certificate, and proof checks. If it is one, the simulator invokes the global abort command before honest-party delivery. Otherwise it submits to ideal(OT) the pair SdSim (V ∗ ) := u∗ ⊕ (χ ⊕ d)∆∗ ,

d ∈ {0, 1}.

(35)

For comparison, write OdSim =⊥ when AbSim = 1 and OdSim = SdSim (V ∗ ) otherwise; here ⊥ records the global ideal abort. Let VAind denote the complete Alice/public/reference view in this experiment, augmented by the simulator’s append-only CP input log, and let VAD=d denote the analogously augmented view in the real execution with choice d. Lemma 8 (Accepted affine payloads and the simulated input pair). In the independent-mask experiment, on good-audit, accepting branches and except with negligible probability, Pi0,∗ ⊕ Pi1,∗ = ri ∆∗

∀i,

OB = u∗ ⊕ e∆∗ ,

(36)

and ∆∗ is unique since r ̸= 0m . Under either hypothesis of Corollary 8, for each d, B , VAind , OdSim ≈c VAD=d , OD=d

(37)

including the public transcript, abort symbol, and untouched reference register. Proof. Goal and plan. The lemma has two parts. The first is algebra: once PAY succeeds, and the audit was good, Bob’s output is the affine function u∗ ⊕ e∆∗ of his private parity e = ⟨r, β⟩, with u∗ and ∆∗ readable from Alice’s committed table. The second is the comparison of the two experiments: since e is uniform given everything Alice sees, a real execution with choice d looks to her like the independent-mask experiment, and in it Bob’s output equals the dth component of the pair that the simulator submits. Step 1: the affine identity. Success of the PAY predicate gives (8) for the same immutable record MA , and for its m block projections used by Lemma 7. Its syndrome equalities, together with the good audit, make Bob’s decoded selected word equal to Ziβi ,∗ except with negligible probability. Hence Piβi ,∗ = Pi0,∗ ⊕ βi (Pi0,∗ ⊕ Pi1,∗ ) = Pi0,∗ ⊕ βi ri ∆∗ , and the XOR over the blocks is (36). The simulator computes these quantities efficiently: it finds a coordinate with ri = 1, reads ∆∗ = Pi0,∗ ⊕ Pi1,∗ there, and verifies the remaining equalities. On an accepting branch, Corollary 7 makes the equalities hold exactly, so the only error in this step is the decoder agreement on the good-audit event. 36

Step 2: the independent mask is indistinguishable from the real one. By Corollary 8, in the ideal CP execution e is negligibly close to uniform jointly with Alice’s view after the selectors, her committed-table input log, and the public seed. In the real execution χ = D ⊕ e, so χ is then negligibly close to a uniform bit independent of that view, as in the independent-mask experiment. Everything that follows, namely the corrupt Alice’s continuation, the certified projections, and the PAY check, is one efficient channel applied to that view and the public (r, χ): the table that the check uses is already in the simulator’s log, and the channel never receives e, D, or β. Data processing therefore carries the closeness through to the end of the execution. Step 3: the outputs agree. In the real execution with D = d we have e = χ ⊕ d, and substituting B this into (36) gives OD=d = u∗ ⊕ (χ ⊕ d)∆∗ = SdSim (V ∗ ). Step 4: the aborts agree. Every rejection before r is sent is generated before any protocol message uses D, so it is exactly independent of D. Every syntax or proof rejection after r is a function of the continuation of Step 2 and of its certificate result. Decoder disagreement on the good-audit event was already charged in Step 1. This proves (37). Corollary 9 (Receiver-view privacy in both parameter regimes). Under either alternative of Corollary 8, the complete view of a cheating Alice with leakage budget ℓA hides D. The isolated m = 1 case requires coordinate-local honest Bob; the general case allows joint instruments and pays the test-answer and audit-bit debits of (31). Proof. Apply the selector-hash replacement, the same authorized continuation, and stateful CP substitution (Lemma 23). Theorem 10 (Receiver simulation in both parameter regimes). Assume either selector-privacy alternative of Corollary 8, together with the common parameter schedule and (15). Then the blockwise protocol is computationally augmented-secure against a cheating Alice communicating at most ℓA leakage qubits. The simulator is strict QPT and uniform over all admissible auxiliary inputs. Proof. Run the independent-mask experiment and obtain V ∗ and AbSim . If AbSim = 1, invoke the one global abort command before honest-party delivery. Otherwise compute u∗ , ∆∗ from the m block projections of the same immutable record MA and Mfin , form the two values of (35), and submit their pair to ideal OT. For ideal choice d, Lemma 8 identifies the selected value with Bob’s real output and simultaneously identifies Alice’s complete view; Claim 3 makes the excluded bad-audit branch negligible. Strict running time, auxiliary-input uniformity, and preservation of the reference follow from Corollary 7 and the entirely classical computation of u∗ , ∆∗ without acting on Alice’s residual register or the live reference. From the game to the protocols. Table 4 lists, for a target block, how Protocol 4 and Protocol 1 instantiate the game of Theorem 4, and what a corrupt receiver obtains beyond the game. The two protocols share their step numbers up to Step 13. Each additional disclosure is guessed at its first appearance, at the stated cost in bits (Fact 7); the hidden-pad budgets (49) and (38) equal the raw entropy γN of Lemma 1 minus the sum of the last column. The sparse test bounds the weight of the complement of Good; that substate is deleted before any guessing step, at purified-distance cost at most the square root of twice its weight (Fact 7). For OT the whole argument takes place in the ideal CP experiment; for BC it takes place after Alice’s commitments have been replaced by equivocal ones.

37

Table 4: The late-erasure game against the protocols, for one target block. Above the rule: the actions of the game. Below it: everything a corrupt receiver obtains beyond the game, with its charge in bits against the raw entropy γN . Game Charlie receives X in and returns Ain Dave receives uniform Y

Dave freezes (B, J) The verifier samples C b Dave receives X

b 1] Dave outputs A[0,

— —

—

— — — — —

3.6.6

BC and OT protocols Step 3: Alice inputs Xjin on every coordinate and records Ain j Step 4: the effective question Y ∗ is Bob’s fixed offset plus Alice’s fresh offset, hence uniform (Lemma 4) Steps 4 and 6: Bob’s committed answers and selector mask; the scored selector is K of (3) Step 7: Alice samples C after both records are frozen Step 13: (Xj , Cj ) opened on J; active questions elsewhere in the block are also permitted late input A guess of ZH together with the frozen Bj [Xj ] (Lemma 1) Device-window communication of at most ℓ qubits Step 5: the hidden test set is revealed, and a fresh partition is sampled after B is frozen; both are independent of the target questions Step 7: Alice’s table commitment (equivocal in the BC hybrid) or metadata-only CP receipt Step 9: the flag tst Step 9: audit openings in all m blocks; (X, C) is permitted late input, the answers are not Step 13: both syndromes in all blocks Step 13: the other seeds (independent) and the other 2m − 1 ciphertext bits The reference R and all other-coordinate registers, as auxiliary entanglement on their original sides

Charge — —

— — 0

— 2ℓ (Fact 11) 0

0

1 3mnaud in BC; 6mδaud N in OT 2ρmax mrEC N + O(m log N ) O(m) 0

Leakage to a cheating Bob: ordered hidden pads

It remains to simulate a corrupt Bob. We need a hidden pad in each block after charging the disclosures of the entire batch. For each block, apply the transcript-defined rule (2) to obtain a hidden branch Hi and put γi = 1 − Hi . For honest Bob, γi = βi . Against a cheating Bob, Hi and γi are deterministic functions of his immutable CP record and the public transcript before the fresh local extractor seed is chosen. Let Accpad collect every public check through Alice’s validation of Bob’s (r, χ), immediately before Alice samples the local extractor seeds and sends Mfin . This event is fixed before every transfer 38

ciphertext; in particular, it includes valid audit- and selector-mask openings, tst = aud = sel = 1, and selector disjointness. We use its subnormalized branch in the ideal CP experiment. Abort branches are reproduced identically. Use the constants fixed in (11). The two terms charge, respectively, both syndromes and at most three opened answer bits on at most 2δaud N audited coordinates in each of all m blocks. The canonical pair (C, X) is the allowed erased late question; it supplies no raw question on an anchor. Lemma 9 (Ordered hidden-pad extraction). Execute all m blocks in parallel and allow at most ℓB communicated leakage qubits. Define kpad := γrep N − 2ℓB − 2ρmax mrEC N − 6mδaud N − O(m log N ),

(38)

kpad ≥ αpad N.

(39)

and suppose Use the fixed transfer order 1, . . . , m of Protocol 1. Immediately before block j’s fresh seed is applied H in the proof hybrid, the hidden raw string Zj j has smooth conditional min-entropy at least kpad on the accepted subnormalized state, given Bob’s complete state, the reference R, all syndromes and answer-table audit openings, all other extractor seeds and ciphertext bits, and the preceding public transcript. Consequently, PreProof orig ≈negl(λ) PreProof F H1 ,...,F Hm ←U , 1

m

1

(40)

where PreProof retains Bob’s complete state, the public transcript, sender-input labels, and R immediately after Mfin and before Πpay , and the right-hand experiment replaces the indicated ciphertexts by independent uniform bits on Accpad . The compared state excludes Alice’s private raw strings and the undisclosed contents of her record; exposing them would invalidate pad uniformity. The replacements are made only on the branch Accpad , which is fixed before Mfin , and the statement stops before the PAY request: intermediate ciphertext hybrids are analysis states, and Lemma 10 extends the comparison between the two predicate-valid endpoints. Proof. Goal and plan. Fix a target block j. We must show that, given everything a corrupt Bob H H holds just before the seed Rj j is applied, the string Zj j has smooth min-entropy at least kpad . H

H

Leftover hashing then makes the pad Ext(Zj j ; Rj j ) uniform, and replacing the m hidden ciphertexts one at a time gives (40). The entropy comes from the repetition bound (Lemma 1), which gives γrep N bits against a Bob who sees only what Dave sees in the game. Steps 1–4 account for everything else that Bob sees, in the order of Table 4, and Step 5 hashes. Step 1: what Alice’s record releases. We work in the ideal CP execution, so that Alice’s committed table reaches Bob only through the functionality. Her commitment receipts contain no source-dependent strings. Before the final PAY request, the only releases from her table are the prescribed certified projections, and Bob cannot request any further predicate or projection from that honest-owned record. Hence Bob’s information about Alice’s answers consists of his own device state, the leakage, and the disclosures charged below. Step 2: the raw entropy of the target block. The repetition bound applies to the event that the block has few Magic Square losses, so we first restrict to it. By Claim 2, the joint weight of Accpad and a failed global or block loss bound is δblk = negl(λ). We √ delete this bad substate in the original ideal CP experiment, at purified-distance cost at most 2δblk (Fact 7), and we do so 39

before any guessing factor is applied, so that the cost is not multiplied. On the remaining substate, H consider any event in which Bob guesses Zj j . We remove the device-window leakage (Fact 11) and apply Lemmas 1 and 4 to the target block. This is legitimate because its frozen answer and selector records are unchanged, and the quantum systems of the other coordinates remain on their original sides, as auxiliary entanglement. The reference R must appear in the conditioning. For this information-theoretic bound only, we therefore grant R to Dave at the start: his early circuit acts as idR , his final guessing map may use it, and the repetition theorem permits such an entangled auxiliary state. The actual protocol and simulator never act on R. This gives the term γrep N on the good substate. Step 3: the leakage, the audit answers, and the test flag. Bob also holds the leakage transcript, Alice’s audit openings, and her bit tst. We guess each at its first appearance: the audit answers at their first public projection, in Step 9, since Step 7 reveals only fixed commitment metadata, and tst in Step 9 as well. On a correct guess, the guessed transcript agrees with the actual one, so the min-entropy drops by at most the number of guessed bits (Fact 7); the guess is a device of the analysis and not an operation available to a real receiver. The total charge is 2ℓB + 6mδaud N + 1 bits. The opened pair (C, X) costs nothing: it is the late-erasure input that the game allows, and it never reveals a raw question at an erased coordinate. Step 4: the syndromes and the other ciphertexts. The two syndromes of all blocks cost at most 2ρmax mrEC N + O(m log N ) bits. Alice’s shares are, conditional on the public χ and the fixed sender inputs, fresh randomness independent of the source, so we append them as private analysis registers at no cost. For the target ciphertext we also append all other seeds and the other 2m − 1 ciphertext bits, at cost O(m): ciphertexts that were already replaced are fresh uniform bits, and the remaining ones use their own independent seeds. Because the transcript-defined Hj is fixed before these seeds are sampled, the target seed stays fresh given its public length, the other ciphertexts, and the target share. Anything that Bob computes from his existing state is covered by data processing. Step 5: hashing and iterating over the blocks. Subtracting the charges of Steps 3 and 4 from γrep N gives (38), which is at least αpad N by (39). We apply Fact 8 with the fresh target seed, at constant entropy rate αpad /ρmax since |J j | ≤ ρmax N , and XOR the extracted pad with its share; H the hidden ciphertext Fj j becomes uniform. Iterating in the fixed block order gives (40), with only a polynomial factor on the negligible smoothing and hashing errors. Aborts before the transfer cut are identical in the two experiments. Let γ = (γ1 , . . . , γm ). In an honest encoding, M

Piγi = Sχ ⊕ ⟨r, γ⟩∆ = SDeff ,

Deff := χ ⊕ ⟨r, γ⟩.

(41)

i

Conditioned on SDeff , the vector (Piγi )i∈[m] is uniform subject to its displayed XOR. The simulator L therefore obtains only SDeff from ideal OT, samples bits Q1 , . . . , Qm uniformly subject to i Qi = SDeff , and sets Pi0 = Pi1 = Qi ∀i. (42) It forms both ciphertexts with the genuine local pads. The resulting zero-difference record satisfies the PAY predicate via ∆∗ = 0. The known-branch shares have exactly the required conditional distribution, and the ordered hidden-pad hybrid makes the two choices of hidden-branch ciphertexts indistinguishable. It never requests the other sender bit and never needs the real ∆ = S0 ⊕ S1 . Lemma 10 (Success continuation at the PAY endpoints). Fix an honest Alice and the outer CP schedule. Both her genuine payload encoding and the zero-difference encoding of (42) satisfy Ppay (MA , xpay ) = 1 for their actual stored MA . A statistical comparison of their pre-PAY receiver 40

views therefore extends to their complete receiver/abort views by the same efficient continuation channel. Intermediate ciphertext hybrids need not satisfy the predicate and are not submitted to the ideal functionality. Proof. Genuine payloads satisfy the predicate with ∆ = S0 ⊕ S1 ; equal branch payloads satisfy it with zero. Both endpoints have the same genuine syndrome rule and prescribed projections. In either endpoint, unless Bob causes failure or abort, the only further honest-record output is the success certificate for the public (MA -identifier, Ppay , xpay ). Its value is one, independent of the hidden table beyond that already valid assertion. No later honest projection or other predicate is authorized. A common channel on the receiver view can therefore append this certificate, run Bob’s actual continuation and scheduling choices, and reproduce his failure, abort, or completion decision. It does not read the hidden record. Contractivity extends the endpoint comparison through this channel. The concrete CP proof transcripts are supplied later by their own stateful simulation theorem, including any verifier-induced abort. Theorem 11 (Sender security with arbitrary bounded leakage). Using the selector-aware restrictedorder repetition theorem of Theorem 4 and the parameter condition (38)–(39), the blockwise protocol is computationally augmented-secure against every QPT cheating Bob allowed by Definition 8. Its QPT simulator submits the effective choice (41) and receives only the corresponding sender bit. Proof. Log Bob’s immutable commitment inputs. On the transfer branch, use Lemma 9 to replace the hidden ciphertexts one by one by independent uniform bits in the pre-PAY receiver view. For the actual pre-transfer γ, the genuine visible-branch payload vector is uniform subject to XOR SDeff . The zero-difference vector has exactly this same law. Replacing the hidden ciphertexts thus yields identical middle receiver states, jointly with Bob’s genuine residual side information, allowed public data, and the reference, but not the private contents of Alice’s record; then reverse the hidden-pad argument for the zero-difference encoding. Both resulting endpoints use the actual committed table and satisfy PAY. By Lemma 10, append their same successful certificate and Bob’s full subsequent channel without evaluating a false intermediate predicate. The simulator requests only SDeff , computes the valid zero-difference payloads, and relays Bob’s final abort before honest sender delivery. All pre-transfer abort branches are identical; all errors are absolute substate errors at every acceptance probability. The resulting CP-hybrid OT simulator is strict QPT and preserves the untouched reference. Lemma 23 then gives the concrete implementation’s computational simulation. 3.6.7

Scope of the leakage theorem and its rate limitation

The leakage in Theorem 6 may be arbitrary, adaptive, bidirectional, and correlated across blocks; it need not be a coordinate projection of Y , and its locations need not be known. No coordinate-local honest-Bob measurement is assumed. The same protocol uses this general parameter regime even at zero leakage when no locality condition is imposed. With coordinate-local honest Bob and zero leakage, the exact symmetry lemma instead permits one block and constant honest-fault tolerance. These alternatives are explicit in Section 2.4. The test debit ctest = 3tA is exactly the released global-test answer string; CP/ZK calls have no physical leakage interface. The general proof’s rate limitation is that the receiver-privacy source contains only one selector bit per block. Thus the present black-box wrapper tolerates total communication below roughly half the number of blocks, not a constant rate against all mN Magic Square coordinates.

41

4

Commit-and-prove from extractable bit commitment via a classical reduction

The OT protocol of Section 3 assumes ideal CP. This section realizes CP from qOWFs and a bit commitment that satisfies the contract below; Section 5 realizes that contract device-independently. All operations are classical outside the source BC calls.

4.1

The underlying commitment

We construct CP from a commitment scheme satisfying the following security properties. Definition 10 (BC with efficient committer-side simulation). A correct BC resource satisfies the source contract if, in either role assignment and uniformly over admissible auxiliary/reference states, it has: (i) Committer simulation. For every QPT committer C∗ , one QPT simulator extracts b∗ ∈ {0, 1, ⊥} at the end of the commit phase, with ABR ρABR real ≈c ρsim .

Here A is the committer’s entire workspace, B contains all registers retained by the honest receiver for this session, including its transcript and opening-verification state, and R is the untouched reference. The simulator’s private output b∗ is omitted from this comparison. For every subsequent QPT opening strategy, the simulated execution satisfies Pr [open accepts b ̸= b∗ ] ≤ negl(λ),

sim

where b∗ = ⊥ makes every accepted bit an error. (ii) Receiver hiding. For every QPT receiver V∗ , ViewV∗ R (commit(0)) ≈c ViewV∗ R (commit(1)) while the honest record is unopened. (iii) Sequential phases. Items (i)–(ii) hold in the model of Definition 3 for polynomially many labeled sessions in either role, with sequential commit phases, delayed openings, and QPT continuations. During each source-BC simulation, all other pending honest session states belong to the untouched reference.

4.2

The compiler

Given a commitment meeting the contract, the compiler realizes CP by a challenge-first version of the three-coloring argument. Theorem 12 (Classical BC-to-CP compiler, adapted from the coloring argument of [GMW91]). Assume that post-quantum one-way functions exist, and let ΠBC be a bit-commitment protocol satisfying Definition 10. We construct a polynomial-time protocol ΠCP that uses polynomially many calls to ΠBC and otherwise only classical computation and communication. The protocol realizes ideal(CP) of Definition 6 against malicious corruption of either party, in the real/ideal model of Definition 3. Security holds for polynomially many sequential commitment and predicate phases, with adaptively chosen requests.

42

We therefore use ideal CP records in the OT construction. Corollary 13 substitutes this compiler, and Theorem 23 instantiates every source BC call. The physical interface of the outer device window is Definition 8. The proof of Theorem 12 is a challenge-first version of the three-coloring argument and is standard in structure; it is given in Section C. The one point specific to this paper is the committed challenge: it lets the simulator obtain the verifier’s edge by source-BC extraction, so that no rewound segment contains a call of the source commitment and hence no device call.

4.3

OT from the compiled commitment interface

Substituting the compiler into the CP-hybrid protocol gives OT from a commitment satisfying Definition 10. Corollary 13 (OT from the compiled commitment interface). Under the assumptions of Theorem 12 and either parameter regime of Theorem 6, substituting the compiler gives the corresponding OT protocol with efficient simulation and sequential composability under Definition 4 and Theorem 5. All compiler operations occur outside the outer device-leakage window. The compiler’s classical routines process the prescribed caller-supplied classical records and act as the identity on the outer device registers and on the reference. Source BC calls use separate batches under Definition 13. The outer Magic-Square coordinate counts and honest-fault tolerances are unchanged; underlying BC calls and total overhead are polynomial. Proof. Apply Lemma 23 jointly to all CP phases within one OT call, retaining the complete corrupted state, honest outer input/output, allowed transcript, outer device registers, and reference. This simulation preserves each record across delayed requests and intervening opposite-role records, including public requests on rejection and the prescribed delivery and abort behavior. Apply Theorem 6 in the resulting ideal-CP experiment and add the negligible computational error. Finally, Theorem 5 composes completed OT calls under Definition 4; pending commitments within a call are covered by the stateful CP simulation.

5

Device-independent bit commitment from qOWFs

The compiler of Section 4 assumed a commitment satisfying Definition 10. This section constructs it with untrusted devices and contains the whole commitment construction: the two security notions, the three steps, their theorems, and coin tossing as an application. Alice is the committer and Bob the receiver. Each session permits one opening attempt; acceptance or rejection closes it. Honest applications access saved verification state only through this operation. The parameters are those of Section 2.4, and the entropy input is Theorem 4. The construction has the three steps of Bartusek, Coladangelo, Khurana, and Ma [BCKM21], with their middle step replaced. Step 1 applies their equivocality compiler to Naor’s commitment and gives a post-quantum equivocal commitment (Section 5.2). Step 2 turns it into an extractable commitment: where [BCKM21] uses trusted BB84 states and quantum communication, we use untrusted Magic Square devices and classical communication (Section 5.3). Step 3 applies the equivocality compiler again to the extractable commitment, and gives simulators for both parties (Section 5.4).

43

5.1

Security notions

The commitment must meet the source contract of Definition 10, which the compiler of Section 4 requires: committer simulation, receiver hiding, and continuations. Step 3 meets a stronger notion, which adds a simulator against a corrupt receiver. Definition 11 (BC with simulation for both parties). A correct BC resource is simulation-secure for both parties if it satisfies items (i) and (iii) of Definition 10 and, under the same continuations: (ii′ ) Receiver simulation. For every QPT receiver V∗ there is a QPT simulator (Simcom , Simopen ). Simcom runs the commit phase with V∗ without the bit b; after the commit phase, Simopen receives b and runs the opening. For each b ∈ {0, 1}, the final state of V∗ , jointly with R, is computationally indistinguishable from its state after an honest commitment to b and an honest opening. The simulator accesses the honest committer’s device shares only through the declared interface of Definition 3. Item (ii′ ) implies item (ii), since Simcom does not depend on b.

5.2

Step 1: post-quantum equivocal commitments

The first step is the classical ingredient: an equivocal commitment from qOWFs, used for every inner commitment of Protocol 4. Fact 4 (Post-quantum equivocal commitments). Under qOWFs, there exists a commitment, with classical messages, that has statistical binding, quantum-computational hiding, and QPT quantum equivocation [BCKM21, Theorem 4.1 and Section 4.1]: ∀ V∗ ∈ QPT ∃ (Simcom , Simopen ) ∀ η ER , b : RealV∗ (b, η ER ) ≈c SimV∗ (b, η ER ), where Simcom runs before b is supplied, Simopen (b) gives a valid native opening, and both maps preserve the inaccessible R. For the compiler of Bartusek, Coladangelo, Khurana, and Ma [BCKM21] applied to Naor commitment, simulation retains classical native-opening witnesses for either bit of every unopened record. We use sequential completed phases and separate records for separately opened fields. Statistical binding concerns real commitments.

5.3

Step 2: the extractable DI commitment

Protocol 4 has the records, tests, audits, selectors, and step numbers of Protocol 1 up to Step 13. It differs in three ways: inner commitments replace CP; Alice’s payloads carry her committed bit instead of (S0 , S1 ) and are checked at the opening instead of by PAY; and Bob accompanies (r, χ) with a mode proof. Table 5 matches the notation of the two protocols. The protocol uses the inner commitment of Fact 4 for the test mask, Bob’s records and masks, and Alice’s tables. A single batch supplies all blocks. In block i, Bob privately chooses a fair label βi and the matching selector J i , disjoint from his audit. He uses a zero-knowledge mode proof to link the selector labels to his question commitments. For a commitment transcript c of Commit, OpenVer(c, u, w) ∈ {0, 1} denotes its classical native-opening predicate for value u and opening witness w; cU j is the transcript of Bob’s commitment to Uj .

44

Table 5: The OT protocol against the commitment protocol. Above the rule: notation, which differs because the commitment already uses b for the committed bit. Below it: three differences between the protocols themselves; each proof treats its own variant, and neither depends on the other’s. Object Bob’s committed question offsets Alice’s question offsets Bob’s question Branch index Extractor seeds Audit set of block i What the payloads encode Audit charge in the pad budget Selector-size check

Honest-fault condition

OT (Protocol 1) YB YA Y =YA+YB b ∈ {0, 1} Rib each coordinate with probability δaud (S0 , S1 ), with ∆ = S0 ⊕ S1 6mδaud N , since Alice checks |TBi | ≤ 2δaud N Bob aborts in Step 6; the analysis defers this abort past Alice’s table commitment (15)

BC (Protocol 4) U V Y =U +V t ∈ {0, 1} sti uniform of size naud the committed bit b 3mnaud part of Bob’s audit bit in Step 10 (Remark 17)

(47)

Definition 12 (The mode relation). For L coordinates, set i xmode = ((cU j )j∈[L] , V, TA , (J )i∈[m] , r, χ, UTA ),

wmode = (U ′ , ζ, (wj )j∈[L] ), m where U ′ ∈ ZL 3 , ζ ∈ F2 , and wj is a native opening witness. The predicate Syntax mode accepts exactly the well-formed tuples satisfying m r ∈ Fm 2 \ {0 },

ρmin N ≤ |J i | ≤ ρmax N

J ∩ J = ∅ (i ̸= k), i

J :=

k

[

(i ∈ [m]),

J ⊆ [L] \ TA . i

i

Define

MODE(xmode ; wmode ) = 1

⇐⇒

Syntaxmode (xmode ) = 1, ′ OpenVer(cU j , Uj , wj ) = 1

(∀j ∈ [L]),

χ = ⟨r, ζ⟩, UT′ A = UTA , J i ⊆ {j : Uj′ + Vj = ζi } (∀i ∈ [m]). For a trit commitment, OpenVer denotes the conjunction of its bitwise native-opening predicates. An honest Bob proves MODE with witness U ′ = U and ζ = β. Here Commit denotes bitwise inner commitment. Every coordinate is queried; Cj = 0 erases its later record to (Xj , Aj ) = (0, 000). The record encoding, the honest fault model (7), Syn, Ext, and canonical syntax are those of Section 3.2. The public parameters are L = mN + tA , anchoring probability δ∗ , audit size naud = ⌈caud N/m⌉, selector bounds ρmin , ρmax , and test and audit thresholds κtest , κaud from Sections 2.4 and 5.6.2. All messages are session-tagged. A failed opening, malformed field, or rejected required check causes a public abort; no receipt is issued. The same steps apply at m = 1, r = 1. 45

Input: Alice’s bit b ∈ {0, 1}. Public parameters and Commit, Syn, Ext are defined immediately above. Trit arithmetic is coordinatewise modulo three. 1. Alice. Sample X in ←U {0, 1, 2}L and a uniform tA -subset TA ⊆ [L]. Commit to its incidence string tmask = 1TA . A 2. Bob. Sample U ←U {0, 1, 2}L and commit to every trit Uj . 3. Alice. Send fresh V ←U {0, 1, 2}L . In the device window shared with the next step, input every Xjin and record its parity-correct row Ain j . 4. Bob. Set Y = U + V , input Y , and record the parity-correct answer batch B. After both parties have collected all outputs, close the leakage window and commit to all Bj . 5. Alice. Open tmask . Send a fresh uniform ordering π of [L] \ TA ; its consecutive groups of N A entries define I1 , . . . , Im . 6. Bob. Verify this opening, |TA | = tA , and π. For each i, sample a uniform naud -subset TBi ⊂ Ii and an independent fair bit βi . Let β = (β1 , . . . , βm ). Set Jti = {j ∈ Ii \ TBi : Yj = t} for t = 0, 1 and J i = Jβi i . Commit to both incidence masks 1T i , 1J i ; defer size decisions. B

7. Alice. Sample independent Cj ← Bern(1 − δ∗ ) for all j ∈ [L]. Set (Xj , Aj ) = (Xjin , Ain j ) if Cj = 1 and (0, 000) otherwise; discard erased raw controller records. Commit separately to S (Xj , Aj , Cj ) for j ∈ i Ii . 8. Bob. Open the audit masks (1T i )i∈[m] and the committed (Uj , Bj ) for j ∈ TA . B

9. Alice. Verify these openings, |TBi | = naud , and TBi ⊂ Ii . Set tst = 1 exactly when at most a κtest fraction of TA fails Cj = 0 or MS(Xj , Uj + Vj , Aj , Bj ) = 1. Send tst; globally abort on zero. Otherwise open (Xj , Aj , Cj ) on every TBi . 10. Bob. Verify the audit openings and canonical table syntax. For each i, require P i |. C 1{A [Y ] = ̸ B [X ]} ≤ κ n , where n = |T Require tst = 1 and i j j j j aud aud aud j∈TB j B i i |J0 |, |J1 | ∈ [ρmin N, ρmax N ] for all i. Send aud = 1 iff all these checks accept; abort on zero, otherwise open all J i masks. 11. Alice. Require aud = 1. Verify the selector openings, J i ⊆ Ii \ TBi , and |J i | ∈ [ρmin N, ρmax N ]. Send sel = 1 iff every check accepts; abort on zero. 12. Bob. Require sel = 1. Sample r ←U {0, 1}m \ {0m } and send χ = ⟨r, β⟩ with r. Prove MODE of Definition 12 using U ′ = U , ζ = β and the saved native opening witnesses. S 13. Alice. Verify the syntax of (r, χ) and the mode proof. Open (Xj , Cj ) on J = i J i . For i ∈ [m], t ∈ {0, 1}, put ni = |J i |, Zit = (Aj [t])j∈J i and Wit = Synni (Zit ). Sample independent L sti ←U {0, 1}ni and Q ←U {q ∈ {0, 1}m : i qi = χb}. Send all (Wit , sti , Fit ), where Fit = Qi ⊕ ri tb ⊕ Extni (Zit ; sti ). 14. Bob. Check openings, anchor X = 0, and the prescribed payload tuple lengths and bit syntax. Issue a commitment receipt. Discard private U, Y, B, β, device state, and mode witnesses; retain the public transcript and Alice-table verification records. No decoder result is announced. 15. Alice (opening). On the single opening request, send b and open all committed block-table fields, reusing earlier openings. No further device operation occurs. 16. Bob. Require b ∈ {0, 1} and verify table syntax, all openings and agreement with previously opened fields. Recompute Zit and require Wit = Synni (Zit ). Set pti = Fit ⊕ Extni (Zit ; sti ). Accept L and output b exactly when p0i ⊕ p1i = ri b for every i and i p0i = χb; otherwise reject. Close the session. Where each step is used. Steps 1–11: as in Protocol 1, with Lemma 16 and Lemma 14 for the test and audit. Step 12: mode relation Definition 12, soundness Lemma 13. Step 13: payloads (50), algebra Lemma 11, hiding Lemma 17. Steps 14–16: opening equations (51), agreement Theorem 18, correctness Theorem 22. 46 Protocol 4: Unified DI BC: commitment and public opening verification.

Theorem 14 (DI realization of efficiently extractable BC). Under qOWFs and the stated device/invocation conditions, Protocol 4 realizes Definition 10 with QPT online algorithms and negligible error. The schedule of Section 2.4 gives m=1:

L = Θ(log2 λ),

τhonest = Θ(1);

m>1:

m = ⌈2ℓ + 4tA + sλ ⌉,

τhonest = Θ((m log N )−1 ).

The first line assumes isolation, ℓ = 0, and coordinate-local Bob; the second permits bounded adaptive leakage and joint honest-Bob instruments. Fault tolerances use the stated fixed slack, physical conditions, and retained-state interfaces. Correctness. With honest parties, the opening checks of Step 16 hold by construction, since Alice computes every syndrome, pad, and payload from her own table. An honest execution can therefore fail only at the sparse test, at an audit, or at the selector-size window. Each threshold exceeds the honest fault rate by a fixed factor (47), so Fact 6 makes every such failure negligible (Lemma 2 and Theorem 22). Committer simulation and receiver hiding were described in words in Section 1.3; the simulator is Protocol 5, and the proof below assembles the argument. Protocol 4 has no receiver-side simulator; Step 3 adds one. Proof. The contract of Definition 10 has three items, and Figure 4 shows which statement proves each. Committer simulation has two halves. The simulator’s view is indistinguishable from the real one (Theorem 19): the mode change χ 7→ χ ⊕ 1 has a valid witness (Lemma 12), and it is hidden because β is hidden from Alice, exactly at the isolated endpoint (Lemma 5) and by the label-entropy bound otherwise (Lemma 15). Every accepted opening agrees with the extracted bit (Theorem 18): the simulator retains Bob’s genuine selector construction, so Yj = βi for every j ∈ J i , and the audits make the simulator’s decoder agree with Alice’s committed table (Lemma 14), with error m exp[−Ω(naud ηA )]. Receiver hiding is Theorem 21: after the sparse test (Lemma 16), the pads of the unselected branches are uniform (Lemma 17), by the same argument as Lemma 9. Correctness, continuations, and parameters. Section 5.6.7 proves correctness and the phase-local sequential contract, retaining other pending honest states and allowing delayed openings in either role. Lemma 2 makes every error term negligible in both regimes. Part of Theorem 14 Simulated view is indistinguishable Openings agree with the extracted bit Receiver hiding Correctness and continuations

Proved by Theorem 19 Theorem 18

Which rests on Lemmas 11 and 12; Lemma 5 at m = 1, Lemma 15 otherwise Lemmas 11 and 14

Theorem 21 Theorem 22

Lemmas 16 and 17, Lemma 1, Table 4 Lemma 2, Fact 6

Figure 4: Proof map of Section 5 for Protocol 4. The second equivocation layer and the coin toss add Theorem 15 and Corollary 16, which use this theorem only through the contract.

47

Setting: Alice is corrupt. SIM runs Bob’s role in Protocol 4. EqCom is the equivocation simulator of Fact 4; Decn (z ′ , W ) is the total decoder of Equation (45). 1. SIM (records). Receive Alice’s test-mask commitment. Generate Bob’s U commitments using EqCom. On Alice’s offset V , run the genuine Y = U + V device execution and leakage window, keeping the actual answers B. Use EqCom for Bob’s answer commitments. 2. SIM (tests). On Alice’s test opening and permutation, follow Bob’s checks and sample the genuine TBi , βi , J i . Use EqCom for both masks, opening all required records to their genuine values. Receive Alice’s table commitments using the ordinary honest receiver algorithm. Complete the test, audit and selector turns and reproduce every public abort. 3. SIM (mode). On sel = 1, sample the prescribed nonzero r but send χ = ⟨r, β⟩ ⊕ 1. Run the witness-independent ZK simulator for MODE. Lemma 12 supplies a valid alternative native witness, so this public statement is true. 4. SIM (extraction). On valid (X, C)J openings (with X = 0 when C = 0) and a well-formed ′ = 0 for C = 0, and z ′ = B [X ] otherwise. Compute payload tuple, let ni = |J i | and set zi,j j j j i,j every Zbi = Decni (zi′ , Wiβi ). If one equals ⊥, set b∗ = 0 privately. Otherwise compute pbi = Fiβi ⊕ Extni (Zbi ; sβi i ),

b∗ =

M

pbi .

i

Submit b∗ to ideal BC at the receipt cut. Send the ordinary receipt and retire the same honest-receiver registers. No extra flag is sent to Alice. 5. SIM (opening). On Alice’s later opening, perform the public checks of Step 16 of Protocol 4. Authorize the ideal opening exactly when they accept, and its bit equals b∗ ; reproduce rejection otherwise. An accepted opening disagreeing with b∗ is the negligible agreement-error event. Where each step is used. Steps 1–2: equivocal commitments, Fact 4. Step 3: alternative witness Lemma 12, hidden by Lemma 15 or Lemma 5. Steps 4–5: Theorem 19, Theorem 18. Protocol 5: DI BC: full committer-side simulator. Every action preserves the genuine physical questions and measurements.

5.4

Step 3: simulation for both parties

Protocol 4 has a simulator against a corrupt committer only; against a corrupt receiver, it is hiding in the sense of Definition 10(ii), and it is not equivocal. This subsection adds a receiver-side simulator and so realizes Definition 11. Bartusek, Coladangelo, Khurana, and Ma obtain extractable and equivocal commitments by applying their equivocality compiler a second time to an extractable commitment, and show that the compiler preserves extractability [BCKM21, Section 4]. We apply that compiler to Protocol 4, with one change that the device model forces. Their equivocator rewinds the receiver across the base commit phases. In Step 1 this is harmless: the base commit phases are classical Naor commitments, which lie outside the device window, so no rewound segment contains a query to an honest party’s device. In Step 3, a base commit phase is a call to Protocol 4, which queries the honest committer’s single-use device, and the simulator of Definition 3 may neither reset nor re-prepare that device. The receiver therefore commits to its challenges first, with Protocol 4 in the reversed role, as the verifier does in the compiler of Section 4. The simulator extracts the challenges and never rewinds across a device call. The layered protocol. Let k = sλ (Section 2.4). A call is one execution of Protocol 4 with its own fresh, isolated device batch and the schedule of Section 2.4; in a reversed call Bob commits, and 48

Alice receives. Protocol 6 uses 5k calls per committed bit. In iteration i, Alice commits twice to each of two random bits, Bob’s challenge ci selects the pair that is opened and checked for equality, and the other pair masks b. Input: Alice’s bit b ∈ {0, 1}. Parameter: k = sλ . Session (i, p, q) is the q-th commitment of pair p in iteration i, for i ∈ [k] and p, q ∈ {0, 1}. Each party aborts on any failed verification. 1. Bob. Sample uniform c1 , . . . , ck ∈ {0, 1} and commit to each ci by a reversed call, sequentially. 2. For i = 1, . . . , k, sequentially: (a) Alice. Sample uniform di,0 , di,1 ∈ {0, 1}. Commit by four sequential calls: sessions (i, 0, 0), (i, 0, 1) to di,0 and sessions (i, 1, 0), (i, 1, 1) to di,1 . (b) Bob. Open ci . Alice. Verify the opening. (c) Alice. Open sessions (i, ci , 0) and (i, ci , 1). Bob. Verify both openings and that the two opened bits are equal. 3. Alice. Send ei = b ⊕ di,1−ci for every i ∈ [k]. This ends the commitment phase. 4. Alice (opening). Send b and uniform α1 , . . . , αk ∈ {0, 1}, and open session (i, 1 − ci , αi ) for every i. 5. Bob (opening). Accept b if every opening is valid and the bit opened in iteration i equals b ⊕ ei . Where each step is used. Every call is Protocol 4 under its contract Definition 10; the protocol realizes Definition 11 by Theorem 15, whose proof treats Steps 1–3 (committed challenges), Steps 4–5 (equivocation), and Step 6 (extraction) in turn. Protocol 6: DI BC with simulation for both parties: the equivocality compiler of [BCKM21] over Protocol 4, with committed challenges. Simulator for a corrupt receiver (Bob). 1. In each reversed call of Step 1, run the committer-side simulator of Protocol 4 (Protocol 5) against Bob and obtain c∗i ∈ {0, 1, ⊥}; replace ⊥ by 0. 2. In iteration i, sample uniform zi , di . With the genuine device batches, commit honestly to zi in both sessions of pair c∗i , to di in session (i, 1 − c∗i , 0), and to 1 − di in session (i, 1 − c∗i , 1). Verify Bob’s opening of ci as Alice does; if it is valid and ci ̸= c∗i , stop with FAIL. Open pair ci honestly. 3. Send uniform e1 , . . . , ek . 4. On input b: send b and αi = di ⊕ b ⊕ ei , and open session (i, 1 − ci , αi ) honestly; it holds b ⊕ ei . Simulator for a corrupt committer (Alice). 1. Commit to uniform c1 , . . . , ck honestly. 2. In iteration i, run the committer-side simulator of Protocol 4 in all four sessions and obtain d′i,p,q ∈ {0, 1, ⊥}. Open ci and verify Alice’s openings as Bob does. 3. After receiving e1 , . . . , ek , let i0 be the first iteration with d′i0 ,1−ci ,0 = d′i0 ,1−ci ,1 ∈ {0, 1}. 0 0 Output b∗ = ei0 ⊕ d′i0 ,1−ci ,0 , or b∗ = ⊥ if there is no such iteration. 0

Where each step is used. Corrupt receiver, Steps 1–4: extraction of the challenges and receiver hiding of Protocol 4, Theorem 15 Step 2. Corrupt committer, Steps 5–7: Theorem 15 Steps 3–4. Protocol 7: The two simulators of Protocol 6. Both use the honest party’s device shares only by running honest calls or the simulator of Protocol 4.

49

Theorem 15 (DI BC with simulation for both parties, adapted from the equivocality compiler of [BCKM21]). Under qOWFs and the device and invocation conditions of Theorem 14, applied to every call, Protocol 6 realizes Definition 11 with the QPT simulators of Protocol 7 and negligible error, in both regimes of Theorem 14 and with the same honest-fault tolerance per call. It uses 5sλ = O(log2 λ) calls per committed bit, hence polylogarithmically many device coordinates. Proof idea. Extracting ci tells the simulator which pair will be checked, so the other pair can hold opposite bits; against Alice, hidden challenges make an unequal pair survive with probability at most 1/2 per iteration. Section 5.6.8 gives the proof. The compiler of Section 4 needs only the contract of Definition 10 and is instantiated with Protocol 4. Its verifier-side simulation comes from the committed challenge, so equivocation of the source is not needed there; using Protocol 6 instead would multiply the device count of every compiler commitment by 5sλ and gain nothing.

5.5

Application: coin tossing

Coin tossing shows why both simulators are needed: extraction handles a corrupt committer and equivocation a corrupt receiver. The ideal functionality ideal(CT) samples a uniform bit c. If both parties are honest, both output c. If one party is corrupt, the functionality releases c to the simulator, which answers deliver or abort; the honest party outputs c or ⊥ accordingly. This is coin tossing with abort. 1. Alice. Sample uniform a ∈ {0, 1} and commit to a by the commitment phase of Protocol 6. 2. Bob. Sample uniform b′ ∈ {0, 1} and send it. If no bit arrives, Alice outputs ⊥. 3. Alice. Open a by Steps 4–5 of Protocol 6 and output a ⊕ b′ . 4. Bob. If the opening is accepted, output a ⊕ b′ ; otherwise output ⊥. Where each step is used. Steps 1 and 3: Protocol 6; Steps 2–4: Corollary 16. Protocol 8: DI coin tossing: Blum’s commit-and-reveal protocol [Blu83] over Protocol 6. Corollary 16 (DI coin tossing with abort). Under qOWFs and the conditions of Theorem 15, Protocol 8 realizes ideal(CT) in the sense of Definition 3, with QPT simulators for either corruption and negligible error, in both regimes of Theorem 14. It uses 5sλ calls of Protocol 4, hence polylogarithmically many device coordinates. For n ≤ poly(λ), n sequential executions realize n independent tosses with abort, at every boundary satisfying Definition 4 (Theorem 5). Proof idea. Against Alice, the simulator extracts a∗ and sends b′ = c ⊕ a∗ ; against Bob, it commits equivocally and opens to c ⊕ b′ . Section 5.6.9 gives the proof. The DI coin-flipping protocols of [SCA+ 11] and [ACK+ 14] are information-theoretic and have constant bias; [SCA+ 11] reports bias at most about 0.336. Corollary 16 assumes qOWFs and, in exchange gives negligible error in the simulation sense, against non-IID devices, with the fault tolerance and leakage resilience of Theorem 14.

50

5.6 5.6.1

Proofs for the commitment Purpose and the mode identity

Alice commits to a bit b. In each of m blocks, Bob has a private label βi ∈ {0, 1} and can reconstruct m the raw string for that label. Let r ∈ Fm 2 \ {0 } be fresh and put e = ⟨r, β⟩. Real Bob sends χ = e. Alice chooses Q1 , . . . , Qm uniformly subject to two payloads Pit = Qi ⊕ ri tb, t ∈ {0, 1}.

i Qi = χb, and encodes the

L

(43)

The identity underlying the construction is m M

Piβi = (χ ⊕ e)b.

(44)

i=1

Thus, this XOR is zero in the real protocol. A simulator that can use χ = e ⊕ 1 obtains b from the same selected branches. Bob proves the real-mode relation in zero knowledge. Its witness consists of ordinary classical commitment openings and labels. In the simulation, equivocation supplies an alternative valid witness for the opposite mode. The physical questions and measurements are not changed by this mode switch. To turn this identity into a commitment, early table commitments and audits must bind accepted openings to the selected records, while selector entropy must hide the mode change. The following interfaces and parameters support these two arguments. 5.6.2

Interfaces and imported facts

This subsection fixes the physical model, the retained state, and the classical commitment and proof tools that the commitment proofs use. Physical model and retained state There are trusted classical controllers and untrusted bipartite devices. Fresh controller coins and inner commitment witnesses are inaccessible to the opposite laboratory. Devices are distributed before question randomization. An honest device interface receives its designated Magic Square questions, not the controller’s other classical messages. In particular, Alice’s device is not supplied with the offset used to randomize Bob’s questions. There is one device-input/device-output window. Within it, arbitrary adaptive communication between the laboratories is allowed, with total length at most ℓ, counting each classical bit or qubit as one unit. All routing, direction, length, and stopping information is included in this budget unless the schedule is fixed publicly. The window closes before record commitments and tests. It never reopens in this session. Devices may be arbitrarily entangled across coordinates and with an inaccessible reference R. Their instruments may be joint in the general regime. The isolated one-block parameter choice uses Definition 5; neither regime assumes an IID adversarial state. The simulator can run the corrupted party’s complete quantum workspace and the honest receiver’s current-session operations. It acts trivially on R and on other pending honest-party states. Equivocation and ZK simulation occur in completed classical subprotocols, outside the physical leakage window. At commitment completion, honest Bob discards his question and answer records, labels, device systems, and mode-proof witnesses. He retains the public transcript and the classical verification 51

records needed for Alice’s later openings. No future honest operation depends on the discarded registers. This is a protocol rule for an honest receiver, not a restriction on a dishonest receiver’s memory. Classical commitment and proof tools Assume one-way functions secure against quantum adversaries and auxiliary inputs under consideration. Instantiate Commit by applying the equivocation compiler of Bartusek, Coladangelo, Khurana, and Ma [BCKM21] to Naor’s commitment [BCKM21, Theorem 4.1 and Section 4.1]. Honest operations and messages are classical. The real scheme is statistically binding and quantum-computationally hiding. Its quantum equivocation simulator preserves the receiver’s continuing state, including a reference. Use separate bit commitments for fields that may open separately, with fixed-length encodings of trits and masks. For a public commitment transcript c, let OpenVer(c, u, w) ∈ {0, 1} be its classical native-opening predicate. A witness w includes the opening messages for the compiled commitment. Retaining the underlying classical decommitment data in that simulation supplies valid native witnesses for either target bit: the unopened pair in each simulated iteration contains opposite bits. These are ordinary classical witnesses, not witnesses of a quantum computation. The negligible simulation-failure probability is charged separately. More explicitly, let the unopened pair in repetition i commit to di ⊕ a, a ∈ {0, 1}, with retained Naor seeds si,a and public mask ei . For target b, set ai (b) = b ⊕ ei ⊕ di , wb = (ai (b), si,ai (b) )i . Then di ⊕ ai (b) = b ⊕ ei , so the native verifier accepts OpenVer(c, b, wb ) = 1 for each b on every successful simulated branch. Retaining and classicalizing these private seeds preserves the receiver/reference marginal. Real-to-equivocal hybrids keep genuine targets at their original sampling cuts; unused target sampling is postponed only afterward by an exact distributional identity. We use the sequential auxiliary-input version of equivocation, including adaptive later native openings. Every individual commitment phase finishes before the next begins. For NP use a classical-message quantum-computational zero-knowledge proof ΠZK , with negligible soundness error and a uniform QPT auxiliary-input simulator [Wat09]. The usual statistically binding, quantum-hiding commitment implementation of the GMW–Watrous proof suffices. Its internal commitments are local to that proof; the simulator does not rewind an external functionality. The simulator is used only for true public statements. Soundness, rather than knowledge extraction, will connect a real proof to the unique values in Bob’s statistically binding commitments. The repetition input Fix δ∗ ∈ (0, 1). Alice and Bob receive independent uniform physical trits X in , Y on every coordinate, and output a row Ain and a column B. Independently, after Bob’s early record is frozen, C = 0 with probability δ∗ erases Alice’s committed record to (X, A) = (0, 000); otherwise (X, A) = (X in , Ain ). Only C and active physical questions are subsequently disclosed. The Magic Square predicate includes the prescribed parities and equality at their intersection. Honest controllers encode each active answer with its prescribed parity, for example by deriving the third bit from the first two. The honest noise rate refers to failures of the resulting game predicate; it does not allow later classical corruption of a committed table or its opening. Use Theorem 4 for these questions and answers, with (B, J) frozen before C and the late question release. Section 7.1 supplies the selector and the reconstruction map. Leakage is removed by Fact 11, at probability cost 2−2ℓ , inside the fixed statistical hybrid, as convention (ii) of Section 2.5 prescribes. 52

Lemmas 1 and 20 give a positive block entropy constant γraw > 0. In this application, all other-coordinate registers stay on their original sides, as auxiliary entanglement of Charlie and Dave. Coding, hashing, and parameters Use the common schedule of Section 2.4. More generally, the one-block endpoint requires ℓ = 0, coordinate-local honest Bob, and tA , N = ω(log λ) with tA = o(N ). The general regime uses polynomially bounded m, N with the scales of (12). In every block, audit a uniform set of exactly naud = ⌈caud N/m⌉ coordinates. The selector window and small constants are fixed as in Section 2.4. For each permitted selected length n, the binary linear code has syndrome length at most rEC n + O(log n), with rEC = cEC /m, and satisfies dH (z, z ′ ) ≤ τEC n

=⇒

Dec(z ′ , Syn(z)) = z.

(45)

Its radius is (6). The decoder returns a failure symbol on an undecodable input; syndrome verification at opening is exact. Each branch uses a fresh independent seed for a quantum-proof two-universal hash Extn (z; s) to one bit. Choose thresholds with fixed multiplicative slack, κaud < ηA < ρmin τEC ,

κaud , ηA = Θ(τEC ).

(46)

The honest-device loss rate satisfies qdev ≤ (1 − ξ) min{κtest , κaud }

for a fixed ξ ∈ (0, 1).

(47)

The test threshold κtest > 0 is a fixed constant below the repetition-loss threshold. In the general regime, require ksel = m − 2ℓ − 3tA − O(1) = ω(log λ).

(48)

At the isolated one-block endpoint, Lemma 5 replaces this condition. Both regimes require kpad = γraw N − 2ℓ − 2ρmax mrEC N − 3mnaud − O(m log N ) ≥ αN

(49)

for a fixed α > 0. Taking 2ρmax cEC + 3caud < γraw /2 leaves a positive margin. Lemma 2 verifies the scales and budgets in both regimes. One global leakage budget covers the whole batch; it is not reset per block. 5.6.3

Protocol conventions used in the proofs

The proofs use the variables and step numbers of Protocol 4. Three conventions of that protocol are load-bearing and are recorded here. First, Alice’s device receives every raw question Xjin without the erasure flag Cj ; after Bob’s selector is frozen, she samples C and overwrites each anchor record by (Xj , Aj ) = (0, 000), and raw anchor questions and answers never occur in later commitments or openings. Second, the table is committed before either audit mask opens, and the selector-size decision is part of Bob’s later global audit bit rather than an earlier public abort. Remark 17 (Why the size decision is deferred). The hidden-mask proof moves the choice of TB , J past Alice’s table commitment. A public size-dependent abort before that commitment would need separate treatment. The stated protocol commits the masks first and includes the size decision only in the later global audit bit. This timing is part of the construction. 53

Third, the tuple Alice sends in Step 13 for each i, t is (Wit , sti , Fit ),

Wit = Syn(Zit ),

Fit = Pit ⊕ Ext(Zit ; sti ),

(50)

where Zit = (Aj [t])j∈J i and Pit = Qi ⊕ri tb; Alice gives no commitment-phase proof of these equalities, and Bob’s receipt announces no decoder flag or selected-payload XOR. At the opening (Steps 15–16), after validating all table openings and recomputed syndromes, Bob puts pti = Fit ⊕ Ext(Zit ; sti ) and checks M p0i ⊕ p1i = ri b for every i, p0i = χb. (51) i

Acceptance or rejection closes the session; neither uses a private Y, B, β record or a further device operation. 5.6.4

Algebra, witnesses, and efficient extraction

We first check the opening identity and construct the alternative mode witness. These give the simulator; the audit argument then shows that its decoded bit agrees with every accepted opening. m m Lemma 11 (Opening algebra). For p0 , p1 ∈ Fm 2 , r ∈ F2 \ {0 } and b, χ ∈ F2 , Equation (51) implies M β ∀β ∈ Fm : pi i = (χ ⊕ ⟨r, β⟩)b. 2 i

Moreover, {b ∈ F2 : p0 ⊕ p1 = rb,

L

0 i pi = χb}

≤ 1.

Proof. For each i, pβi i = p0i ⊕ βi ri b. XOR over i. For uniqueness, choose a coordinate with ri = 1; its first opening equation determines b. Lemma 12 (A valid opposite-mode witness). Suppose cU is equivocated with retained native m witnesses for both bit values. Outside inner simulation failure, for every r ∈ Fm 2 \ {0 } an efficient ′ algorithm returns w with MODE(xmode [χ ← ⟨r, β⟩ ⊕ 1]; w′ ) = 1, (Y, B, J, β)after = (Y, B, J, β)before . Proof. Choose k with rk = 1, and set ζ = β ⊕ ek . On J k , set Uj′ = ζk − Vj . Keep Uj′ = Uj elsewhere. The sets J i are disjoint and avoid TA ; all tested question openings remain unchanged. For each modified trit, obtain the appropriate native witnesses from the equivocation data. The conditions of Definition 12 hold. This calculation changes the logical witness, not the input tape of the device execution. Lemma 13 (Mode soundness for a real receiver). For every admissible QPT Bob using real inner commitments, except with probability negl(λ), m Accmode = 1 =⇒ ∃!(U ∗ , β) ∈ ZL 3 × F2 : ∗ ∀j ∈ [L] ∃wj : OpenVer(cU j , Uj , wj ) = 1,

χ = ⟨r, β⟩,

Uj∗ + Vj = βi

UT∗A = UTA ,

(i ∈ [m], j ∈ J i ).

Write Yj∗ = Uj∗ + Vj . Proof. Outside the statistical-binding failure event, each native commitment has at most one possible value. Soundness makes the accepted NP statement true, so a witness supplies all required valid values. On a nonempty J i , the effective question value determines its label uniquely. 54

The extraction simulator Against a corrupt Alice, SIM proceeds as follows. Equivocation supplies the alternative valid mode witness of Lemma 12. All online steps are QPT. SIM never reads a committed Alice table value before a native opening. Audits without an efficient inner extractor The simulator obtains its candidate bit from selected decoders. We now relate those decoder outputs to Alice’s later openings, using sampling inside the fixed equivocal-commitment experiment. Lemma 14 (Audits bind successful openings to the decoder). For an opening o, write Zit (o) for its raw strings and OpenAcc(o) for the unmodified public opening predicate of Protocol 4, without SIM’s additional test b = b∗ . In SIM’s equivocal-commitment execution, h

i

Pr ∃o, i ∈ [m] : OpenAcc(o) = 1 ∧ dH (Ziβi (o), zi′ ) > ηA N ≤ εaud , εaud ≤ m exp[−Ω(naud ηA )] + negl(λ). Outside this event, every accepted opening satisfies ∀i ∈ [m] :

dH (Ziβi , zi′ ) ≤ ηA N < τEC |J i |.

Proof. Goal and plan. We must show that if Alice’s committed table disagrees with Bob’s records on more than ηA N coordinates of some block, then the audit rejects except with negligible probability, and that otherwise every valid opening lies within the decoding radius on the selectors. The audit is a uniform sample of naud coordinates taken after the table is frozen, so this is a sampling bound; Steps 1 and 2 establish that the sample is fresh and the table is fixed, Step 3 applies the bound, and Step 4 draws the conclusion for the selectors. Step 1: the audit is sampled after the table cut. In this fixed simulation experiment, Bob’s auditand selector-mask commitment algorithms do not use their target masks, so no message before Alice finishes her table commitments depends on (TB , J, β). Their sampling can therefore be moved to immediately after the table cut, with the same experiment; the global size check comes later, as Remark 17 requires. Step 2: the table is fixed at the cut. Statistical binding of Alice’s real table commitments fix a unique possible table at this cut, except with negligible probability. For the analysis, we assign it by an unbounded function of the classical transcript, with a canonical value for unopenable entries; native audit openings must agree with it, and unopenable sampled entries cannot help acceptance. Step 3: a large bad set is caught. Condition on this table and on the genuine (Y, B). In block i, the bad set consists of the invalid table entries, the active intersection mismatches, and the canonicalanchor failures. If it exceeds ηA N , then, because the audit is a fresh uniform sample of size naud , Fact 6 (hypergeometric case) bounds the probability of acceptance by exp[−Ω(naud ηA )]; the thresholds have constant multiplicative slack. This is exp[−Ω(N )] at m = 1 and exp[−Ω(N/(m2 log N ))] under the general BCH parameters, both negligible by Lemma 2. Step 4: within the decoding radius on the selectors. Outside that event, every block has at most ηA N bad entries. On the selected coordinates Yj = βi , and every valid eventual opening, including the already disclosed (X, C)J , agrees with the same fixed entries, so its distance on J i is at most the bad-set size. A union bound over the blocks and the lower bound on |J i | give the stated radius. Theorem 18 (Agreement with accepted openings). Let b∗ be SIM’s commitment-end output and b(o) the bit in opening o. Then Pr [∃o : OpenAcc(o) = 1 ∧ b(o) ̸= b∗ ] ≤ εaud = negl(λ).

SIM

55

Proof. Take any accepted opening. Its syndromes agree exactly with the opened raw strings. By Lemma 14 and Equation (45), Zbi = Ziβi for all i; hence pbi = pβi i . The opening equations and χ = ⟨r, β⟩ ⊕ 1 give M β b∗ = pi i = b i

by Lemma 11. Thus a private decoder failure cannot coexist with an accepted opening outside the same negligible bad event. 5.6.5

Preservation of the corrupt committer’s state

Agreement identifies the bit in every accepted simulated opening. It remains to show that the opposite-mode commit phase presents the correct continuing state to Alice. This is where selector privacy and retirement are needed. The equivocal receiver experiment First define EB by replacing all honest Bob commitments by their equivocation simulation, opening them to genuine values, and replacing his real-mode ZK proof by its witness-independent simulator. Keep χ = e for now. Sequential equivocation and ZK make the retained real state and the EB state computationally indistinguishable, jointly with R. The simulated proof has a true statement at this stage. In EB , the commitment-phase algorithms for U, B do not use their values. Fresh uniform physical Y can therefore be sampled after V and represented by U = Y − V . Bob opens U only on TA , and opens B only on TA . The possible test set is fixed by Alice’s earlier statistically binding mask commitment before this fresh physical Y is chosen. Lemma 15 (Block-label entropy in the fixed hybrid). In the totalized EB experiment, let ρβ Ve

A

be the post-selector, pre-r cq state, where VeA = (VA , Tpub , R) excludes Bob’s private (Y, B, β) and equivocation witnesses. Outside negligible inner failure events, pguess (β | VeA )ρ ≤ 22ℓ+3tA +1−m .

(52)

For the subnormalized accepted substate ρb, pguess (β | VeA )ρb ≤ pguess (β | VeA )ρ . Proof. Goal and plan. This is the argument of Lemma 6, carried out in the experiment EB in place of the ideal CP execution. There, CP receipts carry only metadata; here, Bob’s commitments are equivocal simulations, which are independent of his questions and answers, and that plays the same role. The steps are in the same order: remove the leakage and guess the tested answers, show that the untested questions are uniform given Alice’s view, exchange the labels, and undo the guesses. Step 1: totalization. The label vector must be defined on every branch, including those on which the protocol stopped before Bob sampled it. We define the missing variables in private analysis registers only and retain every actual stopped view: on an abort before the genuine labels are sampled, we append a fresh independent uniform β ∈ {0, 1}m and emit no further message. Except on a failure of statistical binding, every valid opening refers to the unique mask that was fixed before Y . Only that binding failure is charged a negligible probability; an abort on an invalid mask is an ordinary branch. Step 2: remove the leakage and guess the tested answers. We work in EB throughout. The physical-window communication is eliminated by Fact 11, at cost 22ℓ . The 3tA tested answer bits are guessed at their first value-dependent disclosure, which is their native opening: the earlier equivocal 56

commitments did not use B. On a correct guess, the entire continuation agrees with the actual one, so this step costs a factor 2−3tA in probability. Step 3: the untested questions are uniform given Alice’s view. This is Step 2 of the proof of Lemma 6, word for word, with Alice’s table operations in place of her CP commitments. Step 4: label symmetry. For each block we exchange the question labels 0 and 1 on the complement of its audit set and flip βi . This leaves J i unchanged and preserves the uniform law of the questions. It also leaves Alice’s view unchanged: the equivocal mask transcripts depend on the opened masks and on no other representation of βi , and the two-candidate size condition is symmetric. Before Bob’s global audit bit, the label vector is therefore uniform and independent of her view. Appending that single bit costs at most a factor of two, and Alice’s own decisions and later local channels cost nothing further. Step 5: undo the guesses. Multiplying by the two factors of Step 2 gives Equation (52). Restricting a positive cq state to accepted classical branches cannot increase its absolute guessing probability, so the same bound holds for the accepted substate (Fact 7). Theorem 19 (Efficient committer-side state simulation). Assume Equation (48) or the isolated one-block conditions of Lemma 5. For every admissible QPT committer A, the QPT simulator of Section 5.6.4 satisfies ρreal,A ≈c ρSIM,A , V V ret R V V ret R A B

A B

uniformly over admissible auxiliary states. Here VA is Alice’s continuing workspace and VBret is Bob’s prescribed verification record. Together with Theorem 18, this establishes committer-side simulation for Definition 10. Proof. Goal and plan. The simulator differs from honest Bob in one message: it sends χ = e ⊕ 1 instead of χ = e, with e = ⟨r, β⟩, and it proves the mode relation with the alternative witness. We show that Alice’s view, together with the reference, is negligibly changed by this switch. The switch is hidden if e is uniform given her view, which is Step 1; the proof of the mode relation must not betray which witness was used, which is Step 2; and everything Bob does afterwards must be a function of public data only, which is Step 3. Step 4 returns from the hybrid EB to the real protocol. Step 1: the parity e is uniform given Alice’s view. At the isolated one-block endpoint, Lemma 5 makes e = β exactly uniform in the accepted pre-r hybrid state; the only nonzero seed is r = 1, so no seed-conditioning error arises. In the general regime, Lemma 15 gives min-entropy in β, and Fact 9 turns it into √ (r, ⟨r, β⟩, VeA ) ≈εhash (r, U1 , VeA ), εhash ≤ 12 21−ksel + O(2−m ) + negl(λ), where the 2−m term pays for restricting to nonzero r. Hence the states with χ = e and χ = e ⊕ 1 are negligibly close in the respective fixed hybrid, and exactly equal at the isolated endpoint apart from inner failure events. Step 2: the mode proof does not reveal the witness. In the equivocal-question experiment both mode statements are true (Lemma 12), so the same uniform ZK-simulation circuit, run on the public statement and Alice’s current state, is an admissible continuation on either side of the switch; it never reads the physical β. Step 3: everything after the proof is public. Bob’s later messages and his receipt depend only on the public transcript, the syntax checks, and the native openings; the private decoder and the selected-XOR decision are never disclosed. The registers that could identify the mode, including β, are discarded at the commitment boundary, so the remaining verification state is a function of the public transcript. SIM’s private computation of b∗ , followed by discarding its working registers, 57

leaves Alice’s marginal unchanged, and opening verification is the same public computation in both modes; by Theorem 18, restricting an ideal opening to b∗ changes the outcome only with negligible probability. Step 4: back to the real protocol. The sequential equivocation and ZK hybrids that relate the real protocol to EB are computational statements in the original leaked execution, so their errors add to the bound of Step 1. Remark 20 (The boundary is essential). The entropy bound is not conditioned on Bob’s private labels: given β, the two modes are immediately distinguishable from (r, χ). Neither that conditioning nor a later honest operation using the retired label vector is part of this proof. The protocol retirement rule makes the post-r continuation argument applicable. 5.6.6

Hiding against a dishonest receiver

This completes the committer-side simulation. We now take Alice to be honest and prove ordinary computational hiding through commitment completion, allowing Bob to retain all his quantum and classical state. A hybrid in which records can be sampled safely For each honest input bit b, define EA (b) by using equivocation for Alice’s initial test-mask commitment and all of her table commitments. Open all required entries to their genuine values. Bob’s commitments and mode proof remain real. Through the hiding boundary, equivocation relates this to the real commitment to b by efficient sequential hybrids with the complete receiver state retained. In EA (b), the initial commitment does not use TA . One may thus sample TA freshly after Bob finishes committing his answers, and then open it correctly using equivocation. Similarly, Alice’s table commitments transmit no input-dependent table data: only their subsequent native openings do so. Statistical binding now defines Bob’s unique possible U, B, J records before the relevant late disclosures. For analysis, these values may be computed without a time bound from their classical transcripts, with canonical defaults for unopenable entries. Every valid native opening agrees with these fixed values. Lemma 16 (Sparse test and random blocks). In EA (b), let Lossglob and Lossi be the global and block-i canonical loss densities against Bob’s fixed effective questions and answers. For suitable fixed repetition-compatible thresholds κtest < κglob < κblk , 

Pr Acctest = 1 ∧



Lossglob > κglob ∨ max Lossi > κblk i



≤ εtest ,

εtest ≤ exp[−Ω(tA )] + m exp[−Ω(N )] + negl(λ). Proof. Privately presample C but leave it unused by the devices and messages until the table turn. At the completed answer-commitment cut, Alice’s raw table, these independent coins, and Bob’s unique possible records determine the canonical Magic Square loss set. Her test set can be sampled afterward in this very experiment. By Fact 6 (hypergeometric case), a loss set above the chosen constant global threshold passes the sparse test with probability exp[−Ω(tA )]. Valid test-coordinate openings equal the fixed records; a missing valid opening only causes rejection. Alice’s subsequent fresh permutation partitions the complement uniformly. Conditional on a bounded global loss density, Fact 6 (hypergeometric case) bounds excessive loss in any block by m exp[−Ω(N )], using a slightly larger fixed threshold. This conditions on classical records only. The only additional error is statistical binding. 58

Hidden pads for the unselected branches Let Accpad denote successful public continuation through the mode proof, before fresh extractor seeds and ciphertexts. Outside binding and modesoundness failure, Lemma 13 defines a unique β with Yj∗ = βi

(j ∈ J i ),

χ = ⟨r, β⟩.

Thus the hidden branch in block i is Hi = 1 − βi . This is the transcript-defined hidden branch of (2) for a selector contained in one question class. Lemma 17 (Ordered hidden pads with ordinary inner commitments). Assume Equation (49). In (j) EA (b), let ρbVB R be the subnormalized Accpad substate with FiHi replaced by independent uniform bits for i ≤ j, retaining Bob’s complete state VB . Then m X 1

2 j=1

(j−1)

(j)

ρbVB R − ρbVB R 1 = negl(λ).

Proof. Goal and plan. This is the argument of Lemma 9, with three differences. The experiment is the equivocal-commitment execution EA (b) in place of the ideal CP execution, so that Alice’s table commitments are independent of the source. Mode soundness (Lemma 13) fixes one question class per selector, so the hidden branch is 1 − βi . And the audit sets have exactly naud coordinates, so the audit charge is 3mnaud . The steps follow the same order: delete the bad substates, take the raw entropy of the target block from Lemma 1, charge the disclosures of Table 4, and hash. Step 1: delete the bad substates. The entropy bound holds on the event that the sparse test certified few losses, that Bob’s commitments are binding, and that his mode proof is sound. The complementary substates have negligible total probability, by Lemma 16 and soundness. We delete them in the original hybrid, before any leakage-guessing reduction, so that the negligible smoothing cost is not multiplied by a guessing factor. Step 2: the frozen record. The game requires Dave’s answers and selector to be fixed before Alice’s questions arrive. Here Bob’s classical commitment transcripts freeze B, J before Alice’s table disclosures. Their unique possible values are assigned by an unbounded computation inside the statistical argument, which is allowed because the repetition theorem places no computational restriction on Dave. An inaccessible copy of the original classical transcript fixes this assignment through every later local operation, and native openings cannot change it. Step 3: remove the leakage, keeping the causal order. We apply Fact 11 to a guessing event, which costs 2ℓ bits. After this reduction, the fresh post-output partition can be viewed as private randomness that was sampled earlier and is revealed at its prescribed time, and the systems of the other coordinates remain on their original sides. Every honest-controller message before the late table disclosures is then either independent of the source or one of the audit messages charged in Step 5. In particular, the equivocal table-commitment algorithms are source-independent local channels on the receiver’s workspace; this is what the experiment EA (b) is for. Step 4: raw entropy of the hidden string. In the target block i, a guess of Zi1−βi together with the frozen Bj [Xj ] determines two entries of Alice’s row on every active, non-losing selected coordinate. They are different entries, because the effective question fixed by the masked record and the offset is βi on J i . The selected set is frozen before the late questions, so Lemmas 1 and 20 apply and give the raw entropy term γraw N . Step 5: charge the disclosures. Everything else that depends on the source is guessed at its first appearance. The audit tables reveal at most 3mnaud answer bits in total. The one-bit test decision is guessed when it is sent; the flag debit below includes it. The opened pair (C, X) costs nothing: it is the late input that the game allows, and it never supplies a raw question at an erased coordinate. 59

The selector is already immutable before these openings. Both syndromes across all blocks cost at most 2ρmax mrEC N + O(m log N ) bits, and the remaining flags and the other 2m − 1 ciphertext bits cost O(m). These are the debits in Equation (49). Step 6: hash and iterate over the blocks. For the replacement of one target ciphertext, we append all other seeds and ciphertexts, in the fixed hybrid order. Alice’s shares are independent of the source conditional on the preceding public statement, so they are included as analysis registers at no cost. The target seed remains fresh, because no other ciphertext or syndrome uses it. Fact 8 therefore makes the hidden pad, and hence its ciphertext, close to uniform jointly with the retained state. Iterating over the m blocks costs only a polynomial factor in the negligible smoothing and hashing errors. The public prefix already contains Accpad , and abort branches are treated identically in the two experiments. Theorem 21 (Computational hiding). Under Equation (49), for every admissible QPT receiver B and auxiliary state, b=1,B ρb=0,B at commitment completion. VB R ≈c ρVB R Proof. In the hidden-ciphertext hybrid of Lemma 17, consider the remaining branch payloads. For each fixed pre-payload record, (Piβi )m i=1 is uniform subject to

M

Piβi = (χ ⊕ ⟨r, β⟩)b = 0.

i

This distribution is independent of b. It remains so jointly with the genuine raw strings and the receiver’s side information: the shares were sampled independently subject to the displayed constraint. Both syndromes and all seeds are independent of the committed bit. The replaced hidden ciphertexts are uniform. Thus the resulting complete commitment-phase receiver state is identical for b = 0 and b = 1, outside the deleted bad substates. Apply Lemma 17 in both directions and restore Alice’s genuine commitments by equivocation security. The endpoints of each computational transition are efficient executions for a specified bit. 5.6.7

Correctness, composition, and scope

The commitment theorem is now assembled from the preceding lemmas, together with correctness and the continuation properties that the compiler needs. Theorem 22 (Block commitment theorem). Assume qOWFs, the equivocation and ZK interfaces of Section 5.6.2, and the parameters of Section 2.4 or Section 5.6.2. Under the prescribed physical and retirement interfaces, Protocol 4 satisfies Definition 10 with SIM ∈ QPT,

textract ≤ tcommit-end ,

εagree = negl(λ).

For independent honest coordinate faults satisfying (47), εcor = negl(λ). The entropy inputs are Theorem 4 and Fact 11. Proof. State preservation and accepted-opening agreement are Theorems 18 and 19; hiding is Theorem 21. For honest parties, by Fact 6 both candidate sizes concentrate around (N − naud )/3, simultaneously over all blocks. The sparse test fails with probability exp[−Ω(tA )]. Each audit has size naud ; with the stipulated honest noise margin its failure probability is exp[−Ω(naud κaud )]. The scale condition makes a union bound negligible. The mode statement is true, and native openings, syndromes, and payload equations are verified by construction. After acceptance of the audits, honest opening entails no further noisy device operation. 60

Sequential composition here means polynomially many sequential subprotocol phases with arbitrary quantum auxiliary state, references, and delayed openings under the specified retirement interface. Completed inner commitment and proof segments can be replaced one at a time; the next segment is an efficient continuation. Pending honest states from other sessions stay untouched references. The resulting per-segment error sums negligibly. Concurrent interleaving of rewound segments, adaptive corruption exposing discarded receiver records, and extra leakage during later classical phases are outside the stated model. 5.6.8

The second equivocation layer

This subsection proves Theorem 15. Write ε for the largest of the negligible errors of Protocol 4 in Definition 10(i)–(iii); by item (iii) they hold for the 5k sequential calls of Protocol 6, with delayed openings and in both roles, and every call has its own device batch and leakage window (Definition 13). Proof of Theorem 15. What changes from [BCKM21, Section 4] is that the receiver commits to its challenges before the base commit phases, so that the simulator extracts them and never rewinds across a device call; the extraction rule, which reads the bit off the first iteration whose unchecked pair is sound, replaces their majority vote. Step 1: correctness. Each of the 5k honest calls is correct except with negligible probability (Theorem 22). On their intersection both checked bits of iteration i equal di,ci , and the bit opened in iteration i equals di,1−ci = b ⊕ ei . Step 2: receiver simulation. Fix a QPT Bob and a bit b, and consider four experiments. G0 is the real commitment to b followed by the honest opening. G1 replaces honest Alice in every reversed call by the committer-side simulator of Protocol 4, which outputs c∗i , and stops with FAIL if Bob validly opens some ci ̸= c∗i . By Definition 10(i) and (iii), applied to the k reversed calls in order, G0 ≈c G1 and Pr[FAIL] ≤ kε. G2 samples αi at the start of iteration i instead of at the opening; Alice’s messages before the opening do not depend on αi , so G2 and G1 are identically distributed. Unless FAIL occurs, session (i, 1 − c∗i , 1 − αi ) is never opened. G3 commits in that session to 1 − di,1−c∗i . For each i, this changes the bit of one honest call whose record stays unopened, so Definition 10(ii) and (iii) give G2 ≈c G3 by k hybrids. In G3 , put di = di,1−c∗i ⊕ αi . Session (i, 1 − c∗i , 0) holds di and session (i, 1 − c∗i , 1) holds 1 − di ; moreover ei = b ⊕ di,1−c∗i and αi = di ⊕ b ⊕ ei . Since di,1−c∗i and αi are independent and uniform, so are di and ei . Hence G3 is the simulated experiment of Protocol 7, whose commit phase does not use b. The simulator touches Alice’s device shares only by running honest calls and the simulator of Protocol 4, which keeps the genuine device execution; every rewinding step lies inside a classical segment of that simulator. Step 3: committer simulation, state. Fix a QPT Alice. Replace honest Bob in her 4k calls, in order, by the committer-side simulator of Protocol 4. Bob’s pending challenge commitments are honest sender states of other sessions, which item (iii) leaves untouched. By items (i) and (iii) the continuation states are computationally indistinguishable. Let Agree be the event that every accepted opening of a session (i, p, q) equals d′i,p,q ; then Pr[¬Agree] ≤ 4kε. Step 4: committer simulation, the extracted bit. Suppose an opening to b is accepted and Agree holds. If b∗ ̸= ⊥, the session opened in iteration i0 holds d′i0 ,1−ci ,0 = d′i0 ,1−ci ,1 , so b = 0 0 ei0 ⊕ d′i0 ,1−ci ,0 = b∗ . Suppose b∗ = ⊥ instead. Call a pair sound if its two extracted values are 0 equal bits. In every iteration, the unchecked pair is then unsound, while on Agree the checked pair, which opened to equal bits, is sound. Let Badt be the event that, in each iteration i ≤ t, exactly one pair is unsound, in position πi , and ci = 1 − πi . The position πt is computed from d′t,·,· before ct is 61

opened, and Badt−1 is determined earlier still. Consider the receiver of the reversed call for ct that runs this experiment up to that point and guesses ct = 1 − πt . Since ct is uniform, Definition 10(ii) and (iii) give, for pt = Pr[Badt ], pt ≤ 21 pt−1 + ε,

hence

pk ≤ 2−k + 2ε.

An accepted opening to b ̸= b∗ implies ¬Agree or Badk . With k = sλ , Pr[an opening to b ̸= b∗ is accepted] ≤ 2−sλ + (4k + 2)ε = negl(λ). Step 5: continuations and resources. Both simulators act call by call and keep every other pending honest state as an untouched reference, so item (iii) is inherited from Protocol 4. Each call uses the batch size of Theorem 14; there are 5sλ calls. 5.6.9

Coin tossing

The two simulators of Protocol 7 give the two simulations directly. Proof of Corollary 16. Correctness. With honest parties, both output a ⊕ b′ , which is uniform, unless the commitment fails, which has negligible probability by Theorem 15. Corrupt Alice. The simulator receives c. It runs the committer-side simulator of Protocol 7 and obtains a∗ . It sends b′ = c ⊕ a∗ if a∗ ∈ {0, 1} and a uniform b′ otherwise, verifies Alice’s opening as Bob does, and answers deliver if the opening is accepted and abort otherwise. By Definition 10(i) the continuation state is computationally indistinguishable from the real one. Since c is uniform and independent of everything before Step 2, so is b′ . An accepted opening is a = a∗ except with negligible probability, and then the real output a ⊕ b′ equals c. Corrupt Bob. The simulator receives c and runs Simcom of Protocol 7. If Bob sends no bit, it answers abort. Otherwise it runs Simopen (c ⊕ b′ ) and answers deliver. To compare with the real execution, first replace honest Alice, for her uniform a, by Simcom followed by Simopen (a). Definition 11(ii′ ) holds for each fixed a and for every QPT receiver, in particular for one that sends b′ between the two phases; hence Bob’s final state, jointly with Alice’s output a ⊕ b′ and R, changes only negligibly. In the resulting experiment, a is first used after b′ is fixed, so c := a ⊕ b′ is uniform and independent of the commit-phase view and of b′ , and a = c ⊕ b′ . This is the simulated experiment. Both simulators use the honest party’s device shares only through the simulators of Protocol 7. The statement for n tosses follows from Theorem 5, applied to the outer protocol that calls ideal(CT) n times and aborts at the first ⊥.

6

The complete construction and secure computation

This section composes the three reductions of Sections 3 to 5 into DI OT from qOWFs and derives the MPC corollary. The CP-hybrid OT reduction covers both parameter regimes. To obtain the complete construction, we instantiate its records through the classical compiler and fresh DI BC sessions. The following invocation rule keeps the physical guarantees valid at each substitution. Definition 13 (Device invocations in the compiled protocol). An admissible compiled schedule satisfies the following.

62

(i) Batches and budgets. It consists of distinct DI-BC and outer-OT device batches (Bj )j with fresh questions and cost(Lj ) ≤ ℓj ,

X

ℓj ≤ ℓ

when a global budget ℓ is imposed.

j

Each budget covers all blocks, adaptive communication, and routing in that batch. (ii) Hypotheses at every invocation. Every reached invocation, including in replacement hybrids, satisfies its input and device hypotheses; arbitrary initial entanglement is permitted subject to those hypotheses. (iii) Timing. Classical phases lie outside device windows and never interrupt an active equivocation or proof-simulation segment. (iv) Isolation. Pending trusted opening records remain private, other device batches remain isolated, and the caller is accessed only through the prescribed classical interface. (v) Commitments and retirement. Commit phases and delayed openings satisfy Definition 10; retired honest devices are neither reused nor exposed to continuations. Choosing every batch to tolerate ℓ suffices for a global budget ℓ. Theorem 23 (Robust DI OT from qOWFs). Assume qOWFs, Definition 13, and independent honest active-coordinate faults satisfying (7). Composition of Theorems 6, 12 and 14 gives a polynomial-time DI realization P of one-bit OT with ∀ static QPT P∗ ∃ QPT Sim ∀ η R : RealP,P∗ (η R ) ≈c IdealOT,Sim (η R ). The error is auxiliary-input-uniform for either corruption, and the realization admits efficient sequential composition. Its regimes are leakage per call honest receiver honest-fault tolerance 0 coordinate-local Ω(1) polylog(λ) joint instruments 1/ polylog(λ). Total device use, computation, and communication are polynomial in λ. The first regime uses m = 1 and constant audit and decoding rates in every DI-BC and OT call; the second uses the general block parameters. Outline. Compose Theorems 6, 12 and 14 by Theorem 5; the invocation rule preserves each premise. Section 6.1 gives the proof. Outline for Corollary 2. Use the classical OT-hybrid MPC protocol of Ishai, Prabhakaran, and Sahai [IPS08], quantum lifting [Unr10], and sequential replacement by Theorem 23. Section 6.1 gives the full argument.

63

6.1

Proofs of the complete construction and the MPC corollary

This subsection assembles the three reductions into Theorem 23, derives the MPC corollary, and records one concrete polylogarithmic parameter choice. Full proof of Theorem 23. First use Theorem 14 in each source call, with the other pending honest states retained as references. Its phase-local simulator meets item (iii) of Definition 10; the call schedule excludes interruption of a rewound segment. Theorem 12 therefore implements the CP commitment, certified-projection, and predicate interface. Its stateful substitution retains all pending records and outer state. The compiler’s classical operations never touch the outer device batch, so replacing these records with ideal CP leaves the applicable OT device experiment unchanged. Apply Theorem 6 and then Theorem 5 to completed OT calls. If the compiler uses q = poly(λ) BC sessions, each replacement has a uniform negligible error and a QPT simulator; their sum and total running time retain these bounds. The same union bound applies to honest failures. Use the smaller of the constant noise thresholds of both DI reductions at the isolated endpoint. In the general regime, choose the block parameters to meet both BC and OT entropy inequalities for every permitted budget, and use the smaller resulting inverse-polylogarithmic threshold. Classical controllers and commitment algorithms introduce no additional noisy quantum operation. of Corollary 2. Step 1: the outer protocol. Use the classical statistical OT-hybrid MPC protocol of Ishai, Prabhakaran, and Sahai [IPS08], including their statistically UC-secure string-OT to bit-OT reduction [IPS08, Section 2]. Use its public polynomial clock and the stated length/delivery convention. An abort before OT input submission withholds the corrupt input; an abort after corrupt receiver output is a stop after that standard OT output. A missing completion signal triggers the prescribed absorbing outer abort. Honest final delivery follows the same adversarially suppressible interface. For reactive outputs this rule applies only to future delivery. Thus the staged OT interface in Definition 7 adds no delivery guarantee to the target functionality. Unruh’s quantum lifting theorem makes this classical hybrid quantum secure [Unr10, Theorem 15 and Section 6]. Schedule its pairwise calls sequentially and replace each by Theorem 23. All other honest outer registers remain untouched during a call. Use private authenticated channels, pad each call’s traffic to its public polynomial bound, and release only its prescribed input–output interface to the caller. Internal transcripts and honest call-local device systems are retired. The same current device share is supplied through its declared interface in each replacement; future shares remain protected. The final simulator retains these interfaces, so the conclusion is resource-relative. Step 2: calls with one corrupted endpoint. Let C ⊊ [p] be the corrupted set. In a call with exactly one endpoint in C, the coalition plays that endpoint: its joint workspace, including the workspaces and device shares of the other corrupted parties, is the corrupt workspace of Definition 2. Retain the honest parties’ states and the pending outer registers in the reference and apply Theorem 5. Classical call inputs may be correlated with this reference. Conditional on each input value x and reached boundary, the stated invocation hypothesis supplies an admissible extension. The same simulator and the same negligible bound νf work for all x. For any induced QPT test D, put dx := Pr[D(Realx ) = 1] − Pr[D(Idealx ) = 1]. Linearity and the triangle inequality give Pr[D(Real) = 1] − Pr[D(Ideal) = 1] =

X

(53)

px dx

x

≤

X x

64

px |dx | ≤

X x

px νf = νf .

(54)

Thus conditioning for this calculation imposes no independence on the outer classical data and requires no input-dependent simulator. Step 3: calls between corrupted parties. In a call with both endpoints in C, both roles and both device shares belong to the adversary, so the call is part of its own computation. In the OT-hybrid execution, the adversary supplies both inputs to such an ideal call and learns nothing that it does not already hold. These calls are therefore not replaced and contribute no error term. Step 4: calls between honest parties. A call with two honest endpoints needs a separate argument. Its complete DI implementation, including source commitment calls, satisfies the stated honestdevice correctness assumptions. Hence its probability of abort or incorrect delivery is at most a uniform negligible εf . Its private, isolated execution acts only on the two honest laboratories and call-local registers. After those registers are discarded, no-signalling leaves the unconditioned external reference unchanged. For fixed classical inputs x, let ox denote the correct ideal output P P x,o x,o x and write the real output–reference state as σOR = o |o⟩⟨o| ⊗ σR . Then o σR = ρxR and P x,o o̸=ox Tr σR ≤ εf . Consequently, 1 2

x,ox x − ρxR 1 + 21 σOR − |ox ⟩⟨ox | ⊗ ρxR 1 = 12 σR

X

x,o Tr σR

(55)

o̸=ox

=

X

x,o ≤ εf . Tr σR

(56)

o̸=ox

Averaging over x preserves this bound. In particular, we do not infer independence of an abort flag from no-signalling: abort branches are included in the negligible error above. This is why the honest-device hypothesis on honest–honest calls is explicit in the corollary. Step 5: summation. For at most q = poly(λ) reached and replaced calls, the hybrid inequality is AdvMPC ≤ νouter + q(νf + εf ) = negl(λ). Uniform bounds apply at every replacement boundary and retain the probability weights of reached branches. The composed simulator is QPT. The outer protocol uses only trusted classical operations; all quantum device use occurs in the substituted calls. A callwise union bound on honest failures preserves both stated robustness regimes. The channel hypothesis is the secure-channel model used in [Unr10, Section 2]. Corollary 24 (A concrete polylogarithmic regime). For constant c ≥ 1 and ℓA , ℓB ≤ logc λ, set a := max{c, 2},

tA := Θ(log3/2 λ),

m := C loga λ,

N := Θ(m3 ).

With Fact 13, sufficiently large C, and the constants of (11), (23) holds with L = Θ(log4a λ),

qdev ≤ cfault /(loga λ log log λ),

ε = negl(λ).

Here cfault > 0 is a sufficiently small fixed constant. The number of CP calls is polylogarithmic; total classical time and communication, including ZK, are polynomial in λ.

7

Proofs of the repetition theorem and the hidden-string lemma

The entropy input of every hiding argument above is Theorem 4; this section proves it, and then Lemma 1, which turns it into the hidden raw string of one block. The game has an ordinary Magic Square question on Charlie’s side and a fresh erasure on Dave’s second-round question. The distinction is essential: Charlie’s first-round operation must not depend on the erasure flag. We prove the threshold statement used by the BC and OT constructions for this game, including selectors produced by an arbitrary joint instrument. The proof reduces to the product-anchored threshold theorem of Kundu and Tan (Fact 5). 65

Notation for the proof. The game is that of Section 2.1. We write Z late for Dave’s second-round question, that is, Z late = ⊥ if C = 0 and Z late = X in if C = 1, so that ⊥ is the erasure symbol ∗ of b and we use the scores X; b 1] = Ain [0, 1]}MS(X in , Y, Ain , B), W = (1 − C) + C 1{A[0,

(57)

Q = JW,

(58)

L = C 1 − MS(X , Y, A , B) . in

in

In the n-copy game, the first-round questions are sampled productwise, both parties may use arbitrary entangled states and joint first-round operations, Dave may use one joint second-round operation on all the revealed questions and his residual state, and C is sampled after all first-round outputs, including J, are fixed. Lemma 18 (Conservative residual guessing bound). Suppose a Magic Square strategy with even-row and odd-column outputs and independent uniform questions has average loss ε. For fixed questions x, y and k ̸= y, after producing its column, Dave’s probability of guessing Ain [k] from arbitrary √ retained quantum memory and the revealed x is at most 1/2 + 15 ε. Proof. We make the normalization in the reflection argument of Fu–Miller [FM18, Section 3 and Appendix B] explicit and use a conservative constant. Purify the state to |ψ⟩ and dilate the local instruments to projective measurements, retaining all local ancillas. Write Fij and Gij for Alice’s P and Dave’s bit reflections, respectively, and let εij be the loss on questions (i, j), so ij εij = 9ε. The parity and consistency relations give, for r ̸= x and k ̸= y, √ ∥(Fij − Gij )|ψ⟩∥ = 2 εij , X√ √ ∥{Fxk , Fry }|ψ⟩∥ ≤ 2 εij ≤ 18 ε. ij

For clarity, the second estimate follows from the following nine-transfer chain on |ψ⟩; an arrow √ labelled ij has norm error at most 2 εij , and unlabelled equalities are exact: 11

01

F00 F11 −→ F00 G11 = −F02 F01 G21 G01 −→ −F02 G21 02

12

−→ −G21 G02 = G21 G22 G12 −→ F12 G21 G22 22

21

−→ F12 F22 G21 −→ F12 F22 F21 = F12 F20 20

10

00

−→ F12 G20 = −F11 F10 G00 G10 −→ −F11 G00 −→ −F11 F00 . Row and column permutations give the general indices above. Fix r = ̸ x, set F = Fxk , H = Fry , G = Gry , and Ps = (I + (−1)s F )/2. Let Πb be Dave’s fullcolumn projectors for input y, so GΠb = (−1)b[r] Πb . For ub = HP0 Πb |ψ⟩ and vb = (−1)b[r] P1 Πb |ψ⟩, orthogonality gives !1/2 X

∥ub − vb ∥

2

=





1 2 (HF + F H) + P1 (H − G)

√ |ψ⟩ ≤ 15 ε,

b

(∥ub ∥ + ∥vb ∥)2 ≤ 2

(∥P0 Πb |ψ⟩∥2 + ∥P1 Πb |ψ⟩∥2 ) = 2.

X

X

b

b

Let σs be Dave’s subnormalized state when the target bit is s, retaining his classical column outcome. Partial trace over Alice removes the conjugation by H, so its b-blocks are the partial traces of ub u†b and vb vb† . Since ∥uu† − vv † ∥1 ≤ (∥u∥ + ∥v∥)∥u − v∥, contractivity and Cauchy–Schwarz imply 66

√ √ √ √ ∥σ0 − σ1 ∥1 ≤ 15 2ε. Fact 10 therefore gives pguess ≤ 1/2 + (15/ 2) ε ≤ 1/2 + 15 ε. Any original instrument’s residual state is obtained from the retained dilation by a local channel, so the same bound applies to it. An input-independent reference may be included in Dave’s initial share; his copied early operation can act as the identity on that reference. Lemma 19 (Selected one-copy guessing). For a Magic-Square strategy with independent X in , Y ←U {0, 1, 2}, let ε = Pr[MS(X in , Y, Ain , B) = 0]. For every Y -controlled first instrument with output (B, J) and arbitrary retained quantum memory, every subsequent row-guessing measurement given X in and that memory satisfies √ b 1] = Ain [0, 1]] ≤ 1 Pr[J = 1] + 15 ε. Pr[J = 1, A[0, (59) 2 For the scores in (58),

√ EQ ≤ s∗ EJ + 15 EL,

1 + δ∗ . (60) 2 Proof. We use Lemma 18, a conservative form of the residual-guessing argument of Fu–Miller [FM18]. Coarsen the first instrument’s public output from (B, J) to B and retain J as part of Dave’s memory. The lemma includes arbitrary instruments and all retained ancillas, so its pointwise estimate applies to this residual state. For each y ∈ {0, 1, 2}, fix k(y) = (y + 1) mod 3. Complete the guessed two-bit row to even parity, b b b ⊕ A[1]. b writing A[2] = A[0] Consider the following allowed bit guess: if J = 1, output A[k(y)]; if J = 0, output an independent fair bit. Write p = Pr[J = 1]. Averaging the cited pointwise inequality over the uniform first questions gives s∗ :=

b 1] = Ain [0, 1]] + 1 (1 − p) Pr[J = 1, A[0, 2 b ≤ Pr[J = 1, A[k(Y )] = Ain [k(Y )]] + 12 (1 − p)

√ = Pr[the completed bit guess is correct] ≤ 12 + 15 ε.

(61)

Subtracting (1 − p)/2 proves (59). Imposing the additional Magic Square check can only reduce its left side. Since C is independent of the complete first-round experiment, the same p occurs on its two branches and EL = (1 − δ∗ )ε. Thus √
EQ ≤ δ∗ p + (1 − δ∗ ) p/2 + 15 ε √ √ p = s∗ p + 15 1 − δ∗ EL ≤ s∗ p + 15 EL. (62)

Fact 5 (Two-round product-anchored threshold theorem [KT23, Definition 3 and Theorem 29]). Let G be a two-round game with finite alphabets in which the first-round questions to Charlie and Dave are independent, both first-round answers are fixed before the second round, and only Dave receives a second-round question. That question is ⊥ with a fixed probability δ∗ > 0, independently of the first-round questions, and otherwise consists of Charlie’s first-round question together with an additional finite-valued question. Let Vi indicate that copy i is won. For every v ≥ ω ∗ (G) and every fixed ξ > 0 with v + ξ < 1, there are constants cKT > 0 and nKT , depending only on δ∗ , ξ, and the alphabet sizes, such that every strategy for n parallel copies, with arbitrary entanglement and arbitrary quantum memory retained between the two rounds, satisfies Pr

" n X

#

Vi ≥ (v + ξ)n ≤ 2−cKT n

i=1

67

(n ≥ nKT ).

(63)

Dave’s first-round answer alphabet below is (B, J), which is finite. We take the first-round predicate identically one and place all checks in the second-round predicate. Proof of the threshold bound. Recall s∗ = (1 + δ∗ )/2, so the hypothesis of Theorem 4 reads s∗ ρ < γsel < ρ. All constants chosen below depend only on δ∗ , ρ, γsel . Proof of Theorem 4. Goal and plan. We must show that a strategy which keeps its Magic Square losses below ηsel n, selects at most ρn coordinates, and is correct on at least γsel n of them, succeeds with probability 2−Ω(n) . The tool is Fact 5, which bounds the probability of winning many copies of a product-anchored game. Two things stand between the selector game and that class. First, the selector is Dave’s own choice, so "correct on the selected coordinates" is not a per-copy predicate; Step 1 repairs this by scoring an unselected coordinate with a fair coin, which makes the selection cost Dave exactly what a coin would. Second, the threshold theorem bounds wins, not losses; Step 1 also mixes the Magic Square test with the guessing test at a ratio M : 1, so that a loss costs M points and a selected success earns one. The value of the lifted game is then below one, by the one-copy bound of Lemma 18. Steps 2 and 3 show that the selector event forces a large score in the lifted game, and Step 4 applies the threshold theorem. The constants are chosen so that the M ε √ penalty for losses dominates the 15 ε guessing advantage at every ε, which is the completed square below. Put g = γsel − s∗ ρ > 0, and choose M=



450 + 1, g 

M̄ = M + 1,

ζ=

225 g < , 4M 8

u=

g , 8

ηsel =

g . 8M

(64)

Completing the square gives, for every ε ≥ 0, √ √ 225 15 −M ε− 15 ε − M ε = 4M 2M 

2

≤ ζ.

(65)

Step 1: a binary product-anchored game. We define the lifted game and bound its value. Keep the same first questions and first answers. On C = 0, accept. On C = 1, the verifier samples an independent mode T with Pr[T = test] = M/M̄ and Pr[T = guess] = 1/M̄ , and an independent fair bit Q. It gives Dave the second question (X in , T, Q), and checks

V =

  1,     MS(X in , Y, Ain , B),  1{Q = 0},     

W,

C = 0, C = 1, T = test, C = 1, T = guess, J = 0, C = 1, T = guess, J = 1.

(66)

This is a game of the class in Fact 5, and the timing is what puts it there: the anchor C is sampled after (B, J) are frozen, so it is independent of both first questions and of the selector; all output alphabets are finite; and neither C nor T, Q is available before (B, J) is fixed. Had the erasures been sampled before the selector, Dave could have selected only unerased coordinates and the anchor would no longer be independent. The coins T, Q are part of the second-round question, so the predicate is a deterministic function of questions and answers. For any one-copy strategy let p = Pr[J = 1], and let ε be its first-round Magic Square loss. The first-round experiment does not depend on T, Q, C. On the guess branch, the final measurement

68

may depend on Q; Lemma 19 holds for each of these measurements. Therefore √ M (1 − ε) + (1 − p)/2 + p/2 + 15 ε Pr[V = 1 | C = 1] ≤ √ M̄ M + 1/2 + 15 ε − M ε M + 1/2 + ζ = ≤ . M̄ M̄

(67)

Consequently

M + 1/2 + ζ < 1. (68) M̄ Here ζ < g/8 < 1/16, since g < (1 − s∗ )ρ ≤ (1 − δ∗ )/2. Step 2: the two anchor counts. The selector event speaks of all coordinates, whereas the lifted score only counts unerased ones, so we need the erasures to be typical both overall and inside the selector. For the given parallel strategy, define ω ∗ (G) ≤ v := δ∗ + (1 − δ∗ )

N0 =

(1 − Ci ),

NJ,0 =

X i

Ji (1 − Ci ).

X

(69)

i

Conditional on the entire frozen J, the bits 1 − Ci remain independent Bernoulli variables of mean δ∗ . Hence the additive form of Fact 6 gives 2

Pr[N0 < δ∗ n − un] ≤ e−2u n ,

(70)

−2u2 n

(71)

Pr[NJ,0 > δ∗

i Ji + un] ≤ e

P

.

For the second inequality, a fixed selector of size k > 0 gives the bound 2 2

2

e−2u n /k ≤ e−2u n . 2

At k = 0, the bad event is empty. Write T for the two typical events. Thus Pr[T c ] ≤ 2e−2u n . Step 3: selected success implies a large binary score. We show that on the selector event, with typical erasures, the lifted score exceeds the threshold (v + ξ)n by a constant fraction of n. Extend the given parallel strategy to the binary game by ignoring all the added T, Q coins in its final guessing map. It receives the same erased question vector, so this is a legal strategy with the b Conditional on that full classical transcript, the binary same distribution of (X in , Y, Ain , B, J, C, A). P P scores Vi are independent. Let µV be their conditional mean sum. Set NJ = i Ji , NQ = i Ji Wi , P and NL = i Li . Expanding the four cases in (66) yields M̄ µV = M̄ N0 + M (n − N0 − NL ) + 12 (n − N0 − NJ + NJ,0 ) + (NQ − NJ,0 ) = (M + 12 )n + 21 N0 − 12 NJ − 21 NJ,0 + NQ − M NL , M̄ vn = (M + 12 )n + 21 δ∗ n + (1 − δ∗ )ζn.

(72) (73)

Let E be the event in (1). On E ∩ T , the difference satisfies, line by line, M̄ (µV − vn) = 12 (N0 − δ∗ n) + NQ − 12 NJ − 12 NJ,0 − M NL − (1 − δ∗ )ζn ≥ NQ − s∗ NJ − M NL − un − (1 − δ∗ )ζn
5g ≥ g − M ηsel − u − (1 − δ∗ )ζ n ≥ n. 8

(74)

Take ξ = g/(4M̄ ). It is positive and satisfies v + ξ < 1 because 1−v =

(1 − δ∗ )(1/2 − ζ) 7(1 − δ∗ ) g > . > M̄ 16M̄ 4M̄ 69

(75)

The mean in (74) exceeds (v + ξ)n by at least 3gn/(8M̄ ). The additive form of Fact 6, applied conditionally on the transcript, therefore gives "

Pr E ∩ T ∩

( X

)#

Vi < (v + ξ)n

i

3g ≤ exp −2 8M̄ 

2 !

n .

(76)

Step 4: apply Fact 5. A score above (v + ξ)n is exactly what the threshold theorem forbids, so the selector event is contained in the union of the three rare events. Combining (63), (71), and (76), we obtain  !  3g 2 −2u2 n −cKT n n . (77) Pr[E] ≤ 2e +2 + exp −2 8M̄ Let

(

c0 = min

2u2 2(3g/(8M̄ ))2 , cKT , ln 2 ln 2

)

> 0,

csel = c0 /2.

(78)

The right side of (77) is at most 4 · 2−c0 n ≤ 2−csel n whenever n ≥ 4/c0 . Increase n0 to cover this condition and the finite-size requirement of (63). Every choice depends only on the fixed game and thresholds, not on the strategy or its dimension. The theorem generalizes the threshold theorem of Kundu and Tan [KT23] to a receiver-chosen selector, and the one-copy bound of Fu and Miller [FM18] is its only game-specific input; the lift, the late erasures, and the selector scoring are new.

7.1

Min-entropy of the hidden raw string in one block

This subsection proves Lemma 1. The argument concerns the game only; tests, audit disclosures, and leakage are charged in the protocol proofs (Table 4). It applies also when the entire batch has only one block. For the game’s odd-column alphabet, replace an analysis record Bj∗ by B j = (Bj∗ [0], Bj∗ [1], 1 ⊕ Bj∗ [0] ⊕ Bj∗ [1]), using 001 for malformed records. Every original Magic-Square-winning coordinate already has odd column parity, so B j = Bj∗ there. The replacement cannot increase loss and preserves every successful reconstruction coordinate. Actual committed records and opening checks are unchanged. Lemma 20 (Constant-density bucketing). Fix 0 < rmin ≤ rmax ≤ 1 and s∗ = (1 + δ∗ )/2. For sufficiently small constants h, η > 0, cover [rmin n, rmax n] by finitely many buckets [rj n, (rj + h)n) and choose s∗ ρj < gj < rj − η, ρj = min{rj + h, rmax }. If η < minj ηsel (ρj , gj ), then ∃c > 0, n0 such that every admissible strategy with a pre-late-question selector K, rmin n ≤ |K| ≤ rmax n, satisfies, for n ≥ n0 , 

Pr

n X



Lj ≤ ηn ∧

j=1

X

Wj ≥ |K| − ηn ≤ 2−cn .

j∈K

Here Lj , Wj and ηsel are as in Theorem 4. Proof. First choose h > 0 with (1 − s∗ )rmin > s∗ h, and fix gj strictly between s∗ ρj and rj . Apply Theorem 4 to these finitely many fixed pairs (ρj , gj ). Then choose η > 0 below both minj (rj − gj ) and all resulting loss constants. Taking the minimum exponent and a finite union bound proves the claim. All choices precede n and the adversarial state. 70

In the protocols, Dave’s question string is the effective question string, defined as follows. Let trit(00) = 0, trit(01) = 1, trit(10) = 2, and trit(11) = 0 for analysis. Write Uj = trit(YjB,∗ ) and Yj∗ = YjA + Uj . The original two-bit record is retained, and actual projection and syntax checks still reject the encoding 11 wherever it is opened. With Y = Y ∗ and B = B, (2) and (3) define H and K from the immutable early record. Proof of Lemma 1. For either target, a correct guess supplies the same raw answer bit on every active coordinate. On an active non-losing coordinate j ∈ K, Dave’s fixed answer supplies Aj [Yj ] = Bj [Xj ]. A correct guess for ZH supplies the different entry Aj [H]. If Yj = 1 − H, both independent row bits are known; if Yj = 2, the prescribed row parity supplies the remaining bit. Thus a successful guess yields a legal late answer for Aj [0, 1] on every such coordinate. Anchors score automatically. On Good the induced selected-win count is at least |K| − ηn. Because K is determined by the frozen (Y, B, J) before the late questions, it is an admissible selector. Its density is between ρmin /2 and ρmax . Apply Lemma 20 and shrink c > 0 to absorb the fixed number of buckets. This gives (4) for every late map, including a map acting on arbitrary permitted entangled side information.

Acknowledgements We thank Rishabh Batra for helpful discussions. This project is supported by the National Research Foundation, Singapore through the National Quantum Office, hosted in A*STAR, under its Centre for Quantum Technologies Funding Initiative (S24Q2D0009) and its Advanced Quantum Algorithms and Solutions Funding Initiative (S25Q9DA001 and S25Q9DA002).

AI use disclosure We used OpenAI’s ChatGPT to assist with exploring proof strategies, examining commitment assumptions and security simulations, and identifying potential gaps and inconsistencies. It also assisted with literature searches, drafting and revising the manuscript, and preparing the LaTeX source. We used Anthropic’s Claude to assist with restructuring and editing the manuscript and with drafting parts of it. The authors retain full responsibility for all mathematical claims, proofs, references, and the final manuscript.

71

A

Useful facts

This appendix collects the imported concentration, entropy, leakage, and coding facts in the form in which the proofs use them.

A.1

Concentration and sampling

We use, without further mention, the contractivity of trace distance under quantum channels [Tom16] and closure of computational indistinguishability under efficient postprocessing, which follows by composing the distinguisher. Fact 6 (Chernoff–Hoeffding bounds [Hoe63, SSS93]). Let X1 , . . . , Xn ∈ {0, 1} be independent, P X = i Xi , and µ = E X. For 0 < ϵ ≤ 1, 2

Pr[|X − µ| ≥ ϵµ] ≤ 2e−ϵ µ/3 . Let B ⊆ [n], |B| ≥ βn, and include each i ∈ [n] in T independently with probability δ. For fixed ϵ ∈ (0, 1) and 0 ≤ κ ≤ (1 − ϵ)β, Pr[T = ∅ ∨ |T ∩ B| < κ|T |] ≤ exp[−Ω(δβn)]. Consequently, δβn = ω(log λ) gives negl(λ) error. For uniform T ∈ [n] s , the same bound holds with s in place of δn. In additive form, for independent X1 , . . . , Xn ∈ [0, 1] and t > 0,

2

2

Pr[X − µ ≥ tn] ≤ e−2t n ,

Pr[X − µ ≤ −tn] ≤ e−2t n .

All bounds of this fact also hold when X1 , . . . , Xn is a uniform sample without replacement from a finite population [Hoe63, Section 6]; we refer to this as the hypergeometric case.

A.2

Min-entropy and seeded extraction

Definition 14 (Conditional min-entropy [KRS09]). For a subnormalized cq-state ρXE = ρE x , define X Tr(Mx ρE pguess (X | E)ρ := max x ), P Mx ⪰0 x

Mx =IE

x |x⟩⟨x|⊗

P

x

Hmin (X | E)ρ = − log pguess (X | E)ρ , Hεmin (X | E)ρ :=

sup ρ e cq, subnormalized P (ρ e,ρ)≤ε

(79)

Hmin (X | E)ρe,

where P is purified distance and log 0 = −∞. Fact 7 (Min-entropy calculus [Tom16]). For a subnormalized cq-state ρXEL with classical L, |L| ≤ 2ℓ

=⇒

Hεmin (X | E, L)ρ ≥ Hεmin (X | E)ρ − ℓ.

For cq-substates 0 ⪯ σ XE ⪯ ρXE , pguess (X | E)σ ≤ pguess (X | E)ρ , Hmin (X | E)σ/p ≥ Hmin (X | E)ρ − log(1/p), 72

p := Tr σ > 0.

Moreover, Tr(ρ − σ) ≤ δ implies P (ρ, σ) ≤ −k

pguess (X | E)σ ≤ 2

√

2δ,

√

2δ =⇒ Hmin (X | E)ρ ≥ k.

The normalization inequality is unsmoothed; the last implication accounts explicitly for discarded bad branches. Fact 8 (One-bit linear extractor [Tom16]). For N ≥ 1, the explicit linear family ExtN : {0, 1}N × {0, 1}tN → {0, 1},

tN = N,

ExtN (x; R) = ⟨x, R⟩F2

has uniform Boolean depth O(log N ). Let N be public and R | N ←U {0, 1}N independently of sm XE | N . If Hεmin (X | E, N ) ≥ k, then (ExtN (X; R), R, E, N ) ≈εext (U1 , R, E, N ), √ εext ≤ 2εsm + 12 21−k . For fixed N , take k = αN ; for either schedule used below, k = ω(log λ) and negligible εsm imply εext = negl(λ). The independent public seed incurs no entropy debit. The variable-length bound follows by length-block decomposition and Cauchy–Schwarz. Fact 9 (Quantum leftover hashing [Tom16]). Let ρXE be a subnormalized cq-state, X ∈ {0, 1}m , and R ←U {0, 1}m independently of XE. For hR (X) = ⟨R, X⟩F2 and Hεmin (X | E)ρ ≥ k, 1 √ 1−k 1 ρRhR (X)E − ρR ⊗ U1 ⊗ ρE ≤ 2ε + 2 . 1 2 2 Here ρR is normalized uniform and ρE retains the branch trace. Thus k = ω(log λ) and ε = negl(λ) give negligible error. Fact 10 (Helstrom bound; see, e.g., [Wil17]). Let σ0 , σ1 ≥ 0 act on one space, with Tr(σ0 + σ1 ) = 1. The maximum, over all measurements, of
the probability of guessing s from σs , where s occurs with probability Tr σs , equals 21 1 + ∥σ0 − σ1 ∥1 .

A.3

Bounded communication and codes

Fact 11 (Eliminating bounded interactive communication, Jain–Kundu [JK25]). Let S exchange at most c classical bits and q qubits within a specified causal window, with arbitrary prior entanglement. The classical budget includes adaptive routing, direction, lengths, continuation, and stopping; fixed public schedules have zero cost. For every event E, there exists a no-extra-communication strategy S0 satisfying Pr(E) ≥ 2−(c+2q) Pr(E) ≥ 2−2b Pr(E), b := c + q. S0

S

S

S0 preserves the prescribed order, immutable records, and all registers untouched by leakage. Teleportation replaces each qubit with two correction bits; guessing the padded self-delimiting classical transcript gives the bound. Independent reduction coins incur no debit. We use the cited phase-local argument on the device input–output interval.

73

Fact 12 (High-rate binary codes [GRS25]). For every fixed r ∈ (0, 1), there exist constants δr , τr > 0, with 2τr < δr , and explicit binary linear codes Cn ≤ Fn2 such that dim Cn ≥ (1 − r)n, dmin (Cn ) ≥ δr n, n−dim Cn n Synn : F2 → F2 , Decn (Synn (e)) = e (wt(e) ≤ τr n). Encoding and syndrome decoding take poly(n) time. Fact 13 (Binary BCH codes [Hoc59, BRC60, HP03]). For N0 = 2s − 1 and 1 ≤ t < 2s−1 , the primitive narrow-sense binary BCH code C of designed distance 2t + 1 satisfies N0 − dim C ≤ st,

dmin (C) ≥ 2t + 1,

Dec(Syn(e)) = e

(wt(e) ≤ t),

with polynomial-time syndrome decoding. Information-coordinate shortening to length q preserves these bounds; the decoder zero-extends to the parent code [HP03, Section 1.5.3, Theorems 5.1.1 and 5.1.7(ii), and Section 5.4]. For every q ∈ [ρmin N, ρmax N ], choose a parent N0 ≥ q with N0 = Θ(q) and st ≤ q, and take q − dim Cq st cEC ≤ ≤ rEC = , q q m   1 t . τEC = = Θ q m log N

cEC q q t= =Θ , ms m log q 







rcode :=

(80)

Here Cq is the shortened code, and the displayed choice has t ≥ 1 for sufficiently large λ. These choices are uniform for the polylogarithmic m, N in Section 2.4; q = |J i | need not be a primitive BCH length.

B

Feasibility of the common parameter schedule

This appendix verifies that the schedule of Section 2.4 satisfies every inequality the reductions impose, in both regimes. Proof of Lemma 2. First fix the selector window and the positive repetition constants. Choose caud , cEC small enough that all audit answers and both syndromes across the batch cost less than half the smaller raw entropy bound. These costs are O(caud N + cEC N ) for every m, including one. The remaining debits are 2ℓ + O(m log N ); (5) makes them o(N ). Thus both pad budgets leave a fixed positive fraction of N . For m > 1, m − 2ℓ − 3tA − O(1) ≥ sλ + tA − O(1) = ω(log λ), tA = o(m), and N/(m2 log N ) = Ω(m/ log N ) = ω(log λ). Also tA = o(N ) in both regimes. The test error is exp[−Ω(tA )]. Audit errors are at most m exp[−Ω(N/(m2 log N ))] for m > 1 and exp[−Ω(N )] for m = 1. All are negligible. At m = 1, constant redundancy supplies τ0 > 0; choose the audit threshold strictly below ρmin τ0 and the honest-fault rate still lower. At m > 1, make the corresponding choices as fixed multiples of (6). Finally, use Lemma 5 in place of leftover hashing when m = 1.

C

Proof of the BC-to-CP compiler theorem

This appendix proves Theorem 12, deferred from Section 4 because its structure is the standard three-coloring argument, under the source interface of Definition 10. What changes from [GMW91] 74

is the order of the two commitments: the verifier commits to its challenge edge before the prover commits to the coloring, so that the simulator obtains the edge by source-BC extraction rather than by rewinding, and no rewound segment contains a call of the source commitment. All sessions have distinct roles, purpose, and round tags; fixed-length strings are committed bitwise. Honest challenge coins and their opening states stay outside the receiver workspace of every intervening color commitment, as required by the source locality contract. Malformed messages and failed openings cause rejection. The source guarantees include the continuing workspace of pending sessions. All commitments and arguments use security parameter λ, independently of the device counts n, N . The Naor seed length is λ, so for a uniform receiver string the probability of binding failure is at most 2−λ and remains negligible under polynomial union bounds. The internal Naor commitments are those of Fact 2; each record has its own receiver-generated string.

C.1

A challenge-first argument with efficient extraction

We first recall the coloring reduction and then give the protocol and its two simulations. Fact 14 (Witness-preserving reduction to coloring, as used by Goldreich, Micali, and Wigderson [GMW91]). For every NP relation R(x, w) with |w| ≤ poly(|x|), there exist polynomial-time maps f, Enc, Dec such that Hx = f (x) is simple and undirected and, for all x, w, ϕ, R(x, w) = 1 =⇒ Enc(x, w) ∈ Col3 (Hx ), ϕ ∈ Col3 (Hx ) =⇒ R(x, Dec(x, ϕ)) = 1, where Col3 (H) is the set of proper three-colorings of H. Fix R and apply Fact 14. Remove isolated vertices (restoring them with fixed colors for decoding), and add a disjoint edge if needed. Thus Hx has N nonisolated vertices and m ≥ 1 edges. Colors use a fixed two-bit encoding of {0, 1, 2}, with the fourth codeword invalid. Public input: the graph Hx with N nonisolated vertices and m ≥ 1 edges, indexed by [m]. Alice is the prover and knows a proper three-coloring ϕ : V (Hx ) → {0, 1, 2}; Bob is the verifier. Use source BC with distinct round and purpose tags. 1. Bob. Sample e ←U [m] and commit bitwise to its fixed-length binary encoding. 2. Alice. Sample a uniform permutation π of {0, 1, 2}. Commit separately to the two-bit encoding of π(ϕ(v)) for every vertex v. 3. Bob. Open the edge index e. 4. Alice. Verify the native opening and e ∈ [m]; abort on failure. If the indexed edge is {u, v}, open the two committed colors at u, v. 5. Bob. Verify both native openings and require valid, distinct colors. Accept the round iff all checks pass. Repeat these turns sequentially for t = ⌈mλ⌉ rounds, with fresh coins. Reject on a failed round; accept the argument only after all rounds pass. These graph counts are local to the compiler, unrelated to the DI block count. Where each step is used. Steps 1–2: commitments under Definition 10. Steps 3–4: extraction Lemma 21, simulation Lemma 22. Protocol 9: Challenge-first coloring argument using the source BC of Definition 10.

75

Public input: the graph, edge indexing, and round count of Protocol 9. Source extraction means the QPT committer-side simulator of Definition 10. Corrupt Alice; SIM extracts a witness. 1. SIM (challenge). Sample the honest edge e and complete Bob’s edge commitments. Keep their honest sender state untouched while receiving Alice’s color commitments. 2. SIM (colors). Apply source extraction to each color-bit commitment, retaining its openingverification state. Treat a vertex as invalid if either extracted bit is ⊥ or its two-bit code is unused. If the resulting assignment is a proper coloring of Hx , decode and save an NP witness using Fact 14. 3. SIM (continuation). Open the genuine edge e and check Alice’s actual endpoint openings. Continue the prescribed rounds even after saving a witness. Return the saved witness and continuing state; acceptance without a valid witness is the knowledge-error event. Corrupt Bob; SIM simulates without a witness. 1. SIM (challenge). Extract the committed edge e∗ before sending any color commitments. 2. SIM (response). For valid e∗ = {u, v}, sample a uniform ordered pair of distinct colors at u, v and set all other colors arbitrarily to valid values. Commit honestly to this assignment. If e∗ is invalid, commit to any valid assignment. 3. SIM (opening). On Bob’s opening, apply the honest checks; abort for an invalid index or failed opening. Open the two endpoint colors when the index is valid and consistent with e∗ . An accepted inconsistent opening is the source-error event. Repeat for all rounds, retaining every pending session. Where each step is used. Steps 1–3 (extractor): Lemma 21. Steps 4–6 (simulator): Lemma 22. Protocol 10: Challenge-first argument: chronological extractor and witness-free simulator actions. Lemma 21 (Witness extraction). Assume Definition 10. For every QPT prover P ∗ in Protocol 9, b such that, uniformly over admissible auxiliary/refthere is a QPT extractor ExtP ∗ , with output w, erence states, ABR ρABR real ≈c ρExt ,

b∈ Pr [Acc ∧ w / {w : R(x, w) = 1}] ≤ e−λ + negl(λ).

Ext

Here A is the prover’s entire workspace, B contains the honest verifier’s registers retained at the end of the argument, and R is the untouched reference. The comparison omits the extractor’s private witness output. Proof. Use the extractor of Protocol 10: extract the committed colors, decode any proper coloring, and continue the prescribed interaction. Replacing the color commitments one at a time by source simulations gives the joint-state comparison, including abort branches, by Definition 10. The same definition bounds the probability of any accepted opening inconsistent with an extracted color by negl(λ). For soundness, let pr be the probability of passing the first r rounds without obtaining a witness. In the next round, consider only the prefix before the edge opening. Replace the commitment to the uniform edge e by a commitment to a fixed legal edge e0 , keeping e in a private register of the reduction. The extracted assignment is now independent of e, since the color extractors never access the pending challenge’s honest sender state. Every assignment that is not a proper coloring violates at least one edge, including assignments with invalid colors because the graph has no isolated vertices. Thus the probability of reaching this prefix with no witness and an assignment 76

that passes the check on e is at most (1 − 1/m)pr . Source hiding transfers this bound to the original prefix with negligible error: testing the extracted assignment on the known e is QPT, and the modified challenge is never opened. A violated edge can pass the actual round only through an inconsistent color opening. Hence pr+1 ≤ (1 − 1/m)pr + negl(λ),

pt ≤ (1 − 1/m)t + negl(λ) ≤ e−λ + negl(λ).

These are absolute probabilities, so no conditioning on acceptance is needed. The extractor makes polynomially many QPT calls and decodes in polynomial time. Lemma 22 (Witness-free simulation). For every QPT verifier V ∗ of Protocol 9, there is a QPT simulator SimV ∗ such that, uniformly over (x, w) with R(x, w) = 1 and auxiliary states η, sim ρreal V ∗ R (x, w; η) ≈c ρV ∗ R (x; η).

The states include the continuing view and untouched reference R. The same simulator is defined for x ∈ / LR : every consistent valid opening e = {u, v} ∈ E(Hx ) receives colors cu , cv ∈ {0, 1, 2} with cu ̸= cv . Proof. In each round, extract the verifier’s committed edge before sending the color commitments. For a valid extracted edge e∗ , choose an ordered pair of distinct colors uniformly for its endpoints and arbitrary valid colors elsewhere. Commit to this artificial assignment using the honest source algorithms. Continue the verifier’s opening with the saved source state. On an inconsistent opening, record simulation failure; its probability is negligible. On an invalid index or failed opening, abort as the honest prover does. For an extracted invalid value, use any assignment until the opening determines this abort. To justify simulation for a true instance, first replace only the verifier’s challenge commitment by source extraction. Next, condition the description of the hybrid on the extracted edge, without conditioning the error bounds on a rare event. Under a uniformly permuted valid coloring, the endpoint colors are a uniform ordered distinct pair, exactly as in the simulator. All other color commitments are never opened. Change them one bit at a time using source hiding, retaining the endpoints and their opening states. A witness may be supplied to this proof reduction; it is not an input to the simulator. The extracted challenge is available before all these replacements, and accepted openings of a different challenge are already covered by source extraction error. Sequential composition of these hybrids proves the claim. The simulator needs only an edge and two distinct colors, so its algorithm is also defined on a graph having no proper coloring. There is no claim of indistinguishability from an honest proof on a false instance. This well-defined extension will be used inside computational hybrids below. Role of the committed challenge. Both the prover’s colors and the verifier’s challenge use the source BC, with extraction serving a different purpose in each corruption case. The simulator does not reverse an external BC call.

C.2

CP records with selective projections and predicates

The preceding argument realizes Definition 6 directly. Its owner supplies a fixed-length string M at commitment and later authorizes public predicate requests (P, y). The honest verifier checks only requests prescribed by its outer protocol. Opening is the projection predicate [πS (M ) = z]; full opening takes all positions. The receiver’s string and commitment vector below are implementation transcripts, not extra outputs of the ideal CP interface. 77

Roles and input: Alice owns a string M ∈ {0, 1}n of public length n; Bob verifies. G : {0, 1}λ → {0, 1}3λ is the PRG of Fact 2. Every rejection aborts the session as in Definition 6. Commitment. 1. Bob. Send fresh a ←U {0, 1}3λ for this record. 2. Alice. Check a ∈ {0, 1}3λ ; abort on failure. Sample independent seeds sk ←U {0, 1}λ for k ∈ [n] and send D = (Dk )k∈[n] with Dk = G(sk ) ⊕ Mk a. Run Protocol 9 for Rinit (a, D; M, s) =

^

[Dk = G(sk ) ⊕ Mk a],

k∈[n]

using witness (M, s), where s = (sk )k . 3. Bob. Check D ∈ ({0, 1}3λ )n and verify this argument. Store (a, D) only on acceptance; otherwise reject. Later predicate request. The owner publishes the authorized polynomial-size circuit P and public string y before the result. 1. Alice. Check P (M, y) = 1; otherwise reject without proving it. Run Protocol 9 for RP (a, D, y; M, s) = Rinit (a, D; M, s) ∧ [P (M, y) = 1]. For a projection, first send (S, z) and use P (M ; S, z) = [πS (M ) = z]. The claim is public even if the argument is rejected. Full opening is the case of all positions. 2. Bob. Verify the argument on the committed (a, D) and public (P, y). Report success only on acceptance. The initial commitment must finish before any later proof. Every new request is owner-authorized and tagged; no successful request updates M . Keep previously certified projections and check their overlaps. No seed sk is released, including at selective or full opening. Where each step is used. Steps 1–2: commitment, Definition 6(i). Steps 3–4: certification, Protocol 9, Theorem 12. Protocol 11: CP record and predicate proofs, with the public string a explicit in every relation. Lemma 23 (Stateful commit-and-prove simulation). Assuming qOWFs and a BC resource satisfying Definition 10, the CP protocol of Protocol 11 realizes Definition 6 with auxiliary-input-uniform QPT simulation for polynomially many completed commitment and predicate phases. Requests may be adaptive, records may remain pending, and owners may alternate, subject to the stated source locality and invocation conditions. Selective openings release only their claimed projection and certified result, never the internal commitment seeds. Proof. We use Protocol 12. All comparisons retain the joint states of Definition 3, with honest record-internal seeds and proof coins excluded as specified after Definition 6. Step 1: corrupted owner. Let H0 be the real execution. In H1 , replace the initial argument by the extractor of Lemma 21, retaining its private output (M ∗ , s∗ ), and continue all later predicate phases with the honest verifier. The lemma gives H0 ≈c H1 , including the receiver’s retained verification state and the reference; acceptance without a valid initial witness has negligible probability. For each later request, the event Acc ∧ [P (M ∗ , y) = 0] is efficiently testable. To bound its probability in H1 , apply Lemma 21 to that predicate phase only for analysis, keeping (M ∗ , s∗ , a, D, P, y) in the joint state. Except with negligible probability, acceptance in this auxiliary hybrid yields a witness (M ′ , s′ ) for RP . Since a is uniform, setup-wide unique-bit binding fails with probability at 78

Setting: use the commitment and predicate interfaces of Protocol 11, and the argument algorithms of Protocol 10. Map any real rejection or abort to ideal abort, and reproduce withholding by delaying the corresponding ideal release. Corrupt Alice; SIM plays the record receiver. 1. SIM (commitment). Sample and send a ←U {0, 1}3λ . Check Alice’s internal commitments D ∈ ({0, 1}3λ )n and invoke ideal abort on failure. Otherwise, extract a witness (M, s) from the initial argument. When the argument completes, submit M to the ideal CP record and allow delivery of its receipt if it accepts and Rinit (a, D; M, s) = 1; otherwise invoke ideal abort. 2. SIM (predicates). For each later request (P, y), first submit (check, P, y) to ideal(CP), then internally emulate the honest verifier in its interaction with corrupted Alice. When the argument completes, allow delivery of the ideal certificate if it accepts and P (M, y) = 1; otherwise invoke ideal abort. Corrupt Bob; SIM plays the record owner. 1. SIM (commitment). On receiving a, check a ∈ {0, 1}3λ and invoke ideal abort on failure. Otherwise sample independent sk and send Dk = G(sk ), commitments to 0n . Simulate the initial challenge-first argument. 2. SIM (predicates and opening). When ideal CP publishes an authorized request (P, y), relay those public data. If the ideal result authorizes success, simulate the corresponding challenge-first argument; if it is ⊥, reproduce the honest owner’s abort without running an argument. Keep the existing simulated record; do not regenerate it. The custom argument simulator is defined on the dummy instance even when its predicate is false; Lemma 22 justifies the hybrids. Where each step is used. Steps 1–2 (corrupt owner): Lemma 21. Steps 3–4 (corrupt verifier): Lemma 22; stateful use in a call, Lemma 23. Protocol 12: Simulators for the CP interface. most 2−λ by Fact 2. Outside these errors and the initial extraction error, the two witnesses therefore satisfy M ′ = M ∗ , which rules out the tested event. Joint-state indistinguishability transfers its negligible probability back to H1 . Only this efficient event is used in the computational comparison; no test of statistical binding is required. In H2 , use ideal(CP): on initial acceptance with a valid witness, the simulator submits M ∗ and releases the receipt. It submits each later (check, P, y) before internally emulating the verifier, so the functionality publishes the request even on rejection. It releases a certificate exactly when the emulated proof accepts and P (M ∗ , y) = 1, using the functionality’s withholding and abort options otherwise. Every rejected phase causes terminal abort in both experiments. Coupling the emulated messages and coins with H1 , the externally compared states differ only on an invalid initial extraction or a later false acceptance. Their total probability is negligible by the preceding bounds and a polynomial union bound. Thus H1 and H2 are statistically close, and H2 is precisely the ideal execution with the corrupted-owner simulator. Step 2: corrupted verifier. Let K0 be the real execution. In K1 , keep the genuine D and replace every argument by Lemma 22; all these instances are true, since the honest owner aborts on a false predicate without a proof. The lemma gives K0 ≈c K1 jointly with the honest outer input/output and reference. In K2 , change the internal Naor commitments from M to 0n one bit at a time. Hiding applies for the verifier’s arbitrary choice of a, because the seeds are sampled freshly afterwards. Every later proof now uses a total QPT simulator on public inputs, even when the modified instance is false, and no later operation reveals a commitment seed. Thus each replacement 79

admits the full adaptive continuation, giving K1 ≈c K2 . The genuine honest input and controller are unchanged; later requests and predicate values are still computed from that input, including for selective projections. The final hybrid K2 is the ideal execution with the corrupted-verifier simulator: generating D requires only the public record length, the received a, and fresh coins; later proofs require only the ideal public request and its predicate result. The simulator maps the verifier’s rejections to ideal abort and reproduces withholding and abort through the ideal delivery options. It never needs the honest M or any internal commitment seed for that M . Step 3: several records. Apply these hybrids with one persistent simulator state per record and the entire corrupted workspace retained. Replace the argument phases before switching any corresponding honest record’s internal commitments. During each source-BC simulation, other pending honest sessions and protected outer/device registers remain untouched references under Definition 10; subsequent phases are QPT continuations. The bounds are uniform over these states and adaptively chosen public instances, so they also cover interspersed records owned by either party. Polynomially many replacements and extraction/binding errors contribute a negligible total error. The public size and request bounds give one polynomial running-time bound for the simulator. Theorem 12. The protocol of Protocol 11 realizes Definition 6 with the stated security guarantees by Lemma 23. By construction, it uses polynomially many source-BC calls and otherwise performs polynomial-time classical computation and exchanges polynomially many classical bits.

D

Proof of efficient sequential composition

This appendix proves Theorem 5, the replacement theorem for completed OT calls; pending records inside a call are handled by the source contract of Definition 10. It uses the sequential replacement principle with efficient simulation; see also Unruh [Unr10]. The physical conditions are those of Definitions 2 and 4. Fact 15 (Efficient continuation and polynomial hybrids). For joint state ensembles ρ ≈c σ and every QPT channel E, E(ρ) ≈c E(σ). For q = poly(λ), hybrids H0 , . . . , Hq , and a QPT test D, put pj = Pr[D(Hj ) = 1]. Then |p0 − pq | ≤

q X

|pj−1 − pj | ≤ q max |pj−1 − pj |. 1≤j≤q

j=1

In particular, maxj |pj−1 − pj | = negl(λ) implies |p0 − pq | = negl(λ), including arbitrary auxiliary registers. The first assertion is composition of the distinguisher with the channel; the second is the triangle inequality on the telescoped acceptance probabilities. The tests may keep arbitrary auxiliary registers. Full proof of Theorem 5. Step 1: setting. Fix a corrupted party, a QPT outer adversarial machine A, and a polynomial upper bound on the number of calls. Calls are completed and non-overlapping; all messages, including the subroutine’s proof and opening messages, are processed before return. A prescribed ideal resource used within a call is retained with its specified interface. Distinct invocation labels prevent messages from being interpreted in another call. The corruption is static, 80

although the subroutine’s sender/receiver roles may be selected by the outer protocol whenever both component guarantees cover the corresponding role assignment. Step 2: call slots and their simulators. Pad to q potential call slots, with an immutable classical reach flag for each slot. An unreached slot is the identity. The number of reached calls, their inputs, and the decision to continue may depend on preceding outputs and transcripts, subject to boundary admissibility. The corrupted call machine is the fixed code running A during the subroutine; the slot index, role, and all adaptive history are classical or quantum auxiliary input. The single-call quantifier order supplies a simulator for this fixed machine that works uniformly for those inputs. The original adversarial code and the call simulator have polynomial bounds independent of the slot. Simulators run successively, return the prescribed corrupt continuation state, and are not recursively substituted into their own code. Consequently, polynomially many such calls still give a QPT machine. Step 3: the hybrids. Let Hj , for 0 ≤ j ≤ q, replace the first j potential calls by the ideal-f interface and these call simulators, leaving later calls real. Fix j. The prefixes of Hj−1 and Hj agree through the boundary of slot j. Let Cj be the complete corrupted continuation state, Hj the honest subroutine input–output interface, and Uj all remaining outer registers untouched during the call, including scheduling and control state. Apply the single-call guarantee with reference Uj R. Call-local honest scratch and device systems may be traced out only if they are irrevocably unavailable to the continuation. In particular, a discarded device cannot subsequently be reused as an unmodeled communication or memory channel. Step 4: one replacement. Fix a final QPT distinguisher D. The common suffix of the two hybrids, followed by D, is a QPT test Dj of the complete post-call state. It includes all later adaptive choices and any abort continuation. The suffix may act on Uj after return; the external R stays untouched until the final distinguishing test. The theorem’s hypothesis makes the normalized reached boundary state admissible even when earlier slots have been simulated. The call simulator does not depend on that state, its unknown description, or the reference. Hence single-call security bounds this test’s advantage by a negligible νj (λ), uniformly over the reached boundary state. Step 5: weighting by the reach probability. Write pj = Pr[Reachj = 1], the same in both prefixes. On the unreached substate, the hybrids agree. If pj > 0, normalize that branch only to invoke the uniform single-call guarantee and multiply back by pj . Thus |Pr[D(Hj−1 ) = 1] − Pr[D(Hj ) = 1]| ≤ pj νj (λ) ≤ νj (λ).

(81)

Aborts inside a reached call are ordinary output blocks in this same comparison, with the full corrupt state and reference retained. The honest abort flag is absorbing, so no later honest call is made on that branch; a corrupt party’s allowed continuing computation remains part of the common suffix. Step 6: summation. The call tests form a polynomially bounded family, with the index and adaptive control carried as auxiliary data for a fixed call machine. Nonuniform QPT security, uniform over auxiliary states, also covers a sequence of indices maximizing the adjacent advantage. Therefore their maximum νf (λ) is negligible for the fixed outer adversary and distinguisher. Fact 15 yields |Pr[D(H0 ) = 1] − Pr[D(Hq ) = 1]| ≤

q X

νj (λ) ≤ q(λ)νf (λ).

j=1

Step 7: the outer simulator. The final hybrid Hq is Pgf with one stateful QPT adversary comprising A and the call simulators. The outer security theorem gives one QPT simulator Simg , using only ideal(g) and the resources explicitly allowed in that outer theorem. In particular, it has 81

no undeclared ideal-f oracle. The declared device interfaces of Definition 3 remain explicit resources of the outer ideal experiment. This simulator is chosen independently of the initial extension and R. If its induced distinguishing error is νg (λ), the final advantage is at most νg (λ) + q(λ)νf (λ). The simulations are chosen before the final distinguisher; only the negligible advantage bounds may depend on it. This proves the required auxiliary-input-uniform quantifier order and worst-case polynomial running time. Repeat the argument for the other corruption case. Step 8: correctness. For correctness, use the same replacements with both parties honest and the assumed joint input–output/reference correctness guarantees. At each reached slot, these compare the real call with its ideal output while retaining Uj R. Contractivity, weighting by reach cor probability, and telescoping give εcor g + qεf in the same distance convention as the component bounds. In the OT instantiations here, the honest outputs are deterministic functions of the classical inputs. The untouched input–reference marginal is unchanged by a complete honest call, and the incorrect-output/abort substate has mass at most the stated failure probability. Consequently its trace distance 12 ∥ · ∥1 from the ideal joint output is at most that probability. Thus the existing honest-error bounds supply the reference-preserving correctness needed here, including honest aborts. Application to the OT protocol. Theorem 6 provides the single-call simulation and correctness guarantees. At every invocation, retain all corrupt device residuals and place untouched honest outer state in R; only discarded honest call-local systems are traced out. Each call has fresh honest coins, distinct record handles, and its own prescribed device window. Every call satisfies its one global leakage budget; at the isolated one-block endpoint it also satisfies the coordinate-local honest-receiver condition. The next call’s state must again be admissible in every hybrid. No arbitrary device reuse or interleaving is inferred from the single-call result. For the BC-based corollary, first apply Theorem 12 and Corollary 13 within each OT call. Their direct simulation retains pending record states across sequential commit phases and delayed openings. This is the source guarantee of Definition 10, not an application of the completed-call theorem to overlapping commitment lifetimes. It establishes the required efficient OT call simulator; the theorem then composes completed OT calls.

E

Detailed comparison with earlier work

Section 1.5 compares results, reduction chains, and the earlier DI protocols, and credits the ingredients. This section adds what it does not say: the proof-level distinctions and their precise sources. Classical and trusted-quantum baselines. Impagliazzo–Rudich’s barrier concerns fully blackbox constructions of key agreement, and hence OT, from one-way functions [IR89]; it is not a separation between ideal BC and OT, and our compiler uses the explicit simulation contract of Definition 10. Beyond MiniQCrypt, Brakerski, Canetti, and Qian organize equivalences based on efficiently generated, statistically far but computationally indistinguishable state pairs; Ananth, Qian, and Yuen obtain cryptographic tasks from pseudorandom quantum states [BCQ23, AQY22]. These results permit trusted quantum operations or communication by honest users. The DI results under bounded-storage assumptions have different physical and computational hypotheses, so our comparison does not assert domination of those regimes. 82

Technique-level comparison: certification, entropy, and masking. At a high level, our cheating-Bob proof shares a common backbone with earlier DI cryptography: a device test certifies conditional entropy in a raw answer string, and privacy amplification turns that entropy into a mask. The instantiations in prior DI two-party work are not uniform. Kaniewski–Wehner use the CHSH nonlocal game, extending a single-round uncertainty tradeoff by min-entropy additivity for memoryless devices and a martingale argument for sequential attacks [KW16, Sections II.2.1 and II.3.1–II.3.2]; Broadbent–Yuen instead use Learning-with-Errors-based single-device self-testing, an IID entropic uncertainty relation, and two-universal hashing [BY23, Sections 3.1.2 and 4]. Kundu–Sikora–Tan already use Magic Square, but obtain one-shot constant cheating bounds, while Batra–Chakraborty–Jain–Kapshikar are the closest technical antecedent: they also combine Magic Square, parallel repetition, and a seeded extractor [KST22, Sections 1.3–1.5][BCJK25, Section 1 (Proof overview), Sections 4.3 and 5]. Thus, the useful comparison is at the level of this common certification–entropy–masking backbone. Technique-level comparison: security against a cheating Bob. The answer record B and selector J are chosen together, so the scored coordinates may depend on the receiver’s strategy. Fixed-set repetition and the parallel DIQKD analyses of Jain–Miller–Shi and Jain–Kundu do not directly justify that selection [JMS20, JK25]. The selector-aware theorem proved in Section 7 permits this joint choice before the late question. Our causal correspondence and disclosure accounting, Lemmas 4 and 9, justify its use inside the protocol, including the intervening public messages. The proof overview explains how the resulting hidden branch determines the simulator’s ideal OT query. Technique-level comparison: security against a cheating Alice. The quantum difficulty is not merely to show that Alice’s views for D = 0, 1 are indistinguishable. Bob’s raw answer B may remain correlated with Alice’s residual quantum state, so marginal choice hiding alone does not justify adjoining a B-dependent output. The full-simulation QOT proofs of Grilo, Lin, Song, and Vaikuntanathan [GLSV21] and Bartusek, Coladangelo, Khurana, and Ma [BCKM21] handle the analogous correlated measurement record through equivocation and an explicit delayed-measurement joint-state hybrid [GLSV21, Appendix B.1 and Figure 7][BCKM21, Section 6.3]. Our common protocol uses a disjoint-audit label swap at the isolated endpoint and selector entropy in the general regime. In both cases it freezes audited records blockwise, uses the fresh parity hash before Alice’s selective continuation, and enforces affine pairing with the PAY argument. In the outer CP-hybrid proof, the joint abort/output distribution and both counterfactual sender inputs arise from one simulated classical record. CP certifies predicates of that record; equivocation and ordinary ZK are used earlier inside the DI realization of extractable BC. The CP compiler derives its predicate-proof simulation from source extraction. Commit-and-prove functionality. Public-output commitments [CDR16] are an interface-level precedent; we do not identify that interface with CP. Our functionality stores immutable strings, releases certified projections, and certifies only owner-authorized predicates of the same stored string. Sections C and 4 give the stateful compiler and its simulation proof. The outer OT uses these certificates directly; concrete proof transcripts enter through stateful substitution. Further provenance. Beyond the credits in Section 1.5: the robust analysis of the Magic Square game follows [KST22]; the min-entropy, privacy amplification, sampling, and BCH-code tools are from [KRS09, Tom16, Hoe63, SSS93, Hoc59, BRC60]. The affine sharing uses S-Reduce of Damgård, Kilian, and Salvail [DKS99, Section 4.2] and XOR-combiner algebra of Harnik, 83

Kilian, Naor, Reingold, and Rosen [HKN+ 05]; Nielsen, Nordholt, Orlandi, and Burra used random bucketing to handle leakage of individual authenticated-OT choices [NNOB12, Section 5], whereas here quantum leakage may correlate the full selector vector. The phase-local communication reduction is from Jain and Kundu [JK25].

References [ACK+ 14] Nati Aharon, André Chailloux, Iordanis Kerenidis, Serge Massar, Stefano Pironio, and Jonathan Silman. Weak coin flipping in a device-independent setting. In Dave Bacon, Miguel Martin-Delgado, and Martin Roetteler, editors, Theory of Quantum Computation, Communication, and Cryptography, volume 6745 of Lecture Notes in Computer Science, pages 1–12, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. doi:10.1007/978-3-642-54429-3_1. [AQY22]

Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from Pseudorandom Quantum States. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 208–236, Cham, 2022. Springer Nature Switzerland. doi:10.1007/978-3-031-15802-5_8.

[BCJK25] Rishabh Batra, Sayantan Chakraborty, Rahul Jain, and Upendra Kapshikar. A robust and composable device-independent protocol for oblivious transfer using (fully) untrusted quantum devices in the bounded storage model. arXiv preprint arXiv:2404.11283, 2025. arXiv:2404.11283, doi:10.48550/arXiv.2404.11283. [BCK13]

Jonathan Barrett, Roger Colbeck, and Adrian Kent. Memory attacks on deviceindependent quantum cryptography. Physical review letters, 110:010503, 01 2013. doi:10.1103/PhysRevLett.110.010503.

[BCKM21] James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. One-way functions imply secure computation in a quantum world. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology—CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 467–496. Springer, 2021. Full version: arXiv:2011.13486. doi:10.1007/978-3-030-84242-0_17. [BCQ23]

Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS), 2023.

[Blu83]

Manuel Blum. Coin flipping by telephone a protocol for solving impossible problems. ACM SIGACT News, 15(1):23–27, 1983. doi:10.1145/1008908.1008911.

[BRC60]

Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri. On a class of error correcting binary group codes. Information and Control, 3(1):68–79, 1960. doi: 10.1016/S0019-9958(60)90287-4.

[BY23]

Anne Broadbent and Peter Yuen. Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions. New Journal of Physics, 25, 05 2023. doi:10.1088/1367-2630/accf32.

[CDR16]

Jan Camenisch, Maria Dubovitskaya, and Alfredo Rial. UC commitments for modular protocol design and applications to revocation and attribute tokens. In Matthew 84

Robshaw and Jonathan Katz, editors, Advances in Cryptology—CRYPTO 2016, Part III, volume 9816 of Lecture Notes in Computer Science, pages 208–239. Springer, 2016. doi:10.1007/978-3-662-53015-3_8. [DGI+ 26] Eleni Diamanti, Alex B. Grilo, Adriano Innocenzi, Pascal Lefebvre, Verena Yacoub, and Álvaro Yángüez. A practical protocol for quantum oblivious transfer from one-way functions. Quantum, 10:2124, 2026. arXiv:2406.09110. doi:10.22331/q-2026-06-01-2124. [DKS99]

Ivan B. Damgård, Joe Kilian, and Louis Salvail. On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In Jacques Stern, editor, Advances in Cryptology—EUROCRYPT ’99, volume 1592 of Lecture Notes in Computer Science, pages 56–73. Springer, 1999. doi:10.1007/3-540-48910-X_5.

[FM18]

Honghao Fu and Carl A. Miller. Local randomness: Examples and application. Phys. Rev. A, 97:032324, Mar 2018. URL: https://link.aps.org/doi/10.1103/PhysRevA. 97.032324, doi:10.1103/PhysRevA.97.032324.

[GLSV21] Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan. Oblivious Transfer Is in MiniQCrypt. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, pages 531–561, Cham, 2021. Springer International Publishing. doi:10.1007/978-3-030-77886-6_18. [GMW91] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):690–728, 1991. doi:10.1145/116825.116852. [Gol04]

Oded Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, Cambridge, 2004.

[GRS25]

Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. Book draft, August 26, 2025, 2025. URL: https://cse.buffalo.edu/faculty/atri/ courses/coding-theory/book/.

[HILL99]

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999. doi:10.1137/S0097539793244708.

[HKN+ 05] Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, and Alon Rosen. On robust combiners for oblivious transfer and other primitives. In Ronald Cramer, editor, Advances in Cryptology—EUROCRYPT 2005, volume 3494 of Lecture Notes in Computer Science, pages 96–113. Springer, 2005. doi:10.1007/11426639_6. [Hoc59]

Alexis Hocquenghem. Codes correcteurs d’erreurs. Chiffres, 2:147–156, 1959.

[Hoe63]

Wassily Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13–30, 1963. URL: http://links.jstor.org/ sici?sici=0162-1459(196303)58:301<13:PIFSOB>2.0.CO;2-D&origin=MSN, doi: 10.1080/01621459.1963.10500830.

[HP03]

W. Cary Huffman and Vera Pless. Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge, 2003. doi:10.1017/CBO9780511807077.

85

[IPS08]

Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding cryptography on oblivious transfer – efficiently. In David Wagner, editor, Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, pages 572–591. Springer, 2008. doi:10.1007/978-3-540-85174-5_32.

[IR89]

R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC ’89, page 44–61, New York, NY, USA, 1989. Association for Computing Machinery. doi:10.1145/73007.73012.

[JK25]

Rahul Jain and Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent cryptography. SIAM Journal on Computing, 54(4):964–1020, 2025. arXiv:https://doi.org/10.1137/23M1549353, doi:10.1137/23M1549353.

[JMS20]

Rahul Jain, Carl A. Miller, and Yaoyun Shi. Parallel device-independent quantum key distribution. IEEE Transactions on Information Theory, 66(9):5567–5584, 2020. doi:10.1109/TIT.2020.2986740.

[Kil88]

Joe Kilian. Founding cryptography on oblivious transfer. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 20–31, New York, NY, USA, 1988. Association for Computing Machinery. doi:10.1145/62212.62215.

[KLVY23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 1617–1628. Association for Computing Machinery, 2023. doi:10.1145/3564246.3585164. [KMP+ 25] Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, and Michael Walter. A bound on the quantum value of all compiled nonlocal games. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 222–233. Association for Computing Machinery, 2025. Full version: arXiv:2408.06711. doi:10.1145/3717823.3718237. [KRS09]

Robert König, Renato Renner, and Christian Schaffner. The operational meaning of min- and max-entropy. IEEE Trans. Inform. Theory, 55(9):4337–4347, 2009. doi: 10.1109/TIT.2009.2025545.

[KST22]

Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A device-independent protocol for XOR oblivious transfer. Quantum, 6:725, 2022. URL: https://doi.org/10.22331/ q-2022-05-30-725, doi:10.22331/Q-2022-05-30-725.

[KT23]

Srijita Kundu and Ernest Y.-Z. Tan. Composably secure device-independent encryption with certified deletion. Quantum, 7:1047, July 2023. doi:10.22331/ q-2023-07-06-1047.

[KW16]

Jedrzej Kaniewski and Stephanie Wehner. Device-independent two-party cryptography secure against sequential attacks. New Journal of Physics, 18(5):055004, 2016. doi: 10.1088/1367-2630/18/5/055004.

[Mer90]

N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65:3373–3376, Dec 1990. URL: https://link.aps.org/doi/10.1103/ PhysRevLett.65.3373, doi:10.1103/PhysRevLett.65.3373. 86

[Nao91]

Moni Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151– 158, 1991. doi:10.1007/BF00196774.

[NNOB12] Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. A new approach to practical active-secure two-party computation. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology—CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 681–700. Springer, 2012. doi: 10.1007/978-3-642-32009-5_40. [NZ23]

Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification. In 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023), pages 1342–1348. IEEE, 2023. doi:10.1109/FOCS57990.2023.00081.

[Per90]

Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3):107–108, 1990. URL: https://www.sciencedirect.com/science/article/ pii/037596019090172K, doi:10.1016/0375-9601(90)90172-K.

[RTK+ 18] Jérémy Ribeiro, Le Phuc Thinh, J kedrzej Kaniewski, Jonas Helsen, and Stephanie Wehner. Device independence for two-party cryptography and position verification with memoryless devices. Phys. Rev. A, 97:062307, Jun 2018. URL: https://link.aps. org/doi/10.1103/PhysRevA.97.062307, doi:10.1103/PhysRevA.97.062307. [SCA+ 11] J. Silman, A. Chailloux, N. Aharon, I. Kerenidis, S. Pironio, and S. Massar. Fully distrustful quantum bit commitment and coin flipping. Phys. Rev. Lett., 106:220501, Jun 2011. URL: https://link.aps.org/doi/10.1103/PhysRevLett.106.220501, doi: 10.1103/PhysRevLett.106.220501. [SSS93]

Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. In Proceedings of the Fourth Annual ACMSIAM Symposium on Discrete Algorithms (Austin, TX, 1993), pages 331–340. ACM, New York, 1993.

[Tom16]

Marco Tomamichel. Quantum information processing with finite resources: Mathematical foundations, volume 5 of SpringerBriefs in Mathematical Physics. Springer, Cham, 2016. doi:10.1007/978-3-319-21891-5.

[Unr10]

Dominique Unruh. Universally composable quantum multi-party computation. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 486–505, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. doi:10.1007/978-3-642-13190-5_25.

[Wat09]

John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25–58, 2009. doi:10.1137/060670997.

[Wil17]

Mark M. Wilde. Quantum information theory. Cambridge University Press, Cambridge, second edition, 2017. doi:10.1017/9781316809976.

[XMZ+ 20] Feihu Xu, Xiongfeng Ma, Qiang Zhang, Hoi-Kwong Lo, and Jian-Wei Pan. Secure quantum key distribution with realistic devices. Reviews of Modern Physics, 92:025002, 2020. doi:10.1103/RevModPhys.92.025002. 87

[Yan22]

Jun Yan. General Properties of Quantum Bit Commitments. In Advances in Cryptology – ASIACRYPT, 2022.

[ZC26]

Víctor Zapatero and Marcos Curty. Device-independent quantum cryptography with input leakage. arXiv preprint arXiv:2604.20573, 2026. doi:10.48550/arXiv.2604. 20573.

88

Related documents

• Robust and leakage-resilient device-independent oblivious transfer in MiniQCryp#1156693
• Secure quantum key distribution against correlated leakage source.#1140
• Routing Anonymity and Identifiability of Noisy Quantum Hardware#343475
• A robust and composable device-independent protocol for oblivious transfer using (fully) untrusted quantum devices in the bounded storage model#131224
• Adversarial Information Gain in Non-ideal Quantum Measurements#1014621