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

arXiv:1411.0735 · IEEE Transactions on Information Theory

Secret Key Agreement: General Capacity and Second-Order Asymptotics

Masahito Hayashi, Himanshu Tyagi, Shun Watanabe

Published May 12, 2016• 59 citations
arXivHTMLPDF

Abstract

We revisit the problem of secret key agreement using interactive public communication for two parties and propose a new secret key agreement protocol. The protocol attains the secret key capacity for general observations and attains the second-order asymptotic term in the maximum length of a secret key for independent and identically distributed observations. In contrast to the previously suggested secret key agreement protocols, the proposed protocol uses interactive communication. In fact, the standard one-way communication protocol used prior to this paper fails to attain the asymptotic results above. Our converse proofs rely on a recently established upper bound for secret key lengths. Both our lower and upper bounds are derived in a single-shot setup and the asymptotic results are obtained as corollaries.

DOI
10.1109/tit.2016.2567440

Related papers

Secret key agreement: General capacity and second-order asymptotics

Masahito Hayashi, Himanshu Tyagi, Shun Watanabe

We revisit the problem of secret key agreement using interactive public communication for two parties. When the underlying observations are independent and identically distributed, we establish the second-order asymptotic term in the maximum length of a secret key. Furthermore, for general observations, we establish the secret key capacity. Underlying our proofs is a new secret key agreement scheme and a recently established upper bound on secret key lengths.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•14 citations

Second-Order Asymptotics for One-way Secret Key Agreement

Alireza Poostindouz, Reihaneh Safavi–Naini

Secret key agreement (SKA) is a basic cryptographic primitive that establishes a shared secret key between parties. In the two-party source model of SKA, Alice and Bob want to share a secret key. They each have private samples of two correlated variables that are partially leaked to Eve. In a one-way SKA protocol, Alice sends a single message to Bob over a public channel, allowing the two parties to calculate a shared secret key that will be essentially unknown to Eve. The length of the key is a function of the number of samples$n$. In this paper, we prove a tight second-order asymptotic approximation of the key length of one-way SKA protocols, and propose an approach to construct a computationally efficient one-way SKA protocol with near-optimum finite key length. We compare our results with related work, and discuss future research directions.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•2 citations

A Capacity-achieving One-way Key Agreement with Improved Finite Blocklength Analysis

Setareh Sharifian, Alireza Poostindouz, Reihaneh Safavi–Naini

Information-theoretic secret key agreement (SKA) protocols are a fundamental cryptographic primitive that are used to establish a shared secret key between two or more parties. In a two-party SKA in source model, Alice and Bob have samples of two correlated variables that are partially leaked to Eve, and their goal is to establish a shared secret key by communicating over a reliable public channel. Eve must have no information about the established key. In this paper, we study the problem of one-way secret key agreement where the key is established by Alice sending a public message to Bob. We propose a one-way SKA (OW-SKA) protocol, prove that it achieves the one-way secret key capacity, and use it to derive a finite blocklength bound on the achievable secret key length. We compare our results with existing OW-SKAs and show the protocol achieves a longer key, and has a combination of desirable properties.

International Symposium on Information Theory and its Applications•Oct 24, 2020•6 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•6 citations

Interactive Communication for Data Exchange

Himanshu Tyagi, Pramod Viswanath, Shun Watanabe

Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.

IEEE Transactions on Information Theory•Nov 2, 2017•6 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•9 citations
We revisit the problem of secret key agreement using interactive public communication for two parties and propose a new secret key agreement protocol. The protocol attains the secret key capacity for general observations and attains the second-order asymptotic term in the maximum length of a secret key for independent and identically distributed observations. In contrast to the previously suggested secret key agreement protocols, the proposed protocol uses interactive communication. In fact, the standard one-way communication protocol used prior to this paper fails to attain the asymptotic results above. Our converse proofs rely on a recently established upper bound for secret key lengths. Both our lower and upper bounds are derived in a single-shot setup and the asymptotic results are obtained as corollaries.
Secret key agreement (SKA) is a basic cryptographic primitive that establishes a shared secret key between parties. In the two-party source model of SKA, Alice and Bob want to share a secret key. They each have private samples of two correlated variables that are partially leaked to Eve. In a one-way SKA protocol, Alice sends a single message to Bob over a public channel, allowing the two parties to calculate a shared secret key that will be essentially unknown to Eve. The length of the key is a function of the number of samplesnnn. In this paper, we prove a tight second-order asymptotic approximation of the key length of one-way SKA protocols, and propose an approach to construct a computationally efficient one-way SKA protocol with near-optimum finite key length. We compare our results with related work, and discuss future research directions.
Information-theoretic secret key agreement (SKA) protocols are a fundamental cryptographic primitive that are used to establish a shared secret key between two or more parties. In a two-party SKA in source model, Alice and Bob have samples of two correlated variables that are partially leaked to Eve, and their goal is to establish a shared secret key by communicating over a reliable public channel. Eve must have no information about the established key. In this paper, we study the problem of one-way secret key agreement where the key is established by Alice sending a public message to Bob. We propose a one-way SKA (OW-SKA) protocol, prove that it achieves the one-way secret key capacity, and use it to derive a finite blocklength bound on the achievable secret key length. We compare our results with existing OW-SKAs and show the protocol achieves a longer key, and has a combination of desirable properties.
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.
Two parties observing correlated data seek to exchange their data using interactive communication. How many bits must they communicate? We propose a new interactive protocol for data exchange, which increases the communication size in steps until the task is done. We also derive a lower bound on the minimum number of bits that is based on relating the data exchange problem to the secret key agreement problem. Our single-shot analysis applies to all discrete random variables and yields upper and lower bounds of a similar form. In fact, the bounds are asymptotically tight and lead to a characterization of the optimal rate of communication needed for data exchange for a general source sequence, such as a mixture of independent and identically distributed (IID) random variables as well as the optimal second-order asymptotic term in the length of communication needed for data exchange for IID random variables, when the probability of error is fixed. This gives a precise characterization of the asymptotic reduction in the length of optimal communication due to interaction; in particular, two-sided Slepian-Wolf compression is strictly suboptimal.
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.