In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.
In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.
We consider the secret key agreement problem under the multiterminal source model proposed by Csiszár and Narayan. A single-letter characterization of the secrecy capacity is desired but remains unknown except in the extreme case with unlimited public discussion and without wiretapper's side information. Taking the problem to the opposite extreme by requiring the public discussion rate to be zero asymptotically, we obtain the desired characterization under surprisingly general setting with wiretapper's side information, silent users, trusted and untrusted helpers. An immediate consequence of the result is that the capacity with nearly no discussion is the same as the capacity with no discussion, resolving a previous conjecture in the affirmative. The idea of the proof is to characterize the capacity in the special case with neither wiretapper's side information nor untrusted helpers using a multivariate extension of Gács-Körner common information, and then extend the result to the general setting by a change of scenario that turns untrusted helpers into trusted helpers. We further show how to evaluate the capacity explicitly for finite linear sources and discuss how the current result can be extended to improve and unify existing bounds on the capacity for strictly positive discussion rates.
This work considers the problem of multiterminal secret key agreement by limited total public discussion under the hypergraphical source model. The secrecy capacity as a function of the total discussion rate is completely characterized by a polynomial-time computable linear program. Compared to the existing solution for a particular hypergraphical source model called the pairwise independent network (PIN) model, the current result is a non-trivial extension as it applies to a strictly larger class of sources and a more general scenario involving helpers and wiretapper's side information. In particular, while the existing solution by tree-packing can be strictly suboptimal for the PIN model with helpers and the hypergraphical source model in general, we can show that decremental secret key agreement and linear network coding is optimal, resolving a previous conjecture in the affirmative. The converse is established by a single-letter upper bound on the secrecy capacity for discrete memoryless multiple sources and individual discussion rate constraints. The minimax optimization involved in the bound can be relaxed to give the best existing upper bounds on secrecy capacities such as the lamination bounds for hypergraphical sources, helper-set bound for general sources, the bound at asymptotically zero discussion rate via the multivariate Gác--Körner common information, and the lower bound on communication complexity via a multivariate extension of the Wyner common information. These reductions unify existing bounding techniques and reveal surprising connections between seemingly different information-theoretic notions. Further challenges are posed in this work along with a simple example of finite linear source where the current converse techniques fail even though the proposed achieving scheme remains optimal.
For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.
The multiterminal secret key agreement problem by public discussion is formulated with an additional source compression step where, prior to the public discussion phase, users independently compress their private sources to filter out strongly correlated components in order to generate a common secret key. The objective is to maximize the achievable key rate as a function of the joint entropy of the compressed sources. Since the maximum achievable key rate captures the total amount of information mutual to the compressed sources, an optimal compression scheme essentially maximizes the multivariate mutual information per bit of randomness of the private sources, and can therefore be viewed more generally as a dimension reduction technique. Single-letter lower and upper bounds on the maximum achievable key rate are derived for the general source model, and an explicit polynomial-time computable formula is obtained for the pairwise independent network model. In particular, the converse results and the upper bounds are obtained from those of the related secret key agreement problem with rate-limited discussion. A precise duality is shown for the two-user case with one-way discussion, and such duality is extended to obtain the desired converse results in the multi-user case. In addition to posing new challenges in information processing and dimension reduction, the compressed secret key agreement problem helps shed new light on resolving the difficult problem of secret key agreement with rate-limited discussion by offering a more structured achieving scheme and some simpler conjectures to prove.
We investigate the secret key generation in the multiterminal source model, where the users discuss under limited rate. For the minimally connected hypergraphical sources, we give an explicit formula of the maximum achievable secret key rate, called the secrecy capacity, under any given total discussion rate. Besides, we also partially characterize the region of achievable secret key rate and discussion rate tuple. When specializes to the hypertree sources, our results give rise to a complete characterization of the region.
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…