This monograph describes the 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. The focus is on secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are given privileged access to correlated data of which the eavesdropper has only partial knowledge. Part I is concerned with basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Part II applies the methods of Part I to secrecy generation for the multiterminal source and channel models. Based largely on known recent results, this self-contained tutorial also includes new formulations with associated new proofs.
This monograph describes the 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. The focus is on secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are given privileged access to correlated data of which the eavesdropper has only partial knowledge. Part I is concerned with basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Part II applies the methods of Part I to secrecy generation for the multiterminal source and channel models. Based largely on known recent results, this self-contained tutorial also includes new formulations with associated new proofs.
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.
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].
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.
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 setAof 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 fromA. 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 setA, it can generate the secret key at the outset and transmit it over the noisy channel, suitably encoded, whereupon the output terminals inAsecurely 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 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.
This dissertation concerns the secure processing of distributed data by multi-ple terminals, using interactive public communication among themselves, in order to accomplish a given computational task. In the setting of a probabilistic multiterminal source model in which several terminals observe correlated random signals, we analyze secure distributed data processing protocols that harness the correlation in the data. The specific tasks considered are: computing functions of the data under secrecy requirements; generating secretly shared bits with minimal rate of public communication; and securely sharing bits in presence of a querying eavesdropper. In studying these various secure distributed processing tasks, we adopt a unified approach that entails examining the form of underlying common randomness (CR) that is generated at the terminals during distributed processing. We make the case that the exact form of established CR is linked inherently to the data processing task at hand, and its characterization can lead to a structural understanding of the associated algorithms. An identification of the underlying CR and its decomposition into independent components, each with a different operational significance, is