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

IEEE International Symposium on Information Theory (ISIT)

Secret key generation with one communicator and a one-shot converse via hypercontractivity

Jingbo Liu, Paul Cuff, Sergio Verdú

Published Jun 1, 2015• 31 citations
Publisher

Abstract

A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.

DOI
10.1109/isit.2015.7282547

Related papers

Secret Key Generation with One Communicator and a Zero-Rate One-Shot via Hypercontractivity

Jingbo Liu, Paul Cuff, Sergio Verdú

A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.

arXiv:1504.05526•Apr 21, 2015•1 citation

New bounds on the information-theoretic key agreement of multiple terminals

Amin Gohari, Venkat Anantharam

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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•14 citations

On the Optimality of Secret Key Agreement via Omniscience

Chung Chan, Manuj Mukherjee, Navin Kashyap +1 more

For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources, including the hypergraphical sources. We also extend our results to more general class of multiterminal sources with helpers and silent users.

arXiv:1702.07429•IEEE Transactions on Information Theory•Feb 5, 2018•22 citations

Converse results for secrecy generation over channels

Himanshu Tyagi, Shun Watanabe

We revisit the problem of secret key agreement in channel models, where in addition to a noisy, albeit secure channel, the terminals have access to a noiseless public communication channel. We show a strong converse for the secret key capacity in the point-to-point model and give upper bounds for the general case. Underlying our proofs is a recently discovered single-shot converse for secret key rates in multiterminal source models.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2014•0 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

Secrecy Generation for Multiaccess Channel Models

Imre Csiszár, Prakash Narayan

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.

IEEE Transactions on Information Theory•Aug 29, 2012•20 citations
A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.
A new model of multi-party secret key agreement is proposed, in which one terminal called the communicator can transmit public messages to other terminals before all terminals agree on a secret key. A single-letter characterization of the achievable region is derived in the stationary memoryless case. The new model generalizes some other (old and new) models of key agreement. In particular, key generation with an omniscient helper is the special case where the communicator knows all sources, for which we derive a zero-rate one-shot converse for the secret key per bit of communication.
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.
For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources, including the hypergraphical sources. We also extend our results to more general class of multiterminal sources with helpers and silent users.
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…
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.