🔢 mathematics

RankGuardPolar Private Public Finite Length Polar Codes with Rank-Certified Leakage

This paper introduces RankGuard-Polar, a framework that provides an exact algebraic characterization and efficient certification of information leakage for finite-length polar codes when specific codeword coordinates are publicly shared, enabling the construction of linear extractors to identify leaked linear combinations under strong eavesdropping conditions.

Original authors: Hassan Tavakoli, Thinh Nguyen, Bella Bose

Published 2026-05-13

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Hassan Tavakoli, Thinh Nguyen, Bella Bose

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 sending a secret message to a friend, but you have to use a public bulletin board to send part of it. The problem is, a nosy neighbor (the "eavesdropper") is watching the bulletin board. If you write the message directly on the board, the neighbor reads it. If you write it in a secret code, the neighbor might still figure it out if the code isn't perfect.

This paper introduces a new system called RankGuard-Polar. It's a clever way to send a message where you intentionally put some parts of the encoded message on the public board, but you do it in a way that guarantees the neighbor learns nothing about your secret message.

Here is how it works, broken down into simple concepts:

1. The "Magic" Frozen Bits

In standard secret codes (called Polar codes), some parts of the message are "information bits" (your actual secret) and other parts are "frozen bits." Usually, frozen bits are just set to zero to help the code work.

In this new system, the authors treat these frozen bits like fresh, random masks. Think of them as a deck of cards that you and your friend share, but the neighbor doesn't have.

The Trick: You mix your secret message with these random "mask" cards before writing anything down.
The Result: Even if the neighbor sees the mixed-up result on the public board, it looks like random noise to them. Only your friend, who has the matching deck of cards (the frozen bits), can unmask the secret.

2. The "Leakage Certificate" (The Math Check)

The big challenge is: Which parts of the message can you safely put on the public board? If you pick the wrong ones, the neighbor might be able to do some math to figure out your secret.

The authors created a mathematical "leakage certificate." Imagine this as a security scanner for your message.

Before you publish anything, you run the message through this scanner.
The scanner looks at the "rank" (a fancy math word for how many independent pieces of information are visible).
It gives you a simple number: 0 means "Safe to publish" (the neighbor learns nothing), and 1 or higher means "Danger" (the neighbor can figure out some of your secret).

3. The "Score Greedy" Algorithm (The Fast Picker)

Checking every possible combination of what to publish would take forever (like trying every possible lock combination in the world). To solve this, the authors invented a fast, smart shortcut called ScoreGreedy.

Think of it like a smart shopping list:

The system looks at every piece of the message.
It gives a "score" to each piece based on how much it relies on the secret "mask" bits versus the actual secret bits.
It picks the pieces with the best scores (the ones most protected by the masks) to put on the public board.
This happens so fast that it can be done on a computer in real-time, even for large messages.

4. The Real-World Scenario

The paper imagines a situation where you have two types of internet connections:

A Private Tunnel: Super secure, but slow or expensive.
A Public Highway: Fast and free, but anyone can see what's on it.

Instead of sending the whole message through the slow tunnel, you use RankGuard-Polar to split the message. You send the "safe" parts (the ones the scanner says are 100% masked) on the Public Highway, and the rest through the Private Tunnel. This speeds up your communication without letting the nosy neighbor steal your secrets.

Summary

RankGuard-Polar is a toolkit that lets you safely use public resources to send data. It uses a mathematical "security scanner" to prove exactly how much information is leaked (guaranteeing it's zero if you follow the rules) and a fast "smart picker" to decide which parts of your message are safe to share. It turns the problem of "hiding in plain sight" into a precise, calculable science.

Technical Summary: RankGuard-Polar

Problem Statement

The paper addresses the challenge of safely publishing a subset of polar codeword coordinates over shared public resources (e.g., broadcast links, cloud storage) while maintaining information-theoretic secrecy for the confidential message. Unlike classical wiretap scenarios where an eavesdropper observes the output of a noisy channel, this work assumes a "strong eavesdropper" who has direct access to the channel input of the public resource. The core operational question is: How much information about the confidential message leaks when specific codeword coordinates are intentionally exposed on a public channel?

The authors focus on finite-length polar codes over binary fields ( $\mathbb{F}_2$ ), specifically within a framework where a transmitter time-shares between private and public channels. The goal is to determine which indices can be published without revealing independent linear combinations of the information bits, utilizing the inherent structure of polar codes where "frozen bits" can serve as fresh secret randomness (masks) known only to the legitimate receiver.

Methodology

The proposed framework, RankGuard-Polar, relies on an exact algebraic characterization of information leakage derived from the rank properties of submatrices of the polar generator matrix.

1. System Model

Encoder: The encoder generates a codeword $x = uG_N$ , where $u = (u_A, u_F)$ consists of information bits ( $u_A$ ) and frozen bits ( $u_F$ ). Crucially, $u_F$ is drawn i.i.d. from a uniform distribution ( $\text{Bernoulli}(1/2)$ ) and acts as a shared secret key between the encoder and decoder, but is unknown to the adversary.
Public Exposure: A subset of indices $P \subset [1:N]$ is published. The adversary observes $x_P = u_A G_{A,P} \oplus u_F G_{F,P}$ , where $G_{A,P}$ and $G_{F,P}$ are submatrices of the generator matrix restricted to rows $P$ and columns $A$ and $F$ , respectively.
Leakage Definition: The leakage is defined as the mutual information $L(P) = I(u_A; x_P)$ .

2. The Leakage Identity

The paper establishes a fundamental identity linking mutual information to matrix ranks:
$L(P) = \text{rank}(G_P) - \text{rank}(G_{F,P})$
where $G_P$ is the submatrix of $G_N$ restricted to rows $P$ and all columns, and $G_{F,P}$ is restricted to rows $P$ and frozen columns $F$ .

Interpretation: $L(P)$ represents the number of independent linear combinations of the information vector $u_A$ that an adversary can recover from the public observation $x_P$ .
Leakage Certificate: If $L(P) = 0$ , no information about $u_A$ is revealed (the columns of $G_{A,P}$ lie entirely within the column space of $G_{F,P}$ ). If $L(P) = r > 0$ , up to $r$ independent bits of information are exposed.

3. Constructive Extraction

The paper proves that if $L(P) = r$ , there exists an explicit linear extractor matrix $R$ such that:

$G_{F,P} R = 0$ (eliminating the effect of the frozen bits).
$\text{rank}(G_{A,P} R) = r$ .
Multiplying the public observation by $R$ yields $x_P R = u_A (G_{A,P} R)$ , providing the adversary with $r$ independent linear equations regarding the message bits.

4. Selection Algorithm (ScoreGreedy)

Since exhaustively searching for the optimal set $P$ of size $k$ to minimize leakage is combinatorially expensive ( $O(\binom{N}{k} \cdot Nk^2)$ ), the authors propose a ScoreGreedy (SG) algorithm:

Scoring: Each row $i$ is scored based on $s_i = f_i - a_i$ , where $f_i$ is the number of non-zero entries in the frozen columns and $a_i$ is the number of non-zero entries in the information columns for that row.
Selection: The algorithm selects the top- $k$ rows with the highest scores.
Theoretical Bound: Theorem 3 provides a deterministic upper bound, showing that the sum of $a_i$ for the selected set bounds the leakage, justifying the surrogate objective of minimizing information-column touches while maximizing frozen-column touches.

Key Contributions

Exact Leakage Certificate: The derivation of the rank-difference identity $L(P) = \text{rank}(G_P) - \text{rank}(G_{F,P})$ , which provides an exact, non-asymptotic measure of information leakage for any published index set in finite-length polar codes.
Constructive Extractors: The proof of the existence of a matrix $R$ that explicitly constructs the linear combinations of message bits leaked by a specific public set $P$ .
Efficient Certification Procedures: The development of efficient algorithms to compute leakage and certify safety for any index set, moving beyond asymptotic secrecy rate analysis to finite-block guarantees.
Practical Selection Algorithm: The introduction of the ScoreGreedy algorithm, a fast ( $O(N^2)$ ) heuristic for selecting public indices that minimizes leakage, validated by a theoretical upper bound.

Results and Examples

The paper validates the framework through theoretical proofs and illustrative examples (e.g., $N=4$ polar codes):

Scenario 1: Publishing a coordinate that directly carries an information bit (e.g., $x_4 = u_4$ ) results in $L(P)=1$ , fully exposing the bit.
Scenario 2: Publishing a coordinate that is a linear combination of information and frozen bits (e.g., $x_1 = u_4 \oplus u_3 \oplus u_2 \oplus u_1$ ) results in $L(P)=0$ if the frozen bits effectively mask the information, revealing no independent linear combinations.
Mixed Sets: The framework correctly quantifies partial leakage (e.g., $L(P)=2$ ) when a set of coordinates exposes linear relations among information bits despite some being masked.

Significance and Claims

The authors position RankGuard-Polar as an operational audit-and-control layer for systems utilizing public resources.

Finite-Length Focus: Unlike classical wiretap literature which often relies on asymptotic secrecy rates as blocklength $N \to \infty$ , this work provides exact, finite- $N$ guarantees.
Strong Adversary Model: The framework is designed for a strong eavesdropper who observes the channel input, a scenario distinct from standard wiretap models where the adversary observes a noisy channel output.
Practical Utility: The method does not replace asymptotic wiretap constructions but offers a mechanism to certify and control leakage in real-world systems where mixed public/private channel usage is necessary for throughput or cost reduction.
Algebraic Transparency: By reducing secrecy to linear algebra (matrix ranks), the framework offers a transparent and computable way to verify security properties without relying on complex cryptographic assumptions or secret generator matrices.

The paper concludes that RankGuard-Polar enables the safe exploitation of public channels by providing a rigorous, constructive method to determine exactly which codeword coordinates can be exposed and how much information is compromised.