The Vault

Secret Key Generation for a Pairwise Independent Network Model
Research Paper / Jan 2010

6482 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 56, NO. 12, DECEMBER 2010

Secret Key Generation for a Pairwise
Independent Network Model

Sirin Nitinawarat, Student Member, IEEE, Chunxuan Ye, Senior Member, IEEE, Alexander Barg, Fellow, IEEE,
Prakash Narayan, Fellow, IEEE, and Alex Reznik, Member, IEEE

Abstract—We consider secret key generation for a “pairwise in-
dependent network” model in which every pair of terminals ob-
serves correlated sources that are independent of sources observed
by all other pairs of terminals. The terminals are then allowed to
communicate publicly with all such communication being observed
by all the terminals. The objective is to generate a secret key shared
by a given subset of terminals at the largest rate possible, with
the cooperation of any remaining terminals. Secrecy is required
from an eavesdropper that has access to the public interterminal
communication. A (single-letter) formula for secret key capacity
brings out a natural connection between the problem of secret key
generation and a combinatorial problem of maximal packing of
Steiner trees in an associated multigraph. An explicit algorithm is
proposed for secret key generation based on a maximal packing of
Steiner trees in a multigraph; the corresponding maximum rate of
Steiner tree packing is thus a lower bound for the secret key ca-
pacity. When only two of the terminals or when all the terminals
seek to share a secret key, the mentioned algorithm achieves secret
key capacity in which case the bound is tight.

Index Terms—PIN model, private key, public communication,
secret key capacity, security index, spanning tree packing, Steiner
tree packing, wiretap secret key.

I. INTRODUCTION

S UPPOSE that terminals observe distinct but cor-related signals with the feature that every pair of terminals
observes a corresponding pair of correlated signals that are in-
dependent of all other pairs of signals. Following these obser-
vations, all the terminals can communicate interactively over
a public noiseless channel of unlimited capacity, with all such
communication being observed by all the terminals. The goal is
to generate a secret key (SK), i.e., secret common randomness,
for a given subset of the terminals in at the
largest rate possible, with secrecy being required from an eaves-
dropper that observes the public interterminal communication.

Manuscript received November 06, 2009; revised July 20, 2010. Date of
current version November 19, 2010. The work of S. Nitinawarat and P. Narayan
was supported by the National Science Foundation by Grants CCF0515124,
CCF0635271, CCF0830697, and InterDigital. The work of A. Barg was
supported by the National Science Foundation by Grants CCF0515124,
CCF0830699, CCF0916919, DMS0807411, and InterDigital. The material in
this paper was presented at the IEEE International Symposium on Information
Theory, Nice, France, June 2007, and at the IEEE International Symposium on
Information Theory, Toronto, ON, Canada, July 2008.

S. Nitinawarat, A. Barg, and P. Narayan are with the Department of Elec-
trical and Computer Engineering and the Institute for Systems Research, Univer-
sity of Maryland, College Park, MD 20742 USA (e-mail: nitinawa@umd.edu;
abarg@umd.edu; prakash@umd.edu).

C. Ye and A. Reznik are with InterDigital, King of Prussia, PA 19406 USA
(e-mail: Chunxuan.Ye@interdigital.com; Alex.Reznik@interdigital.com).

Communicated by E. Erkip, Associate Editor for Shannon Theory.
Digital Object Identifier 10.1109/TIT.2010.2081210

All the terminals in cooperate in generating the SK for the
secrecy-seeking set .

This model for SK generation, called a “pairwise independent
network” model, was introduced in [23] (see also [22]). Abbre-
viated hereafter as the PIN model, it is motivated by practical as-
pects of a wireless communication network in which terminals
communicate on the same frequency. In a typical multipath en-
vironment, the wireless channel between each pair of terminals
produces a random mapping between the transmitted and re-
ceived signals which is time-varying and location-specific. For
a fixed time and location, this mapping is reciprocal, i.e., ef-
fectively the same in both directions. Also, the mapping decor-
relates over different time-coherence intervals as well as over
distances of the order of a few wavelengths.

The PIN model is, in fact, a special case of a general multiter-
minal “source model” for secrecy generation studied by Csiszár
and Narayan [4]. The latter followed leading investigations by
Maurer [13], [14] and Ahlswede and Csiszár [1] of SK gener-
ation by two terminals from their correlated observations com-
plemented by public communication.

A single-letter characterization of secret key capacity—the
largest rate at which secrecy can be generated—for the terminals
in an arbitrary subset of was provided in [4]. A particular-
ization of this (general) SK capacity formula to our PIN model
displays the special feature that it can be expressed in terms of
a linear combination of mutual information terms that involve
only mutually independent pairs of “reciprocal” random vari-
ables (rvs). Each such mutual information term represents the
maximum rate of an SK that can be generated solely by a cor-
responding pair of terminals from only their own observed sig-
nals using public communication [13], [14], [1]. This observa-
tion leads to the following question that is our main motivation:
Can an SK of optimum rate for the terminals in be generated
by propagating mutually independent and rate-optimal SKs for
pairs of terminals in ?

An examination of this question brings out points of contact
between SK generation for a PIN model and a combinatorial
problem of tree packing in a multigraph. We propose an explicit
algorithm for propagating pairwise SKs for pairs of terminals
in to form a groupwide SK for the terminals in . This al-
gorithm is based on a maximal packing of Steiner trees (for )
in a multigraph associated with the PIN model. Thus, the max-
imum rate of Steiner tree packing in this multigraph is always
a lower bound for SK capacity. This bound is shown to be tight
when the secrecy-seeking set contains only two terminals or
when it consists of all the terminals. In these situations, our al-
gorithm is capacity-achieving. It is of independent interest to
note that given a combinatorial problem of determining the max-

0018-9448/$26.00 © 2010 IEEE



NITINAWARAT et al.: PAIRWISE INDEPENDENT NETWORK MODE 6483

imum rate of Steiner tree packing for in a multigraph, the SK
capacity of an associated PIN model provides, in reciprocity, an
upper bound for the mentioned rate, which is tight for the case

as well as for the spanning tree case .
In the study of secrecy generation for a multiterminal source

model, the notions of wiretap SK [13], [14], [1], [4] and private
key [4] also have been proposed. The former notion corresponds
to the eavesdropper having additional access to a terminal not
in the secrecy-seeking set and from which too the key must
be concealed; this “wiretapped” terminal does not cooperate in
secrecy generation. A single-letter characterization of the cor-
responding capacity remains unresolved in general but for par-
tial results and bounds (cf., e.g., [1], [14], [19], [4], [9], [10],
[5]). The notion of a private key is less restrictive, with the wire-
tapped terminal being allowed to cooperate; the corresponding
capacity is known [4]. We argue in Section IV below that for a
PIN model these two notions correspond to SK generation for
a reduced PIN model, thereby justifying our sole focus on SK
capacity.

Basic concepts and definitions are presented in Section II.
Section III contains statements of our results and proofs;
specifically, the SK capacity for the PIN model is given in
Section III-A, the connection of SK capacity with Steiner tree
packing is treated in Section III-B, and with spanning tree
packing in Section III-C. Concluding remarks and pointers to a
sequel paper are contained in Section IV.

II. PRELIMINARIES

We shall be concerned throughout with a PIN model, which
is a special case of a general multiterminal “source model” for
secrecy generation with public communication (see [14], [1],
[4], [5]). Suppose that terminals , , observe

independent and identically distributed (i.i.d.) repetitions of
the rvs , denoted by , where

, . Each rv ,
is of the form with components,
and the “reciprocal pairs” of rvs
are mutually independent. See Fig. 1. Thus, every pair of termi-
nals in is associated with a corresponding pair of rvs that
are independent of pairs of rvs associated with all the other
pairs of terminals. All the rvs are assumed to take their values
in finite sets. Following their observation of the random se-
quences as above, the terminals in are allowed to communi-
cate among themselves over a public noiseless channel of unlim-
ited capacity; all such communication, which may be interactive
and conducted in multiple rounds, is observed by all the termi-
nals. A communication from a terminal, in general, can be any
function of its observed sequence as well as all previous public
communication. The public communication of all the terminals
will be denoted collectively by .

The overall goal is to generate shared secret common ran-
domness for a given set of terminals at the largest rate
possible, with the remaining terminals (if any) cooperating in
secrecy generation. The resulting secret key must be shared by
every terminal in ; but it need not be accessible to the termi-
nals not in and nor does it need to be concealed from them.
It must, of course, be kept secret from the eavesdropper that has

Fig. 1. The PIN Model.

access to the public interterminal communication , but is oth-
erwise passive, i.e., unable to tamper with this communication.

The following basic concepts and definitions are from [4], [5].
Given , for rvs , , we say that is -recoverable from

if for some function of . With the
rvs and representing a secret key and the eavesdropper’s
knowledge, respectively, information theoretic secrecy entails
that the security index1

be required to be small, where is the range of and
denotes cardinality. This requirement simultaneously renders
to be nearly uniformly distributed and nearly independent of .

Definition 1: Given any set of size a rv
constitutes an -secret key ( -SK) for the set of terminals ,

achievable with communication , if is -recoverable from
for each and, in addition, it satisfies the secrecy

condition

(1)

The condition (1) corresponds to the concept of “strong” se-
crecy in which [15], [4], [5], as distinct from
the earlier “weak” secrecy concept which requires only that

[14], [1].
Definition 2: A number is an achievable SK rate for a set of

terminals if there exist -SKs for , achievable
with communication , such that

and

The largest achievable SK rate for is the SK capacity .
Thus, by definition, the SK capacity for is the largest rate

of a rv that is recoverable at each terminal in from the infor-
mation available to it, and is nearly uniformly distributed and
effectively concealed from an eavesdropper with access to the
public interterminal communication; it need not be concealed
from the terminals in that cooperate in secrecy
generation.

A single-letter characterization of the SK capacity ,
, for a general multiterminal source model, of which

1All logarithms are to the base 2.



6484 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 56, NO. 12, DECEMBER 2010

the PIN model is a special case, is provided in [4]. An upper
bound for in terms of (Kullback-Leibler) divergence is
also given therein and shown to be tight in special cases. These
results play material roles below.

III. RESULTS
Our main results are the following. First, we obtain, upon

particularizing the results of [4], a (single-letter) expression for
for a PIN model, in terms of a linear combination of mu-

tual information terms that involve only pairs of “reciprocal”
rvs . Second, stemming from
this observation, a connection is drawn between SK generation
for the PIN model and the combinatorial problem of maximal
packing of Steiner trees in an associated multigraph. Specifi-
cally, we show that the maximum rate of Steiner tree packing in
the multigraph is always a lower bound for SK capacity. Third,
for the case (when the Steiner tree becomes a path con-
necting the two vertices in ) and for the case (when
the Steiner tree becomes a spanning tree), the previous lower
bound is shown to be tight. This is done by means of an ex-
plicit algorithm, based on maximal path packing and maximal
spanning tree packing, respectively, that forms an SK out of in-
dependent SKs for pairs of terminals. In fact, the maximum rate
of the SK thereby generated equals the previously known upper
bound for SK capacity [4] mentioned above.

A. SK Capacity
We first give the SK capacity for the PIN model. For

, let

and be its subset consisting of those that
contain , . Let be the set of all collections

of weights , satisfying

(2)

Proposition 3.1: For a PIN model, the SK capacity for a set
of terminals , with , is

(3)
Remarks:
i) It is of interest in (3) that the SK capacity for a PIN model

depends on the joint probability distribution of the under-
lying rvs only through a linear combination of the pair-
wise reciprocal mutual information terms.

ii) We note from [4, Th. 3] that additional independent ran-
domization at the terminals in , enabled by giving them
access to the mutually independent rvs ,
respectively, that are independent also of ,
does not serve to enhance SK capacity. Heuristically
speaking, the mentioned independence of the randomiza-
tion forces any additional “common randomness” among

the terminals in to be acquired only through public
communication, which is observed fully by the eaves-
dropper. On the other hand, randomization can serve to
enhance secrecy generation for certain models (cf., e.g.,
[21])

Proof: The proof entails an application of the formula for
SK capacity in [4] and [5] to the PIN model. For ,
denote . From ([5, Th. 3.1])

(4)
For the PIN model, since , we observe
in (4) that

(5)

and

(6)

A straightforward manipulation of (4), using (5), (6), gives

Since by (2)



NITINAWARAT et al.: PAIRWISE INDEPENDENT NETWORK MODE 6485

we get

thereby completing the proof.

An upper bound had been established for SK capacity for a
general multiterminal source model [4, Example 4]. This bound
was expressed in terms of the (Kullback-Leibler) divergence be-
tween the joint distribution of the rvs defining the underlying
correlated sources and the product of the (marginal) distribu-
tions associated with appropriate partitions of these rvs, thereby
measuring the minimum mutual dependence among the latter.
The bound was particularized to the PIN model in [23], and is
restated below in a slightly different form that will be used sub-
sequently.

Let be a partition of , and denote the
number of atoms of by .

Lemma 3.2 [23]: The SK capacity , , for the
PIN model is bounded above according to

crosses

(7)

where for a fixed , a pair of indices crosses if and
are in different atoms of . The minimization in the right side
of (7) is over all partitions of for which every atom of
intersects .

B. SK Capacity and Steiner Tree Packing
There exists a natural connection between SK generation for

the PIN model and the combinatorial problem of tree packing
in an associated multigraph.

Let be a multigraph, i.e., a connected undirected
graph with no selfloops and with multiple edges possible be-
tween any vertex pair, whose vertex set
and edge set , where

is the number of edges connecting the pair of vertices , ,
.

Definition 3: For , a Steiner tree of (for ) is a
subgraph of that is a tree and whose vertex set contains . A
Steiner packing of is any collection of edge disjoint Steiner
trees of . Let denote the maximum size of such a
packing (cf. [11]).

We note that when , a Steiner tree for always con-
tains a path connecting the two vertices in . Clearly, it suffices
to take to be the maximum number of edge disjoint
paths connecting the two terminals in .

Next, assume without any loss of generality in the PIN model
that all pairwise reciprocal mutual information values

, , are rational numbers. Let denote the
collection of positive integers such that the number of edges
between any pair of vertices , is equal to is
integer-valued for all ; clearly, the elements of

form an arithmetic progression. For a PIN model, consider a
sequence of associated multigraphs

, where , , is such that . We
term as the maximum rate of Steiner tree
packing in the multigraph . The connection be-
tween SK generation for the PIN model and Steiner tree packing
is formalized here.

Theorem 3.3: For a PIN model,
i) the SK capacity satisfies

(8)

for every ;
ii) when , the SK capacity is

(9)

Remarks:
i) The inequality in (8) can be strict, as shown by a specific

example in a sequel paper [17]. See also the remark fol-
lowing Theorem 3.4 for a heuristic explanation.

ii) An exact determination of is known to be
NP-hard [3]. A nontrivial upper bound for ,
similar in form to (7), is known [12, para. 5, Sect. 1].
This bound can be extended to yield an upper bound for

which, in general, is inferior to
that provided by in (8).

Proof: i) The proof consists of two main steps. In the first
step, fix an that is smaller than every positive

, . Each pair of terminals , with
, generates a (pairwise) SK of

size bits, using public communication
, and satisfying

(10)
the existence of such an SK follows from [15]. The SK achiev-
ability scheme in [15] consists of a “weak” SK generated by
Slepian–Wolf data compression, followed by “privacy ampli-
fication” to extract a “strong” SK. Note by the definition of
the PIN model that are mutually indepen-
dent.

In the second step, consider the sequence of multigraphs
, where is such that the

number of edges between any pair of vertices , equals
. We next show that every Steiner tree

in a Steiner tree packing of yields one shared bit for the
terminals in that is independent of the communication in that
Steiner tree. Specifically, for edges and , ,
with common vertex in the Steiner tree, vertex broadcasts to



6486 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 56, NO. 12, DECEMBER 2010

vertices , the binary sum of two independent SK bits—one
with and the other with —obtained from the first step. This
enables , , to share any one of these two bits, with the
attribute that the shared bit is independent of the binary sum.
This method of propagation ([4, Proof of Th. 5]) enables all
the vertices in , which are connected in the Steiner tree, to
share one bit that is independent of all the broadcast binary
sums from this tree. Therefore, the maximum number of such
shared bits for the terminals in that can be generated by this
procedure equals . Denote these shared bits (of size

) and the communication messages generated by the
mechanism in this second step by
and , respectively.

We claim that constitutes an SK for . Specifically, it re-
mains to show that satisfies the secrecy condition (1) with
respect to the overall communication in steps 1 and 2. To this
end, we denote by all the pairwise SK
bits generated in the first step, that are residual from the max-
imal Steiner tree packing of used to generate by means
of . Clearly

(11)

Moreover, since the total number of edges in any Steiner tree
equals the sum of unity (i.e., the shared bit of ) and the number
of bits of public communication for that shared bit, we have

(12)

where , and denote the respective ranges of , and
. Note that . Then

where the second-to-last equality is by the fact that
are mutually independent, and the

last equality is by (10). The maximum rate of the SK thus
generated is equal to which, since
was arbitrary, equals

ii) Suppose that , and note from the paragraph
after Definition 3 that is the maximum number of edge
disjoint paths in connecting terminals 1 and 2. It is clear that

is nondecreasing in , by the definition of

. According to Menger’s theorem [16], [2], given a multi-
graph , the maximum number of edge disjoint
paths in connecting terminals 1 and 2 is equal to

number of edges that cross

Applying this to as above, we have that for

It then follows that

The last equality follows upon noting that when , the
minimization in (7) is over only those partitions that contain
two atoms, each of which includes terminal 1 and terminal 2,
respectively. This proves (ii).

C. SK Capacity and Spanning Tree Packing for
When all the terminals in seek a shared SK, i.e., when

, a Steiner tree for is a spanning tree for . In this
case, we show that the lower bound for SK capacity in Theorem
3.3 (i) is, in fact, tight. Specifically, we show that the algorithm
in the proof of Theorem 3.3 yields an SK of maximum rate that
coincides with the upper bound for in Lemma 3.2.

Theorem 3.4: For a PIN model, the SK capacity is

(13)

Remark: When , Steiner tree packing may not attain
SK capacity. In SK generation, a helper terminal in helps link
the user terminals in in complex ways through various com-
binations of subsets of . In general, an optimal such linkage
need not be attained by Steiner tree packing. However, when

, the two user terminals are either directly connected
or are connected by a path through helpers in ; both can be
accomplished by Steiner tree packing. When , the men-
tioned complexity of a helper is nonexistent.

Proof: The proof relies on a graph-theoretic result of Nash-
Williams [18] and Tutte [20], that gives a min max formula for
the maximum size of spanning tree packing in a multigraph.

It is clear that is nondecreasing in ,
by the definition of . By [18] and [20], given a multigraph



NITINAWARAT et al.: PAIRWISE INDEPENDENT NETWORK MODE 6487

, the maximum number of edge disjoint spanning
trees that can be packed in is equal to

number of edges that cross

with the minimization being over all partitions of . Ap-
plying this to as above, we have that for

crosses

Denoting by the quantity in above, it follows that

The assertion in (13) is now immediate.
Last, the following observation is of independent interest.

Given a combinatorial problem of finding the maximal packing
of Steiner trees in a multigraph, we can always associate with it a
problem of SK generation for an associated PIN model. By The-
orem 3.3 i), the SK capacity for the PIN model yields an upper
bound for the maximum rate of edge disjoint Steiner trees that
can be packed in the multigraph; the upper bound is tight both
in the case of path packing by Theorem 3.3 ii) and in the case
of spanning tree packing by Theorem 3.4.

IV. DISCUSSION
Our proofs of Theorems 3.3 and 3.4 give rise to explicit poly-

nomial-time schemes for forming a group-wide SK for the ter-
minals in from the collection of optimum and mutually inde-
pendent SKs for pairs of terminals in (namely the in the
proof of Theorem 3.3). When or , our schemes
achieve SK capacity. Specifically, the schemes combine known
polynomial-time algorithms for finding a maximal collection of
edge-disjoint paths (respectively, spanning trees) connecting the
vertices in when (respectively, ) [6]–[8] with
the technique for SK propagation in each tree as in the proof of
Theorem 3.3.

For a general multiterminal source model, the notions of
wiretap secret key (WSK) [13], [1], [4] and private key (PK)
[4] have also been proposed. Specifically, these notions involve
an extra “wiretapped” terminal, say , that observes
i.i.d. repetitions of a rv with a given joint pmf with

, and to which the eavesdropper has access. The
key must now be concealed from the eavesdropper’s obser-
vations of and the public

communication. The notion of a WSK requires that terminal
not cooperate in key generation. The less restrictive

notion of a PK allows cooperation by terminal by way
of public communication. The corresponding capacities for
the terminals in are defined in the usual manner, and
denoted by and . We remark that in the context
of a PIN model, terminal represents a compromised
entity.

One model for the wiretapped rv entails its con-
sisting of mutually independent components, one
corresponding to each pair , , of
legitimate correlated signals. This model is unresolved even
in the simplest case of terminals [14], [1], [4], [9],
[10]. Instead, we consider a different model which depicts
the situation in which an erstwhile legitimate terminal
becomes compromised. Specifically, the model now involves
every legitimate terminal in observing i.i.d. repetitions
of the rv , while terminal observes i.i.d.
repetitions of . We argue in the
following proposition that the WSK and PK capacities for this
PIN model are the same as the SK capacity of a reduced PIN
model obtained by disregarding terminal and with each
legitimate terminal in observing just .

Proposition 4.1: It holds that

Proof: We shall prove that

The inequality is by definition. Next, let
be a SK for achieved with

communication for the reduced PIN
model. Then is also a WSK since

since , thereby estab-
lishing (a). In order to establish (c), we claim that every
achievable PK rate is an achievable SK rate for the reduced
PIN model upon using randomization at the terminals in ;
by Remark ii) after Proposition 3.1, (c) then follows. Since

is independent of , any
terminal in , say terminal 1, can simulate
and broadcast it to all the terminals. Next, each terminal
in can simulate conditioned on

. This second step of randomiza-
tion is feasible since
are conditionally mutually independent conditioned on

. Thus, each ter-
minal in now has access to while the
eavesdropper observes , so that the reduced
PIN model for SK generation can be used to simulate a PIN



6488 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 56, NO. 12, DECEMBER 2010

model for PK generation with the given underlying joint pmf.
Thus, any achievable rate of a PK for in the given PIN model
for PK generation is an achievable rate of a PK for in the
simulated model. Further, the latter PK is a fortiori an SK for
in the reduced PIN model with randomization permitted at the
terminals in . This establishes (c).

In the proof of achievability of SK capacity for the general
multiterminal source model in [4], an SK of optimum rate was
extracted from “omniscience,” i.e., from a reconstruction by the
terminals in of all the signals observed by
the terminals in . In contrast, the scheme in Theorem 3.3
ii) (respectively, Theorem 3.4) for achieving SK capacity for a
PIN model with (respectively ) neither seeks
nor attains omniscience; however, we note that omniscience can
be attained by letting the terminals in simply broadcast all
the residual bits left over from a maximal path packing (respec-
tively, maximal spanning tree packing).

We close with the observation that in the proof of Theorem
3.3, the SK bit generated by each Steiner tree in Step 2 is exactly
independent of the public communication in that tree. Thus, if
the pairwise SKs in step 1 are “perfect” with zero security index,
then so is the overall SK for . It transpires that for the PIN
model, there is a tight connection between “perfect secrecy gen-
eration” and “communication for perfect omniscience,” redolent
of the asymptotic connection in [4].

This new connection and the role of Steiner tree packing in
attaining perfect omniscience and generating perfect secrecy are
the subjects of a sequel paper [17].

ACKNOWLEDGMENT

The authors thank the anonymous referees for their helpful
comments. P. Narayan thanks S. Khuller for the helpful pointer
to [8].

REFERENCES

[1] 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, Jul. 1993.

[2] A. Bondy and U. S. R. Murty, Graph Theory, ser. Graduate Texts in
Mathematics. New York: Springer, 2008, vol. 244.

[3] J. Cheriyan and M. Salavatipour, “Hardness and approximation results
for packing Steiner trees,” Algorithmica, vol. 45, no. 1, pp. 21–43,
2006.

[4] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,”
IEEE Trans. Inf. Theory, vol. 50, pp. 3047–3061, Dec. 2004.

[5] I. Csiszár and P. Narayan, “Secrecy capacities for multiterminal
channel models,” Special Issue of IEEE Trans. Inf. Theory Inf. The-
oret. Secur., vol. 54, pp. 2437–2452, Jun. 2008.

[6] E. A. Dinic, “An algorithm for the solution of the problem of maximal
flow in a network with power estimation,” Dokl. Akad. Nauk SSSR, vol.
194, pp. 754–757, 1970.

[7] J. Edmonds and R. M. Karp, “Theoretical improvements in algorithmic
efficiency for network flow problems,” in Combinatorial Structures
and Their Applications. New York: Gordon and Breach, 1970, pp.
93–96.

[8] H. N. Gabow and H. H. Westermann, “Forests, frames, and games:
Algorithms for matroid sums and applications,” Algorithmica, vol. 7,
pp. 465–497, 1992.

[9] A. Gohari and V. Anantharam, “Communication for omniscience by a
neutral observer and information-theoretic key agreement of multiple
terminals,” in Proc. IEEE Int. Symp. Inf. Theory, Nice, France, Jun.
2007, pp. 2056–2060.

[10] A. Gohari and V. Anantharam, “New bounds on the information-the-
oretic key agreement of multiple terminals,” in Proc. IEEE Int. Symp.
Inf. Theory, Toronto, Ontario, Canada, Jul. 2008, pp. 742–746.

[11] M. Grötschel, A. Martin, and R. Weismantel, “Packing Steiner trees: A
cutting plane algorithm and computational results,” Math. Program.,
vol. 72, pp. 125–145, Feb. 1996.

[12] K. Jain, M. Mahdian, and M. R. Salavatipour, “Packing Steiner trees,”
in Proc.14th ACM-SIAM Symp. Discr. Algorithms (SODA), Baltimore,
MD, USA, Jan. 2003, pp. 266–274.

[13] U. M. Maurer, “Provably secure key distribution based on independent
channels,” in IEEE Workshop Inf. Theory, Eindhoven, The Netherlands,
Jun. 1990.

[14] U. M. Maurer, “Secret key agreement by public discussion from
common information,” IEEE Trans. Inf. Theory, vol. 39, pp. 733–742,
May 1993.

[15] U. M. Maurer, “The strong secret key rate of discrete random triples,”
in Communications and Cryptography: Two Sides of One Tapestry, R.
E. Blahut, Ed. et al., Norwell, MA, 1994, pp. 271–285, 26.

[16] K. Menger, “Zur allgemeinen Kurventheorie,” Fund. Math., vol. 10,
pp. 96–115, 1927.

[17] S. Nitinawarat and P. Narayan, “Perfect omniscience, perfect secrecy,
and Steiner tree packing,” IEEE Trans. Inf Theory, vol. 56, no. 12, pp.
6490–6500, Dec. 2010.

[18] C. St. J. A. Nash-Williams, “Edge disjoint spanning trees of finite
graphs,” J. London Math. Soc., vol. 36, pp. 445–450, 1961.

[19] R. Renner and S. Wolf, “New bounds in secret-key agreement: The
gap between formation and secrecy extraction,” in Proc. EUROCRYPT
2003. New York: Springer-Verlag, 2003, vol. 2656, Lecture Notes in
Computer Science, pp. 562–577.

[20] W. T. Tutte, “On the problem of decomposing a graph into� connected
factors,” J. London Math. Soc., vol. 36, pp. 221–230, 1961.

[21] A. D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol. 54, pp.
1355–1387, 1975.

[22] C. Ye, A. Reznik, and Y. Shah, “Extracting secrecy from jointly
Gaussian random variables,” in Proc. 2006 IEEE Int. Symp. Inf.
Theory, Seattle, WA, Sep. 2006, pp. 2593–2597.

[23] C. Ye and A. Reznik, “Group secret key generation algorithms,” in
Proc. 2007 IEEE Int. Symp. Inf. Theory, Nice, France, Jun. 2007, pp.
2896–2900.

Sirin Nitinawarat (S’09) received the B.S.E.E. degree from Chulalongkorn
University, Bangkok, Thailand, with first class honors in 2001, and the M.S.E.E.
degree in 2003 from the University of Wisconsin, Madison.

He will receive the Ph.D. degree from the Department of Electrical and Com-
puter Engineering and the Institute for Systems Research, University of Mary-
land, College Park, in December 2010. His research interests are in information
theory and coding theory.

Chunxuan Ye (SM’10) received the B.Eng. (Hons) degree in electrical engi-
neering from Shanghai Jiao Tong University, China, the M.Phil. degree in infor-
mation engineering from the Chinese University of Hong Kong, and the Ph.D.
degree in electrical and computer engineering from the University of Maryland,
College Park, in 1997, 2000, and 2005, respectively.

He has been with InterDigital Communications, King of Prussia, PA, since
2005. His research interests are in the areas of information theory, communi-
cation theory, and wireless communication systems. These include informa-
tion theoretic security, cooperative and relayed networks, network coding and
source coding, wireless system prototyping platform, cognitive radio, and wire-
less communications networks. He has published more than 25 papers and book
chapters. He has more than 15 pending U.S. patents.



NITINAWARAT et al.: PAIRWISE INDEPENDENT NETWORK MODE 6489

Alexander Barg (F’08) received the M.Sc. degree in applied mathematics and
the Ph.D. degree in electrical engineering (information theory), the latter from
the Institute for Information Transmission Problems (IPPI) Moscow, Russia, in
1987.

He has been a Senior Researcher with the IPPI since 1988. During
1995–1996, he was with the Technical University of Eindhoven, Eindhoven,
the Netherlands. During 1997–2002, he was a Member of Technical Staff of
Bell Labs, Lucent Technologies. Since 2003, he has been a Professor with
the Department of Electrical and Computer Engineering and the Institute for
Systems Research, University of Maryland, College Park. His research interests
include coding and information theory and its links with computer science and
mathematics.

Dr. Barg served as an Associate Editor for Coding Theory of the IEEE
TRANSACTIONS ON INFORMATION THEORY during 1997–2000. He was the
Technical Program Co-Chair of the 2006 IEEE International Symposium on
Information Theory. He is presently a member of the Board of Governors of
the Information Theory Society and serves on the Editorial Board of several
journals including Problems of Information Transmission, SIAM Journal on
Discrete Mathematics, and Advances of Mathematics in Communications.

Prakash Narayan (F’01) received the B.Tech. degree in electrical engineering
from the Indian Institute of Technology, Madras, in 1976. He received the M.S.
degree in systems science and mathematics in 1978 and the D.Sc. degree in
electrical engineering in 1981, both from Washington University, St. Louis, MO.

He is Professor of Electrical and Computer Engineering with the University
of Maryland, College Park, with a joint appointment at the Institute for Systems
Research. He is also a founding member of the Center for Satellite and Hybrid
Communication Networks, a NASA Commercial Space Center. He has held
visiting appointments at ETH, Zurich; the Technion, Haifa; the Renyi Institute
of the Hungarian Academy of Sciences, Budapest; the University of Bielefeld;
the Institute of Biomedical Engineering (formerly LADSEB), Padova; and the
Indian Institute of Science, Bangalore. His research interests are in multiuser
information theory, communication theory, communication networks, cryptog-
raphy, and information theory and statistics.

Dr. Narayan has served as an Associate Editor for Shannon Theory for
the IEEE TRANSACTIONS ON INFORMATION THEORY; was Co-Organizer of
the IEEE Workshop on Multi-User Information Theory and Systems, VA
(1983); Technical Program Chair of the IEEE/IMS Workshop on Information
Theory and Statistics, VA (1994); General Co-Chair of the IEEE International
Symposium on Information Theory, Washington, DC (2001); and Technical
Program Co-Chair of the IEEE Information Theory Workshop, Bangalore
(2002). He currently serves as a Member of the Board of Governors of the
IEEE Information Theory Society.

Alex Reznik (M’98) received the B.S.E.E. degree from the Cooper Union, New
York, the S.M. degree in EECS from the Massachusetts Institute of Technology,
Cambridge, and the Ph.D. degree in electrical engineering from Princeton Uni-
versity, Princeton, NJ, in 1996, 1998, and 2005, respectively.

During 2000–2002, he held a MURI fellowship at Princeton University. He
has been with InterDigital, King of Prussia, PA, since 1999, where he is currently
a Principal Engineer in the Advanced Communication Networks Group, leading
a number of activities in the area of cognitive radio. His past contributions at
InterDigital included technical leadership positions on projects in physical layer
security, cellular modem architecture, and advanced receiver design. He holds a
visiting faculty appointment with Winlab, Rutgers University, New Brunswick,
NJ. His research interests are in information and communication theory and
architecture and design of modern communication systems and devices. He is
an inventor or coinventor on more than 40 granted U.S. patents

Dr. Reznik has been awarded several President’s and CTO innovation awards
at InterDigital.