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

The role of game theory in key agreement over a public channel

Nebojsa Milosavljevic, Michael Gastpar, Kannan Ramchandran

Published Jun 1, 2010• 0 citations
Publisher

Abstract

In this work we study the problem of key agreement over a public noiseless channel when Alice, Bob and Charlie observe discrete memoryless sources of an unknown distribution. Alice and Bob want to agree on a key KABthat is protected from Charlie. At the same time, Alice and Charlie want to agree on a key KACthat is protected from Bob. In order to construct codebooks for the key agreement, Alice has to know how the sources are distributed. Therefore, she requests Bob and Charlie to send her sufficient information about their observations. We also assume that Bob and Charlie, besides agreeing with Alice on the keys, want to learn as much as possible about the other user's key: we call this quantity the leakage. We model these reports by having Bob and Charlie select discrete memoryless channels and passing their true observations through them. We approach this problem from a game-theoretic point of view. For a class of Bob and Charlie's objective functions which are linear in the key rate and the leakage rate, we characterize a Nash equilibrium. Also, we propose a strategy that Alice can apply in order to ensure that Bob and Charlie's honest reporting is a Nash equilibrium.

DOI
10.1109/isit.2010.5513707

Related papers

Key agreement over an interference channel with noiseless feedback: Achievable region & distributed allocation

Somayeh Salimi, Eduard Axel Jorswieck, Mikael Skoglund +1 more

Secret key establishment leveraging the physical layer as a source of common randomness has been investigated in a range of settings. We investigate the problem of establishing, in an information-theoretic sense, a secret key between a user and a base-station (BS) (more generally, part of a wireless infrastructure), but for two such user-BS pairs attempting the key establishment simultaneously. The challenge in this novel setting lies in that a user can eavesdrop another BS-user communications. It is thus paramount to ensure the two keys are established with no leakage to the other user, in spite the interference across neighboring cells. We model the system with BS-user communication through an interference channel and user-BS communication through a public channel. We find the region including achievable secret key rates for the general case that the interference channel (IC) is discrete and memoryless. Our results are examined for a Gaussian IC. In this setup, we investigate the performance of different transmission schemes for power allocation. The chosen transmission scheme by each BS essentially affects the secret key rate of the other BS-user. Assuming base stations are trustworthy but that they seek to maximize the corresponding secret key rate, a game-theoretic setting arises to analyze the interaction between the base stations. We model our key agreement scenario in normal form for different power allocation schemes to understand performance without cooperation. Numerical simulations illustrate the inefficiency of the Nash equilibrium outcome and motivate further research on cooperative or coordinated schemes.

arXiv:1512.08679•IEEE Conference on Communications and Network Security•Sep 1, 2015•4 citations

One-Shot Variable-Length Secret Key Agreement Approaching Mutual Information

Cheuk Ting Li, Venkat Anantharam

This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process.

arXiv:1809.01793•IEEE Transactions on Information Theory•Jun 9, 2021•7 citations

One-Shot Variable-Length Secret Key Agreement Approaching Mutual Information

Cheuk Ting Li, Venkat Anantharam

This paper studies an information-theoretic oneshot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X; Y ) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X; Y ) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X, Y ). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn, Y n) are observed sequentially and the key is output bit by bit with small delay, or in situations.

Allerton Conference on Communication, Control, and Computing•Oct 1, 2018•7 citations

Rate Secrecy of Networks with Game Theory Approach

Sadegh Bamohabbat Chafjiri, Mohammad Ali Tebbi, Yasser Karimian

In this paper, we introduce a three-way discrete memoryless Broadcast channel (T-DMBC) between a transmitter (Alice), a receiver (Bob), and an intruder (Eve). We represent a protocol for secret key establishment (SKE) between Alice and Bob so that Eve can also participate in the second round of the secret key establishment. We assume that the intruder cannot act as an initiator (under the conditions that the FCC acts as a dictator of the game). Thus, any transmission by an intruder as his activity in the first round must not make the protocol vulnerable to the DOS attack. We use the Nash Equilibrium (NE) of the game between the receiver and the intruder to prove that there is no guarantee for achievable secure rate stabilization toward the main receiver by using passive intruder protocols for DMC or 2DMBC. In order to achieve secure rate stabilization, we modify the passive model for the secrecy of 2DMBC with a noise-forwarding strategy and post-computations in a game model.

ASME Press eBooks•Jan 1, 2011•0 citations

Information-Theoretic Key Agreement of Multiple Terminals—Part I

Amin Gohari, Venkat Anantharam

We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models, multiple terminals wish to create a shared secret key that is secure from a passive eavesdropper. The terminals have access to a noiseless public communication channel and an additional resource that depends on the model. In the source model, the resource is an external source that repeatedly beams correlated randomness to the terminals; whereas in the channel model, the resource is a secure but noisy discrete memoryless broadcast channel. We derive new lower and upper bounds on the secret key capacity under both the source model and the channel model. The technique used for deriving our bound for the source model is to find certain properties of functions of joint probability distributions which, applied to the joint distribution of the source, will imply that they dominate the secret key capacity, and then prove the bound by a verification argument. A similar technique is used for the channel model. Finally, we also define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement. This generalizes an earlier result of Csiszár and Narayan.

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

Private data transfer over a broadcast channel

Manoj Mishra, Tanmay Sharma, Bikash Kumar Dey +1 more

We study the following private data transfer problem: Alice has a database of files. Bob and Cathy want to access a file each from this database (which may or may not be the same file), but each of them wants to ensure that their choices of file do not get revealed even if Alice colludes with the other user. Alice, on the other hand, wants to make sure that each of Bob and Cathy does not learn any more information from the database than the files they demand (the identities of which will be unknown to her). Moreover, they should not learn any information about the other files even if they collude. It turns out that it is impossible to accomplish this if Alice, Bob, and Cathy have access only to private randomness and noiseless communication links. We consider this problem when a binary erasure broadcast channel with independent erasures is available from Alice to Bob and Cathy in addition to a noiseless public discussion channel. We study the file-length-per-broadcast-channel-use rate in the honest-but-curious model. We focus on the case when the database consists of two files, and obtain the optimal rate. We then extend to the case of larger databases, and give upper and lower bounds on the optimal rate.

arXiv:1504.01101•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•2 citations
In this work we study the problem of key agreement over a public noiseless channel when Alice, Bob and Charlie observe discrete memoryless sources of an unknown distribution. Alice and Bob want to agree on a key KABthat is protected from Charlie. At the same time, Alice and Charlie want to agree on a key KACthat is protected from Bob. In order to construct codebooks for the key agreement, Alice has to know how the sources are distributed. Therefore, she requests Bob and Charlie to send her sufficient information about their observations. We also assume that Bob and Charlie, besides agreeing with Alice on the keys, want to learn as much as possible about the other user's key: we call this quantity the leakage. We model these reports by having Bob and Charlie select discrete memoryless channels and passing their true observations through them. We approach this problem from a game-theoretic point of view. For a class of Bob and Charlie's objective functions which are linear in the key rate and the leakage rate, we characterize a Nash equilibrium. Also, we propose a strategy that Alice can apply in order to ensure that Bob and Charlie's honest reporting is a Nash equilibrium.
Secret key establishment leveraging the physical layer as a source of common randomness has been investigated in a range of settings. We investigate the problem of establishing, in an information-theoretic sense, a secret key between a user and a base-station (BS) (more generally, part of a wireless infrastructure), but for two such user-BS pairs attempting the key establishment simultaneously. The challenge in this novel setting lies in that a user can eavesdrop another BS-user communications. It is thus paramount to ensure the two keys are established with no leakage to the other user, in spite the interference across neighboring cells. We model the system with BS-user communication through an interference channel and user-BS communication through a public channel. We find the region including achievable secret key rates for the general case that the interference channel (IC) is discrete and memoryless. Our results are examined for a Gaussian IC. In this setup, we investigate the performance of different transmission schemes for power allocation. The chosen transmission scheme by each BS essentially affects the secret key rate of the other BS-user. Assuming base stations are trustworthy but that they seek to maximize the corresponding secret key rate, a game-theoretic setting arises to analyze the interaction between the base stations. We model our key agreement scenario in normal form for different power allocation schemes to understand performance without cooperation. Numerical simulations illustrate the inefficiency of the Nash equilibrium outcome and motivate further research on cooperative or coordinated schemes.
This paper studies an information-theoretic one-shot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X;Y) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X;Y) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X,Y). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn,Yn) are observed sequentially and the key is output bit by bit, or in situations where the random source is not an i.i.d. or ergodic process.
This paper studies an information-theoretic oneshot variable-length secret key agreement problem with public discussion. Let X and Y be jointly distributed random variables, each taking values in some measurable space. Alice and Bob observe X and Y respectively, can communicate interactively through a public noiseless channel, and want to agree on a key length and a key that is approximately uniformly distributed over all bit sequences with the agreed key length. The public discussion is observed by an eavesdropper, Eve. The key should be approximately independent of the public discussion, conditional on the key length. We show that the optimal expected key length is close to the mutual information I(X; Y ) within a logarithmic gap. Moreover, an upper bound and a lower bound on the optimal expected key length can be written down in terms of I(X; Y ) only. This means that the optimal one-shot performance is always within a small gap of the optimal asymptotic performance regardless of the distribution of the pair (X, Y ). This one-shot result may find applications in situations where the components of an i.i.d. pair source (Xn, Y n) are observed sequentially and the key is output bit by bit with small delay, or in situations.
In this paper, we introduce a three-way discrete memoryless Broadcast channel (T-DMBC) between a transmitter (Alice), a receiver (Bob), and an intruder (Eve). We represent a protocol for secret key establishment (SKE) between Alice and Bob so that Eve can also participate in the second round of the secret key establishment. We assume that the intruder cannot act as an initiator (under the conditions that the FCC acts as a dictator of the game). Thus, any transmission by an intruder as his activity in the first round must not make the protocol vulnerable to the DOS attack. We use the Nash Equilibrium (NE) of the game between the receiver and the intruder to prove that there is no guarantee for achievable secure rate stabilization toward the main receiver by using passive intruder protocols for DMC or 2DMBC. In order to achieve secure rate stabilization, we modify the passive model for the secrecy of 2DMBC with a noise-forwarding strategy and post-computations in a game model.
We study the problem of information-theoretically secure secret key agreement under the well-known source model and channel model. In both of these models, multiple terminals wish to create a shared secret key that is secure from a passive eavesdropper. The terminals have access to a noiseless public communication channel and an additional resource that depends on the model. In the source model, the resource is an external source that repeatedly beams correlated randomness to the terminals; whereas in the channel model, the resource is a secure but noisy discrete memoryless broadcast channel. We derive new lower and upper bounds on the secret key capacity under both the source model and the channel model. The technique used for deriving our bound for the source model is to find certain properties of functions of joint probability distributions which, applied to the joint distribution of the source, will imply that they dominate the secret key capacity, and then prove the bound by a verification argument. A similar technique is used for the channel model. Finally, we also define a problem of communication for omniscience by a neutral observer and establish the equivalence between this new problem and the problem of secret key agreement. This generalizes an earlier result of Csiszár and Narayan.
We study the following private data transfer problem: Alice has a database of files. Bob and Cathy want to access a file each from this database (which may or may not be the same file), but each of them wants to ensure that their choices of file do not get revealed even if Alice colludes with the other user. Alice, on the other hand, wants to make sure that each of Bob and Cathy does not learn any more information from the database than the files they demand (the identities of which will be unknown to her). Moreover, they should not learn any information about the other files even if they collude. It turns out that it is impossible to accomplish this if Alice, Bob, and Cathy have access only to private randomness and noiseless communication links. We consider this problem when a binary erasure broadcast channel with independent erasures is available from Alice to Bob and Cathy in addition to a noiseless public discussion channel. We study the file-length-per-broadcast-channel-use rate in the honest-but-curious model. We focus on the case when the database consists of two files, and obtain the optimal rate. We then extend to the case of larger databases, and give upper and lower bounds on the optimal rate.