Covert Single-hop Communication in a Wireless
Network with Distributed Artificial Noise
Generation
Ramin Soltani∗ , Boulat Bash† , Dennis Goeckel∗ , Saikat Guha‡ , and Don Towsley†

arXiv:1610.00384v2 [cs.IT] 28 Nov 2017

∗

Electrical and Computer Engineering Department, University of Massachusetts,

Amherst, {soltani, goeckel}@ecs.umass.edu † School of Computer Science, University
of Massachusetts, Amherst, {boulat, towsley}@cs.umass.edu ‡ Raytheon BBN
Technologies ,{sguha}@bbn.com

Abstract
Covert communication, also known as low probability of detection (LPD) communication, prevents the
adversary from knowing that a communication is taking place. Recent work has demonstrated that, in a threeparty scenario with a transmitter (Alice), intended recipient (Bob), and adversary (Warden Willie), the maximum
number of bits that can be transmitted reliably from Alice to Bob without detection by Willie, when additive
white Gaussian noise (AWGN) channels exist between all parties, is on the order of the square root of the
number of channel uses. In this paper, we begin consideration of network scenarios by studying the case where
there are additional “friendly” nodes present in the environment that can produce artificial noise to aid in
hiding the communication. We establish achievability results by considering constructions where the system
node closest to the warden produces artificial noise and demonstrate a significant improvement in the throughput
achieved covertly, without requiring close coordination between Alice and the noise-generating node. Conversely,
under mild restrictions on the communication strategy, we demonstrate no higher covert throughput is possible.
Extensions to the consideration of the achievable covert throughput when multiple wardens randomly located in
the environment collaborate to attempt detection of the transmitter are also considered.

This work has been supported, in part, by the National Science Foundation under grants CNS-1018464 and ECCS-1309573.
This work has been presented at the 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton, Monticello,
IL, October 2014. The final version of this work [1] has been submitted to the IEEE for possible publication.
Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media,
including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. DOI: 10.1109/ALLERTON.2014.7028575

1

I. I NTRODUCTION
The provisioning of security has emerged as a critical issue in wireless communications to prevent
unauthorized access to the information sent from the transmitter to the desired recipient. Standard
security approaches, whether they are computational (cryptographic) or information-theoretic, focus
on preventing the eavesdropper from obtaining the contents of the message. However, it has recently
become apparent that a significant threat to users’ privacy is not only the discovery of a message’s
content, but also the very existence of the message itself (e.g. the seeking of “meta-data,” as detailed
in the Snowden disclosures [2]). This motivates the consideration of covert (i.e. low probability of
detection) communications.
Historically, covert communication has been of military interest, and spread spectrum approaches
have been widely considered [3]. However, the fundamental limits of covert communication were only
recently established by a subset of the authors [4], [5], who presented a square root limit on the number
of bits that can be transmitted securely from the transmitter (Alice) to the intended receiver (Bob) when
there are additive white Gaussian noise (AWGN) channels between Alice and each of Bob and the
adversary (Warden Willie). In particular, by taking advantage of the non-zero noise power at Willie,
√
Alice can reliably transmit O( n) bits to Bob over n uses of a channel while lower bounding Willie’s
error probabilities PF A + PM D ≥ 1 −  for any  > 0 where PF A is the probability of false alarm and
√
PM D is the probability of mis-detection. Conversely, if Alice transmits more than O( n) bits over n
uses of channel, either Willie detects her with high probability or Bob suffers a non-zero probability
of decoding error as n goes to infinity. Covert communications has recently attracted the attention of
other researchers [6]–[8] and further work of the authors [9], [10].
In this paper, we turn our attention to the network case, where a collection of nodes work to establish
covert communication between a collection of source and destination pairs. The goal is to establish an
analog to the line of work on scalable low probability of intercept communications [11]–[14], which
considered the extension of [15], [16] to the secure multipair unicast problem in large wireless networks.
Here, in analog to [11], we consider how security between Alice and Bob can be improved when there
are a number of other nodes present in the environment. Whereas [11] considered low probability of
intercept (LPI) communications, which allowed pilot signaling for protocol set-up, the consideration of
covert communication is more challenging, as we assume that Willie allows no communications from
Alice whatsoever.
Consider a wireless network with AWGN channels between Alice and each of Bob and Willie. The
power received at any node is inversely proportional to dγ , where d is the distance of the receiver
from the transmitter and γ is the path-loss exponent. Alice attempts to communicate covertly with
2

Bob without detection by Willie, but also in the presence of other (friendly) network nodes to assist the
communication by producing background chatter to inhibit Willie’s ability to detect Alice’s transmission.
We assume the friendly nodes are distributed according to a two-dimensional Poisson point process of

density m = o n1/γ . Alice and Bob share a secret (codebook) that is unknown to Willie. For this
scenario, which is described in more detail in Section II, we show in Section III that Alice can covertly
√
transmit O(mγ/2 n) bits to the receiver Bob, who is a unit distance away, over n uses of the channel
while keeping Willie’s sum of error probabilities PF A +PM D ≥ 1− for any  ≥ 0, hence demonstrating
that the presence of friendly nodes, if sufficiently dense, can significantly improve covert throughput.
√
Conversely, if Alice attempts to transmit ω(mγ/2 n) bits to Bob over n uses of the channel, either
there exists a detector that Willie can use to detect her with arbitrarily low sum of error probabilities
PF A + PM D or Bob cannot decode the message with arbitrarily low probability of error. In Section IV,
the extension to the case of multiple collaborating Willies located in the field is also presented, which
establishes the framework for a single transmission on a multi-hop path in a large network.
II. P REREQUISITES
A. System Model
Consider a source Alice wishing to communicate with receiver Bob located at a unit distance away
in the presence of adversaries W1 , W2 , . . . , WNw , who are distributed independently and uniformly in
the unit square shown in Fig. 1 and seek to detect any transmission by Alice. When there is only a
single Willie, we omit the subscript and denote it by W . Also present are friendly nodes allied with
Alice and Bob. These nodes, which are distributed according to a two-dimensional point process with
density m = o(n1/γ ), where γ is the path-loss exponent, are willing to help hide Alice’s transmission by
generating noise. We assume that the system is able to determine which friendly node is the closest to
each Willie. The adversaries try to detect whether Alice is transmitting or not by processing their received
signals and applying hypothesis testing on them, as discussed in the next subsection. We consider three
scenarios: single Willie located half way between Alice and Bob, single Willie located randomly and
uniformly in the 1 by 1 square shown as a dashed box in Fig. 1, and multiple Willies scenario where Nw
Willies are located independently and randomly in the unit box. Discrete-time AWGN channels with
real-valued symbols are assumed for all channels. Alice transmits n real-valued symbols f1 , f2 , ..., fn .
Each friendly node is either on or off according to the strategy employed. Let θj be one when the j th
friendly node is “on” (transmits noise) and zero otherwise (silent). If Rj is on, it transmits symbols
(j)

(j)

∞
{fi }∞
i=1 , where {fi }i=1 is a collection of independent and identically distributed (i.i.d.) zero-mean

Gaussian random variables, each with variance (power) Pr .
3

Fig. 1. System Configuration: Source node A wishes to communicate reliably and without detection to the intended receiver B at distance
one (normalized) with the assistance of friendly nodes (represented by solid nodes in the figure) distibuted according to a two-dimensional
point process with density m in the presence of adversary nodes W1 , W2 , . . . , WNw located in the dashed box (Nw = 3 in the figure).

(b)

(b)

(b)

(b)

(b)

(b)

Bob receives y1 , y2 , ..., yn where yi = fi + zi for 1 ≤ i ≤ n. The noise component is zi =
P
(b,rj )
(b )
(b )
, where {zi 0 }ni=1 is an i.i.d sequence representing the background noise of Bob’s
zi 0 + ∞
j=1 θj zj
(b,rj ) n
}i=1

receiver with zib0 ∼ N (0, σb20 ) for all i, and {zi

is an i.i.d. sequence of received noise samples
(b,rj ) 2

caused by chatter from the j th friendly node when it is “on”, with E[|zj

| ]=

Pr
dγb,r

, where dx,y is the
j

distance between node x and node y.
(w )

(w )

(w )

(w )

(w )

Similarly, the k th Willie (1 ≤ k ≤ Nw ) observes y1 k , y2 k , ..., yn k where yi k = fi + zi k . Here,
P
(wk ,rj )
(w )
(w )
(w )
zi k = zi k 0 + ∞
where {zi k 0 }ni=1 is an i.i.d sequence representing the background
j=1 θj zj
(wk 0 )

noise at Willie’s receiver, where zi

(wk ,rj ) n
}i=1

∼ N (0, σw2 k ,0 ) for all i, and {zi

is the i.i.d sequence

of received noise samples caused by chatter from the j th friendly node when it is ”on” with variance
Pr
dγwk ,rj

.

Note that we assume Alice and the friendly nodes, while having a common goal, are not able to
closely align their transmissions; that is, the friendly nodes set up a constant power background chatter
but are not able to, for example, lower their power at the time Alice transmits.

4

B. Hypothesis Testing
Consider the case of a single Willie. We assume he applies a hypothesis test to his received signal to
determine whether or not Alice is communicating with Bob. This test is performed according to Willie’s
knowledge about his channel to Alice. When Alice is not transmitting, Willie expects to observe Gaussian
white noise along with transmissions from other nodes and, when Alice is transmitting, he expects to
observe a signal with greater power. We denote the probability distribution of Willie’s collection of
(w0 ) n
}i=1

observations {yi

by P1 when Alice is communicating with Bob, and the distribution of the

observations when she is not transmitting by P0 .
There are two hypotheses, H0 and H1 . The null hypothesis (H0 ) corresponds to the case that Alice is
not transmitting, and the alternative hypothesis H1 corresponds to the case that Alice is transmitting. We
denote by PF A as the probability of rejecting H0 when it is true (type I error or false alarm), and PM D
as the probability of rejecting H1 when it is true (type II error or mis-detection). We assume that Willie
uses classical hypothesis testing with equal prior probabilities and seeks to minimize PF A + PM D ;
the generalization to arbitrary prior probabilities is straightforward [5]. For a scenario with multiple
collaborating Willies (Theorem 3), the received signals are processed together at a server to arrive at a
single collective decision as to whether Alice is transmitting or not.
C. Reliability and Covertness
We define Alice’s transmission as reliable if and only if the desired receiver (Bob) can decode her
message with arbitrarily low average probability of error Pe at long block lengths, where the average
is over the node locations. In other words, for any ζ > 0, Bob can achieve Pe < ζ as n → ∞.
Alice’s transmission is covert if and only if she can lower bound Willie’s (or Willies’, for scenarios
with multiple adversary nodes) average sum of probabilities of error (E [PF A + PM D ]) by 1 −  for any
 > 0, as n → ∞ [5].
III. C OVERT C OMMUNICATION IN THE P RESENCE A S INGLE WARDEN AND m F RIENDLY N ODES
In this section, we first consider the case where there is only one Willie located half-way between
Alice and Bob. To hide the presence of Alice’s transmission, we turn on the friendly node closest
to Willie and then analyze Willie’s ability to detect Alice’s transmission. This allows us to derive
a restriction on Alice’s power required to maintain covertness. The achievability proof concludes by
considering the rate at which reliable decoding is still possible under this restriction on Alice’s power
level. A converse under mild restrictions on the signaling scheme is also provided. After considering the

5

case where Willie is located half-way between Alice and Bob in Theorem 1, we analyze the problem of
a single Willie located randomly and uniformly in the 1 by 1 square shown as a dashed box in Fig. 1.

Theorem 1. When friendly nodes are distributed such that m = o n1/γ and m = ω(1) and there is
one warden (Willie) located half-way between Alice and Bob, Alice can reliably and covertly transmit
√
O(mγ/2 n) bits to Bob over n uses of the channel.
√
Conversely, if Alice attempts to transmit ω(mγ/2 n) bits to Bob over n uses of channel, either
there exists a detector that Willie can use to detect her with arbitrarily low sum of error probabilities
PF A + PM D or Bob cannot decode the message with arbitrarily low probability of error.
Proof. (Achievability)
Construction: To establish secret communication, Alice and Bob share a codebook that is not revealed
to Willie. For each message transmission of length M , Alice uses a new codebook to encode the message
into a codeword of length n at the rate of R =
l=2nR

are used; that is, codewords {C(Wl )}l=1

M
.
n

To build a codebook, random coding arguments
nR

are associated with messages {Wl }l=2
l=1 , where each of

u=n
the codewords C(Wl ) = {C (u) (Wl )}u=1
includes random symbols C (u) (Wl ) ∼ N (0, Pf ) where Pf is

defined later. At the receiver, Bob employs a maximum-likelihood (ML) decoder to process his received
signal.
To establish a covert communication, Alice and Bob’s strategy is to turn on the closest friendly node
to Willie and keep all other friendly nodes off, whether Alice is transmitting or not. Therefore, Willie’s
observed noise power is given by
σw2 = σw2 0 +

Pr
,
dγr,w

(1)

where σw2 0 is Willie’s noise power when none of the friendly nodes are transmitting and dr,w is the
(random) distance of the closest friendly node to Willie; hence, σw2 is a random variable which depends
on the locations of the friendly nodes.
Analysis: When Willie applies the optimal hypothesis test [5]:
r

n
ER [PF A + PM D ] ≥ 1 − ER
D(Pw ||Ps )
2

(2)

where ER [.] denotes the expected value over all possible locations of the friendly nodes, D(Pw ||Ps ) is
the relative entropy between Pw and Ps , Pw = N (0, σw2 ) is the probability distribution function (pdf)
(w0 )

for each of Willie’s observations zi

when Alice is not transmitting and Ps = N (0, σw2 +

pdf for each of the corresponding observations when Alice is transmitting.

6

Pf
)
dγw,a

is the

We next show how Alice can lower bound the sum of average error probabilities by upper bounding

p n
D(P
||P
)
. For the given Pw and Ps we calculate the relative entropy [5]:
ER
w
s
2
Z
p0 (x)
D(Pw ||Ps ) = p0 (x) ln
dx
p1 (x)
x





−1 !−1
1
Pf
Pf
.
= ln 1 + γ 2 − 1 +
(3)
γ
2
dw,a σw
dw,a σw2
γ/2

Suppose Alice sets her average symbol power Pf ≤ cm√n where c is a constant defined later. Since m

is o n1/γ , for n large enough Pf ≤ 2σw2 0 dγw,a < 2σw2 dγw,a . Then, using the Taylor series expansion at
Pf = 0 yields

D(Pw ||Ps ) <

2

Pf

.

2dγw,a σw2

(4)

Since dw,a = 21 ,
r
ER

n
D(Pw ||Ps )
2



r

 
n
1
< 2 Pf
ER 2
2
σw
 
γ−1
2
1
≤ √ cmγ/2 ER 2 .
σw
2
γ−1

(5)

Due to the Poisson assumption, the pdf of dr,w is easily obtained as
2

fdr,w (x) = 2mπx e−mπx .

(6)

Therefore,
γ/2

m


ER




1
1
γ/2
= m ER 2
σw2
σw0 + Pr /dγr,w



mγ/2
ER dγr,w
Pr
Z
2mγ/2+1 π x=∞ γ+1 −mπx2
x e
dx
=
Pr
x=0
Γ (γ/2 + 1)
=
,
(7)
2Pr π γ/2+1
−1
√ 
p n

Γ(γ/2+1)
where Γ(.) is the Gamma function. If Alice sets c ≤ 2γ−12 2P
,
she
can
achieve
E
D(P
||P
)
<
R
w
s
γ/2+1
2
rπ
≤

. Thus, with Pf ≤

γ/2
cm
√ ,
n

Alice can covertly transmit to Bob. Note that Alice does not use the locations

of the friendly nodes to select the transmission power (and thus, per below, the corresponding rate).
Rather, she can choose a power and corresponding rate that is covert when averaged over the locations
of the friendly nodes.
Now, we analyze Bob’s decoding error probability averaged over all possible codewords and locations
of friendly nodes. For Bob’s ML decoder, the decoding error probability averaged over all possible

7

codewords conditioned on σb2 = σb20 +

Pr
dγr,b

where dr,b is the distance from Bob to the relay closest to

Willie, is upper bounded using (5)-(9) in [5]:

log
nR− n
2 1+
2


2

Pe σb ≤ 2

Pf
2σ 2
b





cmγ/2
nR− n
log
1+
√
2
2
2
2 nσ

=2

log2 1 +

ρ
2

If the rate is set to R =

cmγ/2
√
2 n(σb2 +4γ Pr )

b

.

(8)


, 0 < ρ < 1,

0


Pe

σb2 dr,b >

1
4

−(1−ρ) n
2



≤2
=

≤

log2

γ/2
1+ √ cm
2 n σ 2 +4γ Pr
b0

(

!

)

!−(1−ρ) n2
cmγ/2

1+ √
2 n σb20 + 4γ Pr
!−1
√
cmγ/2 n(1 − ρ)

1+
.
4 σb20 + 4γ Pr

(9)

where (9) is due to (1 + x)r ≤ (1 − rx)−1 for any r < 0 and x > 0. The expected value of Pe (σb2 ) over
all possible values of the distance of the closest friendly node to Willie is:





1
1
2
2
Pe = ER Pe σb = ER Pe σb dr,b ≤
P(dr,b ≤ )
4
4



1
1
P(dr,b > )
+ ER Pe σb2 dr,b >
4
4

(10)

Consider

ER

Pe σb2



dr,b

 



1
1
1
≤
P dr,b ≤
≤ P dr,b ≤
4
4
4


1
≤ P dr,w >
4
1 2

= e−πm( 4 )

(11)

Next, consider the term in (10):


 

1
1
ER Pe
drb >
P drb >
4
4



1
≤ ER Pe σb2 drb >
4



1
2
≤ ER Pe σb drb =
4
√ !−1
c(1 − ρ)mγ/2 n

= 1+
.
4 σb20 + 4γ Pr
σb2



8

(12)

(13)

Thus, by Eqs. (10), (11), (12), lim Pe = 0 and, for any 0 < ζ < 1, Pe < ζ.
m→∞


Now, we calculate the average number of bits that Bob can receive. Since m is o n1/γ , for n large
cm√γ/2
2 n

< 2σb2 . Based on the fact that for any 0 < x < 1, log2 (1 + x) ≥ x
√
nρcmγ/2
.
nR ≥
4 σb20 + 4γ Pr
√
Thus, Bob receives O(mγ/2 n) bits in n channel uses.
enough

(14)

n
on
(w)
(Converse) Suppose Willie uses a power detector on his collection of observations yi
to form
i=1
2

P
(w)
and performs a hypothesis test based on the comparison of S to a threshold t.
S = n1 ni=1 yi
When H0 is true [5]
E[S] = σw2

(15)

2σw4
n

(16)

E[S] = σw2 + Pk

(17)

Var[S] =
When H1 is true

Var[S] =

4Pk σw2 + 2σw4
n

(18)

where Pk is the power of the codeword sent by Alice. If S < σw2 + t, Willie accepts H0 ; otherwise, he
accepts H1 . Bounding PF A by using Chebyshev’s inequality yields [5]:
PF A ≤

2σw4
nt2

(19)

Therefore
ER [PF A ] = ER [PF A | dr,w ≤ η1 ] P(dr,w ≤ η1 )
+ ER [PF A | dr,w > η1 ] P(dr,w > η1 )
≤ P(dr,w ≤ η1 ) + ER [PF A | dr,w > η1 ]

2
Pr
2


2 σw0 + ηγ
2
1
≤ 1 − e−mπη1 +
2
nt
q

√ 
4
ln ( 4−λ
)
2
2
P
2
r
∀η1 > 0. Let Willie choose threshold t = √nλ σw0 + ηγ where η1 <
. Then
mπ

(20)

1

π  2nλ
λ
ER [PF A ] < 1 − 1 −
+
=
4
8n
2




(21)

In addition, Willie can upper bound PM D by (16) in [5]
PM D ≤

4Pk σw2 + 2σw4
n (Pk − t)2

9

(22)

Therefore
ER [PM D ] = ER [PM D | drw ≤ η2 ] P(drw ≤ η2 )
+ ER [PM D | drw > η2 ] P(drw > η2 )
≤ P(drw ≤ η2 ) + ER [PM D | drw > η2 ]


Pr
2


4P
σ
+
γ
k
w0
η2
2
≤ 1 − e−mπη2 +
n (Pk − t)2
2

2 σw2 0 + Pηγr
2
+
n (Pk − t)2
q

(23)

2
ln ( 2−λ+λ
0)

 γ/2 
m√
0
1/γ
,
where
0
<
λ
<
λ.
Since
m
is
o(n
)
and
t
is
Θ
, if
mπ
n
 γ/2 
Alice sets her average symbol power Pk = ω m√n , then there exists n0 > 0 s.t. ∀n > n0 (λ0 )
∀η2 > 0. We now set η2 =

ER [PM D ] ≤
Therefore

λ
2

λ
λ − λ0 λ0
+
=
2
2
2

and PF A + PM D < λ for any λ > 0.

Thus, to avoid detection for a given codeword, Alice must set the power of that codeword to PU =
 γ/2 
O m√n . Suppose that Alice’s codebook contains a fraction ξ > 0 of codewords with power PU =
 γ/2 
O m√n . Bob’s decoding error probability of such low power codewords is lower bounded by (Eq.
(20) in [5])
PUe
Since Alice’s rate is R = ω



m√γ/2
n



≥1−

bits/symbol,

PU
+ n1
2σb2
log2 ξ
+R
n

(24)

lim PUe is bounded away from zero.

n,m→∞


Theorem 2. When friendly nodes are distributed such that m = o n1/γ and m = w (1), and there is
just one warden (Willie) located randomly and uniformly over the unit square shown in Fig. 1, Alice
√
can reliably and covertly transmit O(mγ/2 n) bits to Bob over n uses of the channel.
Proof. Construction: We use the same construction and strategy as in Theorem 1.
Analysis: By Eqs. (2) and (4)
ER,W [PF A + PM D |dw,a > ψ]
r


n
Pf
≥1−
ER,W
dw,a > ψ
2
2σw2 dγw,a

10

(25)

where ER,W denotes the expectation over all locations of friendly nodes and Willie and ψ is a parameter
such that 0 < ψ < 21 . Suppose Alice sets Pf ≤

As in Eq. (7), ER,W

h

mγ/2
2
σw

γ/2
cm
√
n

where c is a constant defined later. Therefore,

ER,W [PF A + PM D | dw,a > ψ]
 γ/2

c
m
≥ 1 − √ ER,W
dw,a > ψ
σw2 dγw,a
2 2
 γ/2

c
m
≥1− √
ER,W
dw,a > ψ ,
σw2
2 2ψ γ
i
Γ(γ/2+1)
dw,a > ψ ≤ 2P
γ/2+1 . Therefore,
rπ

cΓ (γ/2 + 1)
ER,W [ PF A + PM D | dw,a > ψ] ≥ 1 − √
,
4 2ψ γ Pr π γ/2+1

(26)

(27)

2

Since ψ ≤ 12 , P(dw,a > ψ) = 1 − π ψ2 . The law of total expectation yields
ER,W [PF A + PM D ]
≥ ER,W [PF A + PM D | dw,a > ψ] P(dw,a > ψ)



cΓ (γ/2 + 1)
ψ2
≥ 1− √
1−π
2
4 2ψ γ Pr π γ/2+1


2
cΓ (γ/2 + 1)
ψ
≥ 1− √
−π
(28)
2
4 2ψ γ Pr π γ/2+1
q
−1

Γ(γ/2+1)
√
Now, first choosing ψ = 2
and
then
c
=

, ER,W [PF A + PM D ] ≥ 1 −  for any
4 2ψ γ Pr π γ/2+1
 π 
mγ/2

 > 0 as long as Pf = O √ .
n
Next, we analyze Bob’s ML decoder. The law of total expectation yields
Pe = ER,W [Pe (σb2 , d2w,a )]
≤ ER,W [Pe (σb2 , d2w,a )|dr,b > φ]
+ P (dr,b ≤ φ)

(29)

where dr,b is the distance between Bob andthe closest friendly node to Willie, and 0 < φ ≤ 1. If the
γ/2
rate is set to R = ρ2 log2 1 + 2√ncm
, when 0 < ρ < 1, by (9), the first term on the RHS of
2 + Pr
σ
( b 0 φγ )
Eq. (29) is:
√ !−1
γ/2
c(1
−
ρ)m
n
ER,W [Pe (σb2 , d2w,a )|dr,b > φ] ≤ 1 +
(30)
P
4(σb20 + φγr )

Since m = o n1/γ , lim ER,W [Pe (σb2 , d2w,a )|dr,b > φ] = 0. Now, consider P (dr,b ≤ φ). Since {dr,b ≤
m,n→∞

φ} ⊂ {{dw,b ≤ 2φ} ∪ {dr,w ≥ φ}}, P (dr,b ≤ φ) ≤ P (dw,b ≤ 2φ) + P (dr,w ≥ φ). As m → ∞,

11

2

P (dr,w ≥ φ) → 0 and thus the right side approaches 2πφ . Thus, setting φ =

q

ζ
2π

means lim Pe < ζ
m,n→∞

for any 0 < ζ < 1.
Next, we calculate the average number of bits that Bob can receive. Similar to the approach that
√
√
γ/2
γ/2
n) bits in n
leads to Eq. (14), we can easily show that nR ≥ 4 σnρcm
2 + Pr . Thus, Bob receives O(m
( b 0 φγ )
channel uses.
IV. C OVERT C OMMUNICATION IN THE P RESENCE A M ULTIPLE C OLLABORATING WARDENS
In this section, we consider case when there are Nw collaborating Willies located independently in
the 1 by 1 square.

Theorem 3. When friendly nodes are distributed such that m = o n1/γ and m = ω(1) and Nw =
 γ 
O m γ+2 collaborating Willies are uniformly and independently distributed over the unit square shown
 γ/2 √ 
in Fig. 1, Alice can reliably and covertly transmit O mN 2+γ n bits to Bob over n uses of the channel.
w

Proof. Construction: The codebook construction is same as that in Theorem 1. Analogously to the
constructions of Theorems 1 and 2, Alice and Bob’s strategy is to turn on the closest friendly node to
each Willie and keep all other friendly nodes off, whether Alice is transmitting or not.
Analysis: When Willie applies the optimal hypothesis test, Pinsker’s Inequality (Lemma 11.6.1 in
[17]) yields [5]
r
PF A + PM D ≥ 1 −

1
D(P1 ||P0 ).
2

(31)

Here, P0 and P1 are the joint probability distributions of Willies’ channels observations for the H0
and H1 hypotheses respectively; in other words
(w1 )T

P0 = [P0

(w1 )T

P1 = [P1
(wk )

where P0

(w2 )T

P0

(w2 )T

P1

(wNw )T T

. . . P0

]

(wNw )T T

. . . P1

]

(32)

(33)

is the vector probability distribution of the channel observation of Willie Wk (1 ≤ k ≤ Nw )

when H0 is true and includes n elements with the same probability distribution Pwk = N (0, σw2 k ). In
(wk )

addition, P1

is the channel observation of Willie Wk when H1 is true and includes n elements, each

with the same probability distribution Pwk = N (0, σw2 k +

Pf
).
dγwk ,a

The relative entropy between two multivariate normal distributions P1 and P0 is given by [18]:

1
> −1
D(P1 ||P0 ) =
tr Σ−1
0 Σ1 + (µ0 − µ1 ) Σ0 (µ0 − µ1 )
2


|Σ1 |
− dim (Σ0 ) − ln
|Σ0 |

12

(34)

where tr(.), |.|, and dim(.) denote the trace, determinant and dimension of a square matrix respectively,
µ0 = 0, µ1 = 0 are the mean vectors, and Σ0 , Σ1 are nonsingular covariance matrices of P0 and P1
respectively and are given by
Σ0 = S ⊗ In×n

(35)


Σ1 = S + Pf U U T ⊗ In×n

(36)

where S = diag(σw2 1 , ... , σw2 Nw ), ⊗ denotes the Kronecker product between two matrices, In×n is the
identity matrix of size n, and U is a column vector of size Nw given by

T
1
1
1
U = dγ/2 dγ/2 . . . dγ/2
w1 ,a

wN ,a
w

w2 ,a

(37)

Next, we calculate the relative entropy in (34). The first term of the RHS of (34) is:


Nw
X

Pf
1
2
−1
tr Σ0 Σ1 = n
σwk + γ
σ2
dwk ,a
k=1 wk
= nNw + n

Nw
X
k=1

Pf
γ
dwk ,a σw2 k

(38)

Then,
|Σ0 | = |S ⊗ In×n |
= |S|n |In×n |Nw

(39)

= |S|n
=

Nw
Y

!n
σw2 k

.

(40)

k=1

where (39) is due to the determinant of the kronecker product property presented in [19]. Because each
of the Willies has non-zero noise variance, S is nonsingular. Therefore,
|Σ1 | = S + Pf U U T

n

= S + Pf U U T

n

|In×n |Nw

= |S|n I + Pf S −1 U U T

n

= |S|n 1 + Pf U T S −1 U

n

= |Σ0 | 1 +

Nw
X
k=1

Pf
γ
dwk ,a σw2 k

where step (41) is due to Lemma 1.1 in [20]. Therefore,
!


Nw
X
|Σ1 |
Pf
ln
= n ln 1 +
.
γ
2
|Σ0 |
d
wk ,a σwk
k=1

13

(41)

!n
(42)

(43)

Thus,
n
D(P1 ||P0 ) =
2

Nw
X
k=1

Nw
X
Pf
Pf
−
ln
1
+
γ
γ
2
dwk ,a σwk
dwk ,a σw2 k
k=1

!!
.

(44)

γ/2

cm
Suppose Alice sets her average symbol power Pf ≤ √
where c is a constant defined later. Since
nNw

P
Pf
w
m = o n1/γ , for n large enough N
k=1 dγw ,a σ 2 < 1. Therefore
k

wk

n
D(P1 ||P0 ) ≤
4

Nw
X
k=1

Pf
γ
dwk ,a σw2 k

!2
.

(45)

as long as dwk ,a > κ for all k. Assume Q is the event that dwk ,a > κ for all k where 0 < κ < 12 . By
Eqs. (31) and (45)

As we obtained in (7), ER,W

ER,W [PF A + PM D | Q]
" r N
#
w
Pf
1 nX
≥ 1 − ER,W
Q
2 2 k=1 dγwk ,a σw2 k
"N
#
w
X
mγ/2
c
ER,W
Q
≥1− √
dγwk ,a σw2 k
2 2Nw
k=1
 γ/2 
Nw
X
c
m
ER,W
Q
≥1− √
σw2 k
2 2Nw κγ k=1
h γ/2
i
Γ(γ/2+1)
m
dwk ,a > κ ≤ 2P
γ/2+1 for all k. Therefore,
σ2
rπ

(46)

wk

cΓ (γ/2 + 1)
ER,W [ PF A + PM D | Q] ≥ 1 − √
2 2κγ 2Pr π γ/2+1
N w

2
Since κ < 21 , P(Q) = 1 − πκ2
. Then, the law of total expectation yields

(47)

ER,W [PF A + PM D ]
≥ ER,W [PF A + PM D | Q] P(Q)

N

cΓ (γ/2 + 1)
πκ2 w
≥ 1− √
1−
2
2 2κγ 2Pr π γ/2+1




N
w
πκ2
cΓ (γ/2 + 1)
√
≥ 1−
.
(48)
−
2
2 2κγ 2Pr π γ/2+1
r 

−1
 1 
Γ(γ/2+1)
Thus, for any  > 0 and Nw , κ = π2 1 − 1 − 2 Nw and c = 2 4√2κ
yields ER,W [PF A +
γ P π γ/2+1
r


mγ/2
PM D ] ≥ 1 −  as long as Pf = O  √ 1+γ/2 .
nNw

14

Next, we analyze Bob’s ML decoding error probability over all possible codewords as well as the
locations of Willies and closest friendly node to each Willie. Bob’s noise power is given by
σb2

≤

σb20

Nw
X
Pr
+
d2
k=1 rk ,b

(49)

where drk ,b is the distance between Bob and the closest friendly node to Willie Wk . Suppose G is the
event that drk ,b > δ for all k where 0 ≤ δ ≤ 1. Therefore

Pe = ER,W [Pe σb2 ]

≤ ER,W [Pe σb2 |G] + P(Ḡ)

ρ
Similar to what we did in (8)-(9), if the rate is set to R = 2 log2 1 +
c1 =

γ/2
cNw

c1 mγ/2
1+γ/2 √
r
2Nw
n σb2 +Nw P
δγ
0

(

)

(50)

, where

and 0 < ρ < 1, the first term of the RHS of (50) is

ER,W [Pe |G] ≤ ER,W [Pe |dr1 ,b = · · · = drNw ,b = δ]
!−1
√
c1 (1 − ρ)mγ/2 n
.
(51)
= 1+

1+γ/2
4Nw
σb20 + NδwγPr
q
 γ 
2ζ
.
If
we
set
N
=
o
m 2+γ , lim ER,W [Pe |G] = 0. Consider
For a given Nw , choose δ = 21 πN
w
w
m,Nw →∞

P Ḡ
!
Nw
[

drk ,b ≤ δ
P Ḡ = P
k=1

≤

Nw
X

P (drk ,b ≤ δ)

k=1

= Nw P (dr1 ,b ≤ δ)
≤ Nw (P (dw1 ,b ≤ 2δ) + P (dr1 ,w1 ≥ δ))


(2δ)2
−mπδ 2
≤ Nw π
+e
2
2

Then, Nw e−mπδ → 0 as m → ∞, and

(52)

lim Pe < ζ for any 0 < ζ < 1.

m,n→∞

Now, we calculate the number of bits that Bob receives. Similar to the approach that leads to Eq. (14),
q
√
γ/2
2ζ
1
.
Since
δ
=
we can easily show that nR ≥ 1+γ/2nρc12m
, for m, n, Nw large enough
2
πNw
4Nw
(σb0 +Nw Pδγr )

√
ζ γ/2
nρc1 mγ/2 2π
nR ≥
4Nw2+γ Pr
 γ/2 √ 
Therefore, Bob receives O mN 2+γ n bits in n channel uses.
w

15

V. C ONCLUSION
In this paper, we have considered the first step in establishing low probability of detection (LPD)
√
communications in a network scenario. We established that Alice can transmit O(mγ/2 n) bits reliably
to the desired recipient Bob in n channel uses without detection by an adversary Willie if randomly
distributed system nodes of density m are available to aid in jamming Willie; conversely, no higher
covert rate is possible. The presence of multiple collaborating wardens inhibits communication in two
separate ways - increasing the effective signal-to-noise ratio (SNR) at the wardens’ decision point, and
requiring more interference which inhibits Bob’s ability to reliably decode the message. Future work
consists of embedding the results of this single-hop formulation into large multi-hop covert networks.
R EFERENCES
[1] R. Soltani, D. Goeckel, D. Towsley, B. Bash, and S. Guha, “Covert wireless communication with artificial noise generation,” arXiv
preprint arXiv:1709.07096, 2017.
[2] “Edward Snowden: Leaks that exposed US spy programme.” http://www.bbc.com/news/world-us-canada-23123964, Jan 2014.
[3] M. K. Simon, J. K. Omura, R. A. Scholtz, and B. K. Levitt, Spread Spectrum Communications Handbook. McGraw-Hill, 1994.
[4] B. Bash, D. Goeckel, and D. Towsley, “Square root law for communication with low probability of detection on AWGN channels,”
in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pp. 448–452, July 2012.
[5] B. Bash, D. Goeckel, and D. Towsley, “Limits of reliable communication with low probability of detection on AWGN channels,”
Selected Areas in Communications, IEEE Journal on, vol. 31, pp. 1921–1930, September 2013.
[6] P. H. Che, M. Bakshi, and S. Jaggi, “Reliable deniable communication: Hiding messages in noise,” in Information Theory Proceedings
(ISIT), 2013 IEEE International Symposium on, pp. 2945–2949, July 2013.
[7] S. Kadhe, S. Jaggi, M. Bakshi, and A. Sprintson, “Reliable, deniable, and hidable communication over multipath networks,” in
Information Theory Proceedings (ISIT), 2014 IEEE International Symposium on.
[8] J. Hou and G. Kramer, “Effective secrecy: Reliability, confusion and stealth,” in Information Theory Proceedings (ISIT), 2014 IEEE
International Symposium on.
[9] B. Bash, S. Guha, D. Goeckel, and D. Towsley, “Quantum noise limited optical communication with low probability of detection,”
in Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pp. 1715–1719, July 2013.
[10] B. A. Bash, D. Goeckel, and D. Towsley, “LPD Communication when the Warden Does Not Know When,” in Information Theory
Proceedings (ISIT), 2014 IEEE International Symposium on.
[11] D. Goeckel, S. Vasudevan, D. Towsley, S. Adams, Z. Ding, and K. Leung, “Artificial noise generation from cooperative relays
for everlasting secrecy in two-hop wireless networks,” Selected Areas in Communications: Special Issue on Advances in Military
Communications and Networking, IEEE Journal on, vol. 29, pp. 2067–2076, December 2011.
[12] S. Vasudevan, D. Goeckel, and D. F. Towsley, “Security-capacity trade-off in large wireless networks using keyless secrecy,” in
MobiHoc, pp. 21–30, 2010.
[13] C. Capar, D. Goeckel, B. Liu, and D. Towsley, “Secret communication in large wireless networks without eavesdropper location
information,” in INFOCOM, 2012 Proceedings IEEE, pp. 1152–1160, March 2012.
[14] C. Capar and D. Goeckel, “Network coding for facilitating secrecy in large wireless networks,” in Information Sciences and Systems
(CISS), 2012 46th Annual Conference on, pp. 1–6, March 2012.
[15] P. Gupta and P. Kumar, “The capacity of wireless networks,” Information Theory, IEEE Transactions on, vol. 46, pp. 388–404, Mar
2000.

16

[16] M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, “Closing the gap in the capacity of wireless networks via percolation theory,”
Information Theory, IEEE Transactions on, vol. 53, pp. 1009–1018, March 2007.
[17] T. M. Cover and J. A. Thomas, Elements of Information Theory. Hoboken, N.J. : Wiley-Interscience, 2nd ed., 2006.
[18] F. Nielsen and R. Nock, “Clustering multivariate normal distributions,” in Emerging Trends in Visual Computing (F. Nielsen, ed.),
vol. 5416 of Lecture Notes in Computer Science, pp. 164–174, Springer Berlin Heidelberg, 2009.
[19] K. M. Abadir and J. R. Magnus, Matrix Algebra, pp. 279–280. Cambridge ; New York : Cambridge University Press.
[20] J. Ding and A. Zhou, “Eigenvalues of rank-one updated matrices with some applications,” Applied Mathematics Letters, vol. 20,
no. 12, pp. 1223 – 1226, 2007.

17

