We derive a new upper bound on the secrecy capacity in the source model with eavesdropper which strictly improves the currently best upper bound, i.e. the double intrinsic information bound of Renner and Wolf. Furthermore, unlike that bound, which is defined only in the case of two terminals, the new upper bound is not specific to the two terminals case. We define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement.
We derive a new upper bound on the secrecy capacity in the source model with eavesdropper which strictly improves the currently best upper bound, i.e. the double intrinsic information bound of Renner and Wolf. Furthermore, unlike that bound, which is defined only in the case of two terminals, the new upper bound is not specific to the two terminals case. We define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement.
We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models, multiple terminals wish to create a shared secret key that is secure from a passive eavesdropper. The terminals have access to a noiseless public communication channel and an additional resource that depends on the model. In the source model, the resource is an external source that repeatedly beams correlated randomness to the terminals; whereas in the channel model, the resource is a secure but noisy discrete memoryless broadcast channel. We derive new lower and upper bounds on the secret key capacity under both the source model and the channel model. The technique used for deriving our bound for the source model is to find certain properties of functions of joint probability distributions which, applied to the joint distribution of the source, will imply that they dominate the secret key capacity, and then prove the bound by a verification argument. A similar technique is used for the channel model. Finally, we also define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement. This generalizes an earlier result of Csiszár and Narayan.
We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models the parties wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. In the channel model, the first party can choose a sequence of inputs to a discrete memoryless channel, which has outputs at the other parties and at the eavesdropper. After each channel use, the parties can engage in arbitrarily many rounds of interactive authenticated communication over a public channel. At the end, each party should be able to generate the key. In the source model, the parties wishing to generate a secret key (as well as the eavesdropper) receive a certain number of independent identically distributed copies of jointly distributed random variables after which the parties are allowed interactive authenticated public communication, at the end of which each party should be able to generate the key. We derive new lower and upper bounds on the secret key rate under the source model and the channel model, and introduce a technique for proving that a given expression bounds the secrecy rate from above in the channel model. Our lower bounds strictly improve what is essentially the best known lower bound in both the source model and the channel model. Our upper bound in the channel model strictly improves the current state of art upper bound. We do not know whether our new upper bound in the source model represents an strict improvement but it includes the current best known bound as a special case.
In this paper, we explore the connection between secret key agreement and secure omniscience within the setting of the multiterminal source model with an eavesdropper having side information. While the secret key agreement problem considers the generation of a maximum-rate secret key through public discussion, the secure omniscience problem is concerned with communication protocols for omniscience that minimize the rate of information leakage to the eavesdropper. The starting point of our work is a lower bound on the minimum leakage rate for omniscience,RL, in terms of the wiretap secret key capacity,CW. Our interest is in identifying broad classes of sources for which this lower bound is met with equality, in which case we say that there is a duality between secure omniscience and secret key agreement. We show that this duality holds in the case of certain finite linear source (FLS) models, such as two-terminal FLS models and pairwise independent network models on trees with a linear eavesdropper. Duality also holds for any FLS model in whichCWis achieved by a perfect linear secret key agreement scheme. We conjecture that the duality in fact holds unconditionally for any FLS model. On the negative side, we give an example of a (non-FLS) source model for which duality does not hold if we limit ourselves to communication-for-omniscience protocols with at most two (interactive) communications. We also address the secure function computation problem and explore the connection between the minimum leakage rate for computing a function and the wiretap secret key capacity.
This is the second part of a two-part paper on information-theoretically secure secret key agreement. This part covers the secret key capacity under the channel model. In this model, multiple terminals wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. The terminals are all connected to a noiseless and authenticated but insecure channel, called the “public channel.” Furthermore, the terminals have access to a secure but noisy discrete memoryless broadcast channel (DMBC). The first terminal can choose a sequence of inputs to the DMBC, which has outputs at the other terminals and at the eavesdropper. After each channel use, the terminals can engage in arbitrarily many rounds of interactive authenticated communication over the public channel. At the end, each legitimate terminal should be able to generate the secret key. In this paper, we derive new lower and upper bounds on the secrecy capacity. In each case, an example is provided to show that the new bound represents a strict improvement over the previously best known bound. This part of the paper is not standalone, and is written under the assumption that the reader has access to Part I, which is published in the same issue.
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.
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].