INFORMATION THEORETIC SECRET KEY GENERATION: STRUCTURED CODES AND TREE PACKING

Abstract

This dissertation deals with a multiterminal source model for

secret key generation by multiple network terminals with prior and

privileged access to a set of correlated signals complemented by

public discussion among themselves. Emphasis is placed on a

characterization of secret key capacity, i.e., the largest rate of

an achievable secret key, and on algorithms for key construction.

Various information theoretic security requirements of increasing

stringency: weak, strong and perfect secrecy, as well as different

types of sources: finite-valued and continuous, are studied.

Specifically, three different models are investigated.

First, we consider strong secrecy generation for a

discrete multiterminal source model. We discover a

connection between secret key capacity and a new

source coding concept of ``minimum information rate for signal dissemination,''

that is of independent interest in multiterminal data compression.

Our main contribution is to show for this discrete model

that structured linear codes suffice to generate a

strong secret key of the best rate.

Second, strong secrecy generation is considered for models with

continuous observations, in particular jointly Gaussian signals.

In the absence of suitable analogs of source coding notions for

the previous discrete model, new techniques are required for a

characterization of secret key capacity as well as for the design

of algorithms for secret key generation. Our proof of the secret

key capacity result, in particular the converse proof, as well as

our capacity-achieving algorithms for secret key construction

based on structured codes and quantization for a model with two

terminals, constitute the two main contributions for this second

model.

Last, we turn our attention to perfect secrecy generation for

fixed signal observation lengths as well as for their asymptotic

limits. In contrast with the analysis of the previous two models

that relies on probabilistic techniques, perfect secret key

generation bears the essence of ``zero-error information theory,''

and accordingly, we rely on mathematical techniques of a

combinatorial nature. The model under consideration is the

``Pairwise Independent Network'' (PIN) model in which every pair

of terminals share a random binary string, with the strings shared

by distinct pairs of terminals being mutually independent. This

model, which is motivated by practical aspects of a wireless

communication network in which terminals communicate on the same

frequency, results in three main contributions. First, the

concept of perfect omniscience in data compression leads to a

single-letter formula for the perfect secret key capacity of the

PIN model; moreover, this capacity is shown to be achieved by

linear noninteractive public communication, and coincides with

strong secret key capacity. Second, taking advantage of a

multigraph representation of the PIN model, we put forth an

efficient algorithm for perfect secret key generation based on a

combinatorial concept of maximal packing of Steiner trees of the

multigraph. When all the terminals seek to share perfect secrecy,

the algorithm is shown to achieve capacity. When only a subset of

terminals wish to share perfect secrecy, the algorithm is shown to

achieve at least half of it. Additionally, we obtain nonasymptotic

and asymptotic bounds on the size and rate of the best perfect

secret key generated by the algorithm. These bounds are of

independent interest from a purely graph theoretic viewpoint as

they constitute new estimates for the maximum size and rate of

Steiner tree packing of a given multigraph. Third, a particular

configuration of the PIN model arises when a lone ``helper''

terminal aids all the other ``user'' terminals generate perfect

secrecy. This model has special features that enable us to obtain

necessary and sufficient conditions for Steiner tree packing to

achieve perfect secret key capacity.