Secret Key Generation for a Pairwise Independent Network Model

Research Paper / Jan 2010

- Home /

Secret Key Generation for a Pairwise Independent Network Model

Research Paper / Jan 2010

In order for network slicing to deliver on its promise as an effective tool to generate new revenues and profitability, new business models must match the dynamic technical and operational changes that it brings. Significant progress is being made in demonstrations and trials, as highlighted in this report and the...

Joe Giersch, a biologist from USGS, sat down with InterDigital to discuss technology’s role in the study of stream ecology, and explain why we should all know about the insect, Lednia tumana, that he has spent his life studying.

Recently, the Qualcomm Tricorder XPRIZE® announced its winners. We caught up with Ed Hepler, ex-InterDigital engineer and hardware development lead of the winning bootstrap operation, Final Frontier Medical Devices, after the winning announcement in this CREATORS sit-down.

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.

InterDigital develops mobile technologies that are at the core of devices, networks, and services worldwide. We solve many of the industry's most critical and complex technical challenges, inventing solutions for more efficient broadband networks and a richer multimedia experience years ahead of market deployment.

© Copyright 2017 InterDigital, Inc. All Rights Reserved