# Secret Key and Private Key Constructions for Simple Multiterminal Source
Models

Chunxuan Ye and Prakash Narayan Chunxuan Ye was with the Department of
Electrical and Computer Engineering, and the Institute for Systems Research,
University of Maryland, College Park, MD 20742. He is now with InterDigital
Communications, LLC, King of Prussia, PA 19406, USA. E-mail:
<EMAIL_ADDRESS>Narayan is with the Department of
Electrical and Computer Engineering, and the Institute for Systems Research,
University of Maryland, College Park, MD 20742, USA. E-mail:
<EMAIL_ADDRESS>work of C. Ye and P. Narayan was supported by the
National Science Foundation under Grants CCF0515124, CCF0635271 and
CCF0830697. The material in this paper was presented in part at the IEEE
International Symposium on Information Theory, Adelaide, Australia, Sept.
2005, and at the Information Theory and Applications Workshop, San Diego, CA,
Feb. 2006.

###### Abstract

We propose an approach for constructing secret and private keys based on the
long-known Slepian-Wolf code, due to Wyner, for correlated sources connected
by a virtual additive noise channel. Our work is motivated by results of
Csiszár and Narayan which highlight innate connections between secrecy
generation by multiple terminals that observe correlated source signals and
Slepian-Wolf near-lossless data compression. Explicit procedures for such
constructions and their substantiation are provided. The performance of low
density parity check channel codes in devising a new class of secret keys is
examined.

Index terms: Secret key construction, private key construction, secret key
capacity, private key capacity, Slepian-Wolf data compression, binary
symmetric channel, maximum likelihood decoding, LDPC codes.

##  I Introduction

The problem of secrecy generation by multiple terminals, based on their
observations of separate but correlated signals followed by public
communication among themselves, has been investigated by several authors
([23], [2], [7], among others). It has been shown that these terminals can
generate secrecy, namely “common randomness” which is kept secret from an
eavesdropper that is privy to said public communication and perhaps also to
additional “wiretapped” side information.

Our work is motivated by [8] which studies secrecy generation for
multiterminal “source models” with an arbitrary number of terminals, each of
which observes a distinct component of a discrete memoryless multiple source
(DMMS). Specifically, suppose that $d\geq 2$ terminals observe, respectively,
$n$ independent and identically distributed (i.i.d.) repetitions of finite-
valued random variables (rvs) $X_{1},\ldots,X_{d}$, denoted by ${\bf
X}_{1},\ldots,{\bf X}_{d}$, where ${\bf
X}_{i}=\left(X_{i1},\ldots,X_{in}\right),\ i=1,\ldots,d$. Thereupon,
unrestricted and noiseless public communication is allowed among the
terminals. All such communication is observed by all the terminals and by the
eavesdropper. The eavesdropper is assumed to be passive, i.e., unable to
tamper with the public communication of the terminals. In this framework, two
models considered in [8] dealing with a secret key (SK) and a private key (PK)
are pertinent to our work.

(i) Secret key: Suppose that all the terminals in $\\{1,\ldots,d\\}$ wish to
generate a SK, i.e., common randomness which is concealed from the
eavesdropper with access to their public communication and which is nearly
uniformly distributed 111In [8], a general situation is studied in which a
subset of the terminals generate a SK with the cooperation of the remaining
terminals.. The largest (entropy) rate of such a SK, termed the SK capacity
and denoted by $C_{S}$, is shown in [8] to equal

$C_{S}=H(X_{1},\cdots,X_{d})-R_{min},$ (1)

where

$R_{min}=\min_{(R_{1},\cdots,R_{d})\in{\cal R}}\ \ \sum_{i=1}^{d}R_{i},$ (2)

with222Here, $\subset$ denotes a proper subset.

$\displaystyle{\cal R}$ $\displaystyle=$
$\displaystyle\\{(R_{1},\cdots,R_{d}):\sum_{i\in B}R_{i}\geq$ (3)
$\displaystyle H(\\{X_{j},\ j\in B\\}|\\{X_{j},\ j\in
B^{c}\\}),B\subset\\{1,\cdots,d\\}\\},$

where $B^{c}=\\{1,\cdots,d\\}\backslash B$.

(ii) Private key: For a given subset $A\subset\\{1,\cdots,d\\}$, a PK for the
terminals in $A$, private from the terminals in $A^{c}$, is a SK generated by
the terminals in $A$ with the cooperation of the terminals in $A^{c}$, which
is concealed from an eavesdropper with access to the public interterminal
communication and also from the cooperating terminals in $A^{c}$ (and, hence,
private) 333A general model is considered in [8] for privacy from a subset of
$A^{c}$ of the cooperating terminals.. The largest (entropy) rate of such a
PK, termed the PK capacity and denoted by $C_{P}(A)$, is shown in [8] to be

$\displaystyle C_{P}(A)$ $\displaystyle=$ $\displaystyle
H(X_{1},\cdots,X_{d})-H(\\{X_{i},\ i\in A^{c}\\})-R_{min}(A)$ (4)
$\displaystyle=$ $\displaystyle H(\\{X_{i},\ i\in A\\}|\\{X_{i},\ i\in
A^{c}\\})-R_{min}(A),$

where

$R_{min}(A)=\min_{\\{R_{i},\ i\in A\\}\in{\cal R}(A)}\ \ \sum_{i\in A}R_{i},$
(5)

with

$\displaystyle{\cal R}(A)$ $\displaystyle=$ $\displaystyle\\{\\{R_{i},\ i\in
A\\}:\sum_{i\in B}R_{i}\geq$ (6) $\displaystyle H(\\{X_{j},\ j\in
B\\}|\\{X_{j},\ j\in B^{c}\\}),\ B\subset A\\}.$

The expressions in (1)–(3) and (4)–(6) afford the following interpretation
[8]. The joint entropy $H\left(X_{1},\ldots,X_{d}\right)$ in (1) corresponds
to the maximum rate of shared common randomness – sans secrecy constraints –
that can ever be achieved by the terminals in $\\{1,\ldots,d\\}$ when each
terminal becomes omniscient, i.e., reconstructs all the components of the DMMS
with probability $\cong 1$ as the observation length $n$ becomes large.
Further, $R_{min}$ in (2), (3) corresponds to the smallest aggregate rate of
interterminal communication that enables every terminal to achieve omniscience
[8]. Thus, from (1), the SK capacity $C_{S}$, i.e., largest rate at which all
the terminals in $\\{1,\ldots,d\\}$ can generate a SK, is obtained by
subtracting from the maximum rate of shared common randomness achievable by
these terminals, viz. $H(X_{1},\cdots,X_{d})$, the smallest overall rate
$R_{min}$ of the (data-compressed) interterminal communication that enables
all the terminals to become omniscient. A similar interpretation holds for the
PK capacity $C_{P}(A)$ in (4) as well, with the difference that the terminals
in $A^{c}$, which cooperate in secrecy generation and yet must not be privy to
the secrecy they help generate, can be assumed – without loss of generality –
to simply “reveal” their observations [8]. Hence, the entropy terms in (1),
(3) are now replaced in (4), (6) with additional conditioning on $\\{X_{i},\
i\in A^{c}\\}$. It should be noted that $R_{min}$ and $R_{min}(A)$ are
obtained as solutions to multiterminal Slepian-Wolf (SW) (near-lossless) data
compression problems not involving any secrecy constraints.

The form of characterization of the SK and PK capacities in (1) and (4) also
suggests successive steps for generating the corresponding keys. For instance,
and loosely speaking, in order to generate a SK, the terminals in
$\\{1,\ldots,d\\}$ first generate common randomness (without any secrecy
restrictions) using SW-compressed interterminal communication denoted
collectively by, say, ${\bf F}$. Thus, the terminals generate rvs
$L_{i}=L_{i}({\bf X}_{i},{\bf F}),\ i\in\\{1,\ldots,d\\}$, with
$\frac{1}{n}H(L_{i})>0$, which agree with probability $\cong 1$ for $n$
suitably large; suppressing subscripts, let $L$ denote the resulting “common”
rv where $\frac{1}{n}H(L)>0$. The second step entails an extraction from $L$
of a SK $K=g(L)$ of entropy rate $\frac{1}{n}H(L|{\bf F})$ by means of a
suitable operation $g$ performed identically at each terminal on the acquired
common randomness $L$. In particular, when the common randomness acquired by
the terminals corresponds to omniscience, i.e., $L\cong\left({\bf
X}_{1},\dots,{\bf X}_{d}\right)$, and is achieved using interterminal
communication ${\bf F}$ of the most parsimonious rate $\cong R_{min}$ in (2),
then the corresponding SK $K=g(L)$ has the best rate $C_{S}$ given by (1). It
is important to note, however, that as mentioned in ([8], Section VI) and
already known from [23], [2], neither communication by every terminal nor
omniscience is essential for generating secrecy (SK or PK) at the best rate;
for instance, the rv $L$ above need not correspond to omniscience for the SK
$K=g(L)$ to have the best possible rate in (1).

A similar approach as above can be used to generate a PK of the largest rate
in (4).

The discussion above suggests that techniques for SW data compression could be
used to devise constructive schemes for obtaining SKs and PKs that achieve the
corresponding capacities. Further, in SW data compression, the existence of
linear encoders of rates arbitrarily close to the SW bound has been long known
[5]. In the special situation when the i.i.d. sequences observed at the
terminals are related to each other in probability law through virtual
discrete memoryless channels (DMCs) characterized by independent additive
noises, such linear SW encoders can be obtained in terms of cosets of linear
error correction codes for such virtual channels, a fact first illustrated in
[37] for the case of $d=2$ terminals connected by a virtual binary symmetric
channel (BSC), and later exploited in most known linear constructions of SW
encoders (cf. e.g., [1], [4], [11], [12], [15]-[17], [19], [20], [24], [29],
[33]). When the i.i.d. sequences observed by $d=2$ terminals are connected by
an arbitrary virtual DMC, the corresponding SW data compression can be viewed
in terms of coding for a “semisymmetric” channel, i.e., a channel with
independent additive noise that is defined over an enlarged alphabet [14]; the
case of stationary ergodic observations at the terminals is also considered
therein. These developments in SW data compression can translate into an
emergence of new constructive schemes for secrecy generation.

Motivated by these considerations, we seek to devise new constructive schemes
for secrecy generation in source models in which SW data compression plays a
central role. The main technical contribution of this work is the following:
Considering four simple models of secrecy generation, we show how a new class
of SKs and PKs can be devised for them at rates arbitrarily close to the
corresponding capacities, relying on the SW data compression code in [37].
Additionally, we examine the performance of low density parity check (LDPC)
codes in the SW data compression step of the procedure for secrecy generation.
Preliminary results of this work have been reported in [38], [39]. In
independent work [25] for the case of $d=2$ terminals which is akin to but
different from ours, extraction of a SK from previously acquired common
randomness by means of a linear transformation has been demonstrated.

In related work, SK generation for a source model with two terminals that
observe continuous-amplitude signals, has been studied in [40], [36], [26],
[27], [41]. Furthermore, in recent years, several secrecy generation schemes
have been reported, relying on capacity-achieving channel codes, for “wiretap”
secrecy models that differ from ours. For instance, it was shown in [35] that
such a channel code can attain the secrecy capacity for any wiretap channel.
See also [3], [18].

The paper is organized as follows. Preliminaries are contained in Section II.
In Section III, we consider four simple source models for which we provide
elementary constructive schemes for SK or PK generation which rely on suitable
SW data compression codes; the keys thereby generated are shown to satisfy the
requisite secrecy and rate-optimality conditions in Section IV.
Implementations of these constructions using LDPC codes are illustrated in
Section V which also reports simulation results. Section VI contains closing
remarks.

##  II Preliminaries

###  II-A Secret Key and Private Key Capacities

Consider a DMMS with $d\geq 2$ components, with corresponding generic rvs
$X_{1},\cdots,X_{d}$ taking values in finite alphabets ${\cal
X}_{1},\cdots,{\cal X}_{d}$, respectively. Let ${\bf
X}_{i}=(X_{i,1},\cdots,X_{i,n})$ be $n$ i.i.d. repetitions of rv $X_{i}$,
$i\in{\cal D}=\\{1,\cdots,d\\}$. Terminals $1,\cdots,d$, with respective
observations ${\bf X}_{1},\cdots,{\bf X}_{d}$, represent the $d$ users that
wish to generate a SK by means of public communication. These terminals can
communicate with each other through broadcasts over a noiseless public
channel, possibly interactively in many rounds. In general, a communication
from a terminal is allowed to be any function of its observations, and of all
previous communication. Let ${\bf F}$ denote collectively all the public
communication.

Given $\varepsilon>0$, the rv $K_{\cal S}$ represents an $\varepsilon$-secret
key ($\varepsilon$-SK) for the terminals in ${\cal D}$, achieved with
communication ${\bf F}$, if there exist rvs $K_{i}=K_{i}({\bf X}_{i},{\bf
F})$, $i\in{\cal D}$, with $K_{i}$ and $K_{\cal S}$ taking values in the same
finite set ${\cal K_{S}}$, such that $K_{\cal S}$ satisfies

$\bullet$ the common randomness condition

$\Pr\\{K_{i}=K_{\cal S},\ i\in{\cal D}\\}\geq 1-\varepsilon;$

$\bullet$ the secrecy condition

$\frac{1}{n}I(K_{\cal S}\wedge{\bf F})\leq\varepsilon;$

and

$\bullet$ the uniformity condition

$\frac{1}{n}H(K_{\cal S})\geq\frac{1}{n}\log|{\cal K}_{\cal S}|-\varepsilon.$

Let $A\subset{\cal D}$ be an arbitrary subset of the terminals. The rv
$K_{\cal P}(A)$ represents an $\varepsilon$-private key ($\varepsilon$-PK) for
the terminals in $A$, private from the terminals in $A^{c}={\cal D}\backslash
A$, achieved with communication ${\bf F}$, if there exist rvs
$K_{i}=K_{i}({\bf X}_{i},{\bf F})$, $i\in A$, with $K_{i}$ and $K_{\cal P}(A)$
taking values in the same finite set ${\cal K_{P}}(A)$, such that $K_{\cal
P}(A)$ satisfies

$\bullet$ the common randomness condition

$\Pr\\{K_{i}=K_{\cal P}(A),\ i\in A\\}\geq 1-\varepsilon;$

$\bullet$ the secrecy condition

$\frac{1}{n}I\left(K_{\cal P}(A)\wedge\\{{\bf X}_{i},\ i\in A^{c}\\},{\bf
F}\right)\leq\varepsilon;$

and

$\bullet$ the uniformity condition

$\frac{1}{n}H(K_{\cal P}(A))\geq\frac{1}{n}\log\left|{\cal K}_{\cal
P}(A)\right|-\varepsilon.$

Definition 1 [8]: A nonnegative number $R$ is called an achievable SK rate if
$\varepsilon_{n}$-SKs $K_{\cal S}^{(n)}$ are achievable with suitable
communication (with the number of rounds possibly depending on $n$), such that
$\varepsilon_{n}\rightarrow 0$ and $\frac{1}{n}H\left(K_{\cal
S}^{(n)}\right)\rightarrow R$. The largest achievable SK rate is called the SK
capacity, denoted by $C_{S}$. The PK capacity for the terminals in $A$,
denoted by $C_{P}(A)$, is similarly defined. An achievable SK rate (resp. PK
rate) will be called strongly achievable if $\varepsilon_{n}$ above can be
taken to vanish exponentially in $n$. The corresponding capacities are termed
strong capacities.

Single-letter characterizations have been obtained for $C_{S}$ in the case of
$d=2$ terminals in [2], [23] and for $d\geq 2$ terminals in [8], given by (1);
and for $C_{P}(A)$ in the case of $d=3$ terminals in [2] and for $d\geq 3$
terminals in [8], given by (4). The proofs of the achievability parts exploit
the close connection between secrecy generation and SW data compression.
Loosely speaking, common randomness sans any secrecy restrictions is first
generated through SW-compressed interterminal communication, whereby all the
$d$ terminals acquire a (common) rv with probability $\cong 1$. In the next
step, secrecy is then extracted by means of a suitable identical operation
performed at each terminal on the acquired common randomness. When the common
randomness initially acquired by the $d$ terminals is maximal, the
corresponding SK has the best rate $C_{S}$ given by (1).

In this work, we consider four simple models for which we illustrate the
constructions of appropriate strong SKs or PKs.

###  II-B Linear Codes for the Binary Symmetric Channel

The SW codes of interest will rely on the following classic result concerning
the existence of “good” linear channel codes for a BSC. A BSC with crossover
probability $p$, $0<p<\frac{1}{2}$, will be denoted by BSC($p$). Let
$h(p)=-p\log_{2}p-(1-p)\log_{2}(1-p)$ denote the binary entropy function.

Lemma 1 [9]: For every $\varepsilon>0$, $0<p<\frac{1}{2}$, and for all $n$
sufficiently large, there exists a binary linear $(n,n-m)$ code for a
BSC($p$), with $m<n[h(p)+\varepsilon]$, such that the average error
probability of maximum likelihood decoding is less than $2^{-n\eta}$, for some
$\eta>0$.

###  II-C Types and Typical Sequences

The following standard facts regarding “types” and “typical sequences” and
their pertinent properties (cf. e.g., [6]) are compiled here in brief for
ready reference.

Given finite sets ${\cal X}$, ${\cal Y}$, the type of a sequence ${\bf
x}=(x_{1},\cdots,x_{n})\in{\cal X}^{n}$, ${\cal X}$ a finite set, is the
probability mass function (pmf) $P_{\bf x}$ on ${\cal X}$ given by

$P_{\bf x}(a)=\frac{1}{n}|\\{i:x_{i}=a\\}|,\ \ \ a\in{\cal X},$

and the joint type of a pair of sequences $({\bf x},{\bf y})\in{\cal
X}^{n}\times{\cal Y}^{n}$ is the joint pmf $P_{\bf xy}$ on ${\cal
X}\times{\cal Y}$ given by

$P_{\bf xy}(a,b)=\frac{1}{n}|\\{i:x_{i}=a,y_{i}=b\\}|,\ \ \ a\in{\cal X},\
b\in{\cal Y}.$

The numbers of different types of sequences in ${\cal X}^{n}$ (resp. ${\cal
X}^{n}\times{\cal Y}^{n}$) do not exceed $(n+1)^{|{\cal X}|}$ (resp.
$(n+1)^{|{\cal X}||{\cal Y}|}$).

Given rvs $X$, $Y$ (taking values in ${\cal X}$, ${\cal Y}$, respectively),
with joint pmf $P_{XY}$ on ${\cal X}\times{\cal Y}$, the set of sequences in
${\cal X}^{n}$ which are $X$-typical with constant $\xi$, denoted by
$T_{X,\xi}^{n}$, is defined as

$T_{X,\xi}^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\left\\{{\bf x}\in{\cal
X}^{n}:2^{-n[H(X)+\xi]}\leq P_{X}^{n}({\bf x})\leq 2^{-n[H(X)-\xi]}\right\\},$

where $P_{X}^{n}({\bf x})\stackrel{{\scriptstyle\triangle}}{{=}}\Pr\\{{\bf
X}={\bf x}\\}$, ${\bf x}\in{\cal X}^{n}$; and the set of pairs of sequences in
${\cal X}^{n}\times{\cal Y}^{n}$ which are $XY$-typical with constant $\xi$,
denoted by $T_{XY,\xi}^{n}$, is defined as

$\displaystyle T_{XY,\xi}^{n}$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}$ $\displaystyle\\{({\bf
x},{\bf y})\in{\cal X}^{n}\times{\cal Y}^{n}:{\bf x}\in T_{X,\xi}^{n},{\bf
y}\in T_{Y,\xi}^{n},$ $\displaystyle 2^{-n[H(X,Y)+\xi]}\leq P_{XY}^{n}({\bf
x},{\bf y})\leq 2^{-n[H(X,Y)-\xi]}\\},$

where $P_{XY}^{n}({\bf x},{\bf
y})\stackrel{{\scriptstyle\triangle}}{{=}}\Pr\\{{\bf X}={\bf x},{\bf Y}={\bf
y}\\}$, ${\bf x}\in{\cal X}^{n}$, ${\bf y}\in{\cal Y}^{n}$. It readily follows
that for every $({\bf x},{\bf y})\in T_{XY,\xi}^{n}$,

$2^{-n[H(X|Y)+2\xi]}\leq P_{X|Y}^{n}({\bf x}|{\bf y})\leq
2^{-n[H(X|Y)-2\xi]},$

where $P_{X|Y}^{n}({\bf x}|{\bf
y})\stackrel{{\scriptstyle\triangle}}{{=}}\Pr\\{{\bf X}={\bf x}|{\bf Y}={\bf
y}\\}$, ${\bf x}\in{\cal X}^{n}$, ${\bf y}\in{\cal Y}^{n}$.

For every ${\bf y}\in{\cal Y}^{n}$, the set of sequences in ${\cal X}^{n}$
which are $X|Y$-typical with respect to ${\bf y}$ with constant $\xi$, denoted
by $T_{X|Y,\xi}^{n}({\bf y})$, is defined as

$T_{X|Y,\xi}^{n}({\bf y})\stackrel{{\scriptstyle\triangle}}{{=}}\left\\{{\bf
x}\in{\cal X}^{n}:({\bf x},{\bf y})\in T_{XY,\xi}^{n}\right\\},$

with $T_{X|Y,\xi}^{n}({\bf y})=\phi$ if ${\bf y}\not\in T_{Y,\xi}^{n}$. The
following is an independent and explicit statement of the well-known fact that
the probability of a nontypical set decays to 0 exponentially rapidly in $n$
(cf. e.g., [42, Theorem 6.3]).

Proposition 1: Given a joint pmf $P_{XY}$ on ${\cal X}\times{\cal Y}$ with
$P_{XY}(x,y)>0$, $x\in{\cal X}$, $y\in{\cal Y}$, for every $\xi>0$,

$\sum_{{\bf x}\in T_{X,\xi}^{n}}P_{X}^{n}({\bf x})\geq 1-(n+1)^{|{\cal
X}|}\cdot 2^{-n\frac{\xi^{2}}{2\ln 2\left[\sum_{a\in{\cal
X}}\log\frac{1}{P_{X}(a)}\right]^{2}}},$ (7)

and

$\displaystyle\sum_{({\bf x},{\bf y})\in T_{XY,\xi}^{n}}P_{XY}^{n}({\bf
x},{\bf y})$ (8) $\displaystyle\geq$ $\displaystyle 1-(n+1)^{|{\cal X}||{\cal
Y}|}\cdot 2^{-n\frac{\xi^{2}}{2\ln 2\left[\sum_{(a,b)\in{\cal X}\times{\cal
Y}}\log\frac{1}{P_{XY}(a,b)}\right]^{2}}},$

for all $n\geq 1$.

Proof: See Appendix A.

##  III Main Results

We now present our main results on SK generation for three specific models,
and PK generation for a fourth model. The proofs of the accompanying Theorems
1 - 4 are provided in Section IV.

Model 1: Let the terminals $1$ and $2$ observe, respectively, $n$ i.i.d.
repetitions of the $\\{0,1\\}$-valued rvs $X_{1}$ and $X_{2}$ with joint pmf

$\displaystyle P_{X_{1}X_{2}}(x_{1},x_{2})$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-p)\delta_{x_{1}x_{2}}+\frac{1}{2}p\
(1-\delta_{x_{1}x_{2}}),$ (9) $\displaystyle\hskip 72.26999pt0<p<\frac{1}{2},$

with $\delta$ being the Kronecker delta function. These terminals wish to
generate a strong SK of maximum rate.

The (strong) SK capacity for this model [2], [8], [23], given by (1), is

$C_{S}=I(X_{1}\wedge X_{2})=1-h(p).$

We show a simple scheme for the terminals to generate a SK with rate close to
$1-h(p)$, which relies on Wyner’s well-known method for SW data compression
[37]. The SW problem of interest entails terminal $2$ reconstructing the
observed sequence ${\bf x}_{1}$ at terminal $1$ from the SW codeword for ${\bf
x}_{1}$ and its own observed sequence ${\bf x}_{2}$.

Observe that under the given joint pmf (9), ${\bf X}_{2}$ can be considered as
an input to a virtual BSC($p$), with corresponding output ${\bf X}_{1}$, i.e.,
we can write

${\bf X}_{1}={\bf X}_{2}\oplus{\bf V},$ (10)

where ${\bf V}=(V_{1},\cdots,V_{n})$ is an i.i.d. sequence of
$\\{0,1\\}$-valued rvs, independent of ${\bf X}_{2}$, and with
$\Pr\\{V_{i}=1\\}=p$, $1\leq i\leq n$.

(i) SW data compression [37]: Let ${\cal C}$ be a linear $(n,n-m)$ code as in
Lemma 1 with parity check matrix ${\bf P}$. Both terminals know ${\cal C}$
(and ${\bf P}$). Terminal $1$ communicates the syndrome ${\bf P}{\bf
x}_{1}^{t}$ to terminal $2$. The maximum likelihood estimate of ${\bf x}_{1}$
at terminal 2 is:

${\hat{\bf x}_{2}}(1)={\bf x}_{2}\oplus f_{\bf P}({\bf P}{\bf
x}_{1}^{t}\oplus{\bf P}{\bf x}_{2}^{t}),$

where $f_{\bf P}({\bf P}{\bf x}_{1}^{t}\oplus{\bf P}{\bf x}_{2}^{t})$ is the
most likely sequence ${\bf v}\in\\{0,1\\}^{n}$ (under the pmf of ${\bf V}$ as
above) with syndrome ${\bf P}{\bf v}^{t}={\bf P}{\bf x}_{1}^{t}\oplus{\bf
P}{\bf x}_{2}^{t}$, with $\oplus$ denoting addition modulo 2 and $t$ denoting
transposition. Note that in a standard array corresponding to the code ${\cal
C}$ above, $f_{\bf P}({\bf P}{\bf x}_{1}^{t}\oplus{\bf P}{\bf x}_{2}^{t})$ is
simply the coset leader of the coset with syndrome ${\bf P}{\bf
x}_{1}^{t}\oplus{\bf P}{\bf x}_{2}^{t}$. Also, ${\bf x}_{1}$ and ${\hat{\bf
x}_{2}}(1)$ lie in the same coset.

The probability of decoding error at terminal $2$ is given by

$\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf X}_{1}\\}=\Pr\\{{\bf X}_{2}\oplus f_{\bf
P}({\bf P}{\bf X}_{1}^{t}\oplus{\bf P}{\bf X}_{2}^{t})\neq{\bf X}_{1}\\},$

and it readily follows from (10) that

$\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf X}_{1}\\}=\Pr\\{f_{\bf P}({\bf P}{\bf
V}^{t})\neq{\bf V}\\}.$

By Lemma 1, $\Pr\\{f_{\bf P}({\bf P}{\bf V}^{t})\neq{\bf V}\\}<2^{-n\eta}$ for
some $\eta>0$ and for all $n$ sufficiently large, so that

$\Pr\\{{\hat{\bf X}_{2}}(1)={\bf X}_{1}\\}\geq 1-2^{-n\eta}.$

(ii) SK construction: Consider a (common) standard array for ${\cal C}$ known
to both terminals. Denote by ${\bf a}_{i,j}$ the element of the $i^{th}$ row
and the $j^{th}$ column in the standard array, $1\leq i\leq 2^{m}$, $1\leq
j\leq 2^{n-m}$.

Terminal $1$ sets $K_{1}=j_{1}$ if ${\bf X}_{1}$ equals ${\bf a}_{i,j_{1}}$ in
its coset $i$ in the standard array. Terminal $2$ sets $K_{2}=j_{2}$ if
${\hat{\bf X}_{2}}(1)$ equals ${\bf a}_{i,j_{2}}$ in the coset $i$ of the same
standard array.

The following theorem asserts that $K_{1}$ constitutes a strong SK with rate
approaching SK capacity.

Theorem 1: Let $\varepsilon>0$ be given. Then for some $\eta>0$ and for all
$n$ sufficiently large, the pair of rvs $(K_{1},K_{2})$ generated above, with
(common) range ${\cal K}_{1}$ (say), satisfy

$\Pr\\{K_{1}=K_{2}\\}\geq 1-2^{-n\eta},$ (11) $I(K_{1}\wedge{\bf F})=0,$ (12)
$H(K_{1})=\log|{\cal K}_{1}|,$ (13)

and

$\frac{1}{n}H(K_{1})>1-h(p)-\varepsilon.$ (14)

Remark: The probability of $K_{1}$ differing from $K_{2}$ equals exactly the
average error probability of maximum likelihood decoding when ${\cal C}$ is
used on a BSC($p$). Furthermore, the gap between the rate of the generated SK
and SK capacity equals the gap between the rate of ${\cal C}$ and channel
capacity.

Model 2: Let the terminals $1$ and $2$ observe, respectively, $n$ i.i.d.
repetitions of the $\\{0,1\\}$-valued rvs with joint pmf

$\displaystyle P_{X_{1}X_{2}}(0,0)$ $\displaystyle=$
$\displaystyle(1-p)(1-q),$ $\displaystyle P_{X_{1}X_{2}}(0,1)$
$\displaystyle=$ $\displaystyle pq,$ $\displaystyle P_{X_{1}X_{2}}(1,0)$
$\displaystyle=$ $\displaystyle p(1-q),$ $\displaystyle P_{X_{1}X_{2}}(1,1)$
$\displaystyle=$ $\displaystyle q(1-p),$ (15)

with $0<p<\frac{1}{2}$ and $0<q<1$. These terminals wish to generate a strong
SK of maximum rate.

Note that Model 1 is a special case of Model 2 for $q=\frac{1}{2}$. We show
below a scheme for the terminals to generate a SK with rate close to the
(strong) SK capacity for this model [2], [8], [23], which is given by (1) as

$C_{S}=I(X_{1}\wedge X_{2})=h(p+q-2pq)-h(p).$

(i) SW data compression: This step is identical to step (i) for Model 1. Note
that under the given joint pmf (15), ${\bf X}_{1}$ and ${\bf X}_{2}$ can be
written as in (10). It follows in the same manner as for Model 1 that for some
$\eta>0$ and for all $n$ sufficiently large,

$\Pr\\{{\hat{\bf X}_{2}}(1)={\bf X}_{1}\\}\geq 1-2^{-n\eta}.$

(ii) SK construction: Both terminals know the linear $(n,n-m)$ code ${\cal C}$
as in Lemma 1, and a (common) standard array for ${\cal C}$. Let $\\{{\bf
e}_{i}:1\leq i\leq 2^{m}\\}$ denote the set of coset leaders for all the
cosets of ${\cal C}$.

Denote by $A_{i}$ the set of sequences from $T_{X_{1},\xi}^{n}$ in the coset
of ${\cal C}$ with coset leader ${\bf e}_{i}$, $1\leq i\leq 2^{m}$. If the
number of sequences of the same type in $A_{i}$ is more than
$2^{n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]}$, where
$\varepsilon^{\prime}>\xi+\varepsilon$ with $\varepsilon$ satisfying
$m<n[h(p)+\varepsilon]$ in Lemma 1, then collect arbitrarily
$2^{n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]}$ such sequences to compose a
subset, which we term a regular subset (as it consists of sequences of the
same type). Continue this procedure until the number of sequences of every
type in $A_{i}$ is less than $2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}$. Let $N_{i}$ denote the number of distinct
regular subsets of $A_{i}$.

Enumerate (in any way) the sequences in each regular subset. Let ${\bf
b}_{i,j,k}$, where $1\leq i\leq 2^{m}$, $1\leq j\leq N_{i}$, $1\leq k\leq
2^{n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]}$, denote the $k^{th}$
sequence of the $j^{th}$ regular subset in the $i^{th}$ coset (with coset
leader ${\bf e}_{i}$).

Terminal $1$ sets $K_{1}=k_{1}$ if ${\bf X}_{1}$ equals ${\bf
b}_{i,j_{1},k_{1}}$; else, $K_{1}$ is set to be uniformly distributed on
$\left\\{1,\cdots,2^{n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]}\right\\}$,
independent of $({\bf X}_{1},{\bf X}_{2})$. Terminal $2$ sets $K_{2}=k_{2}$ if
${\hat{\bf X}_{2}}(1)$ equals ${\bf b}_{i,j_{2},k_{2}}$; else, $K_{2}$ is set
to be uniformly distributed on $\left\\{1,\cdots,2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}\right\\}$, independent of $({\bf X}_{1},{\bf
X}_{2},K_{1})$.

The following theorem says that $K_{1}$ constitutes a strong SK with rate
approaching SK capacity.

Theorem 2: Let $\varepsilon>0$ be given. Then for some
$\eta^{\prime}=\eta^{\prime}(\eta,\xi,\varepsilon,\varepsilon^{\prime})>0$ and
for all $n$ sufficiently large, the pair of rvs $(K_{1},K_{2})$ generated
above, with range ${\cal K}_{1}$ (say), satisfy

$\Pr\\{K_{1}=K_{2}\\}\geq 1-2^{-n\eta^{\prime}},$ (16) $I(K_{1}\wedge{\bf
F})=0,$ (17) $H(K_{1})=\log|{\cal K}_{1}|,$ (18)

and

$\frac{1}{n}H(K_{1})=h(p+q-2pq)-h(p)-\varepsilon^{\prime}.$ (19)

The next model is an instance of a Markov chain on a tree (cf. [13], [8]).
Consider a tree ${\cal T}$ with vertex set $V({\cal T})=\\{1,\cdots,d\\}$ and
edge set $E({\cal T})$. For $(i,j)\in E({\cal T})$, let $B(i\leftarrow j)$
denote the set of all vertices connected with $j$ by a path containing the
edge $(i,j)$. The rvs $X_{1},\cdots,X_{d}$ form a Markov chain on the tree
${\cal T}$ if for each $(i,j)\in E({\cal T})$, the conditional pmf of $X_{j}$
given $\\{X_{l},l\in B(i\leftarrow j)\\}$ depends only on $X_{i}$ (i.e., is
conditionally independent of $\\{X_{l},l\in B(i\leftarrow
j)\\}\backslash\\{X_{i}\\}$, conditioned on $X_{i}$). Note that when ${\cal
T}$ is a chain, this concept reduces to that of a standard Markov chain.

Model 3: Let the terminals $1,\cdots,d$ observe, respectively, $n$ i.i.d.
repetitions of $\\{0,1\\}$-valued rvs $X_{1},\cdots,X_{d}$ that form a Markov
chain on the tree ${\cal T}$, with joint pmf $P_{X_{1}\cdots X_{d}}$ specified
as: for $(i,j)\in E({\cal T})$,

$\displaystyle P_{X_{i}X_{j}}(x_{i},x_{j})$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-p_{(i,j)})\delta_{x_{i}x_{j}}+\frac{1}{2}p_{(i,j)}\
(1-\delta_{x_{i}x_{j}}),$ $\displaystyle\hskip
72.26999pt0<p_{(i,j)}<\frac{1}{2},$

for $x_{i},x_{j}\in\\{0,1\\}$. These $d$ terminals wish to generate a strong
SK of maximum rate.

Note that Model 1 is a special case of Model 3 for $d=2$. Without any loss of
generality, let

$p_{max}=p_{(i^{*},j^{*})}=\max_{(i,j)\in E({\cal T})}p_{(i,j)}.$

Then, the (strong) SK capacity for this model [8] is given by (1) as

$C_{S}=I(X_{i^{*}}\wedge X_{j^{*}})=1-h(p_{max}).$

We show how to extract a SK with rate close to $1-h(p_{max})$ by using an
extension of the SW data compression scheme of Model 1 for reconstructing
${\bf x}_{i^{*}}$ at all the terminals.

(i) SW data compression: Let ${\cal C}$ be the linear $(n,n-m)$ code as in
Lemma 1 for a BSC($p_{max}$), and with parity check matrix ${\bf P}$. Each
terminal $i$ communicates the syndrome ${\bf P}{\bf x}_{i}^{t}$, $1\leq i\leq
d$.

Let ${\hat{\bf x}}_{i}(j)$ denote the corresponding maximum likelihood
estimate of ${\bf x}_{j}$ at terminal $i$, $1\leq i\neq j\leq d$. For a
terminal $i\neq i^{*}$, denote by $(i_{0},i_{1},\cdots,i_{r})$ the (only) path
in the tree ${\cal T}$ from $i$ to $i^{*}$, where $i_{0}=i$ and $i_{r}=i^{*}$;
this terminal $i$, with the knowledge of (${\bf x}_{i}$, ${\bf P}{\bf
x}_{i_{1}}^{t},\cdots,{\bf P}{\bf x}_{i_{r-1}}^{t},{\bf P}{\bf
x}_{i^{*}}^{t}$), forms its estimate ${\hat{\bf x}}_{i}(i^{*})$ of ${\bf
x}_{i^{*}}$ through the following successive maximum likelihood estimates of
${\bf x}_{i_{1}},\cdots,{\bf x}_{i_{r-1}}$:

$\displaystyle{\hat{\bf x}}_{i}(i_{1})$ $\displaystyle=$ $\displaystyle{\bf
x}_{i}\oplus f_{\bf P}({\bf P}{\bf x}_{i}^{t}\oplus{\bf P}{\bf
x}_{i_{1}}^{t}),$ $\displaystyle{\hat{\bf x}}_{i}(i_{2})$ $\displaystyle=$
$\displaystyle{\hat{\bf x}}_{i}(i_{1})\oplus f_{\bf P}({\bf P}{\bf
x}_{i_{1}}^{t}\oplus{\bf P}{\bf x}_{i_{2}}^{t}),$ $\displaystyle\vdots$
$\displaystyle\vdots$ $\displaystyle\vdots$ $\displaystyle{\hat{\bf
x}}_{i}(i_{r-1})$ $\displaystyle=$ $\displaystyle{\hat{\bf
x}}_{i}(i_{r-2})\oplus f_{\bf P}({\bf P}{\bf x}_{i_{r-2}}^{t}\oplus{\bf P}{\bf
x}_{i_{r-1}}^{t}),$

and finally,

${\hat{\bf x}}{i}(i^{*})={\hat{\bf x}}_{i}(i_{r-1})\oplus f_{\bf P}({\bf
P}{\bf x}_{i_{r-1}}^{t}\oplus{\bf P}{\bf x}_{i^{*}}^{t}).$ (20)

Proposition 2: By the successive maximum likelihood estimation above, the
estimate ${\hat{\bf X}_{i}}(i^{*})$ at terminal $i\neq i^{*}$, satisfies

$\Pr\\{{\hat{\bf X}_{i}}(i^{*})={\bf X}_{i^{*}}\\}\geq 1-d\cdot 2^{-n\eta},$
(21)

for some $\eta>0$ and for all $n$ sufficiently large.

Proof: See Appendix B.

It follows directly from (21) that for some
$\eta^{\prime}=\eta^{\prime}(\eta,m)>0$ and for all $n$ sufficiently large,

$\Pr\\{{\hat{\bf X}_{i}}(i^{*})={\bf X}_{i^{*}},1\leq i\neq i^{*}\leq d\\}\geq
1-2^{-n\eta^{\prime}}.$

(ii) SK construction: Consider a (common) standard array for ${\cal C}$ known
to all the terminals. Denote by ${\bf a}_{l,k}$ the element of the $l^{th}$
row and the $k^{th}$ column in the standard array, $1\leq l\leq 2^{m}$, $1\leq
k\leq 2^{n-m}$. Terminal $i^{*}$ sets $K_{i^{*}}=k_{i^{*}}$ if ${\bf
X}_{i^{*}}$ equals ${\bf a}_{l,k_{i^{*}}}$ in the standard array. Terminal
$i$, $1\leq i\neq i^{*}\leq d$, sets $K_{i}=k_{i}$ if ${\hat{\bf
X}_{i}}(i^{*})$ equals ${\bf a}_{l,k_{i}}$ in the same standard array.

The following theorem states that $K_{i^{*}}$ constitutes a strong SK with
rate approaching SK capacity.

Theorem 3: Let $\varepsilon>0$ be given. Then for some
$\eta^{\prime}=\eta^{\prime}(\eta,d)>0$ and for all $n$ sufficiently large,
the rvs $K_{1},\cdots,K_{d}$ generated above, with range ${\cal K}_{i^{*}}$
(say), satisfy

$\Pr\\{K_{1}=\cdots=K_{d}\\}>1-2^{-n\eta^{\prime}},$ (22)
$I(K_{i^{*}}\wedge{\bf F})=0,$ (23) $H(K_{i^{*}})=\log|{\cal K}_{i^{*}}|,$
(24)

and

$\frac{1}{n}H(K_{i^{*}})>1-h(p_{max})-\varepsilon.$ (25)

Model 4: Let the terminals 1, 2 and 3 observe, respectively, $n$ i.i.d.
repetitions of the $\\{0,1\\}$-valued rvs $X_{1}$, $X_{2}$, $X_{3}$, with
joint pmf $P_{X_{1}X_{2}X_{3}}$ given by:

$\displaystyle
P_{X_{1}X_{2}X_{3}}(0,0,0)=P_{X_{1}X_{2}X_{3}}(0,1,1)=\frac{(1-p)(1-q)}{2},$
$\displaystyle
P_{X_{1}X_{2}X_{3}}(0,0,1)=P_{X_{1}X_{2}X_{3}}(0,1,0)=\frac{pq}{2},$
$\displaystyle
P_{X_{1}X_{2}X_{3}}(1,0,0)=P_{X_{1}X_{2}X_{3}}(1,1,1)=\frac{p(1-q)}{2},$
$\displaystyle
P_{X_{1}X_{2}X_{3}}(1,0,1)=P_{X_{1}X_{2}X_{3}}(1,1,0)=\frac{q(1-p)}{2},$ (26)

with $0<p<\frac{1}{2}$ and $0<q<1$. Terminals 1 and 2 wish to generate a
strong PK of maximum rate, which is concealed from the helper terminal 3.

Note that under the joint pmf of $X_{1}$, $X_{2}$, $X_{3}$ above, we can write

${\bf X}_{1}={\bf X}_{2}\oplus{\bf X}_{3}\oplus{\bf V},$ (27)

where ${\bf V}=(V_{1},\cdots,V_{n})$ is an i.i.d. sequence of
$\\{0,1\\}$-valued rvs, independent of $({\bf X}_{2},{\bf X}_{3})$, with
$\Pr\\{V_{i}=1\\}=p$, $1\leq i\leq n$. Further, $(X_{2},X_{3})$ plays the role
of $(X_{1},X_{2})$ in Model 1 with $q$ in lieu of $p$ in the latter.

We show below a scheme for terminals 1 and 2 to generate a PK with rate close
to (strong) PK capacity for this model [2], [7], [8], given by (4) as

$C_{P}(\\{1,2\\})=I(X_{1}\wedge X_{2}|X_{3})=h(p+q-2pq)-h(p).$

The first step of this scheme entails terminal 3 simply revealing its
observations ${\bf x}_{3}$ to both terminals 1 and 2. Then, Wyner’s SW data
compression scheme is used for reconstructing ${\bf x}_{1}$ at terminal 2 from
the SW codeword for ${\bf x}_{1}$ and its own knowledge of ${\bf
x}_{2}\oplus{\bf x}_{3}$.

(i) SW data compression: This step is identical to step (i) for Model 1, as
seen with the help of (27). Obviously,

$\Pr\\{{\hat{\bf X}_{2}}(1)={\bf X}_{1}\\}\geq 1-2^{-n\eta},$

for some $\eta>0$ and for all $n$ sufficiently large.

(ii) PK construction: Suppose that terminals 1 and 2 know a linear $(n,n-m)$
code ${\cal C}$ as in Lemma 1, and a (common) standard array for ${\cal C}$.
Let $\\{{\bf e}_{i}:1\leq i\leq 2^{m}\\}$ denote the set of coset leaders for
all the cosets of ${\cal C}$.

For a sequence ${\bf x}_{3}\in\\{0,1\\}^{n}$, denote by $A_{i}({\bf x}_{3})$
the set of sequences from $T_{X_{1}|X_{3},\xi}^{n}({\bf x}_{3})$ in the coset
of ${\cal C}$ with coset leader ${\bf e}_{i}$, $1\leq i\leq 2^{m}$. If the
number of sequences of the same joint type with ${\bf x}_{3}$ in $A_{i}({\bf
x}_{3})$ is more than $2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$, where
$\varepsilon^{\prime}>2\xi+\varepsilon$ and $\varepsilon$ satisfies
$m<n[h(p)+\varepsilon]$ (as in Lemma 1), then collect arbitrarily
$2^{n[I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime}]}$ such sequences to
compose a regular subset. Continue this procedure until the number of
sequences of every joint type with ${\bf x}_{3}$ in $A_{i}({\bf x}_{3})$ is
less than $2^{n[I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime}]}$. Let
$N_{i}({\bf x}_{3})$ denote the number of distinct regular subsets of
$A_{i}({\bf x}_{3})$.

For a given sequence ${\bf x}_{3}$, enumerate (in any way) the sequences in
each regular subset. Let ${\bf b}_{i,j,k}({\bf x}_{3})$, where $1\leq i\leq
2^{m}$, $1\leq j\leq N_{i}({\bf x}_{3})$, $1\leq k\leq 2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$, denote the $k^{th}$ sequence of the
$j^{th}$ regular subset in the $i^{th}$ coset.

Terminal $1$ sets $K_{1}=k_{1}$ if ${\bf X}_{1}$ equals ${\bf
b}_{i,j_{1},k_{1}}({\bf x}_{3})$; else, $K_{1}$ is set to be uniformly
distributed on $\left\\{1,\cdots,2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}\right\\}$, independent of $({\bf
X}_{1},{\bf X}_{2},{\bf X}_{3})$. Terminal 2 sets $K_{2}=k_{2}$ if ${\hat{\bf
X}_{2}}(1)$ equals ${\bf b}_{i,j_{2},k_{2}}({\bf x}_{3})$; else, $K_{2}$ is
set to be uniformly distributed on $\left\\{1,\cdots,2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}\right\\}$, independent of $({\bf
X}_{1},{\bf X}_{2},{\bf X}_{3},K_{1})$.

The following theorem establishes that $K_{1}$ constitutes a strong PK with
rate approaching PK capacity.

Theorem 4: Let $\varepsilon>0$ be given. Then for some
$\eta^{\prime}=\eta^{\prime}(\eta,\xi,\varepsilon,\varepsilon^{\prime})>0$ and
for all $n$ sufficiently large, the pair of rvs $(K_{1},K_{2})$ generated
above, with range ${\cal K}_{1}$ (say), satisfy

$\Pr\\{K_{1}\neq K_{2}\\}<2^{-n\eta^{\prime}},$ (28) $I(K_{1}\wedge{\bf
X}_{3},{\bf F})=0,$ (29) $H(K_{1})=\log|{\cal K}_{1}|,$ (30)

and

$\frac{1}{n}H(K_{1})=I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime}.$ (31)

Remark: The PK construction scheme above applies for any joint pmf
$P_{X_{1}X_{2}X_{3}}$ satisfying (27), and is not restricted to the given
joint pmf in (26).

##  IV Proofs of Theorems 1–4

Proof of Theorem 1: It follows from the SK construction scheme for Model 1
that

$\Pr\\{K_{1}\neq K_{2}\\}=\Pr\\{{\hat{\bf X}_{2}(1)}\neq{\bf
X}_{1}\\}<2^{-n\eta},$

which is (11). Since $X_{1}$ is uniformly distributed on $\\{0,1\\}$, we have
for $1\leq i\leq 2^{m}$, $1\leq j\leq 2^{n-m}$, that

$\Pr\\{{\bf X}_{1}={\bf a}_{i,j}\\}=2^{-n}.$

Hence,

$\displaystyle\Pr\\{K_{1}=j\\}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{2^{m}}\Pr\\{{\bf X}_{1}={\bf a}_{i,j}\\}$
$\displaystyle=$ $\displaystyle 2^{-(n-m)},\ \ \ 1\leq j\leq 2^{n-m},$

i.e., $K_{1}$ is uniformly distributed on ${\cal
K}_{1}=\left\\{1,\cdots,2^{n-m}\right\\}$, and so

$H(K_{1})=\log 2^{n-m}=n-m=\log|{\cal K}_{1}|,$

which is (13). Therefore, (14) holds since $m<n[h(p)+\varepsilon]$.

It remains to show that $K_{1}$ satisfies (12) with ${\bf F}={\bf P}{\bf
X}_{1}^{t}$. Let $\\{{\bf e}_{i},1\leq i\leq 2^{m}\\}$ be the set of coset
leaders for the cosets of ${\cal C}$. For $1\leq i\leq 2^{m}$, $1\leq j\leq
2^{n-m}$,

$\displaystyle\Pr\\{K_{1}=j|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t}\\}$
$\displaystyle=$ $\displaystyle\frac{\Pr\\{K_{1}=j,{\bf P}{\bf X}_{1}^{t}={\bf
P}{\bf e}_{i}^{t}\\}}{\Pr\\{{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t}\\}}$
$\displaystyle=$ $\displaystyle\frac{\Pr\\{{\bf X}_{1}={\bf
a}_{i,j}\\}}{\sum_{j^{\prime}=1}^{2^{n-m}}\Pr\\{{\bf X}_{1}={\bf
a}_{i,j^{\prime}}\\}}$ $\displaystyle=$ $\displaystyle 2^{-(n-m)}$
$\displaystyle=$ $\displaystyle\Pr\\{K_{1}=j\\},$

i.e., $K_{1}$ is independent of ${\bf F}$, and so $I(K_{1}\wedge{\bf F})=0$,
establishing (12).

Proof of Theorem 2: Let ${\cal F}$ denote the union of all regular subsets in
$\bigcup_{i=1}^{2^{m}}A_{i}$. Clearly ${\cal F}\subseteq T_{X_{1},\xi}^{n}$,
so that

$\displaystyle\Pr\\{{\bf X}_{1}\in{\cal F}\\}$ (32) $\displaystyle=$
$\displaystyle\Pr\\{{\bf X}_{1}\in T_{X_{1},\xi}^{n},{\bf X}_{1}\in{\cal
F}\\}$ $\displaystyle=$ $\displaystyle\Pr\\{{\bf X}_{1}\in
T_{X_{1},\xi}^{n}\\}-\Pr\\{{\bf X}_{1}\in T_{X_{1},\xi}^{n}\backslash{\cal
F}\\}.$

By Proposition 1, $\Pr\\{{\bf X}_{1}\in T_{X_{1},\xi}^{n}\\}$ goes to 1
exponentially rapidly in $n$. We show below that $\Pr\\{{\bf X}_{1}\in
T_{X_{1},\xi}^{n}\backslash{\cal F}\\}$ decays to 0 exponentially rapidly in
$n$.

Since the number of different types of sequences in $\\{0,1\\}^{n}$ does not
exceed $(n+1)^{2}$, we have that

$\displaystyle\left|\\{{\bf x}_{1}:{\bf x}_{1}\in
T_{X_{1},\xi}^{n}\backslash{\cal F}\\}\right|$ $\displaystyle\leq$
$\displaystyle 2^{m}\cdot(n+1)^{2}\cdot 2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}$ $\displaystyle<$ $\displaystyle(n+1)^{2}\cdot
2^{n[H(X_{1})+\varepsilon-\varepsilon^{\prime}]},$

where the previous inequality is from
$m<n[h(p)+\varepsilon]=n[H(X_{1}|X_{2})+\varepsilon]$.

Since $P_{X_{1}}^{n}({\bf x}_{1})\leq 2^{-n[H(X_{1})-\xi]}$, ${\bf x}_{1}\in
T_{X_{1},\xi}^{n}$, we get

$\Pr\\{{\bf X}_{1}\in T_{X_{1},\xi}^{n}\backslash{\cal F}\\}<(n+1)^{2}\cdot
2^{-n(\varepsilon^{\prime}-\xi-\varepsilon)}.$

Choosing $\varepsilon^{\prime}>\xi+\varepsilon$, $\Pr\\{{\bf X}_{1}\in
T_{X_{1},\xi}^{n}\backslash{\cal F}\\}$ goes to 0 exponentially rapidly.
Therefore, it follows from (32) that $\Pr\\{{\bf X}_{1}\in{\cal F}\\}$ goes to
1 exponentially rapidly in $n$, with exponent depending on
$(\xi,\varepsilon,\varepsilon^{\prime})$.

By the SK construction scheme for Model 2,

$\displaystyle\Pr\\{K_{1}\neq K_{2}\\}$ $\displaystyle=$
$\displaystyle\Pr\\{K_{1}\neq K_{2},{\bf X}_{1}\in{\cal F}\\}+\Pr\\{K_{1}\neq
K_{2},{\bf X}_{1}\not\in{\cal F}\\}$ $\displaystyle\leq$
$\displaystyle\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf X}_{1},{\bf X}_{1}\in{\cal
F}\\}+\Pr\\{{\bf X}_{1}\not\in{\cal F}\\}$ $\displaystyle\leq$
$\displaystyle\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf X}_{1}\\}+\Pr\\{{\bf
X}_{1}\not\in{\cal F}\\}.$

Since $\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf X}_{1}\\}<2^{-n\eta}$, by the
observation in the previous paragraph, we have

$\Pr\\{K_{1}\neq K_{2}\\}<2^{-n\eta^{\prime}}$

for some
$\eta^{\prime}=\eta^{\prime}(\eta,\xi,\varepsilon,\varepsilon^{\prime})>0$ and
for all $n$ sufficiently large, which is (16).

Next, we shall show that $K_{1}$ satisfies (18). For $1\leq k\leq
2^{n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]}$, it is clear by choice that

$\Pr\\{K_{1}=k|{\bf X}_{1}\not\in{\cal F}\\}=2^{-n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]},$ (33)

and that

$\displaystyle\Pr\\{K_{1}=k|{\bf X}_{1}\in{\cal F}\\}=\frac{\Pr\\{K_{1}=k,{\bf
X}_{1}\in{\cal F}\\}}{\Pr\\{{\bf X}_{1}\in{\cal F}\\}}$ (34) $\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{2^{m}}\sum_{j=1}^{N_{i}}\Pr\\{{\bf X}_{1}={\bf
b}_{i,j,k}\\}}{\sum_{i=1}^{2^{m}}\sum_{j=1}^{N_{i}}2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}\Pr\\{{\bf X}_{1}={\bf b}_{i,j,k}\\}}$
$\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]},$ (35)

where (34) is due to every regular subset consisting of sequences of the same
type. From (33) and (35),

$\Pr\\{K_{1}=k\\}=2^{-n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]},$ (36)

i.e., $K_{1}$ is uniformly distributed on ${\cal
K}_{1}=\left\\{1,\cdots,2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}\right\\}$, with

$\frac{1}{n}H(K_{1})=I(X_{1}\wedge X_{2})-\varepsilon^{\prime},$

which is (19).

It remains to show that $K_{1}$ satisfies (17) with ${\bf F}={\bf P}{\bf
X}_{1}^{t}$. For $1\leq i\leq 2^{m}$, $1\leq k\leq 2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}$, we have

$\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf
X}_{1}\not\in{\cal F}\\}=2^{-n[I(X_{1}\wedge X_{2})-\varepsilon^{\prime}]}$

by choice, and

$\displaystyle\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf
X}_{1}\in{\cal F}\\}$ $\displaystyle=$ $\displaystyle\frac{\Pr\\{K_{1}=k,{\bf
P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf X}_{1}\in{\cal F}\\}}{\Pr\\{{\bf
P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf X}_{1}\in{\cal F}\\}}$
$\displaystyle=$ $\displaystyle\frac{\sum_{j=1}^{N_{i}}\Pr\\{{\bf X}_{1}={\bf
b}_{i,j,k}\\}}{\sum_{j=1}^{N_{i}}2^{n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}\Pr\\{{\bf X}_{1}={\bf b}_{i,j,k}\\}}$
$\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}.$

Hence,

$\displaystyle\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t}\\}$
$\displaystyle=$ $\displaystyle\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf
P}{\bf e}_{i}^{t},{\bf X}_{1}\in{\cal F}\\}\times$ $\displaystyle\Pr\\{{\bf
X}_{1}\in{\cal F}|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t}\\}$
$\displaystyle+\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf
e}_{i}^{t},{\bf X}_{1}\not\in{\cal F}\\}\times$ $\displaystyle\Pr\\{{\bf
X}_{1}\not\in{\cal F}|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t}\\}$
$\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2})-\varepsilon^{\prime}]}$ $\displaystyle=$
$\displaystyle\Pr\\{K_{1}=k\\},$

where the previous equality follows from (36). Thus, $K_{1}$ is independent of
${\bf F}$, establishing (17).

Proof of Theorem 3: Applying the same arguments used in Theorem 1, we see that
the rvs $K_{1},\cdots,K_{m}$ satisfy (22), (24) and (25). It then remains to
show that $K_{i^{*}}$ satisfies (23) with ${\bf F}=({\bf P}{\bf
X}_{1}^{t},\cdots,{\bf P}{\bf X}_{d}^{t})$.

Under the given joint pmf $P_{X_{1}\cdots X_{d}}$, for each $i\neq i^{*}$, we
can write

${\bf X}_{i}={\bf X}_{i^{*}}\oplus{\bf V}_{i},$

where ${\bf V}_{i}=(V_{i,1},\cdots,V_{i,n})$ is an i.i.d. sequence of
$\\{0,1\\}$-valued rvs. Further, ${\bf V}_{i}$, $1\leq i\neq i^{*}\leq d$, and
${\bf X}_{i^{*}}$ are mutually independent. Then,

$\displaystyle I(K_{i^{*}}\wedge{\bf F})$ (37) $\displaystyle=$ $\displaystyle
I(K_{i^{*}}\wedge\\{{\bf P}{\bf X}_{i}^{t},\ 1\leq i\leq d\\})$
$\displaystyle\leq$ $\displaystyle I(K_{i^{*}}\wedge{\bf P}{\bf
X}_{i^{*}}^{t},\\{{\bf P}{\bf V}_{i}^{t},\ 1\leq i\neq i^{*}\leq d\\})$
$\displaystyle\leq$ $\displaystyle I(K_{i^{*}}\wedge{\bf P}{\bf
X}_{i^{*}}^{t})$ $\displaystyle+I(K_{i^{*}},{\bf P}{\bf
X}_{i^{*}}^{t}\wedge\\{{\bf P}{\bf V}_{i}^{t},\ 1\leq i\neq i^{*}\leq d\\}).$

Clearly, the first term on the right hand side of (37) is zero. Since for a
fixed ${\bf P}$, $(K_{i^{*}},{\bf P}{\bf X}_{i^{*}}^{t})$ is a function of
${\bf X}_{i^{*}}$,

$\displaystyle I(K_{i^{*}},{\bf P}{\bf X}_{i^{*}}^{t}\wedge\\{{\bf P}{\bf
V}_{i}^{t},\ 1\leq i\neq i^{*}\leq d\\})$ $\displaystyle\leq$ $\displaystyle
I({\bf X}_{i^{*}}\wedge\\{{\bf V}_{i},\ 1\leq i\neq i^{*}\leq d\\})=0,$

i.e., $K_{i^{*}}$ is independent of ${\bf F}$, establishing (23).

Proof of Theorem 4: For every ${\bf x}_{3}\in\\{0,1\\}^{n}$, let ${\cal
F}({\bf x}_{3})$ denote the union of all regular subsets in
$\bigcup_{i=1}^{2^{m}}A_{i}({\bf x}_{3})$. Since ${\cal F}({\bf
x}_{3})\subseteq T_{X_{1}|X_{3},\xi}^{n}({\bf x}_{3})$,

$\displaystyle\Pr\\{{\bf X}_{1}\in{\cal F}({\bf X}_{3})\\}$ $\displaystyle=$
$\displaystyle\Pr\\{{\bf X}_{1}\in T_{X_{1}|X_{3},\xi}^{n}({\bf X}_{3})\\}$
(38) $\displaystyle-\Pr\\{{\bf X}_{1}\in T_{X_{1}|X_{3},\xi}^{n}({\bf
X}_{3})\backslash{\cal F}({\bf X}_{3})\\}.$

It follows from Proposition 1 that $\Pr\\{{\bf X}_{1}\in
T_{X_{1}|X_{3},\xi}^{n}({\bf X}_{3})\\}$ goes to 1 exponentially rapidly in
$n$. We show below that $\Pr\\{{\bf X}_{1}\in T_{X_{1}|X_{3},\xi}^{n}({\bf
X}_{3})\backslash{\cal F}({\bf X}_{3})\\}$ goes to 0 exponentially rapidly in
$n$.

Recall that the number of different joint types of pairs in
$\\{0,1\\}^{n}\times\\{0,1\\}^{n}$ does not exceed $(n+1)^{4}$. Thus,

$\displaystyle\left|\\{{\bf x}_{1}:{\bf x}_{1}\in T_{X_{1}|X_{3},\xi}^{n}({\bf
x}_{3})\backslash{\cal F}({\bf x}_{3})\\}\right|$ $\displaystyle\leq$
$\displaystyle 2^{m}\cdot(n+1)^{4}\cdot 2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$ $\displaystyle<$
$\displaystyle(n+1)^{4}\cdot
2^{n[H(X_{1}|X_{3})+\varepsilon-\varepsilon^{\prime}]},$

where the previous inequality is from
$m<n[h(p)+\varepsilon]=n[H(X_{1}|X_{2},X_{3})+\varepsilon]$.

Since $P_{X_{1}|X_{3}}^{n}({\bf x}_{1}|{\bf x}_{3})\leq
2^{-n[H(X_{1}|X_{3})-2\xi]}$, $({\bf x}_{1},{\bf x}_{3})\in
T_{X_{1}X_{3},\xi}^{n}$, we get

$\Pr\\{{\bf X}_{1}\in T_{X_{1}|X_{3},\xi}^{n}({\bf X}_{3})\backslash{\cal
F}({\bf X}_{3})\\}<(n+1)^{4}\cdot
2^{-n(\varepsilon^{\prime}-2\xi-\varepsilon)}.$

Choosing $\varepsilon^{\prime}>2\xi+\varepsilon$, $\Pr\\{{\bf X}_{1}\in
T_{X_{1}|X_{3},\xi}^{n}({\bf X}_{3})\backslash{\cal F}({\bf X}_{3})\\}$ goes
to 0 exponentially rapidly. Therefore, it follows from (38) that $\Pr\\{{\bf
X}_{1}\in{\cal F}({\bf X}_{3})\\}$ goes to 1 exponentially rapidly in $n$,
with an exponent depending on $(\xi,\varepsilon,\varepsilon^{\prime})$.

By the PK construction scheme for Model 4,

$\displaystyle\Pr\\{K_{1}\neq K_{2}\\}$ $\displaystyle=$
$\displaystyle\Pr\\{K_{1}\neq K_{2},{\bf X}_{1}\in{\cal F}({\bf
x}_{3})\\}+\Pr\\{K_{1}\neq K_{2},{\bf X}_{1}\not\in{\cal F}({\bf x}_{3})\\}$
$\displaystyle\leq$ $\displaystyle\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf
X}_{1},{\bf X}_{1}\in{\cal F}({\bf x}_{3})\\}+\Pr\\{{\bf X}_{1}\not\in{\cal
F}({\bf x}_{3})\\}$ $\displaystyle\leq$ $\displaystyle\Pr\\{{\hat{\bf
X}_{2}}(1)\neq{\bf X}_{1}\\}+\Pr\\{{\bf X}_{1}\not\in{\cal F}({\bf
X}_{3})\\}.$

Since $\Pr\\{{\hat{\bf X}_{2}}(1)\neq{\bf X}_{1}\\}<2^{-n\eta}$ by the
observation in the previous paragraph, we have

$\Pr\\{K_{1}\neq K_{2}\\}<2^{-n\eta^{\prime}},$

for some
$\eta^{\prime}=\eta^{\prime}(\eta,\xi,\varepsilon,\varepsilon^{\prime})>0$ and
for all $n$ sufficiently large, which is (28).

Next, we shall show that $K_{1}$ satisfies (30). For ${\bf
x}_{3}\in\\{0,1\\}^{n}$ and $1\leq k\leq 2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$, it is clear by choice that

$\Pr\\{K_{1}=k|{\bf X}_{1}\not\in{\cal F}({\bf x}_{3}),{\bf X}_{3}={\bf
x}_{3}\\}=2^{-n[I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime}]},$

and that

$\displaystyle\Pr\\{K_{1}=k|{\bf X}_{1}\in{\cal F}({\bf x}_{3}),{\bf
X}_{3}={\bf x}_{3}\\}$ $\displaystyle=$ $\displaystyle\frac{\Pr\\{K_{1}=k,{\bf
X}_{1}\in{\cal F}({\bf x}_{3})|{\bf X}_{3}={\bf x}_{3}\\}}{\Pr\\{{\bf
X}_{1}\in{\cal F}({\bf x}_{3})|{\bf X}_{3}={\bf x}_{3}\\}}$ $\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{2^{m}}\sum_{j=1}^{N_{i}({\bf
x}_{3})}\Pr\\{{\bf X}_{1}={\bf b}_{i,j,k}({\bf x}_{3})|{\bf X}_{3}={\bf
x}_{3}\\}}{\sum_{i=1}^{2^{m}}\sum_{j=1}^{N_{i}({\bf x}_{3})}2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}\Pr\\{{\bf X}_{1}={\bf b}_{i,j,k}({\bf
x}_{3})|{\bf X}_{3}={\bf x}_{3}\\}}$ $\displaystyle=$ $\displaystyle
2^{-n[I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime}]},$

where the second equality is due to every regular subset consisting of
sequences of the same joint type with ${\bf x}_{3}$. Therefore,

$\displaystyle\Pr\\{K_{1}=k\\}=\sum_{{\bf
x}_{3}\in\\{0,1\\}^{n}}\Pr\\{K_{1}=k,{\bf X}_{3}={\bf x}_{3}\\}$ (39)
$\displaystyle=$ $\displaystyle\sum_{{\bf x}_{3}\in\\{0,1\\}^{n}}[\Pr\\{{\bf
X}_{1}\in{\cal F}({\bf x}_{3}),{\bf X}_{3}={\bf x}_{3}\\}\times$
$\displaystyle\Pr\\{K_{1}=k|{\bf X}_{1}\in{\cal F}({\bf x}_{3}),{\bf
X}_{3}={\bf x}_{3}\\}$ $\displaystyle+\Pr\\{{\bf X}_{1}\not\in{\cal F}({\bf
x}_{3}),{\bf X}_{3}={\bf x}_{3}\\}\times$ $\displaystyle\Pr\\{K_{1}=k|{\bf
X}_{1}\not\in{\cal F}({\bf x}_{3}),{\bf X}_{3}={\bf x}_{3}\\}]$
$\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]},$

i.e., $K_{1}$ is uniformly distributed on ${\cal
K}_{1}=\left\\{1,\cdots,2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}\right\\}$, with

$\frac{1}{n}H(K_{1})=I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime},$

which is (31).

It remains to show that $K_{1}$ satisfies (29) with $({\bf X}_{3},{\bf
F})=({\bf X}_{3},{\bf P}{\bf X}_{1}^{t})$. For ${\bf x}_{3}\in\\{0,1\\}^{n}$,
$1\leq i\leq 2^{m}$ and $1\leq k\leq 2^{n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$, we have

$\displaystyle\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf
X}_{1}\not\in{\cal F}({\bf x}_{3}),{\bf X}_{3}={\bf x}_{3}\\}$
$\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$

by choice, and

$\displaystyle\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf
X}_{1}\in{\cal F}({\bf x}_{3}),{\bf X}_{3}={\bf x}_{3}\\}$ $\displaystyle=$
$\displaystyle\frac{\Pr\\{K_{1}=k,{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf
e}_{i}^{t},{\bf X}_{1}\in{\cal F}({\bf x}_{3})|{\bf X}_{3}={\bf
x}_{3}\\}}{\Pr\\{{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf
X}_{1}\in{\cal F}({\bf x}_{3})|{\bf X}_{3}={\bf x}_{3}\\}}$ $\displaystyle=$
$\displaystyle\frac{\sum_{j=1}^{N_{i}({\bf x}_{3})}\Pr\\{{\bf X}_{1}={\bf
b}_{i,j,k}({\bf x}_{3})|{\bf X}_{3}={\bf x}_{3}\\}}{\sum_{j=1}^{N_{i}({\bf
x}_{3})}2^{n[I(X_{1}\wedge X_{2}|X_{3})-\varepsilon^{\prime}]}\Pr\\{{\bf
X}_{1}={\bf b}_{i,j,k}({\bf x}_{3})|{\bf X}_{3}={\bf x}_{3}\\}}$
$\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}.$

Hence,

$\displaystyle\Pr\\{K_{1}=k|{\bf P}{\bf X}_{1}^{t}={\bf P}{\bf e}_{i}^{t},{\bf
X}_{3}={\bf x}_{3}\\}$ $\displaystyle=$ $\displaystyle 2^{-n[I(X_{1}\wedge
X_{2}|X_{3})-\varepsilon^{\prime}]}$ $\displaystyle=$
$\displaystyle\Pr\\{K_{1}=k\\},$

where the previous equality follows from (39). Thus, $K_{1}$ is independent of
$({\bf X}_{3},{\bf F})$, establishing (29).

##  V Implementation with LDPC Codes

We outline an implementation using LDPC codes (cf. e.g., [21], [30], [34],
[31]) of the scheme for the construction of a SK for Model 1 in Section III.
As will be indicated below, similar implementations can be applied to Models
2–4 as well.

###  V-A SK construction

Without any loss of generality, we consider a systematic $(n,n-m)$ LDPC code
${\cal C}$ with generator matrix ${\bf G}=[{\bf I}_{n-m}\ {\bf A}]$, where
${\bf I}_{n-m}$ is an $(n-m)\times(n-m)$-identity matrix and ${\bf A}$ is an
$(n-m)\times m$-matrix. Then, the parity check matrix for ${\cal C}$ is ${\bf
P}=[{\bf A}^{t}\ {\bf I}_{m}]$, where ${\bf I}_{m}$ is an $m\times m$-identity
matrix. The first $n-m$ bits of every codeword in ${\cal C}$, namely the
information bits, are pairwise distinct. Further, since the coset with coset
leader ${\bf e}_{i}$, $1\leq i\leq 2^{m}$, must contain the sequence ${\bf
b}_{i}=[{\bf 0}_{n-m}\ {\bf e}_{i}{\bf P}^{t}]$, with ${\bf 0}_{n-m}$ denoting
a sequence of $n-m$ zeros, the first ($n-m$)-bit-segments of the sequences in
the coset $\\{{\bf b}_{i}\oplus{\bf c},\ {\bf c}\in{\cal C}\\}$ are pairwise
distinct.

Terminal $1$ transmits the syndrome ${\bf P}{\bf x}_{1}^{t}$, whereupon
terminal $2$, knowing $({\bf x}_{2},{\bf P}{\bf x}_{1}^{t})$, applies the
belief-propagation algorithm described in [19] to estimate ${\hat{\bf
x}_{2}}(1)$. Since the first $n-m$ bits of the sequences in each coset are
pairwise distinct, these bits can serve as the index of a sequence in its
coset. Then, terminal $1$ (resp. 2) sets $K_{1}$ (resp. $K_{2}$) as the first
$n-m$ bits of ${\bf x}_{1}$ (resp. ${\hat{\bf x}_{2}}(1)$).

The same implementation of the SW data compression scheme above holds for
Models 2 and 4, too. It can be applied repeatedly also for the successive
estimates (20) in Model 3. In Model 3, $K_{i^{*}}$ (resp. $K_{i}$, $i\neq
i^{*}$) is set as the first $n-m$ bits of ${\bf x}_{i^{*}}$ (resp. ${\hat{\bf
x}_{i}}(i^{*})$). It should be noted that the current complexity of generating
regular subsets in Models 2 and 4 poses a hurdle for explicit efficient
constructions of a SK and a PK, respectively, for these models.

###  V-B Simulation Results

We provide simulation results for the tradeoff between the relative secret key
rate (i.e., the difference between the SK capacity and the rate of the
generated SK) and the rate of generating unequal SKs at different terminals
(corresponding to the bit error rate in SK-matching), when LDPC codes are used
for SK construction in Model 1.

For the purpose of comparison, three different LDPC codes were used: (i) a
$(3,4)$-regular LDPC code; (ii) a $(3,6)$-regular LDPC code; and (iii) an
irregular LDPC code with degree distribution pair (cf. [19])

$\displaystyle\lambda(x)$ $\displaystyle=$ $\displaystyle
0.234029x+0.212425x^{2}+0.146898x^{5}$
$\displaystyle+0.102840x^{6}+0.303808x^{19},$ $\displaystyle\rho(x)$
$\displaystyle=$ $\displaystyle 0.71875x^{7}+0.28125x^{8},$

with a common codeword length of $10^{3}$ bits, and upto 60 iterations of the
belief-propagation algorithm were allowed. Over $10^{3}$ blocks were
transmitted from terminal 1.

Simulation results are shown in Figures 1 and 2, where conditional entropy
(i.e., $H(X_{1}|X_{2})=h(p)$) is plotted against key bit error rate (KBER). We
note that in this simulation SKs are generated at fixed rates that are equal
to the rates of the LDPC codes used. Since for Model 1, SK capacity equals
$1-h(p)$, the conditional entropy $h(p)$ serves as an indicator of the gap
between SK capacity and the rate of the generated SK.

Figure 1 shows the performance of the $(3,6)$-regular and the irregular LDPC
codes; Figure 2 shows the performance of the $(3,4)$-regular LDPC code. It is
seen in both figures that KBER increases with $h(p)$. Since SK capacity
decreases with increasing $h(p)$, an increase of $h(p)$ narrows the gap
between SK capacity and the rate of the generated SK, but raises the
likelihood of generating unequal SKs at the two terminals.

It is seen from Figure 1 that the irregular LDPC code outperforms the
$(3,6)$-regular LDPC code. For instance, for a fixed crossover probability
$p=0.068$, say, and $h(p)\approx 0.3584$, the KBER for the irregular LDPC code
is as low as $10^{-5}$, while the KBER for the $(3,6)$-regular LDPC code is
only about $4\times 10^{-3}$.

Figure 1: Simulation results for the $(3,6)$-regular and the irregular LDPC
codes.

Figure 2: Simulation results for the $(3,4)$-regular LDPC code.

##  VI Discussion

We have considered four simple secrecy generation models involving multiple
terminals, and propose a new approach for constructing SKs and PKs. This
approach is based on Wyner’s well-known SW data compression code for sources
connected by virtual channels with additive independent noise.

In all the models considered in this paper, the i.i.d. sequences observed at
the different terminals possesses the following structure: They can be
described in terms of sequences at pairs of terminals where each terminal in a
pair is connected to the other terminal by a virtual communication channel
with additive independent noise.

There are two steps in the SK construction schemes. The first step constitutes
SW data compression for the purpose of common randomness generation at the
terminals. Although the existence of linear data compression codes with rate
arbitrarily close to the SW bound has been long known for arbitrarily
correlated sources [5], constructions of such linear data compression codes
are understood in terms of the cosets of linear error-correction codes for the
virtual channel, say $P_{X_{1}|X_{2}}$, only when this virtual channel is
characterized by (independent) additive noise [37]. For instance, when two
terminals are connected by a virtual BSC $P_{X_{1}|X_{2}}$, a linear data
compression code, which attains the SW rate $H(X_{1}|X_{2})$ for terminal 2 to
reconstruct the signal at terminal 1, is then provided by a linear channel
code which achieves the capacity of the BSC $P_{X_{1}|X_{2}}$.

When the i.i.d. sequences observed at terminals 1 and 2 are arbitrarily
correlated, the associated virtual communication channel $P_{X_{1}|X_{2}}$
connecting them is no longer symmetric and corresponds to a virtual channel
with input-dependent noise. In this case, while linear codes are no longer
rate-optimal for the given channel [10], linear code constructions for a
suitably enlarged “semisymmetric” channel that are used for SW data
compression [14] could pave the way for devising schemes for SK construction.

The second step in the SK construction schemes involves SK extraction from the
previously acquired CR. It has been shown [25] that for the special case of a
two-terminal source model, this extraction can be accomplished by means of a
linear transformation. However, it is unknown yet whether this holds also for
a general source model with more than two terminals.

## Appendix A: Proof of Proposition 1

We shall prove (7) here. The proof of (8), which is similar, is omitted. Fix
$\delta>0$ and consider the set $T_{[P_{X}]_{\delta}}^{n}$ of sequences in
${\cal X}^{n}$ which are $P_{X}$-typical with constant $\delta$ (cf. [6, p.
33]), i.e.,

$T_{[P_{X}]_{\delta}}^{n}=\\{{\bf x}\in{\cal X}^{n}:\max_{a\in{\cal X}}|P_{\bf
x}(a)-P_{X}(a)|\leq\delta\\}.$

Since $T_{[P]_{\delta}}^{n}$ is the union of the sets of those types
$\tilde{P}$ of sequences in ${\cal X}^{n}$ that satisfy

$\max_{a\in{\cal X}}|\tilde{P}(a)-P_{X}(a)|\leq\delta,$ (A.1)

we have

$\displaystyle\sum_{{\bf
x}\in\left(T_{[P_{X}]_{\delta}}^{n}\right)^{c}}P_{X}^{n}({\bf x})$ (A.2)
$\displaystyle=$ $\displaystyle\sum_{\tilde{P}:\max_{a\in{\cal
X}}|\tilde{P}(a)-P_{X}(a)|>\delta}P_{X}^{n}\left(\\{{\bf x}:P_{\bf
x}=\tilde{P}\\}\right)$ $\displaystyle\leq$ $\displaystyle(n+1)^{|{\cal
X}|}\cdot 2^{-n\min_{\tilde{P}:\min_{a\in{\cal
X}}|\tilde{P}(a)-P_{X}(a)|>\delta}D(\tilde{P}||P_{X})},$

using the fact that $P_{X}^{n}(\\{{\bf x}:P_{\bf x}=\tilde{P}\\})\leq
2^{-nD(\tilde{P}||P)}$ (cf. [6, Lemma 2.6]).

Next, by Pinsker’s inequality (cf. e.g., [6, p. 58]),

$\displaystyle D(\tilde{P}||P)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2ln2}\left(\min_{a\in{\cal
X}}|\tilde{P}(a)-P_{X}(a)|\right)^{2}$ (A.3) $\displaystyle\geq$
$\displaystyle\frac{\delta^{2}}{2ln2},$

with the previous inequality holding for every $\tilde{P}$ in (A.1). It
follows from (A.2) and (A.3) that

$\sum_{{\bf x}\in T_{[P]_{\delta}}^{n}}P_{X}^{n}({\bf x})\geq 1-(n+1)^{|{\cal
X}|}\cdot 2^{-n\frac{\delta^{2}}{2ln2}}$ (A.4)

for all $n\geq 1$.

Finally, observe that

$T_{[P_{X}]_{\delta}}^{n}\subseteq T_{X,\xi}^{n},\ \ {\rm if}\ \
\xi=\delta\left[\sum_{a\in{\cal X}}\log\frac{1}{P_{X}(a)}\right],$ (A.5)

which is readily seen from the fact that for each ${\bf x}\in{\cal X}^{n}$,

$\displaystyle-\frac{1}{n}\log P_{X}^{n}({\bf x})-H(P_{X})$ $\displaystyle=$
$\displaystyle-\frac{1}{n}\log\left(2^{-n[H(P_{\bf x})+D(P_{\bf
x}||P_{X})]}\right)-H(P_{X})$ $\displaystyle=$ $\displaystyle H(P_{\bf
x})+D(P_{\bf x}||P_{X})-H(P_{X})$ $\displaystyle=$ $\displaystyle H(P_{\bf
x})-H(P_{\bf x})+\sum_{a\in{\cal X}}P_{\bf
x}(a)\log\frac{1}{P_{X}(a)}-H(P_{X})$ $\displaystyle=$
$\displaystyle\sum_{a\in{\cal X}}[P_{\bf
x}(a)-P_{X}(a)]\log\frac{1}{P_{X}(a)}.$

Clearly, (A.4) and (A.5) imply (7).

## Appendix B: Proof of Proposition 2

The proof of Proposition 2 relies on the following lemma concerning the
average error probability of maximum likelihood decoding.

A sequence ${\bf u}\in\\{0,1\\}^{n}$ is called a descendent of a sequence
${\bf v}\in\\{0,1\\}^{n}$ if $u_{i}=1$ implies that $v_{i}=1$, $1\leq i\leq
n$. A subset ${\Omega}\subset\\{0,1\\}^{n}$ is called quasiadmissible if the
conditions that ${\bf u}\in\Omega$ and ${\bf u}$ is a descendent of ${\bf v}$
together imply that ${\bf v}\in\Omega$.

Lemma 2 [22]: If $\Omega$ is a quasiadmissible subset of $\\{0,1\\}^{n}$, then
for $0\leq p\leq 1$,

$\frac{d\mu_{p}(\Omega)}{dp}>0,$

where

$\mu_{p}({\Omega})=\sum_{{\bf x}\in\Omega}p^{w_{H}({\bf
x})}(1-p)^{n-w_{H}({\bf x})},$

with $w_{H}({\bf x})$ denoting the Hamming weight of ${\bf x}$.

For a binary linear code, let ${\bf E}$ denote the set of coset leaders. It is
known (cf. [28, Theorem 3.11]) that
$\Omega^{\prime}=\\{0,1\\}^{n}\backslash{\bf E}$ is a quasiadmissible subset
of $\\{0,1\\}^{n}$. If a binary linear code is used on BSC($p$), the average
error probability of maximum likelihood decoding is given by (cf. [32, Theorem
5.3.3])

$\mu_{p}(\Omega^{\prime})=\sum_{{\bf x}\in\Omega^{\prime}}p^{w_{H}({\bf
x})}(1-p)^{n-w_{H}({\bf x})}.$

Lemma 2 implies that if the same binary linear code is used on two binary
symmetric channels with different crossover probabilities, say,
$0<p_{1}<p_{2}<\frac{1}{2}$, then the average error probability of maximum
likelihood decoding for a BSC($p_{1}$) is strictly less than that for a
BSC($p_{2}$); note that a BSC($p_{2}$) is a degraded version of a
BSC($p_{1}$), being a cascade of the latter and a
BSC($\frac{p_{2}-p_{1}}{1-2p_{1}}$).

Returning to the proof of Proposition 2, it follows from Lemma 1 that for some
$\eta>0$ and for all $n$ sufficiently large,

$\Pr\\{{\hat{\bf X}_{j^{*}}}(i^{*})\neq{\bf X}_{i^{*}}\\}<2^{-n\eta}.$

Recall that $p_{(i^{*},j^{*})}=\max_{(i,j)\in E({\cal T})}p_{(i,j)}$ and
$(i=i_{0},i_{1},\cdots,i_{r}=i^{*})$ is the path from $i$ to $i^{*}$. It
follows by Lemma 2 that

$\Pr\\{{\hat{\bf X}_{i}}(i_{1})\neq{\bf X}_{i_{1}}\\}<\Pr\\{{\hat{\bf
X}_{j^{*}}}(i^{*})\neq{\bf X}_{i^{*}}\\}<2^{-n\eta}.$

Consequently,

$\displaystyle\Pr\\{{\hat{\bf X}_{i}}(i_{2})\neq{\bf X}_{i_{2}}\\}$
$\displaystyle\leq$ $\displaystyle\Pr\\{{\hat{\bf X}_{i}}(i_{2})\neq{\bf
X}_{i_{2}},{\hat{\bf X}_{i}}(i_{1})\neq{\bf X}_{i_{1}}\\}$
$\displaystyle+\Pr\\{{\hat{\bf X}_{i}}(i_{2})\neq{\bf X}_{i_{2}},{\hat{\bf
X}_{i}}(i_{1})={\bf X}_{i_{1}}\\}$ $\displaystyle<$ $\displaystyle 2\cdot
2^{-n\eta}.$

Continuing this procedure, we have finally that

$\Pr\\{{\hat{\bf X}_{i}}(i^{*})\neq{\bf X}_{i^{*}}\\}<r\cdot 2^{-n\eta}<d\cdot
2^{-n\eta}.$

## References

  * [1] A. Aaron and B. Girod, “Compression with side information using turbo codes,” Proc. IEEE Data Compression Conference, pp. 252–261, Snowbird, UT, Apr. 2002.
  * [2] R. Ahlswede and I. Csiszár, “Common randomness in information theory and cryptography, Part I: Secret sharing,” IEEE Trans. Inf. Theory, vol. 39, pp. 1121–1132, July 1993.
  * [3] M. Bloch, J. Barros, M. Rodrigues, S.W.M. McLaughlin, “Wireless Information Theoretic Security,” IEEE Trans. on Inf. Theory, Vol. 54, No. 6, pp. 2515–2534, June, 2008.
  * [4] T. P. Coleman, A. H. Lee, M. Médard, and M. Effros, “On some new approaches to practical Slepian-Wolf compression inspired by channel coding,” Proc. IEEE Data Compression Conference, pp. 282–291, Snowbird, UT, March 2004.
  * [5] I. Csiszár, “Linear codes for sources and source networks: Error exponents, universal coding,” IEEE Trans. Inf. Theory, vol. 28, no. 4, pp. 585–592, July, 1982.
  * [6] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic, New York, N.Y., 1982.
  * [7] I. Csiszár and P. Narayan, “Common randomness and secret key generation with a helper,” IEEE Trans. Inf. Theory, vol. 46, pp. 344–366, March 2000.
  * [8] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,” IEEE Trans. Inf. Theory, vol. 50, pp. 3047–3061, Dec. 2004.
  * [9] P. Elias, “Coding for noisy channels,” IRE Convention Record, Part 4, pp. 37–46, 1955.
  * [10] E. M. Gabidulin, “Bounds for the probability of decoding error when using linear codes over memoryless channels,” Prob. Pered. Inf., vol. 3, pp. 55–62, 1967.
  * [11] J. Garcia-Frias and Y Zhao, “Compression of correlated binary sources using turbo codes,” IEEE Commun. Lett., vol. 5, pp. 417–419, Oct. 2001.
  * [12] J. Garcia-Frias and W. Zhong, “LDPC codes for compression of multi-terminal sources with hidden Markov correlation,” IEEE Commun. Lett., vol. 7, no. 3, pp. 115–117, March 2003.
  * [13] H.O. Georgii, Gobbs Measures and Phase Transitions. de Gruyter, Berlin – New York, 1988.
  * [14] D-K. He and E-H. Yang, “On the duality between Slepian-Wolf coding and channel coding,” Proc. Int. Symp. Inf. Theory, pp. 2546–2550, Seattle, WA, July 2006.
  * [15] R. Hu, R. Viswanathan and J. Li, “A new coding scheme for the noisy-channel Slepian-Wolf problem: Separate design and joint decoding,” Proc. Global Commun. Conference, Dallas, TX, 2004.
  * [16] J. Li, Z. Tu, and R. Blum, “Slepian-Wolf coding for nonuniform sources using turbo codes,” Proc. IEEE Data Compression Conference, pp. 312–321, Snowbird, UT, March 2004.
  * [17] C. Lan, A. Liveris, K. Narayanan, Z. Xiong, and C. N. Georghiades, “Slepian-Wolf coding of multiple M-ary sources using LDPC codes”, Proc. IEEE Data Compression Conference, p. 549, Snowbird, UT, March 2004.
  * [18] Y. Liang, H.V. Poor and S. Shamai (Shitz), “Information Theoretic Security,” Foundations and Trends in Communications and Information Theory, vol. 5, no. 4-5, pp. 355-580, Now Publishers, MA, USA, 2008.
  * [19] A. D. Liveris, Z. Xiong, C. N. Georghiades, “Compression of binary sources with side information at the decoding using LDPC codes,” IEEE Commun. Lett., vol. 6, pp. 440–442, Oct. 2002.
  * [20] A. D. Liveris, C. Lan, K. R. Narayanan, Z. Xiong and C. N. Georghiades, “Slepian-Wolf coding of three binary sources using LDPC codes,” Proc. Int. Symp. Turbo Codes and Related Topics, Brest, France, Sept. 2003.
  * [21] D. J. C. Mackay, “Good error correcting codes based on very sparse matrices,” IEEE Trans. Inf. Theory, vol. 45, pp. 399–431, Mar. 1999.
  * [22] G. A. Margulis, “Probabilistic characteristics of graphs with large connectivity,” Probl. Inf. Trans. vol. 10, pp. 174–179, Apr. 1974\.
  * [23] U. M. Maurer, “Secret key agreement by public discussion from common information,” IEEE Trans. Inf. Theory, vol. 39, pp. 733–742, May 1993.
  * [24] P. Mitran and J. Bajcsy, “Turbo source coding: A noise-robust approach to data compression,” IEEE Data Compression Conference, p. 465, Snowbird, UT, Apr. 2002.
  * [25] J. Muramatsu, “Secret key agreement from correlated source outputs using LDPC matrices,” IEICE Trans. Fundamentals, vol. E89-A, pp. 2036–2046, July, 2006.
  * [26] S. Nitinawarat, “Secret key generation for correlated Gaussian sources,” Proc. Allerton Conf. Commun., Control, and Computing, Monticello, Illinois, pp. 1054-1058, Sept. 2007.
  * [27] S. Nitinawarat, “Secret key generation for correlated Gaussian sources”, Proc. IEEE Int. Symp. Inf. Theory, pp. 702–706, Toronto, Canada, July, 2008.
  * [28] W. W. Peterson and E. J. Weldon, Error-Correcting Codes, 2nd edition, MIT Press: Cambridge, Mass. 1972.
  * [29] S. S. Pradhan and K. Ramchandran, “Distributed source coding using syndromes (DISCUS): Design and construction,” IEEE Trans. Inf. Theory, vol. 49, pp. 626–643, March 2003.
  * [30] T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. Inf. Theory, vol. 47, pp. 599–618, Feb. 2001.
  * [31] T. Richardson and R. Urbanke, Modern Coding Theory, New York: Cambridge, 2008.
  * [32] S. Roman, Introduction to Coding and Information Theory, New York: Springer, 1996.
  * [33] D. Schonberg, K. Ramchandran and S. S. Pradhan, “Distributed code constructions for the entire Slepian-Wolf rate region for arbitrarily correlated sources,” Proc. IEEE Data Compression Conference, pp. 292–301 Snowbird, UT, March 2004.
  * [34] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory, vol. 27, pp. 533–547, Sept. 1981.
  * [35] A. Thangaraj, S. Dihidar, A. R. Calderbank, S. McLaughlin and J. M. Merolla, “Capacity achieving codes for the wiretap channel with applications to quantum key distribution,” e-print cs. IT/0411003, 2004\.
  * [36] R. Wilson, D. Tse and R. Scholtz, “Channel identification: Secret sharing using reciprocity in ultrawideband channels,” IEEE Trans. Inf. Foren. and Security, vol. 2, pp. 364–375, Sept. 2007.
  * [37] A. D. Wyner, “Recent results in the Shannon theory,” IEEE Trans. Inf. Theory, vol. 20, pp. 2–10, Jan. 1974.
  * [38] C. Ye and P. Narayan, “Secret key and private key constructions for simple multiterminal source models,” Proc. IEEE Int. Symp. Inf. Theory, pp. 2133–2137, Adelaide, Australia, Sept. 2005.
  * [39] C. Ye and P. Narayan, “Secret key constructions for simple multiterminal source models,” Proc. Inf. Theory and Applications Workshop, San Diego, California, Feb. 2006.

  * [40] C. Ye, A. Reznik and Y. Shah, “Extracting secrecy from jointly Gaussian random variables,” _Proc. Int. Symp. Inf. Theory_ , pp. 2593–2597, July 2006.
  * [41] C. Ye, S. Mathur, A. Reznik, Y. Shah, W. Trappe and N. Mandayam, “Information theoretic secret key generation from wireless channels,” IEEE Trans. Inf. Foren. and Security, vol. 5, pp. 240-254, June 2010.
  * [42] R. W. Yeung, Information Theory and Network Coding, New York: Springer, 2008.