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

Wiretap Secret Key Capacity of Tree-PIN

Alireza Poostindouz, Reihaneh Safavi–Naini

Published Jul 1, 2019• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit.2019.8849553

Related papers

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

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

Secrecy Capacities for Multiple Terminals

Imre Csiszár, Prakash Narayan

We derive single-letter characterizations of (strong) secrecy capacities for models with an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unrestricted and interactive public communication permitted between the terminals. A subset of these terminals can serve as helpers for the remaining terminals in generating secrecy. According to the extent of an eavesdropper's knowledge, three kinds of secrecy capacity are considered: secret key (SK), private key (PK), and wiretap secret key (WSK) capacity. The characterizations of the SK and PK capacities highlight the innate connections between secrecy generation and multiterminal source coding without secrecy requirements. A general upper bound for WSK capacity is derived which is tight in the case when the eavesdropper can wiretap noisy versions of the components of the underlying multiple source, provided randomization is permitted at the terminals. These secrecy capacities are seen to be achievable with noninteractive communication between the terminals. The achievability results are also shown to be universal.

IEEE Transactions on Information Theory•Nov 30, 2004•427 citations

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

Information theoretic secret key generation: structured codes and tree packing

Prakash Narayan, Sirin Nitinawarat

This dissertation deals with a multiterminal source model for secret key generation by multiple network terminals with prior and privileged access to a set of correlated signals complemented by public discussion among themselves. Emphasis is placed on a characterization of secret key capacity, i.e., the largest rate of an achievable secret key, and on algorithms for key construction. Various information theoretic security requirements of increasing stringency: weak, strong and perfect secrecy, as well as different types of sources: finite-valued and continuous, are studied. Specifically, three different models are investigated. First, we consider strong secrecy generation for a discrete multiterminal source model. We discover a connection between secret key capacity and a new source coding concept of "minimum information rate for signal dissemination," that is of independent interest in multiterminal data compression. Our main contribution is to show for this discrete model that structured linear codes suffice to generate a strong secret key of the best rate. Second, strong secrecy generation is considered for models with continuous observations, in particular jointly Gaussian signals. In the absence of suitable analogs of source coding notions for the previous discrete model, new techniques are required for a characterization of secret key capacity as well as for the design of algorithms for secret key generation. Our proof of the secret key capacity result, in particular the converse proof, as well as our capacity-achieving algorithms for secret key construction based on structured codes and quantization for a model with two terminals, constitute the two main contributions for this second model. Last, we turn our attention to perfect secrecy generation for fixed signal observation lengths as well as for their asymptotic limits. In contrast with the analysis of the previous two models that relies on probabilistic techniques, perfect secret key generation bears the essence of "zero-error information theory," and accordingly, we rely on mathematical techniques of a combinatorial nature. The model under consideration is the "Pairwise Independent Network" (PIN) model in which every pair of terminals share a random binary string, with the strings shared by distinct pairs of terminals being mutually independent. This model, which is motivated by practical aspects of a wireless communication network in which terminals communicate on the same frequency, results in three main contributions. First, the concept of perfect omniscience in data compression leads to a single-letter formula for the perfect secret key capacity of the PIN model; moreover, this capacity is shown to be achieved by linear noninteractive public communication, and coincides with strong secret key capacity. Second, taking advantage of a multigraph representation of the PIN model, we put forth an efficient algorithm for perfect secret key generation based on a combinatorial concept of maximal packing of Steiner trees of the multigraph. When all the terminals seek to share perfect secrecy, the algorithm is shown to achieve capacity. When only a subset of terminals wish to share perfect secrecy, the algorithm is shown to achieve at least half of it. Additionally, we obtain nonasymptotic and asymptotic bounds on the size and rate of the best perfect secret key generated by the algorithm. These bounds are of independent interest from a purely graph theoretic viewpoint as they constitute new estimates for the maximum size and rate of Steiner tree packing of a given multigraph. Third, a particular configuration of the PIN model arises when a lone "helper" terminal aids all the other "user" terminals generate perfect secrecy. This model has special features that enable us to obtain necessary and sufficient conditions for Steiner tree packing to achieve perfect secret key capacity.

ProQuest LLC eBooks•Jan 1, 2010•0 citations
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.
We derive single-letter characterizations of (strong) secrecy capacities for models with an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unrestricted and interactive public communication permitted between the terminals. A subset of these terminals can serve as helpers for the remaining terminals in generating secrecy. According to the extent of an eavesdropper's knowledge, three kinds of secrecy capacity are considered: secret key (SK), private key (PK), and wiretap secret key (WSK) capacity. The characterizations of the SK and PK capacities highlight the innate connections between secrecy generation and multiterminal source coding without secrecy requirements. A general upper bound for WSK capacity is derived which is tight in the case when the eavesdropper can wiretap noisy versions of the components of the underlying multiple source, provided randomization is permitted at the terminals. These secrecy capacities are seen to be achievable with noninteractive communication between the terminals. The achievability results are also shown to be universal.
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.
This dissertation deals with a multiterminal source model for secret key generation by multiple network terminals with prior and privileged access to a set of correlated signals complemented by public discussion among themselves. Emphasis is placed on a characterization of secret key capacity, i.e., the largest rate of an achievable secret key, and on algorithms for key construction. Various information theoretic security requirements of increasing stringency: weak, strong and perfect secrecy, as well as different types of sources: finite-valued and continuous, are studied. Specifically, three different models are investigated. First, we consider strong secrecy generation for a discrete multiterminal source model. We discover a connection between secret key capacity and a new source coding concept of "minimum information rate for signal dissemination," that is of independent interest in multiterminal data compression. Our main contribution is to show for this discrete model that structured linear codes suffice to generate a strong secret key of the best rate. Second, strong secrecy generation is considered for models with continuous observations, in particular jointly Gaussian signals. In the absence of suitable analogs of source coding notions for the previous discrete model, new techniques are required for a characterization of secret key capacity as well as for the design of algorithms for secret key generation. Our proof of the secret key capacity result, in particular the converse proof, as well as our capacity-achieving algorithms for secret key construction based on structured codes and quantization for a model with two terminals, constitute the two main contributions for this second model. Last, we turn our attention to perfect secrecy generation for fixed signal observation lengths as well as for their asymptotic limits. In contrast with the analysis of the previous two models that relies on probabilistic techniques, perfect secret key generation bears the essence of "zero-error information theory," and accordingly, we rely on mathematical techniques of a combinatorial nature. The model under consideration is the "Pairwise Independent Network" (PIN) model in which every pair of terminals share a random binary string, with the strings shared by distinct pairs of terminals being mutually independent. This model, which is motivated by practical aspects of a wireless communication network in which terminals communicate on the same frequency, results in three main contributions. First, the concept of perfect omniscience in data compression leads to a single-letter formula for the perfect secret key capacity of the PIN model; moreover, this capacity is shown to be achieved by linear noninteractive public communication, and coincides with strong secret key capacity. Second, taking advantage of a multigraph representation of the PIN model, we put forth an efficient algorithm for perfect secret key generation based on a combinatorial concept of maximal packing of Steiner trees of the multigraph. When all the terminals seek to share perfect secrecy, the algorithm is shown to achieve capacity. When only a subset of terminals wish to share perfect secrecy, the algorithm is shown to achieve at least half of it. Additionally, we obtain nonasymptotic and asymptotic bounds on the size and rate of the best perfect secret key generated by the algorithm. These bounds are of independent interest from a purely graph theoretic viewpoint as they constitute new estimates for the maximum size and rate of Steiner tree packing of a given multigraph. Third, a particular configuration of the PIN model arises when a lone "helper" terminal aids all the other "user" terminals generate perfect secrecy. This model has special features that enable us to obtain necessary and sufficient conditions for Steiner tree packing to achieve perfect secret key capacity.