🔢 mathematics

Network Oblivious Transfer via Noisy Broadcast Channels

This paper establishes a complete characterization of the oblivious transfer capacity for non-colluding receivers and proposes secure protocols for both non-colluding and colluding scenarios over discrete memoryless broadcast channels, thereby unifying network information theory with cryptographic security.

Original authors: Hadi Aghaee, Christian Deppe, Holger Boche

Published 2026-08-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hadi Aghaee, Christian Deppe, Holger Boche

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the internet as a giant, bustling town square where a single speaker, Alice, tries to shout messages to a crowd of listeners. In a perfect world, everyone hears exactly what she says. But in the real world, the air is full of static, wind, and interference—what scientists call "noise." Usually, we think of this noise as a nuisance, a bug that ruins our phone calls or Wi-Fi. However, a fascinating branch of science called information theory has discovered a secret superpower in this chaos: noise can actually be used to create unbreakable locks.

This paper dives into a specific cryptographic game called "Oblivious Transfer." Think of it as a magical vending machine. Alice has two secret snacks, a chocolate bar and a lollipop. Bob wants one, but he doesn't want Alice to know which one he picked. At the same time, Alice doesn't want Bob to peek at the snack he didn't choose. In a simple, one-on-one conversation, we know how to build this machine using noisy channels. But what happens when Alice is shouting to two people, Bob-1 and Bob-2, at the same time over a shared, noisy broadcast channel? The rules get tricky. If Bob-1 and Bob-2 decide to whisper to each other and combine their notes (collude), can they figure out both snacks? This paper explores exactly that: how to keep the snacks secret even when the listeners might team up, using the very static of the airwaves as a shield.

The authors, a team of researchers from Germany, tackle this problem by treating the noisy broadcast channel like a game of "telephone" played with erasers. They focus on a specific type of noise called an "erasure channel," where messages either arrive perfectly or vanish completely (like a letter lost in the mail). They ask: How fast can Alice send her secrets to Bob-1 and Bob-2 without them learning too much?

First, they look at the "honest-but-curious" scenario. Imagine Bob-1 and Bob-2 are curious neighbors who follow the rules but try to guess the other's snack using only their own ears. The researchers prove that if the neighbors don't talk to each other, there is a clear, mathematical limit to how much secret information Alice can send. They found a "speed limit" for this game. If the noise is just right, they can reach the maximum possible speed, and they even designed a specific set of instructions (a protocol) to do it. In this setup, the math shows that the total speed of both secrets combined is limited by how much information the channel can carry in total, minus the parts that get erased.

However, the story gets more complicated when the neighbors decide to collude. In this version, Bob-1 and Bob-2 share everything they hear. The paper shows that this teamwork makes the job much harder for Alice. The researchers derived new, stricter speed limits for this scenario. They proved that if the two Bobs pool their resources, the amount of secret information Alice can safely send drops significantly. To handle this, they proposed a second, more cautious protocol. Instead of shouting to both at once, this method involves a step-by-step approach where Alice interacts with one Bob, then the other, ensuring that even if they compare notes later, they still can't crack the code.

The paper doesn't just guess these limits; it provides rigorous mathematical proofs. For the non-colluding case, the authors show that their proposed protocol hits the theoretical maximum speed perfectly, meaning they have found the absolute best way to play the game in that setting. For the colluding case, they provide a working method that is secure, though they note that the theoretical maximum speed for this harder scenario isn't fully pinned down yet—their method works, but there might be a slightly faster way we haven't discovered.

Crucially, the paper rules out the idea that perfect secrecy is possible if the players are allowed to deviate from the protocol or act maliciously (like actively changing the noise). The authors stick to the "honest-but-curious" model, where players follow the rules but try to learn as much as they can. They confirm that under these specific conditions, the "magic vending machine" works, but the presence of noise and the possibility of teamwork fundamentally change the rules of the game.

In short, this research maps out the boundaries of privacy in a shared, noisy world. It tells us that while we can use static to hide secrets, the shape of the network (who is listening to whom) and the behavior of the listeners (whether they team up) dictate exactly how much we can hide. The authors have built a unified framework that explains these limits, offering a clear roadmap for how to secure communications in broadcast networks, from satellite signals to local Wi-Fi, ensuring that even in a crowded, noisy room, secrets can remain safe.

Technical Summary: Network Oblivious Transfer via Noisy Broadcast Channels

Problem Statement
Oblivious Transfer (OT) is a fundamental cryptographic primitive where a sender transmits multiple messages to a receiver, who retrieves exactly one without the sender learning which was chosen, while the receiver learns nothing about the unchosen messages. While the information-theoretic realization of OT over noisy point-to-point channels is well-studied, the extension to broadcast channels—where a single sender communicates simultaneously with multiple receivers—remains largely unexplored. In broadcast settings, the statistical dependence of receiver observations and the potential for receiver collusion introduce significant security challenges that differ fundamentally from the point-to-point case. This paper investigates the information-theoretic OT capacity region for a Discrete Memoryless Broadcast Channel (DM-BC) with one sender (Alice) and two receivers (Bob-1 and Bob-2), considering both non-colluding and colluding honest-but-curious user models.

Methodology and System Model
The authors model the system using a DM-BC where Alice inputs a bit $X$ and receivers Bob-1 and Bob-2 observe outputs $Y_1$ and $Y_2$ according to the transition probability $W(y_1, y_2|x)$ . The protocol assumes:

Resources: Unlimited computational power, independent local randomness, and a noiseless public channel for unlimited rounds of communication.
Adversarial Model: Honest-but-curious parties who follow the protocol but attempt to infer unauthorized information. Two scenarios are analyzed:
- Non-colluding: Receivers act independently.
- Colluding: Receivers may share all their views (outputs and public messages) to jointly infer the sender's messages or the other receiver's choice.
Security Criteria: The paper formalizes asymptotic conditions for correctness (low error probability), security for Alice (receivers learn nothing about unchosen messages), and security for Bob (Alice learns nothing about the receivers' choices). For colluding parties, additional criteria ensure that the joint view of the receivers does not reveal more than the sum of their individual legitimate gains.

The study focuses on a specific reduction where the general DM-BC is composed of two independent Binary Erasure Channels (BECs) with erasure probabilities $p_1$ and $p_2$ .

Key Contributions and Results

General Converse Bounds:
The paper derives general outer bounds (converse bounds) on the achievable OT capacity region for both non-colluding and colluding scenarios over a general DM-BC.
- For non-colluding parties, the bounds are derived by applying point-to-point OT capacity results to each link, constrained by the joint mutual information of the broadcast channel.
- For colluding parties, the bounds are tighter, incorporating conditional mutual information terms (e.g., $I(X; Y_1|Y_2)$ ) to account for the information leakage when receivers combine their observations.
Explicit Protocols for Independent BECs:
The authors propose two explicit protocols tailored for a DM-BC consisting of two independent BECs:
- Protocol 1 (Non-colluding): This protocol achieves the full OT capacity region for independent, non-colluding receivers. It utilizes a strategy where receivers identify sets of non-erased and erased positions, exchange subset indices over the public channel, and use two-universal hash functions for privacy amplification. The achievable rate region is characterized as:
  $C_{OT} = \{ (R_1, R_2) : R_1 \le 1-p_1, R_2 \le 1-p_2, R_1 + R_2 \le 1 - p_1 p_2 \}$
  This result provides a complete characterization of the achievable rate region in the non-colluding setting.
- Protocol 2 (Colluding): This protocol maintains security even when receivers collude. It employs a sequential strategy where Alice conducts OT sessions with receivers one after another, utilizing specific erasure patterns and hash functions to prevent the colluding pair from reconstructing the unchosen messages. The paper establishes a new achievable rate region (inner bound) for this scenario, which is strictly smaller than the non-colluding region.
Capacity Characterization:
- In the non-colluding case, the derived lower bounds (via Protocol 1) match the upper bounds, providing a complete characterization of the OT capacity region for independent BECs.
- In the colluding case, the paper presents an achievable region (inner bound) and a converse bound (outer bound). The authors note that these bounds do not generally coincide, leaving the exact capacity region for colluding parties as an open problem, though the proposed protocol establishes new achievable rates under stronger security requirements.

Significance and Claims
The paper claims to provide a unified information-theoretic framework for oblivious transfer over broadcast channels. Its primary significance lies in demonstrating how network topology (specifically the broadcast nature and potential for collusion) fundamentally influences achievable OT rates and security guarantees. By deriving general converse bounds and constructing explicit protocols that achieve the capacity for non-colluding users, the work bridges the gap between point-to-point OT theory and multi-user network cryptography. The authors emphasize that while perfect secrecy is impossible against unbounded adversaries, their focus on the honest-but-curious model allows for the derivation of meaningful capacity regions and the demonstration that shared noisy channels can serve as valuable resources for cryptographic primitives in networked environments. The work also highlights that the presence of collusion significantly restricts the achievable rate region, necessitating different protocol designs compared to the independent user case.

More like this