In this paper, we study both topological and algebraic properties of unrooted Gaussian trees in order to characterize their security performance. Such performance is measured by the corresponding potential in extracting common randomness from a given tree, which is further determined by max-min and min-max conditional mutual information (CMI) values, subject to the order of selecting variables from the tree by legitimate nodes Alice and Bob, and an eavesdropper Eve, respectively. A new operation is proposed to transform a Gaussian tree into another, and also to order different Gaussian trees. Through such operation we construct several equivalent classes of Gaussian trees. Each class includes multiple Gaussian trees that can be partially ordered based on the associated max-min or min-max CMI metric, and thus, we can find the most secure and the least secure trees in each partially ordered set (poset). The union of all posets generates all possible non-isomorphic trees of the given number of variables. Then, we assign a particular polynomial to each Gaussian tree, and show that such polynomial can determine the relative security performance of the Gaussian tree with respect to other trees within the same class. In the end, based on a generalized integer partition method, we propose a novel approach to efficiently enumerate the most secure structures of all posets.
In this paper, we study both topological and algebraic properties of unrooted Gaussian trees in order to characterize their security performance. Such performance is measured by the corresponding potential in extracting common randomness from a given tree, which is further determined by max-min and min-max conditional mutual information (CMI) values, subject to the order of selecting variables from the tree by legitimate nodes Alice and Bob, and an eavesdropper Eve, respectively. A new operation is proposed to transform a Gaussian tree into another, and also to order different Gaussian trees. Through such operation we construct several equivalent classes of Gaussian trees. Each class includes multiple Gaussian trees that can be partially ordered based on the associated max-min or min-max CMI metric, and thus, we can find the most secure and the least secure trees in each partially ordered set (poset). The union of all posets generates all possible non-isomorphic trees of the given number of variables. Then, we assign a particular polynomial to each Gaussian tree, and show that such polynomial can determine the relative security performance of the Gaussian tree with respect to other trees within the same class. In the end, based on a generalized integer partition method, we propose a novel approach to efficiently enumerate the most secure structures of all posets.
In this paper, our objective is to find out how topological and algebraic properties of unrooted Gaussian tree models determine their security robustness, which is measured by our proposed max-min information (MaMI) metric. Such metric quantifies the amount of common randomness extractable through public discussion between two legitimate nodes under an eavesdropper attack. We show some general topological properties that the desired max-min solutions shall satisfy. Under such properties, we develop conditions under which comparable trees are put together to form partially ordered sets (posets). Each poset contains the most favorable structure as the poset leader, and the least favorable structure. Then, we compute the Tutte-like polynomial for each tree in a poset in order to assign a polynomial to any tree in a poset. Moreover, we propose a novel method, based on restricted integer partitions, to effectively enumerate all poset leaders. The results not only help us understand the security strength of different Gaussian trees, which is critical when we evaluate the information leakage issues for various jointly Gaussian distributed measurements in networks, but also provide us both an algebraic and a topological perspective in grasping some fundamental properties of such models.
In this work, our objective is to find out how topological and algebraic properties of unrooted Gaussian tree models determine their security robustness, which is measured by our proposed max-min information (MaMI) metric. Such metric quantifies the amount of common randomness extractable through public discussion between two legitimate nodes under an eavesdropper attack. We show some general topological properties that the desired max-min solutions shall satisfy. Under such properties, we develop conditions under which comparable trees are put together to form partially ordered sets (posets). Each poset contains the most favorable structure as the poset leader, and the least favorable structure. Then, we compute the Tutte-like polynomial for each tree in a poset in order to assign a polynomial to any tree in a poset. Moreover, we propose a novel method, based on restricted integer partitions, to effectively enumerate all poset leaders. The results not only help us understand the security strength of different Gaussian trees, which is critical when we evaluate the information leakage issues for various jointly Gaussian distributed measurements in networks, but also provide us both an algebraic and a topological perspective in grasping some fundamental properties of such models.
In this paper, our objective is to find out how topological and algebraic properties of unrooted Gaussian tree models determine their security robustness, which is measured by our proposed max-min information (MaMI) metric. Such metric quantifies the amount of common randomness extractable through public discussion between two legitimate nodes under an eavesdropper attack. We show some general topological properties that the desired max-min solutions shall satisfy. Under such properties, we develop conditions under which comparable trees are put together to form partially ordered sets (posets). Each poset contains the most favorable structure as the poset leader, and the least favorable structure. Then, we compute the Tutte-like polynomial for each tree in a poset in order to assign a polynomial to any tree in a poset. Moreover, we propose a novel method, based on restricted integer partitions, to effectively enumerate all poset leaders. The results not only help us understand the security strength of different Gaussian trees, which is critical when we evaluate the information leakage issues for various jointly Gaussian distributed measurements in networks, but also provide us both an algebraic and a topological perspective in grasping some fundamental properties of such models.
Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.
This monograph describes principles of information theoretic secrecy generation by legitimate parties with public discussion in the presence of an eavesdropper. The parties are guaranteed secrecy in the form of independence from the eavesdropper’s observation of the communication. Part I develops basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Various information theoretic and cryptographic notions of secrecy are compared. Emphasis is placed on central themes of interactive communication and common randomness as well as on core methods of balanced coloring and leftover hash for extracting secret uniform randomness. Achievability and converse results are shown to emerge from “single shot” incarnations that serve to explain essential structure. Part II applies the methods of Part I to secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are afforded privileged access to correlated observations of which the eavesdropper has only partial knowledge. Characterizations of secret key capacity bring out inherent connections to the data compression concept of omniscience and, for a specialized source model, to a combinatorial problem of maximal spanning tree packing in a multigraph. Interactive common information is seen to govern the minimum rate of communication needed to achieve secret key capacity in the two-terminal source model. Furthermore, necessary and sufficient conditions are analyzed for the secure computation of a given function in the multiterminal source model. Based largely on known recent results, this self-contained monograph also includes new formulations with associated new proofs. Supplementing each chapter in Part II are descriptions of several open problems.
In this paper, the compression of an independent and identically distributed Gaussian source sequence is studied in an unsecure network. Within a game theoretic setting for a three-party noiseless communication network (sender Alice, legitimate receiver Bob, and eavesdropper Eve), the problem of how to efficiently compress a Gaussian source with limited secret key in order to guarantee that Bob can reconstruct with high fidelity while preventing Eve from estimating an accurate reconstruction is investigated. It is assumed that Alice and Bob share a secret key with limited rate. Three scenarios are studied, in which the eavesdropper ranges from weak to strong in terms of the causal side information she has. It is shown that one bit of secret key per source symbol is enough to achieve perfect secrecy performance in the Gaussian squared error setting, and the information theoretic region is not optimized by joint Gaussian random variables.