Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1507.02874 · IEEE Transactions on Information Theory

On the Public Communication Needed to Achieve SK Capacity in the Multiterminal Source Model

Manuj Mukherjee, Navin Kashyap, Yogesh Sankarasubramaniam

Published Feb 23, 2016• 32 citations
arXivHTMLPDF

Abstract

The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, RSK, defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on RSK. For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type S condition, which is verifiable in polynomial time, guarantees that our lower bound on RSKmeets the RCOupper bound. Thus, the PIN models satisfying our condition are RSK-maximal, indicating that the upper bound RSK≤ RCOholds with equality. This allows us to explicitly evaluate RSKfor such PIN models. We also give several examples of PIN models that satisfy our Type S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general.

DOI
10.1109/tit.2016.2533546

Related papers

The communication complexity of achieving SK capacity in a class of PIN models

Manuj Mukherjee, Navin Kashyap

The communication complexity of achieving secret key (SK) capacity in the multiterminal source model of Csiszár and Narayan is the minimum rate of public communication required to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on the communication complexity, denoted by RSK. A source model for which this upper bound is tight is called RSK-maximal. In this paper, we establish a sufficient condition for RSK-maximality within the class of pairwise independent network (PIN) models defined on hypergraphs. This allows us to compute RSKexactly within the class of PIN models satisfying this condition. On the other hand, we also provide a counterexample that shows that our condition does not in general guarantee RSK-maximality for sources beyond PIN models.

arXiv:1504.00629•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•9 citations

Secret Key Generation in the Multiterminal Source Model : Communication and Other Aspects

Manuj Mukherjee

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…

•Jan 1, 2017•0 citations

Bounds on the communication rate needed to achieve SK capacity in the hypergraphical source model

Manuj Mukherjee, Chung Chan, Navin Kashyap +1 more

In the multiterminal source model of Csiszár and Narayan, the communication complexity, RSK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to RSKis given by RCO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to RSKfor the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on RSK. This bound, however, is not tight, as demonstrated by a counterexample.

arXiv:1601.05377•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•9 citations

On the communication complexity of secret key generation in the multiterminal source model

Manuj Mukherjee, Navin Kashyap

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszár and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

arXiv:1401.1117•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•9 citations

Bounds on the Communication Rate Needed to Achieve SK Capacity in the Hypergraphical Source Model

Manuj Mukherjee, Chung Chan, Navin Kashyap +1 more

In the multiterminal source model of Csiszar and Narayan, the communication complexity, R-SK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to R-SK is given by R-CO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to R-SK for the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on R-SK. This bound, however, is not tight, as demonstrated by a counterexample.

•Jan 1, 2016•9 citations

Achieving SK capacity in the source model: When must all terminals talk?

Manuj Mukherjee, Navin Kashyap, Yogesh Sankarasubramaniam

In this paper, we address the problem of characterizing the instances of the multiterminal source model of Csiszár and Narayan in which communication from all terminals is needed for establishing a secret key of maximum rate. We give an information-theoretic sufficient condition for identifying such instances. We believe that our sufficient condition is in fact an exact characterization, but we are only able to prove this in the case of the three-terminal source model.

arXiv:1401.5037•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•13 citations
The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, RSK, defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on RSK. For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type S condition, which is verifiable in polynomial time, guarantees that our lower bound on RSKmeets the RCOupper bound. Thus, the PIN models satisfying our condition are RSK-maximal, indicating that the upper bound RSK≤ RCOholds with equality. This allows us to explicitly evaluate RSKfor such PIN models. We also give several examples of PIN models that satisfy our Type S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general.
The communication complexity of achieving secret key (SK) capacity in the multiterminal source model of Csiszár and Narayan is the minimum rate of public communication required to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on the communication complexity, denoted by RSK. A source model for which this upper bound is tight is called RSK-maximal. In this paper, we establish a sufficient condition for RSK-maximality within the class of pairwise independent network (PIN) models defined on hypergraphs. This allows us to compute RSKexactly within the class of PIN models satisfying this condition. On the other hand, we also provide a counterexample that shows that our condition does not in general guarantee RSK-maximality for sources beyond PIN models.
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…
In the multiterminal source model of Csiszár and Narayan, the communication complexity, RSK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to RSKis given by RCO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to RSKfor the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on RSK. This bound, however, is not tight, as demonstrated by a counterexample.
Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszár and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.
In the multiterminal source model of Csiszar and Narayan, the communication complexity, R-SK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to R-SK is given by R-CO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to R-SK for the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on R-SK. This bound, however, is not tight, as demonstrated by a counterexample.