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

The information is dense, technical, and highly specialized. My task is to synthesize these disparate pieces into a single, long, and detailed summary that captures the essence of the construction, security guarantees, and trade-offs.

Here is the comprehensive synthesis:

Comprehensive Research Synthesis: Robust Leakage-Resilient Device-Independent Oblivious Transfer (DI OT)

The research presented details a novel construction for Device-Independent Oblivious Transfer (DI OT) and bit commitment protocols, leveraging post-quantum one-way functions (qOWFs). The core innovation lies in achieving robustness against device faults and side-channel leakage while maintaining strong security guarantees against quantum polynomial-time adversaries. The construction is fundamentally rooted in the ability of honest parties to operate untrusted quantum devices that may share arbitrary entanglement and exhibit non-Independent and Identically Distributed (non-IID) behavior, relying only on trusted classical computation.

Core Protocol Construction and Components

The protocol relies on a sequence of complex operations involving commitment, syndrome calculation, hashing over blocks, and iteration. A crucial element is the use of Device-Independent Bit Commitment (DI BC) constructed via post-quantum equivocal commitments and an extractable DI commitment scheme. This framework is then used to realize the OT itself.

The protocol's execution involves several distinct phases:

1. Leakage Management and Guessing: The construction addresses leakage resilience by carefully managing device communication. In certain parameter regimes, security is maintained even if the vendor’s devices carry at most qubits of adaptive, bidirectional communication (A). A key technique involves guessing device coordinates or audit answers based on their first appearance in a public projection (Step 9), which allows for the reduction of min-entropy by at most the number of guessed bits.

2. Syndrome and Ciphertext Calculation: Syndromes for all blocks are calculated, costing O(rho mrECN + O(m N)) bits. Alice's shares are generated using fresh randomness independent of the source, which are appended as private analysis registers at no cost. The target ciphertext is constructed by appending all other seeds and the remaining 2m-1 ciphertext bits, ensuring that any computation Bob performs on his existing state is covered by data processing.

3. Hashing and Iteration: Charges from the previous steps are subtracted to yield a value at least alpha padN. This extracted pad is then used with Fact 8 (under certain conditions) to make the hidden ciphertext uniform, followed by iteration in a fixed block order, resulting in a final result with only polynomial factors on negligible smoothing and hashing errors.

Security Guarantees and Robustness Regimes

The protocol's security analysis is highly nuanced, depending on the fault tolerance regime chosen:

1. Fault Tolerance Trade-offs:

The construction explicitly highlights a critical trade-off concerning fault tolerance:

• Constant Fault Tolerance: Achieving this level of robustness requires strict isolation between laboratories and the use of coordinate-local measurements within the honest receiver's device.

• General Regime (Leakage/Joint Measurements): If the protocol permits polylogarithmically many qubits of adaptive leakage between laboratories and allows for arbitrary joint measurements, it can tolerate a less stringent, inverse-polylogarithmic rate of honest-device faults.

2. Security Against Adversaries:

The security is established through simulation arguments against quantum polynomial-time (QPT) adversaries:

• Simulation Security: The protocol is simulation-based against QPT adversaries and can compose sequentially with efficient simulators, satisfying the requirement for post-quantum security. Theorem 23 formally proves a polynomial-time DI realization of one-bit OT with a QPT simulator for either corruption case.

• Corruption Tolerance: The construction yields a DI protocol with abort functionality for every efficiently computable classical functionality on a fixed number of parties, secure against static corruption of any proper subset.

3. Leakage Resilience:

Leakage resilience is addressed by ensuring security holds as long as the vendor's devices carry at most qubits of adaptive, bidirectional communication (A). Furthermore, specific results (Corollary 9 and Theorem 10) demonstrate that under certain conditions (e.g., selector-privacy alternatives), the complete view of a cheating Alice with a leakage budget A is hidden by the protocol.

Key Theorems and Parameter Regimes

The paper establishes several key theoretical results underpinning its practical application:

• Theorem 11 (Sender Security): This theorem proves that under specific parameter conditions derived from selector-aware theorems, the blockwise protocol is computationally augmented-secure against every QPT cheating Bob allowed by Definition 8.

• Theorem 23 (Robust DI OT Realization): This is the central result, establishing a polynomial-time DI realization P of one-bit OT with a QPT simulator for either corruption, provided qOWFs and independent honest active-coordinate faults satisfying condition (7) are assumed.

• Corollary 24 (Concrete Parameter Regime): This corollary provides a concrete polylogarithmic regime for the protocol parameters, specifying relationships between A, B, m (number of blocks), and N (related to the size of the state space).

Conclusion

In summary, this work successfully constructs a robust and leakage-resilient Device-Independent Oblivious Transfer protocol from post-quantum one-way functions. It achieves security against QPT adversaries by combining sophisticated techniques—including sequential composition of theorems, careful handling of device faults via isolation or leakage budgets, and advanced proof techniques like selector entropy analysis—to yield a protocol that is both computationally secure and resilient to physical side channels. The primary technical contribution is the rigorous definition and analysis of the trade-offs between fault tolerance (constant vs. inverse-polylogarithmic rates) and leakage resilience, culminating in a concrete polylogarithmic parameter setting for practical implementation.

1. Bold header: Robust Device-Independent Oblivious Transfer (OT) for Secure Computation

This system can securely compute any efficiently computable classical functionality on a fixed number of parties, even when devices are untrusted, faulty, and share arbitrary entanglement. The construction yields DI protocol, with abort for every efficiently computable classical functionality on a fixed number of parties.

2. Bold header: Leakage-Resilient Protocol Execution

The system can tolerate faults based on the laboratory environment; specifically, it can tolerate a constant rate of honest-device faults in isolated laboratories or an inverse-polylogarithmic rate when polylogarithmically many qubits of adaptive leakage exist between laboratories.

3. Bold header: Device-Independent Bit Commitment with Simulator Security

The system can perform DI bit commitment with efficient simulators against both parties and yields DI coin tossing with abort, providing a mechanism for secure computation that is resistant to static corruption of any proper subset of parties.

4. Bold header: Computation over Post-Quantum One-Way Functions (qOWFs)

The system leverages post-quantum one-way functions to construct DI OT and bit commitment, allowing honest parties to operate untrusted quantum devices using only trusted classical computation and communication.

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.