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 · 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
arXivHTMLPDF

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

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

Multiterminal Secret Key Agreement with Nearly No Discussion

Chung Chan, Manuj Mukherjee, Praneeth Kumar Vippathalla +1 more

We consider the secret key agreement problem under the multiterminal source model proposed by Csiszár and Narayan. A single-letter characterization of the secrecy capacity is desired but remains unknown except in the extreme case with unlimited public discussion and without wiretapper's side information. Taking the problem to the opposite extreme by requiring the public discussion rate to be zero asymptotically, we obtain the desired characterization under surprisingly general setting with wiretapper's side information, silent users, trusted and untrusted helpers. An immediate consequence of the result is that the capacity with nearly no discussion is the same as the capacity with no discussion, resolving a previous conjecture in the affirmative. The idea of the proof is to characterize the capacity in the special case with neither wiretapper's side information nor untrusted helpers using a multivariate extension of Gács-Körner common information, and then extend the result to the general setting by a change of scenario that turns untrusted helpers into trusted helpers. We further show how to evaluate the capacity explicitly for finite linear sources and discuss how the current result can be extended to improve and unify existing bounds on the capacity for strictly positive discussion rates.

arXiv:1904.11383•Apr 25, 2019•2 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•21 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.
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.
We consider the secret key agreement problem under the multiterminal source model proposed by Csiszár and Narayan. A single-letter characterization of the secrecy capacity is desired but remains unknown except in the extreme case with unlimited public discussion and without wiretapper's side information. Taking the problem to the opposite extreme by requiring the public discussion rate to be zero asymptotically, we obtain the desired characterization under surprisingly general setting with wiretapper's side information, silent users, trusted and untrusted helpers. An immediate consequence of the result is that the capacity with nearly no discussion is the same as the capacity with no discussion, resolving a previous conjecture in the affirmative. The idea of the proof is to characterize the capacity in the special case with neither wiretapper's side information nor untrusted helpers using a multivariate extension of Gács-Körner common information, and then extend the result to the general setting by a change of scenario that turns untrusted helpers into trusted helpers. We further show how to evaluate the capacity explicitly for finite linear sources and discuss how the current result can be extended to improve and unify existing bounds on the capacity for strictly positive discussion rates.
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.