Shared information is a measure of mutual dependence among multiple jointly distributed random variables with finite alphabets. For a Markov chain on a tree with a given joint distribution, we give a new proof of an explicit characterization of shared information. The Markov chain on a tree is shown to possess a global Markov property based on graph separation; this property plays a key role in our proofs. When the underlying joint distribution is not known, we exploit the special form of this characterization to provide a multiarmed bandit algorithm for estimating shared information, and analyze its error performance.

For a given function of user data, a querier must recover with at least a prescribed probability, the value of the function based on a user-provided query response. Subject to this requirement, the user forms the query response so as to minimize the likelihood of the querier guessing a list of prescribed size to which the data value belongs based on the query response. We obtain a general converse upper bound for maximum list privacy. This bound is shown to be tight for the case of a binary-valued function through an explicit achievability scheme that involves an add-noise query response.

Shared information is a measure of mutual dependence among m≥2 jointly distributed discrete random variables. A new undirected probabilistic graphical model, a cliqueylon graph, is introduced, with potential applications in leader-follower swarms and neuron clusters with correlations of varying strength. Shared information is characterized explicitly for the cliqueylon, relying on structural properties of an underlying optimization. Implications for the data compression problem of omniscience are highlighted.

In the article[1], in the proof of Lemma 2, the sentence after (10) “For a fixed$Q^{(n)}$, since$(P_{X}W)^{n}(z^{n})$is the same for all$z^{n}\in \mathcal {T}_{Q^{(n)}}$, if$\widehat {P}_{n}(z^{n})$were to vary across$z^{n}\in \mathcal {T}_{Q^{(n)}}$, the querier can pick that$\tilde {z^{n}}$, say, in$\mathcal {T}_{Q^{(n)}}$for which$D\left ({P_{X}\big |\big |\widehat {P}_{n}\left ({\tilde {z^{n}}}\right)}\right)$is smallest over$\mathcal {T}_{Q^{(n)}}$and use$\widehat {P}_{n}\left ({\tilde {z^{n}}}\right)$as the estimate of$P_{X}$for all$z^{n}\in \mathcal {T}_{Q^{(n)}}$, denoting it by$\widehat {P}_{n}\left ({Q^{(n)}}\right)$; this will only serve to decrease the right-side of (10), bearing in mind the$\inf $with respect to$\widehat {P}_{n}$in the left-side of (5)” is incorrect.

Shared information is a measure of mutual dependence among m ≥ 2 jointly distributed discrete random variables. For a Markov chain on a tree with a given joint distribution, we give a new proof of an explicit characterization of shared information. When the joint distribution is not known, we exploit the special form of this characterization to provide a multiarmed bandit algorithm for estimating shared information, and analyze its error performance.

A user generates$n$independent and identically distributed data random variables with a probability mass function that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of$n$independent and identically distributed query responses upon eliciting them from the user. The user chooses the data probability mass function and devises the random query responses to maximize distribution privacy as gauged by the (Kullback-Leibler) divergence between the former and the querier’s best estimate of it based on the$n$query responses. Considering an arbitrary function, a basic achievable lower bound for distribution privacy is provided that does not depend on$n$and corresponds to worst-case privacy. Worst-case privacy equals the logsum cardinalities of inverse atoms under the given function, with the number of summands decreasing as the querier recovers the function with improving accuracy. Next, upper (converse) and lower (achievability) bounds for distribution privacy, dependent on$n$, are developed. The former improves upon worst-case privacy and the latter does so under suitable assumptions; both converge to it as$n$grows. The converse and achievability proofs identify explicit strategies for the user and the querier.

Consider a finite set of multiple sources, described by a random variable with$m$components. Only$k\leq m$source components are sampled and jointly compressed in order to reconstruct all the$m$components under an excess distortion criterion. Sampling can be that of a fixed subset$A$with$\vert A\vert =k$or randomized over all subsets of size$k$. In the case of random sampling, the sampler may or may not be aware of the$m$source components. The compression code consists of an encoder whose input is the realization of the sampler and the sampled source components; the decoder input is solely the encoder output. The combined sampling mechanism and rate distortion code are universal in that they must be devised without exact knowledge of the prevailing source probability distribution. In a Bayesian setting, considering coordinated single-shot sampling and compression, our contributions involve achievability results for the cases of fixed-set, source-independent and source-dependent random sampling.

A user generates$n$independent and identically distributed data rvs with a pmf that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of$n$independent and identically distributed user-devised query responses. The user chooses the data pmf and the random query responses to maximize distribution privacy as gauged by the divergence between the pmf and the querier's best estimate of it based on the$n$query responses. Considering an arbitrary function, a basic achievable lower bound, that does not depend on n, is provided for distribution privacy. Next, upper (converse) and lower (achievable) bounds, dependent on n, are developed that converge to said basic bound as$n$grows. Explicit strategies for the user and the querier are identified.

A user generates n independent and identically distributed data random variables with a probability mass function that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of n independent and identically distributed user-devised query responses. The user chooses the data pmf and the random query responses to maximize distribution privacy as gauged by the divergence between the pmf and the querier's best estimate of it based on the n query responses. A general lower bound is provided for distribution privacy; and, for the case of binaryvalued functions, upper and lower bounds that converge to said bound as n grows. Explicit strategies for the user and querier are identified.

For a given function of user data, a querier must recover with at least a prescribed probability, the value of the function based on a user-provided query response. Subject to this requirement, the user forms its query response so as to maximize probability of error-based predicate privacy or list privacy of the data from the querier. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacies compared with converse upper bounds.

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, which provide maximum privacy to the user. In the former setting, we also consider privacy for a predicate of the user's data. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, that provide maximum privacy to the user. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.

We examine the coordinated and universal rate-efficient sampling of a subset of correlated discrete memoryless sources followed by lossy compression of the sampled sources. The goal is to reconstruct a predesignated subset of sources within a specified level of distortion. The combined sampling mechanism and rate distortion code are universal in that they are devised to perform robustly without exact knowledge of the underlying probability distribution of the sources. Single-letter characterizations are provided for a universal sampling rate distortion function for fixed-set and independent random sampling.

Consider a discrete memoryless multiple source with m component sources. A subset of k ≤ m sources are sampled at each time instant and jointly compressed in order to reconstruct all the m sources under a given distortion criterion. A sampling rate distortion function is studied for two main sampling schemes. First, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether the decoder is informed or not of the sequence of sampling sets. Next, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without.

We revisit A.C. Yao's classic problem of secure function computation by interactive communication, in an information theoretic setting. Our approach, based on examining the underlying common randomness, provides a new proof of the characterization of a securely computable function by deterministic protocols. This approach also yields a characterization of the minimum communication needed for secure computability.

Consider a discrete memoryless multiple source with m components of which k ≤ m possibly different sources are sampled at each time instant and jointly compressed in order to reconstruct all the m sources under a given distortion criterion. A new notion of sampling rate distortion function is introduced, and is characterized first for the case of fixed-set sampling. Next, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether or not the decoder is informed of the sequence of sampled sets. Furthermore, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without.

A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Rényi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source.

Shannon theoretic secret key generation by several parties is considered for models in which a secure noisy channel with multiple input and output terminals and a public noiseless channel of unlimited capacity are available for accomplishing this goal. The secret key is generated for a setAof terminals of the noisy channel, with the remaining terminals (if any) cooperating in this task through their public communication. Single-letter lower and upper bounds for secrecy capacities are obtained when secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint fromA. These bounds coincide in special cases, but not in general. We also consider models in which different sets of terminals share multiple keys, one for the terminals in each set with secrecy required from the eavesdropper as well as from the terminals not in this set. Partial results include showing links among the associated secrecy capacity region for multiple keys, the transmission capacity region of the multiple access channel defined by the secure noisy channel, and achievable rates for a single secret key for all the terminals.

A set of m terminals, observing correlated signals, communicate interactively to generate common randomness for a given subset of them. Knowing only the communication, how many direct queries of the value of the common randomness will resolve it? A general upper bound, valid for arbitrary signal alphabets, is developed for the number of such queries by using a query strategy that applies to all common randomness and associated communication. When the underlying signals are independent and identically distributed repetitions of m correlated random variables, the number of queries can be exponential in signal length. For this case, the mentioned upper bound is tight and leads to a single-letter formula for the largest query exponent, which coincides with the secret key capacity of a corresponding multiterminal source model. In fact, the upper bound constitutes a strong converse for the optimum query exponent, and implies also a new strong converse for secret key capacity. A key tool, estimating the size of a large probability set in terms of Rényi entropy, is interpreted separately, too, as a lossless block coding result for general sources. As a particularization, it yields the classic result for a discrete memoryless source.

Secret key generation by multiple terminals is considered based on their observations of jointly distributed Gaussian signals, followed by public communication among themselves. Exploiting an inherent connection between secrecy generation and lossy data compression, two main contributions are made. The first is a characterization of strong secret key capacity, and entails a converse proof technique that is valid for real-valued (and not necessarily Gaussian) as well as finite-valued signals. The capacity formula acquires a simple form when the terminals observe “symmetrically correlated” jointly Gaussian signals. For the latter setup with two terminals, considering schemes that involve quantization at one terminal, the best rate of an achievable secret key is characterized as a function of quantization rate; secret key capacity is attained as the quantization rate tends to infinity. Structured codes are shown to attain the optimum tradeoff between secret key rate and quantization rate, constituting our second main contribution.

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.

A subset of a set of terminals that observe correlated signals seek to compute a given function of the signals using public communication. It is required that the value of the function be kept secret from an eavesdropper with access to the communication. We show that the function is securely computable if and only if its entropy is less than the “aided secret key” capacity of an associated secrecy generation model, for which a single-letter characterization is provided.

A subset of a set of terminals that observe correlated signals seek to compute a function of the signals using public communication. It is required that the value of the function be concealed from an eavesdropper with access to the communication. We show that the function is securely computable if and only if its entropy is less than the capacity of a new secrecy generation model, for which a single-letter characterization is provided.

Shannon theoretic shared secret key generation by multiple terminals is considered for a source model in which the components of a discrete memoryless multiple source and a noiseless public channel of unlimited capacity are available for accomplishing this goal. A shared secret key is generated for distinct coalitions of terminals, with all the terminals cooperating in this task through their public communication. A communication from a terminal can be a function of its observed source component and of all previous communication. Member terminals of a coalition unite in recovering the key. Secrecy is required from an eavesdropper that observes the public interterminal communication. A single-letter characterization of the shared secret key capacity is obtained. When the key must be concealed additionally from subsets of coalition members, we provide an upper bound for the strict shared secret key capacity.

We consider perfect secret key generation for a “pairwise independent network” model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Our results yield new bounds for the maximum size and rate of Steiner tree packing, and are of independent interest from a graph theoretic viewpoint. Third, when a single “helper” terminal assists the remaining “user” terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a “weak” helper is shown to be sufficient for optimality.

We study a problem of secure computation by multiple parties of a given function of their cumulative observations, using public communication but without revealing the value of the function to an eavesdropper with access to this communication. A Shannon theoretic formulation is introduced to characterize necessary and sufficient conditions for secure computability. Drawing on innate connections of this formulation to the problem of secret key generation by the same parties using public communication, we show that a function is securely computable if and only if its entropy is smaller than the secret key capacity. Conditions for secure computability at a lone terminal are also derived by association with an appropriate secret key generation problem.

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.

Shannon theoretic secret key generation by several parties is considered for models in which a secure noisy channel with multiple input and output terminals and a public noiseless channel of unlimited capacity are available for accomplishing this goal. The secret key is generated for a set A of terminals of the noisy channel, with the remaining terminals (if any) cooperating in this task through their public communication. Single-letter lower and upper bounds for secrecy capacities are obtained when secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from A. These bounds coincide in special cases, and the lower bounds are not tight in general. We also consider models in which different sets of terminals share multiple keys, one for terminals in each set with secrecy required from the eavesdropper as well as the remaining terminals in the other sets. Partial results include showing links among the associated secrecy capacity region for multiple keys, the transmission capacity region of the multiple access channel defined by the secure noisy channel, and achievable rates for a single secret key for all the terminals.

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 consider a Gelfand-Pinsker discrete memoryless channel (DMC) model and provide a strong converse for its capacity. The strong converse is then used to obtain an upper bound on the reliability function. Instrumental in our proofs is a new technical lemma which provides an upper bound for the rate of codes with codewords that are conditionally typical over large message dependent subsets of a typical set of state sequences. This technical result is a nonstraightforward analog of a known result for a DMC without states that provides an upper bound on the rate of a good code with codewords of a fixed type (to be found in, for instance, the Csiszar-Kurner book).

In this survey presentation, we consider Shannon-theoretic secret key generation by multiple parties for two categories of models. In the first category, termed source models, multiple terminals are provided prior and privileged access to correlated signals. In the second category, called channel models, these terminals are connected by a secure noisy channel with multiple input and outputs. In both categories, a public noiseless channel of unlimited capacity is available additionally for accomplishing the goal of secrecy generation. The secret key is generated for a subset of the terminals, with the cooperation of remaining terminals (if any) through their public communication. We ask for single-letter characterizations of secrecy capacities for these models when secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from the secrecy seeking set. Complete results have been obtained for secret key capacity for the source model and the channel model with a single input, while partial results are available for the channel model with multiple inputs. These will be surveyed, and some open problems will be discussed.

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.

Shannon-theoretic secret key generation by several parties is considered for models in which a secure noisy channel with one input terminal and multiple output terminals and a public noiseless channel of unlimited capacity are available for accomplishing this goal. The secret key is generated for a set$A$of terminals of the noisy channel, with the remaining terminals (if any) cooperating in this task through their public communication. Single-letter characterizations of secrecy capacities are obtained for models in which secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from$A$. These capacities are shown to be achievable with noninteractive public communication, the channel input terminal sending no public message and each output terminal sending at most one public message, not using randomization. Moreover, when the input terminal belongs to the set$A$, it can generate the secret key at the outset and transmit it over the noisy channel, suitably encoded, whereupon the output terminals in$A$securely recover this key using public communication as above. For models in which the eavesdropper also possesses side information that is not available to any of the terminals cooperating in secrecy generation, an upper bound for the secrecy capacity and a sufficient condition for its tightness are given.

Shannon-theoretic secret key generation by several parties is considered for source models in which the distinct components of a multiple source observed separately by multiple terminals, and for channel models in which a secure noisy channel with one input terminal and multiple output terminals, and, additionally in both cases, a public noiseless channel of unlimited capacity, are available for accomplishing this goal. The secret key is generated for a set A of terminals, with the remaining terminals (if any) cooperating in this task through their public communication. We show that for source models in which secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from A, secrecy capacity can be achieved with noninteractive communication, the key being generated by any chosen terminal in the secret key-seeking set A of terminals obliviously of the public communication. For models in which the eavesdropper also possesses side information that is not available to any of the terminals cooperating in secrecy generation, an upper bound for the secrecy capacity and a sufficient condition for its tightness are given. The latter partially fills a gap in the authors' previous work [6].

In this first paper of a two-part series, a single-user single-input single-output (SISO) shot-noise-limited Poisson channel is considered over which an information signal is transmitted by modulating the intensity of an optical beam, and individual photon arrivals are counted at the photodetector receiver. The transmitted signal, which is chosen to satisfy peak and average constraints, undergoes multiplicative fading, which occurs over coherence time intervals of fixed duration. The fade coefficient (channel state) remains constant in each coherence interval, and varies across successive such intervals in an independent and identically distributed (i.i.d.) fashion. A single-letter characterization of the capacity of this channel is obtained when the receiver is provided with perfect channel state information (CSI) while the transmitter CSI can be imperfect. The asymptotic behavior of channel capacity in the low and high peak-signal-to-shot-noise ratio (SNR) regimes is studied.

We consider a single-user multiple input multiple output (MIMO) shot-noise limited Poisson fading channel over which information signals are transmitted by modulating the intensities of multiple optical beams, one from each transmit aperture; and individual photon arrivals are counted at multiple receive photodetector apertures. The transmitted signals undergo multiplicative fading, and the fading occurs in coherence intervals of fixed duration in each of which the fade (channel state) matrix remains constant, and changes across successive such intervals in an i.i.d. fashion. We obtain a single-letter characterization of the capacity of this channel when the receiver is provided with perfect channel state information (CSI) while the transmitter CSI can be imperfect. Properties of the optimal transmission strategies are also described.

We derive single-letter characterizations of (strong) secrecy capacities for models in which a "helper" terminal is connected to an arbitrary number of "user" terminals by a discrete memoryless channel (DMC). The helper terminal governs the input of the DMC, over which it transmits to the user terminals that observe the corresponding outputs; transmissions over the DMC are secure. Additionally, following each transmission over the DMC, unrestricted and interactive public communication is permitted between all the terminals. A subset of the user terminals, and possibly the helper terminal, generate secrecy with the remaining user terminals acting as abettors. We distinguish between the cases in which the helper terminal may, or may not, randomize. Two kinds of secrecy capacity are considered, depending on the extent of an eavesdropper's knowledge: secret key (SK) and private key (PK) capacity. These secrecy capacities are shown to be achievable with noninteractive communication between the terminals and with no public transmission from the helper terminal. When the helper terminal is forbidden to randomize, the needed transmission over the DMC entails only that of a constant sequence. It is also shown that additional randomization at the user terminals does not serve to enhance the secrecy capacities

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.

We derive single-letter characterizations of (strong) secrecy capacities for models with an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unrestricted and interactive public communication permitted between the terminals. A subset of these terminals can serve as helpers for the remaining terminals in generating secrecy. According to the extent of an eavesdropper's knowledge, three kinds of secrecy capacity are considered: secret key (SK), private key (PK), and wiretap secret key (WSK) capacity. The characterizations of the SK and PK capacities highlight the innate connections between secrecy generation and multiterminal source coding without secrecy requirements. A general upper bound for WSK capacity is derived which is tight in the case when the eavesdropper can wiretap noisy versions of the components of the underlying multiple source, provided randomization is permitted at the terminals. These secrecy capacities are seen to be achievable with noninteractive communication between the terminals. The achievability results are also shown to be universal.

We consider the problem of characterizing the secret key (SK)-capacity for an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unconstrained public communication allowed between these terminals. Our main contribution is the determination of SK-capacity for an arbitrary subset of terminals with the remaining terminals serving as "helpers," when an eavesdropper observes the communication between the terminals but does not have access to any other information. We also determine the private key (PK)-capacity when the eavesdropper additionally wiretaps some of the helper terminals from which too the key must then be concealed.

We determine the capacity regions for a class of time-varying multiple-access channels (TVMACs), when the underlying channel state evolves in time according to a probability law which is known to the transmitters and the receiver. Additionally, the transmitters and the receiver have access to varying degrees of channel state information (CSI) concerning the condition of the channel. Discrete-time channels with finite input, output, and state alphabets are considered first. The special case of a TVMAC, with the channel state process being a time-invariant, indecomposable, aperiodic Markov chain, shows a surprising anomaly in that imperfect transmitter CSI can cause the capacity under some distributions for the initial state to be strictly larger than that under a stationary distribution for the initial state. We also study a time-varying multiple-access fading channel with additive Gaussian noise, when various amounts of CSI are provided to the transmitters and perfect CSI is available to the receiver, and the fades are assumed to be stationary and ergodic. Implications for transmitter power control are discussed.

We consider the estimation of the order, i.e., the number of hidden states, of a special class of discrete-time finite-alphabet hidden Markov sources. This class can be characterized in terms of equivalent renewal processes. No a priori bound is assumed on the maximum. permissible order. An order estimator based on renewal types is constructed, and is shown to be strongly consistent by computing the precise asymptotics of the probability of estimation error. The probability of underestimation of the true order decays exponentially in the number of observations while the probability of overestimation goes to zero sufficiently fast. It is further shown that this estimator has the best possible error exponent in a large class of estimators. Our results are also valid for the general class of binary independent-renewal processes with finite mean renewal times.

Summary form only given. We address the capacity problem for a class of time-varying multiple-access channels (TVMAC), when the underlying channel state evolves in time according to a probability law which is known to the transmitters and the receiver. Additionally, the transmitters and the receiver have access to varying degrees of channel state information (CSI) concerning the condition of the channel. Discrete-time channels with finite input, output and state alphabets are considered first. The special case of a memoryless TVMAC, with the channel state process being a time-invariant, indecomposable, aperiodic Markov chain, shows a surprising anomaly in that imperfect transmitter CSI can cause the capacity under some distributions for the initial state to be strictly larger than that under a stationary distribution for the initial state. We also consider a time-varying multiple-access fading channel with additive Gaussian noise, when various amounts of CSI are provided to the transmitters and perfect CSI is available to the receiver, and the fades are assumed to be stationary and ergodic. Implications for transmitter power control are discussed.

We consider the generation of common randomness (CR), secret or not secret, by two user terminals with aid from a "helper" terminal. Each terminal observes a different component of a discrete memoryless multiple source. The helper aids the users by transmitting information to them over a noiseless public channel subject to a rate constraint. Furthermore, one of the users is allowed to transmit to the other user over a public channel under a similar rate constraint. We study the maximum rate of CR which can be thus generated, including under additional secrecy conditions when it must be concealed from a wiretapper. Lower bounds for the corresponding capacities are provided, and single-letter capacity formulas are obtained for several special cases of interest.

In many communication situations, the transmitter and the receiver must be designed without a complete knowledge of the probability law governing the channel over which transmission takes place. Various models for such channels and their corresponding capacities are surveyed. Special emphasis is placed on the encoders and decoders which enable reliable communication over these channels.

We consider the problem of estimating the order of a stationary ergodic Markov chain. Our focus is on estimators which satisfy a generalized Neyman-Pearson criterion of optimality. Specifically, the optimal estimator minimizes the probability of underestimation among all estimators with probability of overestimation not exceeding a given value. Our main result identifies the best exponent of asymptotically exponential decay of the probability of underestimation. We further construct a consistent estimator, based on Kullback-Leibler divergences, which achieves the best exponent. We also present a consistent estimator involving a recursively computable statistic based on appropriate mixture distributions; this estimator also achieves the best exponent for underestimation probability.

Given a discrete memoryless source (DMS) with probability mass function P, we seek first an asymptotically optimal description of the source with distortion not exceeding /spl Delta//sub 1/, followed by an asymptotically optimal refined description with distortion not exceeding /spl Delta//sub 2/

For discrete memoryless channels {W: X/spl rarr/Y} we consider decoders, possibly suboptimal, which minimize a metric defined additively by a given function d(x, y)/spl ges/0. The largest rate achievable by codes with such a decoder is called the d-capacity C/sub d/(W). The choice d(x, y)=0 if and only if (iff) W(y|x)>0 makes C/sub d/(W) equal to the "zero undetected error" or "erasures-only" capacity C/sub eo/(W). The graph-theoretic concepts of Shannon capacity (1956, 1974) and Sperner capacity are also special cases of d-capacity, viz. for a noiseless channel with a suitable {0, 1}-valued function d. We show that the lower bound on d-capacity given previously by Csiszar and Korner (1980), and Hui (1983), is not tight in general, but C/sub d/(W)>0 iff this bound is positive. The "product space" improvement of the lower bound is considered,and a "product space characterization" of C/sub eo/(W) is obtained. We also determine the erasures-only (e.o.) capacity of a deterministic arbitrarily varying channel defined by a bipartite graph, and show that it equals capacity. We conclude with a list of challenging open problems.>

We consider first the estimation of the order, i.e., the number of states, of a discrete-time finite-alphabet stationary ergodic hidden Markov source (HMS). Our estimator uses a description of the observed data in terms of a uniquely decodable code with respect to a mixture distribution, obtained by suitably mixing a parametric family of distributions on the observation space. This procedure avoids maximum likelihood calculations. The order estimator is shown to be strongly consistent with the probability of underestimation, decaying exponentially fast in the number n of observations, while the probability of overestimation does not exceed cn/sup -3/, where c is a constant. Next, we present a sequential algorithm for the uniquely decodable universal data compression of the HMS, which performs an on-line estimation of source order followed by arithmetic coding. This code asymptotically attains optimum average redundancy.>

The Gaussian arbitrarily varying channel with input constraint Gamma and state constraint Lambda admits input sequences x=(x/sub 1/,---,X/sub n/) of real numbers with Sigma x/sub i//sup 2/>

The capacity of an arbitrarily varying channel (AVC) is considered for deterministic codes with the average probability of error criterion and, typically, subject to at state constraint. First, sufficient conditions are provided that enable relatively simple decoding rules such as typicality, maximum mutual information, and minimum distance, to attain capacity. Then the (possibly noisy) OR channels and group adder channels are studied in detail. For the former the capacity is explicitly determined and shown to be attainable by minimum-distance decoding. Next, for a large class of addictive AVCs, in addition to providing an intuitively suggestive simplification of the general AVC capacity formula, it is proven that capacity can be attained by a universal decoding rule. Finally, the effect of random state selections on capacity is studied. The merits and limitations of a previous mutual information game approach are also discussed.>

Random coding theorems are proved for discrete memoryless arbitrarily varying channels (AVCs) with constraints on the transmitted codewords and channel state sequences. Two types of constraints are considered: peak (i.e. required for each n-length sequence almost surely) and average (over the message set or over an ensemble). For peak constraints on the codewords and on the channel state sequences, the AVC is shown to have a (strong) random coding capacity. If the codewords and/or the channel state sequences are constrained in the average sense, the AVCs do not possess (strong) capacities; only epsilon -capacities are shown to exist.>

A well-known result of R. Ahlswede (1970) asserts that the deterministic code capacity of an arbitrarily varying channel (AVC), under the average-error-probability criterion, either equals its random code capacity or else is zero. A necessary and sufficient condition is identified for deciding between these alternative, namely, the capacity is zero if and only if the AVC is symmetrizable. The capacity of the AVC is determined with constraints on the transmitted codewords as well as on the channel state sequences, and it is demonstrated that it may be positive but less than the corresponding random code capacity. A special case of the results resolves a weakened version of a fundamental problem of coding theory.>

The random coding capacity of a vector Gaussian arbitrarily varying channel (VGAVC) is determined, along with a simple general method for computing this capacity. The VGAVC is a discrete-time memoryless vector channel with an input power constraint and additive Gaussian noise that is further corrupted by an additive jamming signal. The statistics of this jamming signal are unknown and can be arbitrary, subject only to a power constraint.>

The {\em arbitrarily varying channel} (AVC) can be interpreted as a model of a channel jammed by an intelligent and unpredictable adversary. We investigate the asymptotic reliability of optimal random block codes on Gaussian arbitrarily varying channels (GAVC's). A GAVC is a discrete-time memoryless Gaussian channel with input power constraintP_{T}and noise powerN_{e}, which is further corrupted by an additive "jamming signal." The statistics of this signal are unknown and may be arbitrary, except that they are subject to a power constraintP_{J}. We distinguish between two types of power constraints: {\em peak} and {\em average.} For peak constraints on the input power and the jamming power we show that the GAVC has a random coding capacity. For the remaining cases in which either the transmitter or the jammer or both are subject to average power constraints, no capacities exist and only\lambda-capacities are found. The asymptotic error probability suffered by optimal random codes in these cases is determined. Our results suggest that if the jammer is subject only to an average power constraint, reliable communication is impossible at any positive code rate.

Signal sets are identified that maximize the cutoff rate region for a multiple-access channel with an additive white Gaussian noise, in which the demodulator output alphabet is allowed to be infinite ("infinitely soft decisions"). The optimizing designs consist of a simplex signal set for each sender, such that each sender's set is orthogonal to those of the other senders. For "second moment" and for "fractional out-of-band-energy" bandwidth constraints on the signals of each sender, conditions are derived under which mutually orthogonal simplex sets are still optimal. For the second moment constraint, simplex sets derived from sinusoidal functions yield an optimal design and, for the out-of-band energy constraint, simplex Sets derived from prolate spheroidal wave functions are optimal. Choices of signal sets that maximize the cutoff rate region for an additive shot-noise limited multiple-access optical channel, subject to average energy and peak amplitude constraints, are also identified.

The cutoff rate region for block coding of a two-sender one-receiver multiple-access channel is shown to be the same with and without frame synchronization between the two senders.