1

Strong Secrecy on a Class of Degraded
Broadcast Channels Using Polar Codes
Jaume del Olmo and Javier Rodrı́guez Fonollosa
Universitat Politècnica de Catalunya (UPC), Barcelona, Spain

arXiv:1607.07815v3 [cs.IT] 25 Aug 2017

Emails: jaume.delolmo@tsc.upc.edu, javier.fonollosa@upc.edu
Abstract
Different polar coding schemes are proposed for the memoryless degraded broadcast channel under
different reliability and secrecy requirements: layered decoding and/or layered secrecy. In this setting,
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. The implementation of the proposed
polar coding schemes is discussed and their performance is evaluated by simulations for the symmetric
degraded broadcast channel.
Index Terms
Polar codes, physical layer security, degraded broadcast channels, layered decoding, layered secrecy.

I. I NTRODUCTION
Information theoretic security over noisy channels was introduced by Wyner in [1], which
characterized the secrecy-capacity of the degraded wiretap channel. Later, Csiszár and Kö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 mutual information I(W ; Z n )
between the random message W and the observations at the eavesdropper Z n (information
This work is supported by the “Ministerio de Economı́a y Competitividad” of the Spanish Government and ERDF funds
(TEC2013-41315-R, TEC2015-69648-REDC, TEC2016-75067-C4-2-R), and the Catalan Government (2014 SGR 60 AGAUR).

August 28, 2017

DRAFT

2

leakage), n being the blocklength. Based on this measure, the most common secrecy conditions
required to be satisfied by the coding schemes are the weak secrecy condition, which requires
limn→∞ n1 I(W ; Z n ) = 0, and the strong secrecy condition, requiring limn→∞ 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 Layered Decoding and Non-Layered Secrecy
(DBC-LD-NLS), and b) with Non-Layered Decoding and Layered Secrecy (DBC-NLD-LS). 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 secrecy-capacity region of these models was first characterized in [4]–[7]. 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 [8] to achieve the capacity of binaryinput, symmetric, point-to-point channels under Successive Cancellation (SC) decoding. Polar
codes for the binary symmetric degraded wiretap channel were introduced in [9] and [10], and
provide secrecy-capacity achieving polar codes under the weak and the strong secrecy condition,
respectively. Recently, polar coding has been extended to the general wiretap channel in [11]–
[14]. Furthermore, [13] and [14] generalize their results providing polar coding schemes for the
broadcast channel with confidential messages and [12] 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 (see, for example, [12]–[19]), practical polar codes
for the two models on which this paper is focused are, as far as we know, not analyzed yet.
As mentioned in [4], these settings captures practical scenarios in wireless systems, in which

August 28, 2017

DRAFT

3

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 provide two secrecycapacity achieving polar coding schemes for these models under the strong secrecy condition, but
also to discuss their practical implementation aspects and evaluate their reliability and secrecy
performance by means of simulations.
A. Relation to prior work
A good overview of the similarities and differences between the polar codes proposed in [11]–
[14] for the general wiretap channel can be found in [14, Fig. 1]. The polar coding schemes
proposed for the two models considered in this paper are based mainly on the one introduced
by [14] because of the following reasons:
•

To provide strong secrecy. Despite both weak and strong secrecy conditions result in the
same secrecy-capacity region, the weak secrecy requirement in practical applications can
result in important system vulnerabilities [20, Sec. 3.3]. Notice in [14, Fig. 1] that the polar
coding scheme presented in [12] provides weak secrecy.

•

To provide polar coding schemes that are implementable in practice. Notice in [14, Fig. 1]
that the coding scheme presented in [11] relies on a construction for which no efficient
code is presently known. Moreover, the polar coding scheme in [13] relies on the existence,
through averaging, of certain deterministic mappings for the encoding/decoding process.

As in [14], our polar coding schemes are totally explicit. However, in order to provide strong
secrecy, the transmitter and the legitimate receivers need to share a secret seed of negligible
size in terms of rate penalty and the joint distribution induced by the encoder must be close in
terms of statistical distance to the original distribution used for the polar code construction. In
this sense, the design of the polar coding schemes proposed in this paper aims to minimize this
secret seed due to practical reasons.
Although [14, Remark 3] highlights the connection between polar code constructions and
random binning proofs that allows polar codes to be applied to different problems in network
information theory, the particularization for the models proposed in this paper is not straightforward. In order to make the polar coding schemes practical, besides minimizing the length of
the secret seed, we avoid the use of the chaining construction since it requires the receivers to
have a huge storage capacity. As pointed out in [14, Sec 3.B], even if the eavesdropper channel

August 28, 2017

DRAFT

4

is degraded, transmitting a sequence to the legitimate receivers is required to reliably decode
the messages and this transmission becomes negligible in terms of rate penalty only if it takes
place over several blocks of size n. Hence, in order to allow polar coding schemes to secretly
transmit information in just one block of size n, we introduce a source of common randomness
that will be available to the legitimate receivers and the eavesdroppers. Despite this common
randomness being available to the eavesdroppers, they will not be able to leak any information
about the messages thanks to the degradedness condition of the channel.
B. Overview of novel contributions
The main contributions of this work are summarized below:
1) Scenario. This paper focuses on two different models of the DBC with arbitrary number of
legitimate receivers and arbitrary number of eavesdroppers for which polar codes have not
yet been proposed. These two models arise very commonly in wireless communications.
2) Existence of the polar coding schemes. We prove the existence for sufficiently large n
of two secrecy-capacity achieving polar coding schemes for each model under the strong
secrecy condition. Despite proofs are based on mathematical arguments that are similar to
the ones used for the proofs in [14], the polar code constructions for the models proposed
in this paper are not straightforward.
3) Practical implementation. We provide polar codes that are implementable in practice. We
discuss further the implementation aspects when channels are symmetric. We focus on
symmetric channels mainly because: 1) these channels arise commonly in communication
applications (e.g., m-PSK constellations under Gaussian channels), 2) the algorithms for
the polar encoding and polar decoding can be implemented with very-low complexity using
the simple well-know algorithms.
4) Performance evaluation. Simulations results are provided in order to evaluate both the
reliability and secrecy performance of the polar coding schemes. As far as we know, it
is the first time that the secrecy performance is evaluated in terms of the strong secrecy
condition by using an estimation of the information leakage, instead of evaluating the
secrecy by using the average probability of error at the eavesdroppers.

August 28, 2017

DRAFT

5

C. Notation
Through this paper, let [n] = {1, . . . , n} for n ∈ Z+ , an denotes a row vector (a(1), . . . , a(n)).

We write a1:j for j ∈ [n] to denote the subvector (a(1), . . . , a(j)). Let A ⊂ [n], then we write

a[A] to denote the sequence {a(j)}j∈A and we use AC to denote the set complement with respect

to the universal set [n], that is, AC = [n] \ A. Moreover, let E denote some probability event,
then, in this case, Ē denotes its complement. We use ln to denote the natural logarithm, whereas
log2 to denote the logarithm base 2. We use the notation f (n) = O(g(n)) if there exist a positive
constant c such that f (n) ≤ cg(n) for sufficiently large n, which means that f (n) does not grow
faster than g(n). Moreover, we use f (n) = o(g(n)) if limn→∞

g(n)
f (n)

= 0, which means that g(n)

grows much slower than f (n). Finally, let X be a random variable taking values in X , we define
P
total variation distance between two distributions, pX and qX , as dTV = x∈X |qX (x) − pX (x)|.
D. Organization
The remaining of this paper is organized as follows. In Sec. II, the two different models
for the DBC are introduced and their secrecy-capacity regions are characterized. In Sec. III,
the fundamentals theorems of polar codes are revisited. Sec. IV and Sec. V describe the polar
coding schemes for the DBC-LD-NLS and DBC-NLD-LS respectively, and their performance is
evaluated when n tends to infinity. In Sec. VI, the implementations aspects of the polar coding
schemes are further discussed for the symmetric DBC. Sec. VII provides simulation results that
analyze the reliability and secrecy performance of the proposed polar coding schemes for finite
blocklength. Finally, the concluding remarks are presented in Sec. VIII.
II. S YSTEM M ODEL AND S ECRECY-C APACITY R EGION
Formally, a degraded broadcast channel with K legitimate receivers and M eavesdroppers is
characterized by the probability transition function pYK ...Y1 ZM ...Z1 |X , where X ∈ X denotes the
channel input, Yk ∈ Yk denotes the channel output corresponding to the legitimate receiver k
(k = 1, . . . , K), and Zm ∈ Zm denotes the channel output corresponding to the eavesdropper
m (m = 1, . . . , M ). The broadcast channel is assumed to gradually degrade in such a way that
each legitimate receiver has better channel than any eavesdropper, that is,
X − YK − · · · − Y1 − ZM − · · · − Z1
August 28, 2017

(1)

DRAFT

6

YKn

W1 , . . . , W K

Encoder

X

n

DBC

Y2n

pYK ...Y1 ZM ...Z1 |X

Y1n

satisfying

n
ZM

Leg. Receiver K

Leg. Receiver 2

W1 , W 2

Leg. Receiver 1

W1

Eavesdropper M

H
H

H

W
W
W
1,
2, . . . ,
K

H
H
H

Eq. (1)
Z1n

W1 , W 2 , . . . , W K

..
.

..
.
Eavesdropper 1

H
H

H

W
W
W
1,
2, . . . ,
K

H
H
H

Fig. 1: DBC-LD-NLS.

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 1).
A. Degraded broadcast channel with layered decoding and non-layered secrecy
In this model (see Fig. 1), the transmitter wishes to send K messages, {W` }K
`=1 , to the K
legitimate receivers. The layered decoding requires the k-th receiver to reliably decode the
messages {W` }k`=1 , and the non-layered secrecy requires all eavesdroppers to be kept ignorant
of all K messages. Consider a (d2nR1 e, . . . , d2nRK e, n) code for the DBC-LD-NLS, where

W` ∈ [d2nR` e] for ` = 1, . . . , K. The reliability condition of this code is measured in terms

of the average probability of error at each legitimate receiver and is given by
h
i
lim Pr (Ŵk , Ŵk−1 , . . . , Ŵ1 ) 6= (Wk , Wk−1 , . . . , W1 ) = 0, for k = 1, . . . , K.
n→∞

(2)

The strong secrecy condition is measured in terms of the information leakage to each eavesdropper and is given by
n
lim I(W1 , . . . , WK ; Zm
) = 0,

n→∞

for m = 1, . . . , M.

(3)

Proposition 1 (Adapted from [4] and [5]). The secrecy-capacity region of the DBC-LD-NLS is
the union of all rate K-tuples (R1 , . . . , RK ) ∈ RK
+ satisfying the following inequalities,
k
X
`=1

August 28, 2017

R` ≤

k
X
`=1

I(V` ; Y` |V`−1 ) − I(Vk , ZM ),

k = 1, . . . , K,

DRAFT

7

where V0 , φ and VK , X, and the union is taken over all distributions pV1 ...VK such that
V1 − V2 − · · · − VK forms a Markov chain.
The complete proof for the case of K legitimate receivers and only one eavesdropper is
provided in [5]. The achievable scheme is based on random coding arguments and exploits the
joint design of superposition coding, stochastic encoding and rate sharing. If there are M noncollaborating eavesdroppers with channels satisfying the degradedness condition of Eq. (1), then,
from the data processing inequality, any achievable scheme ensuring the strong secrecy condition
n
at the eavesdropper with channel output ZM
also ensures this condition at any eavesdropper.

Corollary 1 (Secrecy-capacity region of the DBC-LD-NLS without rate-sharing). The sub-region
of the secrecy-capacity given in Prop. 1 without considering rate-sharing is a K-orthotope
defined by the closure of all K-tuples of rates (R1 , . . . , RK ) ∈ RK
+ satisfying
R` ≤ I(V` ; Y` |V`−1 ) − I(V` ; ZM |V`−1 ),

` = 1, . . . , K,

where V0 , φ and VK , X, for some pV1 ...VK such that V1−V2− · · · − VK forms a Markov chain.
B. Degraded broadcast channel with non-layered decoding and layered secrecy
In this model (see Fig. 2), the transmitter wishes to send M messages, {Wm }M
m=1 , to the
K legitimate receivers. The non-layered decoding requires each receiver to reliably decode
all M messages and the layered secrecy requires the m-th eavesdropper to be kept ignorant
nR1
of messages {W` }M
e, . . . , d2nRM e, n) code for the DBC-NLD-LS, where
`=m . Consider a (d2

Wm ∈ [d2nRm e] for m = 1, . . . , M , the reliability condition for this code is given by
h
i
lim Pr (Ŵ1 , . . . , ŴM ) 6= (W1 , . . . , WM ) = 0, for k = 1, . . . , K,

(4)

n→∞

and the strong secrecy condition by

n
lim I(Wm , Wm+1 , . . . , WM ; Zm
) = 0,

n→∞

for m = 1, . . . , M.

(5)

Proposition 2 (Adapted from [4] and [6]). The secrecy-capacity region of the DBC-NLD-LS is
the union of all M -tuples of rates (R1 , . . . , RM ) ∈ RM
+ satisfying the following inequalities,
M
X

`=m

August 28, 2017

R` ≤ I(X; Y1 ) − I(X; Zm ),

m = 1, . . . , M,

DRAFT

8

YKn

W1 , . . . , W M

Encoder

X

n

DBC

Y1n

pYK ...Y1 ZM ...Z1 |X

n
ZM

..
.

Eq. (1)

Z1n

W1 , W 2 , . . . , W M

Leg. Receiver 1
Eavesdropper M

satisfying
Z2n

W1 , W 2 , . . . , W M

Leg. Receiver K

..
.

H
W
M

H

Eavesdropper 2

H
H

W
W
M , . . . ,
2
H

H

Eavesdropper 1

H
H

H

W
W
W
M , . . . ,
2,
1
H
H

H

Fig. 2: DBC-NLD-LS.

where the union is taken over all distributions pX .
The complete proof for the case of only one legitimate receiver in the context of the fading
wiretap channel is provided in [6], where the information-theoretic achievable scheme is based
on embedded coding, stochastic encoding and rate sharing. If there are K legitimate receivers
satisfying the degradedness condition of Eq. (1), then, from the data processing inequality and
by applying Fano’s inequality, an achievable scheme ensuring the reliability condition at the
receiver with channel output Y1 also ensures the reliability condition at any receiver.
Corollary 2 (Secrecy-capacity region of the DBC-NLD-LS without rate-sharing). The sub-region
of the secrecy-capacity given in Prop. 2 without considering rate-sharing is a K-orthotope
defined by the closure of all K-tuples of rates (R1 , . . . , RM ) ∈ RM
+ satisfying
Rm ≤ I(X; Zm+1 ) − I(X; Zm ),

m = 1, . . . , M − 1,

RM ≤ I(X; Y1 ) − I(X; ZM ),
for some distribution pX .
III. R EVIEW OF POLAR CODES
In this section, for convenience, the fundamentals of polar codes are revisited by considering
its counterpart on source coding [21]. Let (X × Y, pXY ) denote a Discrete Memoryless Source
(DMS), where X ∈ {0, 1}1 and Y ∈ Y. Consider an i.i.d. n-sequence of this DMS, n being any
1

We assume binary polarization. The extension to q-ary alphabets is entirely possible [22], [23].

August 28, 2017

DRAFT

9

power of 2. The polar transform over the sequence X n is defined as
U n , X n Gn ,
where Gn ,

 1 1 ⊗n
1 0

(6)

n
n
is the source polarization matrix [21]. Since Gn = G−1
n , then X , U Gn .

The polarization theorem for source coding with side information [21, Th. 1] states that the
polar transform of Eq. (6) extracts the randomness of X n in the sense that, as n → ∞, the set of
(n)

indices j ∈ [n] can be divided practically into two disjoint sets (polarized sets), namely HX|Y and
(n)

(n)

LX|Y , such that U (j) for j ∈ HX|Y is practically independent of (U 1:j−1 , Y n ) and uniformly

(n)
distributed, i.e., H U (j)|U 1:j−1 , Y n → 1, and U (j) for j ∈ LX|Y is almost determined by

β
(U 1:j−1 , Y n ), i.e., H U (j)|U 1:j−1 , Y n → 0. More formally, let δn , 2−n , where β ∈ (0, 12 ),
the following polarized sets are defined for X n ,



(n)
HX|Y , j ∈ [n] : H U (j) U 1:j−1 , Y n ≥ 1 − δn ,


(n)
LX|Y , j ∈ [n] : H U (j) U 1:j−1 , Y n ≤ δn ,

C 
C
(n)
(n)
(n)
BX|Y , HX|Y
∩ LX|Y ,

(7)
(8)
(9)

(n)

where notice that BX|Y contain those indices that have not been polarized, that is, the corresponding entropies of their elements have values in (δn , 1 − δn ). Then, by [21, Th. 1],
lim

n→∞

1
(n)
HX|Y = H(X|Y ),
n

lim

n→∞

1 (n)
= 1 − H(X|Y ),
L
n X|Y

lim

n→∞

1 (n)
= 0.
B
n X|Y

(10)

(n)

Furthermore, [21, Th. 2] states that given the sequence U [(LX|Y )C ] and Y n , the entire sequence
U n can be reconstructed with error probability in O(nδn ) by using SC decoding.
A discrete memoryless channel (X , pY |X , Y) with some arbitrary pX can be seen as a DMS
(n)

(n)

(n)

(X ×Y, pX pY |X ). Similarly to Eqs. (7)-(9), the polarized sets HX , LX , and BX can be defined

by considering that observations Y n are unavailable or absent. In polar coding for point-to-point
channels, based on these polarized sets and the ones defined in Eqs. (7)-(9), the encoder constructs
first the sequence U n and then applies the polar transform X n = U n Gn , whose distribution must
be close in terms of statistical distance to the original distribution pX . Afterwards, the transmitter
sends X n over the channel, which induces the receiver channel observations Y n . From Y n and
(n)

the knowledge of U [(LX|Y )C ], the receiver can reconstruct the entire sequence U n [21, Th. 2].
To conclude this section, the following lemma (subset property of polar codes) provides a
useful property of the polarized sets for degraded broadcast channels.

August 28, 2017

DRAFT

10

Lemma 1 (Adapted from [15, Lemma 4]). Let (V`−1 , V` , YK , . . . , Y1 , ZM , . . . , Z1 ) be random
variables such that V`−1 − V` − YK − · · · − Y1 − ZM − · · · − Z1 forms a Markov chain, then the
following property of the polarized sets defined for the polar transform U` = V` Gn holds,
(n)

(n)

(n)

LV` |V`−1 ⊆ LV` |V`−1 Z1 ⊆ · · · ⊆ LV` |V`−1 ZM ⊆ LV
(n)

(n)

(n)
` |V`−1 Y1

⊆ · · · ⊆ LV

(n)

(n)
` |V`−1 YK

(n)

,

and,

(n)

HV` |V`−1 YK ⊆ · · · ⊆ HV` |V`−1 Y1 ⊆ HV` |V`−1 ZM ⊆ · · · ⊆ HV` |V`−1 Z1 ⊆ HV` |V`−1 .
Remark 1. According to [15, Lemma 4], the subset property also holds if the random variables
involved are stochastically degraded, not necessarily physically degraded. Therefore, since the
construction of the polar codes proposed in the following sections is based on Lemma 1, the
polar coding schemes are suitable for both physically and stochastically degraded channels.
IV. P OLAR C ODING S CHEME FOR THE DBC-LD-NLS
The polar coding scheme provided in this section is designed to achieve the corner point
of the secrecy-capacity subregion given in Cor. 1. In this model, there are K input random
variables, {V` }K
`=1 (VK , X), each one associated to a different superposition layer. Thus,
consider the DMS that represents the input and output random variables involved in the secrecycapacity region of Cor. 1 with joint distribution pV1 ...VK YK ...Y1 ZM ...Z1 . Consider an i.i.d. n-sequence
of this DMS and define the K polar transforms (U1n , . . . , UKn ) for the input random variables
(V1n , . . . , VKn ), where its joint distribution can be decomposed as
pU1n ...UKn

(un1 , . . . , unK )

,

K Y
n
Y

pU` (j)|U 1:j−1 V n

`=1 j=1

`

`−1


u` (j) u1:j−1
, un`−1 Gn .
`

(11)

The polarization-based encoder is similar to that of [15, Sec. VII] and consists of K encoding
blocks operating sequentially at each superposition layer. The encoding block at the `-th layer
is responsible for the construction of the sequence V`n . Indeed, since the encoding process will
modify the joint distribution of the original DMS, we use tilde above random variables in order
to distinguish the ones after this encoding procedure. Thus, we introduce
(Ṽ1 , . . . , ṼK , ỸK , . . . , Ỹ1 , Z̃M , . . . , Z̃1 ) ∼ qV1 ...VK YK ...Y1 ZM ...Z1 ,
and we define Ũ`n = Ṽ`n Gn , for ` = 1, . . . , K.

August 28, 2017

DRAFT

11

A. Polar code construction
Based on pV1 ...VK YK ...Y1 ZM ...Z1 , the polar code construction is carried out similarly at each
superposition layer.
β

Polar code construction at layer `. Let δn , 2−n , where β ∈ (0, 21 ). For the polar transform

U`n = V`n Gn associated to the `-th layer (` = 1, . . . , K), the following polarized sets are defined,


(n)
n
LV` |V`−1 Y` , j ∈ [n] : H U` (j) U`1:j−1 , V`−1
, Y`n ≤ 1 − δn ,
(12)


(n)
n
≥ 1 − δn ,
(13)
HV` |V`−1 , j ∈ [n] : H U` (j) U`1:j−1 , V`−1


(n)
n
n
≥ 1 − δn ,
(14)
, ZM
HV` |V`−1 ZM , j ∈ [n] : H U` (j) U`1:j−1 , V`−1

where recall that V0 = φ for the first layer. Based on this polarized sets, we define the following
partition of the universal set [n], which is shown graphically in Fig. 3,
(n)

I`

(n)

F`

(n)

C`

(n)

T`

(n)

(n)

, HV` |V`−1 ZM ∩ LV` |V`−1 Y` ,
C

(n)
(n)
, HV` |V`−1 ZM ∩ LV` |V`−1 Y` ,
C

(n)
(n)
, HV` |V`−1 ∩ HV` |V`−1 ZM ,

C
(n)
, HV` |V`−1 .

(15)
(16)
(17)
(18)

Roughly speaking, in order to ensure reliability and strong secrecy, the joint distribution of
(Ũ1 , . . . , ŨK ) after the encoding process must be close in terms of statistical distance to the
(n)

(n)

(n)

original distribution of Eq. (11) induced by the DMS. Therefore, the sets I` , C` , and F` ,
(n)

which contain those indices j ∈ HV` |V`−1 , will be suitable for storing uniformly distributed
random sequences. Then,
•

(n)

I`

contains those indices j of U`n that are good for the legitimate receiver ` because
(n)

j ∈ LV` |V`−1 Y` and, according to [21, Th. 2], the legitimate receiver will be able to reliably
(n)

(n)

infer them from (LV` |V`−1 Y` )C . Moreover, the indices j ∈ I`

are bad for the eavesdropper

(n)

M because j ∈ HV` |V`−1 ZM and its uncertainty about the entries stored into those indices
will be almost maximum. By the subset property (Lemma 1), these indices are also good
(n)

for the legitimate receivers ` + 1 to K and bad for all the eavesdroppers. Therefore, I`

can be suitable for containing secret information intended to legitimate receivers ` to K;
•

(n)

F`

contain those indices that are not good for the legitimate receiver ` and bad for all

the eavesdroppers. Therefore, the `-th legitimate receiver will not be able to reliably infer

August 28, 2017

DRAFT

12

(n)

(n)

HV` |V`−1 ZM

(n)

(n)

HV` |V`−1 Y`

HV` |V`−1 Y`

(n)

(n)

F`

HV` |V`−1 ZM
C

C

(n)

I`

C`

(n)

(n)

T`

(n)

HV` |V`−1

HV` |V`−1

C

Fig. 3: Polar code construction for the DBC-LD-NLS at layer `. The hatched area represents
(n)

(n)

(n)

(n)

those indices j ∈ BV` |V`−1 Y` , which can belong to the sets F` , C` , or T` .

any of the values stored in these bit-channel indices and this set will be used to store the
uniformly distributed sequence provided by a source of common randomness. Despite the
sequence stored in this set is known by the eavesdroppers, they will not be able to leak any
(n)

information about the message stored into I`
•

(n)

C`

(n)

because F`

(n)

⊆ HV` |V`−1 ZM ;

contain those indices that are not bad for the eavesdropper M . This set is unsuitable

for containing secret information and it will be used to store the local randomness required
to confuse the eavesdroppers (stochastic encoding in polar codes).
C
(n)
(n)
The remaining set T` contains those indices j ∈ HV` |V`−1 that are unsuitable for storing
(n)

uniformly distributed random sequences. In Fig. 3, the indices j belonging to BV` |V`−1 Y` =
C
C
(n)
(n)
HV` |V`−1 Yk ∩ LV` |V`−1 Yk , where


(n)
n
, Y`n ≥ 1 − δn ,
HV` |V`−1 Y` , j ∈ [n] : H U` (j) U`1:j−1 , V`−1

are highlighted using hatched areas. According to the polar code construction, they can belong to
(n)

F`

(n)

T`

(n)

(n)

if they also belong to HV` |V`−1 ZM , to C`

(n)

if they also belong to HV` |V`−1 ∩(HV` |V`−1 ZM )C , or to
(n)

(n)

if they also belong to (HV` |V`−1 )C ⊆ (HV` |V`−1 ZM )C . Despite BV` |V`−1 Y` is negligible in terms
(n)

of rate (Eq. (10)), this set is critical because the `-th legitimate receiver need both BV` |V`−1 Y` and
(n)

(n)

HV` |V`−1 Y` in order to reliably infer the entries stored in j ∈ LV` |V`−1 Y` . However, if eavesdroppers
(n)

(n)

know the elements stored into the part of BV` |V`−1 Y` belonging also to (HV` |V`−1 ZM )C , then the
strong secrecy is compromised. Therefore, notice that the entries stored into the indices j ∈
(n)

(n)

(n)

BV` |V`−1 Y` ∩ HV` |V`−1 ZM can be public and are included into the set F` , which will contain
the public source of common randomness. Otherwise, the entries stored into the indices j ∈
(n)

(n)

BV` |V`−1 Y` ∩ (HV` |V`−1 ZM )C cannot be public and the coding scheme must somehow make them
available to the corresponding legitimate receivers keeping them masked from the eavesdroppers.

August 28, 2017

DRAFT

13

B. Polar encoding
In the following, the polar encoding process is described in detail. Recall that the encoder
consists of K encoding blocks operating sequentially at each superposition layer, where the
encoding block corresponding to layer ` aims to construct the sequence ṽ`n = ũn` Gn .
(n)

Encoding at layer `. Let W` and C` be uniformly distributed random vectors of size I`
(n)

and C`

respectively, where W` represents the message intended to receivers ` to K, and C`

the local randomness required at the `-th layer to confuse all eavesdroppers about this message.
(n)

Let F` be a given uniformly distributed random F`

-sequence, which represents a source of

common randomness that is available to all parties. The encoder constructs the sequence ũn`
 (n) 
 (n) 
as follows. First, the encoder stores the realizations of W` , C` and F` into ũ` I` , ũ` C` ,
 (n) 
 (n)
(n)
(n) 
n
= ũn`−1 Gn
and ũ` F` , respectively. Then, given ũ` I` ∪ C` ∪ F`
and the sequence ṽ`−1

provided by the previous encoding block that operates at the (`−1)-th layer, the encoder samples
(n)

the remaining entries ũ` (j), j ∈ T`
qU` (j)|U 1:j−1 V n
`

`−1

where

(n)

(n)

(n)

(T` = BV` |V`−1 ∪ LV` |V`−1 ), from the distribution


(n)
n
p
ũ` (j)|ũ1:j−1
, ṽ`−1
if j ∈ BV` |V`−1 ,

n
`
U` (j)|U`1:j−1 V`−1
1:j−1 n
n
o
ũ` (j)|ũ`
, ṽ`−1 ,
(n)
 1 ũ` (j) = ξ (j) (ũ1:j−1 , ṽ n )
if j ∈ LV` |V`−1 ,
`−1
`
`
(j)

n
ξ` (ũ1:j−1
, ṽ`−1
) , arg max pU` (j)|U 1:j−1 V n
`
u∈V`

`

`−1

n
u|ũ1:j−1
, ṽ`−1
`



(19)

(20)

and pU` (j)|U 1:j−1 V n is the distribution induced by the original DMS (see Eq. (11)). Notice that the
`

`−1

(n)

encoding block samples randomly the entries ũ` (j) such that j ∈ BV` |V`−1 , and uses SC encoding
(n)

to draw deterministically the entries ũ` (j) such that j ∈ LV` |V`−1 . Finally, the `-th encoder block

computes the sequence ṽ`n = ũn` Gn and delivers it to the next encoding block. If ` = K, then

n
ṽK
, x̃n and the K-th block transmits x̃n over the DBC.

Secret messages. Additionally, the encoder outputs the following messages from each layer,
h
i
(n)
(n)
(n) 
s` , ũ` BV` |V`−1 Y` ∩ C` ∪ T`
, ` = 1, . . . , K.
(21)
(n)

(n)

As mentioned previously, the entries ũ` (j) such that j ∈ BV` |V`−1 Y` ∩ (HV` |V`−1 ZM )C (the blue and
gray hatched areas in Fig. 3) are critical because the legitimate receivers ` to K need them in
order to reliably infer the message w` but the strong secrecy is compromised if they are available
to the eavesdroppers. Thus, since they cannot be part of the source of common randomness that

August 28, 2017

DRAFT

14

is available to all parties, the message s` must be additionally transmitted to the legitimate
receivers ` to K keeping it masked from all eavesdroppers. Nevertheless, as will be shown later,
transmitting these secret messages can be accomplished with negligible rate penalty.
C. Polar decoding
K
The realizations of {F` }K
`=1 are known by all parties and the secret messages {s` }`=1 are

assumed to be received by the corresponding legitimate receivers before the decoding process.
Decoding at the k-th legitimate receiver. According to the layered decoding requirement,
the k-th legitimate receiver must decode the messages {W` }k`=1 . Thus, the k-th receiver forms

an estimate, {ûn` }k`=1 , of the sequences {ũn` }k`=1 in a successive manner from ũn1 to ũnk . The
procedure to estimate ũn` , for some ` ≤ k, is as follows. First, given that the secret message s`

and the realization of the sequence F` are available to the k-th receiver, notice that the receiver
C
C
C 
 (n)
(n)
(n)
knows ũ` LV` |V`−1 Y` . Since, by Lemma 1, LV` |V`−1 Yk ⊆ LV` |V`−1 Y` for any k ≥ `, the
k-th legitimate receiver uses SC decoding for source coding with side information to estimate

 (n)
 (n)
C 
n
n
ũ` LV` |V`−1 Y` from ũ` LV` |V`−1 Y` , its channel output observations ỹk and v̂`−1
= Û`−1
Gn
estimated previously. That is

C

(n)
 ũ (j)
if
j
∈
L
,
`
V` |V`−1 Y`
ûn` (j) =

 ψ (j) û1:j−1 , v̂ n , ỹ n if j ∈ L(n)
`−1 k
`
`
V` |V`−1 Y` ,

(22)

where

(j)

ψ`
pU` (j)|U 1:j−1 V n


n
û`1:j−1 , v̂`−1
, ỹkn , arg max pU` (j)|U 1:j−1 V n
u∈V`

`

n
`−1 Yk


n
u|û1:j−1
, v̂`−1
, ỹkn ,
`

(23)

n ...Z n .
being a marginal of the original distribution of the DMS pU1n ...UKn Ykn ...Y1n ZM
1
 (n) 
Finally, the decoder of the legitimate receiver k outputs Ŵ` = Û` I`
for ` = 1, . . . , k.
`

n
`−1 Yk

D. Information leakage
n
Besides the channel output observations Z̃m
, the m-th eavesdropper has access to the com (n) 
mon randomness {F` }K
for any ` = 1, . . . , K. Therefore, the
`=1 , or equivalently, to Ũ` F`

information about all messages leaked to the m-th eavesdropper is

n
I(W1 , . . . , WK ; F1 , . . . , FK , Z̃m
)
 (n) 
 (n)   (n) 
 (n)  n 
= I Ũ1 I1 , . . . , ŨK IK ; Ũ1 F1 , . . . , ŨK FK , Z̃m
.
August 28, 2017

(24)

DRAFT

15

E. Performance of the polar coding scheme
The analysis of the polar coding scheme leads to the following theorem.
Theorem 1. Consider a DBC-LD-NLS with binary input alphabet X ∈ {0, 1}, K arbitrary

output alphabets {Yk }K
k=1 corresponding to the K legitimate receivers, and M arbitrary output
alphabets {Zm }M
m=1 corresponding to the M eavesdroppers such that X − YK − · · · − Y1 − ZM −

· · · − Z1 forms a Markov chain. The polar coding scheme defined in Secs. IV-A, IV-B and IV-C
achieves any rate tuple of the secrecy-capacity subregion defined in Cor. 1 providing reliability
 √ 
and strong secrecy: the average probability of error at each legitimate receiver is O n nδn and
 √ 

β
the information leakage to each eavesdropper is O n2 nδn , where δn , 2−n with β ∈ 0, 12 .
Proof. The proof follows in four steps:

1) Transmission rates: We prove that the polar coding scheme described previously approaches the rate tuple corresponding to the corner point given in Cor. 1. In addition, we show
that the overall rate required to transmit the secret messages defined in Eq. (21) is negligible.
Message rates. The transmission rate R` corresponding to the message W` (` = 1, . . . , K) is
(n)

given by the cardinality I`

, which for n sufficiently large satisfies

1 (n) (a)
1
(n)
(n)
I`
= lim
HV` |V`−1 ZM ∩ LV` |V`−1 Y`
n→∞ n
n→∞ n

(b)
1
1
(n)
(n)
HV` |V`−1 ZM − lim
≥ lim
n − LV` |V`−1 Y`
n→∞ n
n→∞ n

lim R` = lim

n→∞

(c)

= I(V` ; Y` |V`−1 ) − I(V` ; ZM |V`−1 ),
(n)

where (a) follows from the definition of the set I`

(25)

in Eq. (15), (b) follows from applying

standard set operations, and (c) holds by applying the polarization theorem for source coding
with side information [21, Th. 1]. Thus, the polar coding scheme approaches the rate tuple
corresponding to the corner point given in Cor. 1.
Additional secret message rate. The overall rate RS required to make available the additional
secret messages {s` }K
`=1 to the corresponding legitimate receivers satisfies
(n)

(n)

lim RS = BV` |V`−1 Y` ∩ C`

n→∞

(n) 

∪ T`

1 X (n)
BV` |V`−1 Y` = 0,
n→∞ n
`=1
K

≤ lim

August 28, 2017

(26)

DRAFT

16

because K  n. Therefore, transmitting these secret messages can be accomplished with
negligible rate penalty.
(n)

Remark 2. In fact, since the entire set BV` |V`−1 Y` is negligible in terms of rate, the part of this
(n)

(n)

(n)

set BV` |V`−1 Y` ∩ HV` |V`−1 ZM (the red hatched area in Fig. 3) could be included into the set I`
(n)

instead of into F` . In this case, the secret message s` will carry additional part of the message
W` and the polar coding scheme will approach the secrecy-capacity faster with n. Nevertheless,
since requiring an additional transmission by using a shared secret key can be problematic in
practical applications, the design of the polar coding scheme aims to minimize the required
secret information to be additionally transmitted.
Remark 3. The transmitter and the K legitimate receivers must share a secret key but its size
P
(n)
is negligible in terms of rate penalty. The required key-length is K
k=1 BV` |V`−1 Y` = o(n).

2) Distribution of the DMS after the polar encoding: The polar encoder modifies the joint

distribution of the DMS, which impacts on the average error probability and on the information
leaked to the eavesdroppers because the polar code construction is based on the original DMS.
Indeed, the encoder constructs the sequences (Ũ1n , . . . , ŨKn ), whose joint distribution satisfies
qU1n ...UKn (ũn1 , . . . , ũnK )

=

K Y
n
Y

k=1 j=1

qUk (j)|U 1:j−1 V n
k

k−1


ũk (j) ũ1:j−1
, ũnk−1 Gn ,
k

where, according to the encoding process described in Sec. IV-B,

qUk (j)|U 1:j−1 V n ũk (j) ũ1:j−1
, ũnk−1 Gn
k
k
k−1

(n)
1


if j ∈ HVk |Vk−1 ,

 2

(n)
, ũnk−1 Gn if j ∈ BVk |Vk−1 ,
= pUk (j)|U 1:j−1 V n ũk (j) ũ1:j−1
k
k
k−1




(n)
1:j−1
 q̃
, ũnk−1 Gn if j ∈ LVk |Vk−1 ,
Uk (j)|U 1:j−1 V n ũk (j) ũk
k

k−1

q̃Uk (j)|U 1:j−1 V n being the distribution induced by taking the arg max function defined in Eq. (23).
k

k−1

Lemma 2. According to the polar encoding process of Sec. IV-B,
(n)

dTV (qU1n ...UKn , pU1n ...UKn ) ≤ δld-nls ,
where
(n)
δld-nls

August 28, 2017

q p
p
p
K(K + 1)
n 2 4nδn ln 2(n − log2 4nδn ln 2) + δn + 4nδn K ln 2,
,
2
DRAFT

17

which implies,
(n)

for any k, ` = 1, . . . , K,

(n)

for any m = 1, . . . , M,

dTV (qU`n0 ...U`n Ykn , pU`n0 ...U`n Ykn ) ≤ δld-nls
dTV (qZmn , pZmn ) ≤ δld-nls

1 ≤ `0 ≤ `,

n ...Z n induced by the
where pU`n0 ...U`n Ykn and pZmn are marginal distributions of pU1n ...UKn YKn ...Y1n ZM
1

original DMS, and qU`n0 ...U`n Ykn and qZmn are these distributions after the encoding process.
Proof: See App. A setting L = K.
3) Reliability performance: Consider the probability of incorrectly decoding the message W`
at the k-th legitimate receiver, where ` = 1, . . . , k. Let us define an optimal coupling [24,
n U n Y n and pU n U n Y n such that
Prop. 4.7] between qU`−1
` k
`−1 ` k

n U nY n ,
where EU`−1
` k





n U nY n
n U n Y n , pU n U n Y n ),
Pr EU`−1
= dTV (qU`−1
` k
` k
`−1 ` k



n
n
Ũ`−1
, Ũ`n , Ỹkn =
6 U`−1
, U`n , Ykn . Additionally, consider the error event
 n
n
6= Ũ`−1
.
EŨ n , Û`−1
`−1

The average probability of incorrectly decoding W` at the k-th receiver can be bounded as
h
i
h
i
Pr Ŵ` 6= W` ≤ Pr Û`n 6= Ũ`n
h
i h
i
n U nY n ∩ E n
n U nY n ∩ E n
≤ Pr Û`n 6= Ũ`n E U`−1
Pr
E
U
Ũ`−1
Ũ`−1
` k
`−1 ` k
i
i h
h
n U nY n ∪ E n
n U nY n ∪ E n
Pr
E
+ Pr Û`n 6= Ũ`n EU`−1
U
Ũ`−1
Ũ`−1
`−1 i k
` k
h
i
i
h
n
n
n
n
n
n
n
n
≤ Pr Û` 6= Ũ` E U`−1 U` Yk ∩ E Ũ n + Pr EU`−1 U` Yk ∪ EŨ n
`−1
`−1
h
i
h
i
(a)
(n)
n U nY n ∩ E n
≤ Pr Û`n 6= Ũ`n E U`−1
n
Ũ`−1 + δld-nls + Pr EŨ`−1
` k
h
i
(b)
(n)
n
n
≤ nδn + δld-nls + Pr Û`−1
6= Ũ`−1
,

where (a) follows from applying the union bound, and by the optimal coupling and Lemma 2,

and (b) holds by the average error probability of SC decoding for source coding with side
information [21, Th. 2] since, according to the polar coding scheme, the k-th receiver knows

August 28, 2017

DRAFT

18

 (n)
C 
Ũ` LV` |V`−1 Yk
for any ` = 1, . . . , k. Therefore, by induction, the average error probability at

the k-th receiver can be upper-bounded as
k
h
i X
h
i
Pr (Ŵk , Ŵk−1 , . . . , Ŵ1 ) 6= (Wk , Wk−1 , . . . , W1 ) ≤
Pr Û`n 6= Ũ`n
`=1

≤
(n)


k(k + 1) 
(n)
nδn + δld-nls ,
2

and, by the definition of δld-nls given in Lemma 2,
h

i
 p
β
−n
Pr (Ŵk , Ŵk−1 , . . . , Ŵ1 ) 6= (Wk , Wk−1 , . . . , W1 ) = O n n2
,
for any k = 1, . . . , K.

4) Secrecy performance: According to Sec. IV-D, the information about all messages leaked
to the m-th eavesdropper is
n
I(W1 , . . . , WK ; F1 , . . . , FK , Z̃m
)
 (n)  n 
 (n)   (n) 
 (n) 
= I Ũ1 I1 , . . . , ŨK IK ; Ũ1 F1 , . . . , ŨK FK , Z̃m
 (n) 
 (n) 
 (n) 
 (n)  n 
= H Ũ1 I1 , . . . , ŨK IK
+ H Ũ1 F1 , . . . , ŨK FK Z̃m
 (n) 
 (n)   (n) 
 (n)  n 
− H Ũ1 I1 , . . . , ŨK IK , Ũ1 F1 , . . . , ŨK FK Z̃m

≤

K 
X
`=1

(n)

I`

(n)

+ F`



 (n)
 (n)

(n) 
(n) 
n
− H Ũ1 I1 ∪ F1 , . . . , ŨK IK ∪ FK Z̃m
.

The last term of Eq. (27) can be lower-bounded as
 (n)
 (n)

(n) 
(n) 
n
H Ũ1 I1 ∪ F1 , . . . , ŨK IK ∪ FK Z̃m


 (n)
 (n)
(n) 
(n) 
n
n
− H Z̃m
= H Ũ1 I1 ∪ F1 , . . . , ŨK IK ∪ FK , Z̃m
 (n)
 (n)

(n) 
(n) 
(n)
(n)
n
≥ H U1 I1 ∪ F1 , . . . , UK IK ∪ FK Zm
− 2δld-nls (n − 2 log2 δld-nls ).

(27)

(28)

where the last inequality follows from applying Lemma 8 in App. A to both terms and by
Lemma 3. Moreover, by using the chain rule of entropy,
K
 (n)
 (a) X
 (n)

 (n)
(n) 
(n) 
(n) 
n
n
n
H U1 I1 ∪ F1 , . . . , UK IK ∪ FK Zm ≥
H U` I` ∪ F`
U`−1
, Zm
`=1

(b)

≥
(c)

≥

August 28, 2017

K
X

X

n
n
, Zm
H U` (j) U`1:j−1 , U`−1

`=1 j∈I (n) ∪F (n)
`
`

K 
X
`=1

(n)

I`

(n)

+ F`



(1 − 2δn ) ,



(29)

DRAFT

19

where (a) holds because conditioning does not increase the entropy and by the fact that U1n −
 (n)
(n) 
n
− U ` I` ∪ F `
· · · − U`−1
forms a Markov chain, (b) also follows from the fact that conditioning does not increase the entropy, and (c) holds because, according to the definition of
(n)

the sets I`
(n)

(n)

I` , F `

(n)

and F`

given in Eq. (15) and Eq. (16) respectively, and by Lemma 1, we have

(n)

(n)

⊆ HV` |V`−1 ZM ⊆ HV` |V`−1 Zm for any m = 1, . . . , M − 1, and, therefore, we have

(n)
(n)
n
n
≥ 1 − 2δn for j ∈ I` ∪ F` , which follows from the definition of
, Zm
H U` (j) U`1:j−1 , U`−1
(n)

n
n
.
and V`−1
the set HV` |V`−1 Zm , and the one-to-one relation between U`−1

Finally, by substituting Eq. (29) into Eq. (28), and the resulting expression into Eq. (27),
n
I(W1 , . . . , WK ; F1 , . . . , FK , Z̃m
)

and, by the definition of

(n)
δld-nls

≤ 2δn

K 
X
`=1

(n)

I`

(n)

+ F`



(n)

(n)

+ 2δld-nls (n − 2 log2 δld-nls ),

given in Lemma 2,


 p
n
I(W1 , . . . , WK ; F1 , . . . , FK , Z̃m
) = O n2 n2−nβ .

Hence, the strong secrecy condition given in Eq. (3) is satisfied and this concludes the proof.

V. P OLAR C ODING S CHEME F OR THE DBC-NLD-LS
The polar coding scheme provided in this section is designed to achieve the corner point of
the secrecy-capacity subregion given in Cor. 2. In this model, the encoding process only takes
place over the input channel random variable X. Thus, consider the DMS that represents the
input and output random variables involved in the secrecy-capacity region of Cor. 2 with joint
distribution pXYK ...Y1 ZM ...Z1 . Consider an i.i.d. n-sequence of this source and define the polar
transform U n , X n Gn , where its distribution can be decomposed as
n
 Y

pU n u n ,
pU (j)|U 1:j−1 u(j) u1:j−1 .

(30)

j=1

The polarization-based encoder aims to construct the sequence X n . Since the encoding process
will modify the joint distribution of the original DMS, we introduce (X̃, ỸK , . . . , Ỹ1 , Z̃M , . . . , Z̃1 )
with joint distribution qXYK ...Y1 ZM ...Z1 and we define Ũ n = X̃ n Gn .

August 28, 2017

DRAFT

20

A. Polar code construction
β

Let δn , 2−n , where β ∈ (0, 12 ). Based on pXYK ...Y1 ZM ...Z1 , the following polarized sets are

defined for the polar transform U n = X n Gn ,



(n)
LX|Y1 , j ∈ [n] : H U (j) U 1:j−1 , Y1n ≤ 1 − δn ,


(n)
HX , j ∈ [n] : H U (j) U 1:j−1 ≥ 1 − δn ,


(n)
n
≥ 1 − δn ,
HX|Zm , j ∈ [n] : H U (j) U 1:j−1 , Zm

(31)
(32)
(33)

where m = 1, . . . , M . Based on this polarized sets, we define the following partition of the
universal set [n], which is shown graphically in Fig. 4,
(n)

(n)

(n)

IM , HX|ZM ∩ LX|Y1 ,

C
(n)
(n)
(n)
(n)
Im
, HX|Zm ∩ HX|Zm+1 ∩ LX|Y1
(n) C
(n)
F (n) , HX|ZM ∩ LX|Y1 ,
(n)
(n) C
C (n) , HX ∩ HX|Z1 ,
(n) C
T (n) , HX .

(34)
(m = 1, . . . , M − 1),

(35)
(36)
(37)
(38)

Following similar reasoning as for the polar construction of the DBC-LD-NLS given in Sec. IV-A,
(n)

the sets Im (m = 1, . . . , M ), F (n) and C (n) will be suitable for storing uniformly distributed
(n)

random sequences and the set T (n) will not. In Fig. 3, the indices j belonging to BX|Y1 ,
(n) C
(n) C
LX|Y1 ∩ HX|Y1 , where


(n)
HX|Y1 , j ∈ [n] : H U (j) U 1:j−1 , Y1n ≥ 1 − δn ,

are highlighted using hatched areas. In this model, according to the polar code construction,
(n)

(n)

they can belong to the set F (n) if they also belong to HX|ZM , to Im if they also belong to
(n)

(n)

(n)

HX|Zm ∩ (HX|Zm+1 )C (m = 1, . . . , M − 1), to C (n) if they also belong to HX ∩ (HX|Z1 )C , or
(n)

(n)

to T (n) if they also belong to (HX )C . Notice that the indices j ∈ BX|Y1 ∩ HX|ZM are included
into set F (n) , which will be used to store the uniformly distributed sequence provided by the
(n)

source of common randomness. Since, by Lemma 1, these indices also belong to HX|Zm for any
m = 1, . . . , M − 1, the strong secrecy condition is not compromised. On the other hand, the
(n)

(n)

(n)

indices j ∈ HX ∩ BX|Y1 ∩ (HX|Z1 )C must be included into the set C (n) because they are not
bad for the eavesdropper 1, and this eavesdropper has to be kept ignorant about all messages.

August 28, 2017

DRAFT

21

(n)

(n)

(n)

HX|Z1

(n)

HX|Z2

..
.
(n)

(n)

HX|ZM
F (n)

(n)

HX|Y1

..
. 
C

HX|Z2

HX|ZM
(n)

IM

(n)

···

(n)

I2

(n)

(n)
HX

HX|Y1

I1
C

C (n)

C

HX|Z1

C

T (n)
(n) C

HX

Fig. 4: Polar code construction for the DBC-NLD-LS. The hatched area represents those indices
(n)

j ∈ BX|Y1 , which can belong to the sets F (n) , C (n) , or T (n) .
(n)

(n)

(n)

Finally, since the indices belonging to BX|Y1 ∩HX|Zm ∩(HX|Zm+1 )C , for some m = 1, . . . , M −1,
are not bad for the eavesdropper m + 1, the entries to be stored in these positions cannot be
part of the source of common randomness because it will compromise the strong secrecy at
eavesdroppers m + 1 to M . Nevertheless, since the message Wm is not required to be kept secret
from eavesdroppers m + 1 to M , these indices can be used to store part of this message.
B. Polar encoding
(n)

(n)
M
Let {Wm }M
m=1 and C be uniformly distributed random vectors of size { Im }m=1 and C

respectively, where {Wm }M
m=1 represent the messages intended to all legitimate receivers, and
C the additional local randomness required to confuse the eavesdroppers. Let F be a given
uniformly distributed random F (n) -sequence, which represents a source of common randomness

that is available to all parties. The encoder constructs the sequence ũn as follows. First, the
 (n) 
encoder stores the realizations of Wm into Ũ Im , for m = 1, . . . , M , and stores the realizations






(n) 
of C and F into Ũ C (n) and Ũ F (n) respectively. Then, given ũ ∪M
∪ C (n) ∪ F (n) ,
m=1 Im
the encoder samples the remaining entries ũ(j), j ∈ T (n) , from the distribution

 pU (j)|U 1:j−1 (ũ(j)|ũ1:j−1 ) if j ∈ B (n) ,

X
1:j−1
n
o
qU (j)|U 1:j−1 ũ(j)|ũ
,
(n)
(j)
1:j−1
 1 ũ(j) = ξ (ũ
) if j ∈ L ,
X

where

ξ (j) (ũ1:j−1 ) , arg max pU (j)|U 1:j−1 u|ũ1:j−1
u∈X

August 28, 2017



(39)

DRAFT

22

and pU (j)|U 1:j−1 is the distribution induced by the original DMS (see Eq. (30)). Finally, the encoder
computes the sequence x̃n = ũn Gn and transmits it over the broadcast channel.
Secret message. In addition of the sequence x̃n , the encoder outputs the following message

s , ũ BX|Y1 ∩



−1 (n)
∪ C (n) ∪ T (n) ,
∪M
m=1 I

As mentioned previously, now the entries ũ` (j) such that j ∈ BX|Y1 ∩

(40)

 (n)
−1 (n)
∪C ∪T (n)
∪M
m=1 I

(the green, blue and gray hatched areas in Fig. 3) are critical because all legitimate receivers

need them in order to reliably infer the messages but the strong secrecy is compromised if they
are available to some eavesdroppers. Thus, since they cannot be part of the source of common
randomness that is available to all parties, the message s must be additionally transmitted to all
legitimate receivers keeping it masked from the eavesdroppers.
C. Polar decoding
The realization of F is assumed to be known by all parties. Moreover, the secret message s
is assumed to be received by all legitimate receivers previously to the decoding procedure.
Decoding at the k-th receiver. The k-th legitimate receiver forms an estimate of the sequence
ũn as follows. First, given that s and the realization of F are available to the receiver k, notice
 (n) C 
(n) C
(n) C
that the receiver knows ũ LX|Y1 . Since, by Lemma 1, LX|Yk ⊆ LX|Y1 for any k > 1,

the k-th legitimate receiver uses SC decoding for source coding with side information [21] to
 (n) 
 (n) C 
estimate ũ LX|Y1 from ũ LX|Y1
and its channel output observations ỹk , that is,


C
(n)
 ũ(j)
if
j
∈
L
,
X|Y1
ûn (j) =
(41)
 ψ (j) (û1:j−1 , ỹ n ) if j ∈ L(n) ,
k

X|Y1

where



ψ (j) û1:j−1 , ỹkn , arg max pU (j)|U 1:j−1 Ykn u|û1:j−1 , ỹkn ,

(42)

u∈X

n ...Z n , where pU n is decomposed as in
pU (j)|U 1:j−1 Ykn being a marginal distribution of pU n Ykn ...Y1n ZM
1
 (n) 
Eq. (30). Finally, the decoder outputs Ŵm = Û Im for m = 1, . . . , M .

August 28, 2017

DRAFT

23

D. Information leakage
n
, the m-th eavesdropper has access to the common
Besides the channel output observations Z̃m
 (n) 
. Therefore, the information about messages {Wi }M
randomness F , or equivalently, to Ũ F
i=m

leaked to the m-th eavesdropper is



 n
(n) 
n
I(Wm , . . . , WM ; F, Z̃m
) = I Ũ ∪M
; Ũ F (n) , Z̃m
.
i=m Ii

(43)

E. Performance of the polar coding scheme
The analysis of the polar coding scheme described previously leads to the following theorem.
Theorem 2. Consider an arbitrary DBC-NLD-LS with binary input alphabet X ∈ {0, 1}, K

arbitrary output alphabets {Yk }K
k=1 corresponding to the K legitimate receivers, and M arbitrary

output alphabets {Zm }M
m=1 corresponding to the M eavesdroppers such that X −YK −· · ·−Y1 −
ZM − · · · − Z1 forms a Markov chain. The coding scheme described in Secs. V-A, V-B and V-C

achieves any rate tuple of the secrecy-capacity subregion defined in Cor. 2 providing reliability
 √ 
and strong secrecy: the average probability of error at each legitimate receiver is O n nδn and
 √ 

β
the information leakage to each eavesdropper is O n2 nδn , where δn , 2−n with β ∈ 0, 12 .
Proof. The proof follows in four steps:

1) Transmission rates: We prove that the polar coding scheme described previously approaches the rate tuple corresponding to the corner point given in Cor. 2. In addition, we show
that the rate required to transmit the secret message defined in Eq. (40) is negligible.
Message rates. The transmission rate Rm corresponding to the message Wm is given by the
(n)

cardinality Im , which satisfies


C
1 (n) (a)
1
(n)
(n)
(n)
lim Rm = lim
Im = lim
HX|Zm ∩ HX|Zm+1 ∩ LX|Y1
n→∞
n→∞ n
n→∞ n
1
(n)
(n)
(n)
HX|Zm ∩ LX|Zm+1 ∩ LX|Y1
n→∞ n
1
(c)
(n)
(n)
= lim
HX|Zm ∩ LX|Zm+1
n→∞ n
(b)

≥ lim

(d)

= I(X; Zm+1 ) − I(X; Zm ),

August 28, 2017

for m = 1, . . . , M − 1,

DRAFT

24

(n)

(n)

where (a) follows from the definition of the set Im in Eq. (35), (b) holds because LX|Zm+1 ⊆
C
(n)
(n)
(n)
HX|Zm+1 , (c) holds because LX|Zm+1 ⊆ LX|Y1 and (d) holds by applying [21, Th. 1] and

following the same steps used in obtaining Eq. (25). Similarly, we obtain
1 (n)
IM = I(X; Y1 ) − I(X; ZM ).
n→∞ n

lim RM = lim

n→∞

Additional secret message rate. The rate required to make available the additional secret
message s defined in Eq. (40) to all K receivers satisfies


1
−1 (n)
∪ C (n) ∪ T (n)
BX|Y1 ∩ ∪M
m=1 I
n→∞ n
1 (n)
≤ lim
BX|Y1 = 0.
n→∞ n

lim RS = lim

n→∞

Remark 4. The transmitter and the K legitimate receivers must share a secret key but its size
(n)

is negligible in terms of rate penalty. Specifically, the required key-length is BX|Y1 = o(n).
2) Distribution of the DMS after the polar encoding: The polar encoder constructs the
sequence Ũ n , whose joint distribution satisfies
n
Y

n
qU n (ũ ) =
qU (j)|U 1:j−1 ũ(j) ũ1:j−1 ,
j=1

where


qU (j)|U 1:j−1 ũ(j) ũ1:j−1 =











(n)

1
2

if j ∈ HX ,


(n) C
pU (j)|U 1:j−1 ũ(j) ũ1:j−1 if j ∈ HX ,

(n)
q̃U (j)|U 1:j−1 ũ(j) ũ1:j−1
if j ∈ LX ,

q̃U (j)|U 1:j−1 being the distribution induced by taking the arg max function defined in Eq. (42).
Lemma 3. According to the polar encoding process of Sec. V-B,
(n)

dTV (qU n , pU n ) ≤ δnld-ls ,
where
(n)
δnld-ls

which implies,

q p
p
p
, n 2 4nδn ln 2(n − log2 4nδn ln 2) + δn + 4nδn ln 2,
(n)

for any k = 1, . . . , K,

(n)

for any m = 1, . . . , M,

dTV (qU n Ykn , pU n Ykn ) ≤ δnld-ls
dTV (qZmn , pZmn ) ≤ δnld-ls
August 28, 2017

DRAFT

25

n ...Z n induced by the original
where pU n Ykn and pZmn are marginal distributions of pU n YKn ...Y1n ZM
1

DMS, and qU n Ykn and qZmn are these marginal distributions after the encoding process.
Proof: See App. A setting L = 1.
3) Reliability performance: Consider the probability of incorrectly decoding all messages
{Wm }M
m=1 at the k-th legitimate receiver. Let us define an optimal coupling [24, Prop. 4.7]
between qU n Ykn and pU n Ykn such that

where EU n Ykn ,





Pr EU n Ykn = dTV (qU n Ykn , pU n Ykn ),



Ũ n , Ỹkn =
6
U n , Ykn . The average probability of incorrectly decoding the

messages {Wm }M
m=1 at the k-th receiver can be upper-bounded as
h
i
h
i
Pr (Ŵ1 , . . . ŴM ) 6= (W1 , . . . , WM ) ≤ Pr Û n 6= Ũ n
i h
i
h
≤ Pr Û n 6= Ũ n E U n Ykn Pr E U n Ykn
h
i h
i
+ Pr Û n 6= Ũ n EU n Ykn Pr EU n Ykn
i
h
i
h
≤ Pr Û n 6= Ũ n E U n Ykn + Pr EU n Ykn
 p

(a)
(n)
β
−n
≤ nδn + δnld-ls = O n n2
,

where (a) holds by the optimal coupling and Lemma 3, and by the average error probability

of SC decoding for source coding with side information [21, Th. 2] because, according to the
 (n) C 
polar coding scheme, the k-th receiver knows Ũ LX|Yk .

4) Secrecy performance: According to Sec. V-D, the information about {Wi }M
i=m leaked to

the m-th eavesdropper is
n
I(Wm , . . . , WM ; F, Z̃m
)


 n
(n) 
= I Ũ ∪M
; Ũ F (n) , Z̃m
i=m Ii

 n


 n
(n) 
(n) 
∪ F (n) Z̃m
= H Ũ ∪M
+ H Ũ F (n) Z̃m
− H Ũ ∪M
i=m Ii
i=m Ii

≤

August 28, 2017

M
X
i=m

(n)

Ii

+ F (n) − H Ũ



(n) 

∪M
i=m Ii

 n
∪ F (n) Z̃m
.

(44)

DRAFT

26

Now, the last term of Eq. (44) can be bounded using Lemma 8 in App. A and Lemma 3 as
 n
(n) 
(n)
∪M
I
∪
F
Z̃m
i=m i
 n


(n) 
n
− H Z̃m
= H Ũ ∪M
∪ F (n) , Z̃m
i=m Ii

 n
(n) 
(n)
(n)
(n)
≥ H U ∪M
I
∪
F
Zm − 2δnld-ls (n − 2 log2 δnld-ls ),
i=m i

H Ũ



(45)

Moreover, by using the chain rule of entropy,
H U



(n) 

∪M
i=m Ii

 n  (a)
∪ F (n) Zm
≥
(b)

≥

X

(n)

j∈ ∪M
i=m Ii
M
X
i=m

(n)
Ii



n
H U (j) U 1:j−1 , Zm

∪F (n)

+ F (n)

!

(1 − 2δn ) ,


(46)

where (a) holds because conditioning does not increase the entropy, and (b) holds because,
(n)

(i = m, . . . , M ) and F (n) given in Eq. (35), Eq. (34)
(n) 
(n)
and Eq. (36), and by Lemma 1, we have ∪M
∪ F (n) ⊆ HX|Zm , and, therefore, we have
i=m Ii

(n) 
n
H U (j) U 1:j−1 , Zm
≥ 1 − 2δn for j ∈ ∪M
∪ F (n) , which follows from the definition
i=m Ii
according to the definition of the sets Ii

(n)

of HX|Zm .

Finally, by substituting Eq. (46) into Eq. (45), and the resulting expression into Eq. (44),
!
M
X
(n)
(n)
(n)
n
I(Wm , . . . , WM ; F, Z̃m
) ≤ 2δn
Ii + F (n) + 2δnld-ls (n − 2 log2 δnld-ls ),
i=m

(n)

and, by the definition of δnld-ls given in Lemma 3,

 p
n
I(Wm , . . . , WM ; F, Z̃m
) ≤ O n2 n2−nβ .

Hence, the strong secrecy condition given in Eq. (5) is satisfied and this concludes the proof.

VI. P OLAR C ODING S CHEMES FOR THE S YMMETRIC D EGRADED B ROADCAST C HANNEL
This section discusses the implementation aspects of the polar coding schemes proposed in
Secs. IV and V when the individual channels of the degraded broadcast channel are symmetric.
Consider a binary-input channel, (X , pY |X , Y), with probability transition matrix given by


pY |X (0|0) · · · pY |X (|Y| − 1|0)
.
(47)
PY |X , 
pY |X (0|1) · · · pY |X |Y| − 1|1)
August 28, 2017

DRAFT

27

Definition 1. (Strong symmetry) A channel (X , pY |X , Y) is strongly symmetric if each row of the
transition matrix PY |X is a permutation of each other row, and each column is a permutation
of each other column.
Definition 2. (Weak symmetry) A channel (X , pY |X , Y) is weakly symmetric if each row of PY |X
P
is a permutation of each other row, and all the column sums x pY |X (y|x) are equal.

The following propositions provide a useful property of the input random variables required

to attain the secrecy-capacity region of the DBC-LD-NLS and DBC-LD-LS models when the
individual channels of the degraded broadcast channel are symmetric.
Proposition 3. If all channels of the DBC are binary-input and symmetric, the secrecy-capacity
region of the DBC-LD-NLS given in Prop. 1 can be obtained by only taking the union over distributions p?V1 ...VK such that p?V` (` = 1, . . . , K) is the uniform and p?V` |V`−1 is strongly symmetric.
Proof. See App. B.
Proposition 4. If all individual channels of the DBC are symmetric, the distribution p?X (x) that
attains the secrecy-capacity region of the DBC-NLD-LS given in Prop. 2 is the uniform.
Proof. Omitted. Follows simply by appropriately applying [20, Prop. 3.2.].
Based on these propositions, the following section focuses on the implementation aspects of
both polar coding schemes.
A. Degraded broadcast channel with layered decoding and non-layered secrecy
Polar Code Construction. Given the blocklength n and the optimum joint distribution
p?V1 ...VK YK ...Y1 ZM ...Z1 = p?V1 ...VK pYK ...Y1 ZM ...Z1 |X ,
p?V1 ...VK being the optimum input distribution satisfying the properties of Prop. 3, the goal of
the polar code construction is to obtain the partition of the universal set [n] at each superpo(n)

(n)

(n)

(n)

sition layer, that is, to define I` , C` , F` , and T`

for ` = 1, . . . , K (see Eqs. (15)-(18)

and Fig. 3 in Sec. IV-A). Thus, the first step is to obtain the corresponding polarized sets
(Eqs. (12)-(14)) involved in the definition of the previous sets at each layer and, consequently,

August 28, 2017

DRAFT

28

the computation of the following entropy terms is required: {H(U` (j)|U`1:j−1 , V`−1 , Y`n )}nj=1 ,

n
{H(U` (j)|U`1:j−1 , V`−1 , ZM
)}nj=1 , and {H(U` (j)|U`1:j−1 , V`−1 )}nj=1 . As mentioned in [21], it is

easier to analyze the evolution of the polarization effect by estimating the Bhattacharyya parameters instead of the entropy terms, which can be obtained with very low complexity using [25,
Alg. PCC-0]. Nevertheless, [21, Prop. 2] proves that both parameters polarize simultaneously.
For instance, to obtain {Z(U` (j)|U`1:j−1 , V`−1 , Y`n )}nj=1 , the algorithm [25, Alg. PCC-0] must
start computing Z(V` |V`−1 , Y` ) and then obtain {Z(U` (j)|U`1:j−1 , V`−1 , Y`n )}nj=1 by recursion.

Although [25, Alg. PCC-0] underestimate the Bhattacharyya parameters, it has been widely
used and produced good polar codes for models without secrecy constraints. Regarding the
first superposition layer (` = 1), since by Prop. 3 the distribution p?V1 is the uniform, notice
(n)

that Z(U1 (j)|U11:j−1 ) = H(U1 (j)|U11:j−1 ) = 1 for all j ∈ [n], which implies HV1 = [n] and
(n)

(n)

(n)

BV1 = HV1 = ∅. Therefore, the set T1

= ∅.

Polar Encoding. According to the polar encoding process defined in Sec. IV-B, the encoder
must construct the sequence ũn` at each superposition layer ` (` = 1, . . . , K), where the entries
 (n) 
n
ũ` T`
must be obtained according to Eq. (19) given ṽ`−1
= ũn Gn from the previous layer.
(n)

Although Eq. (19) suggests to sample randomly those entries ũ` (j) such that j ∈ BV` |V`−1 ⊆ T` ,

the arg max rule in Eq. (20) (SC encoding) used to draw deterministically the entries belonging
(n)

to LV` |V`−1 has proved to perform well in practice also for the entries belonging to BV` |V`−1
(n)

[21]. In the first layer, SC encoding is not needed because the set T1

hand, for layers ` = 2, . . . , K, the computation of the probabilities p?U
(n)

for all j ∈ T`

is empty. On the other

1:j−1 n
V`−1
` (j)|U`

n
(u|ũ1:j−1
, ṽ`−1
)
`

and u ∈ {0, 1} is required in order to perform SC encoding (see Eq. (20)).

Since by Prop. 3, p?V` |V`−1 (ṽ` |ṽ`−1 ) is strongly symmetric and p?V` (ṽ` ) = p?V`−1 (ṽ`−1 ) =

1
2

for

all ṽ` , ṽ`−1 ∈ {0, 1}, then p?V`−1 |V` (ṽ`−1 |ṽ` ) is also strongly symmetric and, indeed, equal to
p?V` |V`−1 (ṽ` |ṽ`−1 ). Thus, we can see the encoding as a decoding process for symmetric channels,

n
where ṽ`−1
will be the receiver’s channel observations and ṽ`n = ũn` Gn the sequence to be

reconstructed with SC decoding. Because of the symmetry, we can use a modification of the
 (n) 
simplest SC decoding algorithm proposed by [8] to obtain the entries ũ` T` . The pseudocode
of this algorithm can be found in [26, Alg. 1], where now the initial likelihood ratios will be
L(j) =

p?V

p?V

`−1 |V`
`−1 |V`

(ṽ`−1 (j)|0)
(ṽ`−1 (j)|1)

n
, for j ∈ [n], and where ṽ`−1
is available from the previous encoding

layer.

August 28, 2017

DRAFT

29

Polar Decoding. According to SC decoding algorithm given Eqs. (22)-(23), we can view
n
, ỹkn ) ∈ {0, 1} × Yk as the receiver’s channel observations. Thus, the initial likelihood
(ṽ`−1

ratios required in [26, Alg. 1] will be L(j, j 0 ) =

(ỹk (j),v̂`−1 (j 0 )|0)
k V`−1 |V`
?
pY V
(ỹk (j),v̂`−1 (j 0 )|1)
k `−1 |V`
p?Y

, for j, j 0 ∈ [n]. The

recursive algorithm proposed by [8] for symmetric channels can be used to estimate the entire
sequence ṽ`n from the previous likelihood ratios if p?Yk V`−1 |V` is symmetric. Since V`−1 − V` − Yk
forms a Markov chain, notice that
p?Yk V`−1 |V` (yk , v`−1 |v` ) = p?Yk |V` (yk |v` )p?V`−1 |V` (v`−1 |v` ).

(48)

As mentioned previously, p?V`−1 |V` is strongly symmetric. Regarding p?Yk |V` , since V` − X − Yk
forms a Markov chain, notice that
p?Yk |V` (yk |v` ) =

X

x∈{0,1}

p?X|V` (x|v` )p?Yk |X (yk |x),

or equivalently, by using matrix notation, P?Yk |V` = P?X|V` P?Yk |X . Indeed, notice that
P?Yk |V` = P?V`+1 |V` P?V`+2 |V`+1 · · · P?X|VK−1 P?Yk |X
because V` −V`+1 −· · ·−X also forms a Markov chain. It is clear that the product of two strongly
symmetric matrices is also strongly symmetric. Therefore, p?X|V` is also strongly symmetric.

Moreover, if the channel p?Y` |X is strongly symmetric, then so will be p?Y` |V` . On the other hand,
if the channel p?Y` |X is weakly symmetric, it is easy to prove that the product of a strongly
symmetric channel (p?X|V` ) and a weakly symmetric channel (p?Y` |X ) results in a weakly symmetric
channel (p?Yk |V` ) because each row of the resulting matrix is simply a linear combination of each
row of p?Y` |X , and this linear combination depends on the structure of the p?X|V` . Finally, if p?V`−1 |V`
is strongly symmetric and p?Yk |V` is (weakly or strongly) symmetric, it is clear that p?Yk V`−1 |V` in
Eq. (48) is (weakly or strongly) symmetric, confirming the the suitability of [26, Alg. 1].
B. Degraded broadcast channel with non-layered decoding and layered secrecy
Polar Construction. Given the blocklength n and the optimum joint distribution
p?XYK ...Y1 ZM ...Z1 = p?X pYK ...Y1 ZM ...Z1 |X ,
p?X being the optimum input distribution satisfying the properties of Prop. 4, the goal of the
polar code construction is to obtain the partition of the universal set [n] defined in Eqs. (35)-(38)

August 28, 2017

DRAFT

30

(see also Fig. 4). Therefore, according to this partition, the computation of the following Bhatn
)}nj=1 , where
tacharyya parameters is required: {Z(U (j)|U 1:j−1 , Y1n )}nj=1 , {Z(U (j)|U 1:j−1 , Zm

m = 1, . . . , M , and {Z(U (j)|U 1:j−1 )}nj=1 . Again, we can use the algorithm [25, Alg. PCC-0] to
compute them. Finally, notice that T (n) = ∅ because p?X (x) =

1
2

for x ∈ {0, 1}.

Polar Encoding. If individual channels of the DBC are symmetric, SC encoding is not needed
because T (n) = ∅. Therefore, according to Sec. V-B, the encoder only has to store the messages
and the realizations of the local and common randomness into ũn .

Polar Decoding. For this model, the recursive algorithm [26, Alg. 1] can be used directly to
estimate the messages because p?Yk |X is weakly or strongly symmetric. For this model, the initial
likelihood ratios will be simply L(j) =

p?Y

(ỹk (j)|0)

p?Y

(ỹk (j)|1)

k |X
k |X

, for j ∈ [n].

VII. F INITE B LOCKLENGHT S IMULATION R ESULTS
For the simulations, we consider the binary-input binary-output symmetric degraded broadcast
channel with two legitimate receivers and two eavesdroppers. Thus, |Yk | = |Zm | = 2 (for
k, m ∈ [1, 2]). The individual channels are defined simply by its crossover probability αYk (or
αZm ). Due to the degradedness condition of the broadcast channel, αY2 < αY1 < αZ2 < αZ1 .
√ 
β
As stated in Th. 1, the information leakage is O n2 nδn , where δn = 2−n for some β ∈

(0, 12 ), which is clear that tends to zero for sufficiently large n. However, for finite blocklength,
q
√
5
it is easy to show that n2 nδn is increasing with n for n ≤ β β log
and then decreases to
2
zero for larger values. Notice that the bigger is the value of β, the smaller is the n for which
β

the information leakage starts to decrease. However, for large β, the δn = 2−n used to obtain
the partition of the universal set [n] in the polar code construction becomes very small, which
may lead to very small rates of the messages. For simplicity, instead of using δn for each value
of n and then evaluate the performance of the proposed polar coding schemes for different
values of n, we introduce the pair (δ (r) , δ (s) ) (which does not depend on n) and we evaluate the
performance for different values of the triple (n, δ (r) , δ (s) ). Since the algorithm [25, Alg. PCC-0]
used in the polar code construction underestimate the Bhattacharyya parameters, we use δ (r) and
δ (s) to define the polarized sets denoted by L and H respectively. Hence, δ (r) will impact mainly
on the reliability performance of the proposed polar codes and δ (s) on their secrecy performance.

Hence, according to this triple, first we construct the polar code (define the partition of [n]),
and afterwards, we run a Monte Carlo simulation: at each realization, we generate randomly

August 28, 2017

DRAFT

31

the messages and the local and common randomness realizations. Then, we run the encoding
n
(m = 1, . . . , M ) after the broadcast
algorithms. Given the observations ỹkn (k = 1, . . . , K) and z̃m

channel realization, we run the decoding algorithms at each legitimate receiver to estimate the
corresponding transmitted messages and the decoding algorithms at each eavesdropper to evaluate
the secrecy performance. After Nr realizations, we evaluate the corresponding average probability
of error at each receiver and the corresponding information leakage at each eavesdropper.
A. Degraded broadcast channel with layered decoding and non-layered secrecy
For this model, we have αY2 = 0.02, αY1 = 0.0968, αZ2 = 0.3387, and αZ1 = 0.3839. Consider
the input random variables V and X associated to the first and second superposition layer
respectively. According to Prop. 3, we set pV (v) = pX (x) =

1
2

for v, x ∈ {0, 1}. Moreover, we

set p?X|V (x|v) = 0.1215 when x 6= v, which is the distribution that maximizes log(R1 ) + log(R2 ).

The theoretically achievable rates associated to the messages W1 and W2 are R1c = 0.2452 and
R2c = 0.4010, respectively (sum-rate RTc = R1c + R2c = 0.6462).
In Fig. 5, the estimated Bhattacharyya parameters using [25, Alg. PCC-0] and the partition of
the universal set are displayed for the superposition layer 1 and 2 when δ (r) = δ (s) = 0.05 and
n = 211 (β = 0.192). In order to obtain a better view of the partition [n], in Fig. 5 j 0 = π1 (j)
and j 00 = π2 (j) denote a particular indexing for the Bhattacharyya parameters given by ordering
{Z(U1 (j 0 )|U11:j−1 , Y1n )}nj0 =1 (layer 1) and {Z(U2 (j 00 )|U21:j−1 , V n )}nj00 =1 (layer 2) from lowest to
highest respectively, π1 and π2 being the permutations of the indices j that provide such ordering.
Note that the subset property for degraded broadcast channels (Lemma 1) is readily apparent. In
this plot, the different colors of the indices j 0 and j 00 represent the set of the partition given in
(n)

Eqs. (15)-(18) that they belong to: I`

(n)

(green), C`

(n)

(blue), F`

` = {1, 2} according to the superposition layer and recall that

(n)

(red), and T`

(n)
T1

(gray), where

= ∅ in layer 1 because of

the symmetry of the individual channels.
Regarding the secrecy performance, we provide an estimate of the information leakage at the
n
m-th eavesdropper, IˆSCd (W1 , W2 ; F1 , F2 , Z̃m
). In order to estimate the information leakage, we
assume that the strategy followed by all eavesdroppers to obtain the messages is to perform
 (n) 
SC decoding. Therefore, to estimate the message W` = ũ` I`
at layer ` (` = 1, 2), they
 (n) C 
 (n) 
run the SC decoding algorithm [26, Alg. 1] to estimate ũ` F`
from ũ` F`
(known
by all eavesdroppers because the source of common randomness is public), its channel output

August 28, 2017

DRAFT

32

1
1:j−1

Z U1(j)|U1

, Y1n

1



0.9


1:j−1
, Y2n
Z U1(j)|U1
1:j−1 n 
, Z2
Z U1(j)|U1

0.8
0.7
0.6

Bhattacharyya parameter

Bhattacharyya parameter

0.9

0.5
0.4
0.3
0.2
0.1
0

0.8
0.7
0.6

1:j−1



, V n, Y2n

1:j−1
, V n, Z2n
Z U2(j)|U2

1:j−1
,V n
Z U2(j)|U2
Z U2(j)|U2

0.5
0.4
0.3
0.2
0.1

200

400

600

0

800 1000 1200 1400 1600 1800 2000
Channel index (j)

200

(a) Superposition layer 1.

400

600

800 1000 1200 1400 1600 1800 2000
Channel index (j)

(b) Superposition layer 2.

Fig. 5: Polar construction for the DBC-LD-NLS when δn = 0.05 (β = 0.192) and n = 211 . The
ordered Bhattacharyya parameters associated to each layer are displayed, and the partition of
(n)

the universal set [n] is depicted: I`

(n)

(green), C`

(n)

(blue), F`

(n)

(red), and T`

(gray), where

` = {1, 2} according to the superposition layer.
n
n
, and the sequence v̂`−1
= ûn`−1 Gn estimated previously at layer ` − 1. Then,
observations z̃m

from the final likelihoods ratios computed in order to make the decisions, we can obtain the
n
)}j∈I (n) ⊆(F (n) )C . After Nr realizations, we can
probabilities {pU` (j)|U 1:j−1 V`−1 Zmn (0|ũ1:j−1
, v̂`−1 , z̃m
`
`

`

`

n
)}j∈I (n) , which denote the
compute the average probabilities {p̄U` (j)|U 1:j−1 V`−1 Zmn (0|ũ1:j−1
, v̂`−1 , z̃m
`
`

`

empirical distribution of the messages estimated at the m-th eavesdropper assuming SC decoding.
Finally, given the the empirical distribution at each layer, we can compute
2
X
X

(n)
n
n
IˆSCd (W1 , W2 ; F1 , F2 , Z̃m
H2 p̄U` (j)|U 1:j−1 V`−1 Zmn (0|ũ1:j−1
,
)=
,
v̂
,
z̃
)
I` −
`−1 m
`
`

`=1

(n)

j∈I`

where H2 (p) = −p log2 p − (1 − p) log2 (1 − p).

The secrecy performance for different values of the triple (n, δ (r) , δ (s) ), δ (r) set to 0.05, is

displayed in Fig. 6. For a fixed δ (s) , notice that the higher n, the worse is the secrecy performance.
This occurs because, for the chosen values of n and δ (s) , the information leakage increases with
n. Nevertheless, since the values of (n, δ (r) , δ (s) ) also impact on the message rates because of
the polarization theorem, notice in Table I that the higher n, the large is the achieved sum-rate
for the polar coding scheme. Indeed, from Fig. 6 and Table I, we can see that, for a given
target sum-rate, the secrecy performance is always better for large blocklength n. Obviously, the
information leakage is always higher at the second eavesdropper because it has better channel.

August 28, 2017

DRAFT

Estimate of the Information Leakage

33

0.5

IˆSCd (W1 , W2 ; F1 , F2 , Z1n )
IˆSCd (W1 , W2 ; F1 , F2 , Z n )

0.4

2

n = 212

0.3
n = 211

0.2
n = 210

0.1
n = 29

0
10−3

10−2
δ

(s)

Fig. 6: Secrecy performance (estimate of the information leakage to the eavesdroppers) of the
polar coding scheme proposed for the DBC-LD-NLS for different δ (s) and n when δ (r) = 0.05.
δ (s)

n = 29

5 · 10−4

10−3

5 · 10−3

10−2

5 · 10−2

0.2509

0.2781

0.3505

0.3898

0.4988

n=2

10

0.3641

0.3914

0.4550

0.4865

0.5698

n=2

11

0.4721

0.4957

0.5517

0.5795

0.6453

n=2

12

0.5569

0.5746

0.6192

0.6422

0.6962

TABLE I: Normalized sum-rate (w.r.t. RTc = 0.6462) vs. δ (s) for the DBC-LD-NLS (δ (r) = 0.05).
Due to space constraints, the reliability performance of the polar coding scheme is not analyzed
for different values of δ (r) in detail. Nevertheless, for δ (r) = 0.05, we obtain that the corresponding
average probabilities of error for the different values of (δ (s) , n) given in Table I are always less


than the following ones: at the legitimate receiver 1, Pr Ŵ1 6= W1 = 0.016; and at the legitimate




receiver 2, Pr Ŵ1 6= W1 = 0 and Pr Ŵ2 6= W2 = 0.015.
Finally, in the simulations, we obtain that the length of the secret messages defined in Eq. (21)

are indeed zero for all triples (n, δ (r) , δ (s) ) (is negligible in terms of length, not only in terms of
rate penalty). This occurs because, as can be seen in Fig. 5, practically all channel indices such
(n)

(n)

that belong to BV` |V`−1 Y` belong also to HV` |V`−1 Z2 (for ` = 1, 2). Therefore, all these indices can
(n)

be included in F`

and their entries will carry part of the source of common randomness.

B. Degraded broadcast channel with non-layered decoding and layered secrecy
For this model, we assume that αY2 = 0.03, αY1 = 0.077, αZ2 = 0.2208, and αZ1 = 0.4162.
The encoding process takes place only over the input random variable X (where recall that

August 28, 2017

DRAFT

34

1
2

U n = X n Gn ). According to Prop. 4, pX (x) =

for x ∈ {0, 1}. The achievable rates associated

to W1 and W2 are R1c = 0.1920 and R2c = 0.2885, respectively (sum-rate RTc = 0.4805).
In relation to the secrecy performance, now we provide an estimate of IˆSCd (W1 , W2 ; F, Z̃1n ) and
IˆSCd (W2 ; F, Z̃2n ) at the eavesdroppers 1 and 2 respectively. We assume that the strategy followed
by all eavesdroppers in order to obtain the messages is to perform the SC decoding algorithm [26,
C 



n
and we obtain
, the m-th eavesdropper estimate ũ F (n)
Alg. 1]. Thus, given ũ F (n) and z̃m

. Finally, we evaluate
the empirical distribution {p̄U (j)|U 1:j−1 Z n (0|ũ1:j−1 , z̃ n )}
(n)
m

m

j∈ ∪M
i=m Ii

⊆(F (n) )C

the estimate of the information leakage at the eavesdropper 1,
IˆSCd (W1 , W2 ; F, Z̃1n ) =

2
X
i=1

(n)

Ii

X

−

(n)

j∈ ∪M
i=m Ii

and at the eavesdropper 2,
(n)
IˆSCd (W2 ; F, Z̃2n ) = I2 −

X

(n)

j∈I2




H2 p̄U (j)|U 1:j−1 Z1n (0|ũ1:j−1 , z̃1n ) ,


H2 p̄U (j)|U 1:j−1 Z2n (0|ũ1:j−1 , z̃2n ) .

The secrecy performance for different values of (n, δ (r) , δ (s) ), δ (r) set to 0.05, is displayed in
Fig. 7. Now, for δ (s) sufficiently small, notice that the corresponding information leakage are
very close to zero and the corresponding sum-rates are close to the capacity (see Table II). This
occurs probably because SC encoding is not needed and, therefore, the joint distribution induced
by the encoding is very close in terms of the total variation distance to the original one used

Estimate of the Information Leakage

for the polar code construction even for n not too large.
0.4
0.3

IˆSCd (W1 , W2 ; F, Z1n )
IˆSCd (W2 ; F, Z n )
2

n = 213
n = 212

0.2
0.1

n = 211

0
10−6

10−5

10−4
10−3
δ (s)

10−2

Fig. 7: Secrecy performance (estimate of the information leakage to the eavesdroppers) of the
polar coding scheme proposed for the DBC-NLD-LS for different δ (s) and n when δ (r) = 0.05.

August 28, 2017

DRAFT

35

δ (s)
10−6

10−5

10−4

10−3

10−2

10−1

n = 211

0.8079

0.8312

0.8545

0.8749

0.9034

0.9236

n=2

12

0.8358

0.8545

0.8739

0.8891

0.9080

0.9253

n=2

13

0.8624

0.8760

0.8899

0.9028

0.9165

0.9315

TABLE II: Normalized sum-rate (w.r.t. RTc = 0.4805) vs. δ (s) for the DBC-NLD-LS (δ (r) = 0.05).

Now, for δ (r) = 0.05, we obtain that the corresponding average probabilities of error for the
different values of (δ (s) , n) given in Table II are always less than the following ones: at the




legitimate receiver 1, Pr Ŵ1 6= W1 = 0.02 and Pr Ŵ2 6= W2 = 0.035; at the legitimate




receiver 2, Pr Ŵ1 6= W1 = 5.5 · 10−6 and Pr Ŵ2 6= W2 = 7.5 · 10−6 .
As for the previous model, we obtain that the length of the secret message defined in Eq. (40)

is always zero for all evaluated triples (n, δ (r) , δ (s) ).
VIII. C ONCLUSIONS
We have proposed two strongly secure polar coding schemes for the degraded broadcast
channel with arbitrary number of legitimate receivers and eavesdroppers. Each polar coding
scheme achieves any rate tuple inside the secrecy-capacity region of two different models, which
are given by different reliability and secrecy constraints. The polar coding schemes do not
require any chaining construction because of the degradedness condition of the channels and the
assumption of a given source of common randomness available to all parties.
Furthermore, we have proposed two simple implementations of the strongly secure polar
coding schemes analyzed theoretically, and we have provided different simulations in order to
evaluate their performance. These simulations show that these polar codes can perform well
over the binary-input symmetric degraded broadcast channel, which is a setting that arises in
many wireless communication systems. Based on the simulations, we show that in practice the
required secret seeds to be shared between the transmitter and legitimate receivers can be indeed
negligible in terms of length, not only in terms of rate penalty.
One of the limitations of these schemes (and for physical layer security applications in general)
is that the transmitter needs to know the statistics of the eavesdropper channels. Nevertheless,
notice that for the DBC-LD-NLS, one can design a good polar coding scheme for a virtual

August 28, 2017

DRAFT

36

eavesdropper with some target channel quality and this polar coding scheme will perform well
for any other eavesdropper channel with worse channel quality. For the DBC-NLD-LS, one can
simply consider different levels of secrecy depending on different target channel qualities.
A PPENDIX A
D ISTRIBUTION OF THE DMS

AFTER

P OLAR E NCODING

Let pU1n ...ULn be the joint distribution of (U1n , . . . , ULn ) and let qU1n ...ULn denote the joint distribution of (Ũ1n , . . . , ŨLn ) after a particular polar encoding procedure,
qU1n ...ULn (un1 , . . . , unL )

=

L Y
n
Y

qU` (j)|U 1:j−1 V n
`

`−1

u` (j) u1:j−1
, un`−1 Gn
`

`=1 j=1

such that

n
qU` (j)|U 1:j−1 V n u` (j) u1:j−1
, v`−1
`
`
`−1

(n)
1


if j ∈ HV` |V`−1 ,

 2

(n)
n
, v`−1
if j ∈ BV` |V`−1 ,
= pU` (j)|U 1:j−1 V n u` (j) u1:j−1
`
`
`−1




(n)
1:j−1 n
 q̃
1:j−1 n
u
(j)
u
,
v
`
`−1 if j ∈ LV` |V`−1 ,
`
U` (j)|U
V
`

where pU` (j)|U 1:j−1 V n
`

`−1



(49)

`−1

is the distribution induced by the original DMS, q̃Uk (j)|U 1:j−1 V n
k

k−1

is the

distribution induced by the arg max function defined as in Eqs. (23) and (42).
Moreover, consider another encoding process that constructs (Ǔ1n , . . . , ǓLn ) with distribution

n
q̌U` (j)|U 1:j−1 V n u` (j) u1:j−1
, v`−1
`
`
`−1

(n)
 1
if j ∈ HV` |V`−1 ,
2
=

C
(n)
1:j−1 n
 p
, v`−1 if j ∈ HV` |V`−1 ,
U` (j)|U 1:j−1 V n u` (j) u`
`

(50)

`−1

(n)

i.e., an encoder that does not take deterministic decisions for the set LV` |V`−1 , but draws its
elements according to the original distribution of the DMS.
β

Lemma 4. Let δn = 2−n for some β ∈ (0, 12 ). Then,

(1)

where δn ,

August 28, 2017

√

dTV (q̌U`n , pU`n ) ≤ δn(1) ,
4nδn ln 2.

DRAFT

37

Proof. First, the Kullback-Leiber distance between pU`n and q̌U`n can be upper-bounded as follows.
By applying the chain rule,
n


 X
DKL pU`n q̌U`n =
DKL pU` (j)|U 1:j−1 q̌U` (j)|U 1:j−1
`

`

j=1

(a)

≤

X

(n)
` |V`−1

j∈HV
(b)





1:j−1
1 − H U` (j) U`1:j−1 , U`−1

(n)

≤ 2δn HV` |V`−1 .
≤ 2nδn .
where (a) holds because conditioning does not increase the entropy, because by Lemma 1 we
have HV` |V`−1 ⊆ HV` , and therefore, we can apply [15, Lemma 10], i.e., DKL (pkq̌) = 1 − H(p)


n
≥ 1 − 2δn
if q̌ denotes the uniform distribution; and (b) holds because H U` (j) U`1:j−1 , U`−1
(n)

(n)

for any j ∈ HV` |V`−1 , which follows from the definition of the set HV` |V`−1 , the one-to-one
n
n
relation between U`−1
and V`−1
. Finally, by using Pinsker’s inequality, we obtain dTV (q̌U`n , pU`n ) ≤
√
4nδn ln 2 and this concludes the proof.
β

Lemma 5. Let δn = 2−n for some β ∈ (0, 21 ). Then,
dTV (qU1n ...ULn , pU1n ...ULn ) ≤ δn(2) ,

where

(2)
δn

,

L(L+1)
n
2

q
√ (1)
(1)
(1)
(1)
2δn (n − log2 δn ) + δn + Lδn , and δn defined as in Lemma 4.

Proof. First, consider a coupling [24] for Ǔ`n and Ũ`n such that
 (n) C 
 (n) C 
Ǔ` LV` |V`−1
= Ũ` LV` |V`−1 .

 n
n
Moreover, consider the error event EŨ n , Ũ`−1
6= Ǔ`−1
. Thus,
`−1

h
i
(a)
dTV (qU`n , q̌U`n ) ≤ Pr Ũ`n 6= Ǔ`n
i h
i
i h
i
h
h
= Pr Ũ`n 6= Ǔ`n E Ũ n Pr E Ũ n + Pr Ũ`n 6= Ǔ`n EŨ n Pr EŨ n
`−1
`−1
`−1
`−1
h
i
h
i
n
n
≤ Pr Ũ`n 6= Ǔ`n E Ũ n + Pr Ũ`−1
6= Ǔ`−1
`−1
q
h
i
(b)
(1)
(1)
n
n
≤ n 2δn (n − log2 δn ) + δn + Pr Ũ`−1 6= Ǔ`−1 ,

August 28, 2017

DRAFT

38

where (a) follows from the coupling lemma [24, Prop. 4.7], and (b) holds by [27, Lemma 2]
and by Lemma 4. Therefore, by induction, we obtain
dTV (qU1n ...ULn , q̌U1n ...ULn ) ≤

L
X
`=1

h
i
n
n
Pr Ũ` 6= Ǔ`

q
L(L + 1)
(1)
(1)
n 2δn (n − log2 δn ) + δn .
≤
2
Finally, by applying the triangle inequality, we have
dTV (qU1n ...ULn , pU1n ...ULn ) ≤ dTV (qU1n ...ULn , q̌U1n ...ULn ) + dTV (q̌U1n ...ULn , pU1n ...ULn )
q
√
L(L + 1)
(1)
(1)
≤
n 2δn (n − log2 δn ) + δn + Lδn(1) ,
2
where the second term is obtained by applying the Pinker’s inequality over
DKL

L
 (a) X
q̌U1n ...ULn kpU1n ...ULn =

X

`=1 j∈H(n)
V |V
`

`−1




n
1 − H U` (j) U`1:j−1 , U`−1

(b)

≤ 2nδn L,
where (a) and (b) hold by similar reasoning as in the proof of Lemma 4.
Lemma 6. Let pU`n0 ...U`n Ykn be the original joint distribution of (U`n0 , . . . , U`n , Ykn ) and qU`n0 ...U`n Ykn
the joint distribution of (Ũ`n0 , . . . , Ũ`n , Ỹkn ) for some ` = 1, . . . , L, 1 ≤ `0 ≤ ` and k = 1, . . . , K 0 .

β
Let δn = 2−n for some β ∈ 0, 12 . Then,

dTV (qU`n0 ...U`n Ykn , pU`n0 ...U`n Ykn ) ≤ dTV qU1n ...ULn , pU1n ...ULn .

Proof. First, notice that

pU`n0 ...U`n Ykn (un`0 , . . . , un` , ykn ) =

X

n
un
g ∈{0,1}
g ∈(`
/ 0 ,`)

pU1n ...ULn (un1 , . . . , unL )pYkn |ULn (ykn |unL )

because U1n − U2n − · · · − ULn − Ykn forms a Markov chain. Similarly,
X
qU`n0 ...U`n Ykn (un`0 , . . . , un` , ykn ) =
qU1n ...ULn (un1 , . . . , unL )pYkn |ULn (ykn |unL ).
n
un
g ∈{0,1}
g ∈(`
/ 0 ,`)

August 28, 2017

DRAFT

39

because Ũ1n − Ũ2n − · · · − ŨLn − Ỹkn also forms a Markov chain and qYkn |ULn = pYkn |ULn because it
only depends on the channel. Thus, by using the definition of the total variation distance,
dTV (qU`n0 ...U`n Ykn , pU`n0 ...U`n Ykn )
X
X
X
=
un
∈{0,1}n ykn ∈Ykn
g0
g 0 ∈(`0 ,`)

≤
=

n
un
g ∈{0,1}
g ∈(`
/ 0 ,`)

X


pYkn |ULn (ykn |unL ) qU1n ...ULn (un1 , . . . , unL ) − pU1n ...ULn (un1 , . . . , unL )

X

X

X

qU1n ...ULn (un1 , . . . , unL ) − pU1n ...ULn (un1 , . . . , unL )

n
un
∈{0,1}n ykn ∈Ykn un
g ∈{0,1}
g0
0 ,`)
0
0
g
∈(`
/
g ∈(` ,`)

n
un
g ∈{0,1}
g∈(1,L)


= dTV qU1n ...ULn , pU1n ...ULn ,


pYkn |ULn (ykn |unL ) qU1n ...ULn (un1 , . . . , unL ) − pU1n ...ULn (un1 , . . . , unL )

where the last equality holds because

P

ykn ∈Ykn

X

ykn ∈Ykn

pYkn |ULn (ykn |unL )

pYkn |ULn (ykn |unL ) = 1 for any unL ∈ {0, 1}n .

Lemma 7. Let pYkn be the original distribution of Ykn , and qYkn the joint distribution of Ỹkn for

β
some k = 1, . . . , K 0 . Let δn = 2−n for some β ∈ 0, 21 . Then,

dTV (pYkn , qYkn ) ≤ dTV qU1n ...ULn , pU1n ...ULn .

Proof. Omitted. The proof is similar to that of Lemma 6.

Lemma 8. Consider the joint distributions pU`n0 ...U`n Ykn and qU`n0 ...U`n Ykn for some ` = 1, . . . , L,
1 ≤ `0 ≤ ` and k = 1, . . . , K 0 , and such that dTV (qU`n0 ...U`n Ykn , pU`n0 ...U`n Ykn ) ≤ n , where n → 0 for

n sufficiently large. Let Ag ⊆ [n], for `0 ≤ g ≤ `. Then


H U`0 [A`0 ], . . . , U` [A` ], Ykn − H Ũ`0 [A`0 ], . . . , Ũ` [A` ], Ỹkn ≤ n (n − 2 log2 n ).
Proof. Let d , dTV (qU`0 [A`0 ]...U` [A` ]Ykn , pU`0 [A`0 ]...U` [A` ]Ykn ). We have


 (a)
H U`0 [A`0 ], . . . , U` [A` ], Ykn − H Ũ`0 [A`0 ], . . . , Ũ` [A` ], Ỹkn ≤ d log2 2n + h (d)
(b)

≤ n (n − 2 log2 n )

where (a) holds by the bound on the entropy via coupling [28, Th. 3], and (b) holds because
d = dTV (qU`0 [A`0 ]...U` [A` ]Ykn , pU`0 [A`0 ]...U` [A` ]Ykn ) ≤ dTV (qU`n0 ...U`n Ykn , pU`n0 ...U`n Ykn ) ≤ n ,
and h() < −2n log2 n for any n < 0.5. Note that it is monotonically decreasing for n → 0.
August 28, 2017

DRAFT

40

A PPENDIX B
P ROOF OF P ROP. 3
According to Coro. 1, the rate R` associated to the message W` satisfies
R` ≤ I(V` ; Y` |V`−1 ) − I(V` ; ZM |V`−1 )
(a)

= I(V` ; Y` |ZM ) − I(V`−1 ; Y` |ZM ).

where (a) holds because V`−1 − V` − Y` − ZM forms a Markov chain. Now, consider the overall
sum rate. Since V1 − · · · − VK − YK − · · · − Y1 − ZM − · · · − Z1 forms a Markov chain, we have
K
X

R` =

`=1

K
X
`=1

=

K
X
`=1

=

K
X
`=1

(I(V` ; Y` |V`−1 ) − I(V` ; ZM |V`−1 ))
I(V` ; Y` |V`−1 ) − I(X; ZM )
(I(V` ; Y` ) − I(V`−1 ; Y` )) − I(X; ZM )

= I(X; YK ) − I(VK−1 ; YK ) +
(a)

K−1
X
`=1

(I(V` ; Y` ) − I(V`−1 ; Y` )) − I(X; ZM )

≤ I(X; YK ) − I(X; ZM ),
where (a) holds with equality only if X is independent of VK−1 . Moreover, if X is independent
of VK−1 , notice that the rate RK associated to the message WK satisfies
RK = I(X; YK |VK−1 ) − I(X; ZM |VK−1 )
= I(X; YK ) − I(X; ZM ).
Thus, the overall rate is maximum when all information is carried only over the message WK .
By [20, Prop. 3.2.], the rate RK will be maximum if pX is the uniform over {0, 1}.
Now, consider that we want to transfer part of the rate of the message WK to WK−1 . Then, as
mentioned in [29, Ex. 15.6.5], by symmetry, VK−1 and X can be connected simply by a binaryinput binary-output symmetric channel, which means that pX|VK−1 will be strongly symmetric.

August 28, 2017

DRAFT

41

Moreover, since we want to transfer part of the rate RK only to RK−1 , then we set VK−2
independent of VK−1 . Thus, we have
RK = I(X; YK |ZM ) − I(VK−1 ; YK |ZM ),
RK−1 = I(VK−1 ; YK−1 |ZM ),
Rk = 0

(k = 1, . . . , K − 2).

If pX|VK−1 is strongly symmetric, and pYk |X (k = 1, . . . , K) and pZm |X (m = 1, . . . , M ) are
(weakly or strongly) symmetric, it is easy to prove that pYK−1 |VK−1 and pZM |VK−1 will be also
(weakly or strongly) symmetric because each row of the resulting probability transition matrix
will be simply a linear combination of each row of the probability transition matrix associated
to pYK−1 |VK−1 or pZM |VK−1 , and this linear combination depends on the structure of the matrix
associated to pX|VK−1 . Thus, by [20, Prop. 3.2.], the distribution on VK−1 that maximizes the
rates RK and RK−1 is the uniform distribution over {0, 1}. Notice that we will have maximum
information transfer to RK−1 by setting X deterministic given VK−1 , which implies RK = 0
and RK−1 = I(X; YK−1 |ZM ).
Finally, we can follow the same reasoning to determine that the whole secrecy capacity region
given in Prop. 1 can be obtained by only taking the union over distributions pV1 ...VK such that
pV` |V`−1 is strongly symmetric and pVk (vk ) =

1
2

for vk ∈ {0, 1} (` = 1, . . . , K).

R EFERENCES
[1] A. Wyner, “The wire-tap channel,” The Bell System Technical Journal, vol. 54, pp. 1355–1387, Oct 1975.
[2] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Transactions on Information Theory,
vol. 24, pp. 339–348, May 1978.
[3] U. Maurer and S. Wolf, “Information-theoretic key agreement: From weak to strong secrecy for free,” in Advances in
CryptologyEUROCRYPT 2000, pp. 351–368, Springer, 2000.
[4] S. Zou, Y. Liang, L. Lai, H. Poor, and S. Shamai, “Broadcast networks with layered decoding and layered secrecy: Theory
and applications,” Proceedings of the IEEE, vol. 103, pp. 1841–1856, Oct 2015.
[5] E. Ekrem and S. Ulukus, “Secrecy capacity of a class of broadcast channels with an eavesdropper,” EURASIP J. Wirel.
Commun. Netw., pp. 1:1–1:29, Mar. 2009.
[6] Y. Liang, L. Lai, H. V. Poor, and S. Shamai, “A broadcast approach for fading wiretap channels,” IEEE Transactions on
Information Theory, vol. 60, pp. 842–858, Feb 2014.
[7] S. Zou, Y. Liang, L. Lai, and S. Shamai, “An information theoretic approach to secret sharing,” IEEE Transactions on
Information Theory, vol. 61, pp. 3121–3136, June 2015.

August 28, 2017

DRAFT

42

[8] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input
memoryless channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, 2009.
[9] H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,” IEEE Transactions
on Information Theory, vol. 57, pp. 6428–6443, Oct 2011.
[10] E. Sasoglu and A. Vardy, “A new polar coding scheme for strong security on wiretap channels,” in IEEE International
Symposium onInformation Theory Proceedings (ISIT), pp. 1117–1121, July 2013.
[11] J. M. Renes, R. Renner, and D. Sutter, “Efficient one-way secret-key agreement and private channel coding via polarization,”
in Advances in Cryptology-ASIACRYPT, pp. 194–213, Springer, 2013.
[12] Y. Wei and S. Ulukus, “Polar coding for the general wiretap channel with extensions to multiuser scenarios,” IEEE Journal
on Selected Areas in Communications, vol. 34, pp. 278–291, Feb 2016.
[13] T. Cihad Gulcu and A. Barg, “Achieving secrecy capacity of the wiretap channel and broadcast channel with a confidential
component,” arXiv preprint arXiv:1410.3422, 2014.
[14] R. A. Chou and M. R. Bloch, “Polar coding for the broadcast channel with confidential messages: A random binning
analogy,” IEEE Transactions on Information Theory, vol. 62, pp. 2410–2429, May 2016.
[15] N. Goela, E. Abbe, and M. Gastpar, “Polar codes for broadcast channels,” IEEE Transactions on Information Theory,
vol. 61, pp. 758–782, Feb 2015.
[16] R. A. Chou, M. R. Bloch, and E. Abbe, “Polar coding for secret-key generation,” IEEE Transactions on Information
Theory, vol. 61, pp. 6213–6237, Nov 2015.
[17] L. Wang and E. Sasoglu, “Polar coding for interference networks,” in 2014 IEEE International Symposium on Information
Theory, pp. 311–315, June 2014.
[18] R. A. Chou and A. Yener, “Polar coding for the multiple access wiretap channel via rate-splitting and cooperative jamming,”
in 2016 IEEE International Symposium on Information Theory (ISIT), pp. 983–987, July 2016.
[19] C. Hirche, C. Morgan, and M. M. Wilde, “Polar codes in network quantum information theory,” IEEE Transactions on
Information Theory, vol. 62, pp. 915–924, Feb 2016.
[20] M. Bloch and J. Barros, Physical-layer security: from information theory to security engineering. Cambridge University
Press, 2011.
[21] E. Arıkan, “Source polarization,” in IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 899–903,
2010.
[22] M. Karzand and E. Telatar, “Polar codes for q-ary source coding,” in 2010 IEEE International Symposium on Information
Theory, pp. 909–912, June 2010.
[23] E. Şasoğlu, E. Telatar, and E. Arikan, “Polarization for arbitrary discrete memoryless channels,” in IEEE Information
Theory Workshop., pp. 144–148, 2009.
[24] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times. American Mathematical Soc., 2009.
[25] H. Vangala, E. Viterbo, and Y. Hong, “A comparative study of polar code constructions for the awgn channel,” arXiv
preprint arXiv:1501.02473, 2015.
[26] H. Vangala, E. Viterbo, and Y. Hong, “Permuted successive cancellation decoder for polar codes,” in 2014 International
Symposium on Information Theory and its Applications, pp. 438–442, Oct 2014.
[27] R. A. Chou and M. R. Bloch, “Using deterministic decisions for low-entropy bits in the encoding and decoding of polar
codes,” in 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1380–1385,
Sept 2015.

August 28, 2017

DRAFT

43

[28] I. Sason, “Entropy bounds for discrete random variables via maximal coupling,” IEEE Transactions on Information Theory,
vol. 59, no. 11, pp. 7118–7131, 2013.
[29] T. M. Cover and J. A. Thomas, Elements of information theory. John Wiley & Sons, 2012.

August 28, 2017

DRAFT

