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 Information Theory Workshop (ITW)

Secret Key Capacity of Wiretapped Polytree-PIN

Alireza Poostindouz, Reihaneh Safavi–Naini

Published Oct 17, 2021• 0 citations
Publisher

Abstract

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.

DOI
10.1109/itw48936.2021.9611419

Related papers

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

Information-Theoretic Key Agreement of Multiple Terminals—Part II: Channel Model

Amin Gohari, Venkat Anantharam

This is the second part of a two-part paper on information-theoretically secure secret key agreement. This part covers the secret key capacity under the channel model. In this model, multiple terminals wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. The terminals are all connected to a noiseless and authenticated but insecure channel, called the “public channel.” Furthermore, the terminals have access to a secure but noisy discrete memoryless broadcast channel (DMBC). The first terminal can choose a sequence of inputs to the DMBC, which has outputs at the other terminals and at the eavesdropper. After each channel use, the terminals can engage in arbitrarily many rounds of interactive authenticated communication over the public channel. At the end, each legitimate terminal should be able to generate the secret key. In this paper, we derive new lower and upper bounds on the secrecy capacity. In each case, an example is provided to show that the new bound represents a strict improvement over the previously best known bound. This part of the paper is not standalone, and is written under the assumption that the reader has access to Part I, which is published in the same issue.

IEEE Transactions on Information Theory•Jul 21, 2010•74 citations

A new multiple access wiretap channel model

Mohamed Nafea, Aylin Yener

A new model for the two-user multiple-access wiretap channel is considered. In this model, the legitimate (main) channel is a discrete memoryless channel (DMC), and the wiretapper chooses a fixed-length subset of the channel uses where she has perfect access to the transmitted symbols of the both users, while observing the remainder of the transmitted codewords through a second DMC. As such, it generalizes the existing multiple-access wiretap channel models and extends the recently proposed new wiretap channel model to a multiple access setting. An achievable strong secrecy rate region for the model is derived. The achievability is established by solving a dual multi-terminal secret key agreement problem in the source model, where two independent sources are communicating confidential keys to a common decoder over a public channel in the presence of a compound wiretapping source. The secrecy of the two keys in the dual source model is established by deriving a lemma which provides a doubly exponential convergence rate for the probability of the keys being uniform and independent from the public discussion and the wiretapping source observation.

IEEE Information Theory Workshop (ITW)•Sep 1, 2016•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

A New Wiretap Channel Model and its Strong Secrecy Capacity

Mohamed Nafea, Aylin Yener

In this paper, a new wiretap channel model is proposed, where the legitimate transmitter and receiver communicate over a discrete memoryless channel. The wiretapper has perfect access to a fixed-length subset of the transmitted codeword symbols of her choosing. Additionally, she observes the remainder of the transmitted symbols through a discrete memoryless channel. This new model subsumes the classical wiretap channel and wiretap channel II with noisy main channel as its special cases. The strong secrecy capacity of the proposed channel model is identified. Achievability is established by solving a dual secret key agreement problem in the source model, and converting the solution to the original channel model using probability distribution approximation arguments. In the dual problem, a source encoder and decoder, who observe random sequences independent and identically distributed according to the input and output distributions of the legitimate channel in the original problem, communicate a confidential key over a public error-free channel using a single forward transmission, in the presence of a compound wiretapping source who has perfect access to the public discussion. The security of the key is guaranteed for the exponentially many possibilities of the subset chosen at wiretapper by deriving a lemma which provides a doubly-exponential convergence rate for the probability that, for a fixed choice of the subset, the key is uniform and independent from the public discussion and the wiretapping source's observation. The converse is derived by using Sanov's theorem to upper bound the secrecy capacity of the new wiretap channel model by the secrecy capacity when the tapped subset is randomly chosen by nature.

arXiv:1701.07007•Jan 24, 2017•0 citations

On Multiterminal Secrecy Capacities

Imre Csiszár, Prakash Narayan

Shannon-theoretic secret key generation by several parties is considered for source models in which the distinct components of a multiple source observed separately by multiple terminals, and for channel models in which a secure noisy channel with one input terminal and multiple output terminals, and, additionally in both cases, a public noiseless channel of unlimited capacity, are available for accomplishing this goal. The secret key is generated for a set A of terminals, with the remaining terminals (if any) cooperating in this task through their public communication. We show that for source models in which secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from A, secrecy capacity can be achieved with noninteractive communication, the key being generated by any chosen terminal in the secret key-seeking set A of terminals obliviously of the public communication. For models in which the eavesdropper also possesses side information that is not available to any of the terminals cooperating in secrecy generation, an upper bound for the secrecy capacity and a sufficient condition for its tightness are given. The latter partially fills a gap in the authors' previous work [6].

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•0 citations
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.
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.
This is the second part of a two-part paper on information-theoretically secure secret key agreement. This part covers the secret key capacity under the channel model. In this model, multiple terminals wish to create a shared secret key that is secure from an eavesdropper with unlimited computational resources. The terminals are all connected to a noiseless and authenticated but insecure channel, called the “public channel.” Furthermore, the terminals have access to a secure but noisy discrete memoryless broadcast channel (DMBC). The first terminal can choose a sequence of inputs to the DMBC, which has outputs at the other terminals and at the eavesdropper. After each channel use, the terminals can engage in arbitrarily many rounds of interactive authenticated communication over the public channel. At the end, each legitimate terminal should be able to generate the secret key. In this paper, we derive new lower and upper bounds on the secrecy capacity. In each case, an example is provided to show that the new bound represents a strict improvement over the previously best known bound. This part of the paper is not standalone, and is written under the assumption that the reader has access to Part I, which is published in the same issue.
A new model for the two-user multiple-access wiretap channel is considered. In this model, the legitimate (main) channel is a discrete memoryless channel (DMC), and the wiretapper chooses a fixed-length subset of the channel uses where she has perfect access to the transmitted symbols of the both users, while observing the remainder of the transmitted codewords through a second DMC. As such, it generalizes the existing multiple-access wiretap channel models and extends the recently proposed new wiretap channel model to a multiple access setting. An achievable strong secrecy rate region for the model is derived. The achievability is established by solving a dual multi-terminal secret key agreement problem in the source model, where two independent sources are communicating confidential keys to a common decoder over a public channel in the presence of a compound wiretapping source. The secrecy of the two keys in the dual source model is established by deriving a lemma which provides a doubly exponential convergence rate for the probability of the keys being uniform and independent from the public discussion and the wiretapping source observation.
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, a new wiretap channel model is proposed, where the legitimate transmitter and receiver communicate over a discrete memoryless channel. The wiretapper has perfect access to a fixed-length subset of the transmitted codeword symbols of her choosing. Additionally, she observes the remainder of the transmitted symbols through a discrete memoryless channel. This new model subsumes the classical wiretap channel and wiretap channel II with noisy main channel as its special cases. The strong secrecy capacity of the proposed channel model is identified. Achievability is established by solving a dual secret key agreement problem in the source model, and converting the solution to the original channel model using probability distribution approximation arguments. In the dual problem, a source encoder and decoder, who observe random sequences independent and identically distributed according to the input and output distributions of the legitimate channel in the original problem, communicate a confidential key over a public error-free channel using a single forward transmission, in the presence of a compound wiretapping source who has perfect access to the public discussion. The security of the key is guaranteed for the exponentially many possibilities of the subset chosen at wiretapper by deriving a lemma which provides a doubly-exponential convergence rate for the probability that, for a fixed choice of the subset, the key is uniform and independent from the public discussion and the wiretapping source's observation. The converse is derived by using Sanov's theorem to upper bound the secrecy capacity of the new wiretap channel model by the secrecy capacity when the tapped subset is randomly chosen by nature.
Shannon-theoretic secret key generation by several parties is considered for source models in which the distinct components of a multiple source observed separately by multiple terminals, and for channel models in which a secure noisy channel with one input terminal and multiple output terminals, and, additionally in both cases, a public noiseless channel of unlimited capacity, are available for accomplishing this goal. The secret key is generated for a set A of terminals, with the remaining terminals (if any) cooperating in this task through their public communication. We show that for source models in which secrecy is required from an eavesdropper that observes only the public communication and perhaps also a set of terminals disjoint from A, secrecy capacity can be achieved with noninteractive communication, the key being generated by any chosen terminal in the secret key-seeking set A of terminals obliviously of the public communication. For models in which the eavesdropper also possesses side information that is not available to any of the terminals cooperating in secrecy generation, an upper bound for the secrecy capacity and a sufficient condition for its tightness are given. The latter partially fills a gap in the authors' previous work [6].