1

Broadcast Channels with Privacy Leakage
PSfrag replacements
Constraints

arXiv:1504.06136v3 [] 28 May 2017

Ziv Goldfeld, Student Member, IEEE, Gerhard Kramer, Fellow, IEEE, and Haim H. Permuter, Senior Member,
IEEE

Abstract—The broadcast channel (BC) with one common and
two private messages with leakage constraints is studied, where
leakage rate refers to the normalized mutual information between
a message and a channel symbol string. Each private message
is destined for a different user and the leakage rate to the
other receiver must satisfy a constraint. This model captures
several scenarios concerning secrecy, i.e., when both, either or
neither of the private messages are secret. Inner and outer
bounds on the leakage-capacity region are derived when the
eavesdropper knows the codebook. The inner bound relies on
a Marton-like code construction and the likelihood encoder. A
Uniform Approximation Lemma is established that states that
the marginal distribution induced by the encoder on each of
the bins in the Marton codebook is approximately uniform.
Without leakage constraints the inner bound recovers Marton’s
region and the outer bound reduces to the UVW-outer bound.
The bounds match for semi-deterministic (SD) and physically
degraded (PD) BCs, as well as for BCs with a degraded message
set. The leakage-capacity regions of the SD-BC and the BC
with a degraded message set recover past results for different
secrecy scenarios. A Blackwell BC example illustrates the results
and shows how its leakage-capacity region changes from the
capacity region without secrecy to the secrecy-capacity regions
for different secrecy scenarios.
Index Terms—Broadcast channel, Marton’s inner bound, Privacy Leakage, Secrecy, Physical-layer Security.

I. I NTRODUCTION
Public and confidential messages are often transmitted over
the same channel. However, the underlying principles for
constructing codes without and with secrecy are different.
Without secrecy constraints, codes should use all available
channel resources to reliably convey information to the destinations. Confidential messages, on the other hand, require
that some channel resources are allocated to preserve security.
We study relationships between the coding strategies and
the fundamental limits of communication with and without
secrecy. To this end we simultaneously account for secret and
non-secret transmissions over a two-user broadcast channel
(BC) by means of privacy leakage constraints (Fig. 1).
Z. Goldfeld and H. H. Permuter were supported in part by European
Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement n◦ 337752, in part by the
Israel Science Foundation and in part by the Cyber Security Research Center
within the Ben-Gurion University of the Negev. G. Kramer was supported by
an Alexander von Humboldt Professorship endowed by the German Federal
Ministry of Education and Research.
Z. Goldfeld and H. H. Permuter are with the Department of Electrical and
Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva,
Israel (gziv@post.bgu.ac.il, haimp@bgu.ac.il). G. Kramer is with the Institute
for Communications Engineering, Technical University of Munich, Munich
D-80333, Germany (gerhard.kramer@tum.de).

Channel
(M0,M1,M2)

Enc f

(n)

Y1

(n)

Dec φ1

X W
Y1 ,Y2 |X
Y2

(1)

(M̂0 , M̂1 )
ℓ2 (cn ) ≤ nL2
(2)

(n)

Dec φ2

(M̂0 , M̂2 )
ℓ1 (cn ) ≤ nL1

Fig. 1: A BC with a common message and privacy leakage
constraints ℓ1 (cn ) , Icn (M1 ; Y2 ) ≤ nL1 and ℓ2 (cn ) ,
Icn (M2 ; Y1 ) ≤ nL2 , where Icn denotes that the mutual
information term are taken with respect to
 the distribution
(n)
(n)
induced by the code cn = f (n) , φ1 , φ2 .
A. Past Work
Information theoretic secrecy was introduced by Shannon
[1] who studied communication between a source and a
receiver in the presence of an eavesdropper. Wyner modeled
secret communication over noisy channels (also known as
physical layer security) when he introduced the degraded
wiretap channel (WTC) and derived its secrecy capacity [2].
Csiszár and Körner [3] extended Wyner’s result to a general
BC where the source also transmits a common message to both
users. The development of wireless communication, whose
inherent open nature makes it vulnerable to security attacks,
has inspired a growing interest in the fundamental limits of
secure communication.
Multiuser settings with secrecy were extensively treated in
the literature. Broadcast and interference channels with two
confidential messages were studied in [4], where inner and
outer bounds on the secrecy-capacity region of both problems were derived. The secrecy-capacity region for the semideterministic (SD) BC was established in [5]. The capacity
region of a SD-BC where only the message of the stochastic
user is kept secret from the deterministic user was derived
in [6]. The opposite case, i.e., when the message of the
deterministic user is confidential, was solved in [7]. Secret
cooperative communication was considered in [8], where the
authors derive inner and outer bounds on the rate-equivocation
region of the relay-BC (RBC) with one or two confidential
messages. Gaussian multiple-input multiple-output (MIMO)
BCs and WTCs were studied in [9]–[14], while [15]–[17]
focused on BCs with an eavesdropper as an external entity
from which all messages are kept secret.
Many of the aforementioned achievability results were derived by combining Marton’s coding for BCs [18], [19] and

2

Wyner’s wiretap coding [2], [3]. Marton coding usually uses
a joint typicality encoder (JTE) whose success is guaranteed
by invoking the Mutual Covering Lemma (MCL) [20, Lemma
8.1]. However, the JTE and the MCL have a cumbersome security analysis. Several past works avoid the complications by
performing the security analysis without conditioning on the
random codebook. This significantly simplifies the derivations,
but one would like to have security even if the codebooks are
known by the eavesdropper.
B. Model
We study a two-user BC over which a common message for
both users and a pair of private messages, each destined for
a different user, are transmitted. A limited amount of rate of
each private message may be leaked to the opposite receiver.
The leaked rate is quantified as the normalized mutual information between the message of interest and the channel output
sequence at the opposite user. Setting either leakage to zero or
infinity reduces the problem to the case where the associated
message is confidential or non-confidential, respectively. Thus,
our problem setting specializes to all four scenarios concerning
secrecy: when both, either or neither of the private messages
are secret. We derive inner and outer bounds on the leakagecapacity region of the BC. The inner bound relies on a leakageadaptive coding scheme that accounts for the codebook being
known to the eavesdropper.
The derived bounds are tight for SD-BCs, physically degraded (PD) BCs, and BCs with a degraded message set, thus
characterizing their leakage-capacity regions. Furthermore, we
derive a condition for identifying the privacy leakage threshold
above which the inner bound saturates. Various past results are
captured as special cases. By taking the leakage thresholds
to infinity, our inner bound recovers Marton’s inner bound
with a common message [21], which is tight for every BC
with a known capacity region. Making the leakage constraint
inactive in our outer bound recovers the UVW-outer bound
[22] or the New-Jersey outer bound [23]. These bounds are at
least as good as previously known bounds (see [24]–[26]). The
leakage-capacity region of the SD-BC reduces to each of the
regions in [5], [6], [21] and [27] by discarding the common
message and choosing the leakage constraints appropriately.
The capacity result also recovers the optimal regions for the
BC with confidential messages [3] and the BC with a degraded
message set (without secrecy) [28]. Finally, a Blackwell BC
(BW-BC) [29], [30] illustrates the results and visualizes the
transition of the leakage-capacity region from the capacity
region without secrecy to the secrecy-capacity regions for
different secrecy scenarios.
C. Organization
This paper is organized as follows. Section II establishes
notation and preliminary definitions. In Section III we discuss
the need for replacing the JTE with the likelihood encoder and
state a Uniform Approximation Lemma. Section IV describes
the BC with privacy leakage constraints, states inner and outer
bounds on the leakage-capacity region and characterize the
optimal regions of several special cases. In Section V we

discuss past results that are captured within our framework
and Section VI visualizes the results by means of a BW-BC
example. Finally, Section VIII summarizes the main achievements and insights of this work.
II. N OTATIONS

AND

P RELIMINARY D EFINITIONS

A. Notations
We use the following notations. As customary N is the set of
natural numbers (which does not include 0), while R denotes
the reals. We further define R+ = {x ∈ R|x ≥ 0} and
R++ = R \ {0}. Given two real
 numbers a, b, we denote
by [a : b] the set of integers n ∈ N ⌈a⌉ ≤ n ≤ ⌊b⌋ .
Calligraphic letters such are X denote sets, the complement
of X is denoted by X c , while |X | stands for its cardinality.
X n denoted the n-fold Cartesian product of X . An element
of X n is denoted by xn = (x1 , x2 , . . . , xn ); whenever the
dimension n is clear from the context, vectors (or sequences)
are denoted by boldface letters, e.g., x. A substring of x ∈ X n
is denoted by xji = (xi , xi+1 , . . . , xj ), for 1 ≤ i ≤ j ≤ n;
when i = 1, the subscript is omitted. We also define xn\i =
(x1 , . . . , xi−1 , xi+1 , . . . , xn ).
Let X , F , P be a probability space, where X is the sample
space, F is the σ-algebra and Pis the probability measure.
Random variables over X , F , P are denoted by uppercase
letters, e.g., X, with conventions for random vectors similar
to those for deterministic vectors. The probability of an event
A ∈ F is denoted by P(A), while P(A B ) denotes the
conditional probability of A given Bn . We use 1A to denote
the indicator function of A. The set of all probability mass
functions (PMFs) on a finite set X is denoted by P(X ), i.e.,
)
(
X
P (x) = 1] .
(1)
P(X ) = P : X → [0, 1]
x∈X

PMFs are denoted by the uppercase letters such as P or Q,
with a subscript that identifies the random variable and its
possible conditioning.
For example, for a discrete probability

space X , F , P and two correlated random variables X and
Y over that space, we use PX , PX,Y and PX|Y to denote,
respectively, the marginal PMF of X, the joint PMF of (X, Y )
and the conditional PMF of X given Y . In particular, PX|Y
represents the stochastic matrix whose
 elements are given
by PX|Y (x|y) = P X = x|Y = y . Expressions such as
PX,Y = PX PY |X are to be understood as PX,Y (x, y) =
PX (x)PY |X (y|x), for all (x, y) ∈ X × Y. Accordingly, when
three random variables X, Y and Z satisfy PX|Y,Z = PX|Y ,
they form a Markov chain, which we denote by X − Y − Z.
We omit subscripts if the arguments of a PMF are lowercase
versions of the random variables. The support of a PMF P
and the expectation of
 arandom variable X ∼ P are denoted
by supp(P ) and EP X , respectively; when the distribution
of Xis clear from the context we write its expectation simply
as E X . Similarly, HP and IP denote entropy and mutual
information that are calculated with respect to an underlying
PMF P .
For a discrete measurable space (X , F ), a PMF Q ∈
P(X ) gives rise to a probability measure on (XP
, F ), which
we denote by PQ ; accordingly, PQ A) =
x∈A Q(x),

3

for every A ∈ F . For a random vector X n , if the entries of X n are drawn in an independent and identically
distributed (i.i.d.) manner according
Qn to PX , then for every
x ∈ X n we have PX n (x) = i=1 PX (xi ) and we write
n
n
n
(x). Similarly,
PX n (x) = PX
Qnif for every (x, y) ∈ X × Y
we have PY n |X n (y|x) = i=1 PY |X (yi |xi ), then we write
PY n |X n (y|x) = PYn|X (y|x). The conditional product PMF
PYn|X given a specific sequence x ∈ X n is denoted by
PYn|X=x .
Let X and Y be finite sets. The empirical PMF νx of a
sequence x ∈ X n is
N (x|x)
(2)
n
Pn
where N (x|x) = i=1 1{xi =x} . We use Tδn (PX ) to denote
the set of letter-typical sequences of length n with respect to
the PMF PX ∈ P(X ) and the positive number δ [31, Chapter
3], i.e., we have
n
o
Tδn (PX ) = x ∈ X n νx (x)−PX (x) ≤ δPX (x), ∀x ∈ X .
(3)
Furthermore, for a joint PMF PX,Y ∈ P(X × Y) a δ > 0 and
a fixed sequence y ∈ Y n , we define
n
o
Tδn (PX,Y |y) = x ∈ X n (x, y) ∈ Tδn (PX,Y ) .
(4)
νx (x) ,

Another notion used throughout this work is information
density. Let (X ×Y, F , PX,Y ) be a probability space, where X
and Y are arbitrary sets. The information density iP : X ×Y →
R++ of PX,Y is given by
iP (x; y) = log

dPX,Y
(x, y)
dPX PY

(5a)

dP
is the Radon-Nikodym derivative of P with respect
where dQ
to Q and PX and PY are the marginal probability measures
induced by PX,Y on X and Y, respectively. If X and Y are
discrete and PX,Y ∈ P(X × Y), then (5a) simplifies as

iP (x; y) = log

PX,Y (x, y)
.
PX (x)PY (y)

Definition 2 (Fidelity): Let (X , F ) be a measurable space
and P and Q be two probability measures on F , such that
P ≪ Q, i.e., P is absolutely continuous with respect to Q.
The fidelity between P and Q is
s
dP
.
(7a)
F(P, Q) = EQ
dQ
If the sample space X is countable and P, Q ∈ P(X ), then
(7a) reduces to
Xp
P (x)Q(x).
(7b)
F(P, Q) =
x∈X

Fidelity satisfies F(P, Q) ∈ [0, 1] and is related to the TV as
follows [32, Lemma 1].
Lemma 1 (Fidelity and Total Variation): For any two probability measures P and Q over the same measurable space
(X , F ), we have
p
1 − F(P, Q) ≤ ||P − Q||TV ≤ 1 − F 2 (P, Q).
(8)

Via Jensen’s inequality, the right-most inequality in (8)
extends to the expected values of the fidelity and the TV
between two conditional distributions as follows [32, Lemma
2], [33, Lemma 7].
Lemma 2 (Extension to Expected Values): Let (Ω, G, µ) be a
probability space, (X , F ) be a measurable space and P and Q
be two transition probability kernels from (Ω, G) to (X , F ).1
We have
r

2
Eµ P − Q TV ≤ 1 − Eµ F P, Q
.
(9)


By virtue of Lemma 2, if Pn n∈N and Qn n∈N are two
sequences of Markov kernels2 then

(10a)
Eµn F Pn , Qn −−−−→ 1
n→∞

implies

Eµn Pn − Qn
(5b)

Whenever the underlying distribution is clear from the context,
we drop the subscript P from iP .

−−−−→ 0.

TV n→∞

(10b)

III. U NIFORM D ISTRIBUTION A PPROXIMATION L EMMA
A. Marton Coding

B. Measures of Distribution Proximity
We measure the proximity between two distributions by
using total variation (TV).
Definition 1 (Total Variation): Let (X , F ) be a measurable
space and P and Q be two probability measures on F . The
total variation between P and Q is
||P − Q||TV = sup P (A) − Q(A) .

(6a)

A∈F

If the sample space X is countable and P, Q ∈ P(X ), then
(6a) reduces to
1X
P (x) − Q(x) .
(6b)
||P − Q||TV =
2
x∈X

We also consider the fidelity between two distributions.

A Marton code involves two independent codebooks from
which a pair of codewords is usually selected by means of a
JTE [19]. A standard tool for the encoding error probability
analysis is the MCL [20, Lemma 8.1]. While the JTE and
the MCL are convenient for analysing reliability, security
(equivocation or leakage) analysis seems cumbersome.
Several past works employ Marton coding without conditioning the security analysis on the random codebook. Attempting to repeat the steps from these derivations while
1 A transition probability kernel between two measurable spaces (Ω, G) and
(X , F ) is a mapping κ : Ω × F → [0, 1] such that: (i) ω 7→ κ(ω, A) is a
G-measurable function for every A ∈ F ; (ii) A 7→ κ(ω, A) is a probability
measure on (X , F ) for every ω ∈ Ω.
2 The formal definition is in accordance with Lemma 2 where we re
place
(Ω, G, µ), (X , F ), P and Q with the sequences (Ωn , Gn , µn ) n ,

(Xn , Fn ) n , {Pn }n and {Qn }n , respectively.

4

conditioning the equivocation on the codebook turns out
to be problematic. The principal difficulty is showing that
the marginal distribution of an index chosen by the JTE is
approximately uniform.3 More precisely, let the output index
pair of the encoder be (I, J); the corresponding alphabets
are In and Jn . Several existing proofs rely on the following
relations holding true:
H(I|Cn ) ≥ log |In | − nδn

H(J|Cn ) ≥ log |Jn | − nδn ,
(11)
where Cn is the random codebook4 and limn→∞ δn = 0. Proving these inequalities while using the JTE is cumbersome. A
potential proof would rely on analysing the output distribution
of the JTE. However, the structure of this distribution quickly
makes the analysis intractable.
;

B. Likelihood Encoder
Our coding scheme also uses a Marton code. We circumvent
the problems with the JTE by replacing it with a likelihood
encoder for Marton codebooks [7], [34], [35]. A similar
encoding rule was used in [32], [36] under the name stochastic
mutual information encoder. This encoder induces a probability distribution over the possible pairs of indices (or, equivalently, codewords). Given two independently generated bins,
the probability of each codeword pair is proportional to the
ratio of their joint probability (under the coding distribution)
to the product of the marginal distributions. Namely, if ui and
vj are the i-th and j-th codewords for each bin, respectively,
and QU,V is the coding distribution (the codebooks are i.i.d.
samples of its marginals QU and QV ), then the encoder
chooses (i, j) with probability proportional to
QnU,V (ui , vj )
.
QnU (ui )QnV (vj )

Nonetheless, as can be seen in the proof of Lemma 3 (Section
VII-A), the derivation is valid for random variables with
general alphabets.
Fix Q
 W,U,V ∈P(W × U × V) and for every n ∈
 N define

In , 1 : 2nS1 , Jn , 1 : 2nS2 and Kn = 1 : 2nT ,
where S1 , S2 , T ∈ R+ . Let W ∼ QnW and fix w ∈ W n with

(n)
QnW (w) > 0. Let BU (w) , Ui (w) i∈In be a random
codebook that comprises |In | vectors of length n that are i.i.d.
according to QnU|W =w . Furthermore, for every k ∈ Kn let

(n)
BV (k, w) , Vj,k (w) j∈Jn be a random codebook with
i.i.d. codewords according to QnV |W =w . The codebooks in the
o
n
(n)
(n)
set BV (w) , BV (k, w)
are conditionally indepenk∈Kn
dent of one another given W = w. Forn any w ∈ W n with
o
(n)
(n)
QnW (w) > 0 we also define Bn (w) , BU (w), BV (w)

and finally we set Bn , W, Bn (W) .
(n)

λ(Bn )
= QnW (w)

C. Setup and Statement of the Lemma
For notational convenience we formulate the setup and state
the result in terms of random variables with finite alphabets.

Y

QnU|W ui (w) w

i∈In

(12)

Thus, the further the joint distribution is from the product of
the marginals the more favorable the corresponding pair of
codewords is.
Replacing the JTE with the likelihood encoder comes at no
cost in reliability. This is because, like the JTE, if the sum
of the bin rates is greater than I(U ; V ), then the likelihood
encoder chooses jointly typical codeword pairs with high
probability [32, Theorem 3]. The leakage analysis, on the
other hand, tremendously simplifies. This allows to derive
the achievability result for the BC with privacy leakage
constraints. Key to the leakage analysis is that the marginal
distribution of the indices at the encoder’s output are indeed
approximately uniform. This relation is formulated in the next
subsection and the proof is provided in Section VII-A.

(n)

A realization of BU (w) or BV (k, w), k ∈ Kn ,

(n)
,
ui (w) i∈In and
is denoted by BU (w)

(n)
BV (k, w) , vj,k (w) j∈Jn , respectively. In accordance
o
n
(n)
(n)
to the above, we also set BV (w) , BV (k, w)
=
k∈K
on
n

(n)
(n)
vj,k (w) (j,k)∈Jn ×Kn , Bn (w) , BU (w), BV (w) and

Bn , w, Bn (w) . Letting Bn denote the collection of all
possible realization of Bn , the above construction induces a
PMF λ ∈ P(Bn ) on Bn that is given by
 Y


QnV |W vj,k (w) w .

(j,k)∈Jn ×Kn

(13)

Now, let K be a random variable independent of Bn and
uniformly distributed over Kn . For each Bn ∈ Bn and k ∈
Kn , the index pair (i, j) ∈ In × Jn is drawn according to

iQn ui (w);vj,k (w) w
2
(B ,k)
 , (14)
PI,Jn (i, j) =
P
2iQn uℓ̄ (w);vj̄,k (w) w
(ℓ̄,j̄)∈In ×Jn

where

iQn (u; v|w) = log

QnU,V |W (u, v|w)
QnU|W (u|w)QnV |W (v|w)

.

(15)

(B ,k)

PI,Jn describes our likelihood encoder. Finally, on account
of (13)-(14) we set
1
(B ,k)
PBn ,K,I,J (Bn , k, i, j) , λ(Bn )
P n (i, j),
(16)
|Kn | I,J
which induces a probability measure PP .

3 Without

the conditioning, uniformity follows by symmetry.
conditioning on Cn is not present in many existing works. Instead, the
relations (11) were replaced with their unconditioned versions H(I) = log |I|
and H(J) = log |J |. Although these relations are true, an unconditioned
analysis does not imply achievability when the codebooks are known to the
eavesdropper.
4 The

The following lemma specifies sufficient conditions on the
sizes of the index sets for approximating the induced marginal
distribution of I with a uniform distribution over In . To state
(U)
the result let pIn be the uniform distribution over In and note

5



(n)
(n)
for the WY1 ,Y2 |X BC with
A code cn = f (n) , φ1 , φ2

that for every Bn ∈ Bn
X
1
PI|Bn (i|Bn ) =
|Kn |

(j,k)
∈Jn ×Kn


2iQn ui (w);vj,k (w) w
P
2iQn uℓ̄ (w);vj̄,k (w)

(ℓ̄,j̄)
∈In ×Jn

w

.

(17)
Lemma 3 (Uniform Approximation Lemma): For any
QW,U,V ∈ P(W × U × V) if

(18a)
S2 + min S1 , T > IQW,U,V (U ; V |W )
then

(U)

EBn PI|Bn − pIn

−−−−→ 0.

TV n→∞

(18b)

The Lemma is proven in Section VII-A via an analysis of the
expected fidelity between the induced marginal distribution of
I and the uniform distribution. Inspired by ideas from [32], we
employ the Cauchy-Schwarz inequality and Jensen’s inequality
to show that the expected fidelity converges to 1 with the
blocklengh. The result of the lemma then follows by (10).

privacy leakage constraints induces a PMF P (cn ) on M0 ×
M1 × M2 × X n × Y1n × Y2n × M̂01 × M̂02 , that is given by



(2)
(1)
P (cn ) m0 , m1 , m2 , x, y1 , y2 , m̂0 , m̂1 , m̂0 , m̂2
Y
1
=
f (n) (x|m0 , m1 , m2 )WYn1 ,Y2 |X (y1 , y2 |x)
(n)
j=0,1,2 Mj
 (j)
× 1T
.
(n)
j=1,2

(m̂0 ,mj )=φj

(yj )

(19)

The induced PMF gives rise to the probability measure PP (cn ) ,
which we abbreviate by Pcn . Similarly, we use the shorthand
Icn instead of IP (cn ) to denote a mutual information expression taken with respect to P (cn ) .
Definition 4 (Average Error Probability): The average error
probability for an (n, R0 , R1 , R2 ) code cn is


o
[ n

(j)
Pe (cn ) , Pcn 
M̂0 , M̂j 6= (M0 , Mj )  (20)
j=1,2

IV. B ROADCAST C HANNELS WITH P RIVACY L EAKAGE
C ONSTRAINTS
A. Problem Setting

The X , Y1 , Y2 , WY1 ,Y2 |X : X → P(Y1 × Y2 ) BC with
privacy leakage constraints is illustrated in Fig. 1. The channel
has one sender and two receivers. The sender randomly
chooses a triple (m0 , m
uniformly
and inde 
 indices

 1 , m2 ) of
pendently from the set 1 : 2nR0 × 1 : 2nR1 × 1 : 2nR2 and
maps them to a sequence x ∈ X n , which is the channel input
(the mapping may be random). The sequence x is transmitted
over a BC with transition probability WY1 ,Y2 |X . The output
sequence yj ∈ Yjn , where j = 1, 2, is received by decoder

(j)
j. Decoder j produces a pair of estimates m̂0 , m̂j of
(m0 , mj ).
Remark 1 (Specific Classes of BCs): We sometimes specialize to the following classes of BCs:
•

•

•

Semi-Deterministic BCs: A BC is SD if its channel transition matrix factors as WY1 ,Y2 |X = 1{Y1 =y1 (X)} WY2 |X ,
where y1 : X → Y1 and WY2 |X : X → P(Y2 ).
Physically-Degraded BCs: A BC is PD if its channel
transition matrix factors as WY1 ,Y2 |X = WY1 |X WY2 |Y1 ,
where WY1 |X : X → P(Y1 ) and WY2 |Y1 : Y1 → P(Y2 ).
Deterministic BCs: A BC is deterministic if its
channel transition matrix factors as WY1 ,Y2 |X =
1{Y1 =y1 (X)}∩{Y2 =y2 (X)} , where yj : X → Yj , for
j = 1, 2.

Definition 3 (Code): An (n, R0 , R1 , R2 ) code cn for the BC
with leakage constraints has:


(n)
1) Three message sets Mj , 1 : 2nRj , j = 0, 1, 2.
(n)
(n)
(n)
2) A stochastic encoder f (n) : M0 × M1 × M2 →
n
P(X ).
(n)
(n)
3) Two decoding functions, φj : Yjn → M̂0j , where
(n)
(n)
(n)
M̂0j , M0 × Mj , for j = 1, 2.


(j)
(n)
where M̂0 , M̂j = φj (Yj ), for j = 1, 2.
Definition 5 (Information Leakage Rate): The information
leakage rate of M1 to receiver 2 under an (n, R0 , R1 , R2 ) code
cn is
1
(21a)
ℓ1 (cn ) , Icn (M1 ; Y2 ).
n
Similarly, the information leakage rate of M2 to receiver 1
under cn is
1
ℓ2 (cn ) , Icn (M2 ; Y1 ).
(21b)
n
Definition 6 (Achievable Rates): Let (L1 , L2 ) ∈ R2+ . A rate
triple (R0 , R1 , R2 ) ∈ R3+ is (L1 , L2 )-achievable if for any ǫ >
0 there exists a sufficiently large n ∈ N and an (n, R0 , R1 , R2 )
code cn such that
Pe (cn ) ≤ ǫ
ℓ1 (cn ) ≤ L1 + ǫ

(22a)
(22b)

ℓ2 (cn ) ≤ L2 + ǫ.

(22c)

Definition 7 (Leakage-Capacity Region): The (L1 , L2 )leakage-capacity region C(L1 , L2 ) is the closure of the set
of the (L1 , L2 )-achievable rates.
Remark 2 (Inactive Leakage Constraints): Setting Lj = Rj ,
for j = 1, 2, makes (22b)-(22c) inactive and reduces the
BC with privacy leakage constraints to the classic BC with
a common message. This is a simple consequence of the nonnegativity of entropy, which implies that Icn (M1 ; Y2 ) ≤ nR1
and Icn (M2 ; Y1 ) ≤ nR2 always hold. To simplify notation
we write Lj → ∞, j = 1, 2 to refer to leakage threshold
values under which (22b)-(22c) are satisfied by default.
B. Leakage-Capacity Results
This section states inner and outer bounds on the (L1 , L2 )leakage-capacity region C(L1 , L2 ) of a BC. The bounds match
for SD-BCs, BCs with a degraded message set and PD-BCs,

6

which characterizes the leakage-capacity regions for these
three cases. We start with the inner bound.
In the following, the transition probability WY1 ,Y2 |X describing the BC stays fixed unless stated otherwise. When
specifying to particular instances of BCs (see Remark 1), we
explicitly mention the corresponding structure of WY1 ,Y2 |X .
Theorem 1 (Inner Bound): Let RI (L1 , L2 ) be the closure of
the union of rate triples (R0 , R1 , R2 ) ∈ R3+ satisfying:
n
o
R0 ≤ min I(U0 ; Y1 ), I(U0 ; Y2 )
(23a)
R1 ≤ I(U1 ; Y1 |U0 )−I(U1 ; U2 , Y2 |U0 )+L1
(23b)
n
o
R0 + R1 ≤ I(U1 ; Y1 |U0 )+min I(U0 ; Y1 ),I(U0 ; Y2 ) (23c)

R2 ≤ I(U2 ; Y2 |U0 )−I(U2 ; U1 , Y1 |U0 )+L2
(23d)
n
o
R0 + R2 ≤ I(U2 ; Y2 |U0 )+min I(U0 ; Y1 ),I(U0 ; Y2 ) (23e)
X
Rj ≤ I(U1 ; Y1 |U0 ) + I(Un2 ; Y2 |U0 )
o (23f)
j=0,1,2
− I(U1 ; U2 |U0 ) + min I(U0 ;Y1 ), I(U0 ;Y2 )

where the union is over all PMFs QU0 ,U1 ,U2 ,X ∈
P(U0 × U1 × U2 × X ), each inducing a joint distribution
QU0 ,U1 ,U2 ,X WY1 ,Y2 |X . The following inclusion holds:
RI (L1 , L2 ) ⊆ C(L1 , L2 ).

(24)

The proof of Theorem 1 is given in Section VII-B and uses a
leakage-adaptive Marton-like code construction. Rate-splitting
is first used to decompose each private message Mj , j = 1, 2,
into a public part M0j and a private part Mjj . A Marton
codebook with an extra layer of bins is then constructed
while treating (M0 , M10 , M20 ) as a public message and Mjj ,
for j = 1, 2, as private message j. The double-binning of
the private messages permits joint encoding (outer layer) and
controlling the total rate leakage to the other user (inner layer).
In contrast to the classic Marton coding scheme [19] that
employes a JTE, we execute joint encoding by means of the
likelihood encoder from (14). Doing so doesn’t affect the
reliability analysis (as the likelihood encoder chooses jointly
typical pairs of codewords with high probability), but it is of
consequence for analysing the leakage rate.
The leakage analysis takes into account the rate leaked due
to the decoding of the public message by both users. Also,
additional leakage occurs due to the joint encoding process,
which introduces correlation between the private message
codewords. We account for the latter by relating the bin sizes
in the inner and outer coding layers to the rate of the public
parts M10 and M20 . The leakage analysis relies heavily on the
structure of the likelihood encoder that lets us establish several
crucial properties of our random coding experiment. The main
challenge is showing that the induced marginal distribution
describing the choice of the private message codewords is
approximately uniform. This follows by virtue of the Uniform
Approximation Lemma (Lemma 3).
Remark 3 (Relation to Marton’s Region): In [21, Theorem
1] Gelfand and Pinsker generalized Marton’s inner bound [18]
to include a common message. An alternative form of Gelfand
and Pinsker’s inner bound was given in [37, Theorem 5] (see
also [38]). This region is the best known inner bound on the

capacity region of the BC with a common message. RI (∞, ∞)
recovers the Gelfand-Pinsker region since (23b) and (23d) are
redundant. A full discussion of the special cases of RI (L1 , L2 )
is given in Section V-D.
The following corollary states a sufficient condition on the
leakage thresholds L1 and L2 to become inactive in the bounds
from (23) when R0 = 0 (i.e., no common message is present).
To state the result, let R̃I (L1 , L2 , QU0 ,U1 ,U2 ,X ) denote the set
of rate pairs (R1 , R2 ) ∈ R2+ satisfying (23) with R0 = 0 when
the mutual information terms are calculated with respect to
QU0 ,U1 ,U2 ,X WY1 ,Y2 |X . Accordingly,
[
R̃I (L1 , L2 ) ,
R̃I (L1 , L2 , QU0 ,U1 ,U2 ,X ) (25)
QU0 ,U1 ,U2 ,X

is the region obtained by setting R0 = 0 in RI (L1 , L2 ).
Corollary 2 (Inactive Leakage Constraints): Let
QU0 ,U1 ,U2 ,X ∈ P(U0 × U1 × U2 × X ). For j = 1, 2
define
Lj ⋆ (QU0 ,U1 ,U2 ,X )
n
o
= min I(U0 ; Y1 ), I(U0 ; Y2 ) + I(Uj ; Uj̄ , Yj̄ |U0 ), (26)

where j̄ = j + (−1)j+1 . The following implications hold:

1) If
L1
≥
L⋆1 (QU0 ,U1 ,U2 ,X )
then
R̃I (L1 , L2 , QU0 ,U1 ,U2 ,X ) = R̃I (∞, L2 , QU0 ,U1 ,U2 ,X ).
2) If
L2
≥
L⋆2 (QU0 ,U1 ,U2 ,X )
then
R̃I (L1 , L2 , QU0 ,U1 ,U2 ,X ) = R̃I (L1 , ∞, QU0 ,U1 ,U2 ,X ).
3) If Lj ≥ L⋆j (QU0 ,U1 ,U2 ,X ), for j = 1, 2, then
R̃I (L1 , L2 , QU0 ,U1 ,U2 ,X ) = R̃I (∞, ∞, QU0 ,U1 ,U2 ,X ).
For the proof of Corollary 2 see Section VII-C. According
to the above, if any of the leakage thresholds Lj , j = 1, 2
surpasses the critical value from (26), then the corresponding
inner bound remains unchanged if Lj is further increased, and
is therefore equivalent to the region where Lj → ∞.
Remark 4 (Application of Corollary 2): Corollary 2 specifies
a condition for L1 and/or L2 being inactive for each input
probability. Getting a condition for the inactivity of the thresholds with respect to the entire region R̃I (L1 , L2 ) from (25) is
a more challenging task. Identifying such a condition involves
identifying which input distributions achieve the boundary of
R̃I (L1 , L2 ). In some communication scenarios this is possible,
e.g., for the MIMO Gaussian BC with or without secrecy requirements the boundary achieving distributions are Gaussian
vectors [39]–[43]. However, the structure of the optimizing
distribution is unknown in general.
The merit of Corollary 2 becomes clear when explicitly
calculating R̃I (L1 , L2 ). One can then identify the optimizing
distribution, e.g., by means of an analytical characterization or
via an exhaustive search. In turn, one can calculate the maximum of L⋆j (QU0 ,U1 ,U2 ,X ) over those distributions. Denoting
by L⋆j this maximal value, if Lj < L⋆j then increasing Lj will
further shrink the region. If, on the other hand, Lj ≥ L⋆j , then
the region remains unchanged even if Lj grows. This idea is
demonstrated in Section VI where we calculate the (L1 , L2 )leakage-capacity region of the Blackwell BC.
Next, we state an outer bound on C(L1 , L2 ). A proof of
Theorem 3 is given in Section VII-D.

7

Theorem 3 (Outer Bound): Let RO (L1 , L2 ) be the closure
of the union of rate triples (R0 , R1 , R2 ) ∈ R3+ satisfying:
n
o
R0 ≤ min I(W ; Y1 ), I(W ; Y2 )
(27a)
R1 ≤ I(U ; Y1 |W, V ) − I(U ; Y2 |W, V ) + L1

(27b)

R1 ≤ I(U ; Y1 |W ) − I(U ; Y2 |W ) + L1
(27c)
n
o
R0 + R1 ≤ I(U ; Y1 |W ) + min I(W ; Y1 ),I(W ; Y2 ) (27d)

R2 ≤ I(V ; Y2 |W, U ) − I(V ; Y1 |W, U ) + L2
R2 ≤ I(V ; Y2 |W ) − I(V ; Y1 |W ) + L2
n
o
R0 + R2 ≤ I(V ; Y2 |W ) + min I(W ; Y1 ),I(W ; Y2 )
X
Rj ≤ I(U ; Y1 |W, V ) + n
I(V ; Y2 |W )
o
j=0,1,2
+ min I(W ; Y1 ), I(W ; Y2 )
X
Rj ≤ I(U ; Y1 |W ) + I(V
n ; Y2 |W, U )
o
j=0,1,2
+ min I(W ; Y1 ), I(W ; Y2 )

(27e)
(27f)

(27g)
(27h)

(27i)

where the union is over all PMFs QW,U,V QX|U,V ∈
P(W × U × V × X ), each inducing a joint distribution
QW,U,V QX|U,V WY1 ,Y2 |X . RO (L1 , L2 ) is convex and the following inclusion holds:
C(L1 , L2 ) ⊆ RO (L1 , L2 ).

(28)

Remark 5 (Relation to UVW-Outer Bound): The best known
outer bounds on the capacity region of a BC with a common
message are the UVW-outer bound [22, Bound 2] and the
New-Jersey outer bound [23] which are equivalent. The region
RO (∞, ∞) recovers the UVW-outer bound since (27b)-(27c)
and (27e)-(27f) are redundant.
The inner and outer bounds in Theorems 1 and 3 are tight
for SD-BCs and give rise to the following theorem.
Theorem 4 (Leakage-Capacity - SD-BC): The (L1 , L2 )leakage-capacity region CSD (L1 , L2 ) of a SD-BC
1{Y1 =y1 (X)} WY2 |X is the closure of the union of rate
triples (R0 , R1 , R2 ) ∈ R3+ satisfying:
n
o
R0 ≤ min I(W ; Y1 ), I(W ; Y2 )
(29a)
R1 ≤ H(Y1 |W, V, Y2 ) + L1
(29b)
n
o
R0 + R1 ≤ H(Y1 |W ) + min I(W ; Y1 ),I(W ; Y2 )
(29c)

R2 ≤ I(V ; Y2 |W ) − I(V ; Y1 |W ) + L2
(29d)
n
o
R0 + R2 ≤ I(V ; Y2 |W ) + min I(W ; Y1 ),I(W ; Y2 ) (29e)
X
≤ H(Y1 |W, V ) + I(V
n ; Y2 |W )
o (29f)
j=0,1,2
+ min I(W ; Y1 ), I(W ; Y2 )

where the union is over all PMFs QW,V,X ∈ P(W × V × X ),
each inducing a joint distribution QW,V,X 1{Y1 =y1 (X)} WY2 |X .
Furthermore, CSD (L1 , L2 ) is convex.
The direct part of Theorem 4 follows from Theorem 1 by
taking U0 = W , U1 = Y1 and U2 = V , while Theorem 3 is
used for the converse. See Section VII-E for the details.
Remark 6 (SD-BC Result - Special Cases): All four cases
of the SD-BC concerning secrecy (i.e., when neither, either
or both messages are secret) are solved and their solutions are

retrieved from CSD (L1 , L2 ) by inserting the appropriate values
of Lj , j = 1, 2. This property of CSD (L1 , L2 ) is discussed in
Section V-D.
The inner and outer bounds in Theorems 1 and 3 also match
when the message set is degraded, i.e., when M2 = 0 and there
is only one private message.
Theorem 5 (Leakage-Capacity - Degraded Message Set):
The L1 -leakage-capacity region CDM (L1 ) of a BC with a degraded message set (M2 = 0) and a privacy leakage constraint
is the closure of the union of rate pairs (R0 , R1 ) ∈ R2+
satisfying:
n
o
R0 ≤ min I(W ; Y1 ), I(W ; Y2 )
(30a)
R1 ≤ I(U ; Y1 |W ) − I(U ; Y2 |W ) + L1

R0 + R1 ≤ I(U ; Y1 |W ) + min I(W ; Y1 ),I(W ; Y2 )

(30b)
(30c)

where the union is over all PMFs QW,U QX|U ∈ P(W × U ×
X ), each inducing a joint distribution QW,U QX|U WY1 ,Y2 |X .
Furthermore, CDM (L1 ) is convex.
Proof: The direct part follows by setting R2 = 0, U0 =
W , U1 = U and U2 = 0 in Theorem 1. For the converse
we show that RO (L1 , L2 ) ⊆ CDM (L1 ). Clearly, (30a), (30b)
and (30c) coincide with (27a), (27c) and (27d), respectively.
Dropping the rest of the inequalities from (27) completes the
proof.
Remark 7 (Degraded Message Set Result - Special Cases):
The BC with a degraded message set and a privacy leakage
constraint captures the BC with confidential messages [3] and
the BC with a degraded message set [28]. The former is
obtained by taking L1 = 0, while L1 → ∞ recovers the
latter. Setting L1 = 0 or L1 → ∞ into CDM (L1 ) recovers the
capacity regions of these special cases (see Section V-E for
more details).
We next characterize the leakage-capacity region of a PDBC WY1 |X WY2 |Y1 with privacy leakage constraints and without a common message (M0 = 0). Since X − Y1 − Y2 forms a
Markov chain, it is impossible to achieve non-trivial leakage
constraints on the message M2 . Accordingly, the leakagecapacity region of the PD-BC (where X − Y1 − Y2 ) is defined
only through L1 .
Corollary 6 (Leakage-Capacity - PD-BC): The L1 -leakagecapacity region CPD (L1 ) of a PD-BC WY1 |X WY2 |Y1 without
a common message is the closure of the union over the
same domain as CDM (L1 ) of rate pairs (R1 , R2 ) ∈ R2+
satisfying
(30), while recasting R0 as R2 and noting that

min I(W ; Y1 ), I(W ; Y2 ) = I(W ; Y2 ).
The proof of Corollary 6 is similar to that of Theorem 5
and is omitted.
Remark 8 (Cardinality Bounds): Cardinality bounds for the
auxiliary random variables in Theorems 1, 3, 4 and 5 can be
derived using the perturbation method [20, Appendix C] or
techniques such as in [22] and [44]. The computability of the
derived regions is not in the scope of this work.
V. S PECIAL C ASES
A. The Gelfand-Pinsker Inner Bound
Theorem 1 generalizes the Gelfand-Pinsker region for the
BC with a common message [21, Theorem 1] to the case

8

with privacy leakage constraints. In other words, RI (∞, ∞)
recovers the result from [21], which is tight for every BC
(without secrecy) whose capacity region is known.
B. UVW-Outer Bound
The New-Jersey outer bound was derived in [23] and shown
to be at least as good as the previously known bounds. A
simpler version of this outer bound was established in [22] and
was named the UVW-outer bound. The UVW-outer bound is
given by RO (∞, ∞).
C. Liu-Marić-Spasojević-Yates Inner Bound
In [4] an inner bound on the secrecy-capacity region of a
BC WY1 ,Y2 |X with two confidential messages (each destined
for one of the receivers and kept secret from the other) was
characterized as the set of rate pairs (R1 , R2 ) ∈ R2+ satisfying:
R1 ≤ I(U1 ; Y1 |U0 ) − I(U1 ; U2 , Y2 |U0 )
R2 ≤ I(U2 ; Y2 |U0 ) − I(U2 ; U1 , Y1 |U0 )

(31a)
(31b)

where the union is over all PMFs QU0 ,U1 ,U2 QX|U1 ,U2 ∈
P(U0 × U1 × U2 × X ), each inducing a joint distribution
QU0 ,U1 ,U2 QX|U1 ,U2 WY1 ,Y2 |X . This inner bound is tight for
SD-BCs [5] and MIMO Gaussian BCs [11]. Setting R0 = 0
in RI (0, 0) recovers (31).
D. SD-BCs with and without Secrecy
The SD-BC 1{Y1 =y1 (X)} WY2 |X without a common message, i.e., when R0 = 0, is solved when both, either or
neither private messages are secret (see [5], [6], [27] and [21],
respectively). Setting Lj = 0, for j = 1, 2, reduces the SD-BC
with privacy leakage constraints to the problem where Mj is
secret. Taking Lj → ∞ results in a SD-BC without a leakage
constraint on Mj . We use Theorem 4 to obtain the leakagecapacity region of the SD-BC without a common message.
Corollary 7 (Leakage-Capacity - SD-BC without M0 ): The
0
(L1 , L2 )-leakage-capacity region CSD
(L1 , L2 ) of a SD-BC
1{Y1 =y1 (X)} WY2 |X without a common message is the closure
of the union over the domain stated in Theorem 4 of rate pairs
(R1 , R2 ) ∈ R2+ satisfying:
R1 ≤ H(Y1 |W, V, Y2 ) + L1
(32a)
n
o
R1 ≤ H(Y1 |W ) + min I(W ; Y1 ), I(W ; Y2 ) (32b)

R2 ≤ I(V ; Y2 |W ) − I(V ; Y1 |W ) + L2
(32c)
n
o
R2 ≤ I(V ; Y2 |W ) + min I(W ; Y1 ),I(W ; Y2 ) (32d)

R1 + R2 ≤ H(Y1 |W, V ) + I(V
n ; Y2 |W )

o (32e)
+ min I(W ; Y1 ), I(W ; Y2 ) .

1) Neither Message is Secret: If L1 , L2 → ∞, the SD-BC
with privacy leakage constraints reduces to the classic case
0
(∞, ∞) by choosing
without secrecy [21]. We recover CSD
W = 0 so that (32) becomes
R1 ≤ H(Y1 )

(33a)

R2 ≤ I(V ; Y2 )

(33b)

R1 + R2 ≤ H(Y1 |V ) + I(V ; Y2 )

(33c)

This agrees with the discussion in Section V-A since Marton’s
inner bound is tight for SD-BCs.
2) Only M1 is Secret: The SD-BC where M1 is a secret
is obtained by taking L1 = 0 and L2 → ∞. The secrecycapacity region was derived in [27, Corollary 4] and is the
closure of the union over the same domain as (33) of rate
pairs (R1 , R2 ) ∈ R2+ satisfying:
R1 ≤ H(Y1 |V, Y2 )

(34a)

R2 ≤ I(V ; Y2 ).

(34b)

0
To see that CSD
(0, ∞) and (34) match, first note that when
L1 = 0, (32b) is redundant due to (32a). The sum rate bound
(32e) also becomes inactive as it is implied by adding (32a)
0
and (32d). Setting W = 0 in CSD
(0, ∞) now recovers (34).
Remark 9 (Relation to Optimal Coding Scheme): The optimal code for the SD-BC with a secret message M1 employs no
public message and relies on double-binning the codebook of
M1 , while M2 is transmitted at maximal rate and no binning
of its codebook is performed. The optimality of W = 0 in
0
CSD
(0, ∞) corresponds to the absence of the public messages.
Furthermore, referring to the bounds in Section VII-B, inserting L1 = 0 and L2 → ∞ into our code construction
results in (68a) and (87b) becoming inactive since (86b) is
the dominant constraint. Consequently, the redundancy used
for correlating the transmission and ensuring security (i.e., the
double-binning) is present only in the M1 codebook.
3) Only M2 is Secret: The SD-BC where M2 is secret is
obtained by taking L1 → ∞ and L2 = 0. The secrecy-capacity
region is the closure of the union of rate pairs (R1 , R2 ) ∈ R2+
satisfying:

R1 ≤ H(Y1 )

(35a)

R1 ≤ H(Y1 |W ) + I(W ; Y2 )
R2 ≤ I(V ; Y2 |W ) − I(V ; Y1 |W )

(35b)
(35c)

where the union is over all PMFs QW,V,X ∈ P(W × V × X ),
each inducing a joint distribution QW,V,X 1{Y1 =y1 (X)} WY2 |X
[6, Theorem 1]. Using Corollary 7, the bounds (32) become
n
o
R1 ≤ H(Y1 |W ) + min I(W ; Y1 ), I(W ; Y2 ) (36a)
R2 ≤ I(V ; Y2 |W ) − I(V ; Y1 |W )

R1 + R2 ≤ H(Y1 |W, V ) + I(V
n ; Y2 |W )

(36b)

o (36c)
+ min I(W ; Y1 ), I(W ; Y2 ) .

and (36c) is redundant by adding (36a) and (36b). The regions
from (35) and (36) thus coincide.
The effect of L1 → ∞ and L2 = 0 on the bins in our coding
scheme (Section VII-B) is analogous to the one described in
Section V-D2. In contrast to Section V-D2, however, here the
achievability of (36) requires a common message. Since L2 =
0, (60c) implies that the public message is a portion of M1
only. Keeping in mind that the public message is decoded by
both receivers, unless R20 = 0 (i.e., unless the public message
contains no information about M2 ) the secrecy constraint will
be violated.

9

4) Both Messages are Secret: Taking L1 = L2 = 0
recovers the SD-BC where both messages are secret. The
secrecy-capacity region for this case was found in [5, Theorem
1] and is the closure of the union of rate pairs (R1 , R2 ) ∈ R2+
satisfying:

Encoder
X
0

R1 ≤ H(Y1 |W, V, Y2 )

(37a)

1

R2 ≤ I(V ; Y2 |W ) − I(V ; Y1 |W )

(37b)

2

where the union is over all PMFs QW,V QX|V
∈
P(W × V × X ), each inducing a joint distribution
QW,V QX|V 1{Y1 =y1 (X)} WY2 |X . The region (37) coincides
0
0
with CSD
(0, 0). Restricting the union in CSD
(0, 0) to encompass
only PMFs that satisfy the Markov relation W − V − X does
not shrink the region. This is since in the proof of Theorem
3 we define Vq , (M2 , Wq ), and therefore, Xq − Vq − Wq
forms a Markov chain for every q ∈ [1 : n].
Remark 10 (Relation to Optimal Coding Scheme): The
coding scheme that achieves (37) uses double-binning for the
codebooks of both private messages. To ensure confidentiality,
the rate bounds of each message includes the penalty term
I(U1 ; U2 |U0 ). Note that without the confidentiality constraints,
Marton’s coding scheme [18] requires only that the sum-rate
has that penalty term. This is evident from our scheme by
setting L1 = L2 = 0 in (60c), (86b) and (87b), which makes
(68a) redundant.

0
1

R12

I(M1 ; Y2 ) ≤ nL1

Y2
Decoder 2
Fig. 2: Blackwell BC with privacy leakage constraints.

R0 + R1 ≤ I(X; Y1 |W ) + I(W ; Y2 )
R0 + R1 ≤ I(X; Y1 )

Consider the BC with leakage constraints in which M2 = 0;
its leakage-capacity region CDM (L1 ) is stated in Theorem 5.
We show that CDM (L1 ) recovers the secrecy-capacity region of
the BC with confidential messages [3] and the capacity region
of the BC with a degraded message set (without secrecy) [28].
1) BCs with Confidential Messages: The secrecy-capacity
region of the BC with confidential messages was derived in
[3] and is the union over the same domain as in Theorem 5
of rate pairs (R0 , R1 ) ∈ R2+ satisfying:
n
o
R0 ≤ min I(W ; Y1 ), I(W ; Y2 )
(38a)
(38b)

Inserting L1 = 0 into the result of Theorem 5 produces (38).
Our code construction (Section VII-B) with L1 = 0 and
U2 = 0 reduces to a superposition code for which the outer
codebook (that is associated with the confidential message) is
binned. This is a secrecy-capacity achieving coding scheme
for the BC with confidential messages.
Remark 11 (Wiretap Channel): The BC with confidential
messages captures the WTC by setting M0 = 0. Thus, the
WTC is also a special case of the BC with privacy leakage
constraints.
2) BCs with a Degraded Message Set: If L1 → ∞, we get
the BC with a degraded message set [28]. Inserting L1 → ∞
into CDM (L1 ) and setting U = X we recover the union of rate
pairs (R0 , R1 ) ∈ R+ satisfying:
n
o
R0 ≤ min I(W ; Y1 ), I(W ; Y2 )
(39a)

(39b)
(39c)

where the union is over all PMFs QW,X ∈ P(V × X ), each
induces a joint distribution QW,X WY1 ,Y2 |X .
CDM (L1 ) in (39) matches [37, Theorem 7] which establishes
the union over all PMFs QT,U,X ∈ P(T ×U ×X ) of rate pairs
(R0 , R1 ) ∈ R+ with
n
o
R0 ≤ min I(T ; Y1 ), I(T ; Y2 )
(40a)
R0 + R1 ≤ I(X; Y1 |T, U ) + I(T, U ; Y2 )
R0 + R1 ≤ I(X; Y1 )

E. BCs with One Private Message

R1 ≤ I(U ; Y1 |W ) − I(U ; Y2 |W ).

Decoder 1
Y1
0
I(M2 ; Y1 ) ≤ nL2
1

(40b)
(40c)

as an outer bound on the capacity region of interest. The RHS
of (40a) can be bounded as
n
o
n
o
min I(T ; Y1 ), I(T ; Y2 ) ≤ min I(T, U ; Y1 ), I(T, U ; Y2 )
(41)
and relabeling W = (T, U ) matches (39).
VI. E XAMPLE
Suppose the channel from the transmitter to receivers 1 and
2 is the BW-BC without a common message as illustrated in
Fig. 2 [29], [30]. Using Corollary 7, the (L1 , L2 )-leakagecapacity region of a deterministic BC (DBC) is the following.
Corollary 8 (Leakage-Capacity - Deterministic BC): The
(L1 , L2 )-leakage-capacity region CD (L1 , L2 ) of the DBC
1{Y1 =y1 (X)}∩{Y2 =y2 (X)} without a common message is the
union of rate pairs (R1 , R2 ) ∈ R2+ satisfying:

(42a)
R1 ≤ min H(Y1 ) , H(Y1 |Y2 ) + L1

(42b)
R2 ≤ min H(Y2 ) , H(Y2 |Y1 ) + L2
R1 + R2 ≤ H(Y1 , Y2 )

(42c)

where the union is over all input PMFs QX ∈ P(X ).
The proof of Corollary 8 is relegated to Appendix A. For the
BW-BC, we parametrize the input PMF QX ∈ P {0, 1, 2}
in Corollary 8 as
QX (0) = α , QX (1) = β , QX (2) = 1 − α − β,

(43)

where α, β ∈ R+ and α + β ≤ 1. Using (43), the (L1 , L2 )leakage-capacity region CBW (L1 , L2 ) of the BW-BC is de-

10

scried as the union of rate pairs (R1 , R2 ) ∈ R2+ satisfying:

1.2

L=0

R2 [bits/use]

L = 0.1

As explained in Remark 4, for each leakage value L, Corollary
PSfrag
replacements
2 (along with some numerical calculations) can be used
to tell
whether a further increase of L will induce a larger region
or not. Accordingly, for each L ∈ {0, 0.05, 0.1, 0.4}, we have
calculated the maximum of L⋆ (α, β) over the distributions that
achieve the boundary points of the capacity region CBW (L, L).
Denoting the value of the maximal L⋆ that corresponds to the
allowed leakage L ∈ {0, 0.05, 0.1, 0.4} by L⋆ (L), we have
L⋆ (0) = L⋆ (0.05) = 0.15897
L⋆ (0.1) = 0.20101
L⋆ (0.4) = 0.38317.

L = 0.4

0.8

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

1.2

R1 [bits/use]
(a)
1.2

L=0
L = 0.05

1

L = 0.1

R2 [bits/use]

where the union is over all α, β ∈ R+ with α + β ≤ 1.
Fig. 3 illustrates CBW (L1 , L2 ) for three cases. In Fig. 3(a)
L2 → ∞ while L1 ∈ {0, 0.05, 0.1, 0.4}. The blue (inner)
line corresponds to L1 = 0 and is the secrecy-capacity
region of a BW-BC where M1 is secret [27, Fig. 5]. The
red (outer) line corresponds to L1 = 0.4 (which is large
enough to be thought of as L1 → ∞) and depicts the capacity
region of the classic BW-BC. As L1 grows, the inner (blue)
region converges to coincide with the outer (red) region. Fig.
3(b) considers the opposite case, i.e., where L1 → ∞ and
PSfrag
replacements
L2 ∈ {0, 0.05, 0.1, 0.4}, and is analogous to Fig. 3(a).
In Fig.
3(c) we choose L1 = L2 = L, where L ∈ {0, 0.05, 0.1, 0.4},
and we demonstrate the impact of two leakage constraints on
the region. When L = 0, one obtains the secrecy-capacity
region of the BW-BC when both messages are confidential [5].
In each case, the capacity region grows with L and saturates
at the red (outer) region, for which neither message is secret.
Focusing on the symmetric case in Fig. 3(c), we note that the
saturation of the region at L = 0.4 is implied by Corollary
2. For the Blackwell BC with L1 = L2 = L, and some
α, β ∈ R+ with α + β ≤ 1, we denote by L⋆ (α, β) the
threshold from (26), which reduces to


β
L⋆ (α, β) = I(Y1 ; Y2 ) = Hb (β) − (1 − α)Hb
. (45)
1−α

L = 0.05

1

L = 0.4

0.8

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

1.2

R1 [bits/use]
(b)
1.2

L=0
L = 0.05

1

R2 [bits/use]





β
+ L1 (44a)
R1 ≤ min Hb (β) , (1 − α)Hb
1−α
PSfrag
replacements




α
+ L2 (44b)
R2 ≤ min Hb (α) , (1 − β)Hb
1−β


β
(44c)
R1 + R2 ≤ Hb (α) + (1 − α)Hb
1−α

L = 0.1
L = 0.4

0.8

0.6

0.4

0.2

0
0

0.2

0.4

0.6

0.8

1

1.2

R1 [bits/use]

(46)

Observing that L⋆ (0.4) ≤ L, Corollary 2 and Remark 4 imply
that increasing L beyond 0.4 will not change the leakagecapacity region. Evidently, CBW (L, L) saturates at L = 0.4.
For L ∈ {0, 0.05, 0.1}, however, L⋆ (L) > L and consequently
CBW (L′ , L′ ) ( CBW (L, L), for L, L′ ∈ {0, 0.05, 0.1} with
L′ < L.
The variation of the sum of rates R1 + R2 as a function
of L is shown by the blue curve in Fig. 4; the red dashed
vertical lines correspond to the values of L considered in Fig.
3. Note that for 0 ≤ L ≤ 0.09818, (44c) is inactive, and
therefore, R1 + R2 is bounded by the summation of (44a) and

(c)

Fig. 3: (L1 , L2 )-leakage-capacity region of the BW-BC for
three cases: (a) L1 = L and L2 → ∞; (b) L1 → ∞ and
L2 = L; (c) L1 = L2 = L.

(44b). Thus, for 0 ≤ L ≤ 0.09818, the sum of rates R1 + R2
increases linearly with L. For L > 0.09818, the bound in (44c)
is no longer redundant, and because it is independent of L,
the sum rate saturates.
The regions in Fig. 3 are a union of rectangles or pentagons,

each corresponds to a different input PMF QX ∈ P {0, 1, 2} .

11

VII. P ROOFS

1.6

A. Proof of Lemma 3

R1 + R2 [bits/use]

1.55

We derives sufficient conditions for


(U)
EBn F PI|Bn , pIn −−−−→ 1

1.5

(47)

n→∞

1.45

1.4

frag replacements
1.35
0

0.02

0.04 0.05 0.06

0.08

0.1

0.12

L [bits/use]

Fig. 4: The sum-rate capacity versus the allowed leakage for
L1 = L2 = L.

which implies Lemma 3 using (10).
First, for each Bn ∈ Bn the fidelity between the induced
and the desired (uniform) distribution is


(U)
F PI|Bn =Bn , pIn
12



X 2i uℓ (w);vj,k (w) w
X
1


(48)
=

P i uℓ̄ (w);vj̄,k (w) w 

 |In ||Kn |
2
ℓ
(j,k)
(ℓ̄,j̄)

where as in (17), the information density is taken with respect
to QnU,V . Now, by theCauchy-Schwarz
inequality we have the

following bound for aj,k , bj,k ⊂ R+ :
 21

 21 
Xp
X
X
aj,k bj,k ≤ 
(49)
bj,k  .
aj,k  

R2

H(Y2 )

j,k

lacements
H(Y2 |Y1 )

j,k

j,k

Using this on each of the summands from the right-hand side
(RHS) of (48) with

2i uℓ (w);vj,k (w) w
1

(50a)
aj,k =
|In ||Kn | P i uℓ̄ (w);vj̄,k (w) w
2
(ℓ̄,j̄)

0
H(Y1 |Y2 )

H(Y1 )

R1

Fig. 5: The pentagons/rectangles whose union produces the
capacity region of a BW-BC for different secrecy cases: The
outer pentagon corresponds to the case without secrecy; the
red and blue rectangles correspond to L1 = 0 and L2 = 0,
respectively; the inner rectangle corresponds to L1 = L2 = 0.

In Fig. 5 we illustrate a typical structure of these rectangles
and pentagons for a fixed QX at the extreme values of L1 and
L2 . When both L1 and L2 are sufficiently large, the leakage
constraints degenerate and the classic BW-BC is obtained.
Its capacity region (the red (outer) line in, e.g., Fig. 3(c)) is
a union of the pentagons depicted in Fig. 5. The secrecycapacity region for L1 = 0 and L2 → ∞ (depicted by the
blue line in Fig. 3(a)) is a union of the red rectangles in
Fig. 5. Similarly, when L2 = 0 and L1 → ∞ the secrecycapacity region is a union of the blue rectangles in Fig. 5.
Finally, if L1 = L2 = 0 and both messages are secret, the
secrecy-capacity region of the BW-BC is the union of the dark
rectangles in Fig. 5, i.e., the intersection of the blue and the red
regions. Fig. 5 highlights that as L1 and/or L2 decrease, the
underlying pentagons/rectangles (the union of which produces
the admissible rate region) shrink, which results in a smaller
region.

and

2
bj,k = P

i uℓ (w);vj,k (w) w

uℓ̄ (w);vj̄,k̄ (w) w

2i

(ℓ̄,k̄)

we obtain


(U)
F PI|Bn =Bn , pIn
≥

X

(ℓ,j,k)

2i

|In ||Kn |

uℓ (w);vj,k (w) w

P



2i



uℓ̄ (w);vj̄,k (w) w

(ℓ̄,j̄)

1

×

(50b)



1

 !2

1

P

(j̄,k̄)

2i

uℓ̄ (w);vj̄,k̄ (w) w

 !2

. (51)

For any w ∈ W n with QnW (w) > 0, we evaluate the
conditional expectation of the fidelity given W = w as given
in (52) at the top of this page. First note that with respect to
the notation from Section III, we have




(U)
(U)
EBn |W=w F PI|Bn , pIn = EBn (w) F PI|Bn , pIn . (53)
Now consider the following justifications for the steps of (52):
(a) uses (51) and the symmetry of the random codebook;
(b) is the law of total expectation;

12



(U)
EBn (w) F PI|Bn , pIn
(a)



1
1

≥ |In | 2 |Jn ||Kn | 2 EBn (w) 2i

U1 (w);V1,1 (w) w



 i
1
1
= |In | 2 |Jn ||Kn | 2 EU1 (w),V1,1 (w) 
2

(b)






X

2i

Uℓ̄ (w);Vj̄,1 w

(ℓ̄,j̄)

U1 (w),V1,1 (w) w



− 12 




X

U1 (w);Vj̃,k̃ (w)

2i

(j̃,k̃)



− 21 
 





− 1 



 2 X
 X
2i U1 (w);Vj̃,k̃ (w)
2i Uℓ̄ (w);Vj̄,1 (w) w  
× EBn (w)|U1 (w),V1,1 (w) 


 (ℓ̄,j̄)
(j̃,k̃)

− 21


(c)
1
1
i U1 (w);V1,1 (w) w
i U1 (w);V1,1 (w) w

2
2
≥ |In | |Jn ||Kn | EU1 (w),V1,1 (w) 2
2
+ |In ||Jn | − 1

× 2i



(d)

i(U;V|w)



−1

i(U;V|w)

− 21 

−1

U1 (w);V1,1 (w) w

> EQnU |W =w QnV |W =w 2
1 + |In ||Jn |
2
1 + |Jn ||Kn |
2


−1 i(U;V|w) − 21
−1 i(U;V|w) − 21 
(e)
1 + |Jn ||Kn |
2
2
= EQnU,V |W =w 1 + |In ||Jn |
µ(Cn ) =

Y

mp ∈Mp

 Y
QnU0 u0 (mp )

j=1,2

Y

(j)
mp
,mjj ,wj ,ij



∈Mp ×Mjj ×Wj ×Ij

(c) uses Jensen’s inequality for the two-valued convex function
1
f : (x, y) 7→ (xy)− 2 and the relation

(54)
EBn (w)|U1 (w),V1,1 (w) 2i Uℓ̄ (w);Vj̄,k̄ (w) w = 1

which holds for any (ℓ̄, j̄, k̄) 6= (1, 1, 1) (see [32], [45] for a
similar derivation);
(d) is by increasing each term in the parenthesis by 1;
(e) is because U1 (w), V1,1 (w)) ∼ QnU|W =w QnV |W =w .

Taking an expectation over W of both sides of (52),
while making use of the law of total expectation and of the
monotonicity of expectation, gives


(U)
EBn F PI|Bn , pIn


(U)
= EW EBn |W F PI|Bn , pIn

−1 i(U;V|W) − 21
n
1 + |In ||Jn |
2
≥ EQW,U,V


−1 i(U;V|W) − 21
. (55)
× 1 + |Jn ||Kn |
2

Finally, note that

1
EQn
2iQW,U,V (U;V|W) = IQW,U,V (U ; V |W ).
(56)
n W,U,V
Therefore, by the weak law of large number for any ζ > 0

i(U;V|w)

− 12 



w




− 12 









+ |Jn ||Kn | − 1




(j)
QnUj |U0 uj m(j)
p , mjj , wj , ij u0 (mp )

− 12




(52)

(61)

there exists a sequence {δn }n∈N with limn→∞ δn = 0, such
that
!
1
PQnW,U,V
iQn
(U;V|W)−IQW,U,V (U;V |W) > ζ ≤ δn ,
n W,U,V
(57)
for all n ∈ N. Combining (55) and (57) we see that as long
as

(58)
S2 + min S1 , T > IQW,U,V (U ; V |W ) + ζ
then



(U)
EBn F PI|Bn , pIn ր 1

(59)

as n → ∞. The relation (10) now establishes the result of
Lemma 3.
B. Proof of Theorem 1
Fix n ∈ N, (L1 , L2 ) ∈ R2+ , ǫ, δ > 0, a PMF QU0 ,U1 ,U2 ,X ∈
P(U0 × U1 × U2 × X ) and denote QU0 ,U1 ,U2 ,X,Y1 ,Y2 ,
QU0 ,U1 ,U2 ,X WY1 ,Y2 |X . In the following we omit the blocklength n from our notations of the ets of indices, e.g., we write
(n)
M0 instead of M0 . Furthermore, we assume that quantities
nR
of the form 2 , where n ∈ N and R ∈ R+ , are integers.5
5 Otherwise simple modifications of some of the subsequent expressions
using floor and ceiling operations are required.

13

Message Splitting: Split each message mj ∈ Mj , j = 1, 2,
into a pair of messages denoted by (mj0 , mjj ). The triple
mp , (m0 , m10 , m20 ) is referred to as a public message
while mjj , j = 1, 2, serves as private message j. The rates
associated with mj0 and mjj , j = 1, 2, are denoted by Rj0
and Rjj , while the corresponding alphabets are Mj0 and Mjj ,
respectively. The partial rates Rj0 and Rjj , j = 1, 2, satisfy
Rj = Rj0 + Rjj
0 ≤ Rj0 ≤ Rj

(60a)
(60b)

Rj0 ≤ Lj .

(60c)

Let Mj0 and Mjj be independent random variables uniformly
distributed over Mj0 and Mjj , respectively. We use the
notations Mp , (M0 , M10 , M20 ), Mp , M0 × M10 × M20
and Rp , R0 + R10 + R20 . Note that Mp is uniformly
distributed over Mp and that |Mp | = 2nRp . Moreover, let
(W1 , W2 ) be a pair of independent random variables,
 where
Wj , j = 1, 2, is uniformly distributed over Wj = 1 : 2nR̃j
and independent of (M0 , M1 , M2 ) (which implies their independence of (Mp , M11 , M22 ) as well).

(n)
Codebook C n : Let C0 , U0 (mp ) mp ∈Mp be a random
public message codebook that comprises 2nRp i.i.d. random
vectors U0 (mp ), each distributed according to QnU0 . A real
(n)
(n)
ization of C0 is denoted by C0 , u0 (mp ) mp ∈Mp .
(n)

a public message codebook C0 . For every
(n)
m
∈
Mp and j
= 1, 2, let Cj (mp ) ,
p

where
Uj (mp , mjj , wj , ij ) (mjj ,wj ,ij )∈Mjj ×Wj ×Ij ,

′ 
(mjj , wj , ij ) ∈ Mjj × Wj × Ij and Ij , 1 : 2nRj ,
be a random codebook of private messages j,
consisting of conditionally independent random vectors
each distributed according to QnUj |U0 =u0 (mp ) . A
Fix

(n)

(n)

realization of Cj (mp ) is denoted by Cj (mp ) ,

uj (mp , mjj , wj , ij ) (mjj ,wj ,ij )∈Mjj ×Wj ×Ij .
o
n
(n)
(n)
We denote Cj , Cj (mp )
, and its realiza(n)

mp ∈Mp

is denotedoby Cn =
tion by Cj . Ao random codebook
n
n
(n)
(n)
(n)
(n)
(n)
(n)
denotes a
C0 , C1 , C2 , while Cn = C0 , C1 , C2
fixed codebook (a possible outcome of Cn ). Denoting the set
of all possible realizations of Cn by Cn , the above codebook
construction induces a PMF µ ∈ P(Cn ) over the codebook
ensemble. For every Cn ∈ Cn , we have (61) at the top of this
page.
For a fixed codebook Cn ∈ Cn we now describe its
associated encoding function f (Cn ) and decoding functions
(C )
φj n , for j = 1, 2.
Encoder f (Cn ) : Fix a codebook Cn ∈ Cn . To transmit
the message pair (m0 , m1 , m2 ) the encoder transforms it into
the triple mp , m11 , m22 ), and draws Wj uniformly from Wj ,
j = 1, 2; denote the realization of Wj by wj ∈ Wj . Given
(mp , m11 , m22 , w1 , w2 ), a pair of indices (i1 , i2 ) ∈ I1 × I2 is
randomly selected by the likelihood encoder according to
(C )

PLE n (i1 , i2 |mp , m11 , m22 , w1 , w2 )

,


2iQn u1 (mp ,m11 ,w1 ,i1 );u2 (mp ,m22 ,w2 ,i2 ) u0 (mp )

P
iQn u1 (mp ,m11 ,w1 ,i′1 );u2 (mp ,m22 ,w2 ,i′2 ) u0 (mp )
2

(i′1 ,i′2 )
∈I1 ×I2

(62)

where iQn stands for the information density with respect
to the conditional product distribution QnU1 ,U2 |U0 (and its
(C )

marginals). The structure of PLE n adheres to the setup of
Lemma 3 from Section III and, in particular, to the stochastic
choice of indices therein as described in (14). Replacing the
(C )
commonly used joint typicality encoder with PLE n , we are
able to establish several important properties of the chosen
codewords and their induced distribution.
Let (i1 , i2 ) be the selected pair of indices. The channel input
sequence is randomly generated according to the conditional
product distribution
QnX|U0 =u0 (mp ),U1 =u1 (mp ,m11 ,w1 ,i1 ),U2 =u2 (mp ,m22 ,w2 ,i2 ) .
(C )

Decoder φj n : Decoder j = 1, 2 operates in two stages.
First, it searches for a unique m̂p ∈ Mp such that


(63)
u0 (m̂p ), yj ∈ Tδn (QU0 ,Yj ).
(C )

If no such unique index is found, set φj n = (1, 1). Otherwise, having m̂p ∈ Mp , Decoder j = 1, 2 proceeds by
looking for a unique pair (m̂jj , ŵj ) ∈ Mjj × Wj for which
there exists an index îj ∈ Ij such that


u0 (m̂p ), uj (m̂p , m̂jj , ŵj , îj ), yj ∈ Tδn (QU0 ,Uj ,Yj ). (64)

Recall that each mp ∈ Mp specifies a triple (m0 , m10 , m20 ) ∈
M0 × M10 × M20 . If the second stage is also executed
successfully the decoder has a triple (m̂p , m̂jj , ŵj ) ∈ Mp ×
Mjj × Wj with m̂p and (m̂jj , ŵj ) being the unique indices satisfying (63) and (64),
respectively. In this case we

(Cn )
set φj (yj ) = m̂0 , m̂j , where m̂j is assembled from
(C )
(m̂j0 , m̂jj ); otherwise, set φj n = (1, 1).
 Induced Code and Joint Distribution: The triple
(C )
(C )
defined with respect to the codebook
f (Cn ) , φ1 n , φ2 n
Cn ∈ Cn constitutes an (n, R0 , R1 , R2 ) code cn for the BC
with privacy leakage constraints. Thus, for every codebook
Cn ∈ Cn , the induced joint distribution is given in (65) at the
top of this page, where the random variables U0 , U1 and U2
are the chosen codewords at the conclusion of the encoding
process (from which the input X to the BC is generated).
Taking the random codebook generation into account, we
also have (66) at the top of this page, where µ ∈ P(Cn ) is
described in (61). The PMF P induces a probability measure
P , PP , with respect to which the subsequent analysis is performed. Specifically, all the multi-letter information measures
in the sequel are taken with respect to P from (66), while
single-letter information terms are calculated with respect to
QU0 ,U1 ,U2 ,X,Y1 ,Y2 .
Average Error Probability Analysis: The output se(C )
quences of PLE n from (62) are jointly typical with high
probability as long as the sum of the rates of the product
bin is greater than the mutual information between the coding

14




P (Cn ) mp ,m11 , m22 , w1 , w2 , i1 , i2 , u0 , u1 , u2 , x, y1 , y2 , m̂0 , m̂1 , m̂0 , m̂2 =
(C )

2−n(Rp +R11 +R11 +R̃1 +R̃2 ) PLE n (i1 , i2 |mp , m11 , m22 , w1 , w2 )1

u0 =u0 (mp ) ∩

× QnX|U0 ,U1 ,U2 (x|u0 , u1 , u2 )WYn1 ,Y2 |X (y1 , y2 |x)1

T
j=1,2

T
j=1,2







uj =uj (mp ,mjj ,wj ,ij )

(Cn )

m̂0 ,m̂j =φj

(65)

(yj )




P Cn , mp , m11 ,m22 , w1 , w2 , i1 , i2 , u0 , u1 , u2 , x, y1 , y2 , m̂0 , m̂1 , m̂0 , m̂2



= µ(Cn )P (Cn ) mp , m11 , m22 , w1 , w2 , s1 , s2 , u0 , u1 , u2 , x, y1 , y2 , m̂0 , m̂1 , m̂0 , m̂2
random variables [32, Theorem 3]. The rest of the error
probability analysis goes through via classic joint typicality
arguments. The details of the analysis are relegated to Appendix B, where it is shown that
′

EPe (Cn ) ≤ η(n, δ, δ )
′

′

(67)
′

where δ ∈ (0, δ) and limn→∞ η(n, δ, δ ) = 0 for all 0 < δ <
δ, if
R1′ + R2′ > I(U1 ; U2 |U0 )
R0 + R10 + R20 < I(U0 ; Y1 ) − τδ

(68a)
(68b)

R0 + R10 + R20 < I(U0 ; Y2 ) − τδ

(68c)

R11 + R̃1 + R1′ < I(U1 ; Y1 |U0 ) − τδ
R22 + R̃2 +

R2′

< I(U2 ; Y2 |U0 ) − τδ

(68d)
(68e)

with τδ → 0 as δ → 0. Furthermore, setting ηn , η(n, δn , δn′ )
where {δn }n∈N and {δn′ }n∈N are sequences that converge sufficiently slowly to zero as n grows, we have limn→∞ ηn = 0.
To clarify, the δ ′ that appears in (67) and in upper bounds
below is a consequence of the Conditional Typicality Lemma
[20, Section 2.5]. This lemma considers conditioning on sequences that are jointly letter-typical with respect to a slightly
smaller gap than the original δ. This smaller gap is δ ′ .
Properties for Leakage Analysis: In contrast to previous
works, we do not analyse the expected leakages of the random
code. Instead, we establish certain properties that the random
code possesses and then extract a specific sequence of codes
that satisfies these properties as well as reliability. It is then
shown that the extracted sequence of codes admits the leakage
constraints.
By symmetry, we consider only the properties required for
the analysis of the rate-leakage from M1 to the 2nd receiver.
The corresponding derivations for M2 follows similar lines
and the resulting rate constraints match up to changing some
indices.
We first need a decodability property. Specifically, Decoder
2 should be able to decode (W1 , I1 ) with a low error probability based on (Mp , M11 , M22 , W2 , I2 , Y2 ). We consider
a decoding rule based on a joint typicality test: Decoder 2
searches for a unique pair (w̌1 , ǐ1 ) ∈ W1 × I1 such that


u0 (mp ), u1 (mp , m11 , w̌1 , ǐ1 ),u2 (mp , m22 , w2 , i2 ), y2
∈ Tδn (QU0 ,U1 ,U2 ,Y2 ). (69)

(66)

For a fixed codebook Cn ∈ Cn (which specifies a code cn ),
(Leak)
let P1
(Cn ) denote the probability that Decoder 2 fails in
this decoding process. As explained in Appendix B, we have
(Leak)

EP1

(Cn ) ≤ κ(n, δ, δ ′ )

′

(70)

′

where δ ∈ (0, δ) and limn→∞ κ(n, δ, δ ) = 0 for all 0 < δ ′ <
δ, if
R̃1 +

R̃1 < I(U1 ; Y2 |U0 , U2 ) − ξδ

(71a)

R1′

(71b)

< I(U1 ; U2 , Y2 |U0 ) − ξδ

with ξδ → 0 as δ → 0. Again, by allowing δ and δ ′ from (70)
to converge to zero sufficiently slow with n, κ(n, δ, δ ′ ) may
be replaced by a κn with limn→∞ κn = 0.
We are now ready to state Lemmas 4-6. Proofs are given in
Appendices C-E.
Lemma 4: If (71) is valid with ξδ → 0 as δ → 0, then there
exists ζ1 (n, δ, δ ′ ), where δ ′ ∈ (0, δ), such that
H(W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 , Cn ) ≤ nζ1 (n, δ, δ ′ )
(72)
and limn→∞ ζ1 (n, δ, δ ′ ) = 0 for all 0 < δ ′ < δ. Furthermore,
setting ζ1,n , ζ1 (n, δn , δn′ ) where {δn }n∈N and {δn′ }n∈N are
sequences that decay sufficiently slow to zero as n grows, we
have limn→∞ ζ1,n = 0.
Lemma 5: There exist ζ2 (n, δ, δ ′ ) that satisfies the same
properties as ζ1 (n, δ, δ ′ ) from Lemma 4, such that
I(U1 ; Y2 |U0 , U2 , Cn ) ≤ nI(U1 ; Y2 |U0 , U2 ) + nζ2 (n, δ, δ ′ ).
(73)
Lemma 6: There exists ζ3 (n, δ, δ ′ ) that satisfies the same
properties as ζ1 (n, δ, δ ′ ) from Lemma 4, such that
I(U1 ; M22 , W2 , I2 |Mp , Cn ) ≤ nI(U1 ; U2 |U0 ) + nζ3 (n, δ, δ ′ ).
(74)
The Uniform Approximation Lemma from Section III further implies that if

(75)
R2′ + min R1′ , R22 + R̃2 > I(U1 ; U2 |U0 ) + δ
then there exist ζ4,n with limn→∞ ζ4,n , such that
(U)

ECn PMp ,M11 ,W1 ,I1 |Cn −pMp ×M11 ×W1 ×I1
(U)

TV

≤ ζ4,n (76)

where pMp ×M11 ×W1 ×I1 is the uniform distribution on Mp ×
M11 × W1 × I1 . To see this, observe that by symmetry we

15

have

and
(U)
pMp ×M11 ×W1 ×I1

ECn PMp ,M11 ,W1 ,I1 |Cn −
X
1
=
|Mp ||M11 ||W1 |


R1′ + min R2′ , R11 + R̃1 > I(U1 ; U2 |U0 ) + δ

TV

(80c)

in accordance with (71) and (75), respectively. This implies
that results analog to those of Lemmas 4-6 and (76) hold for
M2 .

(mp ,m11 ,w1 )
∈Mp ×M11 ×W1

(U)

× ECn PI1 |Mp =mp ,M11 =m11 ,W1 =w1 ,Cn − pI1
= ECn PI1 |Mp =1,M11 =1,W1 =1,Cn −

(U)
pI 1

TV

TV

.

(77)

Note that (Mp , M11 , W1 ) = (1, 1, 1) fixes a single u1 -bin
′
(comprising 2nR1 codewords), while the pair (M22 , W2 ) (of
total rate R22 + R̃2 ) uniformly chooses a u2 -bin (comprising
′
2nR2 codewords). Lemma 3 now gives the desired relation
because bins are generated conditionally independent given
(C )
U0 and the chosen codeword pair is drawn according to PLE n
from (62) which adheres to the structure of (14).
We now invoke the Selection Lemma [46, Lemma 5] to
extract a specific sequence of codes that satisfies several
desired properties. We restate this lemma next.

Lemma 7 (Selection Lemma): Let An n∈N be a sequence
of random variables,
n
o where An takes values in An . Let
(1)
(2)
(J)
fn , fn , . . . , fn
be a collection of J < ∞ sequences
n∈N
(i)

of bounded functions fn : An → R+ , j ∈ [1 : J ]. If
Efn(j) (An ) −−−−→ 0,
n→∞

∀j ∈ [1 : J ],

n→∞

∀j ∈ [1 : J ].

Consider the sequence of random codes
functions6


Cn

fn(1)(Cn) , Pe (Cn )

(78b)
n∈N

, the
(79a)

fn(2)(Cn) , H(W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 , Cn = Cn )
(79b)
1
fn(3)(Cn) , I(U1 ; Y2 |U0 , U2 , Cn = Cn )
n
− I(U1 ; Y2 |U0 , U2 ) (79c)
1
fn(4)(Cn) , I(U1 ; M22 , W2 , I2 |Mp , Cn = Cn )
n
− I(U1 ; U2 |U0 ) (79d)
(U)

fn(5)(Cn) , PMp ,M11 ,W1 ,I1 |Cn =Cn − pMp ×M11 ×W1 ×I1

TV

(79e)
(6)

(7)

(8)

as well as the functions fn , fn and fn that correspond to
(2)
(3)
(4)
fn , fn and fn , respectively, with respect to the analysis
for M2 . We also impose constraints on the rates that arise from
repeating the above steps for M2 . Namely, we set
R̃2 +

R̃2 < I(U2 ; Y1 |U0 , U1 ) − ξ(δ)

(80a)

R2′

(80b)

< I(U2 ; U1 , Y1 |U0 ) − ξ(δ)

ECn fn(j) (Cn ) −−−−→ 0,

j ∈ [1 : 7].

n→∞

(81)

Lemma 7 now implies the existence of a sequence of codebooks Cn n∈N (each inducing an (n, R1 , R1 , R2 ) code cn )
and another sequence of numbers {ηn }n∈N with limn→∞ ηn =
0, such that for j ∈ [1 : 7] we have
fn(j) (Cn ) ≤ ηn ,

∀n ∈ N.

(82)

Leakage Analysis of M1 Under C n : All subsequent
information measures are calculated with respect to P (Cn )
from (65). We emphasize this by using HCn and ICn as
the notation of such entropy or mutual information terms,
respectively.

(78a)

then there exists a sequence {an }n∈N , where an ∈ An for
every n ∈ N, such that
fn(j) (an ) −−−−→ 0,

Replacing δ and δ ′ in the definitions of ηj (n, δ, δ ′ ), for
j = 1, 2, 3, with {δn }n∈N and {δn′ }n∈N that decay to zero
sufficiently slow, we have

(5)

First, because fn (Cn ) −−−−→ 0 and by the continuity of
n→∞
entropy, there exists a sequence {θn }n∈N with limn→∞ θn =
0, such that

HCn (M11 , W1 , I1 |Mp ) − log |M11 ||W1 ||I1 | ≤ θn (83)
for every n ∈ N. Next, since

1
1
(84)
IC (M1 ; Y2 ) = R1 − HCn (M1 |Y2 )
n n
n
we can upper bound the leakage of M1 to the second receiver
by lower bounding the conditional entropy term from the RHS
of (84). We have
ℓ1 (cn ) =

HCn (M1 |Y2 )
(a)

≥ HCn (M11 |Mp , M22 , W2 , I2 , Y2 )
= HCn (M11 , Y2 |Mp , M22 , W2 , I2 )
− HCn (Y2 |Mp , M22 , W2 , I2 )

(b)

≥ HCn (M11 , Y2 |Mp , M22 , W2 , I2 ) − HCn (Y2 |U0 , U2 )
= HCn (M11 , W1 , I1 , Y2 |Mp , M22 , W2 , I2 )
− HCn (W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 )
− H(Y2 |U0 , U2 )
= HCn (M11 , W1 , I1 |Mp , M22 , W2 , I2 )
+ HCn (Y2 |Mp , M11 , W1 , I1 , M22 , W2 , I2 )
− HCn (W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 )
− HCn (Y2 |U0 , U2 )
(c)

6 We

(1)

slightly abuse notation in the definition of fn because Pe is actually
a function of the code cn rather than the codebook Cn . However, since Cn
uniquely defines cn we prefer this presentation for the sake of simplicity.

= HCn (M11 , W1 , I1 |Mp , M22 , W2 , I2 )
− HCn (W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 )
− ICn (U1 ; Y2 |U0 , U2 )

16

= HCn (M11 , W1 , I1 |Mp ) − ICn (U1 ; M22 , W2 , I2 |Mp )
− HCn (W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 )
− ICn (U1 ; Y2 |U0 , U2 )
(85)
where:
(a) is because conditioning cannot increase entropy and
since M1 corresponds to the pair (M10 , M11 ) while Mp =
(M0 , M10 , M20 );
(b) follows because U0 and U2 are specified by
(Mp , M22 , W2 , I2 ) and since conditioning cannot increase
entropy;
(c) uses the deterministic relations stated in (b) along with
U1 being determined by (Mp , M11 , W1 , I1 ) and the Markov
relation Y2 −(U0 , U1 , U2 )−(Mp , M11 , W1 , I1 , M22 , W2 , I2 ).
Inserting (82) (for j ∈ [2 : 4]), (83) and R11 = R1 − R10
into (85) further gives

n
o
− I(U1 ; U2 |U0 )+ min I(U0 ;Y1 ), I(U0 ;Y2 ) . (89e)

To prove the first claim, assume that L1 ≥ L⋆1 (QU0 ,U1 ,U2 ,X ).
Consequently, the term inside the positive part function from
the RHS of (89a) is non-negative as it satisfies

I(U1 ;Y1 |U0 ) − I(U1 ; U2 , Y2 |U0 ) + L1
n
o
≥ I(U1 ; Y1 |U0 ) + min I(U0 ; Y1 ), I(U0 ; Y2 ) , (90)

which makes (89a) inactive due to (89b), and therefore,
R̃O (L1 , L2 , QU0 ,U1 ,U2 ,X ) = R̃O (∞, L2 , QU0 ,U1 ,U2 ,X ).
An analogous argument with respect to L2 proves the
second claim (essentially by showing that if L2 ≥ L⋆2 then
(89c) is inactive due (89d)). The third claim follows by
combining both preceding arguments.

D. Proof of Theorem 3

HCn (M1 |Y2 )
≥ n R1 − R10 + R̃1 + R1′ − I(U1 ; U2 , Y2 |U0 ) − 3ηn − θn
(a)

≥ nR1 − n L1 + 3ηn + θn



where (a) follows by taking

R̃1 + R1′ − R10 > I(U1 ; U2 , Y2 |U0 ) − L1

(86a)

R1′

(86b)

+ L1 − R10 > I(U1 ; U2 |U0 ).

The bound in (86b) ensures the feasibility of an R̃1 > 0 that
satisfies (71a) and (86a) simultaneously. The corresponding
rate bounds for the analysis of ℓ2 (cn ) are
R̃2 + R2′ − R20 > I(U2 ; U1 , Y1 |U0 ) − L2

(87a)

R2′

(87b)

+ L2 − R20 > I(U1 ; U2 |U0 ).

Recalling that ηn and θn can be made arbitrarily small with
n, there exists n0 (ǫ) ∈ N, such that for all n > n0 (ǫ)
Pe (cn ) ≤ ǫ
ℓ1 (cn ) ≤ L1 + ǫ

(88a)
(88b)

ℓ2 (cn ) ≤ L2 + ǫ.

(88c)

as required.
Our last step is to apply FME on (68), (75), (80) and (86)(87), while using (60) and the non-negativity of the involved
terms, to eliminate Rj0 , Rj′ and R̃j , for j = 1, 2. Since all the
above linear inequalities have constant coefficients, the FME
can be performed by a computer program, e.g., by the FME-IT
software [47]. This shows the sufficiency of (23).
C. Proof of Corollary 2
Fix (L1 , L2 ) ∈ R2+ and QU0 ,U1 ,U2 ,X ∈ P(U0 ×U1 ×U2 ×X ).
The rate bounds describing R̃I (L1 , L2 , QU0 ,U1 ,U2 ,X ) are:
R1 ≤ I(U1 ; Y1 |U0 )−I(U1 ; U2 , Y2 |U0 )+L1
(89a)
n
o
R1 ≤ I(U1 ; Y1 |U0 )+min I(U0 ; Y1 ),I(U0 ; Y2 ) (89b)

R2 ≤ I(U2 ; Y2 |U0 )−I(U2 ; U1 , Y1 |U0 )+L2
(89c)
n
o
R2 ≤ I(U2 ; Y2 |U0 )+min I(U0 ; Y1 ),I(U0 ; Y2 ) (89d)

R1 + R2 ≤ I(U1 ; Y1 |U0 ) + I(U2 ; Y2 |U0 )

We show that given an (L1 , L2 )-achievable rate triple
(R0 , R1 , R2 ), there is a PMF QW,U,V,X ∈ P(W ×U ×V ×X ),
such that (27) holds when the information measures are
calculated with respect to QW,U,V,X WY1 ,Y2 |X . Due to the
symmetric structure of the rate bounds defining RO (L1 , L2 ),
we present only the derivation of (27a)-(27d) and (27h).
The other inequalities from (27) are established by similar
arguments.
Since (R0 , R1 , R2 ) is (L1 , L2 )-achievable, for every ǫ > 0
there is a sufficiently large n ∈ N and an (n, R0 , R1 , R2 ) code
cn for which (22) holds. We note that all subsequent entropy
and mutual information terms are calculated with respect to
the PMF from (19) that is specified by cn .
Fix ǫ > 0 and find the corresponding blocklength n ∈ N.
By Fano’s inequality we have
(j)
H(M0 , Mj |Yjn ) ≤ 1 + nǫRj , nδn,ǫ
, j = 1, 2.
(91)
 (1) (2)
Define δn,ǫ = max δn,ǫ , δn,ǫ . Next, by (22b), we write

n(L1 + ǫ) ≥ I(M1 ; Y2n )
= I(M1 ; M0 , M2 , Y2n ) − I(M1 ; M0 , M2 |Y2n )
(a)

≥ I(M1 ; Y2n |M0 , M2 ) − H(M0 , M2 |Y2n )

(b)

≥ I(M1 ; Y2n |M0 , M2 ) − nδn,ǫ

(92)

where (a) uses the independence of M1 and (M0 , M2 ) and the
non-negativity of entropy, while (b) is by (91). (92) implies
I(M1 ; Y2n |M0 , M2 ) ≤ nL1 + n(ǫ + δn,ǫ ).

(93)

Similarly, we have
I(M1 ; Y2n |M0 ) ≤ nL1 + n(ǫ + δn,ǫ ).
The common message rate R0 satisfies
nR0 = H(M0 )
(a)

≤ I(M0 ; Y1n ) + nδn,ǫ
n
X
I(M0 ; Y1,i |Y1i−1 ) + nδn,ǫ
=
i=1

(94)

17

≤
(b)

≤

n
X

I(M0 , Y1i−1 ; Y1,i ) + nδn,ǫ

i=1
n
X

I(Wi ; Y1,i ) + nδn,ǫ

(95a)
(95b)

i=1

n
where (a) uses (91) and (b) defines Wi , (M0 , Y1i−1 , Y2,i+1
).
n
n
By reversing the roles of Y1 and Y2 and repeating similar
steps, we also have

nR0 ≤
≤

n
X

i=1
n
X

where (a) follows from (91) and (b) follows by the definition
of (Wi , Ui ). Moreover, consider
n(R0 + R1 )
= H(M1 |M0 ) + H(M0 )
(a)

≤ I(M1 ; Y1n |M0 ) + I(M0 ; Y2n ) + nδn,ǫ
n h
i
X
n
n
I(M1 , Y2,i+1
; Y1,i |M0 , Y1i−1 ) + I(M0 ; Y2,i |Y2,i+1
)
≤
i=1

n
I(M0 , Y2,i+1
; Y2,i ) + nδn,ǫ

I(Wi ; Y2,i ) + nδn,ǫ .

(96a)
(96b)

+ nδn,ǫ

=

n
I(Ui ; Y1,i |Wi ) + I(Y2,i+1
; Y1,i |M0 , Y1i−1 )

i=1

i=1

For R1 , it follows that

n h
X

i
n
+ I(M0 ; Y2,i |Y2,i+1
) + nδn,ǫ

n h
X
n
I(Ui ; Y1,i |Wi ) + I(Y1i−1 ; Y2,i |M0 , Y2,i+1
)
=

(b)

nR1

i=1

= H(M1 |M0 , M2 )
(a)

≤ I(M1 ; Y1n |M0 , M2 ) − I(M1 ; Y2n |M0 , M2 ) + nL1 + nξn,ǫ
n h
(b) X
n
I(M1 ; Y1i , Y2,i+1
|M0 , M2 )
=
i=1
i
n
− I(M1 ; Y1i−1 , Y2,i
|M0 , M2 ) + nL1 + nξn,ǫ
n h
i
X
I(M1 ; Y1,i |M2 , Wi ) − I(M1 ; Y2,i |M2 , Wi )
=

i
n
+ I(M0 ; Y2,i |Y2,i+1
) + nδn,ǫ
n h
i
(c) X
I(Ui ; Y1,i |Wi ) + I(Wi ; Y2,i ) + nδn,ǫ
(100)
≤
i=1

where (a) is by (91), (b) is Csiszár’s sum identity, while (c)
uses the definition of (Wi , Ui ).

i=1

(c)

=

n h
X
i=1

+ nL1 + nξn,ǫ
i
I(Ui ; Y1,i |Wi , Vi ) − I(Ui ; Y2,i |Wi , Vi )

+ nL1 + nξn,ǫ
(97)

where (a) uses (91) and (92) and ξn,ǫ = 2δn,ǫ + ǫ, (b) follows
from a telescoping identity [48, Eqs. (9) and (11)], and (c)
uses Ui , (M1 , Wi ) and Vi , (M2 , Wi ).
R1 is also upper bounded as

To bound the sum R0 + R1 + R2 , we start by writing
H(M1 |M0 , M2 )
(a)

≤ I(M1 ; Y1n |M0 , M2 ) + nδn,ǫ
n
X
I(M1 ; Y1,i |M0 , M2 , Y1i−1 ) + nδn,ǫ
=
i=1

≤

nR1 = H(M1 |M0 )
(b)

(a)

≤ I(M1 ; Y1n |M0 ) − I(M1 ; Y2n |M0 ) + nL1 + nξn,ǫ
n h
i
(b) X
n
n
I(M1 ; Y1i , Y2,i+1
|M0 ) − I(M1 ; Y1i−1 , Y2,i
|M0 )
=
i=1
+ nL1 + nξn,ǫ
n h
i
X
(c)
I(Ui ; Y1,i |Wi ) − I(Ui ; Y2,i |Wi ) + nL1 + nξn,ǫ
=
i=1

(98)

where (a) is by (91) and (94), (b) uses a telescoping identity,
while (c) follows by the definition of (Wi , Ui ).
For the sum R0 + R1 , we have

i=1
n h
X
i=1

i
n
I(Ui ; Y1,i |Wi , Vi ) + I(Y2,i+1
; Y1,i |M0 , M2 , Y1i−1 )

+ nδn,ǫ
(103)

where (a) uses (91) and (b) follows by the definition of
(Wi , Ui , Vi ). Moreover, we have
H(M2 |M0 )
(a)

≤ I(M2 ; Y2n |M0 ) + nδn,ǫ
n h
i
(b) X
n
n
I(M2 ; Y2,i
|M0 , Y1i−1 ) − I(M2 ; Y2,i+1
|M0 , Y1i )
=
i=1

n h
(c) X
n
I(M2 ; Y2,i+1
|M0 , Y1i−1 ) + I(Vi ; Y2,i |Wi )
=

(a)

i=1

n
I(M1 , Y2,i+1
; Y1,i |M0 , M2 , Y1i−1 ) + nδn,ǫ

+ nδn,ǫ

n(R0 + R1 ) = H(M0 , M1 )
≤ I(M0 , M1 ; Y1n ) + nδn,ǫ
n
(b) X
I(Wi , Ui ; Y1,i ) + nδn,ǫ
≤

=

n
X

i=1

(99)

n
− I(M2 ; Y1,i , Y2,i+1
|M0 , Y1i−1 )

i
+ I(M2 ; Y1,i |M0 , Y1i−1 ) + nδn,ǫ

18

nR2 ≤
nR2 ≤
n(R0 + R2 ) ≤
n(R0 + R2 ) ≤
n(R0 + R1 + R2 ) ≤
n(R0 + R1 + R2 ) ≤

n h
i
X
I(Vi ; Y2,i |Wi , Ui ) − I(Vi ; Y1,i |Wi , Ui ) + nL2 + nξn,ǫ
i=1
n h
X
i=1
n
X

=

I(Wi , Vi ; Y2,i ) + nδn,ǫ

i
I(Ui ; Y1,i |Wi ) + I(Vi ; Y2,i |Wi , Ui ) + I(Wi ; Y1,i ) + 3nδn,ǫ

i=1
n h
X

i
I(Ui ; Y1,i |Wi ) + I(Vi ; Y2,i |Wi , Ui ) + I(Wi ; Y2,i ) + 3nδn,ǫ

i

I(M2 ; Y1,i |M0 , Y1i−1 )

+ nδn,ǫ
(104)

n(R1 + R2 )
n h
X
I(Ui ; Y1,i |Wi , Vi ) + I(Vi ; Y2,i |Wi ) − I(Vi ; Y1,i |Wi )
≤
n h
X

i
n
+ I(M2 , Y2,i+1
; Y1,i |M0 , Y1i−1 ) + 2nδn,ǫ

I(Ui ; Y1,i |Wi , Vi ) + I(Vi ; Y2,i |Wi )

i=1

(108e)
(108f)

and

where:
(a) follows from (91);
(b) is a telescoping identity;
(c) is by the mutual information chain rule and the definition
of (Vi , Ui );
(d) uses the mutual information chain rule again. Combining
(103) and (104) yields

=

(108d)

i=1
n h
X

i=1

i=1

(108c)

i
I(Vi ; Y2,i |Wi ) + I(Wi ; Y1,i ) + nδn,ǫ

n h
X
I(Vi ; Y2,i |Wi ) − I(Vi ; Y1,i |Wi )

+

(108b)

i=1
n h
X

i=1

(d)

i
I(Vi ; Y2,i |Wi ) − I(Vi ; Y1,i |Wi ) + nL2 + nξn,ǫ

(108a)

i

n
+ I(Y2,i+1
; Y1,i |M0 , Y1i−1 )

+ 2nδn,ǫ.
(105a)

Applying Csiszár’s sum identity on the last term in (105a)
gives
n h
X
I(Ui ; Y1,i |Wi , Vi ) + I(Vi ; Y2,i |Wi )
n(R1 + R2 ) =

n(R0 + R1 + R2 ) ≤

n h
X
I(Ui ; Y1,i |Wi , Vi ) + I(Vi ; Y2,i |Wi )
i=1

i
+ I(Wi ; Y2,i ) + 3nδn,ǫ ,

(107)

respectively.
By repeating similar steps, we obtain bounds related to the
remaining rate bounds in (27) as given in (108a)-(108f) at the
top of this page.
The bounds are rewritten by introducing a time-sharing
random variable Q that is uniformly distributed over the set
[1 : n] and is independent of all the other random variables
whose distribution is described in (19). For instance, the bound
(97) is rewritten as
n
i
1 Xh
R1 ≤
I(Uq ; Y1,q |Wq , Vq ) − I(Uq ; Y2,q |Wq , Vq )
n q=1
+ L1 + ξn,ǫ
h
P Q = q I(UQ ; Y1,Q |WQ , VQ , Q = q)
=
i=q
i
− I(UQ ; Y2,Q |WQ , VQ , Q = q) + L1 + ξn,ǫ
n
X

≤ I(UQ ; Y1,Q |WQ , VQ , Q) − I(UQ ; Y2,Q |WQ , VQ , Q)
+ L1 + nξn,ǫ
(109)

i=1

i
n
+ I(Y1i−1 ; Y2,i |M0 , Y2,i+1
) + 2nδn,ǫ .
(105b)

Combining (95a) with (105a) and (96a) with (105b) yields
n h
X
I(Ui ; Y1,i |Wi , Vi )
n(R0 + R1 + R2 ) ≤
i=1

i
+ I(Vi ; Y2,i |Wi ) + I(Wi ; Y1,i ) + 3nδn,ǫ
(106)

Denote Y1 , Y1,Q , Y2 , Y2,Q , W , (WQ , Q), U , (UQ , Q)
and V , (VQ , Q). We thus have the bounds from (27) with
the added terms δn,ǫ and ξn,ǫ , which can be made arbitrarily
small by increasing the blocklength n while decreasing ǫ.
To complete the converse proof note that since the channel
is memoryless and without feedback, and because Uq =
(M1 , Wq ) and Vq = (M2 , Wq ), the chain
(Y1,q , Y2,q ) − Xq − (Uq , Vq ) − Wq

(110)

is Markov for every q ∈ [1 : n]. This implies that (Y1 , Y2 ) −

19

X − (U, V ) − W forms a Markov chain, which establishes
Theorem 3.
E. Proof of Theorem 4
The direct part of Theorem 4 follows by setting U0 = W ,
U1 = Y1 and U2 = V into CSD (L1 , L2 ), which establishes its
inclusion in RI (L1 , L2 ).
For the converse we prove the reverse inclusion, i.e.,
RO (L1 , L2 ) ⊆ CSD (L1 , L2 ). First we remove the restriction from RO (L1 , L2 ) that X − (U, V ) − W forms a
Markov chain; this can only increase the region. Fix a PMF
QW,U,V,X ∈ P(W×U ×V×X ), which induces a joint distribution QW,U,V,X 1{Y1 =y1 (X)} WY2 |X , and let QW,V,Y1 ,X WY2 |X
be its marginal PMF of (W, V, Y1 , X, Y2 ). Each of the
bounds defining RO (L1 , L2 ) are evaluated with respect to
QW,U,V,X 1{Y1 =y1 (X)} WY2 |X , while the information terms
from CSD (L1 , L2 ) are taken with respect to QW,V,Y1 ,X WY2 |X .
We start by noting that (29a) and (27a) are the same. Next,
the RHS of (27b) is upper bounded by the RHS of (29b) since
R1 ≤ I(U ; Y1 |W, V ) − I(U ; Y2 |W, V ) + L1
= H(Y1 |W, V ) − H(Y1 |W, V, U ) − I(U ; Y2 |W, V ) + L1
(a)

≤ H(Y1 |W, V ) − I(Y1 ; Y2 |W, V, U ) − I(U ; Y2 |W, V ) + L1

= H(Y1 |W, V ) − I(U, Y1 ; Y2 |W, V ) + L1
(b)

≤ H(Y1 |W, V, Y2 ) + L1

(111)

where (a) is by the non-negativity of entropy and (b) is because
conditioning cannot increase entropy.
For (27d) we clearly have
n
o
R0 + R1 ≤ I(U ; Y1 |W ) + min I(W ; Y1 ), I(W ; Y2 )
n
o
≤ H(Y1 |W ) + min I(W ; Y1 ), I(W ; Y2 ) , (112)
which coincides with (29c). Furthermore, inequalities (29d)
and (29e) are the same as (27f) and (27g), respectively. For
the sum of rates, the RHS of (29f) upper bounds that of (27h)
because
I(U ; Y1 |W, V ) ≤ H(Y1 |W, V ).
(113)

Removing the other bounds from (27) can only increase
RO (L1 , L2 ), which shows its inclusion in CSD (L1 , L2 ). This
characterizes CSD (L1 , L2 ) as the (L1 , L2 )-leakage-capacity
region of the SD-BC.
VIII. S UMMARY

AND

message that comprises the public parts and the common
message was constructed. To correlate the codewords for
the private parts, we used the likelihood encoder. Its simple
structure enabled a rigorous analysis of performance for the
proposed scheme. Theorem 1 fixes a weakness of previous
work by letting the eavesdropper know the codebook. The
main tool needed was the likelihood encoder (Lemma 3).
Our results include various past works as special cases.
Large leakage thresholds reduce our inner and outer bounds
to Marton’s inner bound with a common message [21] and
the UVW-outer bound [22], respectively. The leakage-capacity
region of the SD-BC without a common message recovers the
capacity regions where both [5], either [6], [27], or neither
[21] private message is secret. The result for the BC with a
degraded message set and a privacy leakage constraint captures
the capacity regions for the BC with confidential messages [3]
and the BC with a degraded message set (without secrecy)
[28]. Furthermore, we derived conditions on the allowed
leakage values that differentiates whether a further increase
of each leakage threshold induces a larger inner bound or
not. The conditions effectively let one (numerically) calculate
privacy leakage threshold values above which the inner bound
saturates. This idea was visualized by means of a BW-BC
example that showed the transition of the leakage-capacity
region from secrecy-capacity regions for different scenarios
to the capacity region without secrecy.

C ONCLUDING R EMARKS

We considered the BC with privacy leakage constraints.
Under this model, all four scenarios concerning secrecy (i.e.,
when both, either or neither of the private messages are
secret) are special cases by appropriate choices for the leakage
thresholds. Inner and outer bounds on the leakage-capacity
region were derived and shown to be tight for SD and PD
BCs, as well as for BCs with a degraded message set. The
coding strategy that achieved the inner bound is based on a
Marton-like codebook construction with a common message
supplemented by an extra layer of binning. Splitting each
private message into a public and a private part, a public

ACKNOWLEDGEMENTS
The authors would like to thank the Associate Editor and the
anonymous reviewers for helping to improve the presentation
of this paper. We also kindly thank Ido B. Gattegno for
his work on the FME-IT software [47] that assisted us with
technical details of proofs.
A PPENDIX A
P ROOF OF C OROLLARY 8
0
The region CD (L1 , L2 ) is obtained from CSD
(L1 , L2 ) by
setting W = 0 and V = Y2 , which implies that CD (L1 , L2 ) ⊆
0
CSD
(L1 , L2 ). For the converse, the RHS of (32a) is upper
bounded by

R1 ≤ H(Y1 |W, V, Y2 ) + L1 ≤ H(Y1 |Y2 ) + L1 .

(114)

For (32c), we have
I(V ; Y2 |W ) − I(V ;Y1 |W ) + L2
≤ I(V ; Y1 , Y2 |W ) − I(V ; Y1 |W ) + L2
= I(V ; Y2 |W, Y1 ) + L2
≤ H(Y2 |Y1 ) + L2 .

(115)

The RHSs of (32b) and (32d) are clearly upper bounded as
n
o
H(Yj |W ) + min I(W ; Y1 ), I(W ; Y2 ) ≤ H(Yj ), j = 1, 2.
(116)
Finally, (42c) is implied by (32e) since
R1 + R2

≤ H(Y1 |W, V ) + I(V ; Y2 |W ) + min I(W ; Y1 ), I(W ; Y2 )

20

E=

D0 =

n

n

o

U0 (1), U1 (1, 1, 1, I1 ), U2 (1, 1, 1, I2 ) ∈
/ Tδn′ (QU0 ,U1 ,U2 )

o

U0 (1), U1 (1, 1, 1, I1 ), U2 (1, 1, 1, I2 ), Y1 , Y2 ∈ Tδn (QU0 ,U1 ,U2 ,Y1 ,Y2 )
(j)

D0 (mp ) =
(j)

D1 (mjj , wj , ij ) =

n

n

(119a)

o

U0 (mp ), Yj ∈ Tδn (QU0 ,Yj )

(119b)

o

U0 (1), Uj (1, mjj , wj , ij ), Yj ∈ Tδn (QU0 ,Uj ,Yj )

= H(Y1 , Y2 ).

(119c)

[2]

≤ H(Y1 |W, V ) + I(W, V ; Y2 )
≤ H(Y1 , Y2 |W, V ) + I(W, V ; Y1 , Y2 )

4) For Pj , j = 1, 2, we have
[2]

Pj

(117)

(a)

≤

X

2−n

[2]

I(U0 ;Yj )−τj (δ)

m̃p 6=1

A PPENDIX B
E RROR P ROBABILITY A NALYSIS FOR THE P ROOF
T HEOREM 1

≤ 2nRp 2−n

[1]

1) By [32, Theorem 3], P0 → 0 as n → ∞ if
R1′ + R2′ > I(U1 ; U2 |U0 ).

(121)

2) The Conditional Typicality Lemma [20, Section 2.5]
[2]
implies that P0 → 0 as n grows. More precisely, there
exists a function β(n, δ, δ ′ ) with limn→∞ β(n, δ, δ ′ ) = 0
[2]
for any 0 < δ ′ < δ, such that P0 ≤ β(n, δ, δ ′ ).
′
Furthermore, replacing δ and δ with properly chosen
decaying sequences {δn }n∈N and {δn′ }n∈N , respectively,
and setting βn , β(n, δn , δn′ ), we have limn→∞ βn = 0.
[1]
[0]
3) The definitions in (119) clearly give Pj = Pj =
0, for j = 1,o2 andn every n ∈ N. This
o is since
n
(j)
(j)
D0 (1)c ∩ D0 = D1 (1, 1, Ij )c ∩ D0 = ∅, for
j = 1, 2.
in Section VII-B, we slightly abuse notation in writing EPe (Cn )
because Pe is actually a function of the code cn rather than the codebook
Cn . We favor this notation for its simplicity and remind the reader that Cn
uniquely defines cn .

[2]

I(U0 ;Yj )−τj (δ)
[2]

Rp −I(U0 ;Yj )+τj (δ)

= 2n

OF

By the symmetry of the codebook construction with respect
to (Mp , M11 , W1 , M22 , W2 ) and due to their uniformity, we
may assume that (Mp , M11 , W1 , M22 , W2 ) = (1, 1, 1, 1, 1).
Encoding errors: Fix any δ ′ ∈ (0, δ). An encoding error
event is described as given in (118) at the top of this page.
Decoding errors: To account for decoding errors, define
(119) from the top of this page, where j = 1, 2.
For any event A from the σ-algebra over which P is
defined, denote P1 = P A Mp = 1, M11 = 1, W1 =
1, M22 = 1, W2 = 1 . By the union bound, the expected
error probability is bounded as in (120), given at the top of
the next page.7 Note that with respect to the notation in (120),
[k]
[1]
P0 is the probability of an encoding error, while Pj , for
k ∈ [0 : 3], are the decoding errors of Decoder j. We proceed
with the following steps:

7 As

(118)







(122)

where (a) follows since U0 (m̃p ) is independent of Yj ,
[2]
for any m̃p 6= 1. Thus, for Pj to vanish as n → ∞,
we take:
[2]

Rp < I(U0 ; Yj ) − τj (δ),

j = 1, 2.

(123)

[2]

where τj (δ) → 0 as δ → 0.
[3]
5) For Pj , j = 1, 2, we have
[3]

Pj

(a)

X

[3]

2−n

I(Uj ;Yj |U0 )−τj (δ)

≤ 2n(Rjj +Rj +R̃j ) 2−n

I(Uj ;Yj |U0 )−τj (δ)

≤

(m̃jj ,w̃j )6=(1,1),
ĩj ∈Ij
′

= 2n

[3]

[3]

Rjj +R′j +R̃j −I(Uj ;Yj |U0 )+τj (δ)







(124)

where (a) follows since Uj (1, m̃jj , w̃j , ĩj ) is independent of Yj , for any (m̃jj , w̃j ) 6= (1, 1) and ĩj ∈ Ij ,
while both of them are drawn conditioned on U0 (1).
[3]
We have Pj → 0 as n → ∞ if
[3]

Rjj + Rj′ + R̃j < I(Uj ; Yj |U0 ) − τj (δ),
[3]

j = 1, 2,
(125)

where, as before, τj (δ) → 0 as δ → 0.
Summarizing the above results, while substituting Rp =
R0 + R10 + R20 and setting
o
n
[k]
τδ , max τj (δ) j=1,2,
(126)
k=2,3

we find that
EPe (Cn ) ≤ η(n, δ, δ ′ ),

∀n ∈ N,

(127)

where limn→∞ η(n, δ, δ ′ ) = 0 for all 0 < δ ′ < δ, if
the conditions in (68) are met. As mentioned before, if we
replace δ and δ ′ with properly chosen sequences {δn }n∈N and
{δn′ }n∈N , respectively, that decay sufficiently slowly to zero

21

EPe (Cn )



c
≤ P1 
E ∪ D0 ∪




[ 


j=1,2 


(j)

D0 (1)c ∪



 [


m̃p 6=1





(j)
(j)
D0 (m̃p ) ∪ D1 (1, 1, Ij )c ∪







[
(j)

D0 (m̃jj , w̃j , Ij )




(m̃jj ,w̃j )6=(1,1)







X 
[ (j)

(j)
(j)
 P1 D (1)c ∩ D0 + P1 D (1, 1, Ij )c ∩ D0 + P1 
≤ P1 E + P1 D0c ∩ E +
D0 (m̃p )
0
1
| {z } |
{z
} j=1,2 
|
|
{z
}
{z
}
m̃p 6=1
[1]
[2]
[0]
[1]
P0
P0
{z
}
|
Pj
Pj



c

[2]

PJ




[


(j)
D1 (m̃jj , w̃j , ĩj ) 
+ P1 



(m̃jj ,w̃j )6=(1,1),


(120)

ĩj ∈Ij

|

and set ηn , η(n, δn , δn′ ), we have limn→∞ ηn = 0.
A. Leakage Associated Errors
(1)

This subsection shows how (71) ensures Eλm11 (Cn ) → 0
as n → ∞, for any m11 ∈ M11 . As before, by the symmetry
of the underlying random code with respect to the messages,
we have
(1)

Eλ(1)
m11 (Cn ) = Eλ1 (Cn ),

∀m11 ∈ M11 ,

(129a)

where ξ(δ) → 0 as δ → 0, results in a vanishing probability
of the event that this u1 -sequence satisfies the typicality test
from (69).
Furthermore, if w̃1 and ĩ1 are both incorrect,
U1 (1, 1, w̃1 , ĩ1 )
conditionally
independent
of
is
U2 (1, 1, 1, I2 ), Y2 given U0 (1). The search space is
′
now of size 2n(R̃1 +R1 ) , and therefore, taking
R̃1 + R1′ < I(U1 ; U2 , Y2 |U0 ) − ξ(δ)

[3]

}

implies a vanishing probability of this second error event.
Finally, note that the error event where W1 = 1 is
correct but ĩ1 is wrong has arbitrarily small probability if
R1′ < I(U1 ; U2 , Y2 |U0 ) − ξ(δ) (the structure of the mutual
information term is the same as in (129b) because an incorrect
ĩ1 produces the same statistical relations as an incorrect pair
(w̃1 , ĩ1 )). Evidently, the latter constraint is redundant due to
(129b).

(128)

and we may further assume that (Mp , W1 , M22 , W2 ) =
(1, 1, 1, 1). By arguments similar to those presented in the
encoding and decoding error probability analysis, one can
verify that (71) implies the existence of a function κ(n, δ) with
(1)
limn→∞ κ(n, δ) = 0 for any δ > 0, such that Eλ1 (Cn ) ≤
κ(n, δ). Furthermore, replacing δ with a sequence {δn }n∈N
that decays sufficiently slow to zero as n grows and setting
κn , κ(n, δn ), we have κn → 0 as n → ∞.
This essentially follows by the law of large numbers and
the Conditional Typicality Lemma that ensure the joint typicality of the transmitted sequences and the outputs. If w̃1
is incorrect but I1 is the true index chosen by the likelihood encoder, U1 (1, 1, w̃1 , I1 ) is conditionally independent
Y2 given (U0 (1), U2 (1, 1, 1, I2 )). The correlation between
U0 (1), U1 (1, 1, w̃1 , I1 ) and U2 (1, 1, 1, I2 ) is a consequence
of the likelihood encoder’s operation. Since the search space
in this case is of size 2nR̃1 , taking
R̃1 < I(U1 ; Y2 |U0 , U2 ) − ξ(δ)

{z

Pj

(129b)

A PPENDIX C
P ROOF OF L EMMA 4
(Leak)

Recall that P1
(Cn ) denotes the error probability in decoding (W1 , I1 ) from (Mp , M11 , M22 , W2 , I2 , Y2 ) by means
of the typicality test from (69) with respect to the fixed code
Cn ∈ Cn . The analysis in Appendix B shows that as long as
(71) holds, we have
(Leak)

EP1

(Cn ) ≤ κ(n, δ, δ ′ )

(130)

where limn→∞ κ(n, δ, δ ′ ) = 0 for all 0 < δ ′ < δ. As a
consequence, we have
H(W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 , Cn )
≤ H(W1 , I1 |Mp , M11 , M22 , W2 , I2 , Y2 )
(a)

≤ 1 + n · κ(n, δ, δ ′ )n(R̃1 + R1′ )

(131)

where (a) is because conditioning cannot increase entropy, while (b) uses Fano’s inequality and (130). Setting
ζ1 (n, δ, δ ′ ) , n1 + κ(n, δ, δ ′ )(R̃1 + R1′ ) completes the proof.
A PPENDIX D
P ROOF OF L EMMA 5
Define the indicator function E = 1A , where
o
n
(132)
A = (U0 , U1 , U2 , Y2 ) ∈
/ Tδn (QU0 ,U1 ,U2 ,Y2 )



and note that P E = 1 ≤ P1 E + P1 D0c ∩ E c , where E
and D0 are defined in (118) and (119a), respectively, from

22

H(Y1 |U0 , U1 , U2 , E = 0, Cn )
(a)

= H(Y1 |U0 , U1 , U2 , E = 0)
X
PU0 ,U1 ,U2 |E (u0 , u1 , u2 |0)H(Y2 |U0 = u0 , U1 = u1 , U2 = u2 , E = 0)
=
(u0 ,u1 ,u2 )
∈Tδn (QU0 ,U1 ,U2 )

=

X

PU0 ,U1 ,U2 |E (u0 , u1 , u2 |0)

=

X

PU0 ,U1 ,U2 |E (u0 , u1 , u2 |0)

X

PU0 ,U1 ,U2 |E (u0 , u1 , u2 |0)

≥ n·

X

H(Y2,i |U0,i = u0,i , U1,i = u1,i , U2,i = u2,i )

X

νu0 ,u1 ,u2 (u0 , u1 , u2 )H(Y2 |U0 = u0 , U1 = u1 , U2 = u2 )

(u0 ,u1 ,u2 )
∈U0 ×U1 ×U2

(u0 ,u1 ,u2 )
∈Tδn (QU0 ,U1 ,U2 )
(c)

n
X
i=1

(u0 ,u1 ,u2 )
∈Tδn (QU0 ,U1 ,U2 )

=

H(Y2,i |U0 = u0 , U1 = u1 , U2 = u2 , Y2i−1 , E = 0)

i=1

(u0 ,u1 ,u2 )
∈Tδn (QU0 ,U1 ,U2 )
(b)

n
X

PU0 ,U1 ,U2 |E (u0 , u1 , u2 |0)(1 − δ)H(Y2 |U0 , U1 , U2 )

(u0 ,u1 ,u2 )
∈Tδn (QU0 ,U1 ,U2 )

= n(1 − δ)H(Y2 |U0 , U1 , U2 )

(137)

Appendix B. The analysis in Appendix B shows the existence
of a function β̃(n, δ, δ ′ ), such that



P E = 1 = P1 E + P1 D0c ∩ E c ≤ β̃(n, δ, δ ′ ) (133)

where 0 < δ ′ < δ and limn→∞ β̃(n, δ, δ ′ ) = 0 for all such
values of δ and δ ′ . Furthermore, limn→∞ β̃(n, δn , δn′ ) = 0 for
sequences {δn }n∈N and {δn′ }n∈N that decay sufficiently slow
to zero with n.
We now expand the mutual information term from the LHS
of (73) as follows
I(U1 ; Y2 |U0 , U2 , Cn )
≤ I(U1 , E; Y2 |U0 , U2 , Cn )
= I(E; U2 |U0 , , U2 , Cn ) + I(U1 ; Y2 |U0 , U2 , E, Cn )
(a)

≤ 1+

1
X
j=0


P E = j I(U1 ; Y2 |U0 , U2 , E = j, Cn ). (134)

where (a) is because E is binary and the entropy function is
non-negative. Note that

P E = 1 I(U1 ; Y2 |U0 , U2 , E = 1, Cn )

≤ P E = 1 H(Y2 |E = 1, Cn )
≤ β̃(n, δ, δ ′ ) · n log |Y2 |.

(135)

where (a) uses (133).
For the mutual information term conditioned on E = 0, we
first have
H(Y2 |U0 , U2 , E = 0, Cn )
≤ H(Y2 |U0 , U2 , E = 0)
X
QU0 ,U2 |E (u0 , u2 |0)H(Y2 |U0 = u0 , U2 = u2 , E = 0)
=

(u0 ,u2 )
∈Tδn (QU0 ,U2 )

≤ nH(Y2 |U0 , U2 )

(136)

where the last inequality is because for every
(u0 , u2 ) ∈ Tδn (QU0 ,U2 ) the support of the conditional
PMF PY2 |U0 =u0 ,U2 =u2 ,E=0 is upper bounded by the size of
the conditional typical set Tδn (QU0 ,U2 ,Y2 |u0 , u2 ), which is
upper bounded by 2nH(Y2 |U0 ,U2 )(1+δ) . This step also relies
on the entropy being maximized by the uniform distribution
and the logarithm being a monotonically increasing function.
For the other (subtracted) entropy term, we have (137)
given at the top of this page, where (a) is because Y2 −
(U0 , U1 , U2 ) − Cn forms a Markov chain, (b) follows since
given (U0,i , U1,i , U2,i ), Y2,i is independent of all other random variables, while (c) is by the definition of letter-typical
sequences from (3).
Inserting (135), (136) and (137) into (134) gives
I(U1 ; Y2 |U0 , U2 , Cn ) ≤ nI(U1 ; Y2 |U0 , U2 ) + nζ2 (n, δ, δ ′ )
(138)
where
1
ζ2 (n, δ, δ ′ ) = + δH(Y2 |U0 , U1 , U2 ) + β̃(n, δ, δ ′ ) (139)
n
as needed.
A PPENDIX E
P ROOF OF L EMMA 6
Rewriting the mutual information term of interest as a
difference of entropies, we have
I(U1 ; M22 , W2 , I2 |Mp , Cn )
= H(U1 |Mp , Cn ) − H(U1 |Mp , M22 , W2 , I2 , Cn ). (140)
Since U0 is defined by (Mp , Cn ) we clearly have,
H(U1 |Mp , Cn ) ≤ H(U1 |U0 , Cn ).

(141)

23

n
D̃ , ∃(m̃p , m̃22 , w̃2 , ĩ2 ) 6= (Mp , M22 , W2 , I2 ),
Next, since (Mp , M22 , W2 , I2 , Cn ) determines both U0 and
U2 , we write the subtracted entropy term as
H(U1 |Mp , M22 , W2 , I2 , Cn )
= H(U1 |U0 , U2 , Mp , M22 , W2 , I2 , Cn )
= H(U1 |U0 , U2 , Cn )−I(U1 ; Mp , M22 , W2 , I2 |U0 , U2 , Cn )
≥ H(U1 |U0 , U2 , Cn ) − H(Mp , M22 , W2 , I2 |U0 , U2 , Cn ).
(142)
We now upper bound H(Mp , M22 , W2 , I2 |U0 , U2 , Cn ) by
a vanishing term times the blocklength n. Let F = 1D̃ be the
indicator function to the event D̃ defined in (143) at the top of
this page. Standard error probability analysis of random codes
shows that



′
P F = 1 = P D̃ ≤ 2n Rp +R22 +R̃2 +R2 −H(U0 ,U2 )+α̃(δ)
(144)
where α̃(δ) → 0 as δ → 0. Consequently, taking
Rp + R22 + R̃2 + R2′ < H(U0 , U2 ) − α̃(δ)
(145)

results in P F = 1 ≤ κ̃(n, δ) with limn→∞ κ̃(n, δ) = 0 for
every δ > 0. Next, note that (145) holds on account of (68c)
and (68e) (adding (68c) and (68e) results in a tighter bound
on the same rates) and consider the following:
H(Mp , M22 , W2 , I2 |U0 , U2 , Cn )
≤ H(Mp , M22 , W2 , I2 |U0 , U2 )
(a)

≤ 1 + H(Mp , M22 , W2 , I2 |U0 , U2 , F )

= 1 + P F = 0 H(M
 p , M22 , W2 , I2 |U0 , U2 , F = 0)
+ P F = 1 H(Mp , M22 , W2 , I2 |U0 , U2 , F = 1)
(b)

≤ 1 + H(Mp , M22 , W2 , I2 |U
 0 , U2 , F = 0)
+ P F = 1 · n(Rp + R22 + R̃2 + R2′ )
i
(c) h
≤ 2 1 + n · κ̃(n, δ)(Rp + R22 + R̃2 + R2′ )
(1)

= nζ̃3 (n, δ)

(146)

where
1
+ κ̃(n, δ)(Rp + R22 + R̃2 + R2′ ). (147)
n
In the above derivation (a) follows because the uniform
distribution maximizes entropy and since F is binary, (b) upper
bounds the first entropy term by the logarithm of the support
size, while (c) uses Fano’s inequality.
Inserting (141), (142) and (146) into (140) gives
(1)

ζ̃3 (n, δ) ,

(1)

I(U1 ;M22 ,W2 , I2 |Mp ,Cn) ≤ I(U1 ;U2 |U0 ,Cn)+nζ̃3 (n,δ).
(148)
To complete the proof, it suffices to show that there exists
(2)
a function ζ̃3 (n, δ, δ ′ ) that satisfies the same properties as
′
ζ3 (n, δ, δ ) from the statement of Lemma 6 for which
(2)

I(U1 ; U2 |U0 , Cn ) ≤ nI(U1 ; U2 |U0 ) + nζ̃3 (n, δ, δ ′ ). (149)

U0 (m̃p ) = U0 and U2 (m̃p , m̃22 , w̃2 , ĩ2 ) = U2

o

(143)

This can be established by arguments similar to those presented in the proof of Lemma 5 and we therefore omit the
details. Combining (148) with (149) and setting ζ3 (n, δ, δ ′ ) ,
(1)
(2)
ζ̃3 (n, δ) + ζ̃3 (n, δ, δ ′ ) completes the proof.
R EFERENCES
[1] C. E. Shannon. Communication theory of secrecy systems. Bell Sys.
Techn., 28(4):656715, Oct. 1949.
[2] A. D. Wyner. The wire-tap channel. Bell Sys. Techn., 54(8):1355–1387,
Oct. 1975.
[3] I. Csiszár and J. Körner. Broadcast channels with confidential messages.
IEEE Trans. Inf. Theory, 24(3):339–348, May 1978.
[4] R. Liu, I. Maric, P. Spasojević, and R. D. Yates. Discrete memoryless
interference and broadcast channels with confidential messages: Secrecy
rate regions. IEEE Trans. Inf. Theory, 54(6):2493–2507, Jun. 2008.
[5] Y. Zhao, P. Xu, Y. Zhao, W. Wei, and Y. Tang. Secret communications over semi-deterministic broadcast channels. In Fourth Int. Conf.
Commun. and Netw. in China (CHINACOM), Xi’an, China, Aug. 2009.
[6] W. Kang and N. Liu. The secrecy capacity of the semi-deterministic
broadcast channel. In Proc. Int. Symp. Inf. Theory, Seoul, Korea, Jun.Jul. 2009.
[7] Z. Goldfeld, G. Kramer, H. H. Permuter, and P. Cuff. Strong secrecy
for cooperative broadcast channels. IEEE Trans. Inf. Theory, 63(1):469–
495, Jan. 2017.
[8] E. Ekrem and S. Ulukus. Secrecy in cooperative relay broadcast
channels. IEEE Trans. Inf. Theory, 57(1):137–155, Jan. 2011.
[9] R. Liu and H. Poor. Secrecy capacity region of a multiple-antenna
Gaussian broadcast channel with confidential messages. IEEE Trans.
Inf. Theory, 55(3):1235–1249, Mar. 2009.
[10] T. Liu and S. Shamai. A note on the secrecy capacity of the multipleantenna wiretap channel. IEEE Trans. Inf. Theory, 6(6):2547–2553, Jun.
2009.
[11] R. Liu, T. Liu, H. V. Poor, and S. Shamai. Multiple-input multipleoutput Gaussian broadcast channels with confidential messages. IEEE
Trans. Inf. Theory, 56(9):4215–4227, Sep. 2010.
[12] A. Khisti and G. W. Wornell. Secure transmission with multiple antennas
- part II: The MIMOME channel. IEEE Trans. Inf. Theory, 56(11):5515–
5532, Nov. 2010.
[13] E. Ekrem and S. Ulukus. The secrecy capacity region of the Gaussian MIMO multi-receiver wiretap channel. IEEE Trans. Inf. Theory,
57(4):2083–2114, Apr. 2011.
[14] F. Oggier and B. Hassibi. The secrecy capacity of the MIMO wiretap
channel. IEEE Trans. Inf. Theory, 57(8):4961–4972, Aug. 2011.
[15] E. Ekrem and S. Ulukus. Secrecy capacity of a class of broadcast
channels with an eavesdropper. EURASIP J. Wireless Commun. and
Netw., 2009(1):1–29, Mar. 2009.
[16] G. Bagherikaram, A. Motahari, and A. Khandani. Secrecy capacity
region of Gaussian broadcast channel. In 43rd Annual Conf. on Inf. Sci.
and Sys. (CISS) 2009, pages 152–157, Baltimore, MD, US, Mar. 2009.
[17] M. Benammar and P. Piantanida. Secrecy capacity region of some
classes of wiretap broadcast channels.
IEEE Trans Inf. Theory,
61(10):5564–5582, Oct. 2015.
[18] K. Marton. A coding theorem for the discrete memoryless broadcast
channel. IEEE Trans. Inf. Theory, 25(3):306–311, May 1979.
[19] A. El Gamal and E. C. Van Der Meulen. A proof of Marton’s coding
theorem for the discrete memoryless broadcast channel. IEEE Trans.
Inf. Theory, 27(1):120–122, Jan. 1981.
[20] A. El Gamal and Y.-H. Kim. Network Information Theory. Cambridge
University Press, 2011.
[21] S. I. Gelfand and M. S. Pinsker. Capacity of a broadcast channel with one
deterministic component. Prob. Pered. Inf. (Problems of Inf. Transm.),
16(1):17–25, Jan-Mar 1980.
[22] C. Nair. A note on outer bounds for broadcast channel. Presented at Int. Zurich Seminar, Jan. 2011. Available on ArXiV at
http://arXiv.org/abs/1101.0640.
[23] G. Kramer Y. Liang and S. Shamai. Capacity outer bounds for broadcast
channels. In IEEE Inf. Theory Workshop (ITW-2008), Porto, Portugal,
2008.

24

[24] Y. Liang. Multiuser communications with relaying and user cooperation.
PhD thesis, Dept. of Electrical and Computer Eng., Univ. Illinois at
Urbana-Champaign, Illinois, 2005.
[25] C. Nair and A. El Gamal. An outer bound to the capacity region of the
broadcast channel. IEEE Trans. Inf. Theory, 53(1):350–355, Jan. 2007.
[26] C. Nair and V. W. Zizhou. On the inner and outer bounds for 2-receiver
discrete memoryless broadcast channels. In Inf. Theory and Applic.
Workshop, San Diego, California, US, Jan. 27-Feb. 1 2008.
[27] Z. Goldfeld, G. Kramer, and H. H. Permuter. Cooperative broadcast
channels with a secret message. In Proc. Int. Symp. Inf. Theory (ISIT2015), pages 1342–1346, Hong Kong, China, Jun. 2015.
[28] J. Körner and K. Marton. General broadcast channels with degraded
message sets. IEEE Trans. Inf. Theory, 23(1):60–64, Jan. 1977.
[29] E. C. van der Meulen. Random coding theorems for the general discrete
memoryless broadcast channel. IEEE Trans. Inf. Theory, IT-21(2):180–
190, May 1975.
[30] S. I. Gelfand. Capacity of one broadcast channel. Probl. Peredachi Inf.,
13(3):106108, Jul./Sep. 1977.
[31] J. L. Massey. Applied Digital Information Theory. ETH Zurich, Zurich,
Switzerland, 1980-1998.
[32] M. H. Yassaee. One-shot achievability via fidelity. In Proc. Int. Symp.
Inf. Theory (ISIT-2015), pages 301–305, Hong Kong, China, Jun. 2015.
[33] M. H. Yassaee, M. R. Aref, and A. Gohari. Achievability proof
via output statistics of random binning. IEEE Trans. Inf. Theory,
60(11):6760–6786, Nov. 2014.
[34] E. Song, P. Cuff, and V. Poor. The likelihood encoder for lossy
compression. IEEE Trans. Inf. Theory, 62(4):1836–1849, Apr. 2016.
[35] Z. Goldfeld, P. Cuff, and H. H. Permuter. Wiretap channels with random
states non-causally available at the encoder. Submitted for publication
to IEEE Trans. Inf. Theory, 2016. https://arxiv.org/abs/1608.00743.
[36] M. H. Yassaee, M. R. Aref, and A. Gohari. A technique for deriving
one-shot achievability results in network information theory. In Proc.
Int. Symp. Inf. Theory (ISIT-2013), Istanbul, Turkey, Jul. 2013. Full
version available on ArXiv at http://arxiv.org/abs/1303.0696.
[37] Y. Liang and G. Kramer. Rate regions for relay broadcast channels.
IEEE Trans. Inf. Theory, 53(10):3517–3535, Oct 2007.
[38] G. Kramer Y. Liang and H. V. Poor. On the equivalence of two
achievable regions for the broadcast channel. IEEE Trans. Inf. Theory,
57(1):95–100, Jan. 2011.
[39] H. Weingarten, Y. Steinberg, and S. Shamai. The capacity region of the
Gaussian multiple-input multiple-output broadcast channel. IEEE Trans.
Inf. Theory, 52(9):3936–3964, Sep. 2006.
[40] R. Liu, T. Liu, H. V. Poor, and S. Shamai. Multiple-input multipleoutput Gaussian broadcast channels with confidential messages. IEEE
Trans. Inf. Theory, 56(9):4215–4227, Sep. 2010.
[41] E. Ekrem and S. Ulukus. Capacity region of Gaussian MIMO broadcast
channels with common and confidential messages. IEEE Trans. Inf.
Theory, 58(9):5669–5680, Sep. 2012.
[42] Y. Geng and C. Nair. The capacity region of the two-receiver vector
Gaussian broadcast channel with private and common messages. IEEE
Trans. Inf. Theory, 60(4):2087–2014, Apr. 2014.
[43] Z. Goldfeld and H. H. Permuter. MIMO Gaussian broadcast channels
with common, private and confidential messages. Submitted to IEEE
Trans. Inf. Theory, 2016.
[44] A. Gohari, C. Nair, and V. Anantharam. Improved cardinality bounds
on the auxiliary random variables in Marton’s inner bound. In Proc. Int.
Symp. Inf. Theory (ISIT-2013), Istanbul, Turkey, Jul. 2013.
[45] J. Hou and G. Kramer. Effective secrecy: Reliability, confusion and
stelth. In IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jun.-Jul.
2014.
[46] Z. Goldfeld, P. Cuff, and H. H. Permuter. Semantic-security capacity for
wiretap channels of type II. IEEE Trans. Inf. Theory, 62(5):2285–2307,
May 2016.
[47] I. B. Gattegno, Z. Goldfeld, and H. H. Permuter. Fourier-Motzkin
Elimination software for information theoretic inequalities. IEEE Inf.
Theory Society Newsletter, 65(3):25–28, Sep. 2015. Version R0.6
Available at http://www.ee.bgu.ac.il/˜ fmeit/.
[48] G. Kramer. Teaching IT: An identity for the Gelfand-Pinsker converse.
IEEE Inf. Theory Society Newsletter, 61(4):4–6, Dec. 2011.

Ziv Goldfeld (S’13) received his B.Sc. (summa cum laude) and M.Sc. (summa
cum laude) degrees in Electrical and Computer Engineering from the BenGurion University, Israel, in 2012 and 2014, respectively. He is currently

a student in the direct Ph.D. program for honor students in Electrical and
Computer Engineering at that same institution.
Between 2003 and 2006, he served in the intelligence corps of the Israeli
Defense Forces.
Ziv is a recipient of several awards, among them are the Dean’s List Award,
the Basor Fellowship, the Lev-Zion fellowship, IEEEI-2014 best student paper
award, a Minerva Short-Term Research Grant (MRG), and a Feder Family
Award in the national student contest for outstanding research work in the
field of communications technology.

Gerhard Kramer (S’91-M’94-SM’08-F’10) received the Dr. sc. techn. (Doktor der technischen Wissenschaften) degree from the Swiss Federal Institute
of Technology (ETH), Zurich, in 1998.
From 1998 to 2000, he was with Endora Tech AG, Basel, Switzerland,
as a Communications Engineering Consultant. From 2000 to 2008, he was
with Bell Labs, Alcatel-Lucent, Murray Hill, NJ, as a Member of Technical
Staff. He joined the University of Southern California (USC), Los Angeles,
in 2009. Since 2010, he has been a Professor and Head of the Institute for
Communications Engineering at the Technical University of Munich (TUM),
Munich, Germany.
Dr. Kramer served as the 2013 President of the IEEE Information Theory
Society. He has won several awards for his work and teaching, including an
Alexander von Humboldt Professorship in 2010 and a Lecturer Award from
the Student Association of the TUM Electrical and Computer Engineering
Department in 2015. He has been a member of the Bavarian Academy of
Sciences and Humanities since 2015.

Haim H. Permuter (M’08-SM’13) received his B.Sc. (summa cum laude) and
M.Sc. (summa cum laude) degrees in Electrical and Computer Engineering
from the Ben-Gurion University, Israel, in 1997 and 2003, respectively, and the
Ph.D. degree in Electrical Engineering from Stanford University, California
in 2008.
Between 1997 and 2004, he was an officer at a research and development
unit of the Israeli Defense Forces. Since 2009 he is with the department of
Electrical and Computer Engineering at Ben-Gurion University where he is
currently an associate professor.
Prof. Permuter is a recipient of several awards, among them the Fullbright
Fellowship, the Stanford Graduate Fellowship (SGF), Allon Fellowship,
and and the U.S.-Israel Binational Science Foundation Bergmann Memorial
Award. Haim is currently serving on the editorial board of the IEEE Transactions on Information Theory.

