PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhili Chen, Rahul Jain, YaoNan Zhang

arXiv:2610.01421v1quant-phcs.CR

TL;DR

Earlier device-independent OT protocols relied on restrictions, and simulation-secure OT from one-way functions alone remained unresolved. This paper constructs device-independent OT and bit commitment from post-quantum one-way functions using a shared protocol skeleton and a selector-aware Magic Square repetition bound. The constructions achieve simulation security in two regimes with different isolation and fault-tolerance trade-offs.

  • Problem

    Earlier device-independent OT protocols required additional restrictions, and to the authors’ knowledge none achieved simulation-secure OT from one-way functions alone.

    Source: §1 · p. 3

  • Method

    A shared protocol skeleton links commit-and-prove reductions to OT, with sender security supported by a selector-aware repetition bound for the Magic Square game.

    Source: §1.3 · p. 9, §2.1 · p. 16

  • Results

    Under post-quantum one-way functions, the protocols provide simulation-secure device-independent OT and bit commitment, with constant fault tolerance under isolation and inverse-polylogarithmic tolerance when leakage or joint measurements are permitted.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    OT completeness extends the construction to device-independent protocols with abort for efficient classical functionalities on a fixed number of parties.

    Source: §1 · p. 3

    Security assumes post-quantum one-way functions, static corruption, and a bounded communication budget between the laboratories during each device window.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The section introduces a device-independent construction of oblivious transfer and bit commitment, assuming post-quantum one-way functions, with simulation security and robustness that trades off against leakage and measurement restrictions. It outlines the security ingredients, including a selector-aware Magic Square repetition bound and extraction that leaves device execution unchanged, and notes OT’s extension to classical secure computation.

1 Introduction

  • The construction gives sequentially composable DI OT and bit commitment against QPT adversaries, using polylogarithmic device coordinates per call and polynomial total device use for compiled OT.The devices may share arbitrary entanglement and behave non-IID; the honest parties rely on trusted classical control rather than trusted quantum operations.Source: §1 · p. 3, §1.1 · p. 5, §1.2 · p. 6
  • Constant fault tolerance requires isolation and a coordinate-local honest receiver; leakage or arbitrary joint measurements instead require an inverse-polylogarithmic fault rate.The leakage allowance is a total adaptive, bidirectional communication budget per single-use batch, not a per-coordinate rate.Source: §1 · p. 4, §1.1 · p. 6

1.2 Our results

  • OT completeness yields DI protocols for every fixed-party efficiently computable classical functionality, secure with abort against static corruption of any proper subset.The protocols use polynomially many sequential pairwise DI OT calls and inherit either robustness and leakage regime.Source: §1.2 · pp. 6–7
  • The commitment has efficient committer-side simulation and receiver hiding; an additional O(log^2 λ)-call layer gives simulators against both parties and DI coin tossing with abort.The equivocality layer has the receiver commit to challenges first, avoiding rewinding an honest party’s single-use device.Source: §1.2 · pp. 6–7

1.3 Protocol and proof overview

  • The OT protocol uses hidden block selectors, error-correcting syndromes, and seeded hashes to reconcile answers and form one-time pads, while commit-and-prove links outputs to Alice’s committed table.Correctness follows from agreement on selector answers up to device faults; receiver security uses hidden question classes and a masked choice bit.Source: §1.3 · pp. 8–9
  • Bob commits to his answers and selectors before learning Alice’s questions, so the repetition bound leaves linear min-entropy in a branch whose payload the hash hides.A second equivocation layer provides simulation against a corrupt receiver; the commitment has simulators against both parties and yields coin tossing with negligible error.Source: §1.3 · pp. 9–11
  • The paper constructs DI OT and secure computation from qOWFs, unlike earlier constructions that require trusted BB84 state preparation and measurement.The inner commitment uses classical messages, and the construction operates untrusted devices through classical control.Source: §1.3 · p. 11

1.5 Previous work and technical contributions

  • The construction must preserve robustness through the commitment and compiler while reproducing device leakage unchanged, extending robustness beyond the bounded-storage setting of [BCJK25].The closest prior leakage treatment, [ZC26], models partial input leakage as a noisy channel in CHSH-based key distribution, unlike this work’s adaptive, bidirectional quantum communication between laboratories.Source: §1.3 · p. 11, §1.5 · p. 14

1.3 Protocol and proof overview

  • The commitment extractor changes a public parity relation using equivocal commitments while leaving the device questions, measurements, and leakage unchanged.This avoids deferring measurements, which a simulator operating an untrusted device cannot do.Source: §1.3 · pp. 11–12

1.4 The technical core: repetition with a receiver-chosen selector

  • The selector-aware repetition bound gives an exponentially small probability that a cheating receiver has few losses, a small selector, and many correct selected answers, even with arbitrary entanglement and quantum memory.The proof extends the two-round threshold theorem of Kundu and Tan: erasures are sampled after the selector is frozen, avoiding conditioning on the receiver’s wins.Source: §1.3 · p. 11, §1.4 · p. 12

2 Cryptographic preliminaries and security definitions

This section sets out the repetition and classical-record interfaces, post-quantum commitment and zero-knowledge tools, and shared parameter schedule used in the protocols. It also defines simulation-based security and sequential composition, specifies the commit-and-prove functionality, and establishes conventions for analyzing the proofs.

2.1 Selector-aware repetition with late erasures

  • Theorem 4 gives selector-aware constant-threshold repetition for the Magic Square game under late erasures, allowing arbitrary entanglement and joint operations across coordinates.The game freezes Dave’s selector and record before the verifier samples the late erasure choice.Source: §2.1 · p. 15
  • Magic Square preserves a hidden answer bit: when strategies win with probability close to one, the other row entry remains close to uniform, unlike CHSH’s determined answer.This residual bit is the hidden string; the proof also uses row parity to reconstruct the third entry.Source: §2.1 · p. 16
  • A hidden-raw-string lemma controls what any late map can learn from Dave’s frozen record when the selector has linear size.The stated condition bounds the selector size between ρmin n and ρmax n.Source: §2.1 · p. 16

2.2 Simulation and sequential composition

  • Efficient sequential composition replaces polynomially many completed ideal calls under at most one static corruption when every reached invocation boundary satisfies the stated conditions.The security guarantee uses auxiliary-input-uniform QPT simulation; abort branches are included in the real–ideal comparison.Source: §2.2 · p. 18

2.3 Commit-and-prove functionality

  • Commit-and-prove stores immutable strings and certifies owner-authorized predicates, with successfully certified projections required to agree on overlapping positions.The functionality is realized from qOWFs and the source commitment of Definition 10.Source: §2.3 · p. 19
  • Post-quantum one-way functions yield Naor commitments with classical messages, while GMW–Watrous proofs provide quantum-computational zero knowledge for NP.The commitment is hiding against receiver-chosen challenges with independent quantum auxiliary input; the sequential proof has perfect completeness and negligible statistical soundness. The OT uses ideal commit-and-prove certificates implemented from source bit commitment, while the DI bit-commitment mode uses ordinary GMW–Watrous proofs.Source: §2.3 · p. 20

2.4 A common parameter schedule

  • For every polylogarithmic leakage budget, the common schedule is feasible with negligible error; its first regime assumes isolation, zero leakage, and coordinate-local honest Bob.Both reductions use the same messages and simulators; the choice of block count depends on the leakage budget and, at zero leakage, the honest receiver’s architecture.Source: §2.4 · pp. 20–21

2.5 Proof conventions

  • Proofs analyze subnormalized branches and fixed statistical hybrids, keep commitment values as analysis-only registers, and totalize stopped-branch variables with private defaults.Computational errors are added to the statistical bound rather than multiplied by a guessing factor.Source: §2.5 · pp. 21–22

2.6 Glossary of recurring terms

  • Table 3 collects shorthand terms used throughout the proofs.Source: §2.6 · p. 22

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

This section develops a unified commit-and-prove reduction to device-independent oblivious transfer across one-block and multi-block regimes, with correctness, simulation, and certification arguments. It analyzes how selector symmetry supports receiver simulation—exactly in the isolated one-block regime with coordinate-local honest-Bob measurements, and via post-selector entropy bounds under laboratory leakage.

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

  • The same protocol uses m = 1 and r = 1 in the isolated regime, while increasing m supplies entropy for bounded leakage or joint honest-receiver measurements.The section states that Sections 4 and 5 realize the commit-and-prove layer and Section 6 assembles the reductions.Source: §3 · p. 22

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

  • In the perfect-device, isolated one-block warm-up, Bob outputs his selected payload, while simulators handle Alice and Bob corruption using committed tables and the padded branch.With m = 1, r = 1, and no syndrome, Alice’s payloads are masked by pads; the general protocol adds fault thresholds, syndromes, multi-block hashing, and entropy accounting.Source: §3.1 · p. 22

3.2 Security notion and physical interface

  • The physical interface allows adaptive bidirectional leakage of at most ℓ qubits during one batch window, but cannot read Bob’s input D.The interface closes after the batch; the classical CP layer does not act on an outer device register, and call-local devices and scratch are retired at delivery or abort.Source: §3.2 · pp. 24–25

3.3 The payload-consistency predicate

  • The payload-consistency predicate certifies that one bit ∆ satisfies all block equations on Alice’s committed table, with honest payloads satisfying it for ∆ = S0 ⊕ S1.A successful ideal CP certificate enforces the predicate on the actual stored table; Alice commits before audit masks are opened.Source: §3.3 · p. 25

3.4 The transfer protocol

  • The transfer protocol collects device records, applies tests and audits, reveals selectors after audit acceptance, hashes Bob’s selector bits, and verifies a payload certificate before delivery.The general regime requires m = ω(log λ), while the isolated endpoint uses m = 1; the protocol’s prescribed checks can globally abort.Source: §3.4 · pp. 26–28

3.5 The theorem and its three properties

  • The OT theorem gives constant honest-fault tolerance with L = Θ(log^2 λ) in the isolated regime and Θ((m log N)^−1) tolerance in the general regime, with negligible errors and efficient sequential composition.The general regime permits adaptive bidirectional cross-block leakage; the simulations cover corruption of either party.Source: §3.5 · pp. 29–30

3.6 Proof of the CP-to-OT reduction

  • The reduction proves correctness and uses selector entropy and affine reconstruction against Alice, while ordered hidden-pad hybrids protect against Bob through the PAY check.For Alice, the audit makes the decoder agree with her table and the PAY certificate supplies the affine form; for Bob, hybrids replace hidden ciphertexts with uniform bits, switch payloads to equal branches, then replace ciphertexts back.Source: §3.6 · p. 30, §3.5 · p. 30

3.6.1 The CP operations of the protocol

  • The commit-and-prove operations commit a fixed-length record, certify projections of that record, and check PAY on the same stored string.Successful PAY checks certify the prescribed predicate exactly, and certified projections and PAY checks concern the same record.Source: §3.6.1 · p. 31

3.6.2 Correctness, the causal cut, and the sparse test

  • For honest parties, audit and decoding errors are negligible across blocks, so selected raw strings and payloads are recovered correctly under the stated correctness conditions.The proof bounds audit and decoding errors exponentially in δaudκaudN and τECN, respectively, and honest proof completeness adds only negligible rejection probability.Source: §3.6.2 · p. 31
  • CP inputs freeze Bob’s question, answer, selector, and audit mask before Alice’s target-block table, preserving the restricted-order causal cut after transcript guessing.The causal-restriction statement concerns the hardwired zero-communication strategy, not the original leakage strategy.Source: §3.6.2 · pp. 31–32
  • The sparse global test bounds losses in every random block against a cheating Bob, while block audits bound bad entries against a cheating Alice.For Bob, outside an exponentially unlikely test event, the complement loss density is at most η0 + o(1), with per-block error m exp[−Ω(N)]. For Alice, the audit bounds use exponent Ω(N) at m = 1 and Ω(N/(m^2 log N)) otherwise.Source: §3.6.2 · pp. 33–34

3.6.3 Exact selector symmetry in the isolated one-block regime

  • In the isolated one-block regime with m = 1 and ℓ = 0, the accepted pre-r substate has uniform selector parity e = β in the stated hybrid.The state includes the audit flag, symmetric size checks, and Alice’s selective continuation; the claim excludes Bob’s private questions, answers, selector label, and inner-sender witnesses.Source: §3.6.3 · p. 34
  • In the isolated one-block regime, coordinate-local honest-Bob measurements give exact equality of the two label branches, including acceptance weight; arbitrary joint instruments are not covered, even with zero physical leakage.The symmetry retains the test and audit registers, so neither is charged.Source: §3.6.3 · p. 35

3.6.4 Leakage from Bob’s laboratory: entropy after the selectors

  • With at most ℓA leakage qubits, the totalized ideal commit-and-prove experiment has a post-selector entropy bound uniform over admissible entangled states.The analysis permits leakage as an arbitrary interactive quantum function of the device execution, rather than requiring coordinate projections.Source: §3.6.4 · pp. 35, 37
  • On accepted pre-r branches, the extracted choice mask is uniform under the general-regime entropy condition, while at the isolated endpoint its symmetry is exact.A fresh nonzero seed is used so that χ = D ⊕⟨r, β⟩ hides D in the hybrid.Source: §3.6.4 · pp. 36–37

3.6.5 Receiver simulation from the classical transcript

  • Except with negligible joint probability on accepted pre-r branches from the bad-audit event, Bob’s post-r abort/output record is an efficient deterministic function of the classical transcript.The reconstruction uses the same immutable committed table and does not access Alice’s residual quantum register.Source: §3.6.5 · p. 37
  • The consistency proof reduces dependence of Bob’s accepted output on the full choice vector β to the single bit e = ⟨r, β⟩; the independent-mask experiment supports reconstruction of accepted affine payloads and the simulated input pair.The accepted-payload statement holds on good-audit branches, except with negligible probability.Source: §3.6.5 · p. 38

A , OSim

The receiver simulation links Bob’s real output and Alice’s complete view to an ideal-OT simulation in both parameter regimes. For sender security, ordered hidden-pad extraction preserves entropy after leakage and disclosures, while the general regime’s receiver-privacy source limits its leakage rate.

A , OSim

  • Theorem 10 gives computational augmented security against a cheating Alice in either selector-privacy regime, with a strict QPT simulator uniform over admissible auxiliary inputs.Receiver-view privacy hides Bob’s choice bit in both regimes; the isolated m = 1 case requires coordinate-local honest Bob, while the general case allows joint instruments and charges test-answer and audit bits.Source: A , OSim · p. 39

3.6.6 Leakage to a cheating Bob: ordered hidden pads

  • Lemma 9 lower-bounds each hidden raw string’s smooth conditional min-entropy by kpad before its fresh extractor seed, given Bob’s state, reference, disclosures, and preceding transcript.The bound applies to m parallel blocks with at most ℓB leakage qubits; the compared state excludes Alice’s private raw strings and undisclosed record contents.Source: §3.6.6 · p. 41
  • Theorem 11 gives computational augmented sender security against any QPT cheating Bob allowed by Definition 8; its simulator submits the effective choice and receives only that sender bit.Ordered hidden-pad extraction underlies replacing hidden ciphertexts with uniform bits; valid genuine-payload and zero-difference endpoints extend the comparison through the PAY continuation.Source: §3.6.6 · pp. 42–43

3.6.7 Scope of the leakage theorem and its rate limitation

  • The general proof tolerates total communication below roughly half the number of blocks, not a constant rate against all mN Magic Square coordinates.The stated rate limitation arises because the receiver-privacy source contains only one selector bit per block; without coordinate-local honest-Bob measurements, the general regime applies even at zero leakage.Source: §3.6.7 · p. 43

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

The section defines a commitment interface with extraction, hiding, and sequential-phase guarantees, then compiles it into commit-and-prove using classical operations. Substituting that compiler into the OT construction preserves its parameter regimes and security guarantees with polynomial overhead.

4.1 The underlying commitment

  • The commitment contract requires committer-side extraction and receiver hiding, with both guarantees holding across polynomially many sequential sessions and delayed openings.The extraction guarantee also covers subsequent QPT opening strategies; the security model retains the honest receiver’s state and untouched reference.Source: §4.1 · p. 44

4.2 The compiler

  • Theorem 12 constructs commit-and-prove from a qualifying commitment using polynomially many commitment calls and otherwise classical computation and communication.The compiler realizes ideal CP against malicious corruption of either party, including polynomially many sequential commitment and predicate phases with adaptively chosen requests.Source: §4.2 · p. 44
  • The committed challenge lets the simulator obtain the verifier’s edge by source-commitment extraction, keeping source-commitment calls out of rewound segments.The challenge-first compiler is adapted from the three-coloring argument of.Source: §4.2 · pp. 44–45

4.3 OT from the compiled commitment interface

  • Substituting the compiler yields OT with efficient simulation and sequential composability in either parameter regime, while preserving outer coordinate counts and honest-fault tolerances.Compiler operations remain outside the device-leakage window and act classically on caller-supplied records; source commitment calls use separate batches, and total overhead is polynomial.Source: §4.3 · p. 45

5 Device-independent bit commitment from qOWFs

This section constructs device-independent bit commitment under qOWFs, replacing a trusted-state quantum step with untrusted Magic Square devices and classical communication. It establishes efficient simulation against either party, the stated commitment properties and sequential-composition guarantees, and an application to coin tossing with abort.

5 Device-independent bit commitment from qOWFs

  • The three-step construction applies an equivocality compiler to Naor commitment, replaces the middle step with an extractable DI commitment, then applies the compiler again.The middle step uses untrusted Magic Square devices and classical communication instead of trusted BB84 states and quantum communication.Source: §5 · p. 45

5.1 Security notions

  • The required security contract includes committer simulation, receiver hiding, and continuations; the final construction adds simulation against a corrupt receiver.Receiver simulation commits without knowing the bit, then opens after receiving it, with the receiver's final state computationally indistinguishable from an honest commitment and opening.Source: §5.1 · p. 46

5.2 Step 1: post-quantum equivocal commitments

  • Under qOWFs, Step 1 uses [BCKM21] to obtain a classical-message commitment with statistical binding, quantum-computational hiding, and quantum equivocation.The compiler is applied to Naor commitment and retains classical native-opening witnesses for either bit of every unopened record.Source: §5.2 · p. 46

5.3 Step 2: the extractable DI commitment

  • Protocol 4 realizes the required commitment contract with QPT online algorithms and negligible error under qOWFs and the stated device and invocation conditions.For m > 1, the schedule sets m = ⌈2ℓ + 4tA + sλ⌉ and τhonest = Θ((m log N)^−1). Its committer simulator changes χ to χ ⊕ 1 while retaining genuine selectors; audits align its decoder with Alice’s table, and receiver hiding follows from uniform pads on unselected branches.Source: §5.3 · p. 49

5.4 Step 3: simulation for both parties

  • Step 3 applies the equivocality compiler to Protocol 4, committing the receiver’s challenges first so simulation never rewinds across a device call.The resulting protocol realizes the stronger definition with simulation against both parties; each committed bit uses 5k calls, where k = sλ.Source: §5.4 · pp. 50–51
  • Protocol 6 realizes bit commitment with QPT simulators against either party and negligible error in both device regimes, using 5sλ = O(log^2 λ) calls per bit.It has the same honest-fault tolerance per call as Theorem 14.Source: §5.4 · p. 52

5.5 Application: coin tossing

  • Protocol 8 realizes DI coin tossing with abort and QPT simulators for either corruption, with negligible error in both regimes and polylogarithmically many device coordinates.For n ≤ poly(λ), sequential executions realize n independent tosses with abort at every boundary satisfying Definition 4.Source: §5.5 · p. 52

5.6.1 Purpose and the mode identity

  • In the real mode the relevant XOR is zero, while setting χ = e ⊕ 1 lets the simulator recover b from the same selected branches.Classical equivocation supplies an alternative valid witness without changing the physical questions or measurements.Source: §5.6.1 · p. 53

5.6.2 Interfaces and imported facts

  • The model permits arbitrarily entangled, non-IID devices and joint instruments with bounded adaptive inter-laboratory communication, while the application has positive block entropy γraw > 0.The communication window closes before record commitments and tests.Source: §5.6.2 · p. 55

5.6.3 Protocol conventions used in the proofs

  • The protocol hides erasure flags from Alice’s device, commits the table before audit masks open, and defers selector-size decisions to the later global audit bit.The specified timing avoids a public size-dependent abort before the table commitment.Source: §5.6.3 · p. 55

5.6.4 Algebra, witnesses, and efficient extraction

  • Equivocation constructs an efficient opposite-mode witness while leaving tested openings and the device input tape unchanged.The witness changes the logical relation used in the proof, not the physical questions or measurements.Source: §5.6.4 · p. 56

Write Y ∗

  • Uniform post-commitment audits bind accepted openings to selected decoders; a bad set larger than η_A N yields acceptance probability at most exp[-Ω(N)] for m = 1 or exp[-Ω(N/(m^2 log N))] generally.The audit samples after the table is fixed, with both bounds negligible under the stated parameters.Source: Write Y ∗ · p. 57
  • Every accepted opening agrees with the simulator’s commitment-end bit except with negligible probability.This is the accepted-opening agreement guarantee used alongside committer-side state simulation.Source: Write Y ∗ · p. 57

5.6.5 Preservation of the corrupt committer’s state

  • A QPT simulator preserves the corrupt committer’s continuing state, while retirement of private labels is essential to the proof.The simulator switches the public mode bit using selector entropy and a witness-independent proof; the entropy bound must not condition on Bob’s private labels, and later honest operations must not use retired labels.Source: §5.6.5 · pp. 59–60

5.6.6 Hiding against a dishonest receiver

  • Under Equation (49), the commitment is computationally hiding against an admissible QPT receiver retaining its complete state through commitment completion.The hidden-ciphertext hybrid makes the complete receiver state identical for either committed bit outside deleted bad substates; equivocation security restores the genuine commitments.Source: §5.6.6 · p. 62

5.6.7 Correctness, composition, and scope

  • With qOWFs and the prescribed interfaces and parameters, Protocol 4 has a QPT simulator, negligible agreement error, and negligible correctness error under the stated honest-fault condition.Sequential composition covers polynomially many phases with arbitrary quantum auxiliary state, references, and delayed openings under retirement; concurrent interleaving of rewound segments, adaptive corruption exposing discarded records, and extra later-phase leakage are excluded.Source: §5.6.7 · pp. 62–63

5.6.8 The second equivocation layer

  • The second equivocation layer commits receiver challenges before base phases, extracts them without rewinding across device calls, and replaces the cited prior majority-vote rule with a sound-pair extraction rule.The resulting simulated commit phase does not use the committed bit.Source: §5.6.8 · p. 63
  • An accepted opening to b ≠ b* occurs with probability at most 2^-sλ + (4k + 2)ε = negl(λ).The bound follows with k = sλ.Source: §5.6.8 · p. 64
  • The simulators act call by call, using 5sλ calls, each with the batch size specified by Theorem 14.They keep other pending honest states as untouched references.Source: §5.6.8 · p. 64

5.6.9 Coin tossing

  • With honest parties, both output a ⊕ b′, which is uniform unless the commitment fails, an event of negligible probability.Source: §5.6.9 · p. 64
  • For either corrupt party, the coin-tossing simulator delivers c except with negligible probability when the opening is accepted.For corrupt Alice, the simulator chooses b′ using c and the extracted bit; for corrupt Bob, it commits and opens to c ⊕ b′. The continuation states are computationally indistinguishable from real execution.Source: §5.6.9 · p. 64
  • For n tosses, sequential composition applies to the outer protocol calling ideal(CT) n times and aborting at the first ⊥.Both simulators use the honest party’s device shares only through the Protocol 7 simulators.Source: §5.6.9 · p. 64

6 The complete construction and secure computation

The section composes the paper’s reductions into DI OT from qOWFs and extends the result to secure computation. Its compiled construction preserves two robustness regimes under a call-by-call invocation schedule.

6 The complete construction and secure computation

  • With zero leakage and coordinate-local receiver measurements, the construction tolerates Ω(1) honest-fault rates; with polylog(λ) leakage and joint instruments, it tolerates 1/polylog(λ).The realization has auxiliary-input-uniform error and efficient sequential composition.Source: §6 · p. 65
  • Total device use, computation, and communication in the compiled OT are polynomial in λ.The proof composes the source reductions with fresh DI bit-commitment sessions and applies a callwise union bound to preserve robustness.Source: §6 · p. 65, §6.1 · p. 66

6.1 Proofs of the complete construction and the MPC corollary

  • The proof assembles the commitment, certified-projection, predicate, and OT interfaces through stateful substitution while preserving pending records and outer state.Uniform negligible replacement errors and honest-failure probabilities sum over polynomially many calls.Source: §6.1 · p. 66
  • Sequential replacement of calls in a classical OT-hybrid MPC protocol yields DI protocols with abort for efficiently computable classical functionalities.The corollary covers a fixed number of parties and static corruption of any proper subset.Source: §6 · p. 65, §6.1 · p. 66
  • For constant c ≥ 1 and leakage budgets ℓA, ℓB ≤ log^c λ, a concrete parameter choice gives L = Θ(log^(4a) λ) and qdev ≤ cfault/(log^a λ log log λ), with negligible ε.Here a := max{c, 2}; the number of CP calls is polylogarithmic, while total classical time and communication are polynomial.Source: §6.1 · p. 67

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

This section proves the selector-aware repetition bound used in the paper’s hiding arguments, then uses it to establish the hidden raw string’s entropy. The proof handles selectors formed by arbitrary joint instruments and relies on erasures arriving after first-round outputs are fixed.

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

  • After Magic Square loss ε, Dave’s probability of guessing the specified row bit from retained memory is at most 1/2 + 15√ε.The bound applies for fixed questions after Dave produces his column.Source: §7 · p. 68
  • The lift scores unselected coordinates with a fair coin and mixes Magic Square testing with guessing so losses outweigh the guessing advantage.Late erasures keep the anchor independent of the frozen selector, placing the lifted game in the product-anchored threshold framework.Source: §7 · p. 70
  • The selector event has probability at most 2^-cseln for sufficiently large n, with constants independent of the strategy and its dimension.The bound follows by translating selector success into an unusually high score in a lifted game and applying the threshold theorem.Source: §7 · pp. 70, 72
  • The threshold theorem extends to a receiver-chosen selector, with the lift, late erasures, and selector scoring supplying the reduction.The one-copy bound of Fu and Miller is the game-specific input.Source: §7 · pp. 70, 72

7.1 Min-entropy of the hidden raw string in one block

  • A correct late guess on active non-losing coordinates yields legal answers there, so the selected-win bound gives the hidden raw string’s entropy.The selected set is fixed before late questions; the argument applies to permitted entangled side information.Source: §7.1 · p. 73

AI use disclosure

The authors disclose using ChatGPT and Claude in preparing the manuscript while retaining responsibility for its mathematical content.

AI use disclosure

  • ChatGPT assisted with proof-strategy exploration, commitment assumptions, security simulations, and identifying potential gaps.It also assisted with literature searches, drafting and revision, and LaTeX preparation.Source: AI use disclosure · p. 73
  • Claude assisted with restructuring and editing the manuscript and drafting parts of it.Source: AI use disclosure · p. 73
  • The authors retain full responsibility for the mathematical claims, proofs, references, and final manuscript.Source: AI use disclosure · p. 73

A Useful facts

The appendix gathers imported facts used in the paper’s proofs.

A Useful facts

A.1 Concentration and sampling

The appendix collects concentration and sampling bounds, then reviews min-entropy tools and seeded extractors used in the paper. It also records how normalization and discarded branches affect entropy guarantees.

A.1 Concentration and sampling

  • The appendix records Chernoff–Hoeffding bounds for independent Boolean variables and an additive form for independent [0,1] variables.Source: §A.1 · p. 74
  • When each index is sampled independently at rate δ from a set of size at least βn, the stated condition δβn=ω(log λ) gives negligible error.Source: §A.1 · p. 74
  • For uniform sampling without replacement, the concentration bounds also hold in the hypergeometric case.Source: §A.1 · p. 74

A.2 Min-entropy and seeded extraction

  • Min-entropy calculus accounts for normalization loss through log(1/p) and explicitly tracks discarded bad branches.The normalization inequality is unsmoothed.Source: §A.2 · pp. 74–75
  • The explicit one-bit linear extractor is an inner product with an independent public seed, has Boolean depth O(log N), and achieves negligible error under the stated schedules when k=ω(log λ).The independent seed incurs no entropy debit.Source: §A.2 · p. 75
  • Quantum leftover hashing uses a random parity hash, with k=ω(log λ) and ε=negl(λ) yielding negligible error.Source: §A.2 · p. 75

A.3 Bounded communication and codes

This appendix supplies tools for removing bounded interactive communication and for decoding errors with explicit binary codes. The communication reduction preserves untouched registers and prescribed record order.

A.3 Bounded communication and codes

  • A bounded-communication strategy can be replaced by one with no extra communication for a specified event, with the budget counting adaptive routing and transcript-control bits.Fixed public schedules have zero cost; the construction uses teleportation correction bits and transcript guessing.Source: §A.3 · p. 75
  • For each fixed rate r, explicit binary linear codes correct errors up to τr n when 2τr<δr, with polynomial-time encoding and syndrome decoding.Source: §A.3 · p. 76
  • Information-coordinate shortening of BCH codes preserves the stated bounds, with zero-extension decoding and polynomial-time syndrome decoding.Source: §A.3 · p. 76

B Feasibility of the common parameter schedule

The schedule in Section 2.4 satisfies the reductions’ inequalities in both regimes. Its entropy budgets retain positive slack, while the specified test and audit errors are negligible.

B Feasibility of the common parameter schedule

  • Audit-answer and syndrome costs leave both pad budgets a fixed positive fraction of N for every m.The remaining debits are 2ℓ+O(m log N), which are o(N) under (5).Source: B Feasibility of the common parameter… · p. 76
  • The test and audit errors are negligible under the selected parameters; for m=1, constant redundancy supplies τ0>0 and leftover hashing is replaced by Lemma 5.For m=1, the audit threshold is strictly below ρminτ0 and the honest-fault rate is lower still.Source: B Feasibility of the common parameter… · p. 76

C Proof of the BC-to-CP compiler theorem

The compiler theorem is proved by adapting the standard three-coloring argument to the source interface. Reordering commitments lets the simulator extract the challenge edge without rewinding across a source-commitment call.

C Proof of the BC-to-CP compiler theorem

  • The verifier commits to the challenge edge before the prover commits to the coloring, enabling source-BC extraction without rewinding across a source-commitment call.Source: C Proof of the BC-to-CP compiler theorem · pp. 76–77
  • Sessions use distinct role, purpose, and round tags, while honest challenge coins and opening states stay outside the receiver workspace of intervening color commitments.Malformed messages and failed openings cause rejection; the source guarantees cover continuing workspaces of pending sessions.Source: C Proof of the BC-to-CP compiler theorem · p. 77
  • The Naor seed length is λ, giving uniform receiver strings binding-failure probability at most 2^-λ, still negligible under polynomial union bounds.The commitments use security parameter λ independently of device counts n and N.Source: C Proof of the BC-to-CP compiler theorem · p. 77

C.1 A challenge-first argument with efficient extraction

The challenge-first coloring argument uses source bit commitments to obtain efficient witness extraction and witness-free simulation. Its extractor continues the prescribed interaction while decoding a proper coloring into an NP witness.

C.1 A challenge-first argument with efficient extraction

  • Bob commits to a uniformly sampled edge, Alice commits to permuted vertex colors, and she opens the two endpoint colors after the edge is revealed.The argument repeats for t = ⌈mλ⌉ rounds with fresh coins and rejects if any round fails.Source: §C.1 · p. 77
  • The extractor obtains committed colors, decodes a proper coloring into a witness, and continues the prescribed interaction.Invalid extracted colors are treated as invalid vertices; acceptance without a valid witness is the knowledge-error event.Source: §C.1 · p. 78
  • Pr[Acc ∧ bw ∉ {w : R(x, w) = 1}] ≤ e^-λ + negl(λ) for the extracted witness.The bound holds uniformly over admissible auxiliary and reference states.Source: §C.1 · p. 78
  • The soundness analysis bounds witness-free passage of the next round by (1 − 1/m) times the preceding probability, plus negligible error.After t rounds, the bound is e^-λ + negl(λ).Source: §C.1 · pp. 78–79
  • For a true instance, the verifier simulator extracts its committed edge first and chooses a uniform ordered pair of distinct endpoint colors.Its simulation uses source hiding for unopened colors; the algorithm is defined even on graphs with no proper coloring, without claiming indistinguishability from an honest proof there.Source: §C.1 · p. 79

C.2 CP records with selective projections and predicates

The commit-and-prove (CP) record commits to an immutable string and supports owner-authorized predicate checks and selective projections. Its stateful compiler provides efficient simulation for adaptive requests and multiple completed phases.

C.2 CP records with selective projections and predicates

  • The CP interface stores a fixed-length string and lets its owner authorize public predicate requests without updating the stored string.The verifier checks only requests prescribed by its outer protocol.Source: §C.2 · p. 79
  • A selective opening certifies a claimed projection of the committed string, while full opening is the projection onto all positions.Previously certified projections are retained and their overlaps checked; internal commitment seeds are never released.Source: §C.2 · p. 80
  • The stateful CP protocol supports auxiliary-input-uniform QPT simulation across polynomially many completed commitment and predicate phases, including adaptive requests and pending records.Selective openings reveal only the claimed projection and certified result, not internal commitment seeds.Source: §C.2 · p. 80
  • For a corrupted owner, the simulator extracts the committed string and releases a certificate only when the predicate argument accepts and the predicate holds.The proof bounds false acceptance through extraction and the unique-bit binding property.Source: §C.2 · p. 81
  • For a corrupted verifier, the simulator replaces internal commitments with commitments to 0^n while preserving the honest input and adaptive continuation.The resulting CP protocol uses polynomially many source-BC calls and polynomial-time classical computation.Source: §C.2 · pp. 81–82

D Proof of efficient sequential composition

The sequential-composition proof replaces completed calls one at a time while retaining the relevant joint state and reference. Uniform single-call guarantees bound each replacement, yielding efficient simulation and preserved correctness for the outer protocol.

D Proof of efficient sequential composition

  • Calls compose when they are completed and non-overlapping, with reached invocation boundaries satisfying the component model and admissibility conditions.The proof retains untouched outer registers as reference and traces out call-local systems only if the continuation cannot access them.Source: D Proof of efficient sequential… · pp. 82–83
  • Each call replacement has negligible distinguishing advantage uniformly over the reached boundary state, and weighting by its reach probability preserves that bound.Aborts are included as ordinary output blocks in the comparison.Source: D Proof of efficient sequential… · p. 83
  • Polynomially many call replacements yield negligible total distinguishing advantage through telescoping, with adaptive history carried as auxiliary input.Efficient call simulators run successively with polynomial bounds independent of the call slot.Source: D Proof of efficient sequential… · pp. 82–83
  • The composition argument preserves honest input-output and reference correctness by applying the same replacements at each reached slot.In the OT instantiations, honest outputs are deterministic functions of the classical inputs, and the proof includes honest aborts.Source: D Proof of efficient sequential… · p. 84
  • For the BC-based corollary, pending record states across sequential commit phases use the source contract, while the completed-call theorem composes the resulting OT calls.The completed-call theorem does not itself cover overlapping commitment lifetimes.Source: D Proof of efficient sequential… · p. 84

E Detailed comparison with earlier work

The comparison distinguishes the paper’s physical and computational setting from trusted-quantum and bounded-storage work, then locates its technical contributions within prior DI methods. It highlights selector-aware analysis, correlated-record handling, and a stateful commit-and-prove interface.

E Detailed comparison with earlier work

  • Earlier trusted-quantum cryptographic results allow trusted quantum operations or communication by honest users, while bounded-storage DI work uses different physical and computational hypotheses.The comparison does not claim domination of those regimes.Source: E Detailed comparison with earlier work · p. 84
  • The cheating-Bob analysis shares a certification–entropy–masking backbone with prior DI work, but uses a selector-aware theorem because the answer record and selector are chosen together.The fixed-set repetition analyses cited in the passage do not directly justify this joint selection.Source: E Detailed comparison with earlier work · p. 85
  • For cheating-Alice security, the raw answer may remain correlated with her residual quantum state, so marginal choice hiding alone does not justify adjoining a choice-dependent output.The protocol uses disjoint-audit label swapping or selector entropy, then freezes audited records and enforces affine pairing with the PAY argument.Source: E Detailed comparison with earlier work · p. 85
  • The CP functionality stores immutable strings, releases certified projections, and certifies owner-authorized predicates of the same stored string.The paper treats this as distinct from the public-output commitment interface.Source: E Detailed comparison with earlier work · p. 85
  • The paper attributes its robust Magic Square analysis to and its phase-local communication reduction to.The passage also credits the affine-sharing components to [DKS99] and.Source: E Detailed comparison with earlier work · pp. 85–86
Loading 2610.01421v1…