Polar Coding for Confidential Broadcasting

Information-theoretic security over noisy channels was introduced by Wyner in [1], which characterized the secrecy-capacity of the degraded wiretap channel. Later, Csiszár and Körner in [2] generalized Wyner’s results to the general wiretap channel. In these settings, one transmitter wishes to reliably send one message to a legitimate receiver, while keeping it secret from an eavesdropper, where secrecy is defined based on a condition of some information-theoretic measure that is fully quantifiable. One of these measures is the information leakage, defined as the mutual information $I(W;Z^n)$ between a uniformly distributed random message W and the channel observations $Z^n$ at the eavesdropper, n being the number of uses of the channel. Based on this measure, the most common secrecy conditions required to be satisfied by channel codes are the weak secrecy, which requires ${lim}_{n\to \infty }\frac{1}{n}I(W;Z^n)=0$, and the strong secrecy, requiring ${lim}_{n\to \infty }I(W;Z^n)=0$. Although the second notion of security is stronger, surprisingly both conditions result in the same secrecy-capacity [3].

In the last decade, information-theoretic security has been extended to a large variety of contexts, and polar codes have become increasingly popular in this area, due to their easily provable secrecy capacity achieving property. Polar codes were originally proposed by Arikan in [4] to achieve the capacity of binary-input, symmetric, and point-to-point channels under Successive Cancellation (SC) decoding. Secrecy capacity achieving polar codes for the binary symmetric degraded wiretap channel were introduced in [5,6], satisfying the weak and the strong secrecy condition, respectively. Recently, polar coding has been extended to the general wiretap channel in [7,8,9,10] and to different multiuser scenarios (for instance, see [11,12]). Indeed, [9,10] generalize their results providing polar codes for the broadcast channel with confidential messages.

This paper provides a polar coding scheme that allows to transmit strongly confidential common information to two legitimate receivers over the Wiretap Broadcast Channel (WTBC). Although [13] provided an obvious lower-bound on the secrecy-capacity of this model, no constructive polar coding scheme has already been proposed so far. Our polar coding scheme is based mainly on the one introduced by [10] for the broadcast channel with confidential messages. Therefore, the proposed polar coding scheme aims to use the optimal amount of randomness in the encoding. Moreover, in order to construct an explicit polar coding scheme that provides strong secrecy, the distribution induced by the encoder must be close in terms of the statistical distance to the original one considered for the code construction, and transmitter and legitimate receivers need to share a secret key of negligible size in terms of rate. Nevertheless, the particularization for the model proposed in this paper is not straightforward. Specifically, we propose a new chaining construction [14] (transmission will take place over several blocks) that is crucial to secretly transmit common information to different legitimate receivers. Indeed, this model generalizes, in part, the one described in [10], where the confidential message is intended only for one legitimate receiver, and the one in [15], which considers only the transmission of non-confidential messages intended for two different receivers. The proposed chaining introduces new bidirectional dependencies between encoding random variables of adjacent blocks that must be considered carefully in the secrecy analysis. Indeed, we need to make use of an additional secret key of negligible size in terms of rate that is privately shared between transmitter and legitimate receivers, which will be used to prove that dependencies between blocks can be broken and, therefore, the strong secrecy condition will be satisfied.

Formally, a WTBC $(\mathcal{X},p_{Y_{(1)}{Y}_{(2)}Z|X},{\mathcal{Y}}_{(1)}\times {\mathcal{Y}}_{(2)}\times \mathcal{Z})$ with 2 legitimate receivers and an external eavesdropper is characterized by the probability transition function $p_{Y_{(1)}{Y}_{(2)}Z|X}$, where $X\in \mathcal{X}$ denotes the channel input, $Y_{(k)}\in {\mathcal{Y}}_{(k)}$ denotes the channel output corresponding to the legitimate Receiver $k\in [1,2]$, and $Z\in \mathcal{Z}$ denotes the channel output corresponding to the eavesdropper. We consider a model, namely Common Information over the Wiretap Broadcast Channel (CI-WTBC), in which the transmitter wishes to send a private message W and a confidential message S to both legitimate receivers. A code $\left(\lceil 2^{n{R}_W}\rceil ,\lceil 2^{n{R}_S}\rceil ,\lceil 2^{n{R}_R}\rceil ,n\right)$ for the CI-WTBC consists of a private message set $\mathcal{W}\triangleq \left[1,\lceil 2^{n{R}_W}\rceil \right]$, a confidential message set $\mathcal{S}\triangleq \left[1,\lceil 2^{n{R}_S}\rceil \right]$, a randomization sequence set $\mathcal{R}\triangleq \left[1,\lceil 2^{n{R}_R}\rceil \right]$ (needed to confuse the eavesdropper about the confidential message S), an encoding function $f:\mathcal{W}\times \mathcal{S}\times \mathcal{R}\to {\mathcal{X}}^n$ that maps $(w,s,r)$ to a codeword $x^n$, and two decoding functions $g_{(1)}$ and $g_{(2)}$ such that $g_{(k)}:{\mathcal{Y}}_{(k)}^n\to \mathcal{W}\times \mathcal{S}$ ($k\in [1,2]$) maps the k-th legitimate receiver observations $y_{(k)}^n$ to the estimates $({\widehat{w}}^{(k)},{\widehat{s}}^{(k)})$. The reliability condition to be satisfied by this code is measured in terms of the average probability of error and is given by The strong secrecy condition is measured in terms of the information leakage and is given by This model is graphically illustrated in Figure 1. A triple of rates $(R_W,R_S,R_R)\in {\mathbb{R}}_{+}^3$ will be achievable for the CI-WTBC if there exists a sequence of $(\lceil 2^{n{R}_W}\rceil ,\lceil 2^{n{R}_S}\rceil ,\lceil 2^{n{R}_R}\rceil ,n)$ codes such that satisfy the reliability and secrecy conditions (1) and (2), respectively.

The achievable rate region is defined as the closure of the set of all achievable rate triples $(R_W,R_S,R_R)$. The following proposition defines an inner-bound on this region.

In this model, the private message W introduces part of the randomness required to confuse the eavesdropper about the confidential message S, and the randomization sequence R denotes the additional randomness that is required for channel prefixing.

Let $(\mathcal{X}\times \mathcal{Y},p_{XY})$ be a Discrete Memoryless Source (DMS), where $X\in \{0,1\}$ (Throughout this paper, we assume binary polarization. Nevertheless, an extension to q-ary alphabets is possible [10,17,18]) and $Y\in \mathcal{Y}$. The polar transform over the n-sequence $X^n$, n being any power of 2, is defined as $U^n\triangleq X^n{G}_n$, where $G_n\triangleq {\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{\otimes n}$ is the source polarization matrix [19]. Since $G_n=G_n^{-1}$, then $X^n=U^n{G}_n$.

The polarization theorem for source coding with side information [19] (Th. 1) states that the polar transform extracts the randomness of $X^n$ in the sense that, as $n\to \infty$, the set of indices $j\in [n]$ can be divided practically into two disjoint sets, namely ${\mathcal{H}}_{X|Y}^{(n)}$ and ${\mathcal{L}}_{X|Y}^{(n)}$, such that $U(j)$ for $j\in {\mathcal{H}}_{X|Y}^{(n)}$ is practically independent of $(U^{1:j-1},Y^n)$ and uniformly distributed, i.e., $H(U(j)|U^{1:j-1},Y^n)\to 1$, and $U(j)$ for $j\in {\mathcal{L}}_{X|Y}^{(n)}$ is almost determined by $(U^{1:j-1},Y^n)$, i.e., $H(U(j)|U^{1:j-1},Y^n)\to 0$. Formally, let where ${\delta }_n\triangleq 2^{-n^{\beta }}$ for some $\beta \in (0,\frac{1}{2})$. Then, by Lemma 4 of [10] we have ${lim}_{n\to \infty }\frac{1}{n}|{\mathcal{H}}_{X|Y}^{(n)}|=H(X|Y)$ and ${lim}_{n\to \infty }\frac{1}{n}|{\mathcal{L}}_{X|Y}^{(n)}|=1-H(X|Y)$, which imply that ${lim}_{n\to \infty }\frac{1}{n}|{({\mathcal{H}}_{X|Y}^{(n)})}^{\mathrm{C}}\setminus {\mathcal{L}}_{X|Y}^{(n)}|=0$, i.e., the number of elements that have not been polarized is asymptotically negligible in terms of rate. Furthermore, Th. 2 of [19] states that given $U[{({\mathcal{L}}_{X|Y}^{(n)})}^{\mathrm{C}}]$ and $Y^n$, $U[{\mathcal{L}}_{X|Y}^{(n)}]$ can be reconstructed using SC decoding with error probability in $O(n{\delta }_n)$. Alternatively, the previous sets can be defined based on the Bhattacharyya parameters ${\{Z(U(j)|U^{1:j-1},Y^n)\}}_{j=1}^n$ because both parameters polarize simultaneously Proposition 2 of [19]. It is worth mentioning that both the entropy terms and the Bhattacharyya parameters required to define these sets can be obtained deterministically from $p_{XY}$ and the algebraic properties of $G_n$ [20,21,22].

Similarly to ${\mathcal{H}}_{X|Y}^{(n)}$ and ${\mathcal{L}}_{X|Y}^{(n)}$, the sets ${\mathcal{H}}_X^{(n)}$ and ${\mathcal{L}}_X^{(n)}$ can be defined by considering that observations $Y^n$ are absent. A discrete memoryless channel $(\mathcal{X},p_{Y|X},\mathcal{Y})$ with some arbitrary $p_X$ can be seen as a DMS $(\mathcal{X}\times \mathcal{Y},p_X{p}_{Y|X})$. In channel polar coding, first we define ${\mathcal{H}}_{X|Y}^{(n)}$, ${\mathcal{L}}_{X|Y}^{(n)}$, ${\mathcal{H}}_X^{(n)}$ and ${\mathcal{L}}_X^{(n)}$ from the target distribution $p_X{p}_{Y|X}$ (polar construction). Then, based on the previous sets, the encoder somehow constructs (since the polar-based encoder will construct random variables that must approach the target distribution of the DMS, throughout this paper we use tilde above the random variables to emphazise this purpose) ${\tilde{U}}^n$ and applies the inverse polar transform ${\tilde{X}}^n={\tilde{U}}^n{G}_n$ with distribution ${\tilde{q}}_{X^n}$. Afterwards, the transmitter sends ${\tilde{X}}^n$ over the channel, which induces ${\tilde{Y}}^n\sim {\tilde{q}}_{Y^n}$. If $\mathbb{V}({\tilde{q}}_{X^n{Y}^n},p_{X^n{Y}^n})\to 0$, then the receiver can reliably reconstruct $\tilde{U}[{\mathcal{L}}_{X|Y}^{(n)}]$ from ${\tilde{Y}}^n$ and $\tilde{U}[{({\mathcal{L}}_{X|Y}^{(n)})}^{\mathrm{C}}]$ by using SC decoding [23].

Let $(\mathcal{V}\times \mathcal{X}\times {\mathcal{Y}}_{(1)}\times {\mathcal{Y}}_{(2)}\times \mathcal{Z},p_{VX{Y}_{(1)}{Y}_{(2)}Z})$ denote the DMS that represents the input $(V,X)$ and output $(Y_{(1)},Y_{(2)},Z)$ random variables of the CI-WTBC, where $|\mathcal{V}|=|\mathcal{X}|\triangleq 2$. Without loss of generality, and to avoid the trivial case $R_S=0$ in Proposition 1, we assume that If $H(V|Y_{(1)})<H(V|Y_{(2)})$, one can simply exchange the role of $Y_{(1)}$ and $Y_{(2)}$ in the polar coding scheme described in Section 4. We propose a polar coding scheme that achieves the following rate triple, which corresponds to the one of the region in Proposition 1 such that the private and the confidential message rate are maximum and the amount of randomness is minimum.

For the input random variable V, we define the polar transform $A^n\triangleq V^n{G}_n$ and the sets

For the input random variable X, we define $T^n\triangleq X^n{G}_n$ and the associated sets

We have $p_{A^n{T}^n}(a^n,t^n)=p_{V^n{X}^n}(a^n{G}_n,t^n{G}_n)$, due to the invertibility of $G_n$, and we write

Consider that the encoding takes place over L blocks indexed by $i\in [1,L]$. At the i-th block, the encoder will construct ${\tilde{A}}_i^n$, which will carry the private and the confidential messages intended for both legitimate receivers. Additionally, the encoder will store into ${\tilde{A}}_i^n$ some elements from ${\tilde{A}}_{i-1}^n$ (if $i\in [2,L]$) and ${\tilde{A}}_{i+1}^n$ (if $i\in [1,L-1]$), so that both legitimate receivers are able to reliably reconstruct ${\tilde{A}}_{1:L}^n$. Then, given ${\tilde{V}}_i^n={\tilde{A}}_i^n{G}_n$, the encoder will perform the polar-based channel prefixing to construct ${\tilde{T}}_i^n$. Finally, it will obtain ${\tilde{X}}_i^n={\tilde{T}}_i^n{G}_n$, which will be transmitted over the WTBC, inducing the channel output observations $({\tilde{Y}}_{(1),i}^n,{\tilde{Y}}_{(2),i}^n,{\tilde{Z}}_i^n)$.

Consider the construction of ${\tilde{A}}_{1:L}^n$. Besides, sets in (5)–(7), define the partition of ${\mathcal{H}}_V^{(n)}$: Moreover, we also define the following partition of the set ${\mathcal{G}}^{(n)}$: and the following partition of the set ${\mathcal{C}}^{(n)}$: These sets are graphically represented in Figure 2. Roughly speaking, $A[{\mathcal{H}}_V^{(n)}]$ is the nearly uniformly distributed part of $A^n$. Thus, ${\tilde{A}}_i[{\mathcal{H}}_V^{(n)}]$, $i\in [1,L]$, is suitable for storing uniformly distributed random sequences. The sequence $A[{\mathcal{H}}_{V|Z}^{(n)}]$ is almost independent of $Z^n$ and, hence, ${\tilde{A}}_i[{\mathcal{G}}^{(n)}]$ is suitable for storing information to be secured from the eavesdropper, whereas ${\tilde{A}}_i[{\mathcal{C}}^{(n)}]$ is not. Sets in (12)–(19) with subscript 1 (sets inside the red curve in Figure 2) form ${\mathcal{H}}_V^{(n)}\cap {\left({\mathcal{L}}_{V|Y_{(1)}}^{(n)}\right)}^{\mathrm{C}}$, while those with subscript 2 (sets inside the blue curve) form ${\mathcal{H}}_V^{(n)}\cap {\left({\mathcal{L}}_{V|Y_{(2)}}^{(n)}\right)}^{\mathrm{C}}$. From Th. 2 of [19,23], recall that ${\tilde{A}}_i\left[{\mathcal{H}}_V^{(n)}\cap {({\mathcal{L}}_{V|Y_{(k)}}^{(n)})}^{\mathrm{C}}\right]$ is the nearly uniformly distributed part of the sequence ${\tilde{A}}_i^n$ required by legitimate Receiver k to reliably reconstruct the entire sequence by performing SC decoding.

For sufficiently large n, assumption (3) imposes the following restriction on the size of the previous sets: The left-hand inequality in (20) holds from the fact that where the positivity holds by Lemma 4 of [10] because, for any $k\in [1,2]$, we have Similarly, the right-hand inequality in (20) holds by Lemma 4 of [10] and the fact that Thus, according to (20), we must consider four cases: