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 Agreement and Secure Omniscience of Tree-PIN Source with Linear Wiretapper

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

Published Jul 12, 2021• 5 citations
Publisher

Abstract

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.

DOI
10.1109/isit45174.2021.9518075

Related papers

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

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

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.

arXiv:2102.01771•Feb 2, 2021•2 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

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

Secret Key Capacity of Wiretapped Polytree-PIN

Alireza Poostindouz, Reihaneh Safavi–Naini

In secret key agreement (SKA) in multiterminal channel model, terminals are connected by a noisy discrete memoryless channel (DMC) with multiple input and multiple outputs. Terminals can use the DMC to obtain correlated randomness, and communicate over a noiseless public channel to establish a shared secret key among a designated subset of terminals. We focus on a special class of multiterminal channel models, called wiretapped Polytree-PIN, in which the noisy channel consists of a set of independent point-to-point channels whose underlying undirected connectivity graph forms a tree. We consider a wiretap setting, where the output of each point-to-point channel is partially leaked to a passive wiretapper adversary, Eve, through a second independent noisy channel. A secure SKA protocol generates a group secret key such that Eve has no information about it. In this paper, we derive the wiretap secret key capacity, which is the largest achievable secret key rate, of the wiretapped PolytreePIN model. Our result also implies the key capacity of the non-wiretapped Polytree-PIN model, that is the case when there is no leakage from point-to-point channels to Eve.

IEEE Information Theory Workshop (ITW)•Oct 17, 2021•0 citations

Positivity of Secret Key Capacity for Hypergraphical Sources with a Linear Wiretapper

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

The characterization of the secret key capacity with wiretapper side information is a challenging open problem. In this paper, we give a necessary and sufficient condition for the positivity of wiretap secret key capacity for the multiterminal source model. This result extends the existing works for two-terminal sources. However, in the case of hypergraphical source models with a linear wiretapper, we derive a simpler equivalent condition for the positivity. We also show that blocklength need not be larger than the logarithm of the number of edges in order to generate a positive rate key. The proofs of these results involve a subclass called minimally connected hypergraphical sources with a linear wiretapper, for which we obtain a single-letter characterization of wiretap secret key capacity.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•2 citations
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.
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.
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.
In secret key agreement (SKA) in multiterminal channel model, terminals are connected by a noisy discrete memoryless channel (DMC) with multiple input and multiple outputs. Terminals can use the DMC to obtain correlated randomness, and communicate over a noiseless public channel to establish a shared secret key among a designated subset of terminals. We focus on a special class of multiterminal channel models, called wiretapped Polytree-PIN, in which the noisy channel consists of a set of independent point-to-point channels whose underlying undirected connectivity graph forms a tree. We consider a wiretap setting, where the output of each point-to-point channel is partially leaked to a passive wiretapper adversary, Eve, through a second independent noisy channel. A secure SKA protocol generates a group secret key such that Eve has no information about it. In this paper, we derive the wiretap secret key capacity, which is the largest achievable secret key rate, of the wiretapped PolytreePIN model. Our result also implies the key capacity of the non-wiretapped Polytree-PIN model, that is the case when there is no leakage from point-to-point channels to Eve.
The characterization of the secret key capacity with wiretapper side information is a challenging open problem. In this paper, we give a necessary and sufficient condition for the positivity of wiretap secret key capacity for the multiterminal source model. This result extends the existing works for two-terminal sources. However, in the case of hypergraphical source models with a linear wiretapper, we derive a simpler equivalent condition for the positivity. We also show that blocklength need not be larger than the logarithm of the number of edges in order to generate a positive rate key. The proofs of these results involve a subclass called minimally connected hypergraphical sources with a linear wiretapper, for which we obtain a single-letter characterization of wiretap secret key capacity.