A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

This paper presents a new, practical, and simulation-secure quantum oblivious transfer protocol based on one-way functions in the plain model that improves efficiency for experimental realization while addressing error correction through equivocal and relaxed-extractable quantum bit commitment.

The Gist

Imagine you are at a magic show where two people, Alice and Bob, want to play a game of "Secret Choice."

The Game: Oblivious Transfer

In this game, Alice has two secret messages (let's call them Message A and Message B). Bob wants to choose one of them to see.

• The Catch: Bob must not be able to peek at the other message.
• The Catch 2: Alice must not know which one Bob picked.

This is called Oblivious Transfer (OT). It's a fundamental building block for secure computing, like a digital "blind box" where the seller doesn't know which box you opened, and you can't open the other one.

The Problem: The Old Protocols Were Too Fragile

For a long time, scientists knew how to do this using quantum mechanics (using tiny particles of light called photons). However, the old methods had three major flaws that made them impossible to build in a real lab:

1. Too Sensitive: If a photon got lost or flipped its state due to a tiny bit of noise (like a bump in the table), the whole game had to restart. It was like trying to build a house of cards in a hurricane.
2. Too Heavy: The old methods required an astronomical number of photons—about 10 trillion (10¹³) for a single round. Even with the fastest lasers, this would take months to send.
3. Too Complicated: They relied on complex mathematical proofs that were hard to implement with standard, off-the-shelf technology.

The Solution: A Practical, "Noise-Tolerant" Protocol

The authors of this paper have built a new version of this game that is practical, fast, and robust. Here is how they did it, using some simple analogies:

1. The "Error-Correcting Net" (Handling Noise)

In the old game, if you dropped one card, the whole deck was ruined. In this new game, Alice and Bob use a safety net.

• The Metaphor: Imagine Alice sends a message written on a piece of paper, but she also sends a "checksum" (a secret code that tells you if the paper got torn).
• How it works: Even if some photons get lost or flipped (noise), the protocol uses error-correcting codes (like a net that catches the dropped cards) to fix the mistakes. This means the game doesn't crash just because the lab isn't perfect.

2. The "One-Time Pass" (Efficiency)

The old protocols were like a game where you had to flip a coin a trillion times to get a single "Heads."

• The Metaphor: The new protocol is like a high-speed train instead of a slow, winding path.
• The Result: Instead of needing 10 trillion photons, they only need about 10 to 30 million. This drops the time required from months down to just seconds. It's the difference between waiting for a letter to arrive by ship versus sending an email.

3. The "Magic Lockbox" (The Technical Trick)

To make the game secure, they use a special type of Quantum Lockbox (called a "Bit Commitment").

• The Old Way: The lockbox was so strict that if you tried to cheat, the whole system broke.
• The New Way: The authors invented a "Relaxed" Lockbox.
  • Imagine a lockbox that usually holds a single, unchangeable secret.
  • The new version says: "We don't need every single lockbox to be perfect. We just need most of them to be locked tight."
  • This "relaxed" rule allows them to skip the heavy, repetitive steps of the old protocols, saving massive amounts of time and resources while still keeping the game secure.

The Big Picture

The authors didn't just prove this works on paper; they provided a blueprint for building it.

• They showed that with current technology (the same kind used in Quantum Key Distribution, which is already being tested in cities), this game can be played today.
• They calculated exactly how many photons are needed and how long it takes, proving that a secure, multi-party quantum network is no longer a distant dream but a feasible engineering project.

In short: They took a fragile, slow, and theoretical quantum game and turned it into a sturdy, fast, and practical tool that can actually be built in a lab.

Technical Summary

Technical Summary: A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

1. Problem Statement

Quantum Oblivious Transfer (QOT) is a fundamental primitive for constructing Multi-Party Computation (MPC) in the quantum setting. While previous works [6, 7] demonstrated that QOT could be built from One-Way Functions (OWFs) and quantum resources, these protocols faced significant barriers to experimental realization. The primary issues identified were:

• Fragility: Existing protocols were intolerant of experimental errors (e.g., bit flips during state distribution).
• Implementation Complexity: The reliance on Zero-Knowledge Proofs that did not make black-box use of OWFs made integration with practical post-quantum hash functions (like SHA) non-trivial.
• Inefficiency: The iterative structure of prior protocols required an impractical number of quantum states (e.g., $\sim 10^{13}$ BB84 states per run), resulting in transmission times on the order of months.

The authors aim to provide a noise-tolerant, efficient QOT protocol based on OWFs in the plain model that is feasible for current experimental setups.

2. Methodology and Technical Approach

The proposed solution constructs a simulation-secure QOT protocol by introducing a new cryptographic primitive: an Equivocal and Relaxed-Extractable (ERE) Bit Commitment scheme.

Core Innovations:

• Relaxed Extractability: The authors observe that full extractability is not strictly necessary to prove the security of QOT. They introduce "relaxed extractability," where a simulator can extract the committed message for a large fraction of commitments, while a negligible fraction may remain unextractable. This relaxation allows for a more efficient protocol structure.
• Noise Tolerance via Error Correction: Unlike previous works assuming noiseless devices, this protocol incorporates linear error-correcting codes (specifically syndrome-based codes like LDPC). The sender transmits syndromes of encoded values, allowing the receiver (or a simulator) to correct errors and extract correct seeds even in the presence of noise.
• Efficient Seed Distillation: The protocol utilizes privacy amplification techniques (Leftover Hash Lemma) on BB84 states to distill random seeds. These seeds serve as keys for equivocal commitments. The structure groups these seeds into families to allow parallel commitments, avoiding the quadratic overhead found in prior compilers.
• Commitment Structure: The ERE-Commitment scheme combines:
  1. EqCommitment: A compiler that transforms a standard statistically binding commitment into an equivocal one. The authors modify the original compiler [7] by reducing the number of sequential repetitions from $\lambda$ to a single instance, trading full binding for "relaxed binding."
  2. ERE-Commitment: A higher-level protocol that uses the EqCommitment scheme. It involves the sender sending BB84 states, the receiver committing to measurement outcomes, and a challenge phase where a subset is opened for verification. The remaining states are used to generate seeds for the final message encryption.

Protocol Flow (Protocol 1):

1. Quantum Transmission: Alice sends $2\lambda_{OT}$ BB84 states to Bob.
2. Commitment: Bob measures and commits to his basis choices and outcomes using the ERE-Commitment scheme.
3. Challenge: Alice challenges a random subset $T$ of the commitments. Bob opens these to verify consistency with Alice's sent states (accounting for experimental error $\alpha$).
4. Key Generation: Alice sends the basis information for the unchallenged set $\bar{T}$. Bob partitions $\bar{T}$ into sets $I_0$ and $I_1$ based on matching bases.
5. Encryption: Alice sends error-correction syndromes and encrypts her messages $m_0, m_1$ using seeds derived from the unchallenged states and a Pseudorandom Generator (PRG).
6. Decryption: Bob corrects his errors using the syndromes and decrypts the message corresponding to his choice bit $b$.

3. Key Contributions

• New Primitive: The definition and construction of an Equivocal and Relaxed-Extractable (ERE) Bit Commitment scheme based on OWFs.
• Noise-Tolerant QOT: A QOT protocol that explicitly handles experimental errors (bit flips and multi-photon events) through syndrome-based error correction, a feature absent in prior theoretical constructions.
• Efficiency Improvement: By optimizing the commitment structure and utilizing error correction, the protocol reduces the required number of BB84 states from $\sim 10^{13}$ (in [7]) to $\sim 10^7$.
• Multi-OT Distillation: The protocol allows for the distillation of multiple OT keys ($n_{OT}$) from a single run of the protocol, which is crucial for efficient MPC implementation.
• Analytical Framework: The paper provides analytical expressions to benchmark the required quantum resources against target security parameters (trace distance $\Delta$), accounting for physical error rates ($\alpha$) and leakage ($\vartheta$).

4. Results and Performance

The authors provide a performance benchmark (Table 1) comparing their protocol against [7] and [21] for a target trace distance $\Delta \le 10^{-15}$:

• Resource Reduction: The required number of BB84 states ($N_{BB84}$) is reduced to approximately $1.43 \times 10^6$ (ideal) to $3.33 \times 10^7$ (realistic noisy setting), compared to $2.27 \times 10^{13}$ for the protocol in [7].
• Time Efficiency: This reduction translates to an acquisition time ($T_{acq}$) of seconds (e.g., 1.43s to 43.6s assuming a 1 MHz rate), whereas the prior work [7] would require approximately 8.6 months.
• Security: The protocol is proven to be simulation-secure against malicious parties in the plain model, relying only on the existence of post-quantum one-way functions.

5. Significance and Claims

The paper claims that this work bridges the gap between theoretical quantum cryptography and practical implementation. By removing the requirement for noiseless devices and drastically reducing the quantum resource overhead, the authors assert that their protocol makes the experimental realization of QOT (and by extension, quantum MPC) feasible with current technology.

The authors emphasize that their construction achieves comparable BB84 costs to Random Oracle Model (ROM) based protocols [21] but operates under strictly weaker computational assumptions (plain model with OWFs rather than ROM). They explicitly state that their goal is a "practical implementation," and they do not claim to match the classical efficiency of ROM-based commitments, but rather to provide a viable path for quantum-secure OT in the real world. The work also highlights that the relaxed extractability property is sufficient for security, a technical insight that enables the efficiency gains without compromising the simulation-based security guarantees required for MPC.