IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)

Secret key generation for pairwise independent networks with curious helpers

Pin-Hsun Lin, Carsten Rudolf Janda, Eduard Axel Jorswieck, Y.-W. Peter Hong

Published Jul 1, 2017• 0 citations

Abstract

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.

DOI: 10.1109/spawc.2017.8227737

Related papers

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, 200818 citations

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.

IEEE Transactions on Information TheoryNov 30, 201080 citations

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.3518Jul 20, 20101 citation

Perfect secrecy and combinatorial tree packing

Sirin Nitinawarat, Prakash Narayan

We consider perfect secret key generation for a “pairwise independent network” model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Our results yield new bounds for the maximum size and rate of Steiner tree packing, and are of independent interest from a graph theoretic viewpoint. Third, when a single “helper” terminal assists the remaining “user” terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a “weak” helper is shown to be sufficient for optimality.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20101 citation

Secret key generation from multiple cooperative helpers by rate unlimited public communication

Bin Yang, Wenjie Wang, Qinye Yin

This paper investigates the secret key generation from multiple cooperative sources. We assume that the public communication between the legitimate users has unlimited capacity. In this case, the secret key rate is the upper bound of a practical system with limited public communication. The random signals from the multiple helpers can help to create correlated Gaussian sources for the legitimate users to generate secret key, and only local channel state information (CSI) is needed by the helpers to cooperate with others. The power allocation between the helpers is studied with a total transmit power constraint, which results in a non-convex optimization problem. A high efficiency sub-optimal solution is proposed. And even when the legitimate users have no idea about the eavesdropper, the scheme still can help the system to achieve fairly good performance.

IEEE International Conference on Acoustics Speech and Signal ProcessingMay 1, 20145 citations

Perfect Omniscience, Perfect Secrecy, and Steiner Tree Packing

Sirin Nitinawarat, Prakash Narayan

We consider perfect secret key generation for a ¿pairwise independent network¿ model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Third, when a single ¿helper¿ terminal assists the remaining ¿user¿ terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a ¿weak¿ helper is shown to be sufficient for optimality.

arXiv:1008.1079Information Theory and Applications Workshop (ITA)Jan 1, 201067 citations