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:1901.05817 · IEEE International Symposium on Information Theory (ISIT)

One-Shot Perfect Secret Key Agreement for Finite Linear Sources

Chung Chan, Navin Kashyap, Praneeth Kumar Vippathalla, Qiaoqiao Zhou

Published Jul 1, 2019• 2 citations
arXivHTMLPDF

Abstract

We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.

DOI
10.1109/isit.2019.8849668

Related papers

Linear perfect secret key agreement

Chung Chan

A linear scheme is proposed for multiterminal secret key agreement under a private finite linear source model with public discussion. With a wiretapper observing the public discussion and a subset of the source components, it attains the secrecy capacity perfectly and non-asymptotically with a finite block length. Upper bounds on the block length and public discussion rate are given.

IEEE Information Theory Workshop (ITW)•Oct 1, 2011•26 citations

Secret Key Agreement via Secure Omniscience

Praneeth Kumar Vippathalla, Chung Chan, Navin Kashyap +1 more

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,$R_{ \text {L}}$, in terms of the wiretap secret key capacity,$C_{ \text {W}}$. 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 which$C_{ \text {W}}$is 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.

arXiv:2112.00394•IEEE Transactions on Information Theory•Oct 24, 2023•1 citation

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•21 citations

One-Shot Variable-Length Secret Key Agreement Approaching Mutual Information

Cheuk Ting Li, Venkat Anantharam

This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process.

arXiv:1809.01793•IEEE Transactions on Information Theory•Jun 9, 2021•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

One-Shot Variable-Length Secret Key Agreement Approaching Mutual Information

Cheuk Ting Li, Venkat Anantharam

This paper studies an information-theoretic oneshot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X; Y ) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X; Y ) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X, Y ). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn, Y n) are observed sequentially and the key is output bit by bit with small delay, or in situations.

Allerton Conference on Communication, Control, and Computing•Oct 1, 2018•6 citations
We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.
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,RLR_{ \text {L}}RL​, in terms of the wiretap secret key capacity,CWC_{ \text {W}}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 whichCWC_{ \text {W}}CW​is 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.
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 paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process.
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…
This paper studies an information-theoretic oneshot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X; Y ) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X; Y ) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X, Y ). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn, Y n) are observed sequentially and the key is output bit by bit with small delay, or in situations.