RankGuard-Polar: Private–Public Finite Length Polar Codes with Rank-Certified Leakage ⋆

Hassan Tavakoli, Thinh Nguyen, Senior Member, IEEE, Bella Bose, Life Fellow, IEEE · 2026

Read RankGuard-Polar: Private–Public Finite Length Polar Codes with Rank-Certified Leakage ⋆ by Hassan Tavakoli, Thinh Nguyen, Senior Member, IEEE, Bella Bose, Life Fellow, IEEE (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11356.txt.

Introduction

Hassan Tavakoli, Thinh Nguyen and Bella Bose introduce RankGuard-Polar, a framework for safely publishing some polar codeword bits on shared public resources. Against a strong spy who sees the published bits, they show leakage has an exact closed form. They build an explicit linear extractor that names the leaked combinations. From this identity they give efficient procedures for working out and proving leakage, plus a proven algorithm. The goal is to share codeword parts in public while keeping the rest safe, and to prove just how much leaks.

Catalog record

CREATORHassan Tavakoli, Thinh Nguyen, Senior Member, IEEE, Bella Bose, Life Fellow, IEEE
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32811
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11356

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

RankGuard-Polar: Private–Public Finite Length Polar Codes with Rank-Certified Leakage ⋆ Hassan Tavakoli, Thinh Nguyen, Senior Member, IEEE, Bella Bose, Life Fellow, IEEE Abstract We introduce RankGuard-Polar , a framework for safely publishing a subset of polar codeword coordinates over shared public resources. We assume a strong eavesdropper who has access to the channel input, i.e., the transmitted codeword coordinates published on a public resource access model. Working over 𝔽 2 \mathbb{F}_{2} and focusing on time-shared public/private BEC uses, we show that leakage from a published index set 𝐏 \mathbf{P} admits an exact algebraic characterization comes from an information-theoretic viewpoint, and we construct an explicit linear extractor ( R R ) that identifies the leaked linear combinations. Building on this identity, we (i) give efficient procedures to compute and certify leakage for any 𝐏 \mathbf{P} , (ii) propose a practical fast algorithm with provable efficiency. † † footnotetext: ⋆ This work was supported by the National Science Foundation under Grant No. CCF:SHF:2417898. I Introduction and Overview Channel coding combats channel noise by adding structured redundancy so the receiver can correct errors and recover the original message reliably [ 1 , 2 , 3 ] . That redundancy, however, increases the number of transmitted symbols and thus enlarges the attack surface available to an adversary who can observe or tamper with some transmissions. For this reason the interplay between coding and cryptography has been studied extensively: redundancy can aid legitimate decoding while, if combined with secret structure or randomness, hindering an attacker. An example is the McEliece cryptosystem, which uses joint error-correcting code with secret linear transformations so legitimate receivers can decode efficiently while attackers face a computationally hard decoding problem [ 4 , 5 ] . Previous works have shown that polar codes can be combined with other communication settings and design goals. In [ 6 , 7 ] , the authors studied polarized multi-relay channels and good index selection for relay settings, and also the author of [ 8 ] , later extended polarization ideas to a multiple-access-based construction. Motivated by this line of work, we study polar codes with rank-based leakage certification in a finite-length public/private framework. Secrecy can be embedded into the encoder–decoder pair, but using the generator matrix G itself as a secret key is restrictive since G must preserve reliability and decoding efficiency. Practical code-based cryptosystems (e.g., McEliece) therefore hide a structured code via secret scramblers and permutations rather than choosing an arbitrary generator matrix. In many practical deployments, a transmitter can use shared public resources to increase throughput or reduce cost. This raises a simple operational question: Under the strong assumption that the eavesdropper has access to the input of the public channel (i.e., the eavesdropper observes the channel input), we ask: How much information about the confidential message leaks when we place some codeword coordinates on that public resource? In this paper, we exploit a practical polar-code mechanism for information-theoretic masking: the polar transform G_{N} is fixed, and the encoder already designates a set of positions as frozen . By drawing frozen bits from fresh secret randomness, one can mask published coordinates without changing the transform or code dimension. However, publish/no-publish decisions must be certified so that no, or as few as possible, independent linear combinations of the information bits are exposed. We address this finite-blocklength problem by developing exact algebraic leakage certificates for any public index set \mathbf{P} , together with constructive extractors and practical selection algorithms. Our focus is on polar-coded systems over stationary erasure channels, in particular the BEC. The rest of the paper is organized as follows. In Section II , we introduce our motivation and preliminaries. Section III develops RankGuard-Polar : we prove the exact leakage identity. Section IV describes practical algorithms for selecting public indices and shows how we can reduce the complexity. In Section V , we compare our finite-block, public/private viewpoint to classical wiretap and general cryptography problem. Finally, Section VI summarizes contributions and outlines directions for extensions. II Motivation and Preliminaries II-A Definitions: We adopt the following notational conventions throughout the paper. All linear algebra is over the binary field \mathbb{F}_{2} unless stated otherwise. Vectors, bold letters like \mathbf{u} , and matrices, capital letters like G , are representing. Shannon entropy and mutual information are H and I , respectively, in bits and base 2. e_{i} is the i -th standard basis column vector. For a vector \mathbf{v} , \|\mathbf{v}\|_{0} denotes Hamming weight, also, diag(\mathbf{v}) is the n\times n diagonal matrix with \mathbf{v} on the diagonal. For a finite set S , |S| is its cardinality. We also write [1:N]\triangleq\{1,\dots,N\} , and u^{N}\triangleq(u_{1},\dots,u_{N}) . We also adopt the standard polar-code notation introduced by [ 9 ] .For blocklength N=2^{n} , the polar transform is given by G_{N}=G_{2}^{\otimes n}, where G_{2}=\begin{bmatrix}1&0\\ 1&1\end{bmatrix}, and \otimes denotes the Kronecker product. We also assume for index sets \mathbf{A} and matrix G , G_{\mathbf{A}}\equiv(G_{N})_{\mathbf{A}} . Let \mathbf{A}\subseteq\{1,\dots,N\} be the information set and \mathbf{F}=\{1,\dots,N\}\setminus\mathbf{A} the frozen set. Let \mathbf{P}\subseteq\{1,\dots,N\} denote a subset of output positions of polar encoder. Definition 1 (Field and vectors) We write \mathbf{u}=(\mathbf{u_{A}},\mathbf{u_{F}}) where \mathbf{u_{A}}\in\mathbb{F}_{2}^{1\times|A|} are the information bits and \mathbf{u_{F}}\in\mathbb{F}_{2}^{1\times|F|} are the frozen bits. For a set of published indices, public indices, \mathbf{P} we write \mathbf{x_{p}}\in\mathbb{F}_{2}^{1\times|P|} for the corresponding subset of codeword coordinates. Definition 2 (Submatrices) For a matrix G\in\mathbb{F}_{2}^{N\times N} and index set \mathbf{P}\subset[1:N] let G_{\mathbf{A,P}}\in\mathbb{F}_{2}^{|A|\times|P|},\quad\text{and}\;G_{\mathbf{F,P}}\in\mathbb{F}_{2}^{|F|\times|P|}, denote the submatrices of G formed by restricting rows to \mathbf{P} public index and columns to the information index set and the frozen index set, respectively. Thus an adversary observing only public bits as: \displaystyle\mathbf{x_{p}}=\mathbf{u_{A}}G_{\mathbf{A,P}}\oplus\mathbf{u_{F}}G_{\mathbf{F,P}}\in\mathbb{F}_{2}^{1\times|P|}. (1) We abbreviate G_{\mathbf{A,P}}=G_{P,\mathrm{info}} and G_{\mathbf{F,P}}=G_{P,\mathrm{frozen}} . We also assume that \mathbf{u_{A}}\in\mathbb{F}_{2}^{1\times|A|},\mathbf{u_{F}}\in\mathbb{F}_{2}^{1\times|F|}, Definition 3 (Image) For a matrix M\in\mathbb{F}_{2}^{m\times n} the image is \mathrm{Im}(M)\;=\;\{\,\mathbf{v}M:\mathbf{v}\in\mathbb{F}_{2}^{m}\,\}\subseteq\mathbb{F}_{2}^{n}. If \operatorname{rank}(M)=r\leq n then |\mathrm{Im}(M)|=2^{r} . Definition 4 Let W:\{0,1\}\to\mathcal{Y} be a binary-input memoryless channel and let G_{N} denote the length- N=2^{n} polar transform. Define the channel input x^{N}=u^{N}G_{N} and the product channel W^{N}(y^{N}\mid x^{N})=\prod_{j=1}^{N}W(y_{j}\mid x_{j}) . The i -th synthetic channel W_{N}^{(i)} is defined as W_{N}^{(i)}\big(y^{N},u^{1:i-1}\mid u_{i}\big)\triangleq\;\frac{1}{2^{\,N-1}}\sum_{u_{i+1}^{N}\in\{0,1\}^{N-i}}W^{N}\big(y^{N}\mid x^{N}\big). Thus, W_{N}^{(i)} represents the effective channel seen by bit u_{i} when the decoder has access to the channel output y^{N} and the previously decoded bits u^{1:i-1} , while the remaining bits u_{i+1}^{N} are averaged out and treated as uniformly random. Definition 5 Let W_{N}^{(i)} denote the i -th synthetic channel of the length- N polar transform. The Bhattacharyya parameter of W_{N}^{(i)} is Z\big(W_{N}^{(i)}\big)\;\triangleq\;\sum_{y\in\mathcal{Y}^{N}}\sqrt{\,W_{N}^{(i)}(y\mid 0)\;W_{N}^{(i)}(y\mid 1)\,}\,, which measures the reliability of the i -th synthetic channel (smaller Z means more reliable). Definition 6 (Information and frozen sets) Let \mathbf{A}\subseteq[1:N] denote the information set and let \mathbf{F}\;=\;[1:N]\setminus\mathbf{A} denote the frozen set . The information set \mathbf{A} is formed from the synthetic-channel reliabilities \{W_{N}^{(i)}\}_{i=1}^{N} . The common selection rule is: \mathbf{A}\;=\;\{\,i\in[1:N]:Z(W_{N}^{(i)})\leq\zeta_{N}\,\} where 0\leq\zeta_{N}<1 are design thresholds that vanish appropriately as N\to\infty . Remark 1 For a target rate R and blocklength N we choose the information set |\mathbf{A}|=\lfloor NR\rfloor (using the selection rule described above). The frozen set is \mathbf{F}=[1:N]\setminus\mathbf{A} . These sets \mathbf{A} and \mathbf{F} are fixed for the remainder of the paper. II-B Motivation: Polar coding with non-identical BEC uses and time-shared physical channels Consider the simplest nontrivial polar encoder with blocklength N=2 and generator G_{2} , \mathbf{u}=(u_{F},u_{A}), where u_{A} is an information

Read the complete text