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.

We propose a PHY-authentication protocol to detect spoofing attacks in wireless networks, exploiting the rapid-decorrelation property of radio channels with distance. In this protocol, a PHY-authentication scheme that exploits channel estimations that already exist in most wireless systems, cooperates with any existing-either simple or advanced-higher-layer process, such as IEEE 802.11i. With little additional system overhead, our scheme reduces the workload of the higher-layer process, or provides some degree of spoofing protection for ``naked" wireless systems, such as some sensor networks. We describe the performance of our approach as a function of the spoofing pattern and the snapshot performance that can be easily measured through field tests. We discuss the implementation issues of the authentication protocol on 802.11 testbeds and verify its performance via field tests in a typical office building.

Since the IEEE 802.11 DCF adopted the Binary Exponential Back-off (BEB) algorithm in its contention window adjustment scheme, many alternative back-off algorithms were proposed in order to enhance the performance. Among them is an Exponential Increase Exponential Decrease (EIED) back-off algorithm, whose performance was simulated and analyzed in a special case of doubling or halving the contention window size. This paper provides an analytical analysis for the general EIED algorithm. A closed form saturation throughput and a closed form saturation delay are derived. Our analytical results further establish the performance improvement of the general EIED algorithm over the BEB algorithm and the basic EIED algorithm.

The multipath-rich wireless environment associated with typical wireless usage scenarios is characterized by a fading channel response that is time-varying, location-sensitive, and uniquely shared by a given transmitter-receiver pair. The complexity associated with a richly scattering environment implies that the short-term fading process is inherently hard to predict and best modeled stochastically, with rapid decorrelation properties in space, time, and frequency. In this paper, we demonstrate how the channel state between a wireless transmitter and receiver can be used as the basis for building practical secret key generation protocols between two entities. We begin by presenting a scheme based on level crossings of the fading process, which is well-suited for the Rayleigh and Rician fading models associated with a richly scattering environment. Our level crossing algorithm is simple, and incorporates a self-authenticating mechanism to prevent adversarial manipulation of message exchanges during the protocol. Since the level crossing algorithm is best suited for fading processes that exhibit symmetry in their underlying distribution, we present a second and more powerful approach that is suited for more general channel state distributions. This second approach is motivated by observations from quantizing jointly Gaussian processes, but exploits empirical measurements to set quantization boundaries and a heuristic log likelihood ratio estimate to achieve an improved secret key generation rate. We validate both proposed protocols through experimentations using a customized 802.11a platform, and show for the typical WiFi channel that reliable secret key establishment can be accomplished at rates on the order of 10 b/s.

We consider secret key generation for a “pairwise independent network” model in which every pair of terminals observes 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 capacity. 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.

We investigate perfect secret key generation for a ¿pairwise independent network¿ model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate interactively in multiple rounds over a public noiseless channel of unlimited capacity. This communication is observed by all the terminals as well as by an eavesdropper. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible. All the terminals cooperate in generating the secret key, with perfect secrecy being required from the eavesdropper. For this model, we introduce the concept of communication for perfect omniscience using which we first obtain a single-letter characterization of the perfect secret key capacity. Moreover, this perfect secret key capacity is shown to be achieved by linear noninteractive communication, and coincides with the (standard) secret key capacity. Our second contribution, exploiting the notion of communication for perfect omniscience, is a new nonasymptotic and computable upper bound for the combinatorial problem of maximal Steiner tree packing in a multigraph. Thus, our work establishes certain connections among perfect secrecy generation and communication for perfect omniscience for the pairwise independent network model, and Steiner tree packing.

We investigate secret key generation for a ldquopair-wise independent networkrdquo model in which every pair of terminals observes correlated sources which are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate interactively in multiple rounds over a public noiseless channel of unlimited capacity, 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. All the terminals cooperate in generating the secret key, with secrecy being required from an eavesdropper which has access to the public interterminal communication. We provide a (single-letter) formula for the secrecy capacity for this model, and show a natural connection between the problem of secret key generation and the combinatorial problem of maximal packing of Steiner trees in an associated multigraph. In particular, we show that the maximum number of Steiner tree packings in the multigraph is always a lower bound for the secrecy capacity. The bound is tight for the case when all the terminals seek to share a secret key; the mentioned connection yields an explicit capacity-achieving algorithm. This algorithm, which can be executed in polynomial time, extracts a group-wide secret key of the optimum rate from the collection of optimum and mutually independent secret keys for pairs of terminals.

Securing communications requires the establishment of cryptographic keys, which is challenging in mobile scenarios where a key management infrastructure is not always present. In this paper, we present a protocol that allows two users to establish a common cryptographic key by exploiting special properties of the wireless channel: the underlying channel response between any two parties is unique and decorrelates rapidly in space. The established key can then be used to support security services (such as encryption) between two users. Our algorithm uses level-crossings and quantization to extract bits from correlated stochastic processes. The resulting protocol resists cryptanalysis by an eavesdropping adversary and a spoofing attack by an active adversary without requiring an authenticated channel, as is typically assumed in prior information-theoretic key establishment schemes. We evaluate our algorithm through theoretical and numerical studies, and provide validation through two complementary experimental studies. First, we use an 802.11 development platform with customized logic that extracts raw channel impulse response data from the preamble of a format-compliant 802.11a packet. We show that it is possible to practically achieve key establishment rates of ~ 1 bit/sec in a real, indoor wireless environment. To illustrate the generality of our method, we show that our approach is equally applicable to per-packet coarse signal strength measurements using off-the-shelf 802.11 hardware.

We consider a pair-wise independent network in which every pair of terminals observes a common pair-wise source that is independent of all the sources accessible to the other pairs. We propose a method for secret key agreement in such a network that is based on well-established point-to- point techniques and repeated application of the one-time pad over a graphical representation of the network. Three specific problems are investigated. (1) Each terminal's observations are correlated only with the observations of a central terminal. All these terminals wish to generate a common secret key. (2) Two designated terminals wish to generate a secret key with the help of other terminals. (3) All terminals wish to generate a common secret key. In each of these cases, we show that our two-step approach can yield an optimal protocol, in terms of the resulting secret key rates. Furthermore, such a protocol is provided for the first two problems, while an efficient protocol is given for the third problem.

We consider the secrecy inherent in the reciprocal nature of multipath fading channels and present a technique to generate a shared perfectly secret key by two terminals observing a multipath fading channel. Using this technique we quantify the secrecy that can be generated from ITU cellular channels for the 2 GHz frequency range.

We present a method for secrecy extraction from jointly Gaussian random sources. The approach is motivated by and has applications in enhancing security for wireless communications. The problem is also found to be closely related to some well known lossy source coding problems

This work is motivated by recent results of Csiszar and Narayan (IEEE Trans, on Inform. Theory, Dec. 2004), which highlight innate connections between secrecy generation by multiple terminals and multiterminal Slepian-Wolf near-lossless data compression (sans secrecy restrictions). We propose a new approach for constructing secret and private keys based on the long-known Slepian-Wolf code for sources connected by a virtual additive noise channel, due to Wyner (IEEE Trans, on Inform. Theory, Jan. 1974). Explicit procedures for such constructions, and their substantiation, are provided

We consider a model for secrecy generation, with three terminals, by means of public interterminal communication, and examine the problem of characterizing all the rates at which all three terminals can generate a "secret key," and - simultaneously - two designated terminals can generate a "private key" which is effectively concealed from the remaining terminal; both keys are also concealed from an eavesdropper that observes the public communication. Inner and outer bounds for the "secret key-private key capacity region" are derived. Under a certain special condition, these bounds coincide to yield the (exact) secret key-private key capacity region

This paper considers a model with three terminals and examines the problem of characterizing the largest rates at which two pairs of terminals can simultaneously generate private keys, each of which is effectively concealed from the remaining terminal.

Upper bounds on the redundancy of Huffman codes have been extensively studied in the literature. Almost all of these bounds are in terms of the probability of either the most likely or the least likely source symbol. We prove a simple upper bound in terms of the probability of any source symbol.

A variable-length code is a fix-free code if no codeword is a prefix or a suffix of any other codeword. This class of codes is applied to speed up the decoding process, for the decoder can decode from both sides of the compressed file simultaneously. We study some basic properties of fix-free codes. We prove a sufficient and a necessary condition for the existence of fix-free codes, and we obtain some new upper bounds on the redundancy of optimal fix-free codes.