We study channel intrinsic randomness, defined as the maximum random bit rate that can be extracted from a channel output independently of an input with known statistics. Independence and uniformity of the extracted process are measured by means of the variational distance between distributions. We obtain an expression for channel intrinsic randomness in terms of the statistics of the channel and its input process, which holds for arbitrary discrete channels and arbitrary discrete inputs. We discuss the connection between channel intrinsic randomness and secret-key distillation, and show that channel intrinsic randomness appears as the natural operation behind key distillation. As a supporting result, we obtain achievable secret-key rates for compound sources.
We study channel intrinsic randomness, defined as the maximum random bit rate that can be extracted from a channel output independently of an input with known statistics. Independence and uniformity of the extracted process are measured by means of the variational distance between distributions. We obtain an expression for channel intrinsic randomness in terms of the statistics of the channel and its input process, which holds for arbitrary discrete channels and arbitrary discrete inputs. We discuss the connection between channel intrinsic randomness and secret-key distillation, and show that channel intrinsic randomness appears as the natural operation behind key distillation. As a supporting result, we obtain achievable secret-key rates for compound sources.
Given a channel and an input process we study the minimum randomness of those input processes whose output statistics approximate the original output statistics with arbitrary accuracy. We introduce the notion of resolvability of a channel, defined as the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process. We obtain a general formula for resolvability which holds regardless of the channel memory structure. We show that, for most channels, resolvability is equal to Shannon capacity. By-products of our analysis are a general formula for the minimum achievable (fixed-length) source coding rate of any finite-alphabet source, and a strong converse of the identification coding theorem, which holds for any channel that satisfies the strong converse of the channel coding theorem.
Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.
The problem of channel resolvability, where a given output probability distribution over a channel is approximated by encoding uniform random number as a channel input, is addressed. The channel resolvability has recently been generalized to the variable-length setting, where the variable-length uniform random number instead of the fixed-length one is encoded. Though the optimum resolvability rate can be reduced compared with the fixed-length resolvability, it is not yet clear how much resolvability rate can be saved even when the given source and channel are stationary and memoryless. Given a stationary memoryless source and a discrete memoryless channel, this paper establishes a single-letter formula for the variable-length resolvability under the variational distance as an approximation measure. When the channel is a full-rank discrete memoryless channel, the established formula reduces to a further simpler formula characterized by the mutual information between the source and the channel. The established formula also recovers a known formula for the variable-length source resolvability.
The ability to exchange secret messages and protect against security attacks becomes increasingly important for providing information superiority and confidentiality in modern information systems. These systems require shared secret keys, which can be generated from common random sources with known distributions. However, the assumption on the distribution of the sources may not hold in many realistic scenarios. In this paper, we establish a mathematical framework for secret-key generation using common unknown deterministic sources (UDSs). In particular, we propose a new information measure called intrinsic information to characterize the achievable length of the secret key that can be generated from a UDS. As a case study, we consider a wideband propagation medium in mobile wireless networks as a UDS and derive its intrinsic information as a function of various network parameters. Our results provide a non-Bayesian perspective for secret-key generation as well as practical implications of this new perspective.
This paper is concerned with secret-key agreement by public discussion: two parties Alice and Bob and an adversary Eve have access to independent realizations of random variables X , Y , and Z, respectively, with joint distribution PXY Z . The secret key rate S(X ; Y jjZ) has been defined as the maximal rate at which Alice and Bob can generate a secret key by communication over an insecure, but authenticated channel such that Eve's information about this key is arbitrarily small. We define a new conditional mutual information measure, the intrinsic conditional mutual information between X and Y when given Z, denoted by I(X ; Y#Z), which is an upper bound on S(X ; Y jjZ). The special scenarios where X , Y , and Z are generated by sending a binary random variable R, for example a signal broadcast by a satellite, over independent channels, or where Z is generated by sending X and Y over erasure channels, are analyzed. In the first scenario it can be shown that the secret key rate is str...
We study the following problem: two agents Alice and Bob are connected to each other by independent discrete memoryless channels. They wish to generate common randomness, i.e. agree on a common random variable, by communicating interactively over the two channels. Assuming that Alice and Bob are allowed access to independent external random sources at rates (in bits per step of communication) of H/sub A/ and H/sub B/, respectively, we show that they can generate common randomness at a rate of max{min[H/sub A/+H(W|Q),I(P;V)]+min[H/sub B/+H(V|P), I(Q;W)]} bits per step, by exploiting the noise on the two channels. Here, V is the channel from Alice to Bob, and W is the channel from Bob to Alice. The maximum is over all probability distributions P and Q on the input alphabets of V and W, respectively. We also prove a strong converse which establishes the above rate as the highest attainable in this situation.