Strong Secrecy on a Class of Degraded Broadcast Channels Using Polar Codes

Abstract

Asymptotic secrecy-capacity achieving polar coding schemes are proposed for the memoryless degraded broadcast channel under different reliability and secrecy requirements: layered decoding or layered secrecy. In these settings, the transmitter wishes to send multiple messages to a set of legitimate receivers keeping them masked from a set of eavesdroppers. The layered decoding structure requires receivers with better channel quality to reliably decode more messages, while the layered secrecy structure requires eavesdroppers with worse channel quality to be kept ignorant of more messages. Practical constructions for the proposed polar coding schemes are discussed and their performance evaluated by means of simulations.

1. Introduction

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 on 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 secrecy conditions result in the same secrecy-capacity region [3].

In the last decade, information-theoretic security has been extended to a large variety of contexts, and this paper focuses on two different classes of discrete memoryless Degraded Broadcast Channels (DBC) surveyed in [4]: (a) with Non-Layered Decoding and Layered Secrecy (DBC-NLD-LS) and (b) with Layered Decoding and Non-Layered Secrecy (DBC-LD-NLS). In these models, the transmitter wishes to send a set of messages through the DBC, and each message must be reliably decoded by a particular set of receivers and kept masked from a particular set of eavesdroppers. The degradedness condition of the channel implies that individual channels can be ordered based on the quality of their received signals. The layered decoding structure requires receivers with better channel quality to reliably decode more messages, while the layered secrecy requires eavesdroppers with worse channel quality to be kept ignorant of more messages.

The capacity region of these models was first characterized in [4,5,6]. However, the achievable schemes used by these works rely on random coding arguments that are nonconstructive in practice. In this sense, the purpose of this paper is to provide coding schemes based on polar codes, which were originally proposed by Arikan [7] to achieve the capacity of binary-input, symmetric, point-to-point channels under Successive Cancellation (SC) decoding. Capacity achieving polar codes for the binary symmetric degraded wiretap channel were introduced in [8,9], satisfying the weak and the strong secrecy condition, respectively. Recently, polar coding has been extended to the general wiretap channel in [10,11,12,13]. Indeed, [12,13] generalize their results providing polar coding schemes for the broadcast channel with confidential messages, and [11] also proposes polar coding strategies to achieve the best-known inner bounds on the secrecy-capacity region of some multi-user settings.

Although recent literature has proven the existence of different secrecy-capacity achieving polar coding schemes for multi-user scenarios (for instance, see [11,12,13,14,15,16,17,18]), polar codes for the two models on which this paper is focused have, as far as we know, not been analyzed yet. As mentioned in [4], these settings capture practical scenarios in wireless systems, in which channels can be ordered based on the quality of the received signals (for example, Gaussian channels are degraded). Hence, the ultimate goal of this work is not only to prove the existence of two asymptotic secrecy-capacity achieving polar coding schemes for these models under the strong secrecy condition, but also to discuss their practical construction and evaluate their performance for a finite blocklength by means of simulations.

1.1. Relation to Prior Work

A good overview of the similarities and differences between the polar codes proposed in [10,11,12,13] for the general wiretap channel can be found in [13] (Figure 1). The polar coding schemes proposed in this paper are based mainly on those introduced by [13] because of the following reasons:

• To provide strong secrecy. Despite both weak and strong secrecy conditions resulting in the same secrecy-capacity region, the weak secrecy requirement in practical applications can result in important system vulnerabilities [19] (Section 3.3).
• To provide polar coding schemes that are implementable in practice. Notice in [13] (Figure 1) that the coding scheme presented in [10] relies on a construction for which no efficient code is presently known. Moreover, the polar coding scheme in [12] relies on the existence, through averaging, of certain deterministic mappings for the encoding/decoding process.

As in [13], our polar coding schemes are totally explicit. However, to provide strong secrecy and reliability simultaneously, the transmitter and the legitimate receivers need to share a secret key of negligible size in terms of rate, and the distribution induced by the encoder must be close in terms of statistical distance to the original one considered for the code construction. Moreover, we adapt the deterministic SC encoder of [20] to our channel models, and we show that it can perform well in practice. As concluded in [20], this deterministic SC encoder will avoid the need to draw large sequences according to specific distributions at the encoder, which can be useful in communication systems requiring low complexity at the transmitter.

In [13] (Remark 3), the authors highlight the connection between polar code constructions and random binning proofs that allows them to apply their designs to different problems in network information theory. Nevertheless, in our polar coding schemes, the chaining construction used in [13] is not needed because of the degradedness condition of the channels, and consequently, we can introduce small changes in the design in order to make our proposed coding schemes more practical. In this sense, we assume that a source of common randomness is accessible to all parties, which allows the transmitter to send secret information in just one block of size n by only using a secret key with negligible size in terms of rate. Despite this common randomness being available to the eavesdroppers, no information will be leaked about the messages. Moreover, if we consider a communication system requiring transmissions over several blocks of size n, the same realization of this source of common randomness can be used at each block without compromising the strong secrecy condition.

1.2. Overview of Novel Contributions

The main novelties of this paper can be summarized as follows:

• Scenario. This paper focuses on two different models of the DBC with an arbitrary number of legitimate receivers and an arbitrary number of eavesdroppers for which polar codes have not yet been proposed. These two models arise very commonly in wireless communications.
• Existence of the polar coding schemes. We prove the existence for sufficiently large n of two secrecy-capacity achieving polar coding schemes under the strong secrecy condition.
• Practical implementation. We provide polar codes that are implementable in real communication systems, and we discuss further how to construct them in practice. As far as we know, although the construction of polar codes has been covered in a large number of references (for instance, see [21,22,23]), they only focus on polar code constructions under reliability constraints.
• Performance evaluation. Simulations results are provided in order to evaluate the reliability and secrecy performance of the polar coding schemes. The performance is evaluated according to different design parameters of the practical code construction. As far as we know, this paper is the first to evaluate the secrecy performance in terms of the strong secrecy, which is done by upper-bounding the information leakage at the eavesdroppers.

1.3. Notation

Through this paper, let $[n]=\{1,\dots ,n\}$ for $n\in {\mathbb{Z}}^{+}$, $a^n$ denote a row vector $(a(1),\dots ,a(n))$. We write $a^{1:j}$ for $j\in [n]$ to denote the subvector $(a(1),\dots ,a(j))$. Let $\mathcal{A}\subset [n]$, then we write $a[\mathcal{A}]$ to denote the sequence ${\{a(j)\}}_{j\in \mathcal{A}}$, and we use ${\mathcal{A}}^{\mathrm{C}}$ to denote the set complement with respect to the universal set $[n]$, that is ${\mathcal{A}}^{\mathrm{C}}=[n]\backslash \mathcal{A}$. If $\mathcal{A}$ denotes an event, then ${\mathcal{A}}^{\mathrm{C}}$ also denotes its complement. We use ln to denote the natural logarithm, whereas log denotes the logarithm base two. Let X be a random variable taking values in $\mathcal{X}$, and let $q_x$ and $p_x$ be two different distributions with support $\mathcal{X}$, then $\mathbb{D}(q_x,p_x)$ and $\mathbb{V}(q_x,p_x)$ denote the Kullback-Leibler divergence and the total variation distance, respectively. Finally, $h_2(p)$ denotes the binary entropy function, i.e., $h_2(p)=-plogp-(1-p)log(1-p)$, and we define the indicator function $𝟙\{u\}$ such that it equals one if the predicate u is true and zero otherwise.

1.4. Organization

The remainder of this paper is organized as follows. In Section 2, the channel models DBC-NLD-LS and DBC-LD-NLS are introduced formally, and their secrecy-capacity regions are characterized. In Section 3, the fundamentals theorems of polar codes are revisited. In Section 4 and Section 5, two polar coding schemes are proposed for the DBC-NLD-LS and DBC-LD-NLS, respectively, and we prove that both are asymptotic secrecy-capacity achieving. In Section 6, practical polar code constructions are discussed for both models, and the performances of the polar codes are evaluated by means of simulations. Finally, the concluding remarks are presented in Section 7.

2. System Model and Secrecy-Capacity Region

Formally, a DBC $(\mathcal{X},p_{Y_K\dots Y_1{Z}_M\dots Z_1|X},{\mathcal{Y}}_K\times \cdots \times {\mathcal{Y}}_1\times {\mathcal{Z}}_M\times \cdots \times {\mathcal{Z}}_1)$ with K legitimate receivers and M eavesdroppers is characterized by the probability transition function $p_{Y_K\dots Y_1{Z}_M\dots Z_1|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,K]$ and $Z_m\in {\mathcal{Z}}_m$ denotes the channel output corresponding to the eavesdropper $m\in [1,M]$. The broadcast channel is assumed to gradually degrade in such a way that each legitimate receiver has a better channel than any eavesdropper, that is:

$$\begin{array}{c}\hfill X-Y_K-\cdots -Y_1-Z_M-\cdots -Z_1\end{array}$$

(1)

forms a Markov chain. Although we consider physically degradation, the polar coding schemes proposed in this paper are also suitable for stochastically degraded channels (see Remark 2).

2.1. Degraded Broadcast Channel with Non-Layered Decoding and Layered Secrecy

In this model (see Figure 1), the transmitter wishes to send M messages ${\{W_m\}}_{m=1}^M$ to the K legitimate receivers. The non-layered decoding structure requires the legitimate receiver $k\in [1,K]$ to reliably decode all M messages, and the layered secrecy structure requires the eavesdropper $m\in [1,M]$ to be kept ignorant about messages ${\{W_i\}}_{i=m}^M$. Consider a $(⎡2^{n{R}_1}⎤,\dots ,⎡2^{n{R}_M}⎤,n)$ code for the DBC-NLD-LS, where $W_m\in [⎡2^{n{R}_m}⎤]$ for any $m\in [1,M]$. The reliability condition to be satisfied by this code is measured in terms of the average probability of error at each legitimate receiver and is given by:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\mathbb{P}\left[({\hat{W}}_1,\dots ,{\hat{W}}_M)\ne (W_1,\dots ,W_M)\right]=0,\mathrm{for}\mathrm{any}\mathrm{legitimate}\mathrm{receiver}k\in [1,K].\end{array}$$

(2)

On the other hand, the strong secrecy condition to be satisfied by the code is measured in terms of the information leakage at each eavesdropper and is given by:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}I(W_m,W_{m+1},\dots ,W_M;Z_m^n)=0,\mathrm{for}\mathrm{the}\mathrm{eavesdropper}m\in [1,M].\end{array}$$

(3)

A tuple of rates $(R_1,\dots ,R_M)\in {\mathbb{R}}_{+}^M$ is achievable for the DBC-NLD-LS if there exists a sequence of $(⎡2^{n{R}_1}⎤,\dots ,⎡2^{n{R}_M}⎤,n)$ codes satisfying Equations (2) and (3).

Proposition 1

(Adapted from [4,5]). The achievable region of the DBC-NLD-LS is the union of all M-tuples of rates $(R_1,\dots ,R_M)\in {\mathbb{R}}_{+}^M$ satisfying the following inequalities,

$$\begin{array}{c}\hfill {\displaystyle \sum _{i=m}^M}{R}_i\le I(X;Y_1)-I(X;Z_m),m=1,\dots ,M,\end{array}$$

where the union is taken over all distributions $p_X$.

The proof for the case of only one legitimate receiver in the context of the fading wiretap channel is provided in [5], where the information-theoretic achievable scheme is based on embedded coding, stochastic encoding and rate sharing. Due to the degradedness condition of Equation (1), by applying the data processing inequality and Fano’s inequality, an achievable scheme ensuring the reliability condition in Equation (2) for the legitimate Receiver 1 will satisfy it for any legitimate receiver $k\in [2,K]$.

Corollary 1.

The achievable subregion of the DBC-NLD-LS without considering rate sharing is a K-orthotope defined by the closure of all K-tuples of rates $(R_1,\dots ,R_M)\in {\mathbb{R}}_{+}^M$ satisfying:

$$\begin{array}{cc}\hfill R_m& \le I(X;Z_{m+1})-I(X;Z_m),m=1,\dots ,M-1,\hfill \\ \hfill R_M& \le I(X;Y_1)-I(X;Z_M).\hfill \end{array}$$

2.2. Degraded Broadcast Channel with Layered Decoding and Non-Layered Secrecy

In this model (see Figure 2), the transmitter wishes to send K messages ${\{W_{\ell }\}}_{\ell =1}^K$ to the K legitimate receivers. The layered decoding structure requires the legitimate receiver $k\in [1,K]$ to reliably decode the messages ${\{W_{\ell }\}}_{\ell =1}^k$, and the non-layered secrecy structure requires the eavesdropper $m\in [1,M]$ to be kept ignorant of all K messages. Consider a $(⎡2^{n{R}_1}⎤,\dots ,⎡2^{n{R}_K}⎤,n)$ code for the DBC-LD-NLS, where $W_{\ell }\in [⎡2^{n{R}_{\ell }}⎤]$ for any $\ell \in [1,K]$. The reliability condition to be satisfied by this code is:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\mathbb{P}\left[({\hat{W}}_1,\dots ,{\hat{W}}_{k-1},{\hat{W}}_k)\ne (W_1,\dots ,W_{k-1},W_k)\right]=0,\mathrm{for}\mathrm{the}\mathrm{legitimate}\mathrm{receiver}k\in [1,K],\end{array}$$

(4)

and the strong secrecy condition is given by:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}I(W_1,\dots ,W_K;Z_m^n)=0,\mathrm{for}\mathrm{any}\mathrm{eavesdropper}m\in [1,M].\end{array}$$

(5)

A tuple of rates $(R_1,\dots ,R_K)\in {\mathbb{R}}_{+}^K$ is achievable for the DBC-LD-NLS if there exists a sequence of $(⎡2^{n{R}_1}⎤,\dots ,⎡2^{n{R}_K}⎤,n)$ codes such that they satisfy Equations (4) and (5).

Proposition 2

(Adapted from [4,6]). The achievable region of the DBC-LD-NLS is the union of all K-tuples of rates $(R_1,\dots ,R_K)\in {\mathbb{R}}_{+}^K$ satisfying the following inequalities,

$$\begin{array}{c}\hfill {\displaystyle \sum _{\ell =1}^k}{R}_{\ell }\le {\displaystyle \sum _{\ell =1}^k}I(V_{\ell };Y_{\ell }|V_{\ell -1})-I(V_k,Z_M),k=1,\dots ,K,\end{array}$$

where $V_0\triangleq ⌀$ and $V_K\triangleq X$, and the union is taken over all distributions $p_{V_1\dots V_K}$ such that $V_1-V_2-\cdots -V_K$ forms a Markov chain.

The proof for the case of only one eavesdropper is provided in [6], where the information-theoretic achievable scheme is based on superposition coding, stochastic encoding and rate sharing. Due to the degradedness condition of Equation (1), note that any achievable scheme ensuring the strong secrecy condition in Equation (5) for the eavesdropper M will also satisfy it for any eavesdropper $m\in [1,M-1]$.

Corollary 2.

The achievable subregion of the DBC-LD-NLS without considering rate sharing is a K-orthotope defined by the closure of all K-tuples of rates $(R_1,\dots ,R_K)\in {\mathbb{R}}_{+}^K$ satisfying:

$$\begin{array}{cc}\hfill R_{\ell }& \le I(V_{\ell };Y_{\ell }|V_{\ell -1})-I(V_{\ell };Z_M|V_{\ell -1}),\ell =1,\dots ,K.\hfill \end{array}$$

3. Review of Polar Codes

Let $(\mathcal{X}\times \mathcal{Y},p_{XY})$ be a Discrete Memoryless Source (DMS), where $X\in \{0,1\}$ (see Endnote [24]—which refers to References [25,26]) and $Y\in \mathcal{Y}$. The polar transform over the n-sequence $X^n$, n being any power of two, 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 [27]. Since $G_n=G_n^{-1}$, then $X^n=U^n{G}_n$.

The polarization theorem for source coding with side information [27] (Theorem 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:

$$\begin{array}{cc}\hfill {\mathcal{H}}_{X|Y}^{(n)}& \triangleq \left\{j\in [n]:H\left(U(j)|U^{1:j-1},Y^n\right)\ge 1-{\delta }_n\right\},\hfill \\ \hfill {\mathcal{L}}_{X|Y}^{(n)}& \triangleq \left\{j\in [n]:H\left(U(j)|U^{1:j-1},Y^n\right)\le {\delta }_n\right\},\hfill \end{array}$$

where ${\delta }_n\triangleq 2^{-n^{\beta }}$ for some $\beta \in (0,\frac{1}{2})$. Then, by [27] (Theorem 1), 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}}\cap {({\mathcal{L}}_{X|Y}^{(n)})}^{\mathrm{C}}|=0$, i.e., the number of elements that have not been polarized is asymptotically negligible in terms of rate. Furthermore, [27] (Theorem 2) 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 [27] (Proposition 2). 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$ [21,22,23].

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 ${\tilde{U}}^n$ and applies the inverse polar transform ${\tilde{X}}^n={\tilde{U}}^n{G}_n$, with distribution ${\tilde{q}}_{X^n}$ (since the polar-based encoder will construct random variables that must approach the target distribution of the DMS, throughout this paper, we use a tilde above the random variables to emphasize this purpose). 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 [28].

To conclude this part, the following lemma provides a useful property of polar codes for the DBC.

Lemma 1

(Subset property, adapted from [14] (Lemma 4)). Let $(X,Y_2,Y_1)$ be random variables such that $X-Y_2-Y_1$ forms a Markov chain. Then, the following property holds for the polar transform $U^n=X^n{G}_n$,

$$\begin{array}{c}H\left(U(j)|U^{1:j-1}\right)\ge H\left(U(j)|U^{1:j-1},Y_1^n\right)\ge H\left(U(j)|U^{1:j-1},Y_2^n\right)\forall j\in [n],\mathit{which}\mathit{implies}\\ {\mathcal{L}}_X^{(n)}\subseteq {\mathcal{L}}_{X|Y_1}^{(n)}\subseteq {\mathcal{L}}_{X|Y_2}^{(n)},\mathit{and}{\mathcal{H}}_{X|Y_2}^{(n)}\subseteq {\mathcal{H}}_{X|Y_1}^{(n)}\subseteq {\mathcal{H}}_X^{(n)}.\end{array}$$

Remark 1.

The subset property also holds if the sets are defined based on the Bhattacharyya parameters because, under the previous Markov chain condition, $Z\left(U(j)|U^{1:j-1}\right)\ge Z\left(U(j)|U^{1:j-1},Y_1^n\right)\ge Z\left(U(j)|U^{1:j-1},Y_2^n\right)$.

Remark 2.

According to [14] (Lemma 4), the subset property also holds if the channels are stochastically degraded. Therefore, since the construction of the polar codes proposed in the following sections is based basically on Lemma 1, the polar coding schemes are suitable for physically- and stochastically-degraded channels.

4. Polar Coding Scheme For the DBC-NLD-LS

The polar coding scheme provided in this section is designed to achieve the supremum of the achievable rates given in Corollary 1 (secrecy-capacity without rate sharing). Thus, consider the DMS $\left(\mathcal{X}\times {\mathcal{Y}}_K\times \cdots \times {\mathcal{Y}}_1\times {\mathcal{Z}}_M\times \cdots \times {\mathcal{Z}}_1,p_{X{Y}_K\dots Y_1{Z}_M\dots Z_1}\right)$ that represents the input and output random variables involved in the achievable subregion of Corollary 1, where $\mathcal{X}=\{0,1\}$. Let $(X^n,Y_K^n,\dots ,Y_1^n,Z_M^n,\dots ,Z_1^n)$ be an i.i.d. n-sequence of this source. We define the polar transform $U^n\triangleq X^n{G}_n$, whose distribution is $p_{U^n}(u^n)=p_{X^n}(u^n{G}_n)$ (due to the invertibility of $G_n$), and we write:

$$\begin{array}{c}\hfill p_{U^n}(u^n)\triangleq {\displaystyle \prod _{j=1}^n}{p}_{U(j)|U^{1:j-1}}(u(j)|u^{1:j-1}).\end{array}$$

(6)

4.1. Polar Code Construction

Let ${\delta }_n\triangleq 2^{-n^{\beta }}$, where $\beta \in (0,\frac{1}{2})$. Based on $p_{X{Y}_K\dots Y_1{Z}_M\dots Z_1}$, we define:

$$\begin{array}{cc}\hfill {\mathcal{H}}_X^{(n)}& \triangleq \left\{j\in [n]:H\left(U(j)|U^{1:j-1}\right)\ge 1-{\delta }_n\right\},\hfill \end{array}$$

(7)

$$\begin{array}{cc}\hfill {\mathcal{L}}_X^{(n)}& \triangleq \{j\in [n]:H\left(U(j)|U^{1:j-1})\le {\delta }_n\right\},\hfill \end{array}$$

(8)

$$\begin{array}{cc}\hfill {\mathcal{L}}_{X|Y_k}^{(n)}& \triangleq \left\{j\in [n]:H\left(U(j)|U^{1:j-1},Y_k^n\right)\le {\delta }_n\right\},k=1,\dots ,K,\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill {\mathcal{H}}_{X|Y_k}^{(n)}& \triangleq \left\{j\in [n]:H\left(U(j)|U^{1:j-1},Y_k^n\right)\ge 1-{\delta }_n\right\},k=1,\dots ,K,\hfill \end{array}$$

(10)

$$\begin{array}{cc}\hfill {\mathcal{H}}_{X|Z_m}^{(n)}& \triangleq \left\{j\in [n]:H\left(U(j)|U^{1:j-1},Z_m^n\right)\ge 1-{\delta }_n\right\},m=1,\dots ,M.\hfill \end{array}$$

(11)

Then, based on the previous sets, we define the following partition of the universal set $[n]$,

$$\begin{array}{cc}\hfill {\mathcal{I}}_M^{(n)}& \triangleq {\mathcal{H}}_{X|Z_M}^{(n)}\cap {\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}},\hfill \end{array}$$

(12)

$$\begin{array}{cc}\hfill {\mathcal{I}}_m^{(n)}& \triangleq {\mathcal{H}}_{X|Z_m}^{(n)}\cap {\left({\mathcal{H}}_{X|Z_{m+1}}^{(n)}\right)}^{\mathrm{C}},m=1,\dots ,M-1,\hfill \end{array}$$

(13)

$$\begin{array}{cc}\hfill {\mathcal{F}}^{(n)}& \triangleq {\mathcal{H}}_{X|Y_1}^{(n)},\hfill \end{array}$$

(14)

$$\begin{array}{cc}\hfill {\mathcal{C}}^{(n)}& \triangleq {\mathcal{H}}_X^{(n)}\cap {\left({\mathcal{H}}_{X|Z_1}^{(n)}\right)}^{\mathrm{C}},\hfill \end{array}$$

(15)

$$\begin{array}{cc}\hfill {\mathcal{T}}^{(n)}& \triangleq {\left({\mathcal{H}}_X^{(n)}\right)}^{\mathrm{C}},\hfill \end{array}$$

(16)

which is graphically represented in Figure 3. Roughly speaking, in order to ensure reliability and strong secrecy, the distribution of ${\tilde{U}}^n$ after the encoding process must be close in terms of statistical distance to the distribution given in Equation (6) corresponding to the original DMS. Hence, the elements $U(j)$ such that $j\in {\mathcal{H}}_X^{(n)}$ will be suitable for storing uniformly-distributed random sequences. On the other hand, $U[{\mathcal{T}}^{(n)}]$ will not, and the elements $U(j)$ such that $j\in {\mathcal{T}}^{(n)}$ will be constructed somehow from $U^{1:j-1}$ and the distribution $p_{U(j)|U^{1:j-1}}$. The set ${\mathcal{I}}_m^{(n)}$ ($m\in [1,M]$) belongs to ${\mathcal{H}}_{X|Z_m}^{(n)}$, and by Lemma 1, we have ${\mathcal{H}}_{X|Z_m}^{(n)}\subseteq {\mathcal{H}}_{X|Z_{m^{\prime }}}^{(n)}$ for any $m^{\prime }<m$. Thus, $U[{\mathcal{I}}_m^{(n)}]$ will be suitable for storing information to be secured from Eavesdroppers 1–m. Since ${\mathcal{C}}^{(n)}\subseteq {({\mathcal{H}}_{X|Z_m}^{(n)})}^{\mathrm{C}}$ for any $m\in [1,M]$, the sequence $U\left[{\mathcal{C}}^{(n)}\right]$ cannot contain information to be secured from any eavesdropper, and it will be used to store the local randomness [8] required to confuse the eavesdroppers (the local randomness in polar codes plays the same role as the stochastic encoding used in [1,2]). According to [27] (Theorem 2), the legitimate Receiver 1 will be able to reliably infer $U[{\mathcal{L}}_{X|Y_1}^{(n)}]$ given $Y_1^n$ and $U[{({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$. Hence, if the polar coding scheme somehow make the entries $U(j)$ such that j belongs to ${\mathcal{F}}^{(n)}$ and ${({\mathcal{H}}_{X|Y_1}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}$ (hatched areas in Figure 3) available to the legitimate Receiver 1, this receiver will be able to reliably infer the entire sequence $U^n$. In this sense, $U[{\mathcal{F}}^{(n)}]$ will be used to store the uniformly-distributed random sequence provided by a source of common randomness that will be available to all parties. Since ${\mathcal{F}}^{(n)}\subseteq {\mathcal{H}}_{X|Z_m}^{(n)}$ for any $m\in [1,M]$, the knowledge of $U[{\mathcal{F}}^{(n)}]$ of the eavesdroppers will not compromise the strong secrecy condition. On the other hand, $U[{({\mathcal{H}}_{X|Y_1}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$ will contain secret information or elements that cannot be known directly by all the eavesdroppers. Therefore, the transmitter somehow will secretly send it to the legitimate receivers. Nevertheless, as will be seen, this additional transmission will incur an asymptotically negligible rate penalty. Finally, by Lemma 1, we have ${({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}\supseteq {({\mathcal{L}}_{X|Y_k}^{(n)})}^{\mathrm{C}}$ for any $k>1$. Hence, given $U[{({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$, all the legitimate receivers will be able to reliably infer the entire sequence $U^n$ from their own channel observations.

Remark 3.

The goal of the polar code construction is to obtain the entropy terms ${\{H(U(j)|U^{1:j-1})\}}_{j=1}^n$, ${\{H(U(j)|U^{1:j-1},Y_1^n)\}}_{j=1}^n$ and ${\{H(U(j)|U^{1:j-1},Z_m^n)\}}_{j=1}^n$ for all $m\in [1,M]$ required to define the sets in Equations (7)–(11) and, consequently, to obtain the partition of $[n]$ given in Equations (12)–(16). In Section 6, we discuss further how to construct polar codes under both reliability and secrecy constraints.

4.2. Polar Encoding

The polarization-based encoder aims to construct the sequence ${\tilde{U}}^n$ and, consequently, ${\tilde{X}}^n={\tilde{U}}^n{G}_n$. Let $W_m$ for all $m\in [1,M]$ and C be uniformly-distributed random vectors of size $|{\mathcal{I}}_m^{(n)}|$ and $|{\mathcal{C}}^{(n)}|$, respectively, where C represents the local randomness required to confuse the eavesdroppers, and recall that $W_m$ represents the message m that is intended for all legitimate receivers. Let F be a given uniformly-distributed random $|{\mathcal{F}}^{(n)}|$-sequence, which represents the source of common randomness that is available to all parties. The encoder constructs the sequence ${\tilde{u}}^n$ as follows. Consider the realizations $w_m$ for all $m\in [1,M]$, c and f, whose elements have been indexed by the set of indices ${\mathcal{I}}_m^{(n)}$, ${\mathcal{C}}^{(n)}$ and ${\mathcal{F}}^{(n)}$, respectively. The encoder draws ${\tilde{u}}^n$ from the distribution:

$$\begin{array}{c}\hfill {\tilde{q}}_{U(j)|U^{1:j-1}}(\tilde{u}(j)|{\tilde{u}}^{1:j-1})\triangleq \left\{\begin{array}{cc}𝟙\left\{\tilde{u}(j)=w_m(j)\right\}\hfill & \mathrm{if}j\in {\mathcal{I}}_m^{(n)},m=1,\dots ,M,\hfill \\ 𝟙\left\{\tilde{u}(j)=c(j)\right\}\hfill & \mathrm{if}j\in {\mathcal{C}}^{(n)},\hfill \\ 𝟙\left\{\tilde{u}(j)=f(j)\right\}\hfill & \mathrm{if}j\in {\mathcal{F}}^{(n)},\hfill \\ p_{U(j)|U^{1:j-1}}\left(\tilde{u}(j)|{\tilde{u}}^{1:j-1}\right)\hfill & \mathrm{if}j\in {\left({\mathcal{H}}_X^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_X^{(n)}\right)}^{\mathrm{C}},\hfill \\ 𝟙\left\{\tilde{u}(j)={\xi }^{(j)}({\tilde{u}}^{1:j-1})\right\}\hfill & \mathrm{if}j\in {\mathcal{L}}_X^{(n)},\hfill \end{array}\right.\end{array}$$

(17)

where:

$$\begin{array}{c}\hfill {\xi }^{(j)}({\tilde{u}}^{1:j-1})\triangleq \underset{u\in \mathcal{X}}{arg\; max}{p}_{U(j)|U^{1:j-1}}(u|{\tilde{u}}^{1:j-1}),\end{array}$$

(18)

$p_{U(j)|U^{1:j-1}}$ being the distribution induced by the original DMS. Note that ${\mathcal{T}}^{(n)}=({({\mathcal{H}}_X^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_X^{(n)})}^{\mathrm{C}})\cup {\mathcal{L}}_X^{(n)}$, and according to Equation (17), $\tilde{U}[{\mathcal{L}}_X^{(n)}]$ is constructed deterministically by adapting the SC encoding algorithm in [20], while $\tilde{U}[{({\mathcal{H}}_X^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_X^{(n)})}^{\mathrm{C}}]$ is constructed randomly. By [27] (Theorem 1), we have that the amount of randomness for SC encoding will be asymptotically negligible in terms of rate. Then, the encoder computes ${\tilde{X}}^n={\tilde{U}}^n{G}_n$ and transmits it over the DBC, inducing $({\tilde{Y}}_K,\dots ,{\tilde{Y}}_1,{\tilde{Z}}_M,\dots ,{\tilde{Z}}_1)$.

Finally, besides the sequence ${\tilde{X}}^n$, the encoder outputs the following additional secret sequence,

$$\begin{array}{c}\hfill \mathsf{\Phi }\triangleq \tilde{U}\left[{\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\right].\end{array}$$

(19)

This sequence $\mathsf{\Phi }$ must be additionally transmitted to all legitimate receivers keeping it masked from the eavesdroppers. To do so, the transmitter can perform a modulo-two addition between $\mathsf{\Phi }$ and a uniformly-distributed secret key that is privately shared with the legitimate receivers and somehow additionally send it to them. Nevertheless, by [27] (Theorem 1), we know that this additional transmission is asymptotically negligible in terms of rate.

Remark 4.

The additional secret sequence Φ can be divided into two parts: $\tilde{U}[{\mathcal{H}}_X^{(n)}\cap {({\mathcal{H}}_{X|Y_1}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$, which will be uniformly distributed according to Equation (17), and the remaining part that will not. The transmitter could make the uniformly-distributed part available to the legitimate receivers by using a chaining structure as the one presented in [9]. However, such a scheme requires the transmission to take place over several blocks of size n. Moreover, it requires having a large memory capacity on either the transmitter or the legitimate receivers, which can make the polar coding scheme unpractical in communication systems.

4.3. Polar Decoding

Before the decoding process, consider that the realization of the source of common randomness F is available to all parties and the sequence $\mathsf{\Phi }$ has been successfully received by the legitimate receivers.

The legitimate receiver $k\in [1,K]$ forms an estimate ${\hat{U}}^n$ of the sequence ${\tilde{U}}^n$ as follows. Given that $\mathsf{\Phi }$ and F are available, notice that it knows $\tilde{U}[{({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$. Moreover, by Lemma 1, ${({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}\supseteq {({\mathcal{L}}_{X|Y_k}^{(n)})}^{\mathrm{C}}$ for any $k>1$. Thus, the k-th legitimate receiver performs SC decoding for source coding with side information [27] to construct ${\tilde{U}}^n$ from $\tilde{U}[{({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$ and its channel output observations ${\tilde{Y}}_k$. In Section 4.5.3, we show formally that the reliability condition in Equation (2) is satisfied at each legitimate receiver $k\in [1,K]$.

4.4. Information Leakage

Besides the observations ${\tilde{Z}}_m^n$, the eavesdropper $m\in [1,M]$ has access to the common randomness $F=\tilde{U}[{\mathcal{F}}^{(n)}]$. Thus, the information about the messages ${\{W_i\}}_{i=m}^M$ leaked to this eavesdropper is:

$$\begin{array}{c}\hfill I(W_m,\dots ,W_M;F,{\tilde{Z}}_m^n)=I\left(\tilde{U}\left[{\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right];\tilde{U}\left[{\mathcal{F}}^{(n)}\right],{\tilde{Z}}_m^n\right).\end{array}$$

(20)

In Section 4.5.4, we prove that $(W_m,W_{m+1},\dots ,W_M)$ is asymptotically statistically independent of $(F,{\tilde{Z}}_m^n)$.

4.5. Performance of the Polar Coding Scheme

The analysis of the polar coding scheme described previously leads to the following theorem.

Theorem 1.

Consider an arbitrary DBC $\left(\mathcal{X},p_{Y_K\dots Y_1{Z}_M\dots Z_1|X},{\mathcal{Y}}_K\times \cdots \times {\mathcal{Y}}_1\times {\mathcal{Z}}_M\times \cdots \times {\mathcal{Z}}_1\right)$ such that $\mathcal{X}\in \{0,1\}$ and $p_{Y_K\dots Y_1{Z}_M\dots Z_1|X}$ satisfies the Markov chain condition $X-Y_K-\cdots -Y_1-Z_M-\cdots -Z_1$. The polar coding scheme described in Section 4.1, Section 4.2, Section 4.3 and Section 4.4 achieves any rate tuple of the region defined in Corollary 1, satisfying the reliability and strong secrecy conditions given in Equations (2) and (3), respectively.

Corollary 3.

Since $\tilde{U}[{\mathcal{I}}_m^{(n)}]$ for some $m\in [1,M]$ can contain information to be secured from Eavesdroppers 1–m, the polar coding scheme described in Section 4.1, Section 4.2, Section 4.3 and Section 4.4 can achieve the entire region considering rate sharing of Proposition 1 by storing part of any message $W_{m^{\prime }}$ such that $m^{\prime }<m$ into $\tilde{U}[{\mathcal{I}}_m^{(n)}]$ instead of part of $W_m$.

Corollary 4.

If we consider a communication scenario requiring transmissions over several blocks of size n, the same realization of the source of common randomness F that is known by all parties could be used at each block, and the reliability and the strong secrecy conditions would still be ensured.

The proof of Theorem 1 follows in four steps with similar reasoning as in [13] and is provided in Section 4.5.1, Section 4.5.2, Section 4.5.3 and Section 4.5.4. The proof of Corollary 3 is immediate, and the proof of Corollary 4 is provided in Section 4.5.5.

4.5.1. Transmission Rates

In this step, we prove that the polar coding scheme approaches the corner point of the subregion defined in Corollary 1. For any $m\in [1,M-1]$, the rate $R_m$ corresponding to the message $W_m$ satisfies:

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim}{R}_m=\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{I}}_m^{(n)}|& \stackrel{(a)}{=}\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{H}}_{X|Z_m}^{(n)}\cap {\left({\mathcal{H}}_{X|Z_{m+1}}^{(n)}\right)}^{\mathrm{C}}|\hfill \\ & \stackrel{(b)}{=}\underset{n\to \infty }{lim}\frac{1}{n}\left(|{\mathcal{H}}_{X|Z_m}^{(n)}|-|{\mathcal{H}}_{X|Z_{m+1}}^{(n)}|\right)\hfill \\ & \stackrel{(c)}{=}I(X;Z_{m+1})-I(X;Z_m),\hfill \end{array}$$

where $(a)$ follows from the definition of the set ${\mathcal{I}}_m^{(n)}$ in Equation (13), $(b)$ holds because, by Lemma 1, ${\mathcal{H}}_{X|Z_m}^{(n)}\supseteq {\mathcal{H}}_{X|Z_{m+1}}^{(n)}$, and $(c)$ follows from [27] (Theorem 1). Similarly, according to Equation (12), we obtain:

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim}{R}_M& =\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{I}}_M^{(n)}|=\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{H}}_{X|Z_M}^{(n)}\cap {\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}|=I(X;Y_1)-I(X;Z_M).\hfill \end{array}$$

4.5.2. Distribution of the DMS after the Polar Encoding

Let ${\tilde{q}}_{U^n}$ be the distribution of ${\tilde{U}}^n$ after the encoding in Section 4.2. The following lemma shows that ${\tilde{q}}_{U^n}$ and the distribution $p_{U^n}$ in Equation (6) of the original DMS are nearly statistically indistinguishable for sufficiently large n and, consequently, so are the overall distributions ${\tilde{q}}_{X{Y}_K\dots Y_1{Z}_M\dots Z_1}$ and $p_{X{Y}_K\dots Y_1{Z}_M\dots Z_1}$.

Lemma 2.

Let ${\delta }_n=2^{-n^{\beta }}$ for some $\beta \in (0,\frac{1}{2})$. Then,

$$\begin{array}{cc}\hfill \mathbb{V}({\tilde{q}}_{U^n},p_{U^n})& \le {\delta }_{\mathit{nld}-\mathit{ls}}^{(n)},\hfill \\ \hfill \mathbb{V}({\tilde{q}}_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n},p_{X{Y}_K\dots Y_1{Z}_M\dots Z_1})=\mathbb{V}({\tilde{q}}_{U^n},p_{U^n})& \le {\delta }_{\mathit{nld}-\mathit{ls}}^{(n)},\hfill \end{array}$$

where ${\delta }_{\mathit{nld}-\mathit{ls}}^{(n)}\triangleq n\sqrt{4\sqrt{n{\delta }_{n}ln2}(2n-log(2\sqrt{n{\delta }_{n}ln2}))+{\delta }_n}+\sqrt{2n{\delta }_{n}ln2}$.

Proof. 

See Appendix A, setting $L=1$. □

Remark 5.

The first term of ${\delta }_{\mathit{nld}-\mathit{ls}}^{(n)}$ bounds the impact on the total variation distance of using the deterministic SC encoding in Equation (18) for the entries $\tilde{U}[{\mathcal{L}}_X^{(n)}]$, while the second term bounds the impact of storing uniformly-distributed random sequences (messages, local randomness and common randomness) into the entries $\tilde{U}[{\mathcal{H}}_X^{(n)}]$.

As will be seen in the following subsections, an encoding process satisfying Lemma 2 is crucial for the reliability and the secrecy performance of the polar code.

4.5.3. Reliability Performance

Consider the probability of incorrectly decoding all messages ${\{W_m\}}_{m=1}^M$ at the legitimate receiver $k\in [1,K]$. Let ${\tilde{q}}_{X^n{Y}_k^n}$ and $p_{X^n{Y}_k^n}$ be the marginal distributions of ${\tilde{q}}_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n}$ and $p_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n}$, respectively. Consider an optimal coupling [29] (Proposition 4.7) between ${\tilde{q}}_{X^n{Y}_k^n}$ and $p_{X^n{Y}_k^n}$ such that:

$$\begin{array}{c}\hfill \mathbb{P}\left[{\mathcal{E}}_{X^n{Y}_k^n}\right]=\mathbb{V}({\tilde{q}}_{X^n{Y}_k^n},p_{X^n{Y}_k^n}),\end{array}$$

where ${\mathcal{E}}_{X^n{Y}_k^n}\triangleq \{({\tilde{X}}^n,{\tilde{Y}}_k^n)\ne (X^n,Y_k^n)\}$ or, equivalently, ${\mathcal{E}}_{X^n{Y}_k^n}\triangleq \{({\tilde{U}}^n,{\tilde{Y}}_k^n)\ne (U^n,Y_k^n)\}$ because of the invertibility of $G_n$. Thus, for the legitimate receiver $k\in [1,K]$, we obtain:

$$\begin{array}{cc}\mathbb{P}\left[({\hat{W}}_1,\dots {\hat{W}}_M)\ne (W_1,\dots ,W_M)\right]\hfill & \le \mathbb{P}\left[{\hat{U}}^n\ne {\tilde{U}}^n\right]\hfill \\ & =\mathbb{P}\left[{\hat{U}}^n\ne {\tilde{U}}^n|{\mathcal{E}}_{X^n{Y}_k^n}^{\mathrm{C}}\right]\mathbb{P}\left[{\mathcal{E}}_{X^n{Y}_k^n}^{\mathrm{C}}\right]+\mathbb{P}\left[{\hat{U}}^n\ne {\tilde{U}}^n|{\mathcal{E}}_{X^n{Y}_k^n}\right]\mathbb{P}\left[{\mathcal{E}}_{X^n{Y}_k^n}\right]\hfill \\ & \le \mathbb{P}\left[{\hat{U}}^n\ne {\tilde{U}}^n|{\mathcal{E}}_{X^n{Y}_k^n}^{\mathrm{C}}\right]+\mathbb{P}\left[{\mathcal{E}}_{X^n{Y}_k^n}\right]\hfill \\ & \stackrel{(a)}{\le }\sum _{j\in {\mathcal{L}}_{X|Y_1}^{(n)}}Z\left(U(j)|U^{1:j-1},Y_k^n\right)+\mathbb{P}\left[{\mathcal{E}}_{X^n{Y}_k^n}\right]\hfill \\ & \stackrel{(b)}{\le }n\sqrt{{\delta }_n}+\mathbb{P}\left[{\mathcal{E}}_{X^n{Y}_k^n}\right]\hfill \\ & \stackrel{(c)}{\le }n\sqrt{{\delta }_n}+{\delta }_{\mathit{nld}-\mathit{ls}}^{(n)},\hfill \end{array}$$

(21)

where $(a)$ holds by [27] (Theorem 2) because $\tilde{U}[{({\mathcal{L}}_{X|Y_1}^{(n)})}^{\mathrm{C}}]$ is available to all receivers, $(b)$ holds by Lemma 1, that is, $Z(U(j)|U^{1:j-1},Y_k^n)\le Z(U(j)|U^{1:j-1},Y_1^n)$ for any $k>1$, and by the definition of ${\mathcal{L}}_{X|Y_1}^{(n)}$ in Equation (9) and [27] (Proposition 2), that is $Z(U(j)|U^{1:j-1},Y_1^n)\le {(H(U(j)|U^{1:j-1},Y_1^n))}^{1/2}$, and $(c)$ holds by the optimal coupling and Lemma 2 because $\mathbb{V}({\tilde{q}}_{X^n{Y}_k^n},p_{X^n{Y}_k^n})\le \mathbb{V}({\tilde{q}}_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n},p_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n})$. Therefore, the polar coding scheme satisfies the reliability condition given in Equation (2).

4.5.4. Secrecy Performance

Consider the information leakage at the eavesdropper $m\in [1,M]$ given in Equation (20). We obtain:

$$\begin{array}{cc}I(W_m,\dots ,W_M;F,{\tilde{Z}}_m^n)\hfill & =H\left(\tilde{U}\left[{\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right]\right)+H\left(\tilde{U}\left[{\mathcal{F}}^{(n)}\right]|{\tilde{Z}}_m^n\right)-H\left(\tilde{U}\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right]|{\tilde{Z}}_m^n\right)\hfill \\ & \le {\displaystyle {\sum }_{i=m}^M}|{\mathcal{I}}_i^{(n)}|+|{\mathcal{F}}^{(n)}|-H\left(\tilde{U}\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right]|{\tilde{Z}}_m^n\right).\hfill \end{array}$$

(22)

Now, we provide a lower-bound for the conditional entropy term of Equation (22). First, for large enough n,

$$\begin{array}{c}|H\left(\tilde{U}\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right]|{\tilde{Z}}_m^n\right)-H\left(U\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right]|Z_m^n\right)|\hfill \\ \stackrel{(a)}{\le }|H\left({\tilde{Z}}_m^n\right)-H\left(Z_m^n\right)|+|H\left(\tilde{U}\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right],{\tilde{Z}}_m^n\right)-H\left(U\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right],Z_m^n\right)|\hfill \\ \stackrel{(b)}{\le }\mathbb{V}({\tilde{q}}_{Z_m^n},p_{Z_m^n})log\frac{2^n}{\mathbb{V}({\tilde{q}}_{Z_m^n},p_{Z_m^n})}\hfill \\ +\mathbb{V}({\tilde{q}}_{U[({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}]Z_m^n},p_{U[({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}]Z_m^n})log\frac{2^{(n+|({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}|)}}{\mathbb{V}({\tilde{q}}_{U[({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}]Z_m^n},p_{U[({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}]Z_m^n})}\hfill \\ \stackrel{(c)}{\le }3n{\delta }_{\mathit{nld}-\mathit{ls}}^{(n)}-2{\delta }_{\mathit{nld}-\mathit{ls}}^{(n)}log{\delta }_{\mathit{nld}-\mathit{ls}}^{(n)},\hfill \end{array}$$

(23)

where $(a)$ holds by the chain rule of entropy and the triangle inequality, $(b)$ holds by [30] (Lemma 2.9) and $(c)$ holds because the function $x\mapsto xlogx$ is decreasing for $x>0$ small enough and by Lemma 2 because $\mathbb{V}({\tilde{q}}_{Z_m^n},p_{Z_m^n})\le \mathbb{V}({\tilde{q}}_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n},p_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n})$, as well as by the invertibility of $G_n$, $\mathbb{V}({\tilde{q}}_{U[({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}]Z_m^n},p_{U[({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}]Z_m^n})\le \mathbb{V}({\tilde{q}}_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n},p_{X^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n})$. Hence, we have:

$$\begin{array}{cc}H\left(\tilde{U}\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right]|{\tilde{Z}}_m^n\right)\hfill & \ge H\left(U\left[\left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}\right]|Z_m^n\right)-(3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)})\hfill \\ & \stackrel{(a)}{\ge }\sum _{j\in \left({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)}\right)\cup {\mathcal{F}}^{(n)}}H\left(U(j)|U^{1:j-1},Z_m^n\right)-(3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)})\hfill \\ & \stackrel{(b)}{\ge }\left({\displaystyle {\sum }_{i=m}^M}|{\mathcal{I}}_i^{(n)}|+|{\mathcal{F}}^{(n)}|\right)(1-{\delta }_n)-(3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}),\hfill \end{array}$$

(24)

where $(a)$ holds because conditioning does not increase the entropy and $(b)$ holds because, according to Equations (12)–(14) and Lemma 1, $({\cup }_{i=m}^M{\mathcal{I}}_i^{(n)})\cup {\mathcal{F}}^{(n)}\subseteq {\mathcal{H}}_{X|Z_m}^{(n)}$, as well as by the definition of ${\mathcal{H}}_{X|Z_m}^{(n)}$ in Equation (11).

Finally, by substituting Equation (24) into Equation (22), for n sufficiently large, we obtain:

$$\begin{array}{c}\hfill I(W_m,\dots ,W_M;F,{\tilde{Z}}_m^n)\le n{\delta }_n+3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)},\end{array}$$

(25)

Hence, the polar code satisfies the strong secrecy condition in Equation (3), and the proof of Theorem 1 is concluded.

4.5.5. Reuse of the Source of Common Randomness

Consider that the transmission takes place over B blocks of size n. We use the subscript $b\in [1,B]$ between parentheses to denote random variables associated with the block b. From Lemma 2, we have $\mathbb{V}({\tilde{q}}_{U_{(b)}^n},p_{U^n})\le {\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}$ for any $b\in [1,B]$ because we use the same encoding of Equation (17) at each block. Hence, by the union bound, the polar code satisfies the reliability condition given in Equation (2) because:

$$\begin{array}{cc}\hfill \mathbb{P}\left[{\cup }_{b=1}^B\left\{{\hat{U}}_{(b)}^n\ne {\tilde{U}}_{(b)}^n\right\}\right]& \le {\displaystyle \sum _{b=1}^B}\mathbb{P}\left[{\hat{U}}_{(b)}^n\ne {\tilde{U}}_{(b)}^n\right]\le B(n\sqrt{{\delta }_n}+{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}),\hfill \end{array}$$

where the last inequality follows from the fact that, since F and ${\mathsf{\Phi }}_{(b)}$ are perfectly known, $\mathbb{P}\left[{\hat{U}}_{(b)}^n\ne {\tilde{U}}_{(b)}^n\right]$ only depends on the decoding at block b and, consequently, can be bounded as in Equation (21).

With a slight abuse of notation, let $W_{m:M,(b_1:b_2)}$, where $1\le b_1\le b_2\le B$, denote the messages ${\{(W_{m,(b)},\dots ,W_{M,(b)})\}}_{b=b_1}^{b_2}$. It remains to show that $W_{m:M,(1:B)}$ is asymptotically statistically independent of $(F,{\tilde{Z}}_{m,(1:B)}^n)$. Since F is reused at each block, we have to consider the dependencies between the random variables of different blocks that are involved in the secrecy analysis. According to these dependencies, which are represented in the Bayesian graph of Figure 4, we obtain:

$$\begin{array}{cc}\hfill I(W_{m:M,(1:B)};{\tilde{Z}}_{m,(1:B)}^n,F)& \stackrel{(a)}{=}I(W_{m:M,(1:B)};{\tilde{Z}}_{m,(1:B)}^n|F)\hfill \\ & ={\displaystyle \sum _{b=0}^{B-1}}I(W_{m:M,(1:B)};{\tilde{Z}}_{m,(b+1)}^n|F,{\tilde{Z}}_{m,(1:b)}^n)\hfill \\ & \stackrel{(b)}{\le }B\left(n{\delta }_n+3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}\right),\hfill \end{array}$$

where $(a)$ follows from the independence between $W_{m:M,(1:B)}$ and F, and $(b)$ holds because:

$$\begin{array}{c}I(W_{m:M,(1:B)};{\tilde{Z}}_{m,(b+1)}^n|F,{\tilde{Z}}_{m,(1:b)}^n)\hfill \\ =I(W_{m:M,(1:b+1)};{\tilde{Z}}_{m,(b+1)}^n|F,{\tilde{Z}}_{m,(1:b)}^n)+I(W_{m:M,(b+2:B)};{\tilde{Z}}_{m,(b+1)}^n|F,{\tilde{Z}}_{m,(1:b)}^n,W_{m:M,(1:b+1)})\hfill \\ \le I(W_{m:M,(1:b+1)},F,{\tilde{Z}}_{m,(1:b)}^n;{\tilde{Z}}_{m,(b+1)}^n)+I(W_{m:M,(b+2:B)};{\tilde{Z}}_{m,(1:b+1)}^n,F,W_{m:M,(1:b+1)})\hfill \\ \stackrel{(a)}{=}I(W_{m:M,(1:b+1)},F,{\tilde{Z}}_{m,(1:b)}^n;{\tilde{Z}}_{m,(b+1)}^n)\hfill \\ \le I(W_{m:M,(b+1)},F;{\tilde{Z}}_{m,(b+1)}^n)+I(W_{m:M,(1:b)},{\tilde{Z}}_{m,(1:b)}^n;{\tilde{Z}}_{m,(b+1)}^n|W_{m:M,(b+1)},F)\hfill \\ \stackrel{(b)}{\le }\left(n{\delta }_n+3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}\right)+I(W_{m:M,(1:b)},{\tilde{Z}}_{m,(1:b)}^n;W_{m:M,(b+1)},{\tilde{Z}}_{m,(b+1)}^n|F)\hfill \\ \stackrel{(c)}{=}n{\delta }_n+3n{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}-2{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)}log{\delta }_{\mathrm{nld}-\mathrm{ls}}^{(n)},\hfill \end{array}$$

where $(a)$ holds because the messages at blocks $b+2$–B are independent of F and all the random variables of the previous blocks, $(b)$ follows from Equation (25) and $(c)$ holds by applying d-separation [31] over the graph of Figure 4 because $(W_{m:M,(1:b)},{\tilde{Z}}_{m,(1:b)}^n)\leftarrow F\to (W_{m:M,(b+1)},{\tilde{Z}}_{m,(b+1)}^n)$ forms a common cause and, consequently, $(W_{m:M,(1:b)},{\tilde{Z}}_{m,(1:b)}^n)$ and $(W_{m:M,(b+1)},{\tilde{Z}}_{m,(b+1)}^n)$ are independent given F.

5. Polar Coding Scheme for the DBC-LD-NLS

The polar coding scheme provided in this section is designed to achieve the supremum of the achievable rates given in Corollary 2 (secrecy-capacity without rate sharing). In this model, there are K input random variables ${\{V_{\ell }\}}_{\ell =1}^K$ (where $V_K\triangleq X$), each one corresponding to a different superposition layer. Consider the DMS $\left({\mathcal{V}}_1\times \cdots \times {\mathcal{V}}_K\times {\mathcal{Y}}_K\times \cdots \times {\mathcal{Y}}_1\times {\mathcal{Z}}_M\times \cdots \times {\mathcal{Z}}_1,p_{V_1\dots V_K{Y}_K\dots Y_1{Z}_M\dots Z_1}\right)$ that represents the input and output random variables involved in the achievable subregion of Corollary 2, where ${\mathcal{V}}_{\ell }=\{0,1\}$ for any $\ell \in [1,K]$. Let $(V_1^n,\dots ,V_K^n,Y_K^n,\dots ,Y_1^n,Z_M^n,\dots ,Z_1^n)$ be an i.i.d. n-sequence of this source. Then, we define the K polar transforms $U_{\ell }^n\triangleq V_{\ell }^n{G}_n$, where $\ell \in [1,K]$. Since $V_1-V_2-\cdots -V_K$ and, consequently, $U_1-U_2-\cdots -U_K$ (by the invertibility of $G_n$) form a Markov chain, the joint distribution of $(U_1^n,\dots ,U_K^n)$ satisfies”

$$\begin{array}{c}\hfill p_{U_1^n\dots U_K^n}(u_1^n,\dots ,u_K^n)\triangleq {\displaystyle \prod _{\ell =1}^K}{\displaystyle \prod _{j=1}^n}{p}_{U_{\ell }(j)|U_{\ell }^{1:j-1}{V}_{\ell -1}^n}\left(u_{\ell }(j)|u_{\ell }^{1:j-1},u_{\ell -1}^n{G}_n\right).\end{array}$$

(26)

5.1. Polar Code Construction

Based on $p_{V_1\dots V_K{Y}_K\dots Y_1{Z}_M\dots Z_1}$, the construction is carried out similarly at each superposition layer. Consider the polar construction at layer $\ell \in [1,K]$. Let ${\delta }_n\triangleq 2^{-n^{\beta }}$, where $\beta \in (0,\frac{1}{2})$. For the polar transform $U_{\ell }^n=V_{\ell }^n{G}_n$ associated with the ℓ-th layer, we define the sets:

$$\begin{array}{cc}\hfill {\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)}& \triangleq \left\{j\in [n]:H\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n\right)\ge 1-{\delta }_n\right\},\hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill {\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)}& \triangleq \left\{j\in [n]:H\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n\right)\le {\delta }_n\right\},\hfill \end{array}$$

(28)

$$\begin{array}{cc}\hfill {\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_k}^{(n)}& \triangleq \left\{j\in [n]:H\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n,Y_k^n\right)\le {\delta }_n\right\},k=\ell ,\dots ,K,\hfill \end{array}$$

(29)

$$\begin{array}{cc}\hfill {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_k}^{(n)}& \triangleq \left\{j\in [n]:H\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n,Y_k^n\right)\ge 1-{\delta }_n\right\},k=\ell ,\dots ,K,\hfill \end{array}$$

(30)

$$\begin{array}{cc}\hfill {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_m}^{(n)}& \triangleq \left\{j\in [n]:H\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n,Z_m^n\right)\ge 1-{\delta }_n\right\},m=1,\dots ,M,\hfill \end{array}$$

(31)

where we recall that $V_0=⌀$ when $\ell =1$ and $V_K\triangleq X$ when $\ell =K$. At each layer $\ell \in [1,K]$, based on these previous sets, we define the following partition of the universal set $[n]$,

$$\begin{array}{cc}\hfill {\mathcal{I}}_{\ell }^{(n)}& \triangleq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}\cap {\left({\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}\right)}^{\mathrm{C}},\hfill \end{array}$$

(32)

$$\begin{array}{cc}\hfill {\mathcal{F}}_{\ell }^{(n)}& \triangleq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)},\hfill \end{array}$$

(33)

$$\begin{array}{cc}\hfill {\mathcal{C}}_{\ell }^{(n)}& \triangleq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)}\cap {\left({\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}\right)}^{\mathrm{C}},\hfill \end{array}$$

(34)

$$\begin{array}{cc}\hfill {\mathcal{T}}_{\ell }^{(n)}& \triangleq {\left({\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)}\right)}^{\mathrm{C}},\hfill \end{array}$$

(35)

which is graphically represented in Figure 5. The way we define this partition at the ℓ-th layer follows similar reasoning as the one to define the partition in Section 4.1 for the DBC-NLD-LS. In this sense, $U_{\ell }[{\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)}]$ will be suitable for storing uniformly-distributed random sequences. Otherwise, $U_{\ell }[{\mathcal{T}}_{\ell }^{(n)}]$ will not and $U_{\ell }(j)$ such that $j\in {\mathcal{T}}_{\ell }^{(n)}$ will be constructed somehow from $(U_{\ell }^{1:j-1},V_{\ell -1})$ and the distribution $p_{U_{\ell }(j)|U_{\ell }^{1:j-1}{V}_{\ell -1}^n}$. Now, $U_{\ell }[{\mathcal{I}}_{\ell }^{(n)}]$ will be suitable for storing information to be secured from all eavesdroppers because ${\mathcal{I}}_{\ell }^{(n)}$ belongs to ${\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}$, and by Lemma 1, ${\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}\subseteq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_{m^{\prime }}}^{(n)}$ for any $m^{\prime }\in [1,M-1]$. Since ${\mathcal{C}}_{\ell }^{(n)}\subseteq {({\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)})}^{\mathrm{C}}$, $U[{\mathcal{C}}_{\ell }^{(n)}]$ will be used to store the local randomness required to confuse all eavesdroppers about the secret information carried on this layer. According to [27] (Theorem 2), the legitimate receiver $k\in [1,K]$ will be able to reliably infer $U_{\ell }[{\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_k}^{(n)}]$ given $Y_k^n$ and $U_{\ell }[{({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_k}^{(n)})}^{\mathrm{C}}]$. By Lemma 1, we have ${({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}\supseteq ({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_k}^{(n)}{)}^{\mathrm{C}}$ for any $\ell <k$. Therefore, given $U_{\ell }[{({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}]$, the legitimate receivers ℓ–K will be able to reliably reconstruct $U_{\ell }^n$ from its own channel observations. In this sense, $U_{\ell }[{\mathcal{F}}_{\ell }^{(n)}]$ will be used to store the random sequence provided by the source of common randomness. Since ${\mathcal{F}}_{\ell }^{(n)}\subseteq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}$, the strong secrecy condition will not be compromised. On the other hand, $U[{({\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}]$ (hatched areas in Figure 5) will contain secret information or elements that cannot be known directly by the eavesdroppers. Therefore, the transmitter somehow will make those elements available to the legitimate receivers ℓ–K keeping them masked from all eavesdroppers by incurring an asymptotically-negligible rate penalty.

As mentioned in Remark 3, the goal of the polar construction is to obtain the entropy terms associated with the sets in Equations (27)–(31) and then define the partition of $[n]$ given in Equations (32)–(35).

5.2. Polar Encoding

The superposition-based polar encoder will consist of K encoding blocks operating sequentially at each superposition layer, the block at layer $\ell \in [1,K]$ being responsible for the construction of ${\tilde{U}}_{\ell }^n$. In order to construct ${\tilde{U}}_{\ell }^n$ for some $\ell \in [2,K]$, the encoder block needs ${\tilde{V}}_{\ell -1}^n={\tilde{U}}_{\ell -1}^n{G}_n$, which have been constructed previously by the encoding block operating at the $(\ell -1)$-th layer.

Consider the encoding procedure at layer $\ell \in [1,K]$. Let $W_{\ell }$ and $C_{\ell }$ be uniformly-distributed random vectors of size $|{\mathcal{I}}_{\ell }^{(n)}|$ and $|{\mathcal{C}}_{\ell }^{(n)}|$, respectively, where $W_{\ell }$ represents the message intended for receivers ℓ–K and $C_{\ell }$ the local randomness required at the ℓ-th layer to confuse all eavesdroppers about this message. Let $F_{\ell }$ be a given uniformly-distributed random $|{\mathcal{F}}_{\ell }^{(n)}|$-sequence, which represents the source of common randomness that is available to all parties. The ℓ-th encoding block constructs the sequence ${\tilde{u}}_{\ell }^n$ as follows. Given the realizations $w_{\ell }$, $c_{\ell }$ and $f_{\ell }$, whose elements have been indexed by the set of indices ${\mathcal{I}}_{\ell }^{(n)}$, ${\mathcal{C}}_{\ell }^{(n)}$ and ${\mathcal{F}}_{\ell }^{(n)}$, respectively, and given ${\tilde{v}}_{\ell -1}^n={\tilde{u}}_{\ell -1}^n{G}_n$ provided by the previous encoding block (recall that ${\tilde{v}}_0^n\triangleq ⌀$ at the first layer), the ℓ-th encoding block draws ${\tilde{u}}_{\ell }^n$ from:

$$\begin{array}{c}{\tilde{q}}_{U_{\ell }(j)|U_{\ell }^{1:j-1}{V}_{\ell -1}^n}\left({\tilde{u}}_{\ell }(j)|{\tilde{u}}_{\ell }^{1:j-1},{\tilde{v}}_{\ell -1}^n\right)\hfill \\ \triangleq \left\{\begin{array}{cc}𝟙\left\{{\tilde{u}}_{\ell }(j)=w_{\ell }(j)\right\}\hfill & \mathrm{if}j\in {\mathcal{I}}_{\ell }^{(n)},\hfill \\ 𝟙\left\{{\tilde{u}}_{\ell }(j)=c_{\ell }(j)\right\}\hfill & \mathrm{if}j\in {\mathcal{C}}_{\ell }^{(n)},\hfill \\ 𝟙\left\{{\tilde{u}}_{\ell }(j)=f_{\ell }(j)\right\}\hfill & \mathrm{if}j\in {\mathcal{F}}_{\ell }^{(n)},\hfill \\ p_{U_{\ell }(j)|U_{\ell }^{1:j-1}{V}_{\ell -1}^n}\left({\tilde{u}}_{\ell }(j)|{\tilde{u}}_{\ell }^{1:j-1},{\tilde{v}}_{\ell -1}^n\right)\hfill & \mathrm{if}j\in {\left({\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)}\right)}^{\mathrm{C}},\hfill \\ 𝟙\left\{{\tilde{u}}_{\ell }(j)={\xi }_{\ell }^{(j)}({\tilde{u}}_{\ell }^{1:j-1},{\tilde{v}}_{\ell -1}^n)\right\}\hfill & \mathrm{if}j\in {\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)},\hfill \end{array}\right.\hfill \end{array}$$

(36)

where:

$$\begin{array}{c}\hfill {\xi }_{\ell }^{(j)}\left({\tilde{u}}_{\ell }^{1:j-1},{\tilde{v}}_{\ell -1}^n\right)\triangleq \underset{u\in {\mathcal{V}}_{\ell }}{arg\; max}{p}_{U_{\ell }(j)|U_{\ell }^{1:j-1}{V}_{\ell -1}^n}\left(u|{\tilde{u}}_{\ell }^{1:j-1},{\tilde{v}}_{\ell -1}^n\right),\end{array}$$

(37)

$p_{U_{\ell }(j)|U_{\ell }^{1:j-1}{V}_{\ell -1}^n}$ being the distribution induced by the original DMS. Notice that ${\mathcal{T}}_{\ell }^{(n)}=({({\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)})}^{\mathrm{C}})\cup {\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)}$, and similarly to the previous model, $\tilde{U}[{\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)}]$ is constructed in a deterministic way by adapting the SC encoding algorithm in [20]; and $\tilde{U}[{({\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)})}^{\mathrm{C}}]$ is constructed randomly. By [27] (Theorem 1), the rate of the amount of randomness for SC encoding will be asymptotically negligible. After constructing ${\tilde{U}}_{\ell }^n$, the ℓ-th encoding block computes the sequence ${\tilde{V}}_{\ell }^n={\tilde{U}}_{\ell }^n{G}_n$ and delivers it to the next encoding block. If $\ell =K$, then ${\tilde{V}}_K^n\triangleq {\tilde{X}}^n$, and the encoder transmits it over the DBC, which induces the channel outputs $({\tilde{Y}}_K^n,\dots ,{\tilde{Y}}_1^n,{\tilde{Z}}_M^n,\dots ,{\tilde{Z}}_1^n)$.

Finally, besides the sequence ${\tilde{X}}^n$, the encoder outputs the following additional secret sequences,

$$\begin{array}{c}\hfill {\mathsf{\Phi }}_{\ell }\triangleq {\tilde{U}}_{\ell }\left[{\left({\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}\right)}^{\mathrm{C}}\right],\ell =1,\dots ,K,\end{array}$$

(38)

The sequence ${\mathsf{\Phi }}_{\ell }$ corresponding to the layer $\ell \in [1,K]$ must be additionally transmitted to the legitimate receivers ℓ–K keeping it masked from the eavesdroppers. To do so, the transmitter can perform a modulo-two addition between ${\{{\mathsf{\Phi }}_{\ell }\}}_{\ell =1}^K$ and a uniformly-distributed secret key privately shared with the legitimate receivers and somehow additionally send it to them. If $K\ll n$, by [27] (Theorem 1), we have that the overall rate required to transmit these additional secret sequences is asymptotically negligible, i.e., ${lim}_{n\to \infty }{\sum }_{\ell =1}^K\frac{|{\mathsf{\Phi }}_{\ell }|}{n}=0$. As for the previous model, the uniformly-distributed part of any ${\mathsf{\Phi }}_{\ell }$ could be made available to the corresponding legitimate receivers by using a chaining structure as in [9]. However, this approach will present the same disadvantages as those mentioned in Remark 4.

5.3. Polar Decoding

Consider that the realizations of ${\{F_{\ell }\}}_{\ell =1}^K$ are available to all parties, and the sequences ${\{{\mathsf{\Phi }}_{\ell }\}}_{\ell =1}^K$ have been successfully received by the corresponding legitimate receivers before the decoding process.

Consider the decoding at the legitimate receiver $k\in [1,K]$. This receiver forms the estimates ${\{{\hat{U}}_{\ell }^n\}}_{\ell =1}^k$ of the sequences ${\{{\tilde{U}}_{\ell }^n\}}_{\ell =1}^k$ in a successive manner from ${\hat{U}}_1^n$-${\hat{U}}_k^n$, and the procedure to estimate ${\tilde{U}}_{\ell }^n$ for some $\ell \in [1,k]$ is as follows. First, given that ${\mathsf{\Phi }}_{\ell }$ and $F_{\ell }$ are available, the receiver knows ${\tilde{U}}_{\ell }[{({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}]$. Moreover, by Lemma 1, $({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_k}^{(n)}{)}^{\mathrm{C}}\subseteq {\left({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}\right)}^{\mathrm{C}}$ for any $\ell <k$. Thus, given ${\tilde{U}}_{\ell }[{({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}]$, the k-th legitimate receiver performs SC decoding for source coding with side information [27] to construct ${\hat{U}}_{\ell }[{\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}]$ from ${\tilde{Y}}_k^n$, and from ${\hat{V}}_{\ell -1}^n={\hat{U}}_{\ell -1}^n{G}_n$ estimated previously. In Section 5.5.3, we show formally that the polar coding scheme satisfies the reliability condition in Equation (4).

5.4. Information Leakage

Besides the observations ${\tilde{Z}}_m^n$, the eavesdropper $m\in [1,M]$ has access to the common randomness ${\{F_{\ell }\}}_{\ell =1}^K$. Therefore, the information about all messages leaked to the m-th eavesdropper is:

$$\begin{array}{c}\hfill I(W_1,\dots ,W_K;F_1,\dots ,F_K,{\tilde{Z}}_m^n)=I\left({\tilde{U}}_1\left[{\mathcal{I}}_1^{(n)}\right],\dots ,{\tilde{U}}_K\left[{\mathcal{I}}_K^{(n)}\right];{\tilde{U}}_1\left[{\mathcal{F}}_1^{(n)}\right],\dots ,{\tilde{U}}_K\left[{\mathcal{F}}_K^{(n)}\right],{\tilde{Z}}_m^n\right).\end{array}$$

(39)

In Section 5.5.4, we prove that $(W_1,\dots ,W_K)$ is asymptotically statistically independent of $(F_1,\dots ,F_K,{\tilde{Z}}_m^n)$.

5.5. Performance of the Polar Coding Scheme

The analysis of the polar coding scheme leads to the following theorem.

Theorem 2.

Consider an arbitrary DBC $\left(\mathcal{X},p_{Y_K\dots Y_1{Z}_M\dots Z_1|X},{\mathcal{Y}}_K\times \cdots \times {\mathcal{Y}}_1\times {\mathcal{Z}}_M\times \cdots \times {\mathcal{Z}}_1\right)$ such that $\mathcal{X}\in \{0,1\}$ and $p_{Y_K\dots Y_1{Z}_M\dots Z_1|X}$ satisfies the Markov chain condition $X-Y_K-\cdots -Y_1-Z_M-\cdots -Z_1$. The polar coding scheme described in Section 5.1, Section 5.2, Section 5.3 and Section 5.4 achieves any rate tuple of the achievable region defined in Corollary 2, satisfying the reliability and strong secrecy conditions in Equations (4) and (5), respectively.

Corollary 5.

Since ${\tilde{U}}_{\ell }[{\mathcal{I}}_{\ell }^{(n)}]$ for some $\ell \in [1,K]$ can contain any information to be reliably decoded by the legitimate receivers ℓ–K, the coding scheme in Section 5.1, Section 5.2, Section 5.3 and Section 5.4 can achieve the entire region considering the rate sharing of Proposition 2 by storing part of any message $W_{{\ell }^{\prime }}$ such that ${\ell }^{\prime }>\ell$ into ${\tilde{U}}_{\ell }[{\mathcal{I}}_{\ell }^{(n)}]$ instead of part of $W_{\ell }$.

Corollary 6.

If we consider a communication scenario requiring transmissions over several blocks of size n, the same realization of the source of common randomness $(F_1,\dots ,F_K)$ that is known by all parties could be used at each block, and the reliability and the strong secrecy conditions would still be ensured.

As in Theorem 1, the proof of Theorem 2 follows in four steps and is provided in Section 4.5.1, Section 4.5.2, Section 4.5.3 and Section 4.5.4. The proof of Corollary 5 is immediate. The proof of Corollary 6 is omitted because it follows similar reasoning as in Corollary 4. Despite that in this model, we have different superposition layers, the dependencies between the random variables at different blocks have the same structure of those graphically represented in Figure 4.

5.5.1. Transmission Rates

We prove that the polar coding scheme approaches the corner point of the subregion defined in Corollary 2. For any $\ell \in [1,K]$, the transmission rate $R_{\ell }$ corresponding to the message $W_{\ell }$ satisfies:

$$\begin{array}{cc}\underset{n\to \infty }{lim}{R}_{\ell }\hfill & =\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{I}}_{\ell }^{(n)}|\stackrel{(a)}{=}\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}\cap {\left({\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}\right)}^{\mathrm{C}}|\hfill \\ & \stackrel{(b)}{=}\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}|-\underset{n\to \infty }{lim}\frac{1}{n}|{\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}|\hfill \\ & \stackrel{(c)}{=}I(V_{\ell };Y_{\ell }|V_{\ell -1})-I(V_{\ell };Z_M|V_{\ell -1}),\hfill \end{array}$$

(40)

where $(a)$ follows from the definition of the set ${\mathcal{I}}_{\ell }^{(n)}$ in Equation (32), $(b)$ holds because, by Lemma 1, ${\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}\supseteq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}$, and $(c)$ holds by [27] (Theorem 1).

5.5.2. Distribution of the DMS after the Polar Encoding

Let ${\tilde{q}}_{U_1^n\dots U_K^n}$ be the distribution of $({\tilde{U}}_1^n,\dots ,{\tilde{U}}_K^n)$ after the encoding in Section 5.2. The following lemma shows that ${\tilde{q}}_{U_1^n\dots U_K^n}$ and $p_{U_1^n\dots U_K^n}$ of the DMS are nearly statistically indistinguishable for sufficiently large n and, consequently, so are the overall distributions ${\tilde{q}}_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n}$ and $p_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n}$.

Lemma 3.

Let ${\delta }_n=2^{-n^{\beta }}$ for some $\beta \in (0,\frac{1}{2})$. Then,

$$\begin{array}{cc}\hfill \mathbb{V}({\tilde{q}}_{U_1^n\dots U_K^n},p_{U_1^n\dots U_K^n})& \le {\delta }_{\mathit{ld}-\mathit{nls}}^{(n)},\hfill \\ \hfill \mathbb{V}({\tilde{q}}_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n},p_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n})=\mathbb{V}({\tilde{q}}_{U_1^n\dots U_K^n},p_{U_1^n\dots U_K^n})& \le {\delta }_{\mathit{ld}-\mathit{nls}}^{(n)},\hfill \end{array}$$

where ${\delta }_{\mathit{ld}-\mathit{nls}}^{(n)}\triangleq Kn\sqrt{4\sqrt{n{\delta }_{n}ln2}\left(2n-log\left(2\sqrt{n{\delta }_{n}ln2}\right)\right)+{\delta }_n}+\sqrt{K2n{\delta }_{n}ln2}$.

Proof. 

See Appendix A setting $L=K$. □

Remark 6.

The first term of ${\delta }_{\mathit{ld}-\mathit{nls}}^{(n)}$ bounds the impact on the total variation distance of using the deterministic SC encoding in Equation (37) for ${\tilde{U}}_{\ell }\left[{\mathcal{L}}_{V_{\ell }|V_{\ell -1}}^{(n)}\right]$ at each layer $\ell \in [1,K]$. The second term bounds the impact of storing uniformly-distributed random sequences that are independent of ${\tilde{V}}_{\ell -1}^n$ into ${\tilde{U}}_{\ell }\left[{\mathcal{H}}_{V_{\ell }|V_{\ell -1}}^{(n)}\right]$.

5.5.3. Reliability Performance

Consider the probability of incorrectly decoding ${\{W_{\ell }\}}_{\ell =1}^k$ at the legitimate receiver $k\in [1,K]$. Let ${\tilde{q}}_{V_{\ell }^n{Y}_k^n}$ and $p_{V_{\ell }^n{Y}_k^n}$ for any $\ell \le k$ be marginals of ${\tilde{q}}_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n}$ and $p_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n}$, respectively. Consider an optimal coupling [29] (Proposition 4.7) between ${\tilde{q}}_{V_{\ell }^n{Y}_k^n}$ and $p_{V_{\ell }^n{Y}_k^n}$ such that:

$$\begin{array}{c}\hfill \mathbb{P}\left[{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\right]=\mathbb{V}({\tilde{q}}_{V_{\ell }^n{Y}_k^n},p_{V_{\ell }^n{Y}_k^n}),\end{array}$$

where ${\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\triangleq \{({\tilde{V}}_{\ell }^n,{\tilde{Y}}_k^n)\ne (V_{\ell }^n,Y_k^n)\}$ or, equivalently, ${\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\triangleq \{({\tilde{U}}_{\ell }^n,{\tilde{Y}}_k^n)\ne (U_{\ell }^n,Y_k^n)\}$ due to the invertibility of $G_n$. Furthermore, for all $\ell \in [1,k]$, we define the error events ${\mathcal{E}}_{{\hat{V}}_{\ell }^n}\triangleq \{{\hat{V}}_{\ell }^n\ne {\tilde{V}}_{\ell }^n\}$ or, equivalently, ${\mathcal{E}}_{{\hat{V}}_{\ell }^n}\triangleq \{{\hat{U}}_{\ell }^n\ne {\tilde{U}}_{\ell }^n\}$; and we define ${\mathcal{E}}_{{\hat{V}}_0^n}\triangleq \varnothing$. Hence, for any $\ell \in [1,k]$, the average probability of incorrectly decoding the message $W_{\ell }$ at the k-th receiver can be upper-bounded as:

$$\begin{array}{cc}\mathbb{P}[{\hat{W}}_{\ell }\ne W_{\ell }]\hfill & \le \mathbb{P}\left[{\hat{U}}_{\ell }^n\ne {\tilde{U}}_{\ell }^n\right]\hfill \\ & =\mathbb{P}\left[{\hat{U}}_{\ell }^n\ne {\tilde{U}}_{\ell }^n|{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}^{\mathrm{C}}\cap {\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}^{\mathrm{C}}\right]\mathbb{P}\left[{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}^{\mathrm{C}}\cap {\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}^{\mathrm{C}}\right]\hfill \\ & +\mathbb{P}\left[{\hat{U}}_{\ell }^n\ne {\tilde{U}}_{\ell }^n|{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\cup {\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}\right]\mathbb{P}\left[{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\cup {\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}\right]\hfill \\ & \le \mathbb{P}\left[{\hat{U}}_{\ell }^n\ne {\tilde{U}}_{\ell }^n|{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}^{\mathrm{C}}\cap {\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}^{\mathrm{C}}\right]+\mathbb{P}\left[{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\right]+\mathbb{P}\left[{\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}\right]\hfill \\ & \stackrel{(a)}{\le }\sum _{j\in {\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)}}Z\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n,Y_k^n\right)+\mathbb{P}\left[{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\right]+\mathbb{P}\left[{\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}\right]\hfill \\ & \stackrel{(b)}{\le }n\sqrt{{\delta }_n}+\mathbb{P}\left[{\mathcal{E}}_{V_{\ell }^n{Y}_k^n}\right]+\mathbb{P}\left[{\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}\right]\hfill \\ & \stackrel{(c)}{\le }n\sqrt{{\delta }_n}+{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}+\mathbb{P}\left[{\mathcal{E}}_{{\hat{V}}_{\ell -1}^n}\right]\hfill \end{array}$$

(41)

where $(a)$ holds by [27] (Theorem 2) because ${\tilde{U}}_{\ell }[{({\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_{\ell }}^{(n)})}^{\mathrm{C}}]$ for any $\ell \le k$ is available to the k-th receiver, $(b)$ holds by Lemma 1, by the definition of the set ${\mathcal{L}}_{V_{\ell }|V_{\ell -1}{Y}_1}^{(n)}$ in Equation (29) and by applying [27] (Proposition 2) and $(c)$ holds by the optimal coupling and Lemma 3 because $\mathbb{V}({\tilde{q}}_{V_{\ell }^n{Y}_k^n},p_{V_{\ell }^n{Y}_k^n})\le \mathbb{V}({\tilde{q}}_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n},p_{V_1^n\dots V_K^n{Y}_K^n\dots Y_1^n{Z}_M^n\dots Z_1^n})$. Thus, by induction, we obtain:

$$\begin{array}{cc}\hfill \mathbb{P}\left[({\hat{W}}_1,\dots {\hat{W}}_k)\ne (W_1,\dots ,W_k)\right]& \le {\displaystyle \sum _{\ell =1}^k}\mathbb{P}[{\hat{U}}_{\ell }\ne {\tilde{U}}_{\ell }]\le \frac{k(k+1)}{2}\left(n\sqrt{{\delta }_n}+{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}\right).\hfill \end{array}$$

(42)

Consequently, if $K\ll n$, the polar coding scheme satisfies the reliability condition in Equation (4).

5.5.4. Secrecy Performance

Consider the leakage at the eavesdropper $m\in [1,M]$ given in Equation (39). As in Equation (22), we obtain:

$$\begin{array}{c}\hfill I(W_1,\dots ,W_K;F_1,\dots ,F_K,{\tilde{Z}}_m^n)\le {\displaystyle \sum _{\ell =1}^K}|{\mathcal{I}}_{\ell }^{(n)}\cup {\mathcal{F}}_{\ell }^{(n)}|-H\left({\tilde{U}}_1\left[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}\right],\dots ,{\tilde{U}}_K\left[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}\right]|{\tilde{Z}}_m^n\right).\end{array}$$

(43)

Following similar reasoning as in Equation (23), for n large enough, we have:

$$\begin{array}{c}|H\left({\tilde{U}}_1\left[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}\right],\dots ,{\tilde{U}}_K\left[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}\right]|{\tilde{Z}}_m^n\right)-H\left(U_1\left[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}\right],\dots ,U_K\left[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}\right]|Z_m^n\right)|\hfill \\ \stackrel{(a)}{\le }\mathbb{V}({\tilde{q}}_{Z_m^n},p_{Z_m^n})log\frac{2^n}{\mathbb{V}({\tilde{q}}_{Z_m^n},p_{Z_m^n})}+{\mathbb{V}}^{†}log\frac{2^{(n+{\sum }_{\ell =1}^K|{\mathcal{I}}_{\ell }^{(n)}\cup {\mathcal{F}}_{\ell }^{(n)}|)}}{{\mathbb{V}}^{†}}\hfill \\ \stackrel{(b)}{\le }(K+2)n{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}-2{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}log{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)},\hfill \end{array}$$

(44)

where $(a)$ holds by defining ${\mathbb{V}}^{†}\triangleq \mathbb{V}({\tilde{q}}_{U_1[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}],\dots ,U_K[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}]Z_m^n},p_{U_1[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}],\dots ,U_K[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}]Z_m^n})$ and [30] (Lemma 2.9) and $(b)$ follows from Lemma 2 by using similar reasoning as in Equation (23) and because the function $x\mapsto xlogx$ is decreasing for $x>0$ small enough. Hence, we obtain:

$$\begin{array}{c}H\left({\tilde{U}}_1\left[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}\right],\dots ,{\tilde{U}}_K\left[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}\right]|{\tilde{Z}}_m^n\right)\hfill \\ \ge H\left(U_1\left[{\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}\right],\dots ,U_K\left[{\mathcal{I}}_K^{(n)}\cup {\mathcal{F}}_K^{(n)}\right]|Z_m^n\right)-((K+2)n{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}-2{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}log{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)})\hfill \\ \stackrel{(a)}{\ge }{\displaystyle {\sum }_{\ell =1}^K}\sum _{j\in {\mathcal{I}}_{\ell }^{(n)}\cup {\mathcal{F}}_{\ell }^{(n)}}H\left(U_{\ell }(j)|U_{\ell }^{1:j-1},V_{\ell -1}^n,Z_m^n\right)-((K+2)n{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}-2{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}log{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)})\hfill \\ \stackrel{(b)}{\ge }{\displaystyle {\sum }_{\ell =1}^K}|{\mathcal{I}}_{\ell }^{(n)}\cup {\mathcal{F}}_{\ell }^{(n)}|\left(1-2{\delta }_n\right)-((K+2)n{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}-2{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}log{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}),\hfill \end{array}$$

(45)

where $(a)$ holds because conditioning does not increase the entropy and because $U_1^n-\cdots -U_{K-1}^n-U_K^n$ forms a Markov chain and the invertibility of $G_n$ and $(b)$ holds because, according to Equations (32) and (33), ${\mathcal{I}}_{\ell }^{(n)}\cup {\mathcal{F}}_{\ell }^{(n)}\subseteq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}$ for all $\ell \in [1,K]$, because by Lemma 1, we have ${\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_M}^{(n)}\subseteq {\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_m}^{(n)}$ for any $m\in [1,M-1]$, and by the definition of the set ${\mathcal{H}}_{V_{\ell }|V_{\ell -1}{Z}_m}^{(n)}$ given in Equation (31).

Finally, by substituting Equation (45) into Equation (43), we obtain:

$$\begin{array}{c}\hfill I(W_1,\dots ,W_K;F_1,\dots ,F_K,{\tilde{Z}}_m^n)\le n{\delta }_n+(K+2)n{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}-2{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)}log{\delta }_{\mathrm{ld}-\mathrm{nls}}^{(n)},\end{array}$$

(46)

Hence, if $K\ll n$, the polar code satisfies the secrecy condition in Equation (5), and the proof is concluded.

6. Polar Construction and Performance Evaluation

In this section, we discuss further how to construct the polar codes for the DBC-NLD-LS and DBC-LD-NLS proposed in Section 4 and Section 5, respectively. Moreover, we evaluate the reliability and the secrecy performance of both polar coding schemes according to different parameters involved in the polar code construction. Although the construction of polar codes has been covered in a large number of references (see, for instance, [21,22,23]), they only focus on polar codes under reliability constraints.

For the DBC-NLD-LS, we consider the Binary Erasure Broadcast Channel (BE-BC), where each individual channel of the DBC is a Binary Erasure Channel (BEC). For this model, we propose a construction of the polar code that is based on the Bhattacharyya parameters instead of the corresponding entropy terms. The reason is that, for the BE-BC, the Bhattacharyya parameters associated with the sets in Equations (7)–(11) can be computed exactly [7] (Proposition 5). Then, we evaluate the reliability and the secrecy performance of the code, and we focus on how different parameters involved in the proposed polar code construction impact its performance.

On the other hand, for the DBC-LD-NLS, we consider the Binary Symmetric Broadcast Channel (BS-BC), where each individual channel is a Binary Symmetric Channel (BSC). From [7] (Proposition 5), we know that the method to compute the exact values of the Bhattacharyya parameters for a BEC provides an upper-bound on the Bhattacharyya parameters of the BSC. Although this method can be useful to construct polar codes under reliability constraints [21,22,23], it fails when the code must guarantee some secrecy condition based on the information leakage. Indeed, in order to upper-bound the information leakage in Equation (39), according to Equation (45), notice that we need a lower-bound on the entropy terms (or Bhattacharyya parameters). Hence, for this model, we focus more on proposing a new polar code construction that is based directly on the entropy terms associated with the sets in Equations (27)–(31).

Throughout this section, as in [7], we say that a channel or a conditional distribution $p_{Y|X}(y|x)$ with $x\in \mathcal{X}\triangleq \{0,1\}$ and $y\in \mathcal{Y}\triangleq \{0,\dots ,|\mathcal{Y}|-1\}$ is symmetric if the columns of the probability transition matrix ${\mathbf{P}}_{Y|X}\triangleq \left[\begin{array}{c}\hfill \begin{array}{ccc}{p}_{Y|X}(0|0)& \cdots & p_{Y|X}(|\mathcal{Y}|-1|0)\\ p_{Y|X}(0|1)& \cdots & p_{Y|X}(|\mathcal{Y}|-1|1)\end{array}\end{array}\right]$ can be grouped into sub-matrices such that for each sub-matrix, each row is a permutation of each other row and each column is a permutation of each other column. Therefore, the individual channels of both BE-BC and the BS-BC are symmetric.

Due to the symmetry of BE-BC, we will see that the distribution induced by the encoding described in Section 4.2 for the DBC-NLD-LS will approach exactly the optimum distribution of the original DMS used in the polar code construction. Consequently, the performance of the polar code will depend only on the parameters involved in the construction. On the other hand, despite the symmetry of the BS-BC, due to its superposition-based structure, the encoding described in Section 5.2 for the DBC-NLD-LS only approaches the target distribution asymptotically. Hence, this encoding will impact the reliability and secrecy performance of the polar code when we consider a finite blocklength.

6.1. DBC-NLD-LS

For this model, we consider BE-BC with two legitimate receivers ($K=2$) and two eavesdroppers ($M=2$). Therefore, each individual channel is a BEC with $\mathcal{X}\triangleq \{0,1\}$ and ${\mathcal{Y}}_k={\mathcal{Z}}_m\triangleq \{0,1,E\}$, E being the erasure symbol and $k,m\in \{1,2\}$. The individual channels are defined simply by their erasure probability, which is denoted by ${ϵ}_{Y_k}$ for the corresponding legitimate receiver k ($\mathbb{P}[Y_k=E]={ϵ}_{Y_k}$) and ${ϵ}_{Z_m}$ for the eavesdropper m ($\mathbb{P}[Z_m=E]={ϵ}_{Z_m}$). Due to the degradedness condition of the broadcast channel given in Equation (1), we have ${ϵ}_{Y_2}<{ϵ}_{Y_1}<{ϵ}_{Z_2}<{ϵ}_{Z_1}$. By properly applying [19] (Proposition 3.2), it is easy to shown that the secrecy-capacity achieving distribution $p_X^{\star }$ for this model is the uniform, i.e., $p_X^{\star }(x)=\frac{1}{2}\forall x\in \{0,1\}$. For the simulations, we consider a BE-BC such that ${ϵ}_{Y_2}=0.01$, ${ϵ}_{Y_1}=0.04$, ${ϵ}_{Z_2}=0.2$ and ${ϵ}_{Z_1}=0.35$. According to Corollary 1 and since $p_X^{\star }(x)$ is uniform, we obtain that the capacity without considering rate sharing is $R_1^{\star }=0.15$ and $R_2^{\star }=0.16$.

6.1.1. Practical Polar Code Construction

Given the blocklength n and the distribution $p_{X{Y}_2{Y}_1{Z}_2{Z}_1}^{\star }=p_X^{\star }{p}_{Y_2{Y}_1{Z}_2{Z}_1|X}$, the goal of the polar code construction is to obtain the partition of the universal set $[n]$ defined in Equations (12)–(16) and graphically represented in Figure 3. Hence, we need to define first the required sets of Equations (7)–(11), which means having to compute the entropy terms ${\{H(U(j)|U^{1:j-1})\}}_{j=1}^n$, ${\{H(U(j)|U^{1:j-1},Y_1^n)\}}_{j=1}^n$ and ${\{H(U(j)|U^{1:j-1},Z_m^n)\}}_{j=1}^n\forall m\in \{1,2\}$ associated with the polar transform $U^n=X^n{G}_n$. Alternatively, as mentioned in Section 3, we can define the sets in Equations (7)–(11) from the corresponding Bhattacharyya parameters. Indeed, since each individual channel is a BEC, by [7] (Proposition 5), we can compute with very low complexity the exact values of ${\{Z(U(j)|U^{1:j-1})\}}_{j=1}^n$, ${\{Z(U(j)|U^{1:j-1},Y_1^n)\}}_{j=1}^n$ and ${\{Z(U(j)|U^{1:j-1},Z_m^n)\}}_{j=1}^n\forall m\in \{1,2\}$. To do so, we use the recursive algorithm [22] (PCC-0) adapted to the BEC, which, for instance, will obtain ${\{Z(U(j)|U^{1:j-1},Y_1^n)\}}_{j=1}^n$ from the initial value $Z(X|Y_1)={ϵ}_{Y_1}$ (the entire code in MATLAB used for this section is provided as Supplementary Material—see Endnote [32]). Regarding ${\{Z(U(j)|U^{1:j-1})\}}_{j=1}^n$, since $p_X^{\star }$ is uniform, it is clear that $Z(U(j)|U^{1:j-1})=H(U(j)|U^{1:j-1})=1$ for all $j\in [n]$, which means ${\mathcal{H}}_X^{(n)}=[n]$. Consequently, the set ${\mathcal{T}}^{(n)}=\varnothing$, and according to Equation (17), neither random, nor deterministic SC encoding will be needed.

In order to compare the performance of the polar coding scheme according to different parameters and to provide more flexibility in the design, instead of using only ${\delta }_n$ to define the sets in Equations (7)–(11), we introduce the pair $({\delta }_n^{(\mathrm{r})},{\delta }_n^{(\mathrm{s})})$, where ${\delta }_n^{(\mathrm{r})}\triangleq 2^{-n^{{\beta }^{(\mathrm{r})}}}$ and ${\delta }_n^{(\mathrm{s})}\triangleq 2^{-n^{{\beta }^{(\mathrm{s})}}}$ for some ${\beta }^{(\mathrm{r})},{\beta }^{(\mathrm{s})}\in (0,\frac{1}{2})$. Let $R_1^{\prime }\in [0,R_1^{\star }]$ and $R_2^{\prime }\in [0,R_2^{\star }]$ denote the target rates that the polar coding scheme must approach. We obtain the partition defined in Equations (12)–(16) as follows. First, we define ${\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\triangleq \left\{j\in [n]:H\left(U(j)\left|U^{1:j-1},Y_1^n\right.\right)\le 1-{\delta }_n^{(\mathrm{s})}\right\}$, where one can notice that we have used ${\delta }_n^{(\mathrm{s})}$. Then, we choose ${\mathcal{I}}_2^{(n)}$ by taking the $n{R}_2^{\prime }$ indices $j\in {\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$ that correspond to the highest Bhattacharyya parameters ${\{Z(U(j)|U^{1:j-1},Z_2^n)\}}_{j=1}^n$ for Eavesdropper 2. Second, we choose ${\mathcal{I}}_1^{(n)}$ by taking the $n{R}_1^{\prime }$ indices $j\in {\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\backslash {\mathcal{I}}_2^{(n)}$ that correspond to the highest Bhattacharyya parameters ${\{Z(U(j)|U^{1:j-1},Z_1^n)\}}_{j=1}^n$ for Eavesdropper 1. Finally, we obtain ${\mathcal{C}}^{(n)}={\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\backslash \left({\mathcal{I}}_1^{(n)}\cup {\mathcal{I}}_2^{(n)}\right)$ and ${\mathcal{F}}^{(n)}={\mathcal{H}}_{X|Y_1}^{(n)}$. Furthermore, in order to evaluate the reliability performance of the code, we define ${\mathcal{L}}_{X|Y_1}^{(n)}\triangleq \left\{j\in [n]:H\left(U(j)\left|U^{1:j-1},Y_1^n\right.\right)\le {\delta }_n^{(\mathrm{r})}\right\}$, where one can notice that we have used ${\delta }_n^{(\mathrm{r})}$. Since the additional secret sequence $\mathsf{\Phi }$ corresponds to those entries belonging to ${\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$, its length will depend on $({\delta }_n^{(\mathrm{r})},{\delta }_n^{(\mathrm{s})})$. According to the polar code construction proposed in this section, notice that ${\delta }_n^{(\mathrm{s})}$ must be small enough to guarantee that $|{\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}|\ge R_1^{\prime }+R_2^{\prime }$.

6.1.2. Performance Evaluation

First, notice that the encoding of Section 4.2 will induce a distribution ${\tilde{q}}_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}=p_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}^{\star }$ because ${\mathcal{T}}^{(n)}=\varnothing$ (we do not use SC encoding), and the encoder will store uniformly-distributed sequences into the entries $U(j)$ that satisfy $H(U(j)|U^{1:j-1})=1$ for all $j\in {\mathcal{H}}_X^{(n)}=[n]$. Hence, $\mathbb{V}({\tilde{q}}_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n},p_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}^{\star })=0$, and the performance will only depend on the code construction.

To evaluate the reliability performance, we obtain an upper-bound $P_{\mathrm{b}}^{\mathrm{ub}(1)}$ on the average bit error probability at the legitimate Receiver 1. Since $\mathbb{V}({\tilde{q}}_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n},p_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}^{\star })=0$, from Equation (21), we have:

$$\begin{array}{c}\hfill P_{\mathrm{b}}^{\mathrm{ub}(1)}\triangleq \frac{1}{|{\mathcal{L}}_{X|Y_1}^{(n)}|}{\displaystyle \sum _{j\in {\mathcal{L}}_{X|Y_1}^{(n)}}}Z\left(U(j)|U^{1:j-1},Y_1^n\right).\end{array}$$

(47)

Due to the degradedness condition of the BE-BC and, consequently, by Lemma 1, the average bit error probability at the legitimate Receiver 2 will be always less than the one at the legitimate Receiver 1. Since the legitimate receivers must estimate the entries belonging to ${\mathcal{L}}_{X|Y_1}^{(n)}$ regardless of ${\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$ and the target rates $(R_1^{\prime },R_2^{\prime })$, the reliability performance only depends on the pair $(n,{\delta }_n^{(\mathrm{r})})$.

In order to evaluate the secrecy performance, we compute an upper-bound on the information leakage $I(W_1,W_2;F,{\tilde{Z}}_1^n)$ and an upper-bound on the information leakage $I(W_2;F,{\tilde{Z}}_2^n)$. Since $\mathbb{V}({\tilde{q}}_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n},p_{X^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}^{\star })=0$, from Equations (22) and (24), we obtain:

$$\begin{array}{cc}\hfill I^{\mathrm{ub}}(W_1,W_2;F,{\tilde{Z}}_1^n)& \triangleq {\displaystyle \sum _{i=1}^2}|{\mathcal{I}}_i^{(n)}|+|{\mathcal{F}}^{(n)}|-{\displaystyle \sum _{j\in {\mathcal{I}}_1^{(n)}\cup {\mathcal{I}}_2^{(n)}\cup {\mathcal{F}}^{(n)}}}Z{\left(U(j)|U^{1:j-1},Z_1^n\right)}^2,\hfill \end{array}$$

(48)

$$\begin{array}{cc}\hfill I^{\mathrm{ub}}(W_2;F,{\tilde{Z}}_2^n)& \triangleq |{\mathcal{I}}_2^{(n)}|+|{\mathcal{F}}^{(n)}|-{\displaystyle \sum _{j\in {\mathcal{I}}_2^{(n)}\cup {\mathcal{F}}^{(n)}}}Z{\left(U(j)|U^{1:j-1},Z_2^n\right)}^2,\hfill \end{array}$$

(49)

where we have used [27] (Proposition 2) to express the information leakage in terms of the Bhattacharyya parameters because $H(U(j)|U^{1:j-1},Z_m^n)\ge Z{(U(j)|U^{1:j-1},Z_m^n)}^2$. According to the proposed polar code construction, the secrecy performance will depend on $(n,{\delta }_n^{(\mathrm{s})})$ and the rates $(R_1^{\prime },R_2^{\prime })$, but not on ${\delta }_n^{(\mathrm{r})}$.

Additionally, we evaluate the rate of the additional sequence $\mathsf{\Phi }$ simply by computing:

$$\begin{array}{c}\hfill \frac{1}{n}|\mathsf{\Phi }|=\frac{1}{n}|{\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}|,\end{array}$$

(50)

which will depend on the triple $(n,{\delta }_n^{(\mathrm{r})},{\delta }_n^{(\mathrm{s})})$, but not on $(R_1^{\prime },R_2^{\prime })$.

Let ${\rho }_{\mathrm{R}}$ be the normalized target rate in which the polar coding scheme operates, that is ${\rho }_{\mathrm{R}}\triangleq \frac{R_1^{\prime }}{R_1^{\star }}=\frac{R_2^{\prime }}{R_2^{\star }}$. In Figure 6A,B, we evaluate the upper-bounds on the information leakage defined in Equations (48) and (49), respectively, as a function of the blocklength n for different values of ${\rho }_{\mathrm{R}}$. To do so, we set ${\beta }^{(\mathrm{r})}=0.16$ and ${\beta }^{(\mathrm{s})}=0.30$, which defines a particular pair $({\delta }_n^{(\mathrm{r})},{\delta }_n^{(\mathrm{s})})$ for each value of n (recall that ${\delta }_n^{(\mathrm{r})}$ does not impact on the secrecy performance of the polar code). As we proved in Section 4.5.4, for large enough n, the secrecy performance improves as n increases. Moreover, to achieve a particular secrecy performance level, the polar code will require a larger blocklength n as the rates approach the capacity. This happens because, given $(n,{\delta }_n^{(\mathrm{s})})$ and, consequently, ${\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$, the parameter ${\rho }_{\mathrm{R}}$ only determines the amount of indices that will belong to ${\mathcal{I}}_1^{(n)}\cup {\mathcal{I}}_2^{(n)}\subseteq {\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$. Since, by construction, we take those indices corresponding to the highest Bhattacharyya parameters associated with the eavesdroppers, taking more elements always increases the corresponding leakage. For rates approaching the capacity and small values of n, notice that we obtain a secrecy performance that is getting worse as n increases (for instance, for ${\rho }_{\mathrm{R}}=0.94$, we obtain that the information leakage is increasing from $n=2^9$ to $n=2^{12}$). This behavior is mainly explained because the elements of $U^n$ have not been polarized enough for small values of n. Consequently, for a given value of ${\beta }^{(\mathrm{s})}$, not all the Bhattacharyya parameters associated with the eavesdroppers corresponding to the sets ${\mathcal{I}}_1^{(n)}$ and ${\mathcal{I}}_2^{(n)}$ are sufficiently close to one. Since, for a given ${\rho }_{\mathrm{R}}$, the cardinality of ${\mathcal{I}}_1^{(n)}$ and ${\mathcal{I}}_2^{(n)}$ increases with n, then the information leakage can increase with n when n is not large enough. Moreover, since operating at lower rates means taking a fewer number of indices in ${\mathcal{I}}_1^{(n)}$ and ${\mathcal{I}}_2^{(n)}$, but taking those that are closest to one, this behavior appears only for large values of ${\rho }_{\mathrm{R}}$.

The impact of ${\delta }_n^{(\mathrm{s})}$ on the secrecy performance is graphically represented in Figure 7A,B, where the former plots the upper-bound defined in Equation (48) and the latter the upper-bound in Equation (49) as a function of the blocklength n for different values of ${\beta }^{(\mathrm{s})}$. Now, we set ${\beta }^{(\mathrm{r})}=0.16$ and ${\rho }_{\mathrm{R}}=0.90$. As can be seen in Figure 7, the secrecy performance improves as the value of ${\beta }^{(\mathrm{s})}$ increases (or equivalently, as ${\delta }_n^{(\mathrm{s})}$ decreases). This behavior is as expected because notice that ${\delta }_n^{(\mathrm{s})}$ defines the value of the highest Bhattacharyya parameter $Z\left(U(j)|U^{1:j-1},Y_1^n\right)$ that will belong to ${\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$, that is the set containing the possible candidates for ${\mathcal{I}}_1^{(n)}\cup {\mathcal{I}}_2^{(n)}$. Since the polar construction chooses the indices that will belong to ${\mathcal{I}}_1^{(n)}$ and ${\mathcal{I}}_2^{(n)}$ by taking the ones corresponding to the highest Bhattacharyya parameters associated with the eavesdroppers and since, by Lemma 1, $Z\left(U(j)|U^{1:j-1},Z_1^n\right)\ge Z\left(U(j)|U^{1:j-1},Z_2^n\right)\ge Z\left(U(j)|U^{1:j-1},Y_1^n\right)$ for any $j\in [n]$, the sums in Equations (48) and (49) over the indices $j\in {\mathcal{I}}_1^{(n)}\cup {\mathcal{I}}_2^{(n)}$ will be larger as ${\beta }^{(\mathrm{s})}$ increases (as ${\delta }_n^{(\mathrm{s})}$ decreases), while their cardinality remains the same for a given ${\rho }_{\mathrm{R}}$. Furthermore, notice that ${\delta }_n^{(\mathrm{s})}$ also defines ${\mathcal{F}}^{(n)}={\mathcal{H}}_{X|Y_1}^{(n)}=\{j\in [n]:Z\left(U(j)|U^{1:j-1},Y_1^n\right)>1-{\delta }_n^{(\mathrm{s})}\}$. Thus, the larger is the value of ${\beta }^{(\mathrm{s})}$ (the lower is ${\delta }_n^{(\mathrm{s})}$), the smaller is the cardinality of ${\mathcal{F}}^{(n)}$ and the higher are the Bhattacharyya parameters associated with the eavesdroppers that belong to this set.

Figure 8 plots the upper-bound on the average bit error probability at the legitimate Receiver 1 defined in Equation (47) as a function of the blocklength n for different values of ${\beta }^{(\mathrm{r})}$ (which defines a particular ${\delta }_n^{(\mathrm{r})}$ for each n). For this figure, we set ${\beta }^{(\mathrm{s})}=0.30$ and ${\rho }_{\mathrm{R}}=0.90$. As can be seen in Figure 8, the higher is the value of ${\beta }^{(\mathrm{r})}$ (the smaller is the value of ${\delta }_n^{(\mathrm{r})}$), the better is the reliability performance of the polar code. This is because ${\delta }_n^{(\mathrm{r})}$ defines the higher Bhattacharyya parameter associated with the legitimate Receiver 1 whose corresponding index will belong to the set ${\mathcal{L}}_{X|Y_1}^{(n)}$ (recall that this set contains the indices of those entries that the legitimate receivers have to estimate). Hence, it is clear that the upper-bound in Equation (47) is decreasing as ${\delta }_n^{(\mathrm{r})}$ decreases (as ${\beta }^{(\mathrm{r})}$ increases). Moreover, as we have proven in Section 4.5.3, we can see that the reliability performance is always improving as n increases.

Finally, how the values of the pair $({\beta }^{(\mathrm{r})},{\beta }^{(\mathrm{s})})$, or equivalently, the values of $({\delta }_n^{(\mathrm{r})},{\delta }_n^{(\mathrm{s})})$, impact the rate of the additional secret sequence $\mathsf{\Phi }$ given in Equation (50) is represented graphically in Figure 9. In Figure 9A, we set ${\rho }_{\mathrm{R}}=0.90$ and ${\beta }^{(\mathrm{r})}=0.16$, and we represent the rate of $\mathsf{\Phi }$ as a function of the blocklength n for different values of ${\beta }^{(\mathrm{s})}$. Otherwise, in Figure 9B, we evaluate the rate of $\mathsf{\Phi }$ as a function of n for different values of ${\beta }^{(\mathrm{r})}$ when ${\rho }_{\mathrm{R}}=0.90$ and ${\beta }^{(\mathrm{s})}=0.30$. As mentioned in Section 4.2, this rate tends to be negligible for sufficiently large n. Moreover, according to the polar code construction proposed previously, for a fixed n, the cardinality of the set ${\left({\mathcal{H}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{X|Y_1}^{(n)}\right)}^{\mathrm{C}}$ will be higher for larger values of $({\beta }^{(\mathrm{r})},{\beta }^{(\mathrm{s})})$, or equivalently, smaller values of $({\delta }_n^{(\mathrm{r})},{\delta }_n^{(\mathrm{s})})$. Therefore, as can be seen in Figure 9, it is clear that higher values of $({\beta }^{(\mathrm{r})},{\beta }^{(\mathrm{s})})$ mean also higher rate of the additional secret sequence.

In conclusion, Figure 6, Figure 7, Figure 8 and Figure 9 show that, for a particular value of the blocklength n, there is a trade-off between the reliability or the secrecy performance of the polar code and the length of the additional secret sequence $\mathsf{\Phi }$, which can be controlled by the value of ${\beta }^{(\mathrm{r})}$ or ${\beta }^{(\mathrm{s})}$, respectively, in the polar code construction. Moreover, for sufficiently large n, the performance of the polar coding scheme always is improving as n increases. Indeed, these figures show that we can transmit at rates very close to the capacity, providing good reliability and secrecy performance levels.

6.2. DBC-LD-NLS

For this model, we consider BS-BC with two legitimate receivers ($K=2$) and two eavesdroppers ($M=2$). Hence, each individual channel is a BSC where $\mathcal{X}={\mathcal{Y}}_k={\mathcal{Z}}_m=\{0,1\}$, and $k,m\in \{1,2\}$. The individual channels are defined simply by their crossover probability, which is denoted by ${\alpha }_{Y_k}$ for the corresponding legitimate receiver k ($\mathbb{P}[Y_k=0|X=1]=\mathbb{P}[Y_k=1|X=0]={\alpha }_{Y_k}$) and ${\alpha }_{Z_m}$ for the corresponding eavesdropper m ($\mathbb{P}[Z_m=0|X=1]=\mathbb{P}[Z_m=0|X=1]={\alpha }_{Z_m}$). Due to the degradedness condition of the broadcast channel given in Equation (1), we have ${\alpha }_{Y_2}<{\alpha }_{Y_1}<{\alpha }_{Z_2}<{\alpha }_{Z_1}$. Due to the symmetry of the channel, it is easy to prove by using similar reasoning as in [33] (Ex. 15.6.5) and by properly applying [19] (Proposition 3.2) that the secrecy-capacity achieving distribution $p_{VX}^{\star }$ satisfies $p_V^{\star }(v)=p_X^{\star }(x)=\frac{1}{2}\forall v,x\in \{0,1\}$, and consequently, $p_{X|V}^{\star }$ is symmetric. Thus, the distribution $p_{X|V}^{\star }$ can be characterized simply by the crossover probability ${\alpha }_{X|V}\triangleq p_{X|V}^{\star }(0|1)=p_{X|V}^{\star }(1|0)$, where ${\alpha }_{X|V}\in [0,\frac{1}{2}]$. Indeed, the overall rate in Proposition 2 is maximized when ${\alpha }_{X|V}=\frac{1}{2}$, which implies that $R_1=0$. Then, by taking ${\alpha }_{X|V}<\frac{1}{2}$, we can transfer part of the rate associated with the message $W_2$ to the rate $R_1$, $R_2=0$ and $R_1$ being maximum if ${\alpha }_{X|V}=0$. For the simulations, we consider a BS-BC with ${\alpha }_{Y_2}=0.01$, ${\alpha }_{Y_1}=0.04$, ${\alpha }_{Z_2}=0.2$ and ${\alpha }_{Z_1}=0.35$. We set ${\alpha }_{X|V}=0.1084$, which corresponds to the distribution that maximizes $ln(R_1)+ln(R_2)$ for this particular channel (proportional fair allocation). Thus, according to Corollary 2, the maximum achievable rates are $R_1^{\star }=0.2507$ and $R_2^{\star }=0.3254$.

6.2.1. Practical Polar Code Construction

Given the blocklength n and the distribution $p_{VX{Y}_2{Y}_1{Z}_2{Z}_1}^{\star }=p_{VX}^{\star }{p}_{Y_2{Y}_1{Z}_2{Z}_1|X}$, the goal of the polar code construction is to obtain the partition of the universal set $[n]$ defined in Equations (32)–(35) and graphically represented in Figure 5. Hence, we need to define first the sets in Equations (27)–(31), which means having to compute the entropy terms ${\{H(U_1(j)|U_1^{1:j-1})\}}_{j=1}^n$, ${\{H(U_1(j)|U_1^{1:j-1},Y_1^n)\}}_{j=1}^n$ and ${\{H(U_1(j)|U_1^{1:j-1},Z_2^n)\}}_{j=1}^n$ associated with the polar transform $U_1^n=V^n{G}_n$ for the first superposition layer and ${\{H(U_2(j)|U_2^{1:j-1},V^n)\}}_{j=1}^n$, ${\{H(U_2(j)|U_2^{1:j-1},V^n,Y_2^n)\}}_{j=1}^n$ and ${\{H(U_2(j)|U_2^{1:j-1},V^n,Z_2^n)\}}_{j=1}^n$ associated with the polar transform $U_2^n=X^n{G}_n$ for the second layer. In the following, we propose an adaptation of the Monte Carlo method [22] (PCC-1), which is based on the butterfly algorithm described in [7] for SC decoding, to directly estimate these entropy terms.

Monte-Carlo method to estimate the entropy terms. First, consider the entropy terms associated with to the first layer. As for the previous model, since $p_V^{\star }(v)=\frac{1}{2}$, we have $H(U_1(j)|U_1^{1:j-1})=1$ for all $j\in [n]$. In order to compute ${\{H(U_1(j)|U_1^{1:j-1},Y_k^n)\}}_{j=1}^n$ and ${\{H(U_1(j)|U_1^{1:j-1},Z_m^n)\}}_{j=1}^n$ for some $k,m\in \{1,2\}$, we run the Monte Carlo simulation as follows. First, due to the symmetry of the channel and the symmetry of $p_{X|V}^{\star }$, as in [22] (PCC-1), we can set $v^n=u_1^n=0^n$ at each iteration. For the realization $\tau \in [1,N_{\tau }]$, $N_{\tau }$ being the number of realizations, we randomly generate $y_k^{n(\tau )}$ and $z_m^{n(\tau )}$ from $p_{Y_k^n|V^n}^{\star }$ and $p_{Z_m^n|V^n}^{\star }$, respectively (by abuse of notation, we use $(\tau )$ in any sequence $a^{n(\tau )}$ to emphasize that it is generated at the iteration $\tau \in [1,N_{\tau }]$). Next, we obtain the log-likelihood ratios ${\{L_{Y_k|V}^{(\tau )}(j)\}}_{j=1}^n$ and ${\{L_{Z_m|V}^{(\tau )}(j)\}}_{j=1}^n$ by using the algorithm [22] (PCC-1). For instance, consider ${\{L_{Y_k|V}^{(\tau )}(j)\}}_{j=1}^n$. From the initial values ${\{p_{Y_k|V}^{\star }(y_k^{(\tau )}(j)|0)/p_{Y_k|V}^{\star }(y_k^{(\tau )}(j)|1)\}}_{j=1}^n$, the algorithm recursively computes:

$$\begin{array}{c}\hfill L_{Y_k|V}^{(\tau )}(j)\triangleq ln\frac{p_{Y_k^n{U}_1^{1:j-1}|U_1(j)}^{\star }(y_k^{n(\tau )},0^{j-1}|0)}{p_{Y_k^n{U}_1^{1:j-1}|U_1(j)}^{\star }(y_k^{n(\tau )},0^{j-1}|1)}\stackrel{(a)}{=}\frac{p_{U_1(j)|U_1^{1:j-1}{Y}_k^n}^{\star }(0|0^{j-1},y_k^{n(\tau )})}{1-p_{U_1(j)|U_1^{1:j-1}{Y}_k^n}^{\star }(0|0^{j-1},y_k^{n(\tau )})},\end{array}$$

for all $j\in [n]$, where $(a)$ follows from the fact that $p_{U_1(j)}^{\star }(0)=p_{U_1(j)}^{\star }(1)=\frac{1}{2}$ because $H(U_1(j)|U_1^{1:j-1})=1$ for all $j\in [n]$. Hence, we can obtain $p_{U_1(j)|U_1^{1:j-1}{Y}_k^n}^{\star }(0|0^{j-1},y_k^{n(\tau )})$ from $L_{Y_k|V}^{(\tau )}(j)$, and since:

$$\begin{array}{c}\hfill H(U_1(j)|U_1^{1:j-1},Y_k^n)={\mathbb{E}}_{U_1^{1:j-1}{Y}_k^n}\left[h_2\left(p_{U_1(j)|U_1^{1:j-1}{Y}_k^n}^{\star }(0|u_1^{1:j-1},y_k^n)\right)\right],\end{array}$$

after $N_{\tau }$ realizations, we can estimate $H(U_1(j)|U_1^{1:j-1},Y_k^n)$ by computing the empirical mean, that is,

$$\begin{array}{c}\hfill H(U_1(j)|U_1^{1:j-1},Y_k^n)\approx \frac{1}{N_{\mathrm{r}}}{\displaystyle \sum _{\tau =1}^{N_{\tau }}}{h}_2\left(p_{U_1(j)|U_1^{1:j-1}{Y}_k^n}^{\star }(0|0^{j-1},y_k^{n(\tau )})\right).\end{array}$$

Now, consider the Monte Carlo method to estimate ${\{H(U_2(j)|U_2^{1:j-1},V^n)\}}_{j=1}^n$, ${\{H(U_2(j)|U_2^{1:j-1},V^n,Y_k^n)\}}_{j=1}^n$ and ${\{H(U_2(j)|U_2^{1:j-1},V^n,Z_m^n)\}}_{j=1}^n$ for any $k,m\in \{1,2\}$ associated with the second layer. To obtain ${\{H(U_2(j)|U_2^{1:j-1},V^n)\}}_{j=1}^n$, we can see X and V as the input and output random variables, respectively, of a symmetric channel with distribution $p_{V|X}^{\star }$. Now, although $p_X^{\star }$ is uniform and, consequently, $H(U_2(j)|U_2^{1:j-1})=1$ for all $j\in [n]$, notice that ${\mathcal{H}}_{X|V}^{(n)}\ne [n]$ and ${\mathcal{T}}_1^{(n)}\ne \varnothing$ because ${\mathcal{H}}_{X|V}^{(n)}$ and its complementary set depend on $p_{X|V}^{\star }$. On the other hand, to obtain ${\{H(U_2(j)|U_2^{1:j-1},V^n,Y_k^n)\}}_{j=1}^n$ or ${\{H(U_2(j)|U_2^{1:j-1},V^n,Z_m^n)\}}_{j=1}^n$, we can see $(V,Y_k)$ or $(V,Z_m)$ as the output of a symmetric channel with distribution $p_{V{Y}_k|X}^{\star }$ or $p_{V{Z}_m|X}^{\star }$, respectively, where notice that $p_{V{Y}_k|X}^{\star }=p_{V|X}^{\star }{p}_{Y_k|X}^{\star }$ and $p_{V{Z}_m|X}^{\star }=p_{V|X}^{\star }{p}_{Z_m|X}^{\star }$ because $V-X-Y_k-Z_m$ forms a Markov chain. Hence, due to the symmetry of the previous distributions, we can set $x^n=u_2^n=0^n$ at each iteration. Then, for the realization $\tau \in [1,N_{\tau }]$, we draw $v^{n(\tau )}$, $y_k^{n(\tau )}$ and $z_m^{n(\tau )}$ from the distributions $p_{V^n|X^n}^{\star }$, $p_{Y_k^n|X^n}$ and $p_{Z_m^n|X^n}$, respectively. Next, we obtain the log-likelihood ratios ${\{L_{V|X}^{(\tau )}(j)\}}_{j=1}^n$, ${\{L_{V{Y}_k|X}^{(\tau )}(j)\}}_{j=1}^n$ and ${\{L_{V{Z}_m|X}^{(\tau )}(j)\}}_{j=1}^n$ by using [22] (PCC-1). Since $H(U_2(j)|U_2^{1:j-1})=1$ for all $j\in [n]$, we have $p_{U_2(j)}^{\star }(u)=\frac{1}{2}$ for all $u\in \{0,1\}$, and we can compute $p_{U_2(j)|U_2^{1:j-1}{V}^n}^{\star }(0|0^{j-1},v^{n(\tau )})$, $p_{U_2(j)|U_2^{1:j-1}{V}^n{Y}_k^n}^{\star }(0|0^{j-1},v^{n(\tau )},y_k^{n(\tau )})$ and $p_{U_2(j)|U_2^{1:j-1}{V}^n{Z}_m^n}^{\star }(0|0^{j-1},v^{n(\tau )},z_m^{n(\tau )})$ from the corresponding log-likelihood ratios. Finally, after $N_{\tau }$ realizations, we can estimate the corresponding entropy terms by computing the empirical mean.

Partition of the universal set$[\mathbf{n}]$. In order to provide more flexibility on the design, now we introduce $({\delta }_n^{(1,\mathrm{r})},{\delta }_n^{(1,\mathrm{s})})$ for the first layer, where ${\delta }_n^{(1,\mathrm{r})}\triangleq 2^{-n^{{\beta }^{(1,\mathrm{r})}}}$ and ${\delta }_n^{(1,\mathrm{s})}\triangleq 2^{-n^{{\beta }^{(1,\mathrm{s})}}}$ for some ${\beta }^{(1,\mathrm{r})},{\beta }^{(1,\mathrm{s})}\in (0,\frac{1}{2})$. For the second layer, we introduce $({\delta }_n^{(2,\mathrm{r})},{\delta }_n^{(2,\mathrm{s})})$ and $({\delta }_n^{(2,\mathrm{L})},{\delta }_n^{(2,\mathrm{H})})$, where ${\delta }_n^{(2,\mathrm{r})}\triangleq 2^{-n^{{\beta }^{(2,\mathrm{r})}}}$, ${\delta }_n^{(2,\mathrm{s})}\triangleq 2^{-n^{{\beta }^{(2,\mathrm{s})}}}$, ${\delta }_n^{(2,\mathrm{L})}\triangleq 2^{-n^{{\beta }^{(2,\mathrm{L})}}}$ and ${\delta }_n^{(2,\mathrm{H})}\triangleq 2^{-n^{{\beta }^{(2,\mathrm{H})}}}$ for some ${\beta }^{(2,\mathrm{r})},{\beta }^{(2,\mathrm{s})},{\beta }^{(2,\mathrm{L})},{\beta }^{(2,\mathrm{H})}\in (0,\frac{1}{2})$.

Consider the partition of $[n]$ for the first layer ($\ell =1$ in Equations (32)–(35)). As mentioned previously, since $p_V^{\star }(v)=\frac{1}{2}$, we have ${\mathcal{H}}_V^{(n)}=[n]$ and ${\mathcal{T}}_1^{(n)}=\varnothing$. Let $R_1^{\prime }\in [0,R_1^{\star }]$ denote the target rate corresponding to the message $W_1$ that the polar coding scheme must approach. We obtain the partition in Equations (32)–(35) as follows. First, we define ${({\mathcal{H}}_{V|Y_1}^{(n)})}^{\mathrm{C}}\triangleq \{j\in [n]:H(U_1(j)|U_1^{1:j-1},Y_1^n)\le 1-{\delta }_n^{(1,\mathrm{s})}\}$. Then, we choose ${\mathcal{I}}_1^{(n)}$ by taking the $n{R}_1^{\prime }$ indices $j\in {({\mathcal{H}}_{V|Y_1}^{(n)})}^{\mathrm{C}}$ that correspond to the highest entropy terms ${\{H(U_1(j)|U_1^{1:j-1},Z_2^n)\}}_{j=1}^n$ associated with Eavesdropper 2. Notice that ${\delta }_n^{(1,\mathrm{s})}$ must guarantee $|{({\mathcal{H}}_{V|Y_1}^{(n)})}^{\mathrm{C}}|\le R_1^{\prime }$. Finally, we obtain ${\mathcal{C}}_1^{(n)}={({\mathcal{H}}_{V|Y_1}^{(n)})}^{\mathrm{C}}\backslash {\mathcal{I}}_1^{(n)}$ and ${\mathcal{F}}_1^{(n)}={\mathcal{H}}_{V|Y_1}^{(n)}$. Furthermore, in order to evaluate the reliability performance, we define ${\mathcal{L}}_{V|Y_1}^{(n)}\triangleq \{j\in [n]:H(U_1(j)|U_1^{1:j-1},Y_1^n)\le {\delta }_n^{(1,\mathrm{r})}\}$.

Consider the partition of $[n]$ for the second layer ($\ell =2$ in Equations (32)–(35)). Since ${\mathcal{H}}_{X|V}^{(n)}\ne [n]$ and ${\mathcal{T}}_1^{(n)}\ne \varnothing$, we define ${\mathcal{H}}_{X|V}^{(n)}\triangleq \{j\in [n]:H(U_2(j)|U_2^{1:j-1},V^n)\ge 1-{\delta }_n^{(2,\mathrm{H})}\}$ and ${\mathcal{L}}_{X|V}^{(n)}\triangleq \{j\in [n]:H(U_2(j)|U_2^{1:j-1},V^n)\le {\delta }_n^{(2,\mathrm{L})}\}$, where we have used ${\delta }_n^{(2,\mathrm{H})}$ and ${\delta }_n^{(2,\mathrm{L})}$, respectively. Let $R_2^{\prime }\in [0,R_2^{\star }]$ denote the target rate corresponding to $W_2$. We define ${({\mathcal{H}}_{X|V{Y}_2}^{(n)})}^{\mathrm{C}}\triangleq \{j\in {\mathcal{H}}_{X|V}^{(n)}:H(U_2(j)|U_2^{1:j-1},V^n,Y_2^n)\le 1-{\delta }_n^{(2,\mathrm{s})}\}$. Then, we choose ${\mathcal{I}}_2^{(n)}$ by taking the $n{R}_2^{\prime }$ indices $j\in {({\mathcal{H}}_{X|V{Y}_2}^{(n)})}^{\mathrm{C}}$ that correspond to the highest entropy terms ${\{H(U_2(j)|U_2^{1:j-1},V^n,Z_2^n)\}}_{j=1}^n$ associated with Eavesdropper 2. Thus, notice that ${\delta }_n^{(2,\mathrm{H})}$ and ${\delta }_n^{(2,\mathrm{s})}$ must guarantee $|{\mathcal{H}}_{X|V}^{(n)}|\ge |{({\mathcal{H}}_{X|V{Y}_2}^{(n)})}^{\mathrm{C}}|\ge R_2^{\prime }$. Then, we obtain ${\mathcal{C}}_2^{(n)}={({\mathcal{H}}_{X|V{Y}_2}^{(n)})}^{\mathrm{C}}\backslash {\mathcal{I}}_2^{(n)}$ and ${\mathcal{F}}_2^{(n)}={\mathcal{H}}_{X|V{Y}_2}^{(n)}$. Finally, in order to evaluate the reliability performance, we define ${\mathcal{L}}_{X|V{Y}_2}^{(n)}\triangleq \{j\in [n]:H(U_2(j)|U_2^{1:j-1},V^n,Y_2^n)\le {\delta }_n^{(2,\mathrm{r})}\}$.

6.2.2. Performance Evaluation

First, notice that the encoding at the first layer induces a distribution ${\tilde{q}}_{V^n}=p_{V^n}$. For the second layer, the entries $U[{\mathcal{H}}_{X|V}^{(n)}]$ of the original DMS only are almost independent of $V^n$ because $H(U_2(j)|U_2^{1:j-1},V^n)\le 1-{\delta }_n^{(2,\mathrm{s})}$ for $j\in {\mathcal{H}}_{X|V}^{(n)}$. Nevertheless, the encoding will construct ${\tilde{U}}_2[{\mathcal{H}}_{X|V}^{(n)}]$ by storing uniformly-distributed sequences that are totally independent of $V^n$. On the other hand, since ${\mathcal{L}}_{X|V}^{(n)}\subseteq {\mathcal{T}}_2^{(n)}\ne \varnothing$, the encoder will use the deterministic SC encoding in Equation (37) to construct ${\tilde{U}}_2[{\mathcal{L}}_{X|V}^{(n)}]$. Therefore, according to Lemma 3 and Remark 6, we will have $\mathbb{V}({\tilde{q}}_{V^n{X}^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n},p_{V^n{X}^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}^{\star })\ne 0$ for finite n. Since, as seen in Section 5.5, this total variation distance impacts the performance, we obtain first an upper-bound $d_{\mathrm{TV}}^{\mathrm{ub}}$ on $\mathbb{V}({\tilde{q}}_{V^n{X}^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n},p_{V^n{X}^n{Y}_2^n{Y}_1^n{Z}_2^n{Z}_1^n}^{\star })$, which is defined as:

$$\begin{array}{c}\hfill d_{\mathrm{TV}}^{\mathrm{ub}}\triangleq d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{L})}+d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})},\end{array}$$

where $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{L})}$ will measure the impact of using the deterministic SC encoding in Equation (37) for the entries ${\tilde{U}}_2\left[{\mathcal{L}}_{X|V}^{(n)}\right]$, and $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$ is the contribution on the total variation distance of storing uniformly-distributed random sequences into ${\tilde{U}}_2\left[{\mathcal{H}}_{X|V}^{(n)}\right]$ that are totally independent of $V^n$.

Consider $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{L})}$, which corresponds to the analytic bound found in Lemma A2. For the simulations, we can use the Monte Carlo method to directly estimate Equation (A4) by computing the empirical mean,

$$\begin{array}{c}\hfill d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{L})}\triangleq \frac{1}{N_{{\tau }^{\prime }}}{\displaystyle \sum _{{\tau }^{\prime }=1}^{N_{{\tau }^{\prime }}}}\left[{\displaystyle \sum _{j\in {\mathcal{L}}_{X|V}^{(n)}}}\left(1-p_{U_2(j)|U_2^{1:j-1}{V}^n}^{\star }\left(u_2^{\ast }(j)|{\check{u}}_2^{1:j-1({\tau }^{\prime })},{\check{v}}^{n({\tau }^{\prime })}\right)\right)\right],\end{array}$$

(51)

where $({\check{v}}^{n({\tau }^{\prime })},{\check{u}}_2^{n({\tau }^{\prime })})$ must be drawn at each iteration ${\tau }^{\prime }\in [1,N_{{\tau }^{\prime }}]$ according to Equation (A2), ${\mathcal{L}}_{X|V}^{(n)}$ has been obtained previously in the polar code construction and, according to Equation (A4), $u_2^{\ast }(j)\triangleq {arg\; max}_{u\in \{0,1\}}{p}_{U_2(j)|U_2^{1:j-1}{V}^n}^{\star }(u|{\check{u}}_2^{1:j-1({\tau }^{\prime })},{\check{v}}^{n({\tau }^{\prime })})$. Due to the symmetry of $p_{V|X}^{\star }$, the probabilities $p_{U_2(j)|U_2^{1:j-1}{V}^n}^{\star }$ can be obtained with low complexity using the butterfly algorithm described in [7].

Consider now $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$, which corresponds to the analytic bound found in Lemma A1. We can compute exactly the Kullback-Leibler divergence as in Equation (A3) by using the corresponding entropy terms obtained in the polar code construction. Thus, by applying Pinsker’s inequality, we have:

$$\begin{array}{c}\hfill d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}\triangleq {\left(2ln2{\displaystyle \sum _{j\in {\mathcal{H}}_{X|V}^{(n)}}}\left(1-H\left(U_2(j)|U_2^{1:j-1},V^n\right)\right)\right)}^{1/2}.\end{array}$$

(52)

According to the polar code construction, $|{\mathcal{L}}_{X|V}^{(n)}|$ and $|{\mathcal{H}}_{X|V}^{(n)}|$ will depend only on the values of ${\delta }_n^{(2,\mathrm{L})}$ and ${\delta }_n^{(2,\mathrm{H})}$, respectively, for a particular n. Hence, the value of $d_{\mathrm{TV}}^{\mathrm{ub}}$ can be controlled by adjusting $({\beta }^{(2,\mathrm{L})},{\beta }^{(2,\mathrm{H})})$. It is clear that higher values of $({\beta }^{(2,\mathrm{L})},{\beta }^{(2,\mathrm{H})})$ mean lower cardinalities of the sets ${\mathcal{L}}_{X|V}^{(n)}$ and ${\mathcal{H}}_{X|V}^{(n)}$ and, consequently, lower $d_{\mathrm{TV}}^{\mathrm{ub}}$. However, $|{({\mathcal{H}}_{X|V}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{X|V}^{(n)})}^{\mathrm{C}}|$ increases with $({\beta }^{(2,\mathrm{L})},{\beta }^{(2,\mathrm{H})})$, and the encoder in Equation (36) requires more randomness to form ${\tilde{U}}_2[{({\mathcal{H}}_{X|V}^{(n)})}^{\mathrm{C}}\cap {({\mathcal{L}}_{X|V}^{(n)})}^{\mathrm{C}}]$.

To evaluate the reliability performance, we obtain the upper-bounds $P_{\mathrm{b}}^{\mathrm{ub}(1)}$ and $P_{\mathrm{b}}^{\mathrm{ub}(2)}$ on the average bit error probability at Receivers 1 and 2, respectively. From Equations (41) and (42) and by applying [27] (Proposition 2) to upper-bound the Bhattacharyya parameters from the entropy terms, we have:

$$\begin{array}{cc}\hfill P_{\mathrm{b}}^{\mathrm{ub}(1)}& \triangleq d_{\mathrm{TV}}^{\mathrm{ub}}+\frac{1}{|{\mathcal{L}}_{V|Y_1}^{(n)}|}{\displaystyle \sum _{j\in {\mathcal{L}}_{V|Y_1}^{(n)}}}\sqrt{H\left(U_1(j)|U_1^{1:j-1},Y_1^n\right)},\hfill \end{array}$$

(53)

$$\begin{array}{cc}\hfill P_{\mathrm{b}}^{\mathrm{ub}(2)}& \triangleq 2d_{\mathrm{TV}}^{\mathrm{ub}}+\frac{2}{|{\mathcal{L}}_{V|Y_1}^{(n)}|}{\displaystyle \sum _{j\in {\mathcal{L}}_{V|Y_1}^{(n)}}}\sqrt{H\left(U_1(j)|U_1^{1:j-1},Y_2^n\right)}+\frac{1}{|{\mathcal{L}}_{X|V{Y}_2}^{(n)}|}{\displaystyle \sum _{j\in {\mathcal{L}}_{X|V{Y}_2}^{(n)}}}\sqrt{H\left(U_2(j)|U_2^{1:j-1},V^n,Y_2^n\right)}.\hfill \end{array}$$

(54)

To evaluate the secrecy performance, we compute an upper-bound $I^{\mathrm{ub}}(W_1,W_2;F_1,F_2,{\tilde{Z}}_2^n)$ on the information leakage $I(W_1,W_2;F_1,F_2,{\tilde{Z}}_2^n)$ for Eavesdropper 2. From Equation (45) we obtain:

$$\begin{array}{cc}\hfill I^{\mathrm{ub}}(W_1,W_2;F_1,F_2,{\tilde{Z}}_2^n)& \triangleq 4n{d}_{\mathrm{TV}}^{\mathrm{ub}}-2d_{\mathrm{TV}}^{\mathrm{ub}}log{d}_{\mathrm{TV}}^{\mathrm{ub}}+{\displaystyle \sum _{\ell =1}^2}|{\mathcal{I}}_{\ell }^{(n)}\cup {\mathcal{F}}_{\ell }^{(n)}|\hfill \\ & -{\displaystyle \sum _{j\in {\mathcal{I}}_1^{(n)}\cup {\mathcal{F}}_1^{(n)}}}H\left(U_1(j)|U_1^{1:j-1},Z_2^n\right)-{\displaystyle \sum _{j\in {\mathcal{I}}_2^{(n)}\cup {\mathcal{F}}_2^{(n)}}}H\left(U_2(j)|U_2^{1:j-1},V^n,Z_2^n\right),\hfill \end{array}$$

(55)

Due to the degradedness condition of BS-BC and, consequently, by Lemma 1, the information leakage at Eavesdropper 1 will be always less than the one at Eavesdropper 2.

Finally, we evaluate the overall rate of the additional sequences $\{{\mathsf{\Phi }}_1,{\mathsf{\Phi }}_2\}$ by computing:

$$\begin{array}{c}\hfill \frac{1}{n}\left(|{\mathsf{\Phi }}_1|+|{\mathsf{\Phi }}_2|\right)=\frac{1}{n}\left(|{\left({\mathcal{H}}_{V|Y_1}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{V|Y_1}^{(n)}\right)}^{\mathrm{C}}|+|{\left({\mathcal{H}}_{X|V{Y}_2}^{(n)}\right)}^{\mathrm{C}}\cap {\left({\mathcal{L}}_{X|V{Y}_2}^{(n)}\right)}^{\mathrm{C}}|\right).\end{array}$$

(56)

The performance of the polar coding scheme is graphically shown in Figure 10. As for the previous model, let ${\rho }_{\mathrm{R}}$ be the normalized target rate in which the polar coding scheme operates, that is ${\rho }_{\mathrm{R}}\triangleq \frac{R_1^{\prime }}{R_1^{\star }}=\frac{R_2^{\prime }}{R_2^{\star }}$. In Figure 10A, we evaluate the upper-bound $I_0^{\mathrm{ub}}(W_1,W_2;F_1,F_2,Z_2^n)$, which corresponds to the upper-bound on the information leakage defined in Equation (55) when we consider $d_{\mathrm{TV}}^{\mathrm{ub}}=0$, as a function of the blocklength n for different values of ${\rho }_{\mathrm{R}}$. For this plot, we set ${\beta }^{(1,\mathrm{s})}=0.30$ and ${\beta }^{(2,\mathrm{s})}=0.36$. Notice that $({\beta }^{(1,\mathrm{r})},{\beta }^{(2,\mathrm{r})})$ and $({\beta }^{(2,\mathrm{L})},{\beta }^{(2,\mathrm{H})})$ if we set $d_{\mathrm{TV}}^{\mathrm{ub}}=0$ will not impact the information leakage. As we have proven in Section 5.5.4, the secrecy performance is improving as n increases. Moreover, to satisfy a particular secrecy performance level, the polar code will need higher values of n as the target rates approach the capacity.

In Figure 10B, we evaluate the upper-bounds $P_{\mathrm{b},0}^{\mathrm{ub}(1)}$ and $P_{\mathrm{b},0}^{\mathrm{ub}(2)}$, which correspond to the bounds on the average bit error probability at the legitimate Receivers 1 and 2, respectively, when we set $d_{\mathrm{TV}}^{\mathrm{ub}}=0$, as a function of the blocklength n. For this plot, we set ${\beta }^{(1,\mathrm{r})}={\beta }^{(2,\mathrm{r})}=0.24$ and notice that the reliability performance will not depend on the values of $({\beta }^{(1,\mathrm{s})},{\beta }^{(2,\mathrm{s})})$ and ${\rho }_{\mathrm{R}}$. If we set $d_{\mathrm{TV}}^{\mathrm{ub}}=0$, then it is clear that it will not depend on $({\beta }^{(2,\mathrm{L})},{\beta }^{(2,\mathrm{H})})$ either. As shown theoretically in Section 5.5.3, the error probability becomes lower as the blocklength n increases.

Figure 10C plots the overall rate of the additional secret sequences computed as in Equation (56) when we set ${\beta }^{(1,\mathrm{r})}={\beta }^{(2,\mathrm{r})}=0.24$, ${\beta }^{(1,\mathrm{s})}=0.30$ and ${\beta }^{(2,\mathrm{s})}=0.36$. As mentioned in Section 5.2, we can see that this rate tends to be negligible for n sufficiently large.

Finally, Figure 10D plots the upper-bounds $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{L})}$ and $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$ defined in Equations (51) and (52), respectively, when we set ${\beta }^{(2,\mathrm{L})}={\beta }^{(2,\mathrm{H})}=0.36$. As we have proven theoretically in Lemma 3, notice that the total variation distance decays with the blocklength n. Precisely, notice that $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{L})}$ is lower than $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$, and therefore, the bound on the total variation distance is practically governed by $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$ ($d_{\mathrm{TV}}^{\mathrm{ub}}\approx d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$). This happens because although we can compute exactly the Kullback–Leibler divergence as in Equation (A3) from the entropy terms estimated in the polar code construction, Pinsker’s inequality to obtain $d_{\mathrm{TV}}^{\mathrm{ub}(\mathrm{H})}$ as in Equation (52) can be too loose for n not sufficiently large. Consider the impact of $d_{\mathrm{TV}}^{\mathrm{ub}}$ on the reliability performance of the code. The average error probability bounds in Equations (53) and (54) are modeled as the sum of two terms, one depending directly on $d_{\mathrm{TV}}^{\mathrm{ub}}$ and the other depending on the polar construction (which has been plotted in Figure 10B). Since $d_{\mathrm{TV}}^{\mathrm{ub}(H)}$ is too loose, what we obtain is that the reliability performance of the code will be governed practically by the bound $d_{\mathrm{TV}}^{\mathrm{ub}}$ for small values of the blocklength n. Now, consider the impact of $d_{\mathrm{TV}}^{\mathrm{ub}}$ on the secrecy performance of the code. The bound on the information leakage in Equation (55) is modeled as the sum of two terms, one also depending only on the polar code construction (which has been plotted in Figure 10A) and the other depending on $d_{\mathrm{TV}}^{\mathrm{ub}}$. However, in this situation, $d_{\mathrm{TV}}^{\mathrm{ub}}$ impacts the information leakage approximately as $n·d_{\mathrm{TV}}^{\mathrm{ub}}$, which means that this term will totally govern the secrecy performance. Recall that this term follows from Equation (44), which bounds the impact of the encoding in Equation (36) on the conditional entropy term of the information leakage as a function of the total variation distance. Hence, we can conclude that this bound, which follows from applying [30] (Lemma 2.9), can be too loose for n not sufficiently large.

7. Conclusions

We have described two polar coding schemes for two different models over the degraded broadcast channel: DBC-NLD-LS and DBC-LD-NLS. For both models, we have proven that the proposed polar coding schemes are asymptotically secrecy-capacity achieving, providing reliability and strong secrecy simultaneously. Then, we have discussed how to construct these polar codes in practice, and we have evaluated their performance for a finite blocklength by means of simulations. Although several polar code constructions methods have been proposed in the literature, this paper, as far as we know, is the first to discuss practical constructions when the polar code must satisfy both reliability and secrecy constraints. In addition, we have evaluated the secrecy performance of the polar code in terms of the strong secrecy performance, which has been possible by obtaining an upper-bound on the corresponding information leakage at the eavesdroppers. Indeed, we have shown that the proposed polar coding schemes can perform well in practice for a finite blocklength.

The criteria we have chosen for designing the polar codes are: to provide reliability and strong secrecy in one block of size n by using only a secret key that is negligible in terms of rate and to minimize the amount of random decisions for the SC encoding. For the first purpose, we have introduced the source of common randomness, and we have avoided the use of the chaining construction given in [9] (which is possible due to the degraded nature of the broadcast channel); for the second one, we have adapted the deterministic SC encoding given in [20]. These two types of randomness have different implications on the practical design: while the common randomness is uniformly distributed and can be provided by the communication system, the randomness for SC encoding is not and must be drawn by the encoder. In communication scenarios requiring several transmissions of size n, we have shown that one realization of the common randomness can be reused without worsening the performance.

Despite the good performance of the polar coding schemes, some issues still persist. How to avoid the transmissions of the additional secret sequences is a problem that remains open. Despite the length of the required secret key being asymptotically negligible in terms of rate, these additional transmissions can be problematic in practical scenarios. As pointed out in Remark 4, one can adopt the chaining construction in [9] to further reduce the length of these sequences, but this requires the transmission to take place over several blocks of size n and a very large memory capacity at the transmitter or receiver side. Furthermore, despite the rate of the amount of randomness required for SC encoding being negligible, how to replace the random decisions entirely by deterministic ones is a problem that still remains unsolved. Another problem that remains open is how to avoid the use of the common randomness, which allows keyless secret communication over a single block of size n (keyless in the sense that the rate of the required secret key is negligible). Finally, to design polar codes based on the proposed performance evaluation, it seems necessary to find tighter upper-bounds on the total variation distance between the distribution induced by the encoder and the original distribution used in the code construction, particularly for the term that models the impact of storing uniformly-distributed sequences. Also, for the secrecy performance, it would be interesting to find a tighter upper-bound to evaluate the impact of the total variation distance on the information leakage.

Lastly, it is worth mentioning that having to know the statistics of the eavesdropper channels for the polar code construction may seem problematic. Nevertheless, for the polar code construction, one can consider virtual eavesdroppers with some target channel qualities. For DBC-LD-NLS, we can design a polar code according to the statistics of this virtual eavesdropper, and due to the degradedness condition of the channel, this code will perform well if the real eavesdroppers have worse channel quality (worst-case design). On the other hand, for the DBC-NLD-LS, one can simply consider different levels of secrecy depending on different target channel qualities. Depending on the channel quality of the real eavesdropper with respect to the virtual ones considered for the design, the polar coding scheme will provide a particular secrecy performance level.