IEEE International Symposium on Information Theory (ISIT)

A game theoretic treatment for pair-wise secret-key generation in many-to-one networks

Rémi A. Chou, Aylin Yener

Published Jun 1, 2017• 3 citations

Abstract

We consider secret-key generation between several agents and a base station that observe independent and identically distributed (i.i.d.) realizations of correlated random variables. Each agent wishes to generate the longest possible individual key with the base station by means of public communication. All keys must be jointly kept secret from all external entities. We do not require them to be kept secret among the agents. In this many-to-one secret-key generation setting, it can be shown that the agents can take advantage of a collective protocol to increase the sum-rate of all the generated keys. However, when each agent is only interested in maximizing its own secret-key rate, agents may be unwilling to participate in a collective protocol. Furthermore, when such a collective protocol is employed, how to fairly allocate individual key rates arises as a valid issue. We study this tension between cooperation and self-interest with a game-theoretic treatment. We establish that cooperation is in the best interest of all agents and that there exists individual secret-key rate allocations that incentivize the agents to follow the protocol. Additionally, we propose an explicit and low-complexity coding scheme based on polar codes and hash functions that achieves such allocations.

DOI: 10.1109/isit.2017.8006784

Related papers

Secret-Key Generation in Many-to-One Networks: An Integrated Game-Theoretic and Information-Theoretic Approach

Rémi A. Chou, Aylin Yener

This paper considers secret-key generation between several agents and a base station that observe independent and identically distributed realizations of correlated random variables. Each agent wishes to generate the longest possible individual key with the base station by means of public communication. All keys must be jointly kept secret from all external entities. In this many-to-one secret-key generation setting, it can be shown that the agents can take advantage of a collective protocol to increase the sum rate of their generated keys. However, when each agent is only interested in maximizing its own secret-key rate, agents may be unwilling to participate in a collective protocol. Furthermore, when such a collective protocol is employed, how to fairly allocate individual key rates arises as a valid issue. This paper studies the tension between cooperation and self-interest with a game-theoretic treatment. This paper establishes that cooperation is in the best interest of all individualistic agents and that there exist individual secret-key rate allocations that incentivize the agents to follow the protocol. In addition, an explicit coding scheme that achieves such allocations is proposed.

arXiv:1710.04643IEEE Transactions on Information TheoryFeb 27, 201913 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

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

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/0701124IEEE International Symposium on Information Theory (ISIT)Jun 1, 200766 citations

Resource-Efficient Common Randomness and Secret-Key Schemes

Badih Ghazi, T. S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.

arXiv:1707.08086Society for Industrial and Applied Mathematics eBooksJan 1, 201814 citations