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 Transactions on Information Theory

Key Generation Algorithms for Pairwise Independent Networks Based on Graphical Models

Lifeng Lai, Siu‐Wai Ho

Published Jul 21, 2015• 11 citations
Publisher

Abstract

We consider two secret key generation problems under a pairwise independent network model, and propose low complexity key generation schemes in a framework that connects our problems to network flow problems in graphs. Our schemes have two components: 1) local key generation and 2) global key propagation. In the local key generation, we use point-to-point source coding with side information to establish pairwise keys, from which we construct a graph with the capacity of each edge being the key rate of the corresponding point-to-point local key. In the global key propagation, depending on the particular problem, secret keys are delivered to users in the network using various network flow algorithms. In particular, in the first problem in which one is required to generate a group key for a group of users in the network, we propose a network coding-based global key propagation approach. This approach has a low complexity and has a better performance than the existing approach. In the second problem, in which one is required to generate multiple keys simultaneously for different pairs of users, we propose a multicommodity flow-based global key propagation approach. We show that the proposed approach is optimal for the case of generating two keys. For the general case of generating more than two keys, we show that the sum rate of the proposed scheme is larger than an upper bound characterized in this paper divided by a constant.

DOI
10.1109/tit.2015.2450729

Related papers

Secret Key Generation for a Pairwise Independent Network Model

Sirin Nitinawarat, Chunxuan Ye, Alexander Barg +2 more

We consider secret key generation for a “pairwise independent network” model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight.

arXiv:1007.3518•IEEE Transactions on Information Theory•Nov 30, 2010•82 citations

Secret key generation for pairwise independent networks with curious helpers

Pin-Hsun Lin, Carsten Rudolf Janda, Eduard Axel Jorswieck +1 more

We consider the problem of group secret key generation through a multi-hop network modeled by a pair-wise independent network and propose a low complexity scheme which can guarantee strong secrecy. We assume that the legitimate transmitter only has the knowledge of the maximum number of precoded keys known to any helpers, where the precoded keys are the output of a precoder at the transmitter to be propagated through the network. We also assume that nodes in the multi-hop network are curious, i.e., they not only help to relay but may eavesdrop. Confidentiality is required against an eavesdropper outside of the multi-hop network and also against the helpers in the multi-hop network, while both the curious helpers and the external eavesdropper can access a finite rate public channel between the legitimate transmitter-receiver pair. The objective is to generate secret keys shared by a given pair of nodes outside of the multi-hop network at the largest possible rate, with the cooperation of the nodes within the multi-hop network. We propose a low complexity linear transformation-based global key propagation approach to combat curious helpers by the number theoretic transform, under two scenarios: with an additional public or private channel between the pair of nodes aiming to share keys. We analyze the achievable secret key rate and investigate the performances under different network setting by numerical examples.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Jul 1, 2017•0 citations

Group Secret Key Generation in Wireless Networks: Algorithms and Rate Optimization

Peng Xu, Kanapathippillai Cumanan, Zhiguo Ding +2 more

This paper investigates group secret key generation problems for different types of wireless networks, by exploiting physical layer characteristics of wireless channels. A new group key generation strategy with low complexity is proposed, which combines the well-established point-to-point pairwise key generation technique, the multisegment scheme, and the one-time pad. In particular, this group key generation process is studied for three types of communication networks: 1) the three-node network; 2) the multinode ring network; and 3) the multinode mesh network. Three group key generation algorithms are developed for these communication networks, respectively. The analysis shows that the first two algorithms yield optimal group key rates, whereas the third algorithm achieves the optimal multiplexing gain. Next, for the first two types of networks, we address the time allocation problem in the channel estimation step to maximize the group key rates. This non-convex max-min time allocation problem is first reformulated into a series of geometric programming, and then, a single-condensation-method-based iterative algorithm is proposed. Numerical results are also provided to validate the performance of the proposed key generation algorithms and the time allocation algorithm.

IEEE Transactions on Information Forensics and Security•Apr 13, 2016•71 citations

Group Secret Key Generation Algorithms

Chunxuan Ye, Alex Reznik

We consider a pair-wise independent network in which every pair of terminals observes a common pair-wise source that is independent of all the sources accessible to the other pairs. We propose a method for secret key agreement in such a network that is based on well-established point-to- point techniques and repeated application of the one-time pad over a graphical representation of the network. Three specific problems are investigated. (1) Each terminal's observations are correlated only with the observations of a central terminal. All these terminals wish to generate a common secret key. (2) Two designated terminals wish to generate a secret key with the help of other terminals. (3) All terminals wish to generate a common secret key. In each of these cases, we show that our two-step approach can yield an optimal protocol, in terms of the resulting secret key rates. Furthermore, such a protocol is provided for the first two problems, while an efficient protocol is given for the third problem.

arXiv:cs/0701124•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•67 citations

Secret key generation for a pairwise independent network model

Sirin Nitinawarat, Chunxuan Ye, Alexander Barg +2 more

We investigate secret key generation for a ldquopair-wise independent networkrdquo model in which every pair of terminals observes correlated sources which are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate interactively in multiple rounds over a public noiseless channel of unlimited capacity, with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible. All the terminals cooperate in generating the secret key, with secrecy being required from an eavesdropper which has access to the public interterminal communication. We provide a (single-letter) formula for the secrecy capacity for this model, and show a natural connection between the problem of secret key generation and the combinatorial problem of maximal packing of Steiner trees in an associated multigraph. In particular, we show that the maximum number of Steiner tree packings in the multigraph is always a lower bound for the secrecy capacity. The bound is tight for the case when all the terminals seek to share a secret key; the mentioned connection yields an explicit capacity-achieving algorithm. This algorithm, which can be executed in polynomial time, extracts a group-wide secret key of the optimum rate from the collection of optimum and mutually independent secret keys for pairs of terminals.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•20 citations

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
We consider two secret key generation problems under a pairwise independent network model, and propose low complexity key generation schemes in a framework that connects our problems to network flow problems in graphs. Our schemes have two components: 1) local key generation and 2) global key propagation. In the local key generation, we use point-to-point source coding with side information to establish pairwise keys, from which we construct a graph with the capacity of each edge being the key rate of the corresponding point-to-point local key. In the global key propagation, depending on the particular problem, secret keys are delivered to users in the network using various network flow algorithms. In particular, in the first problem in which one is required to generate a group key for a group of users in the network, we propose a network coding-based global key propagation approach. This approach has a low complexity and has a better performance than the existing approach. In the second problem, in which one is required to generate multiple keys simultaneously for different pairs of users, we propose a multicommodity flow-based global key propagation approach. We show that the proposed approach is optimal for the case of generating two keys. For the general case of generating more than two keys, we show that the sum rate of the proposed scheme is larger than an upper bound characterized in this paper divided by a constant.
We consider secret key generation for a “pairwise independent network” model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight.
We consider the problem of group secret key generation through a multi-hop network modeled by a pair-wise independent network and propose a low complexity scheme which can guarantee strong secrecy. We assume that the legitimate transmitter only has the knowledge of the maximum number of precoded keys known to any helpers, where the precoded keys are the output of a precoder at the transmitter to be propagated through the network. We also assume that nodes in the multi-hop network are curious, i.e., they not only help to relay but may eavesdrop. Confidentiality is required against an eavesdropper outside of the multi-hop network and also against the helpers in the multi-hop network, while both the curious helpers and the external eavesdropper can access a finite rate public channel between the legitimate transmitter-receiver pair. The objective is to generate secret keys shared by a given pair of nodes outside of the multi-hop network at the largest possible rate, with the cooperation of the nodes within the multi-hop network. We propose a low complexity linear transformation-based global key propagation approach to combat curious helpers by the number theoretic transform, under two scenarios: with an additional public or private channel between the pair of nodes aiming to share keys. We analyze the achievable secret key rate and investigate the performances under different network setting by numerical examples.
This paper investigates group secret key generation problems for different types of wireless networks, by exploiting physical layer characteristics of wireless channels. A new group key generation strategy with low complexity is proposed, which combines the well-established point-to-point pairwise key generation technique, the multisegment scheme, and the one-time pad. In particular, this group key generation process is studied for three types of communication networks: 1) the three-node network; 2) the multinode ring network; and 3) the multinode mesh network. Three group key generation algorithms are developed for these communication networks, respectively. The analysis shows that the first two algorithms yield optimal group key rates, whereas the third algorithm achieves the optimal multiplexing gain. Next, for the first two types of networks, we address the time allocation problem in the channel estimation step to maximize the group key rates. This non-convex max-min time allocation problem is first reformulated into a series of geometric programming, and then, a single-condensation-method-based iterative algorithm is proposed. Numerical results are also provided to validate the performance of the proposed key generation algorithms and the time allocation algorithm.
We consider a pair-wise independent network in which every pair of terminals observes a common pair-wise source that is independent of all the sources accessible to the other pairs. We propose a method for secret key agreement in such a network that is based on well-established point-to- point techniques and repeated application of the one-time pad over a graphical representation of the network. Three specific problems are investigated. (1) Each terminal's observations are correlated only with the observations of a central terminal. All these terminals wish to generate a common secret key. (2) Two designated terminals wish to generate a secret key with the help of other terminals. (3) All terminals wish to generate a common secret key. In each of these cases, we show that our two-step approach can yield an optimal protocol, in terms of the resulting secret key rates. Furthermore, such a protocol is provided for the first two problems, while an efficient protocol is given for the third problem.
We investigate secret key generation for a ldquopair-wise independent networkrdquo model in which every pair of terminals observes correlated sources which are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate interactively in multiple rounds over a public noiseless channel of unlimited capacity, with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible. All the terminals cooperate in generating the secret key, with secrecy being required from an eavesdropper which has access to the public interterminal communication. We provide a (single-letter) formula for the secrecy capacity for this model, and show a natural connection between the problem of secret key generation and the combinatorial problem of maximal packing of Steiner trees in an associated multigraph. In particular, we show that the maximum number of Steiner tree packings in the multigraph is always a lower bound for the secrecy capacity. The bound is tight for the case when all the terminals seek to share a secret key; the mentioned connection yields an explicit capacity-achieving algorithm. This algorithm, which can be executed in polynomial time, extracts a group-wide secret key of the optimum rate from the collection of optimum and mutually independent secret keys for pairs of terminals.
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.