Secret key generation is considered for a pair of terminals that observe correlated sources and communicate interactively over a public channel. It is argued that optimum rate secret key generation is linked inherently to the Wyner's notion of common information between two dependent random variables. The minimum rate of interactive public communication required to generate an optimum rate secret key is characterized in terms of a variant of this notion of common information.
Secret key generation is considered for a pair of terminals that observe correlated sources and communicate interactively over a public channel. It is argued that optimum rate secret key generation is linked inherently to the Wyner's notion of common information between two dependent random variables. The minimum rate of interactive public communication required to generate an optimum rate secret key is characterized in terms of a variant of this notion of common information.
We study the generation of a secret key of maximum rate by a pair of terminals observing correlated sources and with the means to communicate over a noiseless public communication channel. Our main result establishes a structural equivalence between the generation of a maximum rate secret key and the generation of a common randomness that renders the observations of the two terminals conditionally independent. The minimum rate of such common randomness, termed interactive common information, is related to Wyner's notion of common information, and serves to characterize the minimum rate of interactive public communication required to generate an optimum rate secret key. This characterization yields a single-letter expression for the aforementioned communication rate when the number of rounds of interaction are bounded. An application of our results shows that interaction does not reduce this rate for binary symmetric sources. Further, we provide an example for which interaction does reduce the minimum rate of communication. Also, certain invariance properties of common information quantities are established that may be of independent interest.
Secret key generation at two terminals is considered. Each terminal observes one of the outputs of a two component source. The two source outputs are correlated. Additionally one terminal can send a message to the second terminal via a noiseless public channel. It is assumed that this message is rate constrained. An eavesdropper with access to the public communication should be kept ignorant of the secret key. The maximum secret key rate that can be achieved such that the key is uniformly distributed and meets the perfect secrecy requirement is determined. This result is established for a compound source model.
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.
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 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.
This dissertation is primarily concerned with the communication required to achieve secret key (SK) capacity in a multiterminal source model. The multiterminal source model introduced by Csiszar and Narayan consists of a group of remotely located terminals with access to correlated sources and a noiseless public channel. The terminals wish to secure their communication by agreeing upon a group secret key. The key agreement protocol involves communicating over the public channel, and agreeing upon an SK secured from eavesdroppers listening to the public communication. The SK capacity, i.e., the maximum rate of an SK that can be agreed upon by the terminals, has been characterized by Csiszar and Narayan. Their capacity-achieving key generation protocol involved terminals communicating to attain omniscience, i.e., every terminal gets to recover the sources of the other terminals. While this is a very general protocol, it often requires larger rates of public communication than is necessary to achieve SK capacity.
The primary focus of this dissertation is to characterize the communication complexity, i.e., the minimum rate of public discussion needed to achieve SK capacity. A lower bound to communication complexity is derived for a general multiterminal source, although it turns out to be loose in general. While the minimum rate of communication for omniscience is always an upper bound to the communication complexity, we derive tighter upper bounds to communication complexity for a special class of multiterminal sources, namely, the hypergraphical sources. This upper bound yield a complete characterization of hypergraphical sources where communication for omniscience is a rate-optimal protocol for SK generation, i.e., the communication complexity equals the minimum rate of communication for omniscience.
Another aspect of the public communication touched upon by this dissertation is the necessity of omnivocality, i.e., all terminals communicating, to achieve the SK capacity. It is well known that in two-terminal sources, only one terminal communicating success to generate a maximum rate secret key. However, we are able to show that for three or more terminals, omnivocality is indeed required to achieve SK capacity if a certain condition is met. For the specific case of three terminals, we show that this condition is also necessary to ensure omnivocality is essential in generating a SK of maximal rate. However, this condition is no longer necessary when there are four or more terminals.
A certain notion of common information, namely, the Wyner common information, plays a central role in the communication complexity problem. This dissertation thus includes a study of multiparty versions of the two widely used notions of common information, namely, Wyner common information and Gacs-Korner (GK) common information. While evaluating these quantities is difficult in general, we are able to derive explicit expressions for both types of common information in the case of hypergraphical sources.
We also study fault-tolerant SK…