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:2102.01771

Secret Key Agreement and Secure Omniscience of Tree-PIN Source with Linear Wiretapper

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

Published Feb 2, 2021• 2 citations
arXivHTMLPDF

Abstract

While the wiretap secret key capacity remains unknown for general source models even in the two-user case, we obtained a single-letter characterization for a large class of multi-user source models with a linear wiretapper who can observe any linear combinations of the source. We introduced the idea of irreducible sources to show existence of an optimal communication scheme that achieves perfect omniscience with minimum leakage of information to the wiretapper. This implies a duality between the problems of wiretap secret key agreement and secure omniscience, and such duality potentially holds for more general sources.

DOI
10.48550/arxiv.2102.01771

Related papers

Secret Key Agreement and Secure Omniscience of Tree-PIN Source with Linear Wiretapper

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

In this paper, we obtain a single-letter characterization of the wiretap secret key capacity for a large class of multiterminal source models (namely, tree-PIN models) with a linear wiretapper that can observe arbitrary linear combinations of the source. For this class of sources, we also show a duality between the problems of wiretap secret key agreement and secure omniscience, which suggests that such duality potentially holds for more general sources.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•5 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

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

Secure Information Exchange for Omniscience

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

We consider the problem of exchanging sensitive information in public and provide a general formulation that can unify and extend various existing scenarios of information exchange, such as the problems of private information extraction and information bottleneck. The formulation also gives rise to a new scenario called secure omniscience (SO), where users want to exchange all their private information with minimum leakage to a wiretapper with side information. Single-letter lower and upper bounds are obtained for the minimum leakage, and the bounds are shown to be tight under the finite linear source model with two users. The bounds are derived in terms of the solutions of the closely related problems of communication for omniscience (CO) and secret key agreement (SKA). However, we find examples where the bounds are not tight, and so the connections to CO and SKA are not precise. In particular, it is possible that any optimal CO scheme that minimizes communication does not minimize leakage, and any optimal SO scheme that minimizes leakage does not attain the capacity for SKA. Nevertheless, we identify a useful notion of information alignment that can modify an optimal CO scheme to reduce leakage for SO.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•5 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

Wiretap Secret Key Capacity of Tree-PIN

Alireza Poostindouz, Reihaneh Safavi–Naini

Secret key agreement (SKA) is an essential primitive in cryptography and information security. In a multiterminal key agreement problem, there are a set of terminals each having access to a component of a vector random variable, and the goal of the terminals is to establish a shared key among a designated subset of terminals. This problem has been studied under different assumptions about the adversary. In the most general model, the adversary has access to a random variable Z, that is correlated with all terminals' variables. The single-letter characterization of the secret key capacity of this model, known as the wiretap secret key capacity, is not known for an arbitrary Z. In this paper, we calculate the wiretap secret key capacity of a Tree-PIN, when Z consists of noisy version of terminals' variables. We also derive an upper bound and a lower bound for the wiretap secret key capacity of a PIN, and prove their tightness for some special cases.

arXiv:1903.06134•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•9 citations
While the wiretap secret key capacity remains unknown for general source models even in the two-user case, we obtained a single-letter characterization for a large class of multi-user source models with a linear wiretapper who can observe any linear combinations of the source. We introduced the idea of irreducible sources to show existence of an optimal communication scheme that achieves perfect omniscience with minimum leakage of information to the wiretapper. This implies a duality between the problems of wiretap secret key agreement and secure omniscience, and such duality potentially holds for more general sources.
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.
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.
We consider the problem of exchanging sensitive information in public and provide a general formulation that can unify and extend various existing scenarios of information exchange, such as the problems of private information extraction and information bottleneck. The formulation also gives rise to a new scenario called secure omniscience (SO), where users want to exchange all their private information with minimum leakage to a wiretapper with side information. Single-letter lower and upper bounds are obtained for the minimum leakage, and the bounds are shown to be tight under the finite linear source model with two users. The bounds are derived in terms of the solutions of the closely related problems of communication for omniscience (CO) and secret key agreement (SKA). However, we find examples where the bounds are not tight, and so the connections to CO and SKA are not precise. In particular, it is possible that any optimal CO scheme that minimizes communication does not minimize leakage, and any optimal SO scheme that minimizes leakage does not attain the capacity for SKA. Nevertheless, we identify a useful notion of information alignment that can modify an optimal CO scheme to reduce leakage for SO.
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.
Secret key agreement (SKA) is an essential primitive in cryptography and information security. In a multiterminal key agreement problem, there are a set of terminals each having access to a component of a vector random variable, and the goal of the terminals is to establish a shared key among a designated subset of terminals. This problem has been studied under different assumptions about the adversary. In the most general model, the adversary has access to a random variable Z, that is correlated with all terminals' variables. The single-letter characterization of the secret key capacity of this model, known as the wiretap secret key capacity, is not known for an arbitrary Z. In this paper, we calculate the wiretap secret key capacity of a Tree-PIN, when Z consists of noisy version of terminals' variables. We also derive an upper bound and a lower bound for the wiretap secret key capacity of a PIN, and prove their tightness for some special cases.