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• 4 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•28 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.

IEEE Transactions on Information Theory•Oct 24, 2023•0 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

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

Wiretap 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 a wiretapper who has 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 wiretapper. The starting point of our work is a lower bound on the minimum leakage rate for omniscience, $R_{\mathop{\mathrm{L}}}$, in terms of the wiretap secret key capacity, $C_{\mathop{\mathrm{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 wiretapper. Duality also holds for any FLS model in which $C_{\mathop{\mathrm{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•Dec 1, 2021•1 citation

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•7 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.
In this paper, we explore the connection between secret key agreement and secure omniscience within the setting of the multiterminal source model with a wiretapper who has 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 wiretapper. The starting point of our work is a lower bound on the minimum leakage rate for omniscience, RLR_{\mathop{\mathrm{L}}}RL​, in terms of the wiretap secret key capacity, CWC_{\mathop{\mathrm{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 wiretapper. Duality also holds for any FLS model in which CWC_{\mathop{\mathrm{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.
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.