🔢 mathematics

Implementation of Oblivious Transfer over Binary-Input AWGN Channels by Polar Codes

This paper proposes a one-out-of-two oblivious transfer protocol over binary-input AWGN channels using polar codes with random automorphism-based encoding to achieve perfect secrecy for the receiver and asymptotic secrecy for the sender, while deriving relaxed reliability criteria and optimizing finite-blocklength rates through the characterization of polar-transform automorphisms.

Original authors: Pin-Hsun Lin, Hadi Aghaee, Christian Deppe, Eduard A. Jorswieck, Holger Boche

Published 2026-02-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Pin-Hsun Lin, Hadi Aghaee, Christian Deppe, Eduard A. Jorswieck, 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

The Big Picture: The "Blind Box" Game

Imagine you are playing a game with a friend, Alice.

Alice has two sealed boxes: Box A and Box B. Inside each is a secret message.
You (Bob) want to open one of the boxes to see what's inside.
The Rules:
1. You must get the message from the box you chose.
2. Alice must never know which box you picked.
3. You must never learn anything about the box you didn't pick.

This game is called Oblivious Transfer (OT). It's a fundamental building block for secure computing (like private voting or secure auctions). Usually, this game requires complex math or "magic" (computational assumptions). This paper proposes a way to play this game using physical noise (static on a radio line) and a special coding trick called Polar Codes.

The Problem: The Noisy Radio Line

Imagine Alice and Bob are talking over a very noisy radio channel (the AWGN channel).

If Alice shouts a message, Bob hears it mixed with static.
Sometimes the message comes through clearly; sometimes it's garbled beyond recognition.

In a normal conversation, this is bad. But for this game, noise is actually a superpower.

If the channel is too clear, Bob can hear both boxes, breaking the rules.
If the channel is too noisy, Bob can't hear either box, and the game fails.
The Sweet Spot: We need a channel where Bob can hear one message clearly, but the other message is so garbled by noise that it looks like random static.

The Solution: Polar Codes (The "Sorting Hat")

The paper uses a mathematical tool called Polar Codes to create this "Sweet Spot."

The Analogy: The Sorting Hat
Imagine Alice has a long list of 1,000 tiny messages (bits). She sends them all down the noisy radio line at once.

Polarization is like a magical Sorting Hat. It takes the 1,000 bits and sorts them into two groups:
1. The "Good" Channels: These bits come through crystal clear.
2. The "Bad" Channels: These bits are completely drowned out by static (they look like random noise).

In a normal phone call, you would throw away the "Bad" bits because they are useless.
But in this game, the "Bad" bits are the secret sauce.

The Trick: The "Double-View" Illusion

Here is the clever part where the paper shines. The authors realized that if Alice and Bob just use the standard "Good" and "Bad" lists, Alice might be able to guess which box Bob picked. To fix this, they introduce a shuffling trick.

The Analogy: The Magic Mirror

The Setup: Alice and Bob agree on a set of rules (a "Polarization Matrix") that sorts the bits.
The Shuffle: Bob secretly picks a "view" (a permutation) of this matrix. He tells Alice, "Use this shuffled version of the rules," but he doesn't tell her which specific shuffle he is using for his own decoding.
The Result:
- To Alice: The "Good" bits (where the secret message lives) and the "Bad" bits (where the noise lives) look completely mixed up. She has no idea which bits Bob can actually read.
- To Bob: Because he knows his secret shuffle, he can "un-shuffle" the signal. He sees the "Good" bits clearly and the "Bad" bits as noise.

This creates a perfect illusion. Alice sees a jumbled mess and can't tell which message Bob is trying to decode. Bob sees the clear message he wants.

The "Random Noise" Injection

There is a small problem: In the real world, the "Bad" bits aren't perfectly useless; they still carry a tiny bit of information. If Bob tries hard enough, he might guess a little bit about the unchosen message.

The Fix: The "Red Herring"
The authors propose a clever workaround:

Alice intentionally puts random, fake messages into the "Bad" channels.
To Bob, these fake messages look like extra static.
To Alice, they look like random noise.
Because these bits are truly random and unknown to Bob, they act like a digital eraser. Even if Bob tries to peek at the "Bad" channel, he only sees random garbage, which he can mathematically prove tells him nothing about the real secret.

The "Automorphism" (The Key to the Shuffle)

How do they shuffle the bits without breaking the code? They use something called Automorphisms.

The Analogy: The Rubik's Cube
Imagine the Polar Code is a Rubik's Cube.

Most ways of twisting the cube would break the pattern, making the code useless.
However, there are specific, legal twists (Automorphisms) that rearrange the colors but keep the cube's internal structure intact.
The paper proves that for these specific codes, the "legal twists" are exactly the same as shuffling the positions of the bits (like swapping the 1st bit with the 10th bit).
This allows them to generate millions of different "views" of the code mathematically, ensuring that Alice can never guess Bob's choice.

Why This Matters

No "Magic" Needed: Most secure systems rely on the assumption that "computers can't factor big numbers fast." This paper relies on physics (noise). Even if a super-computer exists, it can't beat the laws of physics.
Finite Blocklength: Many theories say "this works if you send infinite data." This paper says, "We made it work with a realistic, small amount of data (like a short text message)."
Optimization: They didn't just guess the best way to shuffle; they built a mathematical recipe to find the perfect shuffle for any specific noise level to get the fastest possible transfer speed.

Summary

The paper describes a way to play a secure "choose one of two secrets" game over a noisy radio line.

They use Polar Codes to separate clear signals from noise.
They use Random Shuffling (Automorphisms) to hide which signal is which from the sender.
They inject Random Noise into the bad signals to ensure the receiver learns nothing about the unchosen secret.
The result is a physically secure system that works with real-world data sizes, without needing unproven computer science assumptions.

It's like sending two letters in a stormy wind: one letter arrives perfectly, the other is shredded by the wind. But the sender doesn't know which letter is which, and the receiver can't reconstruct the shredded one, even if they try.

1. Problem Statement

The paper addresses the construction of a 1-out-of-2 Oblivious Transfer (OT) protocol over a Binary-Input Additive White Gaussian Noise (BI-AWGN) channel using Polar Codes.

Context: OT is a fundamental primitive for secure two-party computation. While OT can be realized information-theoretically using noisy channels, most existing schemes rely on discrete channels (like Binary Symmetric Channels or Erasure Channels) or require alphabet extensions to emulate erasures.
Challenge: Directly applying Polar Codes to continuous channels (like AWGN) for OT is difficult because:
1. Standard Polar Codes freeze "bad" bit-channels (BBCs) to zeros, creating identical information views for the sender (Alice) and receiver (Bob), which destroys the information asymmetry required for OT.
2. Finite blocklength effects mean BBCs are not perfectly useless (zero mutual information), leading to information leakage that compromises secrecy.
3. There is a lack of a systematic method to optimize the OT rate under finite-blocklength constraints while ensuring both sender and receiver privacy.

2. Methodology

The authors propose a novel framework that leverages the intrinsic properties of Polar Codes and their automorphism groups to create the necessary information asymmetry without alphabet extension.

A. Virtual Binary Erasure Channel (BEC) Emulation

Instead of treating the AWGN channel directly, the scheme views the Polarized bit-channels through a virtual BEC abstraction:

Good Bit-Channels (GBCs): Used to carry the receiver's chosen message.
Bad Bit-Channels (BBCs): Instead of being frozen to zero, a carefully selected subset of BBCs is used to carry independent random bits unknown to the receiver.
Mechanism: From the receiver's (Bob's) perspective, these random bits on the BBCs act as "virtual erasures" for the unchosen message, creating the required asymmetry.

B. Automorphism-Driven Two-View Design

To prevent the sender (Alice) from inferring the receiver's choice bit ( $B$ ) based on the public generator matrix, the protocol introduces a randomized permutation:

Automorphism Group ($Aut(T)$): The protocol utilizes the automorphism group of the Polar transform matrix $T$ . These are permutations that preserve the structure of the Polar code.
Two Views: Bob selects a hidden permutation $P_1 \in Aut(T)$ and a choice bit $B$ . He publishes a composite matrix $F = P_1^T T_B$ , where $T_B$ is either $T_1$ (if $B=0$ ) or $T_2 = A T_1$ (if $B=1$ ).
Symmetry: By cycling through powers of an automorphism $A$ , the distribution of the public matrix $F$ becomes independent of Bob's choice bit $B$ , ensuring Perfect Secrecy for Bob (SfB).

C. Finite-Blocklength Optimization

Recognizing that finite blocklengths cause leakage (since BBCs are not perfectly erasures), the authors:

Derive a relaxed reliability criterion based on Monte-Carlo simulations rather than strict analytical bounds.
Use Privacy Amplification (Universal Hashing) to remove residual leakage from the BBCs.
Formulate a discrete optimization problem to jointly select the permutation $\sigma \in Aut(T)$ and the index sets $(G, B)$ to maximize the OT rate under reliability and secrecy constraints.

3. Key Contributions

First Polar-Code OT for BI-AWGN with Automorphisms: This is the first work to implement OT over BI-AWGN using Polar Codes that explicitly leverages the automorphism group of the Polar transform to hide the receiver's choice.
Characterization of $Aut(T)$: The authors provide a complete characterization of the automorphism group of the Polar transform $T = T_0^{\otimes m}$ . They prove that every automorphism is induced by a unique permutation of the $m$ bit positions (the binary index representation), yielding $|Aut(T)| = m!$. This provides a concrete, searchable space for protocol design.
Virtual BEC Abstraction: They introduce a method to emulate a Binary Erasure Channel over AWGN by injecting random bits into selected BBCs. This allows the use of standard Polar Code decoding while achieving the necessary information asymmetry.
Finite-Blocklength Rate Optimization: They develop a low-complexity optimization framework that uses Gaussian Approximation (GA) to compute bit-channel mutual informations. This framework jointly optimizes the permutation and index sets to maximize the achievable OT rate for a given SNR and blocklength.
Security Proofs: The paper provides rigorous information-theoretic proofs for:
- Perfect Secrecy for Bob (SfB): $\delta_B = 0$ , meaning Alice learns nothing about Bob's choice.
- Secrecy for Alice (SfA): The unchosen message is protected via privacy amplification, with leakage bounded by the mutual information of the BBCs.

4. Key Results

Security: The protocol achieves perfect secrecy for the receiver (SfB) regardless of the blocklength. For the sender (SfA), secrecy is achieved asymptotically and is guaranteed at finite blocklengths via privacy amplification, with the leakage explicitly bounded by $|S|\gamma_n$ (where $S$ is the set of random bits and $\gamma_n$ is the threshold).
Reliability: The authors demonstrate via simulation that injecting random bits into a subset of BBCs degrades the Bit Error Rate (BER) in a controlled manner. They propose a statistical reliability constraint (using Clopper-Pearson confidence intervals on Monte-Carlo trials) to ensure the OT protocol meets reliability targets.
Rate Optimization: Using $n=16$ as an illustrative example, the authors show how to select the optimal permutation and index sets. For a specific SNR, they calculate the net achievable OT rate, demonstrating that the scheme can achieve a positive rate (e.g., $\approx 0.018$ bits/channel use in the example) after accounting for reconciliation and security overhead.
Algorithmic Efficiency: The proposed optimization algorithm (Algorithm 1) avoids complex Mixed-Integer Linear Programming (MILP) by exploiting the structure of the problem, reducing the inner optimization to a simple "largest- $k$ selection" rule for a fixed permutation.

5. Significance

Bridging Theory and Practice: The paper moves OT from theoretical capacity bounds to practical, implementable coding schemes over continuous channels (AWGN), which are ubiquitous in real-world communication systems.
Efficiency: By avoiding alphabet extension (unlike previous Generalized Erasure Channel approaches) and using standard Polar Code structures, the scheme is computationally efficient and compatible with existing hardware.
Foundational Insight: The characterization of the Polar transform's automorphism group as bit-permutations provides a new tool for designing secure physical-layer protocols. It transforms the problem of hiding channel structure into a combinatorial problem of index permutation.
Finite-Blocklength Focus: Unlike many information-theoretic works that focus on asymptotic limits ( $n \to \infty$ ), this paper explicitly addresses the challenges of finite blocklengths, providing practical design rules for real-world deployment.

In summary, this work presents a robust, theoretically grounded, and practically implementable OT protocol for AWGN channels, leveraging the unique properties of Polar Codes and their symmetries to achieve high security and efficiency.