🔢 mathematics

On (Im)possibility of Network Oblivious Transfer via Noisy Channels and Non-Signaling Correlations

This paper establishes that perfect oblivious transfer is fundamentally impossible over noisy channels augmented with general tripartite non-signaling correlations, as repeated usage inevitably amplifies message leakage to the receiver(s), although the receiver(s)'s own privacy remains theoretically achievable.

Original authors: Hadi Aghaee, Christian Deppe, Holger Boche

Published 2026-02-04

📖 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 you are trying to build a secure digital vault where two people (let's call them Alice-1 and Alice-2) want to send secret messages to a third person (Bob). The rules of the game are strict:

The Vault: Bob must be able to pick one specific message from each Alice and read it perfectly.
The Blindfold: Bob must not be able to figure out which message he didn't pick.
The Noise: The messages travel through a "noisy" channel, like a walkie-talkie with static, which usually scrambles things up.

For decades, scientists have wondered: Can we use "super-powerful" connections (called Non-Signaling correlations) to fix the noise and make this vault perfectly secure? These connections are like magic telepathy that allows people to coordinate their actions instantly without sending any signals, similar to the famous "quantum entanglement" but even stronger.

This paper says: No. It is impossible.

Here is the breakdown of their findings using simple analogies:

1. The "Magic Box" vs. The Noisy Walkie-Talkie

The researchers imagined a scenario where Alice-1, Alice-2, and Bob all share a special "Magic Box" (a Non-Signaling box). This box lets them coordinate their answers perfectly, even if they are far apart, without breaking the laws of physics (specifically, they can't use it to send secret signals faster than light).

They asked: If we use this Magic Box to help us talk over a noisy walkie-talkie, can we finally build a perfect Oblivious Transfer (OT) system?

The Result: No. Even with this super-powerful Magic Box, the system fails.

2. The "Leakage" Analogy: The Amplifying Echo

Why does it fail? The paper explains that the Magic Box creates a subtle "echo" or correlation between the senders and the receiver.

The Problem: In a perfect OT system, Bob should only learn about the message he chose. But because of the Magic Box, the way Bob receives the message is slightly influenced by the message he didn't choose.
The Amplification: Think of this like a whisper in a canyon. If you whisper a secret, the echo might give away a tiny hint of what you said. In a normal noisy channel, that hint is lost in the static. But with the Magic Box, the "hint" is amplified.
The Result: If Bob listens to the channel enough times (repeating the process), the tiny hints about the unwanted messages get louder and louder. Eventually, Bob can perfectly distinguish between the messages he didn't pick. The "Blindfold" falls off.

3. The "Causality" Paradox: The Time-Traveler's Dilemma

The paper digs deeper into why this happens using a concept called Causality (cause and effect).

The Rule of OT: Bob's choice (e.g., "I want Message A") must be the cause of him getting Message A. He shouldn't get Message A unless he specifically asked for it.
The Rule of the Magic Box: The Magic Box is "Non-Signaling." This means the box's output cannot depend on what the other person decides later. It has to be ready instantly, regardless of what the others do.
The Clash: The researchers found that these two rules fight each other. To make the Magic Box work, it has to ignore Bob's choice until after the messages are sent. But for OT to work, Bob's choice must determine the message before it is fully revealed.
The Metaphor: Imagine a waiter taking an order.
- OT Rule: The waiter must wait for you to say "I'll have the burger" before bringing the burger.
- Magic Box Rule: The kitchen must prepare the burger before you even sit down, because the kitchen is "non-signaling" and can't wait for your order.
- The Conflict: If the kitchen prepares the burger before you order, they might bring you the burger even if you wanted a salad. The system breaks because the "cause" (your order) is disconnected from the "effect" (the food).

4. What About Just Two People?

The paper also looked at a simpler version: What if only the two senders share the Magic Box, but the receiver (Bob) doesn't?

The Finding: In this specific case, the paper says we cannot prove it's impossible yet. It's an open question. It's like saying, "We know the whole team can't win with this strategy, but maybe if only two teammates share a secret handshake, they might still win."

5. What About Bob's Privacy?

The paper also checked if Bob's privacy (keeping his choice secret from the senders) is safe.

The Finding: Unlike the senders' privacy, Bob's privacy isn't automatically doomed. It depends entirely on how the protocol is designed. If the protocol is built carefully, Bob can keep his choice secret. If it's built poorly, he might leak it. There is no universal "doom" for Bob, only for the senders.

Summary

The paper concludes that you cannot build a perfect, secure "Oblivious Transfer" system over a shared noisy network, even if you have access to the most powerful "super-quantum" correlations (Non-Signaling boxes) imaginable.

The fundamental reason is that these super-correlations break the necessary "cause-and-effect" link between a user's choice and the message they receive. The more you try to use these correlations to fix the noise, the more you accidentally leak the secrets you were trying to hide.

In short: You can't have your cake (perfect security) and eat it too (using super-correlations to fix noise) when it comes to this specific type of network communication. The laws of information theory say "No."

Technical Summary: On (Im)possibility of Network Oblivious Transfer via Noisy Channels and Non-Signaling Correlations

1. Problem Statement

This work investigates the fundamental limits of implementing network oblivious transfer (OT) over shared noisy communication channels when parties have access to general tripartite non-signaling (NS) correlations. The study focuses on two primary network topologies:

Discrete Memoryless Multiple-Access Channels (DM-MAC): Two senders (Alice-1, Alice-2) communicating with a single receiver (Bob).
Discrete Memoryless Broadcast Channels (DM-BC): A single sender communicating with two receivers (Bob-1, Bob-2).

The central research question is whether the presence of powerful non-signaling resources (which include classical correlations, quantum entanglement, and super-quantum correlations like Popescu-Rohrlich boxes) can overcome known information-theoretic impossibility results for OT over noisy channels. Specifically, the authors ask if such correlations can enable:

Perfect OT: Zero-error transmission with zero leakage.
Asymptotic OT: Vanishing error and leakage as blocklength increases.

The authors consider a scenario where the NS resource is shared among all parties (tripartite) or, in specific sub-cases, between subsets of parties (bipartite).

2. Methodology and System Model

The paper adopts a unified information-theoretic framework to model both the physical channel behavior and the shared correlation resources.

Tripartite NS-Box: The shared resource is modeled as an arbitrary tripartite non-signaling box defined by a conditional probability distribution $P(x_1, x_2, (j_1, j_2) \mid i_1, i_2, y)$ for the MAC case (and analogous for BC). The NS property enforces that the marginal distribution of any subset of parties is independent of the inputs of the others. This ensures no signaling occurs through the correlation resource itself.
Protocol Structure: The protocol involves deterministic encoding of messages into NS-box inputs and channel inputs, transmission over the noisy channel, and decoding using channel outputs and NS-box outputs. Public communication is allowed but must adhere to non-collusion assumptions.
Security Definitions:
- Correctness: The receiver must decode the selected message with high probability (asymptotically perfect).
- Sender Security (SfA): The receiver must learn nothing about the unselected messages (zero mutual information in the limit).
- Receiver Security (SfB): The senders must learn nothing about the receiver's choice bits.
Trivial vs. Non-Trivial Boxes: The authors distinguish between "trivial" NS-boxes (where outputs are statistically independent of inputs beyond local randomness) and "non-trivial" boxes (where inputs influence outputs).

3. Key Contributions and Results

A. Impossibility of Perfect and Asymptotic OT with Tripartite NS Assistance

The paper's primary contribution is a rigorous proof that perfect OT is impossible over DM-MACs and DM-BCs when all parties share a tripartite NS correlation, regardless of whether the correlation is trivial or non-trivial.

Perfect OT Impossibility (Theorem 1 & 6):
- For a non-trivial NS-box, the receiver's view of the channel output becomes statistically dependent on the senders' inputs in a way that violates sender privacy. Specifically, the decoding law depends jointly on both senders' inputs, allowing the receiver to infer information about unselected messages.
- For a trivial NS-box, the resource provides no correlation useful for distinguishing inputs, rendering reliable communication (correctness) impossible.
- The proof utilizes entropy inequalities and the data processing inequality to show that the NS constraints force a contradiction between the requirement for the receiver to decode the selected message and the requirement to remain ignorant of the unselected one.
Asymptotic OT Impossibility (Theorem 4):
- Even in the asymptotic regime where error and leakage are allowed to vanish, negligible leakage cannot be achieved with non-trivial tripartite NS boxes.
- The authors demonstrate that repeated use of a non-trivial NS-assisted channel amplifies the receiver's ability to distinguish between different encoder inputs. Through a hypothesis testing argument, they show that the total variation distance between the receiver's views for two message tuples (differing only in an unselected file) approaches 1 exponentially fast.
- Consequently, the mutual information between the unselected messages and the receiver's view does not vanish, violating sender security.

B. Receiver Security (SfB) is Not Universally Impossible

In contrast to sender security, the paper establishes that no universal impossibility result exists for receiver security (Theorem 5).

Whether the receiver's choice bits are leaked depends on the specific protocol design (e.g., how public transcripts are generated and whether the sender adapts to the receiver).
If the protocol is designed such that public messages and NS-box inputs do not depend on the receiver's choice bits, SfB can be maintained. Thus, SfB is a protocol-dependent property rather than an inherent limitation of the NS-assisted channel model.

C. Bipartite NS Correlations

The paper briefly addresses the case where NS correlations are shared only between the two senders (in MAC) or two receivers (in BC), but not with the third party.

Theorem 7: For a bipartite NS-box shared exclusively between the two senders (with the receiver having no access), the authors show that no universal information-theoretic impossibility for perfect OT can be derived.
The Markov chains required to force leakage in the tripartite case cannot be established because the receiver observes neither the NS-box outputs nor the sender-side variables directly. However, the paper notes that if parties are allowed to collude, OT collapses.

D. Causal Analysis and Comparison with PR-Box Equivalence

The paper provides a deep causal analysis explaining why NS correlations fail to support OT in network settings, contrasting this with the known equivalence between OT and PR-boxes in abstract settings (Wolf and Wullschleger [39]).

Causal Collapse: OT requires a "positive, functional" causality where the receiver's private choice causally determines the reconstructed message. NS constraints enforce a "negative, structural" causality (no signaling), which prevents the receiver's choice from influencing the sender's view.
Operational Ordering: In the network model, information must flow through a physical channel (Encoding $\to$ Channel $\to$ Decoding). The NS-box acts only as an auxiliary correlation. The non-signaling constraint implies that the receiver's choice cannot causally influence the sender's inputs or the channel transmission. This breaks the causal chain required for OT.
Resolution of Tension: The authors resolve the apparent contradiction with PR-box equivalence results by distinguishing between stand-alone cryptographic primitives (where the PR-box is the functionality) and auxiliary resources in communication networks (where the PR-box assists a noisy channel). In the latter, the operational causality of the channel prevents the NS resource from enforcing the necessary causal irreversibility.

4. Significance and Claims

The paper claims to establish a strong no-go result for network OT in the presence of tripartite non-signaling correlations.

Universality: The impossibility holds for any noise behavior and any type of NS correlation (classical, quantum, or super-quantum).
Implication for Quantum/6G: Since classical and quantum correlations are subsets of NS correlations, the result implies that tripartite entanglement shared between senders and receivers in a network setting inherently leads to information leakage, violating OT secrecy. This suggests that simply adding quantum resources to shared noisy channels does not automatically enable information-theoretic OT.
Distinction from Previous Work: The work clarifies that while NS correlations can simulate OT distributions in abstract, noiseless, stand-alone settings, they cannot guarantee OT security when embedded in a causally ordered communication protocol involving physical noisy channels.

The authors conclude that while bipartite NS correlations (restricted to senders or receivers) remain a potential avenue for OT, the use of tripartite NS resources fundamentally undermines the security of network oblivious transfer.