# Finite-Length Analysis of Wiretap Codes using Universal Hash Functions

Kagan Akcay
Electrical Engineering and Computer Science Department, Technische Universität
Berlin, 10587 Berlin, Germany
<EMAIL_ADDRESS>
###### Abstract

This paper investigates the relation between the second-order coding rate,
where the second-order turns out to be strictly larger than $\sqrt{n}$, and
the mutual information as the leaked information for a fixed error probability
by using wiretap codes constructed by universal2 hash functions. We first
generalize the upper bound on $\epsilon$-smooth max information in [1] and use
it in our analysis where we adopt the method in [2], which uses universal
hashing for compressing a source and making it secure from another correlated
source, and apply it to the wiretap channel. We prove first- and second-order
achievability results by assuming that the conjecture we state holds true.

##  I Introduction

The study of secure communication over a noisy channel with an eavesdropper,
which is called a wiretap channel, began with Wyner [3] and continued with
Csiszár and Körner [4]. It was shown that if the transmission rate is below
the secrecy capacity, the error probability and the information leakage can be
made arbitrarily small as long as the number of channel usage is sufficiently
large. Whereas the studies above analyze the wiretap channel in the asymptotic
regime, the analysis in the finite length regime is also studied in several
papers such as [5, 6, 7], where [5, 6] adopt the leaked information criterion
based on the variational distance and [7] on the mutual information. This
paper adopts the leaked information criterion based on mutual information.

The main purpose of this paper is to find the relation between the second-
order coding rate and the leaked information for a fixed error probability.
Since the mutual information can be unbounded, we don’t fix the leaked
information together with the error probability and analyze the asymptotic
expansion as done in [5] where the variational distance as the leaked
information is bounded. We fix only the error probability and investigate the
first- and second-order asymptotics of the leaked information by adopting the
method in [2]. [2] proves first- and second-order results for the mutual
information between a compressed version of a source $A^{n}$, where universal
hashing is used for compression, and another correlated source $E^{n}$, where
$(A^{n},E^{n})$ is an independent identical distributed (i.i.d) sequence. We
follow the achievability proof method of [2] and apply it to the wiretap
channel by proving an upper bound on $\epsilon$-max smooth information.

In Section III, we define the wiretap channel and the secrecy codes. In
Section IV, we prove new upper bounds on the size of the typical sets and the
channel probability of the elements in a typical set to be used in the upper
bound on $\epsilon$-max information in Section V. In Section VI, we prove an
upper bound on the mutual information between any two random variables taking
values on finite sets by $\epsilon$-max information and an error term by
proving that the Rényi divergence of order $2$ is upper bounded by max
information. In Section VII, we state the definition of a universal2 hash
function and define a new kind of a universal2 hash function, which we call a
c-universal2 hash function, with the extra condition that the cardinality of
the image of its right inverse does not depend on its argument as in [7]. We
also state a lemma from [2] which shows a relation between the Rényi
divergence between the compressed version of $A$ and $E$, and the conditional
Rényi entropy between $A$ and $E$, where $(A,E)$ is a correlated source, to be
used for our finite-length achievability analysis of the wiretap channel in
the next section. In Section VIII, we prove first- and second-order
achievability results for fixed error probability by constructing wiretap
codes using c-universal2 hash functions and assuming that certain conjecture
holds true. The second-order turns out to be strictly larger than $\sqrt{n}$,
whereas in [5, 6, 2] it is exactly $\sqrt{n}$.

##  II Preliminaries

######  Definition 1.

[2] Let A be a finite set where $P$ and $Q$ are two distributions on A. The
Rényi divergence of order $1+s$ is given by

$D_{1+s}(P|{}|{}Q):=\frac{1}{s}\log{}\sum_{a\in{\textbf{A}}}P(a)^{1+s}Q(a)^{-s}$

for every $s>0$. It is easy to show that
$D_{1}(P|{}|{}Q):=\lim_{s\rightarrow{0}}D_{1+s}(P|{}|{}Q)=D(P|{}|{}Q)$.

######  Definition 2.

[2] Let A and E be two sets with finite cardinality, let $(A,E)$ be a pair of
joitnly distributed random variables on $\textbf{A}\times\textbf{E}$. The
conditional Rényi entropy of order $1+s$ of $A$ given $E$ is given by

$H_{1+s}(A|{}E):=-\frac{1}{s}\log{}\sum_{e}P_{E}(e)\sum_{a}P_{A|{}E}(a|{}e)^{1+s}$

for $s>0$. It is easy to show that
$H_{1}(A|{}E):=\lim_{s\rightarrow{0}}H_{1+s}(A|{}E)=H(A|{}E)$.

######  Definition 3.

Let X and Y be finite sets, where $P$ is a distribution on X and
$W:\textbf{X}\rightarrow{\textbf{Y}}$ is a stochastic matrix. The mutual
information is then given by

$I(P;W):=H(PW)-H(W|{}P)$

where $PW(y)=\sum_{x\in{\textbf{X}}}P(x)W(y|{}x)$ for all $y\in{\textbf{Y}}$.
If $(X,Y)$ are jointly distributed on $\textbf{X}\times\textbf{Y}$ and
$P_{Y|{}X}=W$, we write $I(X\wedge{}Y)$ for $I(P_{X};W)$.

##  III Channel Model

The wiretap channel was first introduced by Wyner in [3]. In the wiretap
channel, we have a sender, a legitimate receiver, and an eavesdropper. The
sender aims to transmit a message reliably to the legitimate receiver while
keeping it secret from the eavesdropper. In the discrete memoryless degraded
wiretap channel (DM-DWTC), we have
$V^{n}:\textbf{X}^{n}\rightarrow{\textbf{Y}^{n}}$ and
$W^{n}:\textbf{Y}^{n}\rightarrow{\textbf{E}^{n}}$ where $V$ and $W$ are
discrete memoryless channels (DMCs), X, Y and E are finite sets and $n$ is the
number of the channel usage. $V$ corresponds to the channel from the sender to
the legitimate receiver, whereas $W$ corresponds to the degraded channel to
the eavesdropper. A secrecy code $C_{n}$ for a DM-WTC consists of

  * •

a message $M$ which distributed on a message set
$\textbf{M}=\\{1,...,|{}\textbf{M}|{}\\}$,

  * •

a randomized encoder $e:\textbf{M}\rightarrow{\textbf{X}^{n}}$ which generates
a codeword $x^{n}$ according to a probability distribution $P_{X^{n}|{}M=m}$,

  * •

a decoder $d:\textbf{Y}^{n}\rightarrow{\textbf{M}}$ which maps each channel
observation $y^{n}$ to an estimate $\hat{m}\in{\textbf{M}}$.

We require that $M$ is uniformly distributed on M and the encoder and the
decoder of the legitimate receiver satisfy the average error probability
constraint $Pr(d(Y^{n})\neq{}M)\leq{}\varepsilon$. We assume that the channel
statistics and properties of the code $C_{n}$ are known to all parties.
However, the eavesdropper cannot access realizations $x^{n}$ and $y^{n}$. We
use mutual information $I(M\wedge{}E^{n})$ as the secrecy metric. We fix
$\varepsilon$ and let the message set
$|{}\textbf{M}|{}=e^{nR+(\sqrt{n})^{1+\gamma}L}$ where $0<\gamma<1$ and
$\gamma$ is fixed and analyse the asymptotic behaviour of $I(M\wedge{}E^{n})$
with respect to $\varepsilon$, $R$ and $L$. The reason why $\gamma>0$ and not
exactly $0$ as in [5, 6, 2] will be clear in Section VIII.

##  IV Types and Typicality

######  Definition 4.

[8, Definition 2.1] The type of a sequence $x^{n}\in{\textbf{X}^{n}}$ is the
distribution $P_{x^{n}}$ on X defined by

$P_{x^{n}}(a):=\frac{1}{n}N(a|{}x^{n}),\;\;\forall\;a\in\textbf{X}$

where $N(a|x^{n})$ denotes the multiplicity of symbol $a$ in $x^{n}$. For any
distribution $P$ on X, the set of sequences of type $P$ in $\textbf{X}^{n}$ is
denoted by $T^{n}_{P}$.

######  Definition 5.

[8, Definition 2.8] For any distribution $P$ on X, a sequence
$x^{n}\in{\textbf{X}^{n}}$ is called $P$-typical with constant $\delta$ if

$|{}N(a|{}x^{n})/n-P(a)|{}\leq{\delta}$

for every $a\in{\textbf{X}}$ and, in addition, no $a\in{\textbf{X}}$ with
$P(a)=0$ occurs in $x^{n}$. The set of such sequences will be denoted by
$T^{n}_{[P]_{\delta}}$. If $X$ is a random variable with values in X, we refer
to $P_{X}$-typical sequences as $X$-typical, and write $T^{n}_{[X]_{\delta}}$
for $T^{n}_{[P_{X}]_{\delta}}$.

######  Definition 6.

[8, Definition 2.9] For a stochastic matrix
$W:\textbf{X}\rightarrow{\textbf{Y}}$, a sequence $y^{n}\in{\textbf{Y}^{n}}$
is $W$-typical under the condition $x^{n}\in{\textbf{X}^{n}}$ with constant
$\delta$ if

$\left|{}\frac{1}{n}N(a,b|{}x^{n},y^{n})-\frac{1}{n}N(a|{}x^{n})W(b|{}a)\right|{}\leq{\delta}$

for every $a\in{\textbf{X}}$, $b\in{\textbf{Y}}$, and, in addition,
$N(a,b|{}x^{n},y^{n})=0$ whenever $W(b|{}a)=0$. The set of such sequences
$y^{n}$ will be denoted by $T^{n}_{[W]_{\delta}}(x^{n})$. If $X$ and $Y$ are
random variables with values in X resp. Y and $P_{Y|{}X}=W$, then we speak of
$Y|{}X$-typical sequences and write $T^{n}_{[Y|{}X]_{\delta}}(x^{n})$ for
$T^{n}_{[W]_{\delta}}(x^{n})$.

######  Lemma 1.

[8, Lemma 2.2] The number of different types of sequences in $\textbf{X}^{n}$
is less than $(n+1)^{|{}\textbf{X}|{}}$.

######  Lemma 2.

[8, Lemma 2.10] If $x^{n}\in{T^{n}_{[X]_{\delta}}}$ and
$y^{n}\in{T^{n}_{[Y|{}X]_{\delta^{\prime}}}(x^{n})}$ then
$y^{n}\in{T^{n}_{[Y]_{\delta^{\prime\prime}}}}$ for
$\delta^{\prime\prime}:=(\delta+\delta^{\prime})|{}\textbf{X}|{}$.

######  Lemma 3.

[8, Lemma 2.12] For every stochastic matrix
$W:\textbf{X}\rightarrow{\textbf{Y}}$

$W^{n}(T^{n}_{[W]\delta}(x^{n})|{}x^{n})\geq{1-2|{}\textbf{X}|{}|{}\textbf{Y}|{}e^{-2n\delta^{2}}}$

for every $\delta>0$.

######  Lemma 4.

For every distribution $P$ on X

$\log{}|{}T^{n}_{[P]_{\delta}}|{}\leq{}nH(P)-n\delta|{}\textbf{X}|{}\log{\min_{a\in{supp(P(a))}}P(a)}$

for every $\delta>0$.

###### Proof.

Let $x^{n}\in{T^{n}_{[P]_{\delta}}}$. Then

$\displaystyle P^{n}(x^{n})$
$\displaystyle=\prod_{a\in{supp(P(a))}}P(a)^{N(a|{}x^{n})}$
$\displaystyle\geq{\prod_{a\in{supp(P(a))}}P(a)^{n(\delta+P(a))}}$
$\displaystyle=2^{\sum_{a\in{supp(P(a))}}n(\delta+P(a))\log{P(a)}}$
$\displaystyle\geq{2^{-nH(P)+n\delta|{}\textbf{X}|{}\log{\min_{a\in{supp(P(a))}}P(a)}}}.$

Since $\sum_{x^{n}\in{T^{n}_{[P]_{\delta}}}}P^{n}(x^{n})\leq{}1$,
$|{}T^{n}_{[P]_{\delta}}|{}\min_{x^{n}\in{T^{n}_{[P]_{\delta}}}}P^{n}(x^{n})\leq
1$ so that

$\log{}|{}T^{n}_{[P]_{\delta}}|{}\leq{}nH(P)-n\delta|{}\textbf{X}|{}\log{\min_{a\in{supp(P(a))}}P(a)}.$

∎

######  Lemma 5.

Let $W:\textbf{X}\rightarrow{\textbf{Y}}$ be a stochastic matrix,
$x^{n}\in{\textbf{X}^{n}}$ and $\delta>0$. Then for all
$y^{n}\in{T^{n}_{[W]_{\delta}}(x^{n})}$, it holds that

$\log{W^{n}(y^{n}|{}x^{n})}\leq{-nH(W|{}P)+n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Y}|{}},$

where $P$ is the type of $x^{n}$ and
$W_{c}=-\log{\min_{(a,b)\in{supp(W(b|{}a))}}{W(b|{}a)}}$.

###### Proof.

Let $P$ be the type of $x^{n}$ and $y^{n}\in{T^{n}_{[W]_{\delta}}(x^{n})}$.
Then

$\displaystyle\log{W^{n}(y^{n}|{}x^{n})}=\log{\prod_{(a,b)\in{supp(W(b|{}a))}}W(b|{}a)^{N(a,b|{}x^{n},y^{n})}}$
$\displaystyle\leq{\log{\prod_{(a,b)\in{supp(W(b|{}a))}}W(b|{}a)^{(-n\delta+N(a|{}x^{n})W(b|{}a))}}}$
$\displaystyle=\log{2^{\sum_{(a,b)\in{supp(W(b|{}a))}}(-n\delta+nP(a)W(b|{}a))\log{W(b|{}a)}}}$
$\displaystyle\leq{-nH(W|{}P)-n\delta|{}\textbf{X}|{}|{}\textbf{Y}|{}\log{\min_{(a,b)\in{supp(W(b|{}a))}}{W(b|{}a)}}}.$

∎

##  V Max-Information

######  Definition 7.

[1, Section 3-B] Let $W:\textbf{X}\rightarrow{\textbf{Y}}$ be a subnormalized
channel where X and Y are finite sets and $\sum_{y}W(y|{}x)\leq{}1$ for every
$x\in{\textbf{X}}$. The max-information of $W$ is given by

$I_{max}(W):=\log{\sum_{y}\max_{x}w(y|{}x)}.$

######  Definition 8.

[1, Section 3-B] Let $W:\textbf{X}\rightarrow{\textbf{Y}}$ be a channel, where
X and Y are finite sets. For a subset T of $\textbf{X}\times{}\textbf{Y}$,
denote by $W_{\textbf{T}}$ the subnormalized channel where

$W_{\textbf{T}}(y|{}x)=W(y|{}x)\mathbbm{1}{((x,y)\in{\textbf{T}})}.$

The $\epsilon$-smooth max-information of $W$ is given by

$I_{max}^{\epsilon}(W):=\inf_{\textbf{T}}I_{max}(W_{\textbf{T}})$

over all sets $\textbf{T}\subset{\textbf{X}\times{}\textbf{Y}}$ such that

$W(\\{{}y:(x,y)\in{\textbf{T}}\\}|{}x)\geq{}1-\epsilon$

for all $x\in{\textbf{X}}$.

######  Theorem 1.

Let $W:\textbf{X}\rightarrow{\textbf{Z}}$ be a DMC with finite input and
output alphabets X and Z, respectively, and
$e_{0}:\textbf{V}\rightarrow\textbf{X}^{n}$ be an encoder. Then, denoting
$\epsilon_{n}=2|{}\textbf{X}|{}|{}\textbf{Z}|{}e^{-2n\delta^{2}}$, for the
combined channel $W_{e_{0}}=W^{n}\circ{}e_{0}$ it holds that

$\displaystyle I_{max}^{\epsilon_{n}}(W_{e_{0}})\leq{}$ $\displaystyle
n\max_{P_{X}}I(X\wedge{}Z)+2n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}$
$\displaystyle+|{}\textbf{X}|{}\log{(n+1)},$

for every $\delta>0$ where
$W_{c}=-\log{\min_{(a,b)\in{supp(W(b|{}a))}}{W(b|{}a)}}$.

###### Proof.

Let $P$ be a type in $\textbf{X}^{n}$ as in Definition 4. Denote by
$T^{n}_{(W)_{\delta}}$ the set of sequences $(x^{n},z^{n})$ such that $z^{n}$
is $W$-typical given $x^{n}$ with $\delta$ as in Definition 6, by
$T^{n}_{(P,W)_{\delta}}$ the set of sequences
$(x^{n},z^{n})\in{T^{n}_{(W)_{\delta}}}$ such that $x^{n}$ has type $P$, and
by $\Phi[T^{n}_{(P,W)_{\delta}}]$ the projection of $T^{n}_{(P,W)_{\delta}}$
on $\textbf{Z}^{n}$. Then by Lemma 5 for all
$(x^{n},z^{n})\in{T^{n}_{(P,W)_{\delta}}}$

$\log{W^{n}(z^{n}|{x^{n}})}\leq{-nH(W|{}P)+n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}}.$
(1)

By Lemma 2
$\Phi[T^{n}_{(P,W)_{\delta}}]\subset{T^{n}_{[PW]_{\delta|{}\textbf{X}|{}}}}$
where $PW$ denotes the output distribution for channel $W$ when the input
distribution is $P$. Then by Lemma 4
$\log{|{\Phi[T^{n}_{(P,W)_{\delta}}]}}|{}\leq{}nH(PW)-n\delta|{}\textbf{X}|{}|{}\textbf{Z}|{}\log{\min_{b\in{supp(PW(b))}}PW(b)}.$
Since $PW(b)=\sum_{a}P(a)W(b|{}a)\geq{}\min_{a}W(b|{}a)$,

$\log{|{\Phi[T^{n}_{(P,W)_{\delta}}]}}|{}\leq{}nH(PW)+n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}.$
(2)

Furthermore by Lemma 3 for every $v\in{\textbf{V}}$

$\sum_{z^{n}:(e_{0}(v),z^{n})\in{T^{n}_{(W)_{\delta}}}}W^{n}(z^{n}|{e_{0}(v)})\geq{1-\epsilon_{n}},$

where $\epsilon_{n}=2|{}\textbf{X}|{}|{}\textbf{Z}|{}e^{-2n\delta^{2}}$.
First, we assume that each codeword $e_{0}(v)$ is of type $P$ and $P$ is
fixed. For simplicity, we omit the $\delta$ in $T^{n}_{(P,W)_{\delta}}$. Then
for the subnormalized channel $W_{e_{0},T^{n}_{(P,W)}}$

$\displaystyle
I_{max}^{\epsilon_{n}}(W_{e_{0}})\leq{I_{max}(W_{e_{0},T^{n}_{(P,W)}})}$
$\displaystyle=\log{\sum_{z^{n}}\max_{v}W^{n}(z^{n}|{e_{0}(v))}\mathbbm{1}{((e_{0}(v),z^{n})\in{T^{n}_{(P,W)}})}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq{}}}-nH(W|{P})+\log{\sum_{z^{n}}\max_{v}\mathbbm{1}{((e_{0}(v),z^{n})\in{T^{n}_{(P,W)}})}}$
$\displaystyle+n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq{}}}-nH(W|{P})+\log{|{\Phi[T^{n}_{(P,W)}]}}|{}+n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq{}}}-nH(W|{}P)+nH(PW)+2n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}$
$\displaystyle=nI(P;W)+2n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{},$ (3)

where $(a)$ comes from (1), $(b)$ uses the fact that
$(e_{0}(v),z^{n})\in{T^{n}_{(P,W)}}$ implies $z^{n}\in{\Phi[T^{n}_{(P,W)}]}$
so that
$\sum_{z^{n}}\max_{v}\mathbbm{1}{((e_{0}(v),z^{n})\in{T^{n}_{(P,W)}})}\leq{}\sum_{z^{n}}\mathbbm{1}{(z^{n}\in{\Phi[T^{n}_{(P,W)}]})}=|{}\Phi[T^{n}_{(P,W)}]|{}$,
and $(c)$ comes from (2). This completes the proof where $e_{0}(v)$ is of a
fixed type $P$. Now, we will show proof of an arbitrary code. Let us denote by
$C_{P}$ the set of codewords $e_{0}(v)$ of type $P$. Then, as before,

$\displaystyle
I_{max}^{\epsilon_{n}}(W_{e_{0}})\leq{I_{max}(W_{e_{0},T^{n}_{(W)}})}$
$\displaystyle=\log{\sum_{z^{n}}\max_{v}W^{n}(z^{n}|{e_{0}(v))}\mathbbm{1}{((e_{0}(v),z^{n})\in{T^{n}_{(W)}})}}$
$\displaystyle\leq{\log{\sum_{P}\sum_{z^{n}}\max_{x^{n}\in{C_{P}}}W^{n}(z^{n}|{x^{n})}\mathbbm{1}{((x^{n},z^{n})\in{T^{n}_{(W)}})}}}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq{}}}\log{\max_{P}\sum_{z^{n}}\max_{x^{n}\in{C_{P}}}W^{n}(z^{n}|{x^{n})}\mathbbm{1}{((x^{n},z^{n})\in{T^{n}_{(W)}})}}$
$\displaystyle+|{}\textbf{X}|{}\log{(n+1)}$
$\displaystyle\leq{n\max_{P_{X}}I(P_{X};W)+2n\delta{}W_{c}|{}\textbf{X}|{}|{}\textbf{Z}|{}+|{}\textbf{X}|{}\log{(n+1)}},$

where $(d)$ comes from Lemma 1. Notice that Theorem 1 is a generalization of
[1, Lemma 5]. ∎

######  Remark 1.

The typicality bounds in [8] can also be used in the proof of Theorem 1.
Instead of Lemma 4, [8, Lemma 2.13] can be used for an upper bound on the size
of a typical set. Another upper bound on the channel probability can be
derived by using [8, Lemma 2.6] and the arguments in the proof of [8, Lemma
2.13] where the second term in the upper bound then becomes
$-n|{}\textbf{X}|{}|{}\textbf{Y}|{}\delta\log{\delta}$. Then

$\displaystyle
I_{max}^{\epsilon_{n}}(W_{e_{0}})\leq{n\max_{P_{X}}I(X\wedge{}Z)-n|{}\textbf{X}|{}|{}\textbf{Z}|{}\delta\log{}(\delta^{2}|{}\textbf{X}|{})}$
$\displaystyle+(|{}\textbf{X}|{}+|{}\textbf{Z}|{})\log{(n+1)}$

for every $0<\delta\leq{\frac{1}{2|{}\textbf{X}|{}|{}\textbf{Z}|{}}}$. We
won’t use this upper bound in our achievability analysis, which will be clear
in Section VIII.

##  VI Divergence Bounds

######  Lemma 6.

Let $W:\textbf{A}\rightarrow{\textbf{E}}$ be a subnormalized channel, where A
and E are finite sets. Let $A$ be a random variable uniformly distributed on A
and $P_{E|{}A}=W$. Then

$D_{2}(P_{AE}|{}|{}P_{A}\times{}P_{E})\leq{}I_{max}(W).$

###### Proof.

$\displaystyle D_{2}(P_{AE}|{}|{}P_{A}\times{}P_{E})$
$\displaystyle=\log\sum_{a,e}\frac{(P_{AE})^{2}}{P_{A}P_{E}}$
$\displaystyle=\log\sum_{a,e}\frac{P_{A}^{2}(a)W^{2}(e|{}a)}{P_{A}(a)\sum_{a^{\prime}}P_{A}(a^{\prime})W(e|{}a^{\prime})}$
$\displaystyle=\log\sum_{e}\frac{\sum_{a}W^{2}(e|{}a)}{\sum_{a^{\prime}}W(e|{}a^{\prime})}$
$\displaystyle{\leq{}}\log\sum_{e}\max_{a}W(e|{}a)=I_{max}(W)$

∎

######  Lemma 7.

Let $W:\textbf{A}\rightarrow{\textbf{E}}$ be a channel, where A and E are
finite sets. Let $A$ be a random variable uniformly distributed on A and
$P_{E|{}A}=W$. Then

$D(P_{AE}|{}|{}P_{A}\times{}P_{E})\leq{}I^{\epsilon}_{max}(W)-(1-\epsilon)\log(1-\epsilon)+\epsilon\log|{}\textbf{A}|{}$

for every $\epsilon<1-e^{-1}$.

###### Proof.

Let T be a subset of $\textbf{A}\times{}\textbf{E}$ satisfying
$W(\\{{}e:(a,e)\in{\textbf{T}}\\}|{}a)\geq{}1-\epsilon$ for all
$a\in{\textbf{A}}$. Then
$D(P_{AE}|{}|{}P_{A}\times{}P_{E})=\sum_{a,e}P_{AE}\log\frac{P_{AE}}{P_{A}P_{E}}=\sum_{(a,e)\in{\textbf{T}}}P_{AE}\log\frac{P_{AE}}{P_{A}P_{E}}+\sum_{(a,e)\in{\textbf{T}^{c}}}P_{AE}\log\frac{P_{AE}}{P_{A}P_{E}}.$
First notice that

$\displaystyle\log\frac{P_{AE}}{P_{A}P_{E}}$
$\displaystyle=\log\frac{P_{A}(a)W(e|{}a)}{P_{A}(a)\sum_{a^{\prime}}P_{A}(a^{\prime})W(e|{}a^{\prime})}$
$\displaystyle=\log\frac{|{}\textbf{A}|{}W(e|{}a)}{\sum_{a^{\prime}}W(e|{}a^{\prime})}$
$\displaystyle\leq{}\log\frac{|{}\textbf{A}|{}W(e|{}a)}{W(e|{}a)}=\log|{}\textbf{A}|{}.$

Then
$\sum_{(a,e)\in{\textbf{T}^{c}}}P_{AE}\log\frac{P_{AE}}{P_{A}P_{E}}\leq{}Pr((A,E)\in{\textbf{T}^{c}})\log|{}\textbf{A}|{}\leq\epsilon\log|{}\textbf{A}|{}.$
Also by [9, Lemma 12] if $\epsilon<1-e^{-1}$,
$\sum_{(a,e)\in{\textbf{T}}}P_{AE}\log\frac{P_{AE}}{P_{A}P_{E}}\leq\log{\sum_{(a,e)\in{\textbf{T}}}\frac{(P_{AE})^{2}}{P_{A}P_{E}}}-(1-\epsilon)\log(1-\epsilon)\leq{}I_{max}(W_{\textbf{T}})-(1-\epsilon)\log(1-\epsilon)$
where the last inequality comes from Lemma 6. So we have
$D(P_{AE}|{}|{}P_{A}\times{}P_{E})\leq{}I_{max}(W_{\textbf{T}})-(1-\epsilon)\log(1-\epsilon)+\epsilon\log|{}\textbf{A}|{}.$
Since this is true for every set T where
$W(\\{{}e:(a,e)\in{\textbf{T}}\\}|{}a)\geq{}1-\epsilon$ for all
$a\in{\textbf{A}}$, then it holds also that
$D(P_{AE}|{}|{}P_{A}\times{}P_{E})\leq{}I^{\epsilon}_{max}(W)-(1-\epsilon)\log(1-\epsilon)+\epsilon\log|{}\textbf{A}|{}.$
∎

##  VII Universal Hashing

######  Definition 9.

A random hash function $f_{X}$ is a stochastic map from A to
$\textbf{M}:=\\{1,...,M\\}$, where $X$ denotes a random variable describing
its stochastic behavior. A random hash function $f_{X}$ is called an
$\epsilon$-almost universal2 hash function if it satisfies the following
condition: For any distinct $a_{1}$, $a_{2}\in{A}$,

$Pr(f_{X}(a_{1})=f_{X}(a_{2}))\leq{}\frac{\epsilon}{M}.$

When $\epsilon=1$, we say that $f_{X}$ is a universal2 hash function [2]. Let
X be the set corresponding to $X$. For every $x\in{\textbf{X}}$,
$f_{x}^{-1}:\textbf{M}\rightarrow{\textbf{A}}$ is defined as follows:
$f_{x}^{-1}(m)$ attains values in the preimage $f_{x}^{-1}\\{{}m\\}$ with
uniform distribution. Notice that $f_{x}^{-1}$ is a right inverse, i.e.,
$f_{x}(f_{x}^{-1}(m))=m$. We will use universal2 hash functions with the
following extra condition as in [7]: For any $x\in{\textbf{X}}$, the
cardinality of $f_{x}^{-1}\\{{}m\\}$ does not depend on $m\in{\textbf{M}}$.
Notice that the cardinality of $f_{x}^{-1}\\{{}m\\}$ is
$\frac{|{}\textbf{A}|{}}{|{}\textbf{M}|{}}$ for every $m\in{\textbf{M}}$. We
call a universal2 hash function with this extra condition a c-universal2 hash
function.

######  Definition 10.

[2, Section 2-B] Let A and E be two sets with finite cardinality, let $A$ be a
random variable on A and $E$ be a random variable on E. Then

$\displaystyle C_{1+s}(A|{}E):$
$\displaystyle=D_{1+s}(P_{AE}|{}|{}P_{mix,A}\times{}P_{E})$
$\displaystyle=\log|{}\textbf{A}|{}-H_{1+s}(A|{}E)$

where $P_{mix,A}$ is the uniform distribution on A.

######  Lemma 8.

[2, Lemma 1] For an $\epsilon$-almost universal2 hash function
$f_{X}:\textbf{A}\rightarrow{\textbf{M}=\\{1,...,M\\}}$, we have for
$s\in[0,1]$,

$e^{sC_{1+s}(f_{X}(A)|{}EX)}\leq{}\epsilon^{s}+M^{s}e^{-sH_{1+s}(A|{}E)}.$

##  VIII Achievability Bounds on the Wiretap Channel

We use universal2 hash functions for constructing DM-DWTC codes as in [7, 1]
as follows: We have a wiretap encoder
$e:\textbf{M}\rightarrow{\textbf{X}^{n}}$ where $e(m)=e_{0}(f_{x}^{-1}(m))$, a
wiretap decoder $d:\textbf{Y}^{n}\rightarrow{\textbf{M}}$ where
$d(y^{n})=f_{x}(d_{0}(y^{n}))$, such that

  * •

$e_{0}:\textbf{A}\rightarrow{\textbf{X}^{n}}$ is a channel encoder,

  * •

$f_{x}^{-1}:\textbf{M}\rightarrow{\textbf{A}}$ where $f_{X}$ is a c-universal2
hash function,

  * •

$d_{0}:\textbf{Y}^{n}\rightarrow{\textbf{A}}$ is a channel decoder,

  * •

$f_{x}:\textbf{A}\rightarrow{\textbf{M}}$ where realization $x$ is known to
both receivers.

######  Conjecture 1.

Let $V:\textbf{X}\rightarrow{\textbf{Y}}$ and
$W:\textbf{Y}\rightarrow{\textbf{E}}$ be DMC. Then, for every sequence of
channel encoders $e_{0}[n]:\textbf{A}_{n}\rightarrow{\textbf{X}^{n}}$ which
achieves the capacity of $V$ as $n\rightarrow{\infty}$,

$|{}H(A_{n}|{}E^{n})-H_{1+\frac{1}{\sqrt{n}}}(A_{n}|{}E^{n})|{}\leq{}O(\sqrt{n}).$
(4)

######  Theorem 2.

Let $V:\textbf{X}\rightarrow{\textbf{Y}}$ and
$W:\textbf{Y}\rightarrow{\textbf{E}}$ be DMC. Let
$e_{0}[n]:\textbf{A}_{n}\rightarrow{\textbf{X}^{n}}$ be a sequence of channel
encoders which achieves the capacity of $V$ as $n\rightarrow{\infty}$, let
$M_{n}$ be a random variable uniformly distributed on message set
$\textbf{M}_{n}$ where $|{}\textbf{M}_{n}|{}$ divides $|{}\textbf{A}_{n}|{}$.
Assume Conjecture 1 holds. Then for every sequence of c-universal2 hash
functions $f_{X_{n}}$ where
$f_{x_{n}}^{-1}:\textbf{M}_{n}\rightarrow{\textbf{A}_{n}}$ and $X_{n}$ is
independent of $M_{n}$, if we let $|{}\textbf{M}_{n}|{}=e^{nR}$, then

$\limsup_{n\rightarrow{\infty}}\frac{1}{n}C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})\leq{}|{}R-(C_{V}-C_{U})|{}^{+}$

where $C_{V}$ is the capacity of the channel $V$ and $C_{U}$ is the capacity
of the channel $U:=W\circ{}V$. Also $C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$
goes to $0$ as $n\rightarrow{\infty}$ for $R<(C_{V}-C_{U})$. Let
$|{}\textbf{M}_{n}|{}=e^{n(C_{V}-C_{U})+(\sqrt{n})^{1+\gamma}L}$, then

$\limsup_{n\rightarrow{\infty}}\frac{1}{(\sqrt{n})^{1+\gamma}}C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})\leq{}|{}L+2U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}|{}^{+}$

for every $0<\gamma<1$. Also $C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$ goes to
$0$ as $n\rightarrow{\infty}$ for $L<-2U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}$.

###### Proof.

Let $f_{X_{n}}$ be a c-universal2 hash function where
$f_{x_{n}}^{-1}:\textbf{M}_{n}\rightarrow{\textbf{A}_{n}}$ and $X_{n}$ is
independent of $M_{n}$. Notice that since the messages are uniformly
distributed, $f_{x_{n}}^{-1}:\textbf{M}_{n}\rightarrow{\textbf{A}_{n}}$
defines a random variable $A_{n}$ which is uniformly distributed on
$\textbf{A}_{n}$. This implies that
$C_{1}(A_{n}|{}E^{n})=D(P_{A_{n}E^{n}}|{}|{}P_{A_{n}}\times{}P_{E{{}^{n}}})$.
By Theorem 1, for every $\delta>0$ it holds that

$I^{\epsilon_{n}}_{max}(U_{e_{0}})\leq{}nC_{U}+2n\delta{}U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}+|{}\textbf{X}|{}\log{(n+1)}$
(5)

where $\epsilon_{n}=2|{}\textbf{X}|{}|{}\textbf{E}|{}e^{-2n\delta^{2}}$. Also
by Lemma 7

$\displaystyle
C_{1}(A_{n}|{}E^{n})\leq{}I^{\epsilon}_{max}(U_{e_{0}})-(1-\epsilon)\log(1-\epsilon)$
$\displaystyle+\epsilon\log|{}\textbf{A}_{n}|{}$ (6)

for every $\epsilon<1-e^{-1}$. Then since $\log|{}\textbf{A}_{n}|{}=O(n)$, by
(5) and (VIII) we have
$C_{1}(A_{n}|{}E^{n})\leq{}nC_{U}+2n\delta{}U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}+O(\log{}n)$
for sufficiently large $n$ and $\delta>0$ fixed. Let us analyse the expression
$2n\delta{}U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}$. Since we don’t want this
expression to affect the first order coding rate, we let
$\delta(n)\rightarrow{0}$ as $n\rightarrow{\infty}$ under the constraint
$ne^{-2n\delta^{2}(n)}\leq{}O(\log{}n)$. Then we can choose $\delta(n)$ such
that $\delta(n)=(\sqrt{n})^{-1+\gamma}$ where $0<\gamma<1$ and $\gamma$ is
fixed. We also have from [10, 11] that
$\log|{}\textbf{A}_{n}|{}\geq{}nC_{V}+O(\sqrt{n}).$ So

$\displaystyle
H(A_{n}|{}E^{n})\geq{}n(C_{V}-C_{U})-2U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}(\sqrt{n})^{1+\gamma}$
$\displaystyle+O(\sqrt{n}).$ (7)

Let $|{}\textbf{M}_{n}|{}=e^{nR}$. By Lemma 8 we have for $\epsilon=1$ and
$s>0$

$\displaystyle\limsup_{n\rightarrow{\infty}}\frac{1}{n}C_{1+s}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$
$\displaystyle\leq{}\limsup_{n\rightarrow{\infty}}\frac{1}{n}(s^{-1}\log{}(1+M_{n}^{s}e^{-sH_{1+s}(A_{n}|{}E^{n})}))$
$\displaystyle=|{}\limsup_{n\rightarrow{\infty}}\frac{1}{n}(nR-
H_{1+s}(A_{n}|{}E^{n}))|{}^{+}.$ (8)

Let $s=\frac{1}{\sqrt{n}}$. Then by (4), (VIII), (VIII), and since
$D_{1+s}(P\|{}|{}Q)$ is monotonically increasing in $s\in[0,1]$ [2],

$\limsup_{n\rightarrow{\infty}}\frac{1}{n}C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})\leq{}|{}R-(C_{V}-C_{U})|{}^{+}.$
(9)

Without normalizing by $n$ we also have for $s=\frac{1}{\sqrt{n}}$

$\displaystyle C_{1+\frac{1}{\sqrt{n}}}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$
$\displaystyle\leq{}\sqrt{n}\log{}(1+e^{\frac{1}{\sqrt{n}}(nR-
H_{1+\frac{1}{\sqrt{n}}}(A_{n}|{}E^{n}))}).$ (10)

Then by (4), (VIII), (VIII), , and since $D_{1+s}(P\|{}|{}Q)$ is monotonically
increasing in $s\in[0,1]$ , for sufficiently large $n$

$\displaystyle C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$
$\displaystyle\leq{}\sqrt{n}\log{}(1+e^{\sqrt{n}(R-(C_{V}-C_{U}))+O((\sqrt{n})^{\gamma})}).$
(11)

This implies that $C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$ goes to $0$ as
$n\rightarrow{\infty}$ for $R<(C_{V}-C_{U})$. Let
$|{}\textbf{M}_{n}|{}=e^{n(C_{V}-C_{U})+(\sqrt{n})^{1+\gamma}L}$. Then
similarly as in (VIII)–(9),

$\displaystyle\limsup_{n\rightarrow{\infty}}\frac{1}{(\sqrt{n})^{1+\gamma}}C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})\leq{}|{}L+2U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}|{}^{+}.$

Also $C_{1}(f_{X_{n}}(A_{n})|{}E^{n}X_{n})$ goes to $0$ as
$n\rightarrow{\infty}$ for $L<-2U_{c}|{}\textbf{X}|{}|{}\textbf{E}|{}$
similarly as in (VIII)–(VIII). ∎

######  Remark 2.

In the proof of Theorem 2, we used $ne^{-2n\delta^{2}(n)}\leq{}O(\log{}n)$ as
a constraint for comparison with the case where $\delta>0$ is fixed. However,
there are two terms which depend on $\delta(n)$, namely $n\delta(n)$ and
$ne^{-2n\delta^{2}(n)}$. Depending on the choice of $\delta(n)$, the order of
the bigger term will be the second-order, and it is easy to see that the
second-order will be strictly larger than $\sqrt{n}$ independent of how
$\delta(n)$ is chosen. Notice that we also do not use the upper bound in
Remark 1 in Theorem 2 because it would imply a bigger second-order. There is
also no mention of the average error probability $\varepsilon$ since
$\varepsilon$ just affects the $\sqrt{n}$ order [10, 11]. Similarly, we could
have used maximal error probability, which wouldn’t have affected our results.

######  Remark 3.

Notice that the maximum first-order achievable rate in Theorem 2 is
$(C_{V}-C_{U})$, which is the weakly symmetric degraded wiretap capacity [12,
Proposition 3.2]. Furthermore, Theorem 2 can be generalized from a degraded
wiretap channel to a wiretap channel where the eavesdropper’s channel is less
capable than the legitimate receiver, i.e., $I(P_{X};V)\geq{}I(P_{X};W)$ for
every $P_{X}$ where $V:\textbf{X}\rightarrow{\textbf{Y}}$ and
$W:\textbf{X}\rightarrow{\textbf{E}}$ be DMC [12, Definition 3.12]. First, as
in the proof of [11, Theorem 4.2], choose a type $P$ which is closest in
variational distance to the capacity-achieving input distribution $P_{X}$,
where $C=I(P_{X};V)-I(P_{X};W)$ [12, Corollary 3.5]. Then use in the
generalized theorem the achievability bound for constant composition codes
from [11, Theorem 4.2] together with (V) which is for fixed type similarly as
in Theorem 2. Notice that the first-order rate $(I(P;V)-I(P;W))$ approaches
the capacity as $n\rightarrow{\infty}$, whereas the second-order rate doesn’t
change.

##  IX Conclusion

We have generalized the upper bound on $\epsilon$-max information and proved
an upper bound on the mutual information between any two random variables,
taking values on finite sets by $\epsilon$-max information and an error term.
We proved first- and second-order achievability results for fixed error
probability by constructing wiretap codes using c-universal2 hash functions
and assuming a conjecture holds true, where the second-order turns out to be
strictly larger than $\sqrt{n}$.

## References

  * [1] H. Tyagi and A. Vardy, “Universal hashing for information theoretic security,” _arXiv:1412.4958_ , 2016. [Online]. Available: https://arxiv.org/abs/1412.4958
  * [2] M. Hayashi and V. Y. F. Tan, “Equivocations, exponents, and second-order coding rates under various rényi information measures,” _IEEE Transactions on Information Theory_ , vol. 63, no. 2, pp. 975–1005, 2017.
  * [3] A. D. Wyner, “The wire-tap channel,” _The Bell System Technical Journal_ , vol. 54, no. 8, pp. 1355–1387, 1975.
  * [4] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” _IEEE Transactions on Information Theory_ , vol. 24, no. 3, pp. 339–348, 1978.
  * [5] W. Yang, R. F. Schaefer, and H. V. Poor, “Wiretap channels: Nonasymptotic fundamental limits,” _IEEE Transactions on Information Theory_ , vol. 65, no. 7, pp. 4069–4093, 2019.
  * [6] M. H. Yassaee, M. R. Aref, and A. Gohari, “Non-asymptotic output statistics of random binning and its applications,” in _2013 IEEE International Symposium on Information Theory_ , 2013, pp. 1849–1853.
  * [7] M. Hayashi, “Exponential decreasing rate of leaked information in universal random privacy amplification,” _IEEE Transactions on Information Theory_ , vol. 57, no. 6, pp. 3989–4001, 2011.
  * [8] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_ , 2nd ed. Cambridge University Press, 2011.
  * [9] M. Wiese and H. Boche, “Semantic security via seeded modular coding schemes and ramanujan graphs,” _IEEE Transactions on Information Theory_ , vol. 67, no. 1, pp. 52–80, 2021.
  * [10] Y. Polyanskiy, H. V. Poor, and S. Verdu, “Channel coding rate in the finite blocklength regime,” _IEEE Transactions on Information Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [11] V. Y. F. Tan, “Asymptotic estimates in information theory with non-vanishing error probabilities,” _Foundations and Trends® in Communications and Information Theory_ , vol. 11, no. 1-2, pp. 1–184, 2014. [Online]. Available: http://dx.doi.org/10.1561/0100000086
  * [12] M. Bloch and J. Barros, _Physical-Layer Security: From Information Theory to Security Engineering_. Cambridge University Press, 2011.