1

Time-Division Transmission is Optimal for Covert
Communication over Broadcast Channels

arXiv:1710.09754v1 [cs.IT] 26 Oct 2017

Vincent Y. F. Tan† and Si-Hyeon Lee‡

Abstract—We consider a covert communication scenario where
a legitimate transmitter wishes to communicate simultaneously to
two legitimate receivers while ensuring that the communication
is not detected by an adversary, also called the warden. The
legitimate receivers and the adversary observe the transmission
from the legitimate transmitter via a three-user discrete or
Gaussian memoryless broadcast channel. We focus on the case
where the “no-input” symbol is not redundant, i.e., the output
distribution at the warden induced by the no-input symbol is
not a mixture of the output distributions induced by other input
symbols, so that the covert communication
is governed by the
√
square root law, i.e., at most Θ( n) bits can be transmitted
over n channel uses. We show that for such a setting of covert
communication over broadcast channels, a simple time-division
strategy achieves the optimal throughputs. Our result implies
that a code that uses two separate optimal point-to-point codes
each designed for the constituent channels and each used for a
fraction of the time is√ optimal in the sense that it achieves the
best constants of the n-scaling for the throughputs. Our proof
strategy combines several elements in the network information
theory literature, including concave envelope representations of
the capacity regions of broadcast channels and El Gamal’s outer
bound for more capable broadcast channels.
Index Terms—Covert communication, Low probability of detection, Broadcast channels, Time-division, Concave envelopes

I. I NTRODUCTION
There has been a recent surge of research interest in reliable
communications in the presence of an adversary, or a warden,
who must be kept incognizant of the presence of communication between the legitimate transmitters and receivers.
The lack of communication is modelled in discrete channels
by sending a specially-designed “no-input” symbol 0 ∈ X
(where X , a finite set, is the input alphabet of the discrete
channel); in Gaussian channels, it is also modelled as sending
0 ∈ R. This line of research, known synonymously as covert
communications, low probability or detection (LPD) [1]–
[3], deniability [4], [5], or undetectable communication [6],
seeks to establish fundamental limits on the throughputs to
communicate to the legitimate receiver(s) while ensuring that
the signals observed by the warden are statistically close
to the signals if communication were not present. It was
shown by Bash et al. [1] that in the point-to-point setting,
if the legitimate user’s channel and the adversary’s channel
are perfectly known, the number of bits that can be reliably
† Vincent Y. F. Tan is with the Department of Electrical and Computer
Engineering and the Department of Mathematics, National University of
Singapore, Singapore 117583 (Email: vtan@nus.edu.sg).
‡ Si-Hyeon Lee (Corresponding author) is with the Department of Electrical
Engineering, Pohang University of Science and Technology (POSTECH),
Pohang, South Korea 37673 (Email: sihyeon@postech.ac.kr).

and√covertly transmitted over n channel uses scales at most as
Θ( n) for additive white Gaussian noise (AWGN) channels.
This is colloquially known as the “square root law”. For
discrete memoryless channels, the covert communication is
also governed by the square root law if the no-input symbol
is not redundant, i.e., the output distribution at the warden
induced by the no-input symbol is not a mixture of the
output distributions induced by other√input symbols. Recently,
the optimal pre-constant in the Θ( n) term has also been
established in a couple of elegant papers by Bloch [7] and
Wang, Wornell and Zheng [8].
In this paper, we are interested in extending the above
model and results to a multi-user (or network) scenario [9]
in which there is one legitimate transmitter, two legitimate
receivers and, as usual, one warden. See Fig. 1. We are
interested in communicating reliably and simultaneously to
the two receivers over the same medium while ensuring that
the warden remains incognizant of the presence of any communication. We call our model a two-user discrete memoryless
broadcast channel (BC) with a warden. This communication
model mimics the scenario of a military general delivering
commands to her/his multiple subordinates while, at the same
time, ensuring that the probability of the communication being
detected by a furtive enemy, the warden, is vanishingly small.
Note that the enemy is not interested in the precise commands
per se but on whether or not communication between the
general and her/his subordinates is actually happening in order
to pre-empt a possible attack. We establish the fundamental
performance limits for communicating in this scenario when
the no-input symbol is not redundant. Somewhat surprisingly,
we show that the most basic multi-user communication scheme
of time-division [9, Sec. 5.2] is optimal. This implies that a
code designed for the BC that uses two separate point-to-point
codes, each designed for the constituent channels and each
used for a fraction of the time (blocklength) is √
optimal in the
sense that it achieves the best constants of the n-scaling of
the throughput.
A. Related Work
As mentioned, there has been a flurry of recent work
on covert communications. In particular, refined asymptotics
on the fundamental limits of covert communications over
memoryless channels from the second-order [10] and error
exponent [11] perspectives have been studied. In addition,
the fundamental limits of covert communications for channels
with random state known at the transmitter [12] and classicalquantum channels [13] have also been established. In contrast,

2

work on multi-user extensions of covert communications is
relatively sparse. Of note are the works by Arumugam and
Bloch [14], [15]. In [14], the authors derived the fundamental limits of covert communications over a multiple-access
channel (MAC). The authors showed that if the MAC to the
legitimate receiver is “better”, in a precise sense, than the
one to the adversary, then the legitimate
users can reliably
√
communicate on the order of Θ( n) bits per n channel uses
with arbitrarily LPD without using a secret key. The authors
also quantified the pre-constant terms exactly. In [15], the
authors considered a BC communication model. However, note
that the model in [15] is significantly different from that in the
present work. In [15], the authors were interested in transmitting two messages, one common and another covert, over a BC
where there are two receivers, one legitimate and the other the
warden. The common message is to be communicated to both
parties, while the covert message has LPD from the perspective
of the warden. This models the scenario of embedding covert
messages in an innocuous codebook and generalizes existing
works on covert communications in which innocent behavior
corresponds to lack of communication between the legitimate
receivers. In our work, there are three receivers, two legitimate
and the other denotes the warden. Both messages that are
communicated can be considered as covert message from the
perspective of the warden. See Fig. 1 for our model.
B. Main Contribution
Our main contribution is to establish the covert capacity
region (the set of all achievable
pre-constants of the through√
puts which scale as Θ( n)) of the two-user (discrete and
Gaussian) memoryless BC with a warden when the no-input
symbol is not redundant. While the (usual) capacity region of
the two-user discrete memoryless BC is a long-standing open
problem in network information theory, we show that under the
covert communications constraint, the covert capacity region
admits a particularly simple expression. This region implies
that time-division transmission is optimal for all two-user BCs.
We emphasize that no restriction on the BC is required. In
particular, the BC does not have to be degraded, less noisy
or more capable [9, Chapter 5]. Our main result is somewhat
analogous to that of Lapidoth, Telatar and Urbanke [16] who
showed that time-division is optimal for wide-band broadcast
communication over Gaussian, Poisson, “very noisy” channels,
and average-power limited fading channels. However, the
analysis in [16] is restricted to stochastically degraded BCs.
The first analytical tool that is used to prove our main
theorem is a converse bound derived by El Gamal [17] initially
designed for more capable BCs. However, it turns out to be
useful a starting point for our setting. We manipulate this
bound into a form that is reminiscent of an outer bound for
degraded BCs. Subsequently, we express the λ-sum throughput
of this outer bound, for appropriately chosen λ ≥ 1, in terms
of upper concave envelopes [18]. This circumvents the need
to identify the optimal auxiliary random variable for specific
BCs. The identification of optimal auxiliaries is typically
possible only if the BC possesses some special structure.
For example for the binary symmetric BC, Mrs. Gerber’s

lemma [19] is a key ingredient in simplifying the converse
bound. Similarly for the Gaussian BC, a highly non-trivial
result known as the entropy power inequality [20], [21] is
needed to obtain an explicit expression for the capacity region.
Note that both these channels are degraded. Our main results
applies to all two-user discrete memoryless BCs. We employ
concave envelopes and take into consideration that under the
covertness constraint, the weight of the input (codeword) is
necessarily vanishingly small [7], [8]. Augmenting some basic
analytical arguments (e.g., [7, Lemma 1]) to these existing
techniques allows us to simplify the outer bound to conclude
that the time-division inner bound [9, Sec. 5.2] is optimal.
C. Intuition Behind The Main Result
We now provide intuition as to why time-division transmission is optimal for BCs with covertness constraints. We
use the binary symmetric BC [9, Example 5.3], degraded in
favor of Y1 (say), as an example to illustrate this fact. It is
well known that in the absence of the covertness constraint,
superposition coding [9, Sec. 5.3] [22] is optimal. The coding
scheme is illustrated in Fig. 2 where un1 (w1 ), un2 (w2 ) ∈ Fn2
are generated independently, un2 (w2 ) denotes the cloud center
and xn (w1 , w2 ) = un1 (w1 ) ⊕ un2 (w2 ) denotes the satellite
codeword. Because in covert communications, xn (w1 , w2 ) is
required to have low (Hamming) weight [7], [8], either both
un1 (w1 ) and un2 (w2 ) have low weight or both have high weight.
Let us assume it is the former without loss of generality. Then,
the set of locations of the 1’s in the satellite codeword is likely
to be a disjoint union of the sets of 1’s in un1 (w1 ) and un2 (w2 ).
Thus the relative weight of xn (w1 , w2 ), denoted as αn , can be
decomposed into the relative weights of un1 (w1 ) and un2 (m2 ),
denoted as ραn and (1−ρ)αn respectively for some ρ ∈ [0, 1].
Thus, the superposition coding inner bound for the degraded
BC [9, Theorem 5.2] [22] with X = U1 ⊕ U2 reads
R1 ≤ I(X; Y1 |U2 ) = I(U1 ; Y1 ) ≈ ραn L∗1 ,
R2 ≤ I(U2 ; Y2 ) ≈ (1 − ρ)αn L∗2 ,

(1)
(2)

where L∗1 and L∗2 are the “covert capacities” [7], [8] of
the constituent point-to-point binary symmetric channels; see
Theorem 1. Thus, (1) and (2) suggest that time-division is
optimal, at least for degraded BCs but we show the same is
true for all BCs.
D. Paper Outline
This paper is structured as follows. In Section II, we
formulate the problem and define relevant quantities of interest
precisely. In Section III, we state our main result for the
general BC. We also provide some qualitative interpretations.
The main result, corollaries, and bounds on the required length
of the secret key are proved in Sections IV, V, and VI
respectively. We conclude our discussion in Section VII where
we also suggest avenues for future research.
E. Notation
We adopt standard information-theoretic notation, following the text by El Gamal and Kim [9] and on occasion,

3

(W1 , W2 )
✲

f

Xn
✲ P ×n
Y1 Y2 Z|X

Y1n
✲

ϕ1

Y2n
✲

ϕ2

Ŵ1
✲
Ŵ2
✲

✲ H0 : Q×n
Zn
0
✲ Warden
✲ H1 : Q̂Z n
Fig. 1. Illustration of two-user BC with a warden. The key which is accessible to f, ϕ1 , and ϕ2 is not shown here.

un1 (w1 )
⊕

⊕

||

||

un2 (w2 )
xn (w1 , w2 )

Fig. 2. Illustration of intuition of optimality of time-division. Shaded (resp. unshaded) boxes indicate that that coordinate equals 1 (resp. 0). Because un
1 (w1 )
n
n
n
and un
2 (w2 ) are very sparse, the set of locations of the 1’s in x (w1 , w2 ) is highly likely to be a disjoint union of those in u1 (w1 ) and u2 (w2 ).

the book by Csiszár and Körner [23]. We use hb (q) :=
−q log q − (1 − q) log(1 − q) to denote the binary entropy
P
P (z)
function and D(P kQ) :=
z P (z) log Q(z) is the relative
entropy. Throughout log is taken to an arbitrary base. We
also use h(·) to denote the differential entropy. The notation
a ∗ b := a(1 − b) + b(1 − a) denotes the binary convolution
operator. For two discrete distributions, P and Q defined on
the same alphabet X , we say that P is absolutely continuous
with respect to Q, denoted as P ≪ Q if for all x ∈ X ,
Q(x) = 0 implies that P (x) = 0. Other notation will be
introduced as needed in the sequel.
II. P ROBLEM F ORMULATION
A discrete memoryless1 two-user BC with a warden
(X , Y1 , Y2 , Z, PY1 ,Y2 ,Z|X ) consists of a channel input alphabet X , three channel output alphabets Y1 , Y2 , and Z,
and a transition matrix PY1 ,Y2 ,Z|X . The output alphabets Y1
and Y2 correspond to the two legitimate receivers and Z
corresponds to that of the warden. Without loss of generality,
we let X = {0, 1, . . . , K}. We let 0 ∈ X be the “no
input” symbol that is sent when no communication takes place
and define Qx = PZ|X (·|x) for each x ∈ X . The BC is
used n times in a memoryless manner. If no communication
takes place, the warden at receiver Z observes Z n , which is
distributed according to Q×n
0 , the n-fold product distribution
of Q0 . If communication occurs, the warden observes Q̂Z n ,
the output distribution induced by the code. For convenience,
in the sequel, we often denote the two marginal channels
corresponding to the two legitimate receivers as W = PY1 |X
and V = PY2 |X respectively.
1 We omit the qualifier “discrete memoryless” for brevity in the sequel.
We will mostly discuss discrete memoryless BCs in this paper. However, in
Corollary 2, we present results for the BC with a warden when the constituent
channels are Gaussian.

The transmitter and the receiver are assumed to share a
secret key S uniformly distributed over a set K. We will, for
the most part, assume that the key is sufficiently long, i.e., the
set K is sufficiently large. However, we will bound the length
of the key in Section III-D. The transmitter and the receiver
aim to construct a code that is both reliable and covert. Let
the messages to be sent be W1 and W2 . These messages are
assumed to be independent and also independent of S. Also
let their reconstructions at the receiver Yj be Ŵj for j = 1, 2.
As usual, a code is said to be ε-reliable if the probability of
error Pr(∪2j=1 {Ŵj 6= Wj }) is asymptotically upper bounded
by ε ∈ [0, 1) as n → ∞. The code is covert if it is difficult
for the warden to determine whether the transmitter is sending
a message (hypothesis H1 ) or not (hypothesis H0 ). Let π1|0
and π0|1 denote the probabilities of false alarm (accepting H1
when the transmitter is not sending a message) and missed
detection (accepting H0 when the transmitter is sending a
message), respectively. Note that a blind test (one with no side
information) satisfies π1|0 + π0|1 = 1. The warden’s optimal
hypothesis test satisfies
q
π1|0 + π0|1 ≥ 1 − D(Q̂Z n kQ×n
(3)
0 ).

See [7], [24] for details of this claim. Hence, covertness is
guaranteed if the relative entropy between the observed distribution Q̂Z n and the product of no communication distribution
Q×n
vanishes as the blocklength grows.
0
Note that if supp(PZ|X (·|x)) * supp(Q0 ) for some x ∈ X ,
such x should not be transmitted, otherwise it is not possible
for D(Q̂Z n kQ×n
0 ) to vanish [8]. Hence, by dropping all such
input symbols as well as all output symbols not included in
supp(Q0 ), we assume throughout that supp(Q0 ) = Z. In addition, we assume that the no-input symbol 0 is not redundant
i.e., PZ|X (·|0) ∈
/ conv{PZ|X (·|x′ ) : x′ ∈ X , x′ 6= 0} where

4

conv{·} denotes the convex hull. If the symbol 0 is redundant,
there exists a sequence of codes for which D(Q̂Z n kQ×n
0 )= 0
for all n [8] so π1|0 +π0|1 = 1 (i.e., the warden’s test is always
blind) and transmitting at positive rates is possible; this is a
regime we do not consider in this paper.
A code for the BC with a covertness constraint and the
covert capacity region are defined formally as follows.
Definition 1. An (n, M1n , M2n , Kn , ε, δ)-code for the BC
with a warden (X , Y1 , Y2 , Z, PY1 ,Y2 ,Z|X ) and with a covertness constraint consists of
• Two message sets Mj := {1, . . . , Mjn } for j = 1, 2;
• Two independent messages uniformly distributed over
their respective message sets, i.e., Wj ∼ Unif(Mj ) for
j = 1, 2;
• One secret key set K := {1, . . . , Kn };
n
• One encoder f : M1n × M2n × K → X ;
n
• Two decoders ϕj : Yj × K → Mj for j = 1, 2;
such that the following constraints hold:

Pr ∪2j=1 {Ŵj 6= Wj } ≤ ε,
(4)
D(Q̂Z n kQ×n
0 ) ≤ δ.

(5)

For most of our discussion, we ignore the secret key set
(i.e., we assume that the secret key is sufficiently long) for the
sake of simplicity and refer to the family of codes above with
secret key sets of arbitrary sizes as (n, M1n , M2n , ε, δ)-codes.
We will revisit the effect of the key size in Section III-D.
Definition 2. We say that the pair (L1 , L2 ) ∈ R2+ is (ε, δ)achievable for the BC with a warden and with a covertness
constraint if there exists a sequence of (n, M1n , M2n , εn , δ)codes such that
1
lim inf √ log Mjn ≥ Lj ,
n→∞
nδ
lim sup εn ≤ ε.

j ∈ {1, 2},

(6)
(7)

n→∞

Define the (ε, δ)-covert capacity region Lε,δ ⊂ R2+ to be
the closure of all (ε, δ)-achievable pairs of (L1 , L2 ). We are
interested in the δ-covert capacity region
\
Lε,δ = lim Lε,δ .
(8)
Lδ :=
ε∈(0,1)

ε→0

Note that L1 and L2 are measured in bits (or information
units) per square root channel use.
We will also need the notion of covert capacities for pointto-point discrete memoryless channels (DMCs) with a warden
(X , Y, Z, PY,Z|X ) [7], [8]. This scenario corresponds to the
above definitions with Y1 = Y and Y2 = ∅. Recall that the
chi-squared distance between two distributions Q0 and Q1
supported on the same alphabet Z is defined as
X (Q1 (z) − Q0 (z))2
.
χ2 (Q1 kQ0 ) :=
Q0 (z)

(9)

z∈Z

Theorem 1 (Bloch [7] and Wang, Wornell, Zheng [8]). Let
(X , Y, Z, PY,Z|X ) be a DMC with a warden in which W :=
PY |X and Qk := PZ|X (·|k) for k ∈ X . We assume that it

satisfies W (·|k) ≪ W (·|0) for all k ∈ X \{0}, supp(Q0 ) = Z
and 0 ∈ X is not redundant. Then its covert capacity is
v
u PK
2
u2
k=1 pk D(W (·|k)kW (·|0))
∗
L (PY,Z|X ) := max t

PK
p
χ2
k=1 pk Qk Q0
(10)
where the maximization extends over all length-K probability
vectors p (i.e., p = [p1 , . . . , pK ]T where pk ≥ 0 and
P
K
k=1 pk = 1). If X = {0, 1}, i.e., PY,Z|X has a binary input,
then the maximization over p in (10) is unnecessary and
s
2D(W (·|1)kW (·|0))2
.
(11)
L∗ (PY,Z|X ) :=
χ2 (Q1 kQ0 )
As previously mentioned, we assume P
that Q1 ≪ Q0 in
∗
the binary input case (or more generally, K
k=1 pk Qk ≪ Q0
∗
∗
∗ T
where p = [p1 , . . . , pK ] is any maximizer of (10)). Otherwise, covert communication is impossible [7, Appendix G].
With this assumption and the fact that 0 ∈ X is not redundant,
L∗ (PY,Z|X ) as defined in (10) and (11) is finite.
III. M AIN R ESULTS
In this section, we present our main results. In Section III-A,
we state our main result for the case where the BC is general
and the key is of sufficiently long length. We interpret our
result in Section III-B by placing it in context via several
remarks. In Section III-C, we specialize our result to two
degraded BCs and show that standard techniques apply for
such models. In Section III-D, we extend our main result to
the case where the key size is also a parameter of interest.
A. General Memoryless BCs
Our main result is a complete characterization of the δcovert capacity region for all BCs satisfying certain absolute
continuity conditions.
Theorem 2. Assume that a BC with a warden PY1 ,Y2 ,Z|X
is such that the constituent DMCs W := PY1 |X and V :=
PY2 |X satisfy W (·|k) ≪ W (·|0) and V (·|k) ≪ V (·|0) for all
k ∈ X \ {0}. Also assume that the length of the secret key
is sufficiently large. Denote the individual covert capacities of
the constituent DMCs with a warden PY1 ,Z|X and PY2 ,Z|X
as L∗1 := L∗ (PY1 ,Z|X ) and L∗2 := L∗ (PY2 ,Z|X ) respectively.
Then, for all δ > 0, the δ-covert capacity region is


L2
L1
2
(12)
Lδ = (L1 , L2 ) ∈ R+ : ∗ + ∗ ≤ 1 .
L1
L2
Theorem 2 is proved in Section IV.
B. Remarks on the Main Theorem
A few remarks are in order.
1) First, note that (12) implies that under the covert
communication constraints, time-division transmission
is optimal for all BCs. The achievability part simply
involves two optimal covert communication codes, one
for each DMC with a warden. The first code, designed
for PY1 ,Z|X , is employed over ⌊ρn⌋ channel uses where

5

ρ ∈ [0, 1]. The second code, designed for PY2 ,Z|X , is
employed over the remaining n − ⌊ρn⌋ channel uses.
This achieves the point (ρL∗1 , (1 − ρ)L∗2 ) which is on
the boundary of Lδ . By varying ρ ∈ [0, 1], we achieve
the whole boundary and hence the entire region in (12).
2) The converse of Theorem 2 thus constitutes the main
contribution of this paper. To obtain an explicit outer
bound for the capacity region for BCs that satisfy some
ordering—such as degraded, less noisy or more capable
BCs [9, Chapter 5]—one often has to resort to the
identification of the optimal auxiliary random variablechannel input pair (U, X) in the characterization of the
capacity region of these classes of BCs. However, this is
only possible for specific BCs; see Corollaries 1 and 2
to follow. For general (or even arbitrary degraded) BCs,
this is, in general, not possible. Our workaround involves
first starting with an outer bound of the capacity region
for general memoryless BCs by El Gamal [17]. We
combine the inequalities in the outer bounds and use this
to upper bound a linear combination of the throughputs
of the point-to-point channels in terms of the concave
envelope of a linear combination of mutual information
terms [18]. This allows us to circumvent the need to explicitly characterize (U, X) since U is no longer present
in this concave envelope characterization. We exploit
the fact that in covert communications, the input to
the channel is required to have low weight. Leveraging
this constraint and applying some approximations then
allows us to obtain the outer bound to (12) for all BCs.
The appeal of this approach is not only that we do not
need to find the optimal (U, X) as this is implicit in the
concave envelope representation.
3) Let us say that the absolute continuity condition holds
for a channel W if W (·|k) ≪ W (·|0) for all k ∈ X \{0}.
Then it was shown by Bloch [7, Appendix G] that if
W √does not satisfy the absolute continuity condition,
Θ( n log n) bits per n channel uses can be covertly
transmitted. In our setting, the same is true for the constituent channels; if W satisfies
√ the absolute continuity
condition but V does not Θ( n) bits
√ per n channel uses
can be transmitted to Y1 , while Θ( n log n) bits per n
channel uses can be transmitted to Y2 and vice versa.

An alternative (converse) proof of this result follows from
Mrs. Gerber’s lemma [19] and is presented in Section V-A.
This result generalizes [8, Example 3].
We now consider the scenario in which the BC PY1 ,Y2 ,Z|X
consists of three additive white Gaussian noise (AWGN)
channels [9, Sec. 5.5], i.e.,
Yj = X + Ψj ,
Z = X + Ψ3 ,

j ∈ {1, 2}

(14)
(15)

where Ψ1 , Ψ2 , and Ψ3 are independent zero-mean Gaussian
noises with variances N1 , N2 , and σ 2 respectively. There is
no (peak, average, or long-term) power constraint on the
codewords [8, Sec. V]. Let the “no communication” input
symbol be 0 ∈ R, so by (15), Q0 is distributed as a zeromean Gaussian with variance σ 2 .
Corollary 2. Suppose that W and V be AWGN channels as
in (14) with noise variances satisfying 0 ≤ N1 ≤ N2 (without
loss of generality). Then Lδ is as in (12) with
L∗j =

σ 2 log e
,
Nj

j ∈ {1, 2}.

(16)

An alternative (converse) proof of this result follows from
the entropy power inequality [20], [21] and is presented in
Section V-B. This result generalizes [7, Theorem 6] and [8,
Theorem 5]. This result is also analogous to [16, Prop. 1] in
which it was shown that time-division is optimal for Gaussian
BCs in the low-power limit.
We note that Corollaries 1 (for the binary symmetric BC)
and 2 (for the Gaussian BC) apply to an arbitrary but finite number of successively degraded legitimate receivers [9,
Sec. 5.7], say N ∈ N. This means that X ⊸−
− Y1 ⊸−
−
Y2 ⊸−
− . . . ⊸−
− YN . The corresponding δ-covert capacity
region is


N
X
Lj
N
Lδ = (L1 , . . . , LN ) ∈ R+ :
≤1 ,
(17)
L∗
j=1 j
where L∗j is given as in (13) or (16). We omit the proofs
as they are straightforward generalizations of the corollaries
above.

C. Degraded BCs

D. On the Length of the Secret Key

We now specialize Theorem 2 to two specific classes of
(degraded) BCs and show that slight modifications of standard
techniques are applicable in establishing the outer bound to
Lδ . To state the first corollary, we use the following notation:
W = BSC(q) if it is a binary-input, binary-output channel in
which Y = X ⊕ Ψ where Ψ ∼ Bern(q).

In the preceding derivations, we have assumed that the
secret key that the transmitter and legitimate receivers share is
arbitrarily long. In other words, the set K is sufficiently large.
In this section, we derive fundamental limits on the length of
the key so that covert communication remains successful.
To formalize this, we will need to augment Definition 2. We
say that (L1 , L2 , Lkey ) is δ-achievable or simply achievable
if in addition to (6) and (7) (with ε = 0),

Corollary 1. Suppose that W = BSC(p1 ) and V = BSC(p2 )
with 0 ≤ p1 ≤ p2 ≤ 1/2 (without loss of generality) [9,
Example 5.3]. Then Lδ is as in (12) with
s
1 − pj
2
∗
Lj = (log e)(1−2pj ) log
·
, j ∈ {1, 2}.
pj
χ2 (Q1 kQ0 )
(13)

1
lim sup √ log Kn ≤ Lkey .
n→∞
nδ

(18)

Finally, we set L∗Z := L∗ (PZ,Z|X ). The generalization of
Theorem 2 is as follows.

6

Theorem 3. The tuple (L1 , L2 , Lkey ) ∈ R3+ is achievable if
and only if
L1
L2
+ ∗ ≤1
∗
L1
L2

(19)

and
Lkey ≥



L2
L1
+ ∗
∗
L1
L2



L∗Z − L1 − L2 .

(20)

Note that if the throughputs of the code (log M1n , log M2n )
are such that we operate on the boundary of the covert capacity
region (i.e., that (19) holds with equality), the optimum
(minimum) key length
L∗key = L∗Z − L1 − L2 .

(21)

Then, it follows that

Also note that if Lkey is sufficiently large, then (20) is satisfied
so based on (19), Theorem 3 reverts to Theorem 2. The proof
of this enhanced theorem follows largely along the same lines
as that for Theorem 2. However, we need to carefully bound
the length of the secret key. The additional arguments to
complete the proof of Theorem 3 are provided in Section VI.
IV. P ROOF

OF

T HEOREM 2

A. Preliminaries for the Proof of Theorem 2
Before we commence, we recap some basic notions in convex analysis. The (upper) concave envelope of f : D → R, denoted as C[f ](x) := inf{g(x) : g ≥ f over D, g is concave},
is the smallest concave function lying above f . Clearly, if f is
concave, then C[f ] = f . Furthermore if D is a subset of Rd ,
then by Carathéodory’s theorem [18],
g = C[f ]

⇐⇒

g(x) =

sup

d+1
X

pi f (xi ),

(22)

{(xi ,pi )}d+1
i=1 i=1

where xi ∈ D and {pi }d+1
i=1 is a probability distribution such
P
that d+1
p
x
=
x.
Here,
we record a basic fact:
i
i
i=1
f1 ≥ f2 on D

=⇒

g1 ≥ g2 on D

(23)

where gj = C[fj ], j = 1, 2. This can be easily proved by
means of the representation of the concave envelope in (22).
Indeed,
g2 (x) ≥

d+1
X
i=1

pi f2 (xi ) ≥

d+1
X

pi f1 (xi )

(24)

i=1

where the first inequality holds for any {(xi , pi )}d+1
i=1 such that
Pd+1
p
x
=
x
and
the
second
inequality
because
f2 ≥ f1 on
i=1 i i
D. Since the inequality holds for all {(xi , pi )}d+1
i=1 such that
Pd+1
i=1 pi xi = x, we have
g2 (x) ≥

sup

d+1
X

{(xi ,pi )}d+1
i=1 i=1

which establishes (23).

B. Converse Proof of Theorem 2: Binary-Input BCs
We first prove the converse to Theorem 2 for the case
when X = {0, 1}. This is done for the sake of clarity and
simplicity. We subsequently show how to extend the analysis
to the multiple symbol case (i.e., |X | > 2) in Section IV-C. Fix
a sequence of (n, M1n , M2n , εn , δ)-codes for the BC with a
warden PY1 ,Y2 ,Z|X satisfying the 0-reliability constraint in (4)
and (7) and the covertness constraint in (5). In the proof, we
use the following result by Bloch [7, Lemma 1, Remark 1]:
P
Lemma 1. Let Qγ (z) :=
x∈X PZ|X (z|x)Pγ (x) for γ ∈
[0, 1] where Pγ is a Bernoulli distribution with parameter γ,
i.e.,

1−γ x=0
Pγ (x) :=
.
(26)
γ
x=1

pi f1 (xi ) = g1 (x),

(25)

I(Pγ , PZ|X ) = γD(Q1 kQ0 ) − D(Qγ kQ0 ).

(27)

Furthermore, for any sequence γn such that γn → 0 as n →
∞, for all n sufficiently large,

√
γn2
χ2 (Q1 kQ0 ) (1 − γn ) ≤ D(Qγn kQ0 )
2
γ2
√
≤ n χ2 (Q1 kQ0 ) (1 + γn ) .
(28)
2
1) Covertness Constraint: We first discuss the covertness
constraint in (5). Let Z n (resp. X n ) have distribution Q̂Z n
(resp. P̂X n ) and let Q̂Zi (resp. P̂Xi ) be the marginal of Q̂Z n
Q̄n be the
(resp. P̂X n ) on the i-th element. Additionally, let P
n
average output distribution on Z, i.e., Q̄n := n1 i=1 Q̂Zi .
Similarly wePdefine the average input distribution P̄n on X
as P̄n := n1 ni=1 P̂Xi . Then mimicking the steps in the proof
of [8, Theorem 1], we have
D(Q̂Z n kQ×n
0 ) ≥ nD(Q̄n kQ0 ).

(29)

Thus, by the covertness constraint in (5) and (29), we have
δ
(30)
D(Q̄n kQ0 ) ≤ .
n
Since limn→0 D(Q̄n kQ0 ) = 0 and symbol 0 ∈ X is not
redundant,2 it follows that
P̄n = Pαn for some αn → 0.

(31)

Because Q̄n (z) = Qαn (z) for all z ∈ Z, by Lemma 1,

√
α2n
χ2 (Q1 kQ0 ) (1 − αn ) ≤ D(Q̄n kQ0 )
2
√
α2
≤ n χ2 (Q1 kQ0 ) (1 + αn ) . (32)
2
From (30) and (32), we conclude that αn has to satisfy the
weight constraint
√
2δ
=: ᾱ2n .
(33)
α2n (1 − αn ) ≤
χ2 (Q1 kQ0 )n
From this relation, we see that αn ≤ ᾱn (1 + o(1)) = Θ( √1n ).

2 Indeed, if 0 were redundant (e.g., P
Z|X (·|0) = PZ|X (·|1) for binary X ),
there exists an input distribution
P P̃ such that P̃ (0) = 0 and its corresponding
output distribution Q̃ =
x P̃ (x)PZ|X (·|x) = Q0 [8, Eqn. (5)]. The
distribution Q̃ (taking the role of Q̄n ) satisfies D(Q̃kQ0 ) = 0 so (30)
is trivially satisfied. However, P̃ (taking the role of P̄n ) clearly does not
satisfy (31).

7

2) Upper Bound on Linear Combination of Code Sizes:
We now proceed to consider upper bounds on the code sizes
subject to the reliability and covertness constraints. Without
loss of generality, we assume L∗1 ≥ L∗2 . We start with a lemma
that is a direct consequence of the converse proof for more
capable BCs by El Gamal [17]. This lemma is stated in a
slightly different manner in [9, Theorem 8.5].
Lemma 2. Every (n, M1n , M2n , εn )-code for any BC satisfies
(log M1n )(1 − εn ) − 1 ≤
(log M2n )(1 − εn ) − 1 ≤

n
X

i=1
n
X

I(U1i ; Y1i ),

(34)

PX PU |X

= max max I(X; Y1 |U ) + λ[I(X; Y2 ) − I(X; Y2 |U )] (42)
PX PU |X

= max λI(X; Y2 ) + max I(X; Y1 |U ) − λI(X; Y2 |U ) (43)
PX

I(U2i ; Y2i ),

(35)

(36)

(37)

= max
PU |X

where U1i
:=
and U2i
:=
i−1
n
(W2 , Y1,i+1 , Y2 ) satisfies (U1i , U2i ) ⊸−
− Xi ⊸−
−
(Y1i , Y2i ). In addition, if a secret key S is available to the
encoders and decoder, then the auxiliary random variables
U1i and U2i also include S.
For completeness, the proof of Lemma 2, with the effect
of the secret key, is provided in Appendix A. Note that no
assumption (e.g., degradedness, less noisy or more capable
conditions) is made on the BC in Lemma 2.
Now fix a constant λ ≥ 1. By adding (λ − 1) copies
of (35) to one copy of (36) and writing Ui := U2i for all
i ∈ {1, . . . , n}, we obtain

(38)

i=1

By introducing the usual time-sharing random variable J ∈
Unif{1, . . . , n} which is independent of all the other random
variables (W1 , W2 , X n , Y1n , Y2n ) and defining U := (J, UJ ),
X := XJ , Y1 := Y1J and Y2 := Y2J , we obtain
≤ nI(X; Y1 |U ) + nλI(U ; Y2 ).

max I(X; Y1 |U ) − λI(X; Y2 |U )
X
PU (u)[I(X; Y1 |U = u)−λI(X; Y2 |U = u)]
= max
PU |X

n
(W1 , Y1i−1 , Y2,i+1
)

(log M1n + λ log M2n )(1 − εn ) − (1 + λ)

(44)

PU |X

i=1

(log M1n + λ log M2n )(1 − εn ) − (1 + λ)
n
X


I(Xi ; Y1i |Ui ) + λI(Ui ; Y2i ) .
≤

= max λI(X; Y2 ) + CPX [I(X; Y1 ) − λI(X; Y2 )].

− X ⊸−
− Y2
Here, (42) follows from the Markov chain U ⊸−
and (44) follows from the definition of the concave envelope.
Namely, for fixed PX ,

i=1

(log M1n + log M2n )(1 − εn ) − 2
n
X


I(U1i ; Y1i ) + I(Xi ; Y2i |U1i ) ,
≤

PU |X

PX

i=1

(log M1n + log M2n )(1 − εn ) − 2
n
X


I(Xi ; Y1i |U2i ) + I(U2i ; Y2i ) ,
≤

X

PU (u)[I(PX|U (·|u), W )−λI(PX|U (·|u), V )] (46)

u

= CPX [I(X; Y1 ) − λI(X; Y2 )],

(47)

−
where (46) follows from the Markov chain U ⊸−
X
⊸−
−
(Y
,
Y
)
and
(47)
follows
from
the
fact
that
1
2
P
u PU (u)PX|U (·|u) = PX and (22). Note that we employ
the subscript PX on C to emphasize that the concave envelope
operation is taken with respect to the distribution PX and it
is thus a function of PX .
3) Approximating the Maximization over Low-Weight Inputs: Due to the above considerations, it now suffices to
simplify (44). To obtain the outer bound to (12), we set
λ := L∗1 /L∗2 in the following. Note that since it is assumed
that L∗1 ≥ L∗2 , λ ≥ 1 as required to obtain (38). If instead
L∗2 > L∗1 , then we set λ := L∗2 /L∗1 and add (λ − 1) copies
of (34) to one copy of (37) to obtain the analogue of (38) with
Ui := U1i . In the rest of the proof, we also replace the index 1
by 2 and W by V and vice versa. The following argument goes
through verbatim with these minor amendments.
By expressing the mutual information quantities in (44) as
I(PX , W ) and I(PX , V ) [23] (for I(X; Y1 ) and I(X; Y2 )
respectively), we can write (44) as follows:
PX

(39)

(45)

u

max λI(PX , V ) + CPX [I(PX , W ) − λI(PX , V )].

Note that the above identification of (U, X) satisfies U ⊸−
−
X ⊸−
− (Y1 , Y2 ). Furthermore, since X is equal to Xi for each
i ∈ {1, . . . , n} with equal probability 1/n (because of X =
XJ ), it follows PX = P̄n = Pαn for some αn satisfying (33).
Hence, (39) can be bounded by taking a maximization over
all such distributions, i.e.,

1
(log M1n + λ log M2n )(1 − εn ) − (1 + λ)
n
≤ max max I(X; Y1 |U ) + λI(U ; Y2 ),
(40)
PX PU |X

where the maximization over PX is over distributions Pαn
where αn satisfies (33).
Now by using the concave envelope representation for the
capacity region of degraded BCs [18], we may write (39) as
follows:

1
(log M1n + λ log M2n )(1 − εn ) − (1 + λ)
n
≤ max max I(X; Y1 |U ) + λI(U ; Y2 )
(41)

(48)

Now we parametrize PX = Pαn = P̄n as the vector [1 −
αn , αn ]T where 0 ≤ αn ≤ ᾱn (1 + o(1)) [cf. (33)] such that
PX is linear in the parameter αn . By applying (27) and (28) to
both mutual information terms, we can approximate the terms
in the argument of the concave envelope in (48) as
I(PX , W ) − λI(PX , V )


= αn D(W (·|1)kW (·|0)) − λD(V (·|1)kV (·|0))
+ O(α2n ).

O(α2n )

(49)

Note that the implied constant in the term
depends only
on χW := χ2 (W (·|1)kW (·|0)) and χV := χ2 (V (·|1)kV (·|0))

8

and these are finite under the absolute continuity conditions
of the theorem, i.e., W (·|1) ≪ W (·|0) and V (·|1) ≪ V (·|0).
Consequently, for every η > 0, there exists an integer
N1 (η; χW , χV ) such that for n > N1 (η; χW , χV ), we have
I(PX , W ) − λI(PX , V )


≤ αn D(W (·|1)kW (·|0))−λD(V (·|1)kV (·|0))+η . (50)

This is because the quadratic term O(α2n ) can be upper
bounded by ηαn for all n sufficiently large (depending only
on (χW , χV )).
Equipped with the fact in (23) and the upper bound in (50),
we obtain that for all n > N1 (η; χW , χV ),
CPX [I(PX , W ) − λI(PX , V )]
h 
≤ CPX αn D(W (·|1)kW (·|0))

i
− λD(V (·|1)kV (·|0)) + η .

CPX [I(PX , W ) − λI(PX , V )]


≤ αn D(W (·|1)kW (·|0))−λD(V (·|1)kV (·|0))+η . (52)

In addition, by the same reasoning involving Taylor approximations, there exists an integer N2 (η; χV ) such that for all
n > N2 (η; χV ), we can upper bound the first term in (48) as
follows:
(53)

Combining (52) and (53), we see that the terms
λαn D(V (·|1)kV (·|0)) cancel and the expression in (48) can
be upper bounded as
max I(PX , V ) + CPX [I(PX , W ) − λI(PX , V )]
PX


≤ αn D(W (·|1)kW (·|0)) + 2η

Since (57) holds for all η > 0 and η is arbitrary, we obtain
s
2D(W (·|1)kW (·|0))2
L∗1
L1 + ∗ L2 ≤
.
(58)
L2
χ2 (Q1 kQ0 )

Finally, by recalling the definition of the covert capacity of
PY1 ,Z|X according to (11) in Theorem 1, we notice that the
right-hand-side of (58) is exactly L∗1 . Hence we obtain the
desired outer bound corresponding to the region Lδ in (12) in
Theorem 2.

(51)

Now, observe that g(αn ) := αn [D(W (·|1)kW (·|0)) −
λD(V (·|1)kV (·|0)) + η] is linear in αn and PX is also a
linear function in αn so by expressing αn as a function of
(any one of the components of) PX , we know that g(·) is a
linear function of PX . Since a linear function is concave, we
can remove the concave envelope operation in (51) yielding

λI(PX , V ) ≤ λαn D(V (·|1)kV (·|0)) + ηαn .

pairs according to Definition 2, and the facts that εn → 0
and nδ → ∞, we obtain
s


2
L∗1
D(W (·|1)kW (·|0))+2η . (57)
L1 + ∗ L2 ≤
L2
χ2 (Q1 kQ0 )

(54)

for all n > max{N1 (η; χW , χV ), N2 (η; χV )}. Note that PX
in the maximization above is such that PX = Pαn with the
constraint 0 ≤ αn ≤ ᾱn (1 + o(1)). Now, combining (54) with
the upper bound in (44), we have

1
(log M1n + λ log M2n )(1 − εn ) − (1 + λ)
n


≤ ᾱn (1 + o(1)) D(W (·|1)kW (·|0)) + 2η .
(55)

4) Completing the Converse Proof Taking Limits: At this
point, we invoke the definition of ᾱn in (33) and normalize (55) to obtain

1 
√
(log M1n + λ log M2n )(1 − εn ) − (1 + λ)
nδ
s


2δn
D(W (·|1)kW (·|0))+2η . (56)
≤ (1+o(1))
χ2 (Q1 kQ0 )δn

Taking the lim sup in n on both sides, recalling that (i)
λ = L∗1 /L∗2 and (ii) the definition of achievable (L1 , L2 )

C. Converse Proof of Theorem 2: General BCs
We generalize the converse proof for binary-input in Section IV-B to the multiple symbol case, i.e., |X | > 2. We use
the following lemma whose proof is in [7, Section VII-B].
Lemma 3. For γ ∈ [0, 1] and length-K
PK probability vector p =
T
[p
,
.
.
.
,
p
]
,
i.e.,
p
≥
0
and
1
K
k
k=1 pk = 1, let Qγ,p (z) :=
P
P
(z|x)P
(x)
where
γ,p
Z|X
x∈X

1−γ
x=0
Pγ,p (x) :=
.
(59)
γpk x = k ∈ X \ {0}
Then, it follows that
X

K
I(Pγ,p , PZ|X ) =
γpk D(Qk kQ0 ) −D(Qγ,pkQ0 ). (60)
k=1

Furthermore, for any sequence γn such that γn → 0 as n →
∞, for all n sufficiently large,
X

K
γn2
√
χ2
pk Qk Q0 (1 − γn ) ≤ D(Qγn ,p kQ0 )
2
k=1
X

K
γn2
√
≤
χ2
pk Qk Q0 (1 + γn ) (61)
2
k=1

1) Covertness Constraint: By a close inspection of the
steps in Section IV-B1 and by applying Lemma 3, we conclude
that the average input distribution P̄n is given by Pαn ,p for
some length-K probability vector p and αn such that
α2n (1 −

√
αn ) ≤

2δ

χ2

 =: ᾱ2p,n .
p
Q
Q
0 n
k=1 k k

PK

(62)

2) Upper Bound on Linear Combination of Code Sizes:
Let us assume L∗1 ≥ L∗2 (without loss of generality), then
λ = L∗1 /L∗2 ≥ 1. It can be easily checked that the steps in
Section IV-B2 go through in the same manner for the multiple
symbol case except that PX = Pαn ,p for some length-K
probability vector p and αn ∈ [0, 1] satisfying (62). As such,
we have that (44) also holds where now the maximization
over PX is over those distributions Pαn ,p for some p and αn
satisfying (62).

9

3) Approximating the Maximization over Low-Weight Inputs: Now we approximate (48). We fix p throughout. By the
same arguments up to (50) and using (60) and (61), we have
for PX = Pαn ,p ,
I(PX , W ) − λI(PX , V )
" K
X 
≤ αn
pk D(W (·|k)kW (·|0))

where the equality in (69) follows from the Markov chain
U ⊸−
− X ⊸−
− Y2 and (70) follows from the fact that the
entropy of Y2 = X ⊕Ψ1 ⊕ Ψ̃2 when E[X] = αn is hb (αn ∗p2 ).
As a result, from (70), there exists a τn ∈ [0, αn ] such that
H(Y2 |U ) = hb (τn ∗ p2 ).

(71)

hb (τn ∗ p2 ) = H(Y2 |U ) = H(Y1 ⊕ Ψ̃2 |U )

≥ hb h−1
b (H(Y1 |U )) ∗ p̃2

(72)

τn ∗ p1 ∗ p̃2 ≥ h−1
b (H(Y1 |U )) ∗ p̃2 .

(74)

Then, we have

k=1



#

− λD(V (·|k)kV (·|0))] + η .

(63)

for some fixed η > 0 and n sufficiently large.
Since the right-hand side of (63) is linear in PX , due to the
same reasoning up to (55), we have

1
(log M1n + λ log M2n )(1 − εn ) − (1 + λ)
n
" K
#

X
≤ ᾱp,n (1+o(1))
pk D(W (·|k)kW (·|0)) +2η (64)

where (73) follows from the conditional version of Mrs.
Gerber’s lemma [19]. By the monotonicity of hb (·) on [0, 1/2]
and the fact that p1 ∗ p̃2 = p2 , we have

As a result, we have
H(Y1 |U ) ≤ hb (τn ∗ p1 ).

(75)

I(X; Y1 |U ) = H(Y1 |U ) − H(Y1 |U, X)
= H(Y1 |U ) − hb (p1 )

(76)
(77)

k=1

for n sufficiently large.
4) Completing the Converse Proof Taking Limits: By substituting λ = L∗1 /L∗2 and ᾱp,n defined in (62) into (64), taking
limits as in Section IV-B4, and subsequently maximizing over
all probability vectors p on X \ {0}, we obtain
v
u PK
2
∗
u2
L1
k=1 pk D(W (·|k)kW (·|0))
t
L1 + ∗ L2 ≤ max

PK
p
L2
χ2
k=1 pk Qk Q0
= L∗1 .

(65)

This completes the proof for the multiple symbol case.
V. P ROOFS

OF

C OROLLARIES

IN

A. Proof of Corollary 1
As the the capacity region of the stochastically degraded
BC is the same as that of the physically degraded BC with the
same marginals [9, Sec. 5.4] even under the covertness constraint, we assume that the physically degradedness condition
holds, i.e., Y1 = X ⊕Ψ1, Y2 = Y1 ⊕ Ψ̃2 where Ψ̃2 ∼ Bern(p̃2 )
such that p1 ∗ p̃2 = p2 .
We follow the exposition in [9, Sec. 5.4.2] closely. By the
standard argument to establish the weak converse for degraded
BCs [25], we know that every (n, M1n , M2n , εn )-code for a
BC must satisfy
(66)
(67)

for some U ⊸−
− X ⊸−
− (Y1 , Y2 ) in which X satisfies the
weight constraint in (33), i.e., PX = Pαn or E[X] = αn . We
now evaluate the region in (66)–(67) explicitly in terms of the
channel parameters and the upper bound on the weight of X.
Now we have
hb (p2 ) = H(Y2 |X)
= H(Y2 |U, X) ≤ H(Y2 |U ) ≤ H(Y2 )
= hb (αn ∗ p2 ),

Now consider

≤ hb (τn ∗ p1 ) − hb (p1 ).

(78)

For the other rate bound in (67), we have
I(U ; Y2 ) = H(Y2 ) − H(Y2 |U )
≤ hb (αn ∗ p2 ) − hb (τn ∗ p2 ).

(79)
(80)

d
hb (q) = (log e) log 1−q
Now, note that for all q ∈ (0, 1/2), dq
q .
By Taylor expanding hb around q, we obtain

S ECTION III-C

(log M1n )(1 − εn ) − 1 ≤ nI(X; Y1 |U )
(log M2n )(1 − εn ) − 1 ≤ nI(U ; Y2 ),

(73)

(68)
(69)
(70)

hb (q ∗ ξ) = hb (q + (1 − 2q)ξ)
(81)
1−q
2
= hb (q) + (log e) log
· (1 − 2q)ξ + O(ξ ) (82)
q
as ξ → 0. Now we can simplify the bounds√on the righta/ n and τn :=
hand-sides
of (78) and (80). Write αn :=p
√
t/ n where t ∈ [0, a] and a := (1 + o(1)) 2δ/χ2 (Q1 kQ0 );
see (33) for the relation between αn and an upper bound on a
function of it given by ᾱn . By combining (66), (67), (78), (80),
and (82), we obtain the outer bound

1
(log M1n )(1 − εn ) − 1
n
 
t
1
1 − p1
√
·
+O
≤ (log e)(1 − 2p1 ) log
p1
n
n

1
(log M2n )(1 − εn ) − 1
n
 
1 − p2 a − t
1
≤ (log e)(1 − 2p2 ) log
.
· √ +O
p2
n
n

(83)

(84)

By dividing the first and second bounds by (log e)(1 −
1
2
2p1 ) log 1−p
and (log e)(1 − 2p2 ) log 1−p
respectively,
p1
p2
p
adding them, multiplying the resultant expression by n/δ,
and taking limits, we immediately recover the outer bound to
Lδ with L∗j defined in (13).

10

B. Proof of Corollary 2
The proof follows similarly to that of Corollary 1 but we
use the entropy power inequality [20], [21] in place of Mrs.
Gerber’s lemma. As in the proof of Corollary 1, we assume
physically degradedness, i.e., Y1 = X + Ψ1 , Y2 = Y1 + Ψ̃2
where Ψ̃2 is independent zero-mean Gaussian noise with
variance N2 − N1 . Let the second moment of the input
distribution be denoted as αn = E[X 2 ]; this plays the role
of the weight of X in the discrete case. The bounds (66)
and (67) clearly still hold so we only have to single-letterize
the two mutual information terms I(X; Y1 |U ) and I(U ; Y2 ).
We follow the exposition in [9, Sec. 5.5.2] closely.
First, we have
I(U ; Y2 ) = h(Y2 ) − h(Y2 |U )
(85)
1
(86)
≤ log(2πe(αn + N2 )) − h(Y2 |U )
2
where (86) follows from the fact that a Gaussian maximizes
differential entropy over all distributions with the same second
moment. Now note that
1
log(2πeN2 ) = h(Y2 |X)
(87)
2
= h(Y2 |U, X) ≤ h(Y2 |U ) ≤ h(Y2 )
(88)
1
≤ log(2πe(αn + N2 )).
(89)
2
As such there exists a τn ∈ [0, αn ] such that

1
log(2πe(τn + N2 )).
(90)
2
Then, by the conditional form of the entropy power inequality [20], [21],
h(Y2 |U ) =

h(Y2 |U ) = h(Y1 + Ψ̃2 |U )
(91)


1
(92)
≥ log 22h(Y1 |U) + 22h(Ψ̃2 |U)
2


1
= log 22h(Y1 |U) + 2πe(N2 − N1 ) .
(93)
2
Thus,
1
h(Y1 |U ) ≤ log(2πe(τn + N1 )).
(94)
2
Now, we are ready to upper bound the mutual information
terms using the above calculations. We have
I(X; Y1 |U ) = h(Y1 |U ) − h(Y1 |U, X)
(95)
1
1
≤ log(2πe(τn + N1 )) − log(2πeN1 ) (96)
2
2


1
τn log e
τn
= log 1 +
≤
,
(97)
2
N1
2N1
where the last inequality follows from the fact that log(1+t) ≤
t log e for t ≥ −1. Similarly,
I(U ; Y2 ) = h(Y2 ) − h(Y2 |U )


(αn − τn ) log e
αn + N2
1
≤
≤ log
2
τn + N2
2(τn + N2 )
(αn − τn ) log e
≤
.
2N2

(98)
(99)
(100)

Using the same calculations as those leading to [8, Eqn. (75)],
we conclude that the covert communication constraint in the
Gaussian case translates to
δ
α2n
+ o(α2n ) ≤ .
4σ 4
n

(101)

The proof is completed by uniting (97), (100), and (101) in a
way that is analogous to the conclusion of the proof for the
binary symmetric BC in Section V-A.
VI. P ROOF S KETCH

OF

T HEOREM 3

Proof: The achievability in (20) follows by augmenting
the standard time-division argument given in Remark 1 in
Section III-B. More specifically, we let ρ1 := L1 /L∗1 and
ρ2 := L2 /L∗2 . Then ρ1 + ρ2 ≤ 1. We use an optimal code for
the first receiver for ρ1 fraction of time, an optimal code for
the second receiver for ρ2 fraction of time, and stay idle for the
remaining fraction of time. Then the required secret key rate3
is ρ1 (L∗Z − L∗1 ) + ρ2 (L∗Z − L∗2 ) as a direct consequence of [7,
Theorem 3], which is equal to the right-hand side of (20).
For the converse, for simplicity, we only consider the
binary-input
Q1
PK case; the general case follows from replacing
PK
with
k=1 pk Qk everywhere and P̄n (1) with
k=1 P̄n (k)
everywhere. We show that there is a tradeoff between the
√ message rates and the secret key rate (with normalizations nδ); if
the message rates are in the interior of (12), a strictly smaller
secret key rate is required. To elucidate this tradeoff, let us
consider a rate tuple (L1 , L2 ) such that L1 /L∗1 + L2 /L∗2 = κ
for some κ ∈ [0, 1]. Note that κ strictly less than one means
that the message rates are in the interior of (12).
By applying similar steps as in [7, Eqns. (91)–(94)], we
obtain
log M1n + log M2n + log Kn = H(W1 , W2 , S)
≥ I(W1 , W2 , S; Z n )
≥ I(X n ; Z n )

≥ nI(X; Z) − δ,

(102)
(103)
(104)
(105)

where (105) follows from similar steps presented in [26,
Sec. 5.2.3]. Here X = XJ and Z = ZJ where J is the
time-sharing random variable defined in Section IV-B2. Then,
1
√ (log M1n + log M2n + log Kn )
nδ
1
≥ √ (nI(X; Z) − δ)
(106)
nδ 

δ
D(Qαn kQ0 )
nαn
, (107)
−
D(Q1 kQ0 ) −
= √
αn
nαn
nδ
where (107) follows from Lemma 1. Note that the lower
bound (107) depends on the “weight” αn = P̄n (1). Hence,
substituting the smallest “weight” αn = P̄n (1) that attains
L1 /L∗1 + L2 /L∗2 = κ into (107) results in a lower bound
on the required secret key rate to attain the message rate
pair (L1 , L2 ).
3 With a slight abuse of terminology, we will refer to L , L , and L
1
2
key as
rates even though they are not communication rates in the usual sense [9].

11

Now let us denote the smallest αn = P̄n (1) that attains
L1 /L∗1 + L2 /L∗2 = κ by ν ᾱn .4 By a close inspection of the
proof of Theorem 2, we can check that under the constraint
αn = ν ᾱn , the message pairs are bounded by L1 /L∗1 +
L2 /L∗2 ≤ ν. Hence, to achieve L1 /L∗1 + L2 /L∗2 = κ, it should
follow that ν ≥ κ. Indeed, we can see that L1 /L∗1 +L2 /L∗2 = κ
is achievable with weight κᾱn from the direct part above, by
communicating κ fraction of the time and staying idle for the
remaining 1 − κ fraction.
Note that when αn = κᾱn , it follows from (28) that
D(Qαn kQ0 )
δ
= 0 and lim
= 0.
n→∞
n→∞ nαn
αn
Then, by combining (107)–(108), we have
lim

1
lim inf √ (log M1n + log M2n + log Kn )
n→∞
nδ
s
2D(Q1 kQ0 )2
= κL∗Z .
≥κ
χ2 (Q1 kQ0 )

(108)

AND

A PPENDIX A
P ROOF OF L EMMA 2
Proof: We will only prove (34) and (36) as the other two
bounds follow by swapping indices 1 with 2 and vice versa.
In addition, in this proof, we include the effect of the secret
key S. By Fano’s inequality,
H(Wj |Yjn , S) ≤ εn log Mjn + 1,

j ∈ {1, 2}.

(110)

Because W1 and W2 are uniform and independent of each
other and of S, we have
(log M1n )(1 − εn ) − 1 ≤ I(W1 ; Y1n |S)

(109)

Since κ = L1 /L∗1 + L2 /L∗2 , (109) immediately implies a
matching converse to (20).
VII. C ONCLUSION

BCs with feedback [31] but it does for other classes of
BCs. The natural question is whether feedback enlarges
the covert capacity region for various classes of BCs.

F UTURE W ORK

In this paper, we established the covert capacity region for
all two-user discrete and Gaussian memoryless BCs. Somewhat surprisingly, the most basic multi-user communication
strategy—time-division transmission—turns out to be optimal.
Our proof strategy provides further evidence that the concave
envelope characterization of bounds on capacity regions in
network information theory [18] is convenient and useful.
There are at least three promising avenues for future work.
1) Can we establish the strong converse property for BCs
under a covert communication requirement? We conjecture that Lε,δ (Definition 2) for all ε ∈ [0, 1) is
given by the time-division region given by (12) in Theorem 2. However, existing strong converse techniques for
BCs [23], [27]–[30] are not directly applicable. This is
because throughputs
in covert communications typically
√
scale as Θ( n) instead of being √
linear in n, so the
remainder terms (which scale as O( n) in state-of-theart results [29], [30]) resulting from the usual strong
converse techniques are not negligible. Note though
that the remainder terms in existing results are derived
without the covert communication requirement so it is
likely that they can be strengthened under this scenario.
2) What is the covert capacity region for BCs where
there are more than two legitimate receivers? While
Corollaries 1 and 2 hold for an arbitrary number of
legitimate receivers (see (17)), Theorem 2 does not seem
to generalize easily. At the very least, can we do the
same for all successively degraded BCs [9, Sec. 5.7]?
3) What is the covert capacity region for two-user BCs with
feedback? Unfortunately, the bound in Lemma 2 does
not hold for BCs with feedback. We note that feedback
does not enlarge the usual capacity region for degraded
4 We omit mulitplying ᾱ by the factor 1 + o(1) as this is inconsequential
n
in the (asymptotic) arguments that follows.

(log M1n + log M2n )(1 − εn ) − 2

(111)

≤ I(W1 ; Y1n |W2 , S)
+ I(W2 ; Y2n |S). (112)

We start by single letterizing (111) as follows:
(log M1n )(1 − εn ) − 1
n
X
I(W1 ; Y1i |Y1i−1 , S)
≤
≤
=

i=1
n
X

i=1
n
X

(113)

n
I(W1 , S, Y1i−1 , Y2,i+1
; Y1i )

(114)

I(U1i ; Y1i ),

(115)

i=1

where (115) follows from the identification U1i :=
n
(W1 , S, Y1i−1 , Y2,i+1
). This proves (34).
Next we single letterize (112) using the steps at the top
of the next page, where (120) follows from the Csiszár-sumn
identity [9] and the identification U2i := (W2 , S, Y1,i+1
, Y2i−1 )
and (121) follows from the fact that Xi is a function of
(W1 , W2 , S). This proves (36).
Acknowledgements
The authors thank Dr. Ligong Wang (ETIS—Université
Paris Seine, Université de Cergy-Pontoise, ENSEA, CNRS)
for helpful discussions in the initial phase of this work and
for pointing us to [16]. The first author also thanks Dr. Lei Yu
(NUS) for fruitful discussions on the relation of the present
work to stealth [26].
R EFERENCES
[1] B. A. Bash, D. Goekel, and D. Towsley. Limits of reliable communication with low probability of detection on AWGN channels. IEEE
Journal on Selected Areas in Communications, 31(9):1921–1930, Sep
2013.
[2] B. A. Bash, A. H. Gheorghe, M. Patel, J. L. Habif, D. Goeckel,
D. Towsley, and S. Guha. Quantum-secure covert communication on
bosonic channels. Nature Commun., 6:8626, Oct 2015.
[3] B. A. Bash, D. Goeckel, D. Towsley, and S. Guha. Hiding information
in noise: Fundamental limits of covert wireless communication. IEEE
Communications Magazine, 53(12):26–31, Dec 2015.
[4] P. H. Che, M. Bakshi, and S. Jaggi. Reliable deniable communication:
Hiding messages in noise. In Proc. of the Intl. Symp. on Inform. Th.,
pages 2945–2949, Istanbul, Turkey, Jul 2013.

12

(log M1n + log M2n )(1 − εn ) − 2
n
X
n
, S) + I(W2 ; Y2i |Y2i−1 , S)
I(W1 ; Y1i |W2 , Y1,i+1
≤
≤
=
=

i=1
n
X

i=1
n
X

i=1
n
X
i=1

n
I(W1 , Y2i−1 ; Y1i |W2 , S, Y1,i+1
) + I(W2 , S, Y2i−1 ; Y2i )

(117)

n
n
n
I(W1 , Y2i−1 ; Y1i |W2 , S, Y1,i+1
) + I(W2 , S, Y1,i+1
, Y2i−1 ; Y2i ) − I(Y1,i+1
; Y2i |W2 , S, Y2i−1 )

(118)

n
n
I(W1 ; Y1i |W2 , S, Y1,i+1
, Y2i−1 ) + I(Y2i−1 ; Y1i |W2 , S, Y1,i+1
)

n
n
+ I(W2 , S, Y1,i+1
, Y2i−1 ; Y2i ) − I(Y1,i+1
; Y2i |W2 , S, Y2i−1 )
n
X
I(W1 ; Y1i |U2i ) + I(U2i ; Y2i )
=

≤

i=1
n
X
i=1

(116)

I(Xi ; Y1i |U2i ) + I(U2i ; Y2i ),

[5] P. H. Che, M. Bakshi, C. Chan, and S. Jaggi. Reliable deniable
communication with channel uncertainty. In Proc. of the Inform. Th.
Workshop, pages 30–34, Hobart, Australia, Nov 2014.
[6] S. Lee, R. J. Baxley, M. A. Weitnauer, and B. Walkenhorst. Achieving
undetectable communication. IEEE Journal of Selected Topics in Signal
Processing, 9(7):1195–1205, Oct 2015.
[7] M. R. Bloch. Covert communication over noisy channels: A resolvability
perspective. IEEE Trans. on Inform. Th., 62(5):2334–2354, 2016.
[8] L. Wang, G. W. Wornell, and L. Zheng. Fundamental limits of
communication with low probability of detection. IEEE Trans. on
Inform. Th., 62(6):3493–3503, 2016.
[9] A. El Gamal and Y.-H. Kim. Network Information Theory. Cambridge
University Press, Cambridge, U.K., 2012.
[10] M. Tahmasbi and M. R. Bloch. Second-order asymptotics of covert
communications over noisy channels. In Proc. of the Intl. Symp. on
Inform. Th., pages 2224–2228, Barcelona, Spain, Jul 2016.
[11] M. Tahmasbi, M. R. Bloch, and V. Y. F. Tan. Error exponent for covert
communications over discrete memoryless channels. In Proc. of the
Inform. Th. Workshop, Kaohsiung, Taiwan, Nov 2017.
[12] S.-H. Lee, L. Wang, A. Khisti, and G. W. Wornell. Covert communication with noncausal channel-state information at the transmitter. In Proc.
of the Intl. Symp. on Inform. Th., pages 2830–2834, Aachen, Germany,
Jun 2017.
[13] L. Wang. Optimal throughput for covert communication over a classicalquantum channel. In Proc. of the Inform. Th. Workshop, pages 364–368,
Cambridge, UK, Sep 2016.
[14] K. S. K. Arumugam and M. R. Bloch. Keyless covert communication
over multiple-access channels. In Proc. of the Intl. Symp. on Inform.
Th., pages 2229–2233, Barcelona, Spain, Jul 2016.
[15] K. S. K. Arumugam and M. R. Bloch. Covert communication over
broadcast channels. In Proc. of the Inform. Th. Workshop, Kaohsiung,
Taiwan, Nov 2017.
[16] A. Lapidoth, E. Telatar, and R. Urbanke. On wide-band broadcast
channels. IEEE Trans. on Inform. Th., 49(12):3250–3258, Dec 2003.
[17] A. El Gamal. The capacity of a class of broadcast channels. IEEE
Trans. on Inform. Th., 25(2):166–169, 1979.
[18] C. Nair. Upper concave envelopes and auxiliary random variables.
International Journal of Advances in Engineering Sciences and Applied
Mathematics, 5(1):12–20, 2013.
[19] A. Wyner and J. Ziv. A theorem on the entropy of certain binary
sequences and applications–I. IEEE Trans. on Inform. Th., 19(6):769–
772, 1973.
[20] C. E. Shannon. A mathematical theory of communication. The Bell
Systems Technical Journal, 27:379–423, 1948.
[21] A. J. Stam. Some inequalities satisfied by the quantities of information
of Fisher and Shannon. Information and Control, 2:101–112, Jun 1959.

(119)
(120)
(121)

[22] T. Cover. Broadcast channels. IEEE Trans. on Inform. Th., 18(1):2–14,
1972.
[23] I. Csiszár and J. Körner. Information Theory: Coding Theorems for
Discrete Memoryless Systems. Cambridge University Press, 2011.
[24] E. L. Lehmann and J. P. Romano. Testing Statistical Hypotheses.
Springer-Verlag, New York, NY, 2005.
[25] R. G. Gallager. Capacity and coding for degraded broadcast channels.
Problems of Information Transmission, 10(3):3–14, 1974.
[26] J. Hou. Coding for relay networks and effective secrecy for wiretap
channels. PhD thesis, Technische Univ. München, Munich, Germany,
2014.
[27] M. Raginsky and I. Sason. Concentration of measure inequalities
in information theory, communications and coding. Foundations and
Trends ® in Communications and Information Theory, 10(1–2):1–247,
2013.
[28] Y. Oohama. New strong converse for asymmetric broadcast channels.
arXiv, 2016. arXiv:1604.02901.
[29] S. L. Fong and V. Y. F. Tan. A proof of the strong converse theorem
for Gaussian broadcast channels via the Gaussian Poincaré inequality.
IEEE Trans. on Inform. Th., 63(12), Dec 2017.
[30] J. Liu, R. van Handel, and S. Verdú. Beyond the blowing-up lemma:
Sharp converses via reverse hypercontractivity. In Proc. of the Intl.
Symp. on Inform. Th., pages 943–947, Aachen, Germany, Jun 2017.
[31] A. El Gamal. The feedback capacity of degraded broadcast channels
(corresp.). IEEE Trans. on Inform. Th., 24(3):379–381, 1978.

