1

Wiretap Channels: Nonasymptotic
Fundamental Limits
Wei Yang, Member, IEEE, Rafael F. Schaefer, Senior Member, IEEE,

arXiv:1706.03866v1 [cs.IT] 12 Jun 2017

and H. Vincent Poor, Fellow, IEEE

Abstract
This paper investigates the maximal secret communication rate over a wiretap channel subject
to reliability and secrecy constraints at a given blocklength. New achievability and converse bounds
are derived, which are uniformly tighter than existing bounds, and lead to the tightest bounds on the
second-order coding rate for discrete memoryless and Gaussian wiretap channels. The exact secondorder coding rate is established for semi-deterministic wiretap channels, which characterizes the optimal
tradeoff between reliability and secrecy in the finite-blocklength regime. Underlying our achievability
bounds are two new privacy amplification results, which not only refine the existing results, but also
achieve stronger notions of secrecy.

I. I NTRODUCTION
The pioneering work of Wyner [1] and Csiszár and Körner [2] has characterized the maximal secret communication rate – called the secrecy capacity – at which information can be
transmitted securely and reliably over a wiretap channel. In particular, it was shown that both
The work of H. V. Poor and W. Yang was supported in part by the US National Science Foundation under Grants CNS1702808, ECCS-1343210 and ECCS-1647198. The work of R. F. Schaefer was supported by the German Research Foundation
(DFG) under Grant WY 151/2-1. The material of this paper was presented in part at the IEEE International Symposium on
Information Theory (ISIT), Barcelona, Spain, July 2016, and the IEEE International Symposium on Information Theory (ISIT),
Aachen, Germany, June 2017.
W. Yang and H. V. Poor are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA
(email: {weiy, poor}@princeton.edu).
R. F. Schaefer is with the Information Theory and Applications Chair, Technische Universität Berlin, 10587 Berlin, Germany
(email: rafael.schaefer@tu-berlin.de).

June 14, 2017

DRAFT

2

the error probability and the information leakage can be made as small as desired, as long
as the transmission rate is below the secrecy capacity and as long as the data are mapped to
sufficiently long codewords. Since then, there have been extensive studies on the secrecy capacity
of different wiretap models as well as schemes that achieve the secrecy capacity (see [3] and [4]
for a comprehensive treatment on this subject).
Motivated by contemporary practical applications that often use short packets (e.g., smart
metering and traffic safety), there is considerable interest in investigating the backoff from
(secrecy) capacity incurred by coding at a finite blocklength [5]–[7]. In this paper, we study
the maximal secret communication rate R∗ (n, , δ) for a given blocklength n, error probability ,
and information leakage δ, over wiretap channels. An exact characterization of this fundamental
quantity is computationally impossible for most wiretap channels of interest; instead, the aim
of this paper is to develop tight upper and lower bounds as well as accurate approximations.
Throughout this paper, the information leakage to the eavesdropper is measured by the total
variation distance (between proper distributions). More specifically, we consider two secrecy
metrics:
•

Average secrecy: the total variation distance between the joint distribution PW Z of the secret
message W and the eavesdropper’s observation Z, and an ideal distribution in which W is
uniformly distributed and is independent of Z.

•

Maximum secrecy: the maximum total variation distance between PZ|W =m and PZ , maximized over all messages m in the message set.

As we shall see in Section II, the latter is equivalent to distinguishing security and semantic
security [8], [9], which are two secrecy metrics widely accepted in the cryptography literature.
Prior work: Hayashi [10] established general achievability bounds using the channel resolvability technique [11] (a.k.a. soft-covering [12]) and studied the secrecy exponent (i.e., the
exponential decreasing rate of the information leakage) for a fixed communication rate. Later,
he improved the secrecy exponent by leveraging the privacy amplification technique [13]. For
the setting of fixed  and δ and n → ∞, Yassaee et al. [14] derived an achievability bound on
the second-order coding rate [6] (also known as dispersion [5]) by using the output statistics of
random binning, which improves an earlier result by Tan [15]. Achievability bounds for wiretap
channels with other secrecy metrics can be found in [16]–[19]. On the converse side, Tyagi and
Watanabe proposed a one-shot converse bound for the problem of secret key agreement [20],
June 14, 2017

DRAFT

3

which exploits binary hypothesis testing. Building upon the technique in [20], Hayashi et al. [21]
established a converse bound for wiretap channels, which leads to the strong converse for the
degraded case. This result strengthens a previous strong converse established by Tan and Bloch
using the information spectrum method [22].
Contributions: In this paper, we develop new achievability and converse bounds on the
maximal secrecy rate R∗ (n, , δ) for general wiretap channels. Our achievability bounds are based
on two new privacy amplification results, which yield secrecy codes that satisfy, respectively,
the average and maximum secrecy constraints. These bounds are expressed in terms of the Eγ
metric [23], and establish a nice connection between two popular tools used in the achievability
proofs of information-theoretic security—privacy amplification and channel resolvability. Our
converse bound is motivated by the secret-key-agreement converse in [20] and the meta-converse
in [5]. It relates the error probability and the information leakage of a secrecy code to the error
probability of a binary hypothesis testing, and relies on a test that is tailored to the wiretap
channel. Both our achievability and converse bounds are uniformly tighter than the best existing
bounds (to the best of our knowledge).
By analyzing the behavior of our bounds in the regime of fixed  and δ and n → ∞, we
obtain upper and lower bounds on the second-order coding rate of discrete-memoryless wiretap
channels (DM-WTCs) and Gaussian wiretap channels. More specifically, we show that
r
r
r
V1 −1
V2 −1
V3 −1
Q () −
Q (δ) / R∗ (n, , δ) / CS −
Q ( + δ)
CS −
n
n
n

(1)

where CS is the secrecy capacity, and V1 , V2 , and V3 are constants that depend on the stochastic
variations of the legitimate and the eavesdropper’s channel. This result holds under both the
average secrecy and the maximum secrecy constraint. Furthermore, the achievable second-order
rate in (1) improves on the ones derived in [14] and [15].
Bridging the gap between the upper and lower bounds in (1) for general wiretap channels seems
very difficult. This can be done, however, for the class of semi-deterministic wiretap channels, in
which the channel between the transmitter and the legitimate receiver is deterministic, while that
between the transmitter and the eavesdropper is a discrete memoryless channel (DMC). Indeed,
for semi-deterministic wiretap channels both the achievability and the converse bounds in (1)

June 14, 2017

DRAFT

4

can be tightened, which yields the following asymptotic expansion for R∗ (n, , δ):
r




VS −1
δ
log n
∗
R (n, , δ) = CS −
Q
+O
n
1−
n

(2)

for every  and δ such that  + δ < 1. Here, VS is the conditional variance of an appropriate
information density term. The key idea behind the proof of (2) is to understand the optimal
tradeoff between reliability and secrecy. While it is possible to trade reliability for secrecy for
a general wiretap channel, the deterministic nature of the semi-deterministic wiretap channel
makes it also possible to trade secrecy for reliability (through additional privacy amplification).
Notation: The cardinality of a finite set A is denoted by |A|, and the uniform distribution
over A is designated as Qunif
A . For an input distribution PX and a random transformation PY |X ,
we let PY |X ◦ PX denote the marginal distribution of PX PY |X on Y . If PX = Qunif
for some
C
finite set C ⊂ X , then we write PY |C , PY |X ◦ Qunif
C . We shall consider the following “metrics”
between two probability measures P and Q on a sigma-algebra F of subsets of the set A:
•

`p distance,1 p ∈ {1, 2}
!1/p
X

|P (x) − Q(x)|p

(3)

d(P, Q) , sup |P (E) − Q(E)|

(4)

1
= kP − Qk1
2

(5)

kP − Qkp ,

x∈A
•

Total variation distance
E∈F

•

Eγ metric [23]





dP
dP
Eγ (P, Q) , P
≥ γ − γQ
≥γ
dQ
dQ

= sup P [E] − γQ[E]

(6)
(7)

E∈F

with the understanding dP /dQ = +∞ in the singular set if P is not absolutely continuous
with respect to Q
•

Neyman-Pearson β function
Z
βα (P, Q) , min

1

PT | X (1 | x)Q(dx)

(8)

For notational convenience, we write summation over A. However, our bounds hold for arbitrary probability spaces, unless

otherwise specified.
June 14, 2017

DRAFT

5

where the minimum is over all random transformations PT | X : A 7→ {0, 1} satisfying
Z
PT | X (1 | x)P (dx) ≥ α.
(9)
II. D EFINITIONS AND P RELIMINARIES
We consider the wiretap channel (WTC) model (X , PY Z | X , Y × Z) with transmitter X,
legitimate receiver Y and eavesdropper Z introduced by Wyner [1]. The transmitter wishes
to communicate a message W ∈ M , {1, ..., M } to the receiver while keeping it secret from
the eavesdropper. We first introduce the secrecy metrics used in this paper.
A. Secrecy Metrics
A secrecy metric measures the statistical independence between the message W and the
eavesdropper’s observation Z. In this paper, we consider two secrecy metrics:
•

Average total variation secrecy:
S(W |Z) , d(PW Z , Qunif
M PZ ).

(10)

Following [24, Eq. 7] and [25, p. 400], we shall also refer to S(W |Z) as the security index
of W against Z.
•

Maximum total variation secrecy:
Smax (W |Z) , max d(PZ|W =m , QZ )
m∈M

(11)

where QZ , PZ|W ◦ Qunif
M .
To the best of our knowledge, the maximum total variation secrecy has not been used in the
literature. However, as we shall show in Theorem 1 below, it is equivalent to distinguishing
security and to semantic security [8], [9], which are secrecy metrics widely accepted in the
cryptography literature. Formally, the distinguishing security metric is defined as
DS(W |Z) ,

max d(PZ|W =m0 , PZ|W =m1 ).

m0 ,m1 ∈M

(12)

In words, DS(W |Z) measures the (maximum) distinguishability of two messages m0 and m1 .
And the semantic security metric is defined as


SS(W |Z) , sup P[f (W ) = g(Z)] − sup P[S = f (W )] .
PW ,f,g

June 14, 2017

(13)

S

DRAFT

6

Here, the outer supremum is over all probability distributions PW of the message W , and
(possibly randomized) functions f : M → A and g : Z → A, where the cardinality of
the common co-domain of f and g is unrestricted. The inner supremum is over all random
simulators S (i.e., random variables) supported on A that is independent of f (W ). The first
probability term measures the probability of success of the eavesdropper who tries to guess a
function f of the message W upon observing Z. The second probability term is the probability
of success of the eavesdropper before observing Z.
Theorem 1: For every transition probability distribution PZ|W : M → Z, we have
SS(W |Z) ≤ Smax (W |Z) ≤ DS(W |Z) ≤ 2SS(W |Z) ≤ 2Smax (W |Z).

(14)

Proof: The following relation between distinguishing security and semantic security was
established in [8]:
SS(W |Z) ≤ DS(W |Z) ≤ 2SS(W |Z).

(15)

To conclude (14), it remains to show that
Smax (W |Z) ≤ DS(W |Z)

(16)

SS(W |Z) ≤ Smax (W |Z).

(17)

and that

The inequality (16) can be established as follows:
DS(W |Z) =

max d(PZ|W =m0 , PZ|W =m1 )

m0 ,m1 ∈M

1 X
d(PZ|W =m0 , PZ|W =m )
m0 ∈M M
m∈M

(18)

≥ max

(19)

≥ max d(PZ|W =m0 , PZ|W ◦ Qunif
M )

(20)

= Smax (W |Z).

(21)

m0 ∈M

Here, (20) follows because from Jensen’s inequality and because the total variation distance
d(P, Q) is convex in Q.

June 14, 2017

DRAFT

7

To prove (17), we observe that (recall that QZ , PZ|W ◦ Qunif
M )


SS(W |Z) ≤ sup PW Z [f (W ) = g(Z)] − (PW QZ )[g(Z) = f (W )]

(22)

PW ,f,g

≤ sup d(PW Z , PW QZ )

(23)

PW

= sup d(PZ|W =m , QZ )

(24)

m∈M

= Smax (W |Z).

(25)

Here, (22) follows because under PW QZ , the random variables g(Z) and f (W ) are independent; (23) follows from the definition (4); and (24) follows because the mapping PW 7→
d(PW Z , PW QZ ) is linear.
B. Secrecy Codes
We next introduce the notion of secrecy codes for a wiretap channel. An (M, , δ)avg secrecy
code for the wiretap channel PY Z|X consists of
•

a message W which is distributed on the message set M = {1, . . . , M },

•

a randomized encoder that generates a codeword X(m), m ∈ M, according to a conditional
probability distribution PX | W =m , and

•

a decoder g : Y → M that assigns an estimate Ŵ to each received signal Y ∈ Y.

The encoder and decoder satisfy the average error probability constraint
P[g(Y ) 6= W ] ≤ 

(26)

and the average total variation secrecy constraint
S(W |Z) ≤ δ.

(27)

Remark 1: Note that in the definition of average secrecy code above, we do not require the
message W to be uniformly distributed over M. However, the codes used in our achievability
bounds satisfy this additional constraint. Our converse bounds hold regardless of whether the
message is uniformly distributed or not.
An (M, , δ)max secrecy code is defined similarly except that (26) is replaced by the maximum
error probability constraint
max PY |W =m [g(Y ) 6= m] ≤ 

m∈M
June 14, 2017

(28)
DRAFT

8

and that (27) is replaced by the maximum total variation secrecy constraint
Smax (W |Z) ≤ δ.

(29)

An (M, , δ)avg secrecy code for the channel PY n Z n | X n will be called an (n, M, , δ)avg secrecy
code. Furthermore, the maximal secrecy rate (average probability of error and average secrecy)
is defined as
∗
Ravg
(n, , δ)



log M
: ∃ (n, M, , δ)avg secrecy code .
, max
n

(30)

∗
(n, , δ)
The maximal secrecy rate (maximum probability of error and maximum secrecy) Rmax

can be defined analogously. By definition, we have
∗
∗
Rmax
(n, , δ) ≤ Ravg
(n, , δ).

(31)

III. B OUNDS ON THE S ECRECY R ATE
A. Privacy Amplification
Our achievability bounds rely on the privacy amplification technique. Privacy amplification is
a method of distilling secret information from a random source that is only partially secret [26].
More specifically, let Alice and Bob be given a random variable X ∈ X , such as a random key,
which is correlated with an eavesdropper Eve’s observation Z. Alice and Bob wish to publicly
choose a (hash) function g : X → K with |K| < |X | such that g(X) is almost independent of
Eve’s observation Z, and that the resulting random variable g(X) is approximately uniformly
distributed over K. In this section, we establish two privacy amplification results that will be
used to prove achievability bounds for wiretap channels.
Our first result refines the existing privacy amplification results in the literature.
Lemma 2: Let X , K be finite sets, and Z be an arbitrary set. Let PXZ be a probability
distribution on X × Z. Then,
1) For every γ > 0 and every probability distribution QZ supported on Z, there exists a
function g : X → K such that
S(g(X)|Z) ≤

Eγ (PXZ , Qunif
X QZ )

1
+
2

r


γ 
E exp − ı(X; Z) − log γ
L

(32)

where L , |X |/|K|,
ı(x; z) , log
June 14, 2017

dPXZ
(x, z)
d(Qunif
X QZ )

(33)
DRAFT

9

and the expectation in (32) is taken with respect to (X, Z) ∼ PXZ .
2) If in addition L ∈ N and PX = Qunif
X , then there exists a function g(·) that satisfies (32)
and that g(X) is uniformly distributed over K.
Proof: The proof is based on random hashing. Similar to a random coding argument, the
idea is to show that the average secrecy index of a properly chosen random hash function G is
upper-bounded by (32). See Appendix I for the proof.
Remark 2: The bound [27, Cor. 5.6.1] can be obtained from (32) by upper-bounding the
expectation term on the right-hand side (RHS) of (32) by 1 and by using [28, Lem. 19]. This
implies that [27, Cor. 5.6.1] is weaker than Lemma 2. Similarly, the bounds in [13, Th. 1] and [29,
Th. 6] can also be obtained by weakening (32), and are therefore weaker than Lemma 2.
Remark 3: The bound (32) can be slightly improved if PXZ admits additional (symmetry)
structures; see Theorem 18 for the case in which PZ|X is the channel law of a binary symmetric
channel.
Note that, the security index S(g(X)|Z) measures the average total variation distance between
PZ|g−1 (K) and PZ for the random variable K = g(X). The next result shows that there exists a
hash function g such that the maximum total variation secrecy Smax (g(X)|PZ ) is very close to the
average. Its proof relies on Hoeffding’s reduction argument for sample without replacement [30]
and on McDiarmid’s inequality (also known as bounded difference inequality) [31].
Lemma 3: Let X and K be finite sets satisfying L , |X |/|K| ∈ N, and let Z be an arbitrary
be the uniform distribution over X , and let PZ = PZ|X ◦ PX . Let G be
set. Let PX = Qunif
X
the set of all functions g : X → K that satisfy |g −1 (k)| = L, ∀k ∈ K, and let G be uniformly
distributed over G. Then, we have


2
P max d(PZ|G−1 (k) , PZ ) ≥ r + µ ≤ |K|e−2Lr
k∈K

(34)

where


µ , E d(PZ|A , PZ )

(35)

with A = {X̄1 , . . . , X̄L } being a random codebook whose codewords are i.i.d. and PX -distributed.
Consequently, there exists a function g ∈ G such that
r
max d(PZ|g−1 (k) , PZ ) ≤ µ +
k∈K

June 14, 2017

log(|K| + 1)
.
2L

(36)

DRAFT

10

Proof: See Appendix II.
Remark 4: In the applications of Lemma 3, |K| and L are usually taken to be exponential
2

in the dimension n. In such cases, |K|e−2Lr vanishes double-exponentially fast in n. Such a
double-exponential convergence was first observed by Ahlswede and Csiszár in the analysis of
random bits extractors [32] (see also [25, p. 404]), and more recently in the setting of channel
resolvability/soft-covering [33], [34].
Interestingly, Lemma 3 connects privacy amplification to channel resolvability [11]. Indeed,
given a probability distribution PX on X and a random transformation PZ|X : X → Z, the
channel resolvability problem aims to find a set A ⊂ X with cardinality |A| ≤ L that minimizes
the (total variation) distance between PZ|A and the target PZ , PZ|X ◦ PX . A good way to
find A is through random coding. Namely, we generate each element (i.e., codeword) in A
independently and identically according to PX . It turns out that the average total variation distance


E d(PZ|A , PZ ) for the random codebook A is a tight upper bound on minA:|A|≤L d(PZ|A , PZ ).


The next result shows that E d(PZ | A , PZ ) admits an upper bound that is of the same form
as (32), which indicate that channel resolvability and privacy amplification are based on the
same probabilistic principle.
Lemma 4: Let X be a finite set, and let Z be an arbitrary set. Let PXZ be a probability
distribution supported on X × Z such that PX (x) > 0 for every x ∈ X . Let A , {X1 , . . . , XL }
be a random codebook whose codewords are independently and identically generated according
to PX . For every γ > 0, every probability distribution QZ supported on Z, we have
r
i


1 γ h
unif
e Z) − log γ|)
E exp(−|ı(X;
E d(PZ|A , PZ ) ≤ Eγ (PXZ , QX QZ ) +
2 L

(37)

where ı(·; ·) is defined in (33), and the expectation on the right-hand side of (37) is taken with
e Z) ∼ Qunif PZ|X .
respect to (X,
X

Proof: See Appendix III.
In this paper, we will only use privacy amplification to prove achievability bounds for the
wiretap channel. For completeness, though, we present a converse result for privacy amplification
below, which shows that the achievability bounds in Lemmas 2–4 are tight up to some nuisance
terms.
Lemma 5: Let X , Z, K, and PXZ be as defined in Lemma 2. Then, every function g : X → K

June 14, 2017

DRAFT

11

satisfies
S(g(X)|Z) ≥ EL (PXZ , Qunif
X QZ ).

(38)

Proof: See Appendix IV.
As a corollary of Lemma 5, we obtain the following converse bound for channel resolvability.
Corollary 6: For every finite set C = {x1 , ..., xL } ⊂ X , every PZ|X : X → Z, and every QZ ,
we have
unif
d(PZ | C , QZ ) ≥ EL (Qunif
C PZ | X , QC QZ ).

(39)

Proof: The proof follows by using Lemma 5 with X = C, K = {1}, PX = Qunif
C , and
g(·) ≡ 1.
B. Achievability Bound: Average Secrecy and Average Probability of Error
The privacy amplification lemmas developed in Section III-A allow us to convert an arbitrary
(nonsecret) channel code for the legitimate channel PY |X into a secrecy code with a guaranteed
secrecy performance. By combining the random coding union (RCU) bound [5, Th. 16] and the
dependence testing (DT) bound [5, Th. 17, Eq. (79)] for channel coding with Lemma 2, we
obtain the following achievability bound for the wiretap channel.
Theorem 7: Let PX be a probability distribution supported on A ⊂ X . For every L ∈ N, every
γ > 0, and every QZ , there exists an (M, , δ)avg code with a uniformly distributed message for
the wiretap channel (X , PY Z | X , Y × Z) that satisfies
r


1 γ
EPZ|X=x exp − ı(x; Z) − log γ
δ ≤ sup Eγ (PZ|X=x , QZ ) + sup
L
x∈A
x∈A 2

(40)

and that
n
 M L − 1 o
 ≤ min RCU (M L), DT
.
2

(41)

Here, ı(·; ·) is defined in (33),


RCU (a) , E min{1, (a − 1)P[i(X̄; Y ) ≥ i(X; Y ) | X, Y ]}
where i(x; y) , log

dPY |X (y|x)
,
dPY (y)

PXY X̄ (x, y, x̄) = PX (x)PY |X (y|x)PX (x̄), and
DT (a) , 1 − Ea (PXY , PX PY ).

June 14, 2017

(42)

(43)

DRAFT

12

Proof: By the RCU bound [5, Th. 16] and the DT bound [5, Th. 17 and Eq. (79)], there
exists a code C = {x1 , . . . , xLM } whose error probability over the legitimate channel PY |X
satisfies (41). Next, we construct a secrecy code for the wiretap channel PY Z|X from this code
using Lemma 2.
Let X ∼ Qunif
C . Then, by Lemma 2, there exists a function g : C → M such that g(X) is
uniformly distributed over M, and that for every γ > 0 and every QZ
unif
S(g(X)|Z) ≤ Eγ (Qunif
C PZ|X , QC QZ )
r


1 γ
+
EQunif
exp
−|ı(X;
Z)
−
log
γ|
2 L C PZ|X
≤ sup Eγ (PZ|X=x , QZ )
x∈A
r


1 γ
+ sup
EPZ|X=x exp − ı(x; Z) − log γ .
L
x∈A 2

(44)

(45)

Here, the last step follows because the map PX 7→ Eγ (PXZ , PX QZ ) is linear and because C ⊂ A.
Consider now a secrecy code with message W = g(X) and with a random encoder PX|W =m =
Qunif
g −1 (m) . In words, for each message m ∈ M, the encoder PW |X picks a codeword from the
set g −1 (m) uniformly at random. The decoder first decodes the codeword X̂ and then outputs
Ŵ = g(X̂). By construction, the message W of the code is uniformly distributed, and the
average error probability is upper-bounded by (41), i.e.,
n
 M L − 1 o
.
P[W 6= Ŵ ] ≤ P[X 6= X̂] ≤ min RCU (M L), DT
2

(46)

Furthermore, we have
S(W |Z) = S(g(X)|Z).

(47)

From (45) and (47), we conclude that the resulting code also satisfies the secrecy condition (40).
Hence, it is an (M, , δ)avg secrecy code.
C. Achievability Bounds: Maximum Secrecy and Maximum Probability of Error
By a standard expurgation argument applied to the RCU bound [5, Th. 16], we observe that
for the legitimate channel PY |X , there exists a code with M L codewords whose maximum error
probability is upper-bounded by (see [5, Eq. (220)])
RCU,max (M L) , inf τ −1
τ ∈(0,1)

June 14, 2017

RCU ((1 − τ )M L)
.
τ

(48)
DRAFT

13

Combining Lemma 3 and Lemma 4 with the achievability bounds in [5, Th. 21] and (48) for
maximum error probability constrained channel codes, we obtain the following result.
Theorem 8: Let PX be a probability distribution supported on A ⊂ X . For every L ∈ N,
every γ > 0, and every QZ , there exists an (M, , δ)max secrecy code for the wiretap channel
(X , PY Z | X , Y × Z) that satisfies
r

log(M + 1)
δ ≤ sup Eγ (PZ|X=x , QZ ) +
2L
x∈A
r


1 γ
EPZ|X=x exp − ı(x; Z) − log γ
+ sup
L
x∈A 2

(49)

and that

 ≤ min{DT,max M L − 1 , RCU,max (M L)}.
Here, ı(·; ·) is defined in (33), and
n
o
DT,max (a) , inf P[i(X; Y ) ≤ log γ] + a sup P[i(x; Y ) ≥ log γ]
γ≥0

with i(x; y) , log

dPY |X (y|x)
dPY (y)

(50)

(51)

x∈A

and PXY (x, y) = PX (x)PY |X (y|x).

In the proof of Theorem 8, we apply the privacy amplification lemma (Lemma 3) to a maximum
error probability constrained code C for the legitimate channel. Since each codeword of C has
a maximum error probability upper-bounded by  over PY |X , the maximum error probability
of the resulting secrecy code is also upper-bounded by . The remaining part of the proof is
analogous to the proof of Theorem 7 and is omitted.
An alternative bound can be obtained by using the privacy amplification technique on an average error probability constrained code for the legitimate channel, and by using the concentration
of measure technique employed in the proof of Lemma 3.
Theorem 9: Let PX be a probability distribution supported on A ⊂ X . For every L ∈ N, every
γ > 0, and every QZ , there exists an (M, , δ)max code for the wiretap channel (X , PY Z | X , Y ×Z)
that satisfies
r

log(2M + 1)
δ ≤ sup Eγ (PZ|X=x , QZ ) +
2L
x∈A
r


1 γ
+ sup
EPZ|X=x exp − ı(x; Z) − log γ
L
x∈A 2

June 14, 2017

(52)

DRAFT

14

and that
r

 M L − 1 
log(2M + 1)
 ≤ min RCU (M L), DT
+
.
2
2L

(53)

Here, ı(·; ·), RCU (·), and DT are defined in (33), (42), and (43), respectively.
Proof: As shown in the proof of Theorem 7, there exists a code C = {x1 , . . . , xLM } whose
average error probability 0 on the channel PY |X satisfies (41). Next, we construct a secrecy
code for the wiretap channel PY Z|X from this code C using privacy amplification.
Let X ∼ PX = Qunif
C , and let PZ = PZ|X ◦PX . Let G be the set of all functions g : C → M that
satisfy |g −1 (m)| = L for every m ∈ M, and let G be uniformly distributed over G. Furthermore,
let Pe (x), x ∈ C, be the error probability of the codeword x over the legitimate channel PY |X .
By definition, we have
EX∼Qunif
[Pe (X)] = 0 .
C

(54)

The key step of the proof is to establish the following bound:
h
i
2
P max d(PZ|G−1 (m) , PZ ) ≥ r + µ ∪ max EX∼Qunif
[P
(X)]
≥
r
+

≤ 2M e−2Lr
(55)
e
0
−1
G
(m)
m∈M
m∈M
q
log(2M +1)
where µ is defined in (35), and r is an arbitrary positive constant. Setting r =
2L
in (55), we see that the RHS of (55) is strictly less than 1. This in turn implies that there exists
a hash function g : C → M such that
r
max d(PZ|g−1 (m) , PZ ) ≤

m∈M

log(2M + 1)
+µ
2L

(56)

and
r
max EX∼Qunif
−1

m∈M

g

(m)

[Pe (X)] ≤
r
≤

log(2M + 1)
+ 0
2L

(57)


 M L − 1 
log(2M + 1)
+ min RCU (M L), DT
. (58)
2L
2

Furthermore, the RHS of (56) is upper-bounded by the expression on the RHS of (52) according
to Lemma 4.
Consider now a secrecy code with message W = g(X) and with a random encoder PX|W =m =
Qunif
g −1 (m) . The decoder first decodes the codeword X̂ and then set Ŵ = g(X̂). By construction,
we have
d(PZ|W =m , PZ ) = d(PZ|g−1 (m) , PZ ),
June 14, 2017

∀m ∈ M.

(59)
DRAFT

15

Furthermore, the error probability of a message m ∈ M is equal to
Pe (m) = EX∼PX|W =m [Pe (X)] = EX∼Qunif
−1
g

(m)

[Pe (X)] .

(60)

Therefore, the maximum error probability and maximum information leakage of the resulting
secrecy code satisfy the bounds specified in (53) and (52).
To conclude the proof, it remains to show (55). By the union bound, we have
h
i
P max d(PZ|G−1 (m) , PZ ) ≥ r + µ ∪ max EX∼Qunif
[P
(X)]
≥
r
+

e
0
G−1 (m)
m∈M
m∈M
h
i
≤ P max d(PZ|G−1 (m) , PZ ) ≥ r + µ + M P[EX∼Qunif
[Pe (X)] ≥ r + 0 ]
−1
m∈M

G

2

≤ M e−2Lr + M P[EX∼Qunif
[Pe (X)] ≥ r + 0 ].
−1
G

(61)

(1)

(62)

(1)

Here, (62) follows from Lemma 3. Note that
L

1X
Pe (Xi )
EX∼Qunif
[P
(X)]
=
e
G−1 (1)
L i=1
d

(63)
d

where X1 , ..., XL are random samples without replacement from C, and = denotes equality in
distribution. Since 0 ≤ Pe (Xi ) ≤ 1 almost surely, and since E[Pe (Xi )] = 0 , we can invoke
Hoeffding’s inequality for samples without replacement [30] and obtain
h
i
−2Lr2
P EX∼Qunif
[P
(X)]
≥
r
+

.
e
0 ≤ e
−1
G

(64)

(1)

Substituting (64) into (62) we conclude (55).
D. Achievability: Trading Reliability for Secrecy
Our next result shows that one can trade reliability for secrecy for a wiretap channel.
Theorem 10: Consider a wiretap channel PY Z|X . Every (M, 0 , δ0 )max (resp. (M, 0 , δ0 )avg )
secrecy code for PY Z|X can be converted to an (M, , δ)max (resp. (M, , δ)avg ) secrecy code
with  > 0 and δ = δ0 (1 − )/(1 − 0 ). Consequently,


δ0 (1 − )
∗
∗
Rmax (n, 0 , δ0 ) ≤ Rmax n, ,
1 − 0


δ0 (1 − )
∗
∗
Ravg (n, 0 , δ0 ) ≤ Ravg n, ,
.
1 − 0

June 14, 2017

(65)
(66)

DRAFT

16
C
Proof: Choose an arbitrary (M, 0 , δ0 )max secrecy code C. Let PX|W
be the stochastic encoder

of this code, and let PXC be the empirical output distribution of the encoder for a uniformly
distributed message. We construct a new secrecy code Ce from C by using the following encoder
C
C
PX|W
= (1 − p)PX|W
+ pPXC
e

(67)

where
p=

 − 0
.
1 − 0

(68)

The decoder of Ce is chosen to be the same as that of C. We shall prove that the maximum error
probability of the new code Ce is upper-bounded by , and its maximum information leakage
is upper-bounded by δ. Consequently, Ce is an (M, , δ)max code, from which the claim of the
theorem follows.
e
Let Dm be the decoding region corresponding to the message m. The error probability Pe,m (C)
of Ce for the message m can be evaluated as follows:

e = 1 − PY n |X n ◦ PXCen |W =m [Dm ]
Pe,m (C)

(69)


= 1 − (1 − p)0 − p PY n |X n ◦ PXC n [Dm ]
{z
}
|

(70)

≤

(71)

≥0

where (70) follows from (67) and because C has error probability 0 .
e
Let PZC and PZC be the empirical output distributions of C and Ce over the channel PZ|X ,
respectively. For every message m ∈ M, we have


Ce
Ce
d PZ|W =m , PZ


Ce
C
= d PZ|W
,
P
=m
Z

(72)

 C
C
C
= d PZ|X ◦ (1 − p)PX|W
+
pP
=m
X , PZ

(73)

C
C
= (1 − p)d(PZ|W
=m , PZ )

(74)

≤

δ0 (1 − )
= δ.
1 − 0

(75)

Here, (72) follows because PZC = PZC , (73) follows from (67), and (75) follows because, by
e

C
C
definition, d(PZ|W
=m , PZ ) ≤ δ0 for every m ∈ M. The result for average probability of error

and average secrecy constraint can be proved similarly.
June 14, 2017

DRAFT

17

E. Converse Bounds
We first present a general converse bound.
Theorem 11: Every (M, , δ)avg secrecy code satisfies
M ≤ sup

inf

inf

PX|W 0<τ <1−δ QY

βδ+τ (PW Z , Qunif
M PZ )
τ β1− (PW Y , Qunif
M QY )

(76)

where PW denotes the distribution of the message (not necessarily uniformly distributed), and PY
and PZ are the marginal distributions of the Markov chains W → X → Y and W → X → Z,
respectively.
Proof: By the meta-converse bound for non-equiprobable messages [35], every (M, , δ)avg
secrecy code satisfies
M ≤ inf
QY

1
.
β1− (PW Y , Qunif
X QY )

(77)

Furthermore, by the secrecy constraint,
unif
δ ≥ d(PW Z , Qunif
M PZ ) ≥ δ + τ − βδ+τ (PW Z , QM PZ )

(78)

where the last step follows from (4). Rearranging the terms in (78), we conclude that
βδ+τ (PW Z , Qunif
M PZ ) ≥ τ.

(79)

Combining (79) with (77), and optimizing the resulting bound over all stochastic encoders PX|W ,
we obtain (76).
The bound (76) is in general difficult to compute or analyze. Next, we prove a converse
bound, which is motivated by the converse in [20] for secret key generation. This bound is both
numerically and analytically tractable.
Theorem 12: Let QY |Z : Y → Z be an arbitrary random transformation. Then, every (M, , δ)avg
secrecy code for the wiretap channel (X , PY Z|X , Y × Z) satisfies
M≤

τ +δ
τ ∈(0,1−−δ) τ β1−−δ−τ (PXY Z , PXZ QY |Z )
inf

(80)

where PXY Z denotes the distribution induced by the code.
Remark 5: Using the result in [20], Hayashi, Tyagi, and Watanabe recently derived the following converse bound [21] (for the case of uniformly distributed message):
M≤

June 14, 2017

inf

1

τ ∈(0,1−−δ) τ 2 β1−−δ−τ (PXY Z , PXZ QY |Z )

.

(81)

DRAFT

18

P : W → X → (Y, Z)
&
Ŵ
QY |Z
Q : W → X → Z −→ Y → Ŵ

Fig. 1.

A graphical illustration of the probability distributions PW XY Z Ŵ and QW XY Z Ŵ .

Our bound is stronger than (81) since (τ + δ)/τ < 1/τ 2 .
Proof: Fix an arbitrary (M, , δ)avg secrecy code and let PW XY Z Ŵ , PW PX|W PY Z|X PŴ |Y
be the joint distribution induced by the code. And let QW XY Z Ŵ , PW PX|W PZ|X QY |Z PŴ |Y
(see Fig. 1 for a graphical illustration). As in the meta-converse bound [5, Th. 26] and in [20],
the idea is to relate the error probability and secrecy index of the secrecy code to the binary
hypothesis testing between PW Ŵ Z and QW Ŵ Z through a suboptimal test. The following test
PT |W Ŵ Z : M2 × Z 7→ {0, 1} plays an prominent role in our proof:

T (m, m̂, z) = 1 m = m̂, PW |Z (m|z) ≤ 1/(ηM )

(82)

where η ∈ (0, 1).
One the one hand, we have
QW Ŵ Z [T = 1]
X
=
QZ Ŵ (z, m̂)PW |Z (m|z)
m,m̂,z


· 1 m = m̂, PW |Z (m|z) ≤ 1/(M η)

1 X
QZ Ŵ (z, m)1 PW |Z (m|z) ≤ 1/(M η)
≤
M η m,z
≤

1
.
Mη

(83)
(84)
(85)

One the other hand, by (26), the probability PW Ŵ Z [T = 1] can be lower-bounded as
PW Ŵ Z [T = 1] ≥ 1 −  − PW Z [PW |Z (W |Z) ≥ 1/(M η)].

June 14, 2017

(86)

DRAFT

19

To further lower-bound the RHS of (86), we observe that
δ ≥ d(PW Z , Qunif
M PZ )

(87)

≥ PW Z [PW |Z (W |Z) ≥ 1/(M η)]
− Qunif
M PZ [PW |Z (W |Z) ≥ 1/(M η)]

(88)

and that
PW Z [PW |Z (W |Z) ≥ 1/(M η)]
1
≥ Qunif
PZ [PW |Z (W |Z) ≥ 1/(M η)].
η M

(89)

Here, (89) follows from a standard change of measure argument. Combining (88) and (89), we
obtain
PW Z [PW |Z (W |Z) ≥ 1/(M η)] ≤

δ
.
1−η

(90)

1
.
Mη

(91)

Substituting (90) into (86), and using (85), we conclude that
β1−−δ/(1−η) (PW Ŵ Z , QW Ŵ Z ) ≤

The final bound (80) follows by rearranging the terms in (91), by the change of variable τ =
δ/(1 − η) − δ, and by observing that
βα (PW Ŵ Z , QW Ŵ Z ) ≥ βα (PXY Z , PXZ QY |Z )

(92)

which follows from the data-processing inequality for βα .
IV. B OUNDS ON THE S ECOND -O RDER S ECRECY R ATE
A. DM-WTC
We shall use the following notation:
I(PX , PY |X ) , I(X; Y )
X

X
2 PY |X (y|x)
2
V (PX , PY |X ) ,
PX (x)
PY |X (y|x) log
− D(PY |X=x kPY )
PY (y)
x∈X
y∈Y
˜ X , PY Z|X ) , I(X; Y |Z)
I(P
X
X
Ṽ (PX , PY Z|X ) ,
PX (x)
PZY |X (y, z|x) log2
x∈X

June 14, 2017

PY Z|X (y, z|x)
PZ|X (z|x)PY |Z (y|z)
y,z

2
− D(PY Z|X=x kPY |Z PZ|X=x ) .

(93)
(94)
(95)

(96)
DRAFT

20

The secrecy capacity of a general DM-WTC is given by [2]


CS = max I(V ; Y ) − I(V ; Z)
PV X

(97)

where the maximization is over all probability distributions PV X for which V → X → Y Z
form a Markov chain. For simplicity, we shall assume that there exists a unique probability
∗
distribution PV∗ X = PV∗ PX|V
that achieves the maximum in (97). Note that if the eavesdropper’s

channel PZ|X is less capable than the legitimate channel PY |X , then the secrecy capacity reduces
to [4, Sec. 3.5.1]


CS = max I(X; Y ) − I(X; Z) .
PX

(98)

The auxiliary random variable V makes the evaluation of (97) difficult. An upper bound
on (97) is given by [21]
CS ≤ CSu , max I(X; Y |Z).
PX

(99)

For simplicity, we shall also assume that there exists a unique probability distribution P̃X∗ that
attains the maximum in (99), and that Ṽ (P̃X∗ , PY Z|X ) > 0. Note that, the bound (99) is tight
(i.e., CS = CSu ) if the wiretap channel is physically degraded [4, Def. 3.8].
Theorem 13: Consider a DM-WTC PY Z|X . If  + δ < 1, then we have
r
r


V
V2 −1
log n
1
−1
∗
Q () −
Q (δ) + O
Rmax (n, , δ) ≥ CS −
n
n
n
and

(100)

r



log n
Vc −1
Q ( + δ) + O
.
≤
−
n
n
R∞
2
Here, Q−1 (·) is the inverse of the Gaussian Q-function Q(x) , x √12π e−t /2 dt and
∗
Ravg
(n, , δ)

CSu

(101)

∗
V1 , V (PV∗ , PY |X ◦ PX|V
)

(102)

∗
)
V2 , V (PV∗ , PZ|X ◦ PX|V

(103)

Vc , Ṽ (P̃X∗ , PY Z|X ).

(104)

If  + δ > 1, then
r
∗
(n, , δ)
Rmax

≥ Clegit −





Vlegit −1  + δ − 1
log n
+O
Q
n
δ
n

(105)

where Clegit and Vlegit denote the capacity and channel dispersion of the legitimate channel.

June 14, 2017

DRAFT

21

Proof: See Appendix V.
A few remarks are in order.
•

As implied by (105), the strong converse does not hold if δ +  > 1.

•

It is possible to slightly improve the achievability bound (100) by using Theorem 10; see
Section V-C.

•

∗
By Theorem 1, every achievability bound on Rmax
(n, , δ) can be converted to achievability

bounds on semantic security and distinguishing security. In particular, the bound (100)
implies the semantic security capacity of wiretap channels recently studied in [36] and [37].
The achievability bound (100) is tighter than the achievable second-order coding rate in [14]
obtained by using output statistics of random binning, and is tighter than the one in [15] obtained
via channel resolvability. The latter two approaches use a random coding argument and bound the
average error probability and average information leakage averaged over all random codebooks
separately. They then invoke Markov’s inequality to show the existence of a code that satisfies
simultaneously the reliability and secrecy constraint. The use of Markov’s inequality introduces
a penalty to the second-order coding rate, which corresponds to the gap between (100) and [14,
Eq. (23)]. In contrast, our result shows that every code that satisfies the reliability constraint can
be modified to satisfy the secrecy constraint, thereby avoiding the use of Markov’s inequality.
However, this does not mean that channel resolvability based approaches have worse asymptotic
performance than the privacy amplification based approach adopted in this paper. Indeed, the
same bound (100) can be proved by using the stronger channel resolvability result developed
in [34], which shows that the random coding procedure in channel resolvability succeeds with
a probability double-exponentially close to unity.
B. Gaussian wiretap channel
Consider the Gaussian wiretap channel
Yi = Xi + U i ,

Zi = Xi + Ũi ,

i = 1, . . . , n

(106)

where {Ui } are independent and identically distributed (i.i.d.) N (0, N1 ) random variables, and
{Ũi } are i.i.d. N (0, N2 ) random variables. Without loss of generality, we assume that N2 > N1
(otherwise the secrecy capacity is zero). Furthermore, we assume that each codeword xn satisfies

June 14, 2017

DRAFT

22

the power constraint
kxn k2 ≤ nP.
Theorem 14: For the Gaussian wiretap channel (106), we have
r
r


V
V2 −1
log n
1 −1
∗
Rmax (n, , δ) ≥ CS −
Q () −
Q (δ) + O
n
n
n
and

r
∗
(n, , δ)
Ravg

≤ CS −



Vc −1
log n
Q ( + δ) + O
n
n

(107)

(108)

(109)

where




1
1
P
P
CS = log 1 +
− log 1 +
2
N1
2
N2
log2 e P 2 + 2P Ni
, i ∈ {1, 2}
2 (P + Ni )2


P N1
1
1
Vc = V1 + V2 −
+
log2 e.
P + N1 N2 P + N2
Vi =

(110)
(111)
(112)

Proof: See Appendix VI.
C. Numerical Results and Discussions
In this section, we compare the bounds proposed in this paper with existing bounds in [21]
and [29], and with the approximations provided in Theorem 14 for a Gaussian wiretap channel
(with the O(·) terms omitted). The results are shown in Fig. 2. The bound labeled by “Hayashi
et al.” is [21, Th. 6] (see also (81)), and the one labeled by “Watanabe-Hayashi” is obtained
by combining the privacy amplification bound [29, Cor. 2] with Shannon’s channel coding
achievability bound [38] (which is the tightest achievability bound for Gaussian channels [5,
Sec. III.J-4]).2
Several observations are in order. First of all, both our achievability and converse bounds are
uniformly better than the ones in [21] and [29]. Secondly, the expansions (108) and (109) provide
reasonable approximations for the bounds in Theorems 9 and 12. Last but not least, there is a
nontrivial gap between our achievability and converse bounds (which can also be inferred from
the approximations (108) and (109)).
2

The numerical routine used to compute Shannon’s channel coding achievability bound is available at https://github.com/yp-

mit/spectre
June 14, 2017

DRAFT

23

CS = 0.5

Secrecy rate, bits/(ch. use)

0.5

0.4
Hayashi et al.
Converse (Theorem 12)
Approximation (109)

0.3

Achievability (Theorem 9)

0.2

Approximation (108)
0.1

0

Watanabe-Hayashi

0

300

600

900

1200

1500

1800

2100

2400

2700

3000

Blocklength, n

Fig. 2.

Secrecy rate for the Gaussian wiretap channel with P/N1 = 3 dB, P/N2 = −3 dB,  = δ = 10−3 .

To understand the causes of the gap between the upper and lower bound in Theorems 13
and 14, we note that our achievability schemes come with two limitations.
•

In our achievability schemes, the secrecy and reliability constraints are treated separately. In
particular, the transmitter adds redundancy to the transmitted signals to guarantee reliability,
and uses (separated) randomness to derive secrecy. The amount of redundancy depends
on the quality of the legitimate channel and the error probability constraint, whereas the
amount of randomness depends on the quality of the eavesdropper’s channel and the secrecy
constraint. While separation-based schemes are secrecy-capacity-achieving, it is not clear
whether they are second-order optimal.3

•

Assuming a separation-based structure, our achievability schemes further require the legitimate decoder to decode both the message and the randomness inserted by the transmitter.

It would be interesting to construct schemes that relax these requirements, and to see if such
schemes achieve better second-order secrecy rate.
3

A similar phenomenon occurs in the joint source-channel coding setting. Recently, it was shown that separate source-channel

coding is first-order but not second-order optimal [39].

June 14, 2017

DRAFT

24

V. S EMI -D ETERMINISTIC W IRETAP C HANNEL
In this section, we focus on a special class of wiretap channels known as semi-deterministic
DM-WTCs. More specifically, in a semi-deterministic DM-WTC PY Z|X : X → Y ×Z, the output
of the legitimate channel is a deterministic function of the input, i.e., PY |X (y|x) = 1{y = f (x)}
for some deterministic function f , and the eavesdropper’s channel is a (noisy) DMC. Without
loss of generality, we assume that the function f is surjective. Note that, in general, a semideterministic wiretap channel is not (stochastically) degraded.
The secrecy capacity of a semi-deterministic wiretap channel is given by [40]
CS = max H(Y |Z).

(113)

PX

This can be achieved by setting V = Y in the secrecy capacity formula (97). An alternative
expression for the secrecy capacity is given by
CS = max I(X; Y |Z).

(114)

PX

The equivalence between (113) and (114) follows because, for a semi-deterministic DM-WTC,
I(X; Y |Z) − H(Y |Z) = H(Y |X, Z) = 0.

(115)

Throughout this section, we shall assume that there exists a unique input distribution PX∗
∗
denote the marginal and conditional
that achieves the secrecy capacity (113). Let PY∗ and PZ|Y

distributions of PX∗ PY Z|X . For semi-deterministic wiretap channels, the bounds in Theorem 13
match for the special case  = 0, which yields4
r


VS −1
log n
∗
Ri (n, 0, δ) = CS −
Q (δ) + O
,
n
n

i ∈ {avg, max}

(116)

where
∗
VS , V (PY∗ , PZ|Y
).

(117)

The main result of this section is a complete characterization of the second-order secrecy rate
of the semi-deterministic DM-WTC for arbitrary  and δ.
4

Rigorously speaking, the bounds in Theorem 13 do not directly imply (116), since there it is required that  > 0 and that

the dispersion of the legitimate channel is nonzero. Nevertheless, it is not difficult to prove (116) using the same arguments as
in the proof of Theorem 13. We omit these mechanical details here.

June 14, 2017

DRAFT

25

A. Nonasymptotic Converse Bound
We first give a nonasymptotic converse bound for semi-deterministic wiretap channels.
Theorem 15: Every (M, , δ)avg secrecy code for the semi-deterministic DM-WTC PY Z|X
satisfies
min

min E

PX ∈P(X )QZ ∈P(Z)

|Y|
M (1−)

(PY Z|X ◦ PX , Qunif
Y QZ ) ≤

δ
1−

(118)

where Qunif
is the uniform distribution over Y.
Y
Remark 6: By the triangular inequality for Eγ (·, ·) [23, Eq. (21)], the function (PX , QZ ) 7→
Eγ (PY Z|X ◦ PX , Qunif
Y QZ ) is continuous in the topology of total variation. Moreover, since the
probability simplexes P(X ) and P(Z) are compact, a minimizer for Eγ (PY Z|X ◦ PX , Qunif
Y QZ )
exists.
Proof: Choose an arbitrary (M, , δ)avg secrecy code. Without loss of generality, we can
assume that the decoder at the legitimate receiver is deterministic, and that the error probability
constraint (26) holds with equality. Denote by Dm , m ∈ M, the decoding region for message m.
By definition, we have
P[Y ∈ DW ] =

M X
X

PW Y (m, y)1{y ∈ Dm }

(119)

m=1 y∈Y

= 1 − .

(120)

Next, we derive a lower bound on the security index S(W |Z) = d(PW Z , Qunif
W PZ ) by using a
suboptimal set E in (4). Let
PXc (x)

M
1 X
,
PW X (m, x)1{f (x) ∈ Dm }
1 −  m=1

(121)

and let PYc Z , PY Z|X ◦ PXc . By (120), both PXc and PYc Z are probability distributions. Consider
the following subset of M × Z
n
E , (m, z) : max

y∈Dm

June 14, 2017

o
PYc Z
(y; z) ≥ γ
Qunif
Y PZ

(122)

DRAFT

26

where the threshold γ will be specified later. On the one hand, we have
M
1 XX
PW Y (m, y)
PW Z [E] =
M m=1 y∈Y


PYc Z
· PZ|Y =y,W =m max unif (ỹ; Z) ≥ γ
ỹ∈Dm Q
Y PZ

≥

M X
X

(123)

PW Y (m, y)

m=1 y∈Dm


PYc Z
· PZ|Y =y,W =m unif (y; Z) ≥ γ
Q Y PZ


PYc Z
c
= (1 − )PY Z unif (Y ; Z) ≥ γ .
Q Y PZ


(124)
(125)

On the other hand, we have
(Qunif
M PZ )[E]



M
1 X
PYc Z
PZ max unif (y; Z) ≥ γ
=
y∈Dm Q
M m=1
Y PZ


M
1 X X
PYc Z
≤
PZ unif (y; Z) ≥ γ
M m=1 y∈D
QY PZ
m


|Y| unif  PYc Z
(Y ; Z) ≥ γ
=
QY PZ
M
Qunif
Y PZ

(126)

(127)
(128)

where (127) follows from the union bound. Setting γ = |Y|/(M (1 − )), and using (6), (125),
and (128), we finally obtain
δ ≥ d(PW Z , PW PZ )

(129)

≥ PW Z [E] − (Qunif
M PZ )[E]


PYc Z
c
≥ (1 − )PY Z log unif (Y ; Z) ≥ γ
QY PZ


|Y| unif  PYc Z
QY PZ
−
(Y ; Z) ≥ γ
M
Qunif
Y PZ
= (1 − )E

|Y|
M (1−)

(PYc Z , Qunif
Y PZ )

≥ (1 − ) min min E
PX

QZ

|Y|
M (1−)

(PY Z|X ◦ PX , Qunif
Y QZ ).

(130)

(131)
(132)
(133)

This concludes the proof.

June 14, 2017

DRAFT

27

B. Trading Secrecy for Reliability
In Section III-D, we have shown that one can trade reliability for secrecy for an arbitrary
wiretap channel. While the converse is not true in general, the following result shows that one
can trade secrecy for reliability for a semi-deterministic wiretap channel.
Theorem 16: Every (M, , δ)avg secrecy code for a semi-deterministic wiretap channel can be
converted to an (M 0 , 0, δ 0 )avg secrecy code for the same channel, where M 0 ∈ N and
s
1
M0
δ
+
.
δ0 ,
1 −  2 M (1 − )

(134)

Consequently, we have
∗
Ravg
(n, , δ)

≤

∗
Ravg




δ
1
n, 0,
+ τn − log(4τn2 (1 − ))
1−
n

(135)

where τn is an arbitrary positive constant that satisfies 4M (1 − )τn2 ∈ N.
Proof: Choose an arbitrary (M, , δ)avg secrecy code. Note that, by (132) in the proof of
Theorem 15, this code must satisfy
min E
QZ

|Y|
M (1−)

(PY Z|X ◦ PXc , Qunif
Y QZ ) ≤

δ
1−

(136)

c
where PXc was defined in (121). Let PYc and PX|Y
be the marginal (conditional) distributions
c
of PXc PY |X . Then, using PX|Y
as a prefix to the channel PY Z|X , we obtain an auxiliary semi-

deterministic wiretap channel PYc Z|Ŷ : Y → Y × Z:
c
PX|Y

PY Z|X

Ŷ −→ X −→ (Y, Z).

(137)

By construction, every secrecy code for the auxiliary channel PYc Z|Ŷ is also a secrecy code for
the original channel PY Z|X . Furthermore, PYc |Ŷ (y|ŷ) = 1{y = ŷ}.
Next, we construct a secrecy code for the auxiliary channel PYc Z|Ŷ as follows. Let M 0 ∈ N be
a positive integer. Using Lemma 2 on the joint distribution PY Z with γ = |Y|/(M (1 − )), and
upper-bounding the expectation term on the RHS of (32) by 1, we conclude that there exists a
mapping g0 : Y → {1, . . . , M 0 } satisfying
1
S(g0 (Y )|Z) ≤ min E |Y| (PYc Z , Qunif
Y QZ ) +
QZ
M (1−)
2
s
δ
1
M0
≤
+
= δ0.
1 −  2 M (1 − )
June 14, 2017

s

M0
M (1 − )

(138)

(139)

DRAFT

28

Let now the message W be distributed according to g(Ŷ ) where Ŷ ∼ PYc . For each message
m ∈ {1, . . . , M 0 }, the stochastic encoder PŶ |W =m is chosen to be the conditional distribution
of Ŷ ∼ PYc given Ŷ ∈ g −1 (m). Such a code has zero error over the legitimate channel since
the sets {g −1 (m)} are disjoint. Furthermore, PŶc Z (y, z) = PYc Z (y, z) for every (y, z) ∈ Y × Z.
Hence, we have
S(W |Z) = S(g0 (Ŷ )|Z) = S(g0 (Y )|Z) ≤ δ 0 .

(140)

This concludes the first part of the theorem. The bound (135) follows by choosing M =
∗
exp(nRavg
(n, , δ)) and by setting M 0 = 4M (1 − )τn2 .

C. Second-Order Secrecy Rate
Using Theorems 10 and 16 in (116), we obtain the following complete characterization of the
second-order secrecy rate for semi-deterministic wiretap channels.
Theorem 17: Consider a semi-deterministic DM-WTC PY Z|X . Assume that
1) There exists a unique input distribution PX∗ that achieves the secrecy capacity (113).
∗
) > 0.
2) V (PY∗ , PZ|Y

If δ +  < 1, then
r
Ri∗ (n, , δ)

= CS −





VS −1
δ
log n
Q
+O
,
n
1−
n

∀i ∈ {avg, max}

(141)

where VS is given in (117). If δ +  ≥ 1, then
∗
∗
Ravg
(n, , δ) ≥ Rmax
(n, , δ) ≥ |Y|.

Proof: We first consider the case  + δ < 1. On the achievability side, we have


δ
∗
∗
Rmax (n, , δ) ≥ Rmax n, 0,
1−
r




VS −1
δ
log n
= CS −
Q
+O
n
1−
n

(142)

(143)
(144)

where (143) follows Theorem 10, and (144) follows from (116). On the converse side, we have


δ
1
1
n
∗
∗
Ravg (n, , δ) ≤ R n, 0
+√
+ log
(145)
1−
n
4(1 − )
n
r




VS −1
δ
log n
= CS −
Q
+O
(146)
n
1−
n
June 14, 2017

DRAFT

29

√
where (145) follows from Theorem 16 with τn = 1/ n, and (146) follows from (116) and by
∗
∗
Taylor-expanding Q−1 (x) around x = δ/(1−). Since Rmax
(n, , δ) ≤ Ravg
(n, , δ) by definition,

together (144) and (146) imply the expansion (141) for the case  + δ < 1.
By (65), if  + δ ≥ 1, then
∗
∗
(n, 0, 1).
(n, , δ) ≥ Rmax
Rmax

(147)

Since the legitimate channel is noiseless and since the function f defining the channel PY |X is
surjective, we can prefix an arbitrary random transformation PŶ n |X n to the channel PY n |X n , and
transmit |Y|n codewords in the channel Ŷ n → X n → Y n without making an error. Furthermore,
since d(P, Q) ≤ 1 for every pair of probability distributions P and Q, the secrecy constraint is
∗
(n, 0, 1) ≥ |Y|.
trivially satisfied without any additional processing. This implies that Rmax

A few remarks are in order.
1) An alternative expression for VS is
VS = Var[log PY∗ |Z (f (X)|Z)|X].

(148)

2) It follows from (141) that neither the achievability nor the converse bound in Theorem 13
is tight for the semi-deterministic wiretap channels (unless  = 0).
3) The expansion (141) is still valid if one of the average constraints in the definition of
∗
(n, , δ) is replaced with its maximum counterpart.
Ravg

4) The expansion (141) is still valid if the channel between the transmitter and the eavesdropper is discrete input and continuous output.
5) Interestingly, the second-order rate in Theorem 17 does not match the second-order rate
of secret key generation (although the first-order rates in the two settings do match each
other). As shown in Hayashi et al. [41], the latter rate (for independent and identically
distributed sources X n , Y n , and Z n ) is
r


V −1
log n
Q ( + δ) + O
I(X; Y |Z) −
n
n

(149)

where  denotes the probability that the keys generated by the legitimate users do not
coincide, δ represents a secrecy constraint similar to (27), and V is a constant depending
on the stochastic variation of the sources. This comparison reveals a subtle difference in the
tradeoffs between reliability and secrecy in the two settings. Another interesting observation

June 14, 2017

DRAFT

30

CS = 0.5

Secrecy rate, bits/(ch. use)

Converse (80)
0.4

0.3

Achievability (150)

0.2

Approximation (155)
Converse (154)
0.1

0

0

200

400

600

800

1000

1200

1400

1600

1800

2000

Blocklength, n

∗
Fig. 3. Maximum secrecy rate Ravg
(n, , δ) for a binary symmetric wiretap channel with crossover probability p = 0.11; here,

δ =  = 10−3 .

is that, if the wiretap channel is augmented by an authenticated public discussion channel,
then the second-order secrecy rate is equal to the one in (149) [18].
6) In our conference paper [42], we proved the achievability part of (141) using a stronger
soft-covering lemma for constant-composition codes similar to the one developed in [34].
Our proof here is based on the (strong) privacy amplification result in Lemma 3, and is
much simpler.
D. The Binary Symmetric Wiretap Channel
Consider a specific wiretap channel, where X = Y = Z = F2 , PY |X = 1{Y = X}, and PZ|X
is a binary symmetric channel with crossover probability p. We shall refer to this channel as the
binary symmetric wiretap channel (BS-WTC). Without loss of generality, we assume p < 1/2.
Theorem 18: For the BS-WTC with crossover probability p, there exists an (n, 2k , , δ)avg
secrecy code with uniformly distributed message such that
r


1
γ
δ
≤ min gn (γ) + gn (γ) + n−k hn (γ)
1−
2 γ
2

June 14, 2017

(150)

DRAFT

31

where k ∈ N,


n h
gn (γ) , 1 − E exp − B log


p
γ i+o
+ n log(1 − p) − log n
1−p
2

(151)

with [x]+ , max{x, 0} and B following the binomial distribution with parameters n and p, and
 n

p
γ o
hn (γ) , E exp − B log
+ n log(1 − p) − log n
.
(152)
1−p
2
Furthermore, there exists an (n, 2k , , δ)max secrecy code such that
r

 r
δ
1
γ
log(2k + 1)
≤ min gn (γ) + gn (γ) + n−k hn (γ) +
.
1−
2 γ
2
2n−k+1
Conversely, every (n, M, , δ)avg secrecy code satisfies


δ
2n
≤
.
gn
M (1 − )
1−

(153)

(154)

Proof: The achievability bounds (150) and (153) follow from strengthened versions of
Lemma 2 and Lemma 4. The converse bound (154) follows by showing that the optimal PX and
QZ in (118) are both uniform distributions over Fn2 . Their proofs are given in Appendix VII.
For the BS-WTC, the reminder term in (141) can be improved to O(1/n).
Theorem 19: For the BS-WTC with crossover probability p, and for every  ≥ 0 and δ > 0
that satisfy  + δ < 1, we have
r
Ri∗ (n, , δ)

= Hb (p) −



 
VBSC −1
δ
1
Q
+O
,
n
1−
n

i ∈ {max, avg}

(155)

where Hb (·) denotes the binary entropy function, and
VBSC , p(1 − p) log2 ((1 − p)/p).

(156)

Proof: See Appendix VIII.
Remark 7: The strengthened achievability bounds (150) and (153) are crucial in establishing
√
the correct order O(1/ n) in the achievability bound. For comparison, the bound (32) in
Lemma 2 yields − 12 log n for the third-order term.
In Fig. 3, we plot the bounds (150) and (154) for p = 0.11, and δ =  = 10−3 . For comparison,
we also plot the general converse bound in (80) and the approximation (155). From this figure,
we see that the new converse bound in (154) is uniformly tighter than (80). Numerically, the
maximum secrecy rate at blocklength 400 is between 0.34 and 0.36 bits/ch. use.

June 14, 2017

DRAFT

32

VI. C ONCLUSION
In this paper, we have established nonasymptotic achievability and converse bounds on the
maximum secret communication rate R∗ (n, , δ) for a given blocklength n, error probability ,
and information leakage δ over wiretap channels. These bounds are shown to be tighter than
the best previously known bounds. The proofs of our achievability bounds are based on new
privacy amplification results that may be useful for other security problems. We have also
established connections between privacy amplification and channel resolvability, and have used
this connection to derive tighter bounds for channel resolvability.
By analyzing the nonasymptotic bounds, we have further derived upper and lower bounds on
the second-order secrecy rate for general discrete memoryless wiretap channels and for Gaussian
wiretap channels. For the special case of semi-deterministic wiretap channels, we have established
the exact second-order secrecy rate, which characterizes the optimal tradeoff between reliability
and secrecy in the finite-blocklength regime. For general (non-deterministic) wiretap channels,
the problem of establishing the second-order secrecy rate is still open.
A PPENDIX I
P ROOF OF L EMMA 2
The proof is based on random hashing (also known as universal hashing) and the left-over
hash lemma [26], [27].
A. Proof of Part 1
Let G be a random function from X to K that satisfies the following collision probability
bound
P[G(x1 ) = G(x2 )] ≤

1
,
|K|

∀x1 6= x2 .

(157)

In other words, G is a universal2 hash function [43], [26].5 The average secrecy index of G can
be computed as follows:


EG [S(G(X)|Z)] = EG d(PG(X)Z , Qunif
K PZ )
5

(158)

One example of a universal2 hash function is the one that is uniformly distributed over the set of all functions from X to

K (see [26, Sec. IV]).

June 14, 2017

DRAFT

33





1
1
PXZ (x, z) −
PZ (z) 
EG 
2 k∈K,z∈Z
|K|
x∈G−1 (k)


X
X
|K|
1
=
EG 
PZ (z)  .
PXZ (x, z) −
2 z∈Z
|K|
−1

=

X

X

x∈G

(159)

(160)

(1)

Here, (160) follows from the symmetry of the set G.
Observe that the expectation on the RHS of (160) is the first absolute central moment of the
random variable
X

A(z) ,

PXZ (x, z).

(161)

PZ (z)
.
|K|

(162)

x∈G−1 (1)

Indeed, it is not difficult to verify that
E[A(z)] =

An exact computation of the first absolute moment of A(z) is highly complex, and is not
suitable for numerical evaluation or analytical analysis. To get a simpler bound on (160), we
shall split A(z) into two parts A1 (z) and A2 (z) that satisfy Var[A1 (z)]  Var[A2 (z)], and bound
E[|A(z) − E[A(z)]|] using the triangle inequality as in [27] and [13]. Doing so, we obtain
E[|A(z) − E[A(z)] |] = E[|A1 + A2 − E[A1 (z) + A2 (z)] |]
≤ 2E[|A1 (z)|] + E[|A2 (z) − E[A2 (z)] |]
p
≤ 2E[|A1 (z)|] + Var[A2 (z)].
Without loss of generality, we can assume that A1 (z) and A2 (z) take the form
X
RXZ (x, z), A1 (z) = A(z) − A2 (z)
A2 (z) =

(163)
(164)
(165)

(166)

x∈G−1 (z)

where RXZ is an arbitrary nonnegative measure (not necessary a probability measure). Substituting (166) into (165), then (165) into (160), we obtain


X
X
E[S(G(X)|Z)] ≤ |K|
E
(PXZ − RXZ )(x, z) 
k,z

x∈G−1 (1)

h
Xs
1
+ |K|
Var
2
z
≤ kPXZ − RXZ k1 +

June 14, 2017

X

i
RXZ (x, z)

(167)

x∈G−1 (1)

1X
RZ (z)
2 z

q


2
|K|E kRG(X)|Z=z − Qunif
(168)
K k2
DRAFT

34

where RZ is the projection of RXZ on Z. Here, in (168), we have used the triangular inequality
on the first term on the RHS of (167) and applied the following identity


X
RZ (z)
E
.
R(x, z) =
|K|
−1
x∈G

(169)

(z)

The second term on the RHS of (168) can be further bounded as
q 
X

2
RZ (z) E kRG(X)|Z=z − Qunif
K k2
z

s
Xp
=
QZ (z)
z

s
≤
s


RZ2 (z) 
2
E kRG(X)|Z=z − Qunif
K k2
QZ (z)

X R2 (z) 

Z
2
E kRG(X)|Z=z − Qunif
K k2
QZ (z)
z
X R2 (z) X
Z

≤

z

QZ (z)

2
(x|z)
RX|Z

(170)

(171)

(172)

x

p

exp(−H2 (RXZ |QZ )).
(173)
P
Here, H2 (RXZ |QZ ) , − log x,z RXZ (x, z)2 /QZ (z) denotes the conditional Rényi entropy
=

of order 2 relative to QZ , (171) follows from the Cauchy-Schwarz inequality and because
P
z QZ (z) = 1, and (172) follows from the left-over hash lemma by Bennett et al. [26]. Note
that the steps in (160)–(173) are essentially the ones employed in [27, Sec. 5.5] and [13]. The
reason that we present them here (in a different form) are two-fold. First, as will be shown in
the proof of Lemma 4, the same bounding techniques as above can be used to analyze channel
resolvability. Second, as will be shown in Appendix VII-A, if the distribution PXZ admits further
structures (e.g., symmetry), then the bounds (164) and (165) can be tightened.
We next minimize the RHS of (173) over RXZ . This is unlike the existing privacy amplification
results (for example, those discussed previously), in which one selects a convenient RXZ and
then proves an upper bound on (173). Consider the following optimization problem
X RXZ (x, z)2
min
RXZ :kPXZ −RXZ k1 ≤˜

QZ (z)
x,z

(174)

∗
∗
where ˜ ∈ [0, 2]. It is not difficult to see that the optimal RXZ
must satisfy RXZ
(x, z) ≤

PXZ (x, z) for every pair (x, z), i.e., (174) is equivalent to
X RXZ (x, z)2
min
.
RXZ :kPXZ −RXZ k1 ≤˜
, RXZ ≤PXZ
QZ (z)
x,z
June 14, 2017

(175)

DRAFT

35
∗
Indeed, suppose on the contrary that there exists (x0 , z0 ) which satisfy RXZ
(x0 , z0 ) > PXZ (x0 , z0 ).

Since the objective function in (174) is monotonically increasing with RXZ (x0 , z0 ), we can
∗
further decrease it by setting RXZ
(x0 , z0 ) = PXZ (x0 , z0 ) without violating the constraint in (174).
∗
But this contradicts the assumption that RX,Z
is the optimizer of (174). Therefore, we must have
∗
RX,Z
≤ PXZ . Observe that the problem (175) is a convex optimization problem. Hence, by

the Karush-Kuhn-Tucker (KKT) condition [44, Sec. 5.5.3], the optimizer of (175) must take the
form
∗
RXZ
(x, z) ,



PXZ (x, z)

ı(x; z) ≤ log γ


γQunif (x)QZ (z)

otherwise

X

(176)

∗
where γ is chosen such that kPXZ − RXZ
k1 = ˜.

Using (176) in the first term on the RHS of (168), we obtain
∗
kPXZ − RXZ
k1 = Eγ (PXZ , Qunif
X QZ ).

(177)

The bound (173) can be evaluated as follows:
∗
exp(−H2 (RXZ
|QZ ))
X R∗ (x, z)2
XZ
=
QZ (z)
x,z
1 X
PXZ (x, z) exp(ı(x; z))1{ı(x; z) ≤ log γ}
=
|X | x,z

γ 2 unif
Q QZ [ı(X; Z) ≥ log γ]
|X | X
γ
EP [exp(−|ı(X; Z) − log γ|)]
=
|X | XZ
γ
−
EP [exp(−|ı(X; Z) − log γ|)1{ı(X; Z) ≥ log γ}]
|X | XZ
γ 2 unif
+
Q QZ [ı(X; Z) ≥ log γ]
|X | X

γ 
=
E exp −|ı(X; Z) − log γ| .
|X |
+

(178)

(179)

(180)
(181)

Substituting (181) into (173), and then (177) and (173) into (168), we conclude that for every
γ > 0,
1
EG [S(G(X)|Z)] ≤ Eγ (PXZ , Qunif
X QZ ) +
2

s


γ|K| 
E exp −|ı(X; Z) − log γ| .
|X |

(182)

Finally, the inequality (182) implies that there exists a g ∈ G for which (32) holds.
June 14, 2017

DRAFT

36

B. Proof of Part 2
Let G be the set of all functions g from X to K that satisfies g −1 (k) = L for every k ∈ K.
Let G be uniformly distributed over the set G. It is not difficult to check that such a random
function satisfies the collision probability bound (157), i.e., it is a universal2 function. As such, it
unif
satisfies the bound (182). Furthermore, for every g ∈ G we have g(X) ∼ Qunif
K , where X ∼ QX .

This concludes the proof of Part 2.
A PPENDIX II
P ROOF OF L EMMA 3
By the union bound and the Chernoff bound, we have




P max d(PZ|G−1 (k) , PZ ) ≥ r + µ ≤ |K|P d(PZ|G−1 (1) , PZ ) ≥ r + µ
k∈K
h
i
≤ |K|e−t(r+µ) E etd(PZ|G−1 (1) ,PZ )

(183)
(184)

where t is an arbitrary positive constant. Observe that the random variable d(PZ|G−1 (1) , PZ ) can
be rewritten as
d(PZ|G−1 (1) , PZ ) =
d

=

1 X −1
|L
2 z∈Z

X

PZ|X (z|x) − PZ (z)|

(185)

1 X −1 X
|L
PZ|X (z|Xi ) − PZ (z)|
2 z∈Z
i=1,...,L

(186)

x∈G−1 (1)

, h(X1L )

(187)

d

where = denotes equality in distribution, and X1 , ..., XL are distributed according to the joint
distribution
PX1L (xL1 )

=

Qunif
X (x1 )

L
Y
i=2

Qunif
(x ).
X \{xL−1 } i

(188)

1

In other words, X1L are random samples without replacement from X .
h
i
L
We proceed to upper-bound E eth(X1 ) . The key idea is to replace the dependent random
variables X1L with the i.i.d. samples X̄1L defined in the lemma. More specifically, we shall prove
that
h
i
h
i
th(X1L )
th(X̄1L )
E e
≤E e
.

June 14, 2017

(189)

DRAFT

37

This is done by using the elegant reduction argument of Hoeffding [30]. Let
L

f (xL1 ) , eth(x1 ) .

(190)

Since f (·) is symmetric in its arguments, there exists a symmetric function f¯ : X L → R that
satisfies




E f¯(X1L ) = E f (X̄1L )

(191)

as observed in [30, Sec. 5]. Such a function takes the form
X
pk,r1 ,...,rk ,i1 ,...,ik f (xi1 , ..., xi1 , ...., xik , ..., xik )
f¯(xL1 ) =
| {z }
| {z }
r1

(192)

rk

where the sum is taken over the integers k, r1 , ..., rk , i1 , ..., ik such that k ∈ {1, ..., L}, r1 + · · · +
rk = n, {i1 , . . . , ik } ⊂ {1, ..., L} are distinct, and
X
pk,r1 ,...,rk ,i1 ,...,ik = 1.

(193)

To prove (189), it suffices to show that
f¯(xL1 ) ≥ f (xL1 ),

∀xL1 ∈ X L .

(194)

Consider the chain of inequalities


X
f¯(xL1 ) ≥ exp t log(e)
pk,r1 ,...,rk ,i1 ,...,ik h(xi1 , ..., xi1 , ...., xik , ..., xik )
| {z }
| {z }
r1

(195)

rk

 t log(e) X X

= exp
pk,r1 ,...,rk ,i1 ,...,ik gz (xi1 , ..., xi1 , ...., xik , ..., xik )
| {z }
| {z }
2
z∈Z

(196)

 t log(e) X X

≥ exp
pk,r1 ,...,rk ,i1 ,...,ik gz (xi1 , ..., xi1 , ...., xik , ..., xik )
| {z }
| {z }
2
z∈Z

(197)

r1

r1

=

f (xL1 )

rk

rk

(198)

where the functions {gz (·)} are defined as
L

gz (xL1 )

1X
,
PZ|X (z|xi ) − PZ (z).
L i=1

(199)

Here, (195) follows from Jensen’s inequality and the convexity of x 7→ etx ; (196) follows
from (187); (197) follows from the triangle inequality; and finally, (198) follows because
X
pk,r1 ,...,rk ,i1 ,...,ik gz (xi1 , ..., xi1 , ...., xik , ..., xik ) = gz (xL1 ).
(200)
| {z }
| {z }
r1

June 14, 2017

rk

DRAFT

38

This concludes (194), and, hence (189).
Now, observe that the partial discrete derivatives of h(·) are uniformly bounded, i.e.,
L
i−1 0
L
sup |h(xi−1
1 , y, xi+1 ) − h(x1 , y , xi+1 )| ≤

y,y 0 ∈X

1
,
L

i = 1, ..., L.

(201)

This allows us to conclude that (see the proof of McDiarmid’s inequality [31] and [45, Eq. (2.2.25)],


and recall that µ = E h(X̄1L ) )
h
i
L
2
E et(h(X̄1 )−µ) ≤ et /(8L) .
(202)
Using (202) and (189) in (184), we conclude that


2
P max d(PZ|G−1 (k) , PZ ) ≥ r + µ ≤ |K|e−tr+t /(8L) .

(203)

k∈K

The choice t = 4rL minimizes the RHS of (203) and yields (34).
p
Finally, using r = log(1 + |K|)/(2L) on the RHS of (34), we obtain


|K|
<1
P max d(PZ|G−1 (k) , PZ ) ≥ r + µ ≤
k∈K
|K| + 1

(204)

which implies (36).
A PPENDIX III
P ROOF OF L EMMA 4
Consider
EA



 1X
d(PZ|A , PZ ) =
EX1 ,...,XL
2 z∈Z

"

1 X
PZ|X (z|Xi ) − PZ (z)
L i=1,...,L

As in the proof of Lemma 2, we shall split the random variable
1 X
PZ|X (z|Xi )
B(z) ,
L i=1,...,L

#
.

(205)

(206)

into two parts. Let {RZ|X=x }x∈X be a sequence of arbitrary nonnegative measures indexed by x.
Let
B2 (z) ,

June 14, 2017

1 X
RZ|X (z|Xi ),
L i=1,...,L

B1 (z) , B(z) − B2 (z).

(207)

DRAFT

39

It follows that

 1X
EA d(PZ|A , PZ ) =
E[|B(z) − B1 (z)|]
2 z∈Z
X
1 Xp
≤
E[|B1 (z)|] +
Var[B2 (z)]
2
z∈Z
z∈Z
1 X q −1
= kPXZ − RZ|X PX k1 +
L Var[RZ|X (z|X)].
2 z∈Z

(208)
(209)
(210)

Here, in (209) we have used the triangle inequality and Jensen’s inequality. The second term on
the RHS of (210) can be evaluated as follows:
Xq
Var[RZ|X (z|X)]
z∈Z

s
=

Xp

QZ (z)

z

s
≤

X
z

s
≤

X
z

1
Var[RZ|X (z|X)]
QZ (z)

(211)

1
Var[RZ|X (z|X)]
QZ (z)

(212)

i
h
1
2
(z|X) .
E RZ|X
QZ (z)

(213)

v
uX 2
RZ|X (z|x)PX (z)
u
=t
.
QZ (z)
x,z

(214)

As in the proof of Lemma 2, we shall minimize the RHS of (214) over all RZ|X that satisfy
kPXZ − RZ|X PX k1 ≤ ˜.

(215)

The minimizer takes the form
∗
RZ|X
(z|x) ,



PZ|X (z|x)

ı(x; z) ≤ log γ

γQZ (z)


|X |PX (x)

otherwise

(216)

∗
where γ is chosen such that kPXZ −RZ|X
PX k1 = ˜. Substituting (216) into (214), and then (216)

and (214) into (210), we conclude the proof of Lemma 4.

June 14, 2017

DRAFT

40

A PPENDIX IV
P ROOF OF L EMMA 5
Let ı(·; ·) be defined as in (33). Let K , g(X). By definition, for every m ∈ M and every
γ > 0, we have

S(g(X)|Z) ≥ PKZ



max ı(x̄; Z) ≥ log γ


unif
− (QK PZ ) max
ı(x̄; Z) ≥ log γ .
−1
x̄∈g −1 (K)

x̄∈g

The first term on the RHS of (217) can be bounded as


PKZ max
ı(x̄; Z) ≥ log γ
x̄∈g −1 (K)
n
o
X X
=
PXZ (x, z)1 max
ı(x̄;
z)
≥
log
γ
−1
k,z

≥

X

x̄∈g

x∈g −1 (k)

(217)

(K)

(218)

(k)

n
o
PXZ (x, z)1 ı̃(x; z) ≥ log γ

(219)

x,z

= PXZ [ı(X; Z) ≥ γ] .

(220)

The second term on the RHS of (217) can be bounded using the union bound as follows:

 X
1 X
unif
(QK PZ ) max
ı(x̄;
Z)
≥
log
γ
≤
PZ [ı(x; Z) ≥ log γ]
(221)
x̄∈g −1 (K)
|K|
−1
k∈K
x∈π

=

(k)

|X | unif
Q PZ [ı(X; Z) ≥ log γ].
|K| X

(222)

Substituting (220) and (222) into (217), setting γ = L = |X |/|K|, we obtain
S(g(X)|Z) ≥ PXZ [ı(X; Z) ≥ log L] − L · (Qunif
X PZ )[ı(X; Z) ≥ log L]
= EL (PXZ , Qunif
X PZ ).

(223)
(224)

A PPENDIX V
P ROOF OF T HEOREM 13
A. Achievability
To prove the achievability bound (100), we shall use Theorem 8 with a constant-composition
code. The reason for using constant-composition codes instead of i.i.d. codes is two-fold. First,
for a properly chosen QZ n , all codewords xn of a constant-composition code have the same
June 14, 2017

DRAFT

41

Eγ (PZ n |X n =xn , QZ n ). Secondly, constant-composition codes achieve the conditional variances V1
and V2 , whereas i.i.d. codes achieve (the slightly bigger) unconditional variances. For simplicity
of presentation, we only prove (100) for the special case in which
CS = max I(X; Y ) − I(X; Z).
PX

(225)

Using channel prefixing, we can generalize the proof in a straightforward manner to the case in
which this condition does not hold.
Before presenting the proof, we first introduce some standard notation used in the method of
types [25, Ch. 2]. We denote the simplex of probability distributions on a finite alphabet A by
P(A). The set of all n-types on A is defined as
Pn (A) , {P ∈ P : nP (a) ∈ Z+ , ∀a ∈ A}.

(226)

The subset of sequences in An with the same type P is denoted by TPn (A) or simply TPn if
the alphabet A is clear from the context. Let Pn ∈ Pn (X ) be the type that is closest in total
variation distance to the (unique) secrecy-capacity-achieving input distribution PX∗ . Furthermore,
n
let PX n = Qunif
TPn (X ) denote the uniform distribution over the type class TPn (X ), and let PY ,

PY n |X n ◦ PX n . Using the permutation symmetry of the type class TPn (X ) and of the channel
PZ n |X n , it is not difficult to check that the probability term


PY n |X n n n
(x , Y ) ≥ log γ
PY n log
PY n

(227)

takes the same value for every xn ∈ TPn (X ). As a consequence, we have by [5, Th. 22]
DT,max (a) = 1 − Ea (PX n PY n |X n , PX n PY n ).

(228)

Next, we evaluate Ea (PX n PY n |X n , PX n PY n ) for a given a > 0 as follows:
1 − Ea (PX n PY n |X n , PX n PY n )





PY n |X n n n
PY n |X n n n
= inf (PX n PY n |X n )
(X , Y ) ≤ γ1 + a(PX n PY n )
(X , Y ) > γ1
(229)
γ1 >0
PY n
PY n


√
PY n |X n n n
1
≤ (PX n PY n |X n )
(X , Y ) ≤ na + √ .
(230)
PY n
n
Here, (229) follows from (7), and (230) follows by relaxing the infimum on the RHS of (229)
√
with γ1 = na and by applying the standard change of measure technique to the second term

June 14, 2017

DRAFT

42

on the RHS of (229). Suppose that V1 = V (PX∗ , PY |X ) > 0. Proceeding as in the proof of [7,
Th. 4.2], we can further upper-bound the RHS of (230) by
√




nI(PX∗ , PY |X ) − log( na)
1
√
+O √
.
Q
n
nV1

(231)

This implies that there exists an

p
√ 
an = n−1/2 exp nI(X; Y ) − nV1 Q−1  − O(1/ n)

(232)

 ≥ 1 − Ean (PX n PY n |X n , PX n PY n ).

(233)

that satisfies

For the case V1 = 0, we have that
V (Pn , PY |X ) = O(1/n)

(234)

which follows because |Pn − PX∗ | = O(1/n) and because P 7→ V (P, PY |X ) are smooth maps
on the interior of the probability simplex on X . Proceeding step by step as in the proof of [7,
Th. 4.2], and using Chebyshev’s inequality and (234) in place of [7, Eq. (4.53)], we conclude
that (231) and (233) remain to hold if V1 = 0.
Let

γn (xn , δ) , inf γ : Eγ (PZ n |X n =xn , QZ n )
1
+
2

r

1
E[exp(−|ı(xn ; Z n ) − log γ|)] +
n

s

log(1 + an /(nγ))
≤δ
2nγ


(235)

where an is given in (232) and QZ n is set to be the product distribution (PZ|X ◦ Pn )n . Setting
γ = supxn ∈TPn γn (xn , δ), L = nγ, Mn = an /L, and using (235), (233), and Theorem 8, we
conclude that there exists an (n, Mn , , δ)max secrecy code. Therefore,
1
log Mn
n
1
log n
= log an − sup log γn (xn , δ) −
.
n
n
xn ∈TPn (X )

∗
Rmax
(n, , δ) ≥

(236)
(237)

It remains to evaluate γn (xn , δ). Using the permutation symmetry of TPn and of PZ n |X n , we see
that γn (xn , δ) takes the same value for every xn ∈ TPn . We next upper-bound Eγ (PZ n |X n =xn , QZ n ).

June 14, 2017

DRAFT

43

In the analysis below, we shall assume that V2 = V (PX∗ , PY |X ) > 0. The case V2 = 0 can be
handled similarly as in (234). Consider the following chain of (in)equalities:


PZ n |X n =xn n
(Z ) ≥ log γ
Eγ (PZ n |X n =xn , QZ n ) ≤ PZ n |X n =xn log
QZ n
#
" n
X
PZ|X=xi
(Zi ) ≥ log γ
= PZ n |X n =xn
log
(PZ|X ◦ Pn )
i=1
!


log γ − nI(Pn , PZ|X )
1
p
≤Q
+O √
n
nV (Pn , PZ|X )




log γ − nI(PX∗ , PZ|X )
1
√
=Q
+O √
.
n
nV2

(238)
(239)

(240)
(241)

Here, (240) follows from the Berry-Esseen theorem [46, Sec. XVI.5] and [5, Lemma 46],
and (241) follows because |Pn − PX∗ | = O(1/n) and because P 7→ I(P, PZ|X ) and P 7→
V (P, PZ|X ) are smooth maps on the interior of the probability simplex on X . Furthermore, we
have
E[exp(−|ı(xn ; Z n ) − log γ|)] ≤ 1

(242)

and
s

 
1
log(1 + an /(nγ))
≤O
2nγ
n

as long as γ ≥ n2 . Together (241)–(243) imply that
 
p

1
−1
∗
.
log γn (xn , δ) ≤ nI(PX , PZ|X ) + nV2 Q δ + O
n

(243)

(244)

Substituting (244) into (237) we conclude (100).
B. Converse
We next prove the converse bound (101) using (80). In order to apply (80), we need to select a
QY n | Z n . Before doing so, we remark that in the point-to-point channel coding setting, a converse
bound is usually proved by reducing a code to a constant-composition subcode (see, e.g., [5]
and [47]). The rationale behind this reduction is that removing all codewords except those of a
dominant type reduces the coding rate by at most O((log n)/n), and at the same time it does not
increase the error probability. A converse bound can be then proved by using the meta-converse
bound [5, Th. 27] on the dominant type, with the auxiliary output distribution QY n chosen to be
June 14, 2017

DRAFT

44

the output distribution induced by this type. This reduction argument, however, does not work
for the wiretap channel, because it is not clear how removing codewords will affect the secrecy
index S(W |Z). Instead, we shall choose QY n |Z n to be a mixture of conditional distributions
PY n | Z n induced by all types in Pn (X ). We now proceed with the proof.
(t)

(t)

(t)

(t)

For each type PX ∈ Pn , t = 1, . . . , |Pn |, let PY Z , PY Z|X ◦ PX and let PY |Z be the induced
conditional distribution. Furthermore, let
|Pn | n

1 X Y (t)
QY n |Z n (y | z ) =
P (yi |zi ).
|Pn | t=1 i=1 Y |Z
n

n

(245)

Using this conditional distribution in the bound (80), we obtain that, for every τ ∈ (0, 1 −  − δ)
and every γ ∈ R,
τ +δ
∗
(246)
nRavg
(n, , δ) ≤ − inf log β1−−δ−τ (PX n Y n Z n , PX n Z n QY n | Z n ) + log
PX n
τ



PX n Y n Z n
τ +δ
≤ γ − log 1 −  − δ − τ − sup PX n Y n Z n log
≥γ
+ log
PX n Z n Q Y n | Z n
τ
PX n
(247)
where the second step follows from [5, Eq. (102)]. The probability term on the RHS of (247)
can be evaluated as follows:


PX n Y n Z n
≥γ
PX n Y n Z n
PX n Z n Q Y n | Z n

≤ sup PY n Z n | X n =xn log



xn ∈X n


PY n Z n |X n =xn
≥γ .
PZ n | X n =xn QY n | Z n

(248)

For an arbitrary xn ∈ X n , let t ∈ {1, . . . , |Pn |} denote the index of the type of xn . Using (245)
and using that log |Pn | ≤ |X | log(n + 1), we obtain


PY n Z n |X n =xn
≥γ
PY n Z n | X n =xn log
PZ n | X n =xn QY n | Z n
"
#
PY n Z n |X n =xn
≤ PY n Z n | X n =xn log
≥ γ − |X | log(n + 1)
(t)
PZ n | X n =xn (PY |Z )n
" n
#
X
PY Z|X (Yi , Zi |xi )
= PY n Z n | X n =xn
log
≥ γ − |X | log(n + 1) .
(t)
PZ|X (Zi |xi )PY |Z (Yi |Zi )
i=1
Let now 

γ̃(α) , inf ξ :
sup
 t{1,...,|Pn |}, xn ∈T

"
PY n Z n | X n =xn
(t)
P
X

n
X
i=1

log

PZY |X (Yi , Zi |xi )
(t)

PZ|X (Zi |xi )PY |Z (Yi |Zi )

(249)

(250)

#
≥ξ ≥α




.


(251)

June 14, 2017

DRAFT

45

Following similar steps as in the proof of [5, Th. 48], and using that P̃X∗ is the unique maximizer
of (99), that Ṽ (P̃X∗ , PY Z|X ) > 0, and that PX 7→ I(X; Y |Z) is concave, we obtain
p
γ̃(α) = nCSu − nVc Q−1 (1 − α) + O(log n).

(252)

√
Finally, setting γ = |X | log(n + 1) + γ̃(1 −  − δ − τ ) and τ = 1/ n, and using (252), (250),
and (248) in (247), we conclude the proof of (101).
C. The  + δ > 1 Case
By (65), if  + δ > 1, then
∗
Rmax
(n, , δ)

≥

∗
Rmax




+δ−1
n,
,1 .
δ

(253)

By [5, Sec. IV.A], the maximum communication rate over the legitimate channel for a given
blocklength n and maximum error probability ( + δ − 1)/δ is lower-bounded by
r




Vlegit −1  + δ − 1
log n
Q
+O
.
Clegit −
n
δ
n

(254)

Furthermore, since d(P, Q) ≤ 1 for every pair of probability distributions P and Q, the secrecy
constraint is trivially satisfied without any additional processing. This implies (105).
A PPENDIX VI
P ROOF OF T HEOREM 14
To prove (108), we shall use Theorem 8 with PX n being the uniform distribution over the
power sphere Sn , {xn ∈ Rn : kxn k2 = nP } and with QZ n ∼ N (0, (P + N2 )In ). For such a
PX n it was shown in [48] that there exists an

n
p
√
log(1 + P/N1 ) − nV1 Q−1 ( − / n) + O(log n)
ãn = exp
2

(255)

that satisfies
√
√
RCU (ãn ) ≤ (1 − 1/ n) − / n.

(256)

√
√
Setting an = ãn / n, τ = 1 − 1/ n, and using (48), we conclude that
RCU,max (an ) ≤ τ −1 RCU (ãn ) ≤ .

June 14, 2017

(257)

DRAFT

46

Furthermore, from (255), we see that
log an =

p
n
log(1 + P/N1 ) − nV1 Q−1 () + O(log n).
2

(258)

We next evaluate (49). Due to the spherical symmetry of Sn and QZ n , we have that for every
xn ∈ Sn
Eγ (PZ n | X n =xn , QZ n ) = Eγ (PZ n | X n =x̄n , QZ n )

(259)

√
√
x̄n , [ P , . . . , P ].

(260)

where

The RHS of (259) can be evaluated
Eγ (PZ n | X n =x̄n , QZ n )


dPZ n | X n =x̄n n
≤ PZ n | X n =x̄n log
(Z ) ≥ log γ
dQZ n




log γ − n log(1 + P/N2 )
1
√
=Q
+O √
n
nV2

(261)
(262)

where the last step follows from [5, p. 2357]. The proof of (108) follows by repeating the
steps (235)–(244) with (262) used in place of (241).
To prove the converse bound (109), we assume that the channel PY n Z n |X n is physically
degraded. This assumption comes without loss of generality since the maximal coding rate
R∗ (n, , δ) depends on the channel law PY n Z n | X n only through the marginal transition probabilities PY n | X n and PZ n | X n [4, Lemma 3.4]. We shall use Theorem 12 with


P + N1 n (P + N1 )(N2 − N1 )
z ,
In
QY n | Z n = N
P + N2
P + N2

(263)

which coincides with the marginal conditional distribution PY n |Z n of PX n Y n Z n for the case
X n ∼ N (0, P In ). Observe that, by the data-processing inequality for βα (·, ·), we have
βα (PX n Y n Z n , PX n Z n QY n |Z n ) ≥ βα (PX n+1 Y n+1 Z n+1 , PX n+1 Z n+1 QY n+1 |Z n+1 ).

(264)

By (264) and [5, Lemma 39], it suffices to consider the case where PX n is supported on the
power sphere Sn . Furthermore, by the spherical symmetry of PY n Z n |X n , QY n |X n , and Sn , and
by using [5, Lemma 29], we obtain that, for every PX n supported on Sn ,
βα (PX n Y n Z n , PX n Z n QY n |Z n ) = βα (PY n Z n |X n =x̄n , PZ n |X n =x̄n QY n |Z n )
June 14, 2017

(265)
DRAFT

47

where x̄n is defined in (260).
To evaluate the asymptotic behavior of the RHS of (265) we observe that, under PY n Z n | X n =x̄n ,
dP

n n

n

n

the random variable log d(PZ n Y| X nZ=x̄|nXQY=x̄n | Z n ) (Y n , Z n ) has the same distribution as
!
√
√
n
log e X (Ui + Ūi )2 Ui2 ( P + Ui )2 ( P + Ui + Ūi )2
nCS +
−
+
−
2 i=1
N2
N1
P + N1
P + N2

(266)

where {Ūi } are i.i.d. N (0, N2 − N1 )-distributed, and {Ui } are i.i.d. N (0, N1 ) distributed. As
in [5, Sec. IV.B], a central limit theorem analysis of (266) shows that
p
− log βα (PY n Z n |X n =x̄n , PZ n |X n =x̄n QY n |Z n ) = nCS − nVc Q−1 (1 − α) + O(log n)

(267)

√
where Vc is given in (112). Setting α = 1 −  − δ − τ and τ = 1/ n, and substituting (267)
and (265) into (80), we conclude (109).
A PPENDIX VII
P ROOF OF T HEOREM 18
A. Achievability
To prove the achievability bound (150), we shall use a strengthened version of the privacy
amplification lemma (Lemma 2). Fix a positive integer k and let M , 2k . Let X = Z = Fn2 ,
let K = M = {1, ..., M }, and let PX and QZ be the uniform distributions over X and Z,
respectively. Let PZ|X denote the channel law of n uses of a BSC. It follows that PZ|X ◦PX = QZ .
Furthermore, let G be uniformly distributed over the set of functions g from X → K satisfying
|g −1 (`)| = 2n−k , for every ` ∈ K. As in the proof of Lemma 2, we can rewrite the average
security index as
S(G(X)|Z) =

|K| X
E[|A1 (z) + A2 (z) − E[A1 (z) + A2 (z)]|]
2 z

(268)

where A1 (z) and A2 (z) are defined in (166) with RXZ taking the form (176). Different from (165),
we now upper-bound the absolute value in (268) as follows:
E[|A1 (z) + A2 (z) − E[A1 (z) + A2 (z)] |]
≤ E[|A1 (z)|] + E[|A2 (z) − E[A1 (z) + A2 (z)] |]
p
≤ E[|A1 (z)|] + E[|A2 (z) − E[A1 (z) + A2 (z)] |2 ]
q
≤ E[|A1 (z)|] + E[|A1 (z)|]2 + Var[A2 (z)].
June 14, 2017

(269)
(270)
(271)
DRAFT

48

Now, by the symmetry of PZ|X , QZ , PX , and RXZ , it can be shown that E[|A1 (z)|] is independent
of z. This guarantees that
X
z∈Z

1
E[|A1 (z)|]2 =
QZ (z)

!2
X

E[|A1 (z)|]

.

(272)

z∈Z

Substituting (271) into (268), using (272), and following straightforward computations, we obtain
r


1
γ
1
gn (γ) + n−k hn (γ) .
S(G(X)|Z) ≤ min gn (γ) +
(273)
2 γ
2
2
This implies that there exists a function g : X → M such that g(X) ∼ Qunif
M and that S(g(X)|Z)
is upper-bounded by the RHS of (273). Setting W = g(X), PX|W = Qunif
g −1 (W ) , and using that
the legitimate channel is noiseless, we conclude that there exists an (n, 2k , 0, δ̃)avg secrecy code
with δ̃ upper-bounded by the RHS of (273). The claimed achievability bound (150) follows then
from (66).
Similarly, Lemma 4 can be strengthened to show that for a random codebook A with 2n−k
i.i.d. PX -distributed codewords, if PZ|X is a BSC, then
r



 1
1
γ
gn (γ) + n−k hn (γ) .
EA d(PZ|A , PZ ) ≤ min gn (γ) +
2 γ
2
2

(274)

Using this result and Lemma 3 on the BS-WTC, we conclude the bound (153).
B. Converse
The proof of the converse bound (154) follows by showing that the optimal PX and QZ
of (118) are both uniform distributions over Fn2 . For the BS-WTC with n channel uses, the
left-hand side (LHS) of (118) is equivalent to
min

min

n
PX n ∈P(Fn
2 ) QZ n ∈P(F2 )

E

|X |n
M (1−)

(PX n Z n , Qunif
QZ n ).
Fn
2

(275)

Our proof relies on the following properties of the function Eγ (PX n Z n , Qunif
QZ n ).
Fn
2
•

Translation invariance: for every PX n and every QZ n supported on Fn2 , the value of the
function Eγ (PX n Z n , Qunif
QZ n ) does not change if we translate PX n and QZ n by a fixed
Fn
2
vector v n ∈ {0, 1}n simultaneously, i.e.,

June 14, 2017

X n → X n ⊕ vn

(276)

Z n → Z n ⊕ vn.

(277)

DRAFT

49

•

Convexity: the map (PX n , QZ n ) 7→ Eγ (PX n Z n , Qunif
QZ n ) is convex for every γ > 0. This
Fn
2
follows because the Eγ divergence is an f -divergence, and every f -divergence is jointly
convex in its arguments [49].

For a given vector v n ∈ {0, 1}n and a given probability distribution X n ∼ PX n , we define
n

PXv n as the probability distribution of X n ⊕ v n , and P̄X n as the distribution of X n ⊕ V n with V n
uniformly distributed over Fn2 . It is not difficult to see that P̄X n is also a uniform distribution.
n

The probability distributions QvZ n and Q̄Z n are defined similarly. Now, by Jensen’s inequality
and the translation invariance and convexity of Eγ (·, ·), we have
Eγ (PX n PZ n |X n , Qunif
QZ n )
Fn
2
1 X
n
n
Eγ (PXv n PZ n |X n , Qunif
QvZ n )
= n
Fn
2
2 n
n

(278)

v ∈{0,1}

≥ Eγ (P̄X n PZ n |X n , Qunif
Q̄Z n ).
Fn
2

(279)

Therefore, (275) is indeed minimized by uniform distributions. Note that, the function gn (γ) is
equal to
gn (γ) = Eγ (Qunif
PZ n |X n , Qunif
Qunif
).
Fn
Fn
Fn
2
2
2

(280)

This concludes the converse bound (154).
A PPENDIX VIII
P ROOF OF T HEOREM 19
The converse part of (155) follows from (154) and the following estimate
p
log gn−1 (t) = n log 2 − nHb (p) + nVBSC Q−1(t) + O(1)

(281)

which can be distilled from [5, Sec. IV.A.1]. Here, gn−1 (t) : [0, 1] → [0, ∞) denotes the pseudoinverse of the non-increasing function gn (·)
gn−1 (t) , inf{x ∈ [0, ∞) : gn (x) ≤ t}.

(282)

To prove the achievability part of (155), we shall evaluate the upper bound in (153) with
the parameters k = bn − log2 (gn−1 (δ̃))c and γ = 2n−k for some arbitrary δ̃ ∈ (0, 1). Since
γ 7→ gn (γ) is non-increasing (because gn (γ) corresponds to the Eγ “distance” between two

June 14, 2017

DRAFT

50

probability distributions, which is non-increasing in γ; see (280)), and since γ ≥ gn−1 (δ̃), it
follows that
gn (γ) ≤ gn (gn−1 (δ̃)) ≤ δ̃.

(283)

The term hn (γ) in (153) can be rewritten as
" 
)#
 (X
n
n
X
hn (γ) = E exp −
Zi + n log(1 − p) + log 2k 1
Zi > −n log(1 − p) − log 2k
i=1

i=1

)#
 (X
X
n
n
Zi ≤ −n log(1 − p) − log 2k
(284)
+ E exp
Zi − n log(1 − p) − log 2k 1
"

i=1

i=1

where Zi , Bi log(p/(1 − p)) with {Bi } i.i.d. Bern(p) distributed. Using [5, Lemma 47] on
both terms on the RHS of (284), we obtain
c1 (p)
hn (γ) ≤ √
n

(285)

where
4
c1 (p) , √
VBSC



log 2
12p|Hb (p) − log p|3 12(1 − p)|Hb (p) + log(1 − p)|3
√
+
+
VBSC
VBSC
2πVBSC


(286)

is a constant independent of n. Using (283) and (285) in (153), we conclude that there exists
an (n, 2k , 0, δ̂)max secrecy code that satisfies
k = bn − log2 (gn−1 (δ̃))c

(287)

and
s

1
c1 (p)
1
δ̂ = δ̃ +
δ̃ 2 + √ +
2
2
n


1
= δ̃ + O √
.
n

r

log(2k + 1)
2n−k+1

(288)
(289)

This implies that
∗
Rmax






 1 
1
−1
n, 0, δ̂ ≥ log(2) n − (log2 )gn δ̂ − O √
−1
n
n
r
 
VBSC −1 
1
= Hb (p) −
Q δ̂ + O
.
n
n


(290)
(291)

Here, the second step follows from (281) and by Taylor-expanding Q−1 (x) around x = δ̂.
Combining (65) and (291) we conclude the proof.

June 14, 2017

DRAFT

51

R EFERENCES
[1] A. D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol. 54, no. 8, pp. 1355–1367, Oct. 1975.
[2] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Trans. Inf. Theory, vol. 24, no. 3, pp.
339–348, May 1978.
[3] Y. Liang, H. V. Poor, and S. Shamai (Shitz), “Information theoretic security,” in Foundations and Trends in Communications
and Information Theory.

NOW, 2008, vol. 5, no. 4–5, pp. 355–580.

[4] M. Bloch and J. Barros, Physical-Layer Security: from Information Theorey to Security Engineering.

Cambridge, UK:

Cambridge University Press, 2011.
[5] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Trans. Inf. Theory,
vol. 56, no. 5, pp. 2307–2359, May 2010.
[6] M. Hayashi, “Information spectrum approach to second-order coding rate in channel coding,” IEEE Trans. Inf. Theory,
vol. 55, no. 11, pp. 4947–4966, Nov. 2009.
[7] V. Y. F. Tan, “Asymptotic estimates in information theory with non-vanishing error probabilities,” in Foundations and
Trends in Communications and Information Theory. Delft, The Netherlands: now Publishers, 2014, vol. 11, no. 1–2, pp.
1–184.
[8] M. Bellare, S. Tessaro, and A. Vardy, “Semantic security for the wiretap channel,” in Advances in Cryptology (Lecture
Notes in Computer Science).

Berlin, Germany: Springer, 2012, vol. 7417, pp. 2940–311.

[9] S. Goldwasser and S. Micali, “Probabilistic encryption,” J. Comput. Syst. Sci., vol. 28, no. 2, pp. 270–299, Apr. 1984.
[10] M. Hayashi, “General nonasymptotic and asymptotic formulas in channel resolvability and identification capacity and their
application to the wiretap channel,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1562–1575, Apr. 2006.
[11] T. S. Han and S. Verdú, “Approximation theory of output statistics,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 752–772,
May 1993.
[12] A. Wyner, “The common information of two dependent random variables,” IEEE Trans. Inf. Theory, vol. 21, no. 2, pp.
163–179, Mar. 1975.
[13] M. Hayashi, “Tight exponential analysis of universally composable privacy amplification and its applications,” IEEE Trans.
Inf. Theory, vol. 59, no. 11, Nov. 2013.
[14] M. H. Yassaee, M. R. Aref, and A. Gohari, “Non-asymptotic output statistics of random binning and its applications,” in
Proc. IEEE Int. Symp. Inf. Theory (ISIT), Istanbul, Turkey, Jul. 2013, pp. 1849–1853.
[15] V. Y. F. Tan, “Achievable second-order coding rates for the wiretap channel,” in Proc. IEEE Int. Conf. Comm. Syst.,
Singapore, Nov. 2012, pp. 65–69.
[16] M. Hayashi, “Exponential decreasing rate of leaked information in universal random privacy amplification,” IEEE Trans.
Inf. Theory, vol. 57, no. 6, pp. 3989–4001, Jun. 2011.
[17] M. H. Yassaee, “One-shot achievability via fidelity,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Hong Kong, China, Jun.
2015.
[18] M. Tahmasbi and M. R. Bloch, “Second order asymptotics for degraded wiretap channels: How good are existing codes?”
in Proc. 54th Allerton Conf. Commun., Contr., Comp., UIUC, Illinois, USA, Sep. 2016, pp. 830–837.
[19] M. B. Parizi, E. Telatar, and N. Merhav, “Exact random coding secrecy exponents for the wiretap channel,” IEEE Trans.
Inf. Theory, vol. 63, no. 1, pp. 509–531, Jan. 2017.
[20] H. Tyagi and S. Watanabe, “Converses for secret key agreement and secure computing,” IEEE Trans. Inf. Theory, vol. 61,
no. 9, pp. 4809–4827, Sep. 2015.

June 14, 2017

DRAFT

52

[21] M. Hayashi, H. Tyagi, and S. Watanabe, “Strong converse for a degraded wiretap channel via active hypothesis testing,”
in Proc. Allerton Conf. Commun., Contr., Comput., Monticello, IL, Sep. 2014, pp. 148–151.
[22] V. Y. F. Tan and M. Bloch, “Information spectrum approach to strong converse theorems for degraded wiretap channels,”
IEEE Trans. Inf. Forensics Security, vol. 10, no. 9, pp. 1891–1904, Sep. 2015.
[23] J. Liu, P. Cuff, and S. Verdú, “Eγ -resolvability,” IEEE Trans. Inf. Theory, vol. 63, no. 5, pp. 2629–2658, May 2017.
[24] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,” IEEE Trans. Inf. Theory, vol. 50, no. 12, pp.
3047–3061, Dec. 2004.
[25] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed.

Cambridge,

U.K.: Cambridge Univ. Press, 2011.
[26] C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, “Generalized privacy amplification,” IEEE Trans. Inf. Theory,
vol. 41, no. 6, pp. 1915–1923, Nov. 1995.
[27] R. Renner, “Security of quantum key distribution,” Ph.D. dissertation, ETH, Zurich, Switzerland, Sep. 2005.
[28] M. Hayashi, “Security analysis of ε-almost dual universal2 hash functions: Smoothing of min entropy vs. smoothing of
Rényi entropy of order 2,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3451–3476, Jun. 2016.
[29] S. Watanabe and M. Hayashi, “Non-asymptotic analysis of privacy amplification via Rényi entropy and inf-spectral entropy,”
in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Istanbul, Turkey, Jul. 2013, pp. 2715–2719.
[30] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” J. Amer. Statist. Assoc, vol. 58, no. 301,
pp. 13–30, Mar. 1963.
[31] C. McDiarmid, “On the method of bounded differences,” in Surveys in Combinatorics.

Cambridge, UK: Cambridge

University Press, 1989, vol. 141, pp. 148–188.
[32] R. Ahlswede and I. Csiszár, “Common randomness in information theory and cryptography—part ii. cr capacity,” IEEE
Trans. Inf. Theory, vol. 44, no. 1, pp. 225–240, Jan. 1998.
[33] P. Cuff, “A stronger soft-covering lemma and applications,” in IEEE Commun. Netw. Security (CNS), Florence, Italy, Sep.
2015, pp. 40–43.
[34] ——, “Soft covering with high probability,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Barcelona, Spain, Jul. 2016, pp.
2963–2967.
[35] G. Vazquez-Vilar, A. T. Campo, A. Guillén i Fàbregas, and A. Martinez, “Bayesian m-ary hypothesis testing: The metaconverse and Verdú-Han bounds are tight,” IEEE Trans. Inf. Theory, vol. 62, no. 5, pp. 2324–2333, May 2016.
[36] M. Hayashi and R. Matsumoto, “Secure multiplex coding with dependent and non-uniform multiple messages,” IEEE
Trans. Inf. Theory, vol. 62, no. 5, pp. 2355–2409, May 2016.
[37] Z. Goldfeld, P. Cuff, and H. H. Permuter, “Semantic-security capacity for wiretap channels of type II,” IEEE Trans. Inf.
Theory, vol. 62, no. 7, pp. 3863–3879, Jul. 2016.
[38] C. E. Shannon, “Probability of error for optimal codes in a Gaussian channel,” Bell Syst. Tech. J., vol. 38, no. 3, pp.
611–656, May 1959.
[39] V. Kostina and S. Verdú, “Lossy joint source-channel coding in the finite blocklength regime,” IEEE Trans. Inf. Theory,
vol. 59, no. 5, pp. 2545–2575, May 2013.
[40] J. Grubb, S. Vishwanath, Y. Liang, and H. V. Poor, “Secrecy capacity of semi-deterministic wire-tap channels,” in Proc.
IEEE Inf. Theory Workshop Inf. Theory Wireless Netw., Solstrand, Norway, Jul. 2007.
[41] M. Hayashi, H. Tyagi, and S. Watanabe, “Secret key agreement: General capacity and second-order asymptotics,” IEEE
Trans. Inf. Theory, vol. 62, no. 7, pp. 3796–3810, Jul. 2016.

June 14, 2017

DRAFT

53

[42] W. Yang, R. F. Schaefer, and H. V. Poor, “Secrecy-reliability tradeoff for semi-deterministic wiretap channels at finite
blocklength,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany, Jun. 2017.
[43] L. Carter and M. Wegman, “Universal classes of hash functions,” J. Comput. Syst. Sci., vol. 18, no. 2, pp. 143–154, 1979.
[44] S. Boyd and L. Vandenberghe, Convex Optimization.

Cambridge, U.K.: Cambridge Univ. Press, 2004.

[45] M. Raginsky and I. Sason, “Concentration of measure inequalities in information theory, communications and coding,” in
Foundations and Trends in Communications and Information Theory. now Publishers, 2013, vol. 10, no. 1–2, pp. 1–246.
[46] W. Feller, An Introduction to Probability Theory and Its Applications. New York, NY, USA: John Wiley & Sons, 1970,
vol. 1.
[47] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless
channels I,” Inf. Contr., vol. 10, pp. 65–103, 1967.
[48] V. Y. F. Tan and M. Tomamichel, “The third-order term in the normal approximation for the AWGN channel,” IEEE Trans.
Inf. Theory, vol. 61, no. 5, pp. 2430–2438, May 2015.
[49] I. Csiszár and P. C. Shields, “Information theory and statistics: A tutorial,” in Foundations and Trends in Communications
and Information Theory.

June 14, 2017

now Publishers, 2004, vol. 1, no. 4, pp. 417–528.

DRAFT

