1

The MAC Resolvability Region, Semantic Security
and Its Operational Implications

arXiv:1710.02342v2 [cs.IT] 22 Jan 2018

Matthias Frey, Igor Bjelaković and Sławomir Stańczak
Technische Universität Berlin

Abstract—Building upon previous work on the relation between secrecy and channel resolvability, we revisit a secrecy
proof for the multiple-access channel (MAC) from the perspective
of resolvability. In particular, we refine and extend the proof
to obtain novel results on the second-order achievable rates.
Then we characterize the resolvability region of the memoryless
MAC by establishing a conceptually simple converse proof for
resolvability that relies on the uniform continuity of Shannon’s
entropy with respect to the variational distance. We discuss the
operational meaning of the information theoretic concept of semantic security from the viewpoint of Ahlswede’s General Theory
of Information Transfer and show interesting implications on the
resilience against a large class of attacks even if no assumption
can be made about the distributions of the transmitted messages.
Finally we provide details on how the resolvability results can be
used to construct a wiretap code that achieves semantic security.

I. I NTRODUCTION
With an increasing number of users and things being connected to each other, not only the overall amount of communication increases, but also the amount of private and personal
information being transferred. This information needs to be
protected against various attacks. In fact, for some emerging
applications such as e-health services where sensitive medical
data might be transmitted using a Body Area Network, the
problem of providing secrecy guarantees is a key issue.
As discovered by Csiszár [12] and later more explicitly
by Bloch and Laneman [10] and investigated by Yassaee and
Aref [45] for the multiple-access case, the concept of channel
resolvability can be applied to provide such guarantees; in
essence, an effective channel is created by an encoder in such
a way that the output observed by a wiretapper is almost
independent of the transmitted messages, which renders the
output useless for the wiretapper. Moreover, the concept can
also be used in point-to-point settings as a means of exploiting
channel noise to convey randomness in such a way that
the distribution observed at the receiver can be accurately
controlled by the transmitter.
In this paper, we explore channel resolvability in a multipleaccess setting in which there is no communication between
the transmitters, yet they can control the distribution observed
at the receiver in a non-cooperative manner. More precisely,
given a multiple-access channel with an ideal or desired
The work was supported by the German Research Foundation (DFG) under
grant STA864/7-1 and by the German Federal Ministry of Education and
Research under grant 16KIS0605.
This paper was presented in part at the 4th Workshop on Physical-Layer
Methods for Wireless Security held during the 2017 IEEE Conference on
Communications and Network Security [21].

X ∼ qX

W

Y ∼ qY

qZ|X,Y

Z ∼ qZ

Fig. 1. Idealized input-output model of the multiple-access channel.

M1
M2

C1
C2

Xn
Yn

W n qZ n |X n ,Y n

Z n ∼ pZ n |C1 ,C2

Fig. 2. Resolvability codebooks are used as an input to the MAC channel to
create a channel output at the receiver that well approximtes the given ideal
output distribution (i.e. the output looks as if n independent instances of the
output in Figure 1 were observed).

output distribution under some input distribution (see Figure
1), the resolvability problem for this multiple-access channel
consists in finding for each transmitter a finite sequence of
codewords (called a codebook) such that if each transmitter
chooses a codeword at random and independently of the other
transmitter, then the MAC output well approximates the given
ideal output distribution. The coding setting is illustrated in
Figure 2 where each codeword is a tuple of n elements of the
input alphabet and n is referred to as the block length.
The first part of the paper deals with the resolvability
problem for the memoryless MAC, while in the second part we
show how the concept of channel resolvability can be exploited
to achieve strong operational secrecy guarantees over a wiretap
MAC.
A. Literature
To the best of our knowledge, the concept of approximating
a desired output distribution over a communication channel using as little randomness as possible at the transmitter was first
introduced by Wyner [43], who used normalized KullbackLeibler divergence as a similarity measure between the actual
and the desired output distribution. Han and Verdú [25]
introduced the term channel resolvability for a similar concept;
however, instead of the Kullback-Leibler divergence, they
used the variational distance as a metric and showed, among
others, the existence of a codebook that achieves an arbitrarily
small variational distance by studying the expected variational
distance of a random codebook.
A stronger result stating that the probability of drawing an
unsuitable random codebook is doubly exponentially small is
due to Cuff [14]. Related results were proposed before by

2

Csiszár [12] and by Devetak [16] for the quantum setting, who
based his work on the non-commutative Chernoff bound [3].
Further secrecy results that are either based on or related to the
concept of channel resolvability can be found in Hayashi [27],
Bloch and Laneman [10], Hou and Kramer [29], and Wiese
and Boche [42], who applied Devetak’s approach to a multipleaccess setting. Cuff [14] presented a result on the secondorder rate; a related result was proposed by Watanabe and
Hayashi [41]. Resolvability for MACs has been explored
by Steinberg [38] and later by Oohama [36]. Explicit lowcomplexity codebooks for the special case of symmetric MACs
have been proposed by Chou, Bloch and Kliewer [11].
Converse results for channel resolvability have been proposed by Han and Verdú [25] and, for the multiple-access
channel, by Steinberg [38]. However, since these studies consider channels with memory and allow for arbitrary input and
output distributions (in particular, they need not be identical or
independent across channel uses), these results are not directly
transferrable to the memoryless case considered in this paper.
Converse proofs for the memoryless single-user case were
given by Wyner [43] and later by Hou [30]; however, instead of
the variational distance considered in this study, they assumed
the Kullback-Leibler divergence as a similarity measure so that
the results of [30] cannot be applied directly either.
Security concepts from cryptography have been redefined as
secrecy concepts for the information theoretic setting by Bellare, Tessano and Vardy in [7] and [6], where the authors also
discussed the interrelations between these concepts; however,
the proposed schemes involve some cryptographic elements,
such as shared secrets between transmitter and legitimate
receiver or shared (public) randomness. To the best of our
knowledge, there are currently no results explicitly linking the
concept of semantic security to the operational meaning in
communication theory.
Wiretap codes that achieve semantic security over the Gaussian channel have been proposed by Ling, Luzzi, Belfiore
and Stehlé [33]. Thangaraj [39] showed how to construct
semantically secure wiretap codes for the single-user channel
and already noted the link to channel resolvability. Goldfeld,
Cuff and Permuter [23][22] showed how channel resolvability
techniques can be used to obtain wiretap codebooks that
achieve semantic security over the single-user channel; the
technique had been previously sketched by Cuff [15].
Liang and Poor [32], Ekrem and Ulukus [18], as well as Liu
and Kang [34] provided converse results for related multipleaccess wiretap channels, but these results do not carry over in a
straightforward fashion to the converse results for the channel
model we consider in this paper to study achievable secrecy
rates.
II. OVERVIEW

AND

M AIN C ONTRIBUTIONS

The main contributions of this study can be summarized as
follows:
1) We characterize the resolvability region of the discrete
memoryless multiple-access channel. Section IV proves
the direct theorem and a result on the second-order rate,
while Section V deals with the converse theorem.

R2

I(Y ; Z|V, X)
resolvability
region
capacity
region

I(Y ; Z|V )

R1
I(X; Z|V ) I(X; Z|V, Y )
Fig. 3. The MAC capacity region and the resolvability region as characterized
in Theorem 1.

2) In Section VI we show how resolvability can be exploited to achieve strong secrecy and semantic security,
and discuss operational implications of semantic security.
In the remainder of this section, we discuss our results in
more detail and explain their implications in the context of
secrecy and security. We start with a basic definition and refer
the reader to Section III for further definitions.
Given a multiple-access channel W = (X , Y, Z, qZ|X,Y )
and an output distribution qZ , we call a rate pair
(R1 , R2 ) achievable if there are sequences of codebooks
(C1,n )n≥1 , (C2,n )n≥1 of rates R1 and R2 , respectively, and
each of block length n such that
lim kpZ n |C1,n ,C2,n − qZ n kTV = 0 .

n→∞

The resolvability region SW,qZ is defined as the closure of the
set of all achievable rate pairs.
The main resolvability result in this work is the following
characterization of SW,qZ .
Theorem 1. Let W = (X , Y, Z, qZ|X,Y ) be a channel and
qZ an output distribution. Let
[
′
:=
SW,q
{(R1 , R2 ) :I(X, Y ; Z|V )≤R1 + R2
Z
pV ,qX|V ,qY |V

∧ I(X; Z|V )

∧ I(Y ; Z|V )

≤R1

≤R2 },

where pV ranges over all probability mass functions on the
alphabet V := {1, . . . , |Z| + 3} and qX|V , qY |V range over
all conditional probability distributions such that, for every
v ∈ V and z ∈ Z,
XX
qZ (z) =
qX|V (x|v)qY |V (y|v)qZ|X,Y (z|x, y),
x∈X y∈Y

and the mutual information is computed with respect to the
induced joint probability mass function. Then
′
= SW,qZ .
SW,q
Z

3

X

qZlegit |X,Y

by distinguishing security, has some very strong operational
implications, some of which we explore from the point of view
of Ahlswede’s General Theory of Information Transfer [1].

Zlegit

W
Y

qZtap |X,Y

III. N OTATION , D EFINITIONS
Ztap

Fig. 4. Channel resolvability problem as part of the wiretap coding problem.

Figure 3 illustrates the resolvability region as characterized
in this theorem and the well-known capacity region of the
MAC.
′
Theorem 8 in Section V yields the converse part SW,q
⊇
Z
SW,qZ of the above theorem. The proof is remarkably simple
and mainly relies on the fact that entropy is continuous with
respect to the variational distance.
′
The direct part SW,q
⊆ SW,qZ follows from a stronger
Z
statement proven in Section IV. In particular, the statement
shows that not only does a sequence of codebook pairs
achieving the rates exist, but if they are constructed randomly,
the probability of drawing a bad pair of codebooks vanishes
doubly exponentially with increasing block length. Precisely,
we show the following.
Theorem 2. Let W = (X , Y, Z, qZ|X,Y ) be a given channel;
let qX and qY be input distributions,
R1 > I(X; Z)

(1)

R2 > I(Y ; Z)

(2)

R1 + R2 > I(X, Y ; Z).

(3)

Then there exist γ1 , γ2 > 0 such that for sufficiently large
block length n, the codebook distributions of block length n
and rates R1 and R2 satisfy

PC1 ,C2 kpZ n |C1 ,C2 − qZ n kTV > exp(−γ1 n)
≤ exp (− exp (γ2 n)) .
To prove this theorem, we revisit the proof in [42], thereby
focusing on channel resolvability. We use a slightly different
technique than that in [14], which we extend to the multipleaccess case to provide an explicit statement and a more
intuitive proof for a result only implicitly contained in [42].
In an excursus, we show how a slight refinement of the same
technique similarly as in [14] yields also a partial second-order
result.
In Section VI, we discuss different notions of secrecy and
the interconnection between them. In particular, in addition
to the classical concept of strong secrecy, we review the
notions of distinguishing security and semantic security, both
of which originate from the field of cryptography. Distinguishing security allows us to decompose the problem for wiretap
coding into a problem of coding for the MAC and a channel
resolvability problem as shown in Figure 4. The concept
of semantic security, on the other hand, which is implied

AND

P REREQUISITES

The operations log and exp use Euler’s number as a basis,
+
and all information quantities are given in nats. [·] denotes
the maximum of its argument and 0.
A channel W = (X , Y, Z, qZ|X,Y ) is given by finite input
alphabets X and Y, a finite output alphabet Z and a collection
of probability mass functions qZ|X,Y on Z for each pair
(x, y) ∈ X × Y. The random variables X, Y and Z represent
the two channel inputs and the channel output, respectively.
Input distributions for the channel are probability mass functions on X and Y denoted by qX and qY , respectively. We
define an induced joint distribution qX,Y,Z on X × Y × Z by
qX,Y,Z (x, y, z) := qX (x)q
Y (y)qP
Z|X,Y (z|x, y) and the output
P
distribution qZ (z) :=
x∈X
y∈Y qX,Y,Z (x, y, z) is the
marginal distribution of Z.
By a pair of codebooks of block length n ≥ 1 and
rates R1 ≥ 0 and R2 ≥ 0, we mean finite sequences
exp(nR )
exp(nR )
C1 = (C1 (m))m=1 1 and C2 = (C2 (m))m=1 2 , where
n
the codewords C1 (m) ∈ X and C2 (m) ∈ Y n are finite
sequences of elements of the input alphabets. We define a
probability distribution PC1 ,C2 on these codebooks as i.i.d.
drawings in each component of each codeword according to
qX and qY , respectively. Accordingly, we define the output
distribution induced by C1 and C2 on Z n by
pZ n |C1 ,C2 (z n ) := exp(−n(R1 + R2 ))
exp(nR1 ) exp(nR2 )

·

X

m1 =1

X

m2 =1

qZ n |X n ,Y n (z n |C1 (m1 ), C2 (m2 )).

Given probability distributions P and Q on a finite set A
with mass functions p and q, respectively, and positive α 6= 1,
the Rényi divergence of order α of P from Q is defined as
X
1
Dα (P ||Q) :=
log
p(a)α q(a)1−α .
α−1
a∈A

Furthermore, we define the variational distance between P
and Q (or between their mass functions) as
X
1X
+
kp − qkTV :=
|p(a) − q(a)| =
[p(a) − q(a)] .
2
a∈A

a∈A

Given random variables A, B and C distributed according
to rA,B,C , we define the (conditional) information density as
i(a; b) := log

rB|A,C (b|a, c)
rB|A (b|a)
, i(a; b|c) := log
.
rB (b)
rB|C (b|c)

The (conditional) mutual information is the expected value
of the (conditional) information density. We use H(A) and
H(A|B) to denote Shannon’s (conditional) entropy.
The following inequality was introduced in [8] and [20]; we
use a refinement here which follows e.g. from [5].
Theorem 3 (Berry-Esseen Inequality). Given a sequence
(Ak )nk=1 of i.i.d. copies of a random variable A on the reals

4

3

with EA = 0, EA2 = σ 2 < ∞ and E |A| = ρ < ∞,
define Ā := (A1 + · · · + An )/n.
dis√ Then the cumulative
√
tribution Rfunctions F (a) := P(Ā n/σ ≤ a) of Ā n/σ and
a
Φ(a) := −∞ 1/(2π) exp(−x2 /2)dx of the standard normal
distribution satisfy
ρ
∀a ∈ R : |F (a) − Φ(a)| ≤ 3 √ .
σ n

r and a family (rb′ ′ )b′ ∈B′ of elements of P such that for each
k ∈ {1, . . . , n},
Z
X
fk (rb )P (db) =
fk (rb′ ′ )r(b′ ).
(4)

We further use variations of the concentration bounds introduced in [28].

In this section, we prove Theorem 2. Together with the
observation that the resolvability region SW,qZ is convex, by
a standard time sharing argument, this yields the direct part
of Theorem 1 as an immediate consequence.
First, we show a slightly weaker version of Theorem 2.

Theorem 4 (Chernoff-Hoeffding Bound). Suppose A =
P
n
k=1 Ak , where the random variables in the sequence
(Ak )nk=1 are independently distributed with values in [0, 1]
and EA ≤ µ. Then for 0 < δ < 1,
 2 
δ
P(A > µ(1 + δ)) ≤ exp − µ .
3
This version can e.g. be found in [17, Ex. 1.1]. We also use
an extension of the Chernoff-Hoeffding bound for dependent
variables due to Janson [31, Theorem 2.1], of which we state
only a specialized instance that is used in this paper.
P
Theorem 5 (Janson [31]). Suppose A = nk=1 Ak , where the
random variables in the sequence (Ak )nk=1 take values in [0, 1]
and can be partitioned into χ ≥ 1 sets such that the random
variables in each set are independently distributed. Then, for
δ > 0,


δ2
.
P(A ≥ EA + δ) ≤ exp −2
χ·n
We also use [13, Lemma 2.7] which provides bounds for
the entropy difference of random variables that are close to
each other in terms of their variational distance. Note that the
definition of the variational distance in [13] differs from the
one used in this paper by a factor of 1/2, and we state the
lemma conforming with our definitions.
Lemma 1. Let A and B be random variables on an alphabet
A, distributed according to probability mass functions rA and
rB , respectively. If krA − rB kTV = δ ≤ 1/4, then
1
δ
|H(A) − H(B)| ≤ − δ log
.
2
2|A|
Remark 1. Since the function −δ/2 · log(δ/2|A|) is nondecreasing (in particular) for 0 ≤ δ ≤ 1/4, the assumption can
be weakened to krA − rB kTV ≤ δ ≤ 1/4.
Furthermore, for the proof of the converse theorem, we need
a lemma that is based on the Fenchel-Eggleston-Carathéodory
theorem and appeared first in [4] and of which we state the
version from [19, Appendix C].
Lemma 2. Let A be a finite set and B an arbitrary set.
Suppose that P is a connected compact subset of probability
mass functions on A and consider a family (rb )b∈B of elements
of P. Suppose further that (fk )nk=1 are continuous functions
mapping from P to the reals and B is a random variable
on B distributed according to some probability measure P .
Then there exist a random variable B ′ on some alphabet
B ′ of cardinality at most n with probability mass function

b′ ∈B′

B

IV. P ROOF

OF THE

D IRECT T HEOREM

Theorem 6. Suppose W = (X , Y, Z, qZ|X,Y ) is a channel,
qX and qY are input distributions,
R1 > I(X; Z|Y )
R2 > I(Y ; Z).
Then there exist γ1 , γ2 > 0 such that for large enough block
length n, the codebook distributions of block length n and
rates R1 and R2 satisfy

PC1 ,C2 kpZ n |C1 ,C2 − qZ n kTV > exp(−γ1 n)
≤ exp (− exp (γ2 n)) . (5)

The full Theorem 2 can then be proven with a time sharing
argument which we detail at the end of this section. In the
proof of Theorem 6, we consider two types of typical sets:
n
:= {(xn , y n , z n ) : i(xn ; z n |y n ) ≤ n(I(X; Z|Y ) + ε)}
T1,ε
n
T2,ε
:= {(y n , z n ) : i(y n ; z n ) ≤ n(I(Y ; Z) + ε)}.

We split the variational distance in atypical and typical parts
as follows, where Patyp,1 , Patyp,2 and Ptyp (z n ) are defined
by (6), (7) and (8) shown on the next page.
kpZ n |C1 ,C2 − qZ n kTV
+

X
pZ n |C1 ,C2 (z n )
n
−1
=
qZ n (z )
qZ n (z n )
z n ∈Z n
X
+
≤Patyp,1 + Patyp,2 +
qZ n (z n ) [Ptyp (z n ) − 1] . (9)
z n ∈Z n

Remark 2. The denominator of the fraction is almost surely
not equal to 0 as long as the numerator is not equal to 0. We
implicitly let the summation range only over the support of
the denominator, as we do in all further summations.
So the theorem can be proven by considering typical and
atypical terms separately. But first, we prove two lemmas to
help us to bound the typical and the atypical terms.
Lemma 3 (Bound for typical terms). Given a block length n,
ε > 0, 0 < δ < 1, random variables A, B and C on finite
alphabets A, B and C respectively with joint probability mass
exp(nR)
function rA,B,C , a rate R and a codebook C = (C(m))m=1
with each component of each codeword drawn i.i.d. according
to rA , for any bn ∈ B n and cn ∈ C n , we have

5

exp(nR1 ) exp(nR2 )

Patyp,1 :=

X

exp(−n(R1 + R2 ))

X

exp(−n(R1 + R2 ))

m1 =1

z n ∈Z n

Patyp,2 :=

X

X

X

exp(−n(R1 + R2 ))

m2 =1

m1 =1

P̌ := PC 

exp(nR)

X

X

m1 =1

exp(nR1 ) exp(nR2 )



n
qZ n |X n ,Y n (z n |C1 (m1 ), C2 (m2 ))1(C1 (m1 ),C2 (m2 ),zn )∈T
/ 1,ε

(6)

X

n
qZ n |X n ,Y n (z n |C1 (m1 ), C2 (m2 ))1(C2 (m2 ),zn )∈T
/ 2,ε

(7)

m2 =1

exp(nR1 ) exp(nR2 )

z n ∈Z n

Ptyp (z n ) :=

X

exp(−nR)

m=1

m2 =1

qZ n |X n ,Y n (z n |C1 (m1 ), C2 (m2 ))
n 1(C (m ),C (m ),z n )∈T n
1(C2 (m2 ),zn )∈T2,ε
1
1
2
2
1,ε
qZ n (z n )
(8)

A ⊆ X n × Y n × Z n , δ > 0, µ ≥ P((X n , Y n , Z n ) ∈ A) as
well as rates R1 and R2 and codebooks distributed according
to PC1 ,C2 defined in Section III, we have

rC n |An ,B n (cn |C(m), bn )
rC n |B n (cn |bn )


· 1(C(m),bn,cn )∈Tεn > 1 + δ 

X

P̂ := PC1 ,C2


δ2
≤ exp − exp(−n(I(A; C|B) + ε − R)) ,
3


where the typical set is defined as

exp(−n(R1 + R2 ))

z n ∈Z n
exp(nR1 ) exp(nR2 )

X

X

m2 =1

m1 =1

Tεn := {(an , bn , cn ) : i(an ; cn |bn ) ≤ n(I(A; C|B) + ε)}.

qZ n |X n ,Y n (z n |C1 (m1 ), C2 (m2 ))
!

1(C1 (m1 ),C2 (m2 ),zn )∈A > µ(1 + δ)

(10)

≤ exp(−2δ 2 µ2 exp(n min(R1 , R2 ))).

Proof. We have

exp(nR)
X

exp(−n(I(A; C|B) + ε))
P̌ = PC

Proof. We have


exp(nR1 ) exp(nR2 )

m=1

n

·

P̂ =PC1 ,C2 

n

rC n |An ,B n (c |C(m), b )
· 1(C(m),bn ,cn )∈Tεn
rC n |B n (cn |bn )



> exp(−n(I(A; C|B) + ε − R))(1 + δ) .

By the definition of Tεn in (10), the summands are at most 1,
and furthermore, the expectation of the sum can be bounded
as

exp(nR)
X
exp(−n(I(A; C|B) + ε))
EC 
m=1

exp(nR)

≤

X


rC n |An ,B n (cn |C(m), bn )
1(C(m),bn,cn )∈Tεn 
·
rC n |B n (cn |bn )

exp(−n(I(A; C|B) + ε))

m=1

rC n |An ,B n (cn |C(m), bn )
rC n |B n (cn |bn )
= exp(−n(I(A; C|B) + ε − R)).
· EC





Now applying Theorem 4 to the above shows the desired
probability statement and completes the proof.
Lemma 4 (Bound for atypical terms). Given a channel W =
(X , Y, Z, qZ|X,Y ), input distributions qX and qY , some set

X

m1 =1

X

m2 =1

X

z n ∈Z n

qZ n |X n ,Y n (z n |C1 (m1 ), C2 (m2 ))1(C1 (m1 ),C2 (m2 ),zn )∈A
!
> exp(n(R1 + R2 ))(µ + µδ)


exp(nR1 ) exp(nR2 )

≤PC1 ,C2 

X

m1 =1
n

X

m2 =1

X

z n ∈Z n

qZ n |X n ,Y n (z |C1 (m1 ), C2 (m2 ))1(C1 (m1 ),C2 (m2 ),zn )∈A
!



n
n
n
> exp n(R1 + R2 ) P((X , Y , Z ) ∈ A) + µδ

exp(2n(R1 + R2 ))µ2 δ 2
exp(n max(R1 , R2 )) exp(n(R1 + R2 ))
2 2
= exp(−2δ µ exp(n min(R1 , R2 ))),

≤ exp −2



where the inequality follows from Theorem 5 by observing that the innermost sum is confined to [0, 1], the two
outer summations together have exp(n(R1 + R2 ) summands
which can be partitioned into exp(n(max(R1 , R2 )) sets with
exp(n min(R1 , R2 )) independently distributed elements each,
and the overall expectation of the term is exp(n(R1 +
R2 )P((X n , Y n , Z n ) ∈ A).
We now have all the technical ingerdients needed to finish
the proof of Theorem 6.

6

Proof of Theorem 6. In order to bound Patyp,1 , we observe
that for any α > 1, we can bound
n
/ T1,ε
)
PX n ,Y n ,Z n ((X n , Y n , Z n ) ∈

n
n
qZ n |X n ,Y n (Z |X , Y n )
= PX n ,Y n ,Z n
qZ n |Y n (Z n |Y n )

(11)

= PX n ,Y n ,Z n

≤EX n ,Y n ,Z n

n

n

n

qZ n |X n ,Y n (Z |X , Y )
qZ n |Y n (Z n |Y n )

(12)

α−1

> exp(n(α − 1)(I(X; Z|Y ) + ε))

α−1 !
qZ n |X n ,Y n (Z n |X n , Y n )
qZ n |Y n (Z n |Y n )

· exp(−n(α − 1)(I(X; Z|Y ) + ε))

= exp n(α − 1) · (Dα PX,Y,Z ||PX|Y PZ|Y PY

− I(X; Z|Y ) − ε)
≤ exp(−nβ),

 (13)



(14)

(15)
(16)

where (16) holds as long as β < (α − 1)(I(X; Z|Y ) +
ε − Dα PX,Y,Z ||PX|Y PZ|Y PY ). We can achieve this for
sufficiently small β > 0 as long as α > 1 and I(X; Z|Y ) +
ε − Dα PX,Y,Z ||PX|Y PZ|Y PY > 0. In order to choose an
α > 1 such that the latter requirement holds, note that since
our alphabets are finite, the Rényi divergence is also finite
and thus it is continuous and approaches the Kullback-Leibler
divergence for α tending to 1 [40], which is in this case equal
to the mutual information term.
n
and
We apply Lemma 4 with A = (X n × Y n × Z n ) \ T1,ε
δ = 1 to obtain
PC1 ,C2 (Patyp,1 > 2 exp(−nβ))
≤ exp(−2 exp(n(min(R1 , R2 ) − 2β))).

(17)

Proceeding along similar lines of reasoning including another
n
application of Lemma 4 with A = X n × ((Y n × Z n ) \ T2,ε
)
and δ = 1, we show that if β > 0 is small enough,
PC1 ,C2 (Patyp,2 > 2 exp(−nβ))
≤ exp(−2 exp(n(min(R1 , R2 ) − 2β))).

(18)

As for the typical term, we first observe that for any fixed y n
and z n , we can apply Lemma 3 with A = X, B = Y , C = Z
and δ = exp(−nβ) to obtain
PC1 (Ptyp,1 (y n , z n ) > 1 + exp(−nβ))


1
≤ exp − exp(−n(I(X; Z|Y ) + ε + 2β − R1 )) , (19)
3
where we used
exp(nR1 )
n

n

Ptyp,1 (y , z ) :=

X

exp(−n(R1 ))

m1 =1

·

q

n

n

(z |C1 (m1 ), y )
n .
1(C1 (m1 ),yn ,zn )∈T1,ε
(20)
qZ n |Y n (z n |y n )

Z n |X n ,Y n

y n ∈Y n

and bound for arbitrary but fixed z n


> exp(n(I(X; Z|Y ) + ε))



We define a set of codebooks
\
Czn :=
{C1 : Ptyp,1 (y n , z n ) ≤ 1 + exp(−nβ)} (21)
P̃ := PC1 ,C2 (Ptyp (z n ) > 1 + 3 exp(−nβ) | C1 ∈ Czn )
in (78) to (81) in the appendix.
We can now put everything together as shown in (82) to
(84) in the appendix.
What remains is to choose γ1 and γ2 such that (5) holds.
First, we have to choose ε and β small enough such that
δ̂ := min min(R1 , R2 ) − 2β,

R1 − 2β − ε − I(X; Z|Y ),

R2 − 2β − ε − I(Y ; Z)

is positive. Since there have so far been no constraints on β
and ε except that they are positive and sufficiently small, such
a choice is possible provided R1 > I(X; Z|Y ) and R2 >
I(Y ; Z). The theorem then follows for large enough n by
choosing positive γ2 < δ̂ and γ1 < β.
Obviously, we can reverse the roles of X and Y in Theorem 6. In order to prove the full Theorem 2, however, we
need time sharing between the two corner points, as we detail
in the following proof.
Proof of Theorem 2. We are given R1 and R2 satisfying (1),
(2) and (3). In this proof, we show how to find a time sharing
parameter λ̂ with the following properties:
R1 > λ̂I(X; Z) + (1 − λ̂)I(X; Z|Y )

R2 > λ̂I(Y ; Z|X) + (1 − λ̂)I(Y ; Z)

We can then conclude the proof by applying Theorem 6 twice:
First we apply it with a block length of (1 − λ̂)n and then we
apply it with reversed roles of X and Y and a block length
of λ̂n.
To this end, we define functions mapping from [0, 1] to the
reals
R1 (λ) := λI(X; Z) + (1 − λ)I(X; Z|Y )
R2 (λ) := λI(Y ; Z|X) + (1 − λ)I(Y ; Z).
Note that R1 (λ) and R2 (λ) are continuous in λ, R1 (0) =
I(X; Z|Y ), R1 (1) = I(X; Z), R2 (0) = I(Y ; Z) and
R2 (1) = I(Y ; Z|X). If R1 > I(X; Z|Y ) or R2 >
I(Y ; Z|X), there is nothing to prove since Theorem 6 can
be applied directly. So we assume R1 ≤ I(X; Z|Y ) and
R2 ≤ I(Y ; Z|X), which means that R1 (λ) is strictly decreasing and R2 (λ) is strictly increasing in λ and we can find
λ1 , λ2 ∈ [0, 1] such that R1 (λ1 ) = R1 and R2 (λ2 ) = R2 .
Next, we note that λ1 < λ2 because under the assumption
λ1 ≥ λ2 , we can obtain the contradiction
R1 + R2 ≤ R1 (λ2 ) + R2 (λ2 ) = I(X, Y ; Z).
So we can find λ̂ with λ1 < λ̂ < λ2 . We then have R1 >
R1 (λ̂) and R2 > R2 (λ̂), as required.

7

A. Second Order Rates
Although the probability statement in Theorem 2 is quite
strong in the sense that it guarantees a doubly exponentially
low probability of drawing a bad pair of codebooks, a weak
spot of the theorem as stated is that the constants γ1 and
γ2 are guaranteed to be positive, but can be arbitrarily small
depending on the channel, the input distribution and the codebook rates and that the theorem is only valid for sufficiently
large n. So in particular, if we are given a fixed n (even
a very large one), we cannot draw any conclusions for the
error probabilities of codebooks of block length n. However, a
closer examination of the proof shows that stronger statements
are possible in this case. In this subsection, we give details how
the proof of Theorem 2 can be modified so that it yields the
following second-order result.
Theorem 7. Given a channel W = (X , Y, Z, qZ|X,Y ), input
distributions qX and qY , ε ∈ (0, 1), let the central second
and absolute third moment of i(X; Z|Y ) be V1 and ρ1 ,
respectively; analogously, we use V2 and ρ2 to denote the
central second and absolute third moment of i(Y ; Z). Suppose
the rates R1 , R2 depend on n in the following way:
r
log n
V1 −1
Q (ε) + c
(22)
R1 = I(X; Z|Y ) +
n
rn
V2 −1
log n
R2 = I(Y ; Z) +
Q (ε) + c
,
(23)
n
n
where Q := 1 − Φ with Φ as defined in the statement of
Theorem 3, and c > 1. Then, for any d ∈ (0, c − 1), we have

PC1 ,C2 kpZ n |C1 ,C2 − qZ n kTV >



3
1
+√
(µ1 + µ2 ) 1 + √
n
n


2
2
2 min(µ1 , µ2 )
exp(n min(R1 , R2 ))
≤ 2 exp −
n


1
+ 2 exp n(log|Z| + log|Y|) − nc−d−1 ,
3
where for both k = 1 and k = 2,


ρk
d log n
−1
+ 3√
µk := Q Q (ε) + √
nVk
Vk2 n
tends to ε for n → ∞.
An immediate consequence of this theorem is the following
corollary that follows by applying the theorem with the roles
of X and Y reversed.
Corollary 1. Theorem 7 holds with (22) and (23) replaced by
r
log n
V1 −1
Q (ε) + c
R1 = I(X; Z) +
n
n
r
V2 −1
log n
Q (ε) + c
R2 = I(Y ; Z|X) +
n
n
and V1 , ρ1 , V2 and ρ2 redefined to be the second and third
moments of i(X; Z) and i(Y ; Z|X), respectively.

Remark 3. The question of how the achievable second-order
rates behave near the line connecting these two corner points
should be a subject of further research.
n
and
Proof of Theorem 7. We consider the typical sets T1,ε
1
n
T2,ε2 , where for k = 1, 2, we choose εk > 0 to be
r
log n
Vk −1
Q (ε) + d
.
(24)
εk :=
n
n

The definitions (6), (7) and (8) change accordingly.
In order to bound Patyp,1 , we use Theorem 3 to obtain
n
)
/ T1,ε
PX n ,Y n ,Z n ((X n , Y n , Z n ) ∈
1
!
n
X
1
= PX n ,Y n ,Z n
(i(Xk ; Zk |Yk ) − I(X; Z|Y )) > ε1
n
k=1
 r 
n
ρ1
+ 3 √ = µ1 .
≤ Q ε1
V1
2
V1 n
√
An application of Lemma 4 with δ = 1/ n yields




1
PC1 ,C2 Patyp,1 > µ1 1 + √
n


2
2µ1
≤ exp −
exp(n min(R1 , R2 )) . (25)
n
Reasoning along similar lines shows
n
) ≤ µ2
/ T2,ε
PY n ,Z n ((Y n , Z n ) ∈
2

so that a further application of Lemma 4 yields



1
PC1 ,C2 Patyp,2 > µ2 1 + √
n


2
2µ
≤ exp − 2 exp(n min(R1 , R2 )) . (26)
n
For the typical term, we use the definitions (20) and (21) with
n
, and observe that for any fixed y n and z n ,
the typical set T1,ε
1
we can√apply Lemma 3 with A = X, B = Y , C = Z and
δ = 1/ n to obtain


1
PC1 Ptyp,1 (y n , z n ) > 1 + √ )
n


1
≤ exp −
exp(−n(I(X; Z|Y ) + ε1 − R1 )) . (27)
3n
Now proceeding in a similar manner as in (78) to (81) shows


3
PC1 ,C2 Ptyp (z n ) > 1 + √ | C1 ∈ Czn
n


1
≤ exp −
exp(−n(I(Y ; Z) + ε2 − R2 )) ,
3n
√
where there is no assumption on n because 1/ n ≤ 1 for all
n ≥ 1.
The theorem then follows from (85) to (88) in the appendix.

8

V. C ONVERSE T HEOREM
In this section, we establish the following theorem which
implies the converse part of Theorem 1.
Theorem 8. Let W = (X , Y, Z, qZ|X,Y ) be a channel, qX , qY
input distributions (with induced output distribution qZ ) and
(C1,n )n≥1 , (C2,n )n≥1 sequences of codebooks of block lengths
n and rates R1 and R2 , respectively, such that
lim kpZ n |C1,n ,C2,n − qZ n kTV = 0.

n→∞

Then there are random variables X on X , Y on Y, Z on
Z and V on alphabet V = {1, . . . , |Z| + 3} with a joint
probability mass function pV pX|V pY |V qZ|X,Y such that the
marginal distribution of Z is qZ and
I(X, Y ; Z|V ) ≤ R1 + R2
I(X; Z|V ) ≤ R1
I(Y ; Z|V ) ≤ R2 .

even if the same probability mass functions have already been
introduced using a different notation before; e.g. we will write
pZ̃ n instead of pZ n |C1 ,C2 .
Additionally, we define a random variable V̂ that is uniformly distributed on {1, . . . , n} and independent of the other
random variables. We furthermore define X̂ := X̃V , Ŷ := ỸV
and Ẑ := Z̃V , noting that the conditional distribution of Ẑ
given X̂ and Ŷ is qZ|X,Y .
We observe that for any k ∈ {1, . . . , n}, an application of
the triangle inequality yields
1X
pZ̃k (z) − qZ (z)
kpZ̃k − qZ kTV =
2
z∈Z

=

(28)

≤

pẐ − qZ

TV

≤δ

δ
≤ R1 + R2
2|Z|
δ
≤ R1
I(X̂; Ẑ|V̂ ) + δ log
2|Z|
δ
I(Ŷ ; Ẑ|V̂ ) + δ log
≤ R2 .
2|Z|

I(X̂, Ŷ ; Ẑ|V̂ ) + δ log

(32)
(33)

Proof of Lemma 5. The codebooks induce random variables
X̃ n , Ỹ n and Z̃ n with joint probability mass function

X

exp(−nR1 )1C1 (m)=xn

X

exp(−nR2 )1C2 (m)=yn .

m=1
exp(nR2 )
n

pY n |C2 (y ) =

m=1

Note that for notational convenience, we will throughout this
proof use the definition of pX̃ n ,Ỹ n ,Z̃ n and the definitions
implied through the marginals of this probability mass function

1X
pZ̃k − qZ
n

≤ δ,

(36)

k=1
n
X
k=1

pZ̃k − qZ

(37)
TV
TV

(38)
(39)

where (37) is by definition of V̂ and Ẑ, (38) follows by the
triangle inequality and (39) by applying (36).
Next, we bound
nI(X̂, Ŷ ; Ẑ|V̂ ) − I(X̃ n , Ỹ n ; Z̃ n ) ≤ −nδ log

δ
2|Z|

(40)

as shown in (89) through (93) in the appendix.
Taking into consideration that
n(R1 + R2 ) ≥ H(X̃ n , Ỹ n ) ≥ I(X̃ n , Ỹ n ; Z̃ n )
and that (n + 1)/n ≤ 2, this proves (33).
Furthermore, we note that
nI(X̂; Ẑ|V̂ ) − I(X̃ n ; Z̃ n )


= nI(X̂, Ŷ ; Ẑ|V̂ ) − I(X̃ n , Ỹ n ; Z̃ n )


− nI(Ŷ ; Ẑ|X̂, V̂ ) − I(Ỹ n ; Z̃ n |X̃ n )
δ
≤ −nδ log
,
2|Z|

where
pX n |C1 (x ) =

TV

=

1
≤
n

= pX n |C1 (xn )pY n |C2 (y n )qZ n |X n ,Y n (z n |xn , y n ),
exp(nR1 )

z ∈Z

n

pẐ − qZ

pX̃ n ,Ỹ n ,Z̃ n (xn , y n , z n ) = pX n ,Y n ,Z n |C1 ,C2 (xn , y n , z n )

n

1 X
|p n (z n ) − qZ n (z n )|
2 n n Z̃

Now, we can bound

(34)
(35)

(pZ̃ n (z n ) − qZ n (z n ))

= kpZ̃ n − qZ n kTV ≤ δ.

Lemma 5. Let W = (X , Y, Z, qZ|X,Y ) be a channel, qX , qY
input distributions (with induced output distribution qZ ) and
C1 , C2 a pair of codebooks of rates R1 , R2 and block length
n such that
1
kpZ n |C1 ,C2 − qZ n kTV ≤ δ ≤ .
(31)
4
Then there are random variables X̂ on X , Ŷ on Y, Ẑ on
Z and V̂ on V := {1, . . . , n} with a joint probability mass
function pV̂ pX̂|V̂ pŶ |V̂ qẐ|X̂,Ŷ such that qẐ|X̂,Ŷ = qZ|X,Y and

X

z∈Z z n ∈Z n
zk =z

(29)
(30)

We first prove the following lemma, which states conclusions we can draw from the existence of a codebook pair for a
fixed block length n. Theorem 8 then follows by considering
the limit n → ∞, as we detail at the end of this section.

1X
2

(41)

where the inequality step follows by (40) and the observation
that nI(Ŷ ; Ẑ|X̂, V̂ ) − I(Ỹ n ; Z̃ n |X̃ n ) is nonnegative, because
I(Ỹ n ; Z̃ n |X̃ n )
n 

X
=
H(Z̃k |X̃ n , Z̃ k−1 ) − H(Z̃k |X̃ n , Ỹ n , Z̃ k−1 ) (42)
=

k=1
n 
X
k=1


H(Z̃k |X̃ n , Z̃ k−1 ) − H(Z̃k |X̃k , Ỹk )

(43)

9

≤

n 
X
k=1


H(Z̃k |X̃k ) − H(Z̃k |X̃k , Ỹk )

(44)

= nI(Ŷ ; Ẑ|X̂, V̂ ),

where (42) follows by the entropy chain rule, (43) follows
from the fact that Z̃k is conditionally independent of the other
random variables given X̃k and Ỹk and (44) follows because
conditioning does not increase entropy.
Analogous reasoning exchanging the roles of X and Y
yields
δ
.
(45)
nI(Ŷ ; Ẑ|V̂ ) − I(X̃ n ; Z̃ n ) ≤ −nδ log
2|Z|
In a similar way as we obtained (33) from (40), we
can derive the bounds (34) and (35) from (41) and (45),
respectively.
In order to ensure convergence in the limit n → ∞, we
need a slight refinement of Lemma 5.
Corollary 2. Lemma 5 holds with V replaced by some (fixed)
V ′ with |V ′ | ≤ |Z| + 3.
Proof. We apply Lemma 2 with A := X × Y, B := V,
letting P be the set of all probability distributions on X × Y
corresponding to independent random variables X on X and
Y on Y. Define
rv (x, y) := pX̂|V̂ (x|v)pŶ |V̂ (y|v)

=

n
X
1 XX
rv (x, y)qZ|X,Y (z|x, y)
n

k=1

x∈X y∈Y

= pẐ (z),

implying that (32) is preserved and completing the proof of
the corollary.
We are now ready to put everything together and prove our
main converse result.
Proof of Theorem 8. We write
δn := kpZ n |C1,n ,C2,n − qZ n kTV ,
and apply Corollary 2 with C1 := C1,n , C2 := C2,n and δ :=
δn to obtain random variables Xn , Yn , Zn and Vn satisfying
conditions (32), (33), (34) and (35). We assume without loss
of generality that Vn are all on the same alphabet V with
cardinality |Z| + 3 and observe that the space of probability
distributions on a finite alphabet is compact. So we can pick
an increasing sequence (nk )k≥1 such that pVnk converges to
a probability mass function pV , pXnk |Vnk =v converges for all
v ∈ V to a probability mass function pX|V =v and pYnk |Vnk =v
converges for all v ∈ V to a probability mass function pY |V =v .
The random variables X, Y , Z and V are then defined by
the joint probability mass function pV pX|V pY |V qZ|X,Y . (32)
implies that the marginal distribution of Z is qZ , (33) implies
(28), (34) implies (29) and (35) implies (30).

and
f1 (rv ) := I(X̂; Ẑ|V̂ = v)
f2 (rv ) := I(Ŷ ; Ẑ|V̂ = v)
f3 (rv ) := I(X̂, Ŷ ; Ẑ|V̂ = v)
XX
f4,z (rv ) :=
rv (x, y)qZ|X,Y (z|x, y),
x∈X y∈Y

where f4,z defines a set of |Z| functions. Note that the mutual
information terms depend only on rv and are continuous.
By Lemma 2, we have a random variable V ′ distributed
according to r on some alphabet of cardinality at most |Z| + 3
and probability mass functions (rv′ ′ )v′ ∈V ′ corresponding to
random variables independently distributed on X and Y. These
probability mass functions induce random variables X ′ and Y ′
that depend on V ′ , but are conditionally independent given V ′ .
We further define a random variable Z ′ on Z depending on
X ′ and Y ′ through qZ|X,Y . We have, by (4),
X
I(X ′ , Y ′ ; Z ′ |V ′ ) =
r(v ′ )I(X ′ , Y ′ ; Z ′ |V ′ = v ′ )
=

v ′ ∈V ′
n
X
k=1

1
I(X̂, Ŷ ; Ẑ|V̂ = k)
n

= I(X̂, Ŷ ; Ẑ|V̂ ),
and, by similar arguments, I(X ′ ; Z ′ |V ′ ) = I(X̂; Ẑ|V̂ ) and
I(Y ′ ; Z ′ |V ′ ) = I(Ŷ ; Ẑ|V̂ ), so properties (33), (34) and (35)
are preserved for the new random variables. Furthermore, also
by (4), we have for each z ∈ Z,
X
XX
pZ ′ (z) =
r(v ′ )
rv′ ′ (x, y)qZ|X,Y (z|x, y)
v ′ ∈V ′

x∈X y∈Y

VI. C HANNEL R ESOLVABILITY

AND

S ECRECY

In this section, we summarize some existing notions of
secrecy and a few facts about their relations to each other,
and also discuss their operational meaning. We then show
explicitly how our channel resolvability results can be applied
to derive a secrecy result for the multiple-access wiretap
channel that not only implies strong secrecy, but has even
stronger operational properties than the classical notion of
strong secrecy. We start by providing additional definitions in
Subsection VI-A, then we discuss different notions of secrecy
and interconnections between them in Subsection VI-B. Then
we show how our resolvability results can be used to achieve
secrecy over the multiple-access channel. To this end, we first
repeat a well-known result on achievable rates for the multipleaccess channel in Subsection VI-C which is the second crucial
ingredient besides resolvability for the secrecy theorem we
prove in Subsection VI-D.
A. Additional Definitions
In contrast to the other sections, in this section we will also
look at probability distributions on the alphabet of possible
messages. We therefore use M1 := {1, . . . , exp(nR1 )} and
M2 := {1, . . . , exp(nR2 )} to denote the message alphabets;
for convenience we denote by M := M1 × M2 the message
alphabet of both transmitters. M1 , M2 and M = (M1 , M2 )
are random variables on M1 , M2 and M, respectively, to
denote the messages chosen by the transmitters to be sent and
pM denotes a probability mass function on M describing the
distribution of M .

10

By a wiretap channel W = (Wlegit , Wtap ), we mean a
pair of channels, where Wlegit = (X , Y, Zlegit , qZlegit |X,Y ),
which we call the legitimate receiver’s channel and Wtap =
(X , Y, Ztap , qZtap |X,Y ), which we call the wiretapper’s channel, share the same input alphabets.
A wiretap code of block length n for the multiple-access
channel consists of two collections of probability mass functions pX n |M1 for each m1 ∈ M1 and pY n |M2 for each
m2 ∈ M2 (called the encoders), as well as a decoder
n
dn : Zlegit
→ M. The encoders and the wiretap channel
together induce for each m ∈ M a wiretapper’s output
n
distribution on Ztap
.
In this paper, we will consider a special class of wiretap
encoders: By a pair of wiretap codebooks of block length n, information rates R1 , R2 and randomness rates L1 , L2 , we mean
functions C1 : {1, . . . , exp(nR1 )}×{1, . . . , exp(nL1 )} → X n
and C2 : {1, . . . , exp(nR2 )} × {1, . . . , exp(nL2 )} → Y n .
Given input distributions qX and qY , we define a probability
distribution PC1 ,C2 on the set of all possible codebooks such
that every component of every function value is independently distributed according to qX or qY , respectively. Such
a pair of codebooks induces encoders in the sense defined
above: For k ∈ {1, 2}, transmitter k picks (independently
of the other transmitter and without cooperation) a message
mk ∈ {1, . . . , exp(nRk )} and draws uniformly at random
ℓk ∈ {1, . . . , exp(nLk )}. The transmitted codeword is then
Ck (mk , ℓk ). The wiretapper’s output distribution induced by
these encoders is
n
n |C (m ,·),C (m ,·) (z ) := exp(−n(L1 + L2 ))
pZtap
1
1
2
2
exp(nL1 ) exp(nL2 )

X

ℓ1 =1

X

ℓ2 =1

n
n |X n ,Y n (z |C1 (m1 , ℓ1 ), C2 (m2 , ℓ2 )).
qZtap

B. Secrecy Concepts and their Operational Meanings
In this subsection, we give a short overview over some
notions of information-theoretic secrecy. We adapt the notation
in the sources we are citing in such a way that it conforms
with the notation we have been using in this paper, which
is specific to the multiple-access wiretap channel, but the
concepts apply also to (and have originally been introduced
for) wiretap channels with only one transmitter.
Before we give formal definitions of secrecy, we first take a
look at what operational implications we want a good notion of
secrecy to have. In [1], Ahlswede generalized the communication task in the following way: The transmitter picks a message
M ∈ M, encodes it and transmits the codeword over a
channel. The receiver then aims not necessarily at decoding the
exact message M , but rather has a partition {M1 , . . . , Mℓ }
of M, i.e. disjoint subsets of M with ∪ℓk=1 Mk = M. Its task
is then to reconstruct k such that M ∈ Mk . The transmitter
does not know the exact partition Π that defines the receiver’s
task, but has only a subset {Π1 , . . . , Πt } of the set of all
possible partitions of M and has to encode the message in
such a way that the receiver can decode with high probability
no matter which partition in this set defines its task, or put
differently, we assume there is one receiver for each partition

and we want each receiver to be able to decode with high
probability. Ahlswede gave a list of specializations of this
very general concept that he deemed potentially useful for
real-world communication systems. Two of these are:
1) t = 1 and the only partition Π1 is the partition of
singletons {{m} : m ∈ M}. Here the receiver’s task
amounts to Shannon’s classical decoding problem.
2) t = |M| and the set of partitions is
n
o
{m}, M \ {m} : m ∈ M .

This corresponds to the problem of identification codes
introduced by Ahlswede and Dueck [2].
These decoding tasks can not only be understood as having
to be performed by a legitimate receiver in cooperation with
the transmitter, but can also be seen as possible attacks carried
out by a wiretapper, where each possible attack is defined by a
partition on M. For instance, we could deem the wiretapper’s
attack to have been successful only if it is able to decode
the exact message which corresponds to item 1), or, by an
alternative definition, we might choose a particular message
m that the wiretapper has to identify corresponding to one
of the partitions of item 2) and thus obtain a much weaker
definition of what constitutes a successful attack.
The best thing we might wish for in this context would be
that the wiretapper be unable to perform attacks corresponding
to any possible partition of the message set. In fact, demanding
this is equivalent to insisting that the wiretapper shall not
be able to decode any function of the transmitted message
(because a function induces a partition of its domain via the
preimages of singletons in its range).
Shannon introduced the concept of information theoretic
secrecy and required for his condition of perfect secrecy [37]
n
that I(M ; Ztap
) = 0. In Shannon’s cipher system, both
legitimate receiver and wiretapper get the same channel output,
but transmitter and legitimate receiver share a key, which is
unknown to the wiretapper.
Later, Wyner introduced the wiretap channel, where the
wiretapper’s channel output is degraded with respect to the
legitimate receiver’s channel output, but wiretapper and legitimate receiver do not share a key. In order to be more
amenable to analysis, he weakened Shannon’s perfect secrecy
criterion and introduced the concept of weak secrecy [44].
A sequence of codes for increasing block length n is said
n
to achieve weak secrecy if I(M ; Ztap
)/n approaches 0 as
n tends to infinity, where M is assumed to be uniformly
distributed over the message set. It turns out that a sequence
of codes can achieve weak secrecy while the total amount
of information leaked still tends to infinity with the block
length approaching infinity. Therefore, the notion of strong
secrecy was introduced by Maurer [35] which demands that
n
I(M ; Ztap
) shall approach 0 as n tends to infinity, where M
is still assumed to be distributed uniformly.
Strong secrecy has been shown to imply that full decoding
is only possible with an error probability that approaches the
probability of guessing correctly without any channel output
at all and it has also been shown to provide some resilience
against identification attacks [9], however, some messages

11

might remain identifiable and no method was proposed of ensuring that any particular given message m not be identifiable.
This leads us to the concept of semantic security, which
originates from the field of cryptography [24], but has also
been redefined to yield an information-theoretic secrecy criterion [7][6].
Following the discussion in [6] and adapting to our notation,
we say that a sequence of codebooks achieves semantic
security if

n
n (M ∈ f (Z
max
PM,Ztap
max
tap ))
n →Π
Π,PM
f :Ztap

− max PM (M ∈ g)
(46)
g∈Π

tends to 0 with n → ∞, where Π ranges over all partitions
of M and PM over all possible probability distributions of
M ∈ M. The positive term can be seen as the probability that
the wiretapper solves its decoding task successfully given its
channel output and an optimal decoder, while the second term
can be seen as subtracting the probability that the decoding
task is solved without knowledge of the wiretapper’s channel
output (i.e. by optimal guessing). This notion has a wide range
of operational implications in the sense that it is impossible
for the wiretapper to carry out an attack corresponding to any
of Ahlswede’s general communication tasks, as we show in
Examples 1 and 2.
Remark 4. (46) remains unchanged even if we allow stochastic wiretapper’s decoders, i.e. if we let f range over functions
n
to probability mass functions on Π.
that map from Ztap
On the other hand, it is not easy to prove directly that
a particular wiretap code achieves semantic security. We
therefore define a notion of secrecy that is more amenable to
analysis, namely, we say that a sequence of wiretap codebooks
achieves distinguishing security if
max

m1 ,m2 ,m̃1 ,m̃2

n |C (m ,·),C (m ,·)
kpZtap
1
1
2
2
n |C (m̃ ,·),C (m̃ ,·) kTV
− pZtap
1
1
2
2

(47)

approaches 0 with n tending to infinity.
Remark 5. Due to the triangle inequality, this notion of
distinguishing security is equivalent to
n |C (m ,·),C (m ,·) − pkTV
max kpZtap
1
1
2
2

m1 ,m2

approaching 0, where p is an arbitrary probability mass
n
function on Ztap
that does not change with m1 or m2 .
In [6], these and several other related concepts of
information-theoretical secrecy and their interrelations are
discussed. It turns out that distinguishing and semantic security
are equivalent and strictly stronger than strong secrecy. On the
other hand, if the definition of strong secrecy is strengthened
n
) approaches 0, where pM
to demand that maxpM I(M ; Ztap
ranges over all distributions of M (not just uniform), then
it becomes equivalent to the notions of distinguishing and
semantic security. We will present here versions of the proofs
adapted to our notation only for the implications that seem

most important to us in this context, namely that distinguishing
security, which we show in Theorem 10 can be achieved
over the multiple-access channel, implies both strong secrecy
(Lemma 6) and semantic security (Lemma 7).
We now give two examples to show how the concept of
semantic security implies resilience to the Ahlswede attacks
discussed before. Example 1 is a special case of Example 2,
but we lay it out explicitly anyway because we believe that it
illustrates the ideas involved in a particularly accessible way
and that the type of attack it describes could be particularly
relevant in practice.
Example 1 (Identification attacks). Suppose the wiretapper’s
n
objective is to determine from an observation of Ztap
whether
the transmitted message was m or not, i.e. the attack we consider can be described by the partition Π = {{m}, M\{m}}.
To this end, we assume that it has found some decoding
n
function f : Ztap
→ Π. Without assuming any probability
distribution on M, we can define two types of error

n
n
E1 := PZtap
f (Ztap
) = M \ {m} M = m

n
n
E2m̂ := PZtap
f (Ztap
) = {m} M = m̂ ,

where E2m̂ is defined for each m̂ 6= m. Note that if the
wiretapper is allowed to guess stochastically, it can trivially
achieve any values for E1 and E2m̂ that satisfy E1 + E2m̂ = 1
(where E2m̂ can be chosen the same for all m̂), even without
n
observing Ztap
. On the other hand, we now show that if (46)
is bounded above by δ > 0 and we fix an arbitrary m̂ 6= m,
the wiretapper cannot achieve much lower error probabilities
n
E1 and E2m̂ , even given the observation of Ztap
. We first note
that if PM is defined by the probability mass function
(
1
, m̃ = m ∨ m̃ = m̂
pM (m̃) := 2
0, otherwise,
then PM (M ∈ g) = 1/2 regardless of the choice of g. We can
thus bound
n
n (M ∈ f (Z
δ > PM,Ztap
tap )) − max PM (M ∈ g)
g∈Π

(48)

1
n
n (m ∈ f (Z
= PZtap
tap )|M = m)
2
(49)
1
1
n
n (m̂ ∈ f (Z
+ PZtap
tap )|M = m̂) −
2
2
1
m̂
= (1 − E1 + 1 − E2 − 1),
(50)
2
where (48) is by assumption valid for all PM , (49) follows
by plugging in PM as defined above and (50) follows by
plugging in the definitions of E1 and E2m̂ . We can express this
equivalently as
E1 + E2m̂ > 1 − 2δ,
which shows that as (46) tends to 0, the wiretapper’s minimum
error probabilities approach values that can be achieved by
stochastic guessing without observing any channel output at
all.
Example 2 (General Ahlswede Attacks). As a second, slightly
more involved example, we show the operational meaning
of semantic security for attacks defined by more general

12

partitions. Let Π = {M1 , . . . , Mℓ } be a partition of M.
Instead of assuming that the wiretapper can determine the
correct partition element based on any transmitted message,
we make a weaker assumption, namely that there is (at
least) one message in each partition element that can be
correctly identified. Formally, we say that the attacker has
n
a decoding function f : Ztap
→ Π and we fix messages
m1 ∈ M1 , . . . , mℓ ∈ Mℓ . For all k ∈ {1, . . . , ℓ}, the
error probabilities associated with partition element Mk and
message mk ∈ Mk is then defined as

n
n
Ekmk := PZtap
f (Ztap
) 6= Mk M = mk .

We observe that if stochastic guessing is allowed, the wiretapper can achieve any combination of error probabilities that
satisfies E1m1 + · · · + Eℓmℓ = ℓ − 1. We consider PM defined
by the probability mass function
(
1
, m = mk for some k
pM (m) := ℓ
0, otherwise,
noting that PM (M ∈ g) = 1/ℓ regardless of the choice of g.
Assuming that (46) is upper bounded by δ > 0, we have
n
n (M ∈ f (Z
δ > PM,Ztap
tap )) − max PM (M ∈ g)

(51)

ℓ
X
1
1
n
n (f (Z
PZtap
=
tap ) = Mk |M = mk ) −
ℓ
ℓ

(52)

g∈Π

=

k=1
ℓ
X

k=1

1
1
(1 − Ekmk ) −
ℓ
ℓ

k=1

(53)

which shows that also in this more general case, as (46) tends
to 0, the wiretapper’s error probabilities approach the values
that can be achieved by stochastic guessing without observing
any channel output at all, even if these error probabilities
are only assumed to hold for one message in every partition
element.
Lemma 6. If distinguishing security holds, i.e. (47) apn
). In particular,
proaches 0, then so does maxpM I(M ; Ztap
strong secrecy holds.
Proof. Fix an arbitrary distribution pM on M and observe that
(54)
(55)

where m̃ is chosen as the element in M that minimizes
n
H(Ztap
|M = m̃) and the last inequality follows from
Lemma 1, as long as δ < 1/4, where
δ=

X

(m1 ,m2 )∈M

n |C (m ,·),C (m ,·)
pM (m1 , m2 )pZtap
1
1
2
2

TV

pM (m1 , m2 )

(m1 ,m2 )∈M
n |C (m ,·),C (m ,·) − pZ n |C (m̃ ,·),C (m̃ ,·)
pZtap
1
1
2
2
1
2
2
tap 1

TV

.

Note that the latter variational distance term is clearly
bounded by (47), and so (55) approaches 0 if (47) does.
Lemma 7. (46) is upper bounded by (47). In particular,
distinguishing security implies semantic security.
Proof. Fix a partition Π of M and a probability mass function
pM on M that realize the outer maximum in (46) as well
n
as a decoding function f : Ztap
→ Π and a guess g ∈ Π
that realize the inner maxima. We can then rewrite (46) as
P1 + P2 − P3 by steps as shown in (94) through (97) in the
appendix.
Observe that P2 = PM (M ∈
/ g) and that, taking into
account that g minimizes PM (M ∈
/ g) over the elements of
Π,
X
X
pM (m̃1 , m̃2 )
P3 =
≥

Ekmk > ℓ − 1 − ℓδ,

n
n
n
I(M ; Ztap
) ≤ H(Ztap
) − H(Ztap
|M = m̃)
1
δ
≤ − δ log
n,
2
2 |Ztap |

≤

X

(m̃1 ,m̃2 )∈M

where (51) is by assumption valid for all PM , (52) follows by
plugging in PM and (53) follows by plugging in the definitions
of the Ekmk . We can express this equivalently as
ℓ
X

n |C (m̃ ,·),C (m̃ ,·)
− pZtap
1
1
2
2

n
z n ∈Ztap

n
n
n |C (m̃ ,·),C (m̃ ,·) (z )PM (M ∈
))
pZtap
/ f (Ztap
1
1
2
2
X
X
pM (m̃1 , m̃2 )

(m̃1 ,m̃2 )∈M

n
z n ∈Ztap

n
n |C (m̃ ,·),C (m̃ ,·) (z )PM (M ∈
pZtap
/ g))
1
1
2
2

= PM (M ∈
/ g).

Observe further that, optimizing the outcome of the indicator
function in P1 for each term in the innermost sum individually,
we get
X
pM (m1 , m2 )pM (m̃1 , m̃2 )
P1 ≤
(m1 ,m2 ),(m̃1 ,m̃2 )∈M

n |C (m ,·),C (m ,·) − pZ n |C (m̃ ,·),C (m̃ ,·)
· pZtap
1
1
2
2
1
2
2
tap 1

TV

,

which is clearly upper bounded by (47). Summarizing, we
have seen that P2 − P3 ≤ 0 and P1 is upper bounded by (47)
and consequently (46) is upper bounded by (47).
C. Coding for the Multiple-Access Channel
The capacity region of the multiple-access channel is well
known and proofs can be found in almost any textbook on
information theory, however, usually only the existence of a
suitable codebook is proven. We need here the slightly stronger
statement that the probability of randomly choosing a bad
codebook is exponentially small, which requires only a slight
modification of these proofs, which is, however, normally not
given in the textbooks explicitly. For the sake of completeness,
we state here the result that we need and present a proof that
is similar to the one given in [26].
Theorem 9. Suppose W = (X , Y, Z, qZ|X,Y ) is a channel, qX and qY are input distributions, R1 < I(X; Z|Y ),

13

R2 < I(Y ; Z|X) and R1 + R2 < I(X, Y ; Z). Then there
exist decoding functions
dn : Z n → {1, . . . , exp(nR1 )} × {1, . . . , exp(nR2 )}
and γ1 , γ2 > 0 such that for large enough block length n, the
codebook distributions of block length n and rates R1 and R2
satisfy
PC1 ,C2 (E > exp(−γ1 n)) ≤ exp (−γ2 n) ,

(56)

where we define the average decoding error probability as
E :=

nR2
exp
nR1 exp
X
X
m1 =1

exp(−n(R1 + R2 ))

m2 =1


PZ n dn (Z n ) 6= (m1 , m2 )


X n = C1 (m1 ), Y n = C2 (m2 ) .

Proof. We define typical sets

n
T1,ε
:= {(xn , y n , z n ) : i(xn ; z n |y n ) ≥ n(I(X; Z|Y ) − ε)}

n
T2,ε
:= {(xn , y n , z n ) : i(y n ; z n |xn ) ≥ n(I(Y ; Z|X) − ε)}

n
T3,ε
:= {(xn , y n , z n ) : i(xn , y n ; z n ) ≥ n(I(X, Y ; Z) − ε)}
n
n
n
Tεn := T1,ε
∩ T2,ε
∩ T3,ε

and a corresponding joint typicality decoder

n
n

(m1 , m2 ), (C1 (m1 ), C2 (m2 ), z ) ∈ Tε
dn (z n ) :=
for unique (m1 , m2 )


(1, 1),
otherwise.

So in order to correctly decode a received message, we need
the received sequence to be jointly typical with the encoded
messages, while it must not be jointly typical with any other
pair of codewords. We formalize these notions by defining the
probabilities of three error events corresponding to the former
being false as in (57) for k ∈ {1, 2, 3} and the probabilities
of error events corresponding to the latter being false as in
(58), (59) and (60). We observe by the union bound and the
definition of dn that
E≤

nR2
exp
nR1 exp
X
X
m1 =1

(62)

! (63)

> exp(n(α − 1)(I(X; Z|Y ) − ε))


≤EX n ,Y n ,Z n

qZ n |X n ,Y n (Z n |X n , Y n )
qZ n |Y n (Z n |Y n )

α−1 !

where (63) follows for all α < 1 by substituting the definition
n
of T1,ε
and reformulating, (64) follows by Markov’s inequality,
(65) follows by reformulating and substituting the definition of
Rényi divergence, and (66) follows for sufficiently small but
positive β by taking α < 1 close enough to 1 such that the
exponent in (65) is negative. This is possible by observing
that the Rényi divergence approaches the Kullback-Leibler
divergence for α → 1 and is finite and thus continuous since
our alphabets are finite [40].
Moreover, we have
1,1
EC1 ,C2 Eatyp,1

(67)
n

n

n

n
T1,ε



≤ exp(nR1 )PY n ,Z n PX n (X , Y , Z ) ∈
(68)
X X X
n
n n
= exp(nR1 )
qX n (x )qY n ,Z n (y , z )
xn ∈X n y n ∈Y n z n ∈Z n
n
· 1(xn ,yn ,zn )∈T1,ε

= exp(nR1 )

X

X

X

(69)
n

n


m1 ,m2
m1 ,m2
m1 ,m2
+
+ Etyp,3
+ Etyp,2
Etyp,1

m1 ,m2
m1 ,m2
m1 ,m2
Eatyp,1
+ Eatyp,2
+ Eatyp,3

1,1
1,1
1,1
+EC1 ,C2 Etyp,2
+EC1 ,C2 Etyp,2
EC1 ,C2 E ≤ EC1 ,C2 Etyp,1

1,1
1,1
1,1
+EC1 ,C2 Eatyp,3
+EC1 ,C2 Eatyp,2
+EC1 ,C2 Eatyp,1

We next bound each of these summands above by
exp(−nβ) for sufficiently large n and sufficiently small but
positive β.
To this end, we observe
(61)

n

qX n ,Y n ,Z n (x , y , z )

xn ∈X n y n ∈Y n z n ∈Z n
n n n

n
· exp(−i(x ; z |y ))1(xn ,yn ,zn )∈T1,ε

≤ exp(−nβ),

m2 =1

(64)

· exp(−n(α − 1)(I(X; Z|Y ) − ε))

= exp n(α − 1)


· Dα PX,Y,Z ||PX|Y PZ|Y PY − I(X; Z|Y ) + ε
(65)
≤ exp(−nβ)
(66)

≤ exp(n(R1 − I(X; Z|Y ) + ε)),

exp(−n(R1 + R2 ))

and thus, taking into cosideration that since the codewords are
m1 ,m2
m1 ,m2
have expectations
and Eatyp,k
identically distributed, Etyp,k
that do not depend on m1 or m2 , we get

1,1
EC1 ,C2 Etyp,1



n
/ T1,ε
= PX n ,Y n ,Z n (X n , Y n , Z n ) ∈


qZ n |X n ,Y n (Z n |X n , Y n ) α−1
= PX n ,Y n ,Z n
qZ n |Y n (Z n |Y n )

(70)
(71)
(72)

where (68) is an application of the union bound, (70) follows
by reformulating and substituting the definition of information
n
density, (71) follows by the definition of T1,ε
and (72) follows
for all sufficiently small β > 0 as long as ε is so small that
R1 − I(X; Z|Y ) + ε < 0.
We skip the calculations showing that
1,1
1,1
≤ exp(−nβ)
, EC1 ,C2 Eatyp,k
EC1 ,C2 Etyp,k

for k ∈ {2, 3}, sufficiently large n and sufficiently small β >
0, since these statements follow in a straightforward manner
by calculations very similar to the ones shown above.
Putting everything together and applying Markov’s inequality, we get that for sufficiently large n, sufficiently small
β > 0, γ1 < β, and γ2 < β − γ1 ,
PC1 ,C2 (E > exp(−γ1 n)) ≤ EC1 ,C2 (E) exp(γ1 n)

14



m1 ,m2
n
/ Tk,ε
X n = C1 (m1 ), Y n = C2 (m2 )
:= PZ n (X n , Y n , Z n ) ∈
Etyp,k


m1 ,m2
n
X n = C1 (m1 ), Y n = C2 (m2 )
Eatyp,1
:= PZ n ∃m̃1 6= m1 : (C1 (m̃1 ), Y n , Z n ) ∈ T1,ε


m1 ,m2
n
Eatyp,2
:= PZ n ∃m̃2 6= m2 : (X n , C1 (m̃2 ), Z n ) ∈ T2,ε
X n = C1 (m1 ), Y n = C2 (m2 )


m1 ,m2
n
X n = C1 (m1 ), Y n = C2 (m2 )
Eatyp,3
:= PZ n ∃m̃1 6= m1 , m̃2 6= m2 : (C1 (m̃1 ), C1 (m̃2 ), Z n ) ∈ T3,ε
≤ 6 exp(−n(β − γ1 ))
≤ exp(−γ2 n),

I(X; Ztap |V ) < I(X; Zlegit|Y, V ) − R1

I(Y ; Ztap |V ) < I(Y ; Zlegit |X, V ) − R2
I(X, Y ; Ztap |V ) < I(X, Y ; Zlegit |V ) − (R1 + R2 ).

(73)
(74)
(75)

Then there exist randomness rates L1 , L2 , decoding functions
n
dn : Zlegit
→{1, . . . , exp(nR1 )} × {1, . . . , exp(nL1 )}×

{1, . . . , exp(nR2 )} × {1, . . . , exp(nL2 )}

and γ1 , γ2 > 0, such that for sufficiently large n, the probability Pbad under the wiretap codebook distribution of drawing
a bad pair of codebooks is less than exp(−nγ2 ). A pair of
codebooks is considered to be bad if it does not satisfy all of
the following:
1) (Distinguishing Security). For any m1 , m2 , we have
n |C (m ,·),C (m ,·) − qZ n kTV ≤ exp(−γ1 n),
kpZtap
1
1
2
2

i.e. the wiretap codebooks achieve distinguishing security and the variational distance vanishes exponentially.
2) (Average decoding error). We have E ≤ exp(−nγ1 ),
where
nL1 exp
nR2 exp
nL2
exp
nR1 exp
X
X
X
X
ℓ1 =1

(60)

L1,2 = −I(Y ; Zlegit |X, V ) + R2 + I(X, Y ; Ztap |V )

Theorem 10. Suppose W = (Wlegit , Wtap ) is a wiretap
channel, V is a random variable, qX|V and qY |V are input
distributions and R1 and R2 are rates satisfying

m2 =1

(59)

L1,1 = I(X; Ztap |V )

D. Achievable Secrecy Rates under Distinguishing Security

m1 =1

(58)

where

concluding the proof of the theorem.

E :=

(57)

ℓ2 =1

exp(−n(R1 + R2 + L1 + L2 ))

PZ n dn (Z n ) 6= (m1 , ℓ1 , m2 , ℓ2 )


X n = C1 (m1 , ℓ1 ), Y n = C2 (m2 , ℓ2 ) .

is the average decoding error; i.e. the legitimate receiver
is able to (on average) reconstruct both the messages
and the randomness used at the transmitters with exponentially vanishing error probability.
Proof. Choose L1 such that
max(L1,1 , L1,2 ) < L1 < min(L1,1 , L1,2 ),

(76)

L1,1 = I(X; Zlegit |Y, V ) − R1

L1,2 = −I(Y ; Ztap |V ) + I(X, Y ; Zlegit |V ) − (R1 + R2 ).
To see that this is possible, we note that L1,1 < L1,1 is
equivalent to (73), L1,1 < L1,2 and L1,2 < L1,1 both follow
from (75), and L1,2 < L1,2 follows from (74) and (75).
Then, choose L2 such that
max(L2,1 , L2,2 ) < L2 < min(L2,1 , L2,2 ),

(77)

where
L2,1 = I(X, Y ; Ztap |V ) − L1

L2,2 = I(Y ; Ztap |V )

L2,1 = I(Y ; Zlegit |X, V ) − R2

L2,2 = I(X, Y ; Zlegit |V ) − L1 − (R1 + R2 ).
To see that this is possible, we note that L2,1 < L2,1 is
equivalent to L1 > L1,2 , which we have by (76), L2,1 < L2,2
is equivalent to (75), L2,2 < L2,1 is equivalent to (74) and
L2,2 < L2,2 is equivalent to L1 < L1,2 , which we also have
by (76).
Summarizing, with these choices, L1 , L2 have the properties
I(X; Ztap |V ) <

L1 < I(X; Zlegit|Y, V ) − R1

I(Y ; Ztap |V ) <
L2 < I(Y ; Zlegit |X, V ) − R2 .
I(X, Y ; Ztap |V ) < L1 + L2 < I(X, Y ; Zlegit |V ) − R2 .
We can look at the thus defined pair of random wiretap
codebooks in two ways. On the one hand, they can be
understood as a pair of codebooks of rates R1 + L1 and
R2 +L2 . They fulfill all the requirements of Theorem 9 (noting
that by time sharing, the theorem is also valid for the convex
closure specified in the theorem statement), and so we get
γ1′ , γ2′ > 0 such that
PC1 ,C2 (E > exp(nγ1′ )) ≤ exp(nγ2′ ).
On the other hand, we can look at them as a colexp(nR )
lection (C1 (m1 , ·))m1 =1 1 of codebooks of rate L1 and
exp(nR )
(C2 (m2 , ·))m2 =1 2 of codebooks of rate L2 , respectively.
Therefore, each pair (m1 , m2 ) corresponds to a pair of codebooks fulfilling the requirements of Corollary 2 (again noting
the possibility of time sharing), and so we get γ1′′ , γ2′′ > 0 such
that for all m1 , m2

15


PC1 ,C2 kpZ n |C1 (m1 ,·),C2 (m2 ,·) − qZ n kTV > exp(−γ1′′ n)

≤ exp (− exp (γ2′′ n)) .

Choosing γ1 := min(γ1′ , γ1′′ ), we can apply the union bound
to get
Pbad
≤ PC1 ,C2 (E > exp(nγ1′ ))+
exp(nR1 ) exp(nR2 )

X

m1 =1

X

m2 =1


PC1 ,C2 kpZ n |C1 (m1 ,·),C2 (m2 ,·) − qZ n kTV

> exp(−γ1′′ n)

≤ exp(γ2′ n) + exp(n(R1 + R2 ) − exp(γ2′′ n))
≤ exp(γ2 n)
for sufficiently large n, as long as we choose γ2 < γ2′ .
R EFERENCES
[1] R. Ahlswede. General theory of information transfer: Updated. Discrete
Applied Mathematics, 156(9):1348–1388, 2008.
[2] R. Ahlswede and G. Dueck. Identification via channels. Trans. Inf.
Theory, 35(1):15–29, 1989.
[3] R. Ahlswede and A. Winter. Strong converse for identification via
quantum channels. Trans. Inf. Theory, 48(3):569–579, 2002.
[4] Rudolf Ahlswede and Janos Korner. Source coding with side information
and a converse for degraded broadcast channels. IEEE Transactions on
Information Theory, 21(6):629–637, 1975.
[5] P. Beek. An application of Fourier methods to the problem of sharpening
the Berry-Esseen inequality. Prob. Theo. Rel. Fields, 23(3):187–196,
1972.
[6] M. Bellare, S. Tessaro, and A. Vardy. A cryptographic treatment of the
wiretap channel. arXiv:1201.2205, 2012.
[7] M. Bellare, S. Tessaro, and A. Vardy. Semantic security for the wiretap
channel. In Advances in Cryptology–CRYPTO 2012, pages 294–311.
Springer, 2012.
[8] A.C. Berry. The accuracy of the Gaussian approximation to the sum of
independent variates. Trans. Am. Math. Soc., 49(1):122–136, 1941.
[9] I. Bjelaković, H. Boche, and J. Sommerfeld. Secrecy results for
compound wiretap channels. Problems Inform. Transmission, 49(1):73–
98, 2013.
[10] M. R. Bloch and J. N. Laneman. Strong secrecy from channel
resolvability. Trans. Inf. Theory, 59(12):8077–8098, 2013.
[11] R. A. Chou, M. R. Bloch, and J. Kliewer. Low-complexity channel
resolvability codes for the symmetric multiple-access channel. In
Information Theory Workshop, pages 466–470. IEEE, Nov 2014.
[12] I. Csiszár. Almost independence and secrecy capacity. Problems Inform.
Transmission, 32(1):40–47, 1996.
[13] I. Csiszár and J. Körner. Information theory: coding theorems for
discrete memoryless systems. Cambridge University Press, 2011.
[14] P. Cuff. Soft covering with high probability. In ISIT, pages 2963–2967.
IEEE, 2016.
[15] Paul Cuff. A stronger soft-covering lemma and applications. In
Communications and Network Security (CNS), 2015 IEEE Conference
on, pages 40–43. IEEE, 2015.
[16] I. Devetak. The private classical capacity and quantum capacity of a
quantum channel. Trans. Inf. Theory, 51(1):44–55, 2005.
[17] D. P. Dubhashi and A. Panconesi. Concentration of measure for the
analysis of randomized algorithms. Cambridge University Press, 2009.
[18] E. Ekrem and S. Ulukus. On the secrecy of multiple access wiretap
channel. In 2008 46th Annual Allerton Conference on Communication,
Control, and Computing, pages 1014–1021, Sept 2008.
[19] Abbas El Gamal and Young-Han Kim. Network information theory.
Cambridge university press, 2011.
[20] C.-G. Esseen. On the Liapounoff limit of error in the theory of
probability. Almqvist & Wiksell, 1942.
[21] M. Frey, I. Bjelaković, and S. Stańczak. Mac resolvability: First and
second order results. In 2017 IEEE Conference on Communications and
Network Security (CNS): The Workshop on Physical-Layer Methods for
Wireless Security, pages 569–573, 2017.

[22] Z. Goldfeld, P. Cuff, and H. H. Permuter. Semantic-security capacity for
the physical layer via information theory. In 2016 IEEE International
Conference on Software Science, Technology and Engineering (SWSTE),
pages 17–27, June 2016.
[23] Z. Goldfeld, P. Cuff, and H. H. Permuter. Semantic-security capacity for
wiretap channels of type ii. IEEE Transactions on Information Theory,
62(7):3863–3879, July 2016.
[24] S. Goldwasser and S. Micali. Probabilistic encryption. Journal of
computer and system sciences, 28(2):270–299, 1984.
[25] T. S. Han and S. Verdú. Approximation theory of output statistics. Trans.
Inf. Theory, 39(3):752–772, 1993.
[26] Te Sun Han. Information-spectrum methods in information theory,
volume 50. Springer Science & Business Media, 2013.
[27] M. Hayashi. General nonasymptotic and asymptotic formulas in channel
resolvability and identification capacity and their application to the
wiretap channel. Trans. Inf. Theory, 52(4):1562–1575, 2006.
[28] W. Hoeffding. Probability inequalities for sums of bounded random
variables. J. Am. Stat. Ass., 58(301):13–30, 1963.
[29] J. Hou and G. Kramer. Effective secrecy: Reliability, confusion and
stealth. In ISIT, pages 601–605. IEEE, 2014.
[30] Jie Hou. Coding for relay networks and effective secrecy for wire-tap
channels. PhD thesis, Universitätsbibliothek der TU München, 2014.
[31] S. Janson. Large deviations for sums of partly dependent random
variables. Random Structures & Algorithms, 24(3):234–248, 2004.
[32] Y. Liang and H. V. Poor. Multiple-access channels with confidential
messages. IEEE Transactions on Information Theory, 54(3):976–1002,
March 2008.
[33] C. Ling, L. Luzzi, J.-C. Belfiore, and D. Stehlé. Semantically secure
lattice codes for the gaussian wiretap channel. Trans. Inf. Theory,
60(10):6399–6416, 2014.
[34] N. Liu and W. Kang. The secrecy capacity region of a special class of
multiple access channels. In 2011 IEEE International Symposium on
Information Theory Proceedings, pages 623–627, July 2011.
[35] Ueli M. Maurer. The Strong Secret Key Rate of Discrete Random Triples,
pages 271–285. Springer US, Boston, MA, 1994.
[36] Y. Oohama. Converse coding theorems for identification via multiple
access channels. In ISIT, pages 1650–1654, July 2013.
[37] C. E. Shannon. Communication theory of secrecy systems. Bell Labs
Technical Journal, 28(4):656–715, 1949.
[38] Y. Steinberg. Resolvability theory for the multiple-access channel. Trans.
Inf. Theory, 44(2):472–487, Mar 1998.
[39] A. Thangaraj. Coding for wiretap channels: Channel resolvability and
semantic security. In 2014 IEEE Information Theory Workshop (ITW
2014), pages 232–236, Nov 2014.
[40] T. van Erven and P. Harremoës. Rényi divergence and Kullback-Leibler
divergence. Trans. Inf. Theory, 60(7):3797–3820, July 2014.
[41] S. Watanabe and M. Hayashi. Strong converse and second-order
asymptotics of channel resolvability. In ISIT, pages 1882–1886. IEEE,
2014.
[42] M. Wiese and H. Boche. An achievable region for the wiretap multipleaccess channel with common message. In ISIT, pages 249–253. IEEE,
2012.
[43] A. Wyner. The common information of two dependent random variables.
Trans. Inf. Theory, 21(2):163–179, 1975.
[44] A. D. Wyner. The wire-tap channel. Bell Labs Technical Journal,
54(8):1355–1387, 1975.
[45] M. H. Yassaee and M. R. Aref. Multiple access wiretap channels with
strong secrecy. In ITW, pages 1–5. IEEE, Aug 2010.

16

A PPENDIX

P̃ =

X
Cˆ2



PC2 (C2 = Cˆ2 )PC1 ,C2 



exp(nR2 )

X

exp(−nR2 )

m2 =1

qZ n |Y n (z n |C2 (m2 ))
n
1(C2 (m2 ),zn )∈T2,ε
qZ n (z n )


(78)

Ptyp,1 (C2 (m2 ), z n ) > 1 + 3 exp(−nβ) | C1 ∈ Czn , C2 = Cˆ2 

exp(nR2 )

qZ n |Y n (z n |C2 (m2 ))
n
1(C2 (m2 ),zn )∈T2,ε
qZ n (z n )
m2 =1
Cˆ2

1 + 3 exp(−nβ)
>
| C1 ∈ Czn , C2 = Cˆ2 
1 + exp(−nβ)


exp(nR2 )
X
qZ n |Y n (z n |C2 (m2 ))
n > 1 + exp(−nβ)
1(C2 (m2 ),zn )∈T2,ε
≤ PC2 
exp(−nR2 )
qZ n (z n )
m2 =1


1
≤ exp − exp(−n(I(Y ; Z) + ε + 2β − R2 ))
3
≤

X

PC2 (C2 = Cˆ2 )PC1 ,C2 

X

exp(−nR2 )

(79)

(80)
(81)

(78) follows from the law of total probability, (79) is a consequence of the condition C1 ∈ Czn , (80) results from an application
of the law of total probability and the assumption that n is sufficiently large such that exp(−nβ) ≤ 1. Finally, (81) follows
from Lemma 3 with A = Y , C = Z, B a deterministic random variable with only one possible realization and δ = exp(−nβ).


PC1 ,C2 kpZ n |C1 ,C2 − qZ n kTV > 7 exp(−nβ)

≤PC1 ,C2 (Patyp,1 > 2 exp(−nβ)) + PC1 ,C2 (Patyp,2 > 2 exp(−nβ))
X
+
/ Czn ) + PC1 ,C2 (Ptyp (z n ) > 1 + 3 exp(−nβ) | C1 ∈ Czn ))
(PC1 (C1 ∈

(82)
(83)

z n ∈Z n



1
≤2 exp(−2 exp(n(min(R1 , R2 ) − 2β))) + |Z|n |Y|n exp − exp(−n(I(X; Z|Y ) + ε + 2β − R1 ))
3


1
+ |Z|n exp − exp(−n(I(Y ; Z) + ε + 2β − R2 ))
3

(84)

(83) follows from (9) and the union bound. (84) is a substitution of (17), (18), (19) and (81).




3
1
+√
PC1 ,C2 kpZ n |C1 ,C2 − qZ n kTV > (µ2 + µ1 ) 1 + √
n
n






1
1
+ PC1 ,C2 Patyp,2 > µ2 1 + √
≤PC1 ,C2 Patyp,1 > µ1 1 + √
n
n



X
3
/ Czn ) + PC1 ,C2 Ptyp,1 (C2 (m2 ), z n ) > 1 + √ | C1 ∈ Czn
+
PC1 (C1 ∈
n
z n ∈Z n




2µ2
2µ2
≤ exp − 1 exp(n min(R1 , R2 )) + exp − 2 exp(n min(R1 , R2 ))
n
n




1
1
n
n
n
+ |Y| |Z| exp − exp(−n(I(X; Z|Y ) + ε1 − R1 )) + |Z| exp −
exp(−n(I(Y ; Z) + ε2 − R2 ))
3n
3n




1 c−d−1
2 min(µ21 , µ22 )
exp(n min(R1 , R2 )) + 2 exp n(log|Z| + log|Y|) − n
≤ 2 exp −
n
3

(85)

(86)

(87)

(88)

(86) results from (9) and the union bound, (87) follows by substituting (25), (26) and (27). (88) follows by substituting (22),
(23) and (24), as well as elementary operations.

17

nI(X̂, Ŷ ; Ẑ|V̂ ) − I(X̃ n , Ỹ n ; Z̃ n ) =

n X X X
X

k=1 x∈X y∈Y z∈Z

−
=

pX̃k ,Ỹk ,Z̃k (x, y, z) log

X

X

X

n
X

H(Z̃k )

X

pX̃ n ,Ỹ n ,Z̃ n (xn , y n , z n ) log qZ|X,Y (zk |xk , yk ) − H(Z̃ n ) (90)

H(Z̃k ) − H(Z̃ n )

k=1
n
X

(89)

k=1

k=1 xn ∈X n y n ∈Y n z n ∈Z n

n
X

qZ n |X n ,Y n (z n |xn , y n )
pZ̃ n (z n )

pX̃k ,Ỹk ,Z̃k (x, y, z) log qZ|X,Y (z|x, y) +

k=1 x∈X y∈Y z∈Z
n
X
X X

=

pX̃ n ,Ỹ n ,Z̃ n (xn , y n , z n ) log

xn ∈X n y n ∈Y n z n ∈Z n

n X X X
X

−

qZ|X,Y (z|x, y)
pZ̃k (z)

(91)


 

1
1
δ
δ
≤
H(Zk ) − H(Z ) + n − δ log
+ − δ log
2
2|Z|
2
2|Z n |
k=1


δ
≤ n −δ log
2|Z|
n

(92)
(93)

(92) follows by (31), (36) and Lemma 1.
max
X

Π,PM

=



max P
X

n →Π
f :Ztap

(m1 ,m2 )∈M

−

n
M,Ztap

n
z n ∈Ztap

X

X

X


− max PM (M ∈ g)

X

n
z n ∈Ztap

n
n |C (m ,·),C (m ,·) (z )1(m ,m )∈f (z n )
pZtap
1
1
2
2
1
2

n
z n ∈Ztap

(m1 ,m2 ),(m̃1 ,m̃2 )∈M

−

(95)

n
n |C (m̃ ,·),C (m̃ ,·) (z ) · 1(m̃ ,m̃ )∈g
pM (m̃1 , m̃2 )pZtap
1
1
2
2
1
2

pM (m1 , m2 )pM (m̃1 , m̃2 )
X

(94)

g∈Π

n
n |C (m ,·),C (m ,·) (z ) · 1(m ,m )∈f (z n )
pM (m1 , m2 )pZtap
1
1
2
2
1
2

n
(m̃1 ,m̃2 )∈M z n ∈Ztap

=

(M ∈

n
f (Ztap
))

n

!

(96)

n |C (m̃ ,·),C (m̃ ,·) (z ) · (1(m ,m )∈f (z n ) + 1(m ,m )∈f
n − 1(m̃ ,m̃ )∈g
pZtap
)
1
1
2
2
1
2
1
2 / (z )
1
2 /

= P1 + P2 − P3

(97)

with the definitions
X

P1 :=

pM (m1 , m2 )pM (m̃1 , m̃2 )

n
z n ∈Ztap

(m1 ,m2 ),(m̃1 ,m̃2 )∈M

P2 :=

X

(m̃1 ,m̃2 )∈M

P3 :=

X

pM (m̃1 , m̃2 ) ·

(m1 ,m2 ),(m̃1 ,m̃2 )∈M

X 

X


n
n
n |C (m ,·),C (m ,·) (z ) − pZ n |C (m̃ ,·),C (m̃ ,·) (z )
pZtap
1
1
2
2
1
2
2
tap 1
n

n |C (m̃ ,·),C (m̃ ,·) (z )1(m̃ ,m̃ )∈g
pZtap
1
1
2
2
1
2 /

(98)

·1(m1 ,m2 )∈f (zn )
(99)

n
z n ∈Ztap

pM (m1 , m2 )pM (m̃1 , m̃2 )

X

n
z n ∈Ztap

n
n |C (m̃ ,·),C (m̃ ,·) (z )1(m ,m )∈f
n .
pZtap
1
1
2
2
1
2 / (z )

(100)

