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)

Second-Order Asymptotics for One-way Secret Key Agreement

Alireza Poostindouz, Reihaneh Safavi–Naini

Published Jul 12, 2021• 2 citations
Publisher

Abstract

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.

DOI
10.1109/isit45174.2021.9518202

Related papers

A Capacity-achieving One-message Key Agreement With 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-message secret key agreement where the key is established by Alice sending a single message to Bob. We propose a one-message SKA (OM-SKA) protocol, prove that it achieves the one-way secret key capacity, and derive finite blocklength approximations of the achievable secret key length. We compare our results with existing OM-SKAs and show the protocol has a unique combination of desirable properties.

arXiv:1905.04280•May 10, 2019•1 citation

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

A One-way Secret Key Agreement with Security Against Active Adversaries

Somnath Panja, Shaoquan Jiang, Reihaneh Safavi–Naini

In a one-way secret key agreement (OW-SKA) protocol in source model, Alice and Bob have private samples of two correlated variables X and Y that are partially leaked to Eve through the variable Z, and use a single message from Alice to Bob to obtain a shared secret key. We propose an efficient secure OW-SKA when the sent message over the public channel can be tampered with by an active adversary. Our construction uses a specially designed hash function that is used for reconciliation, as well as detection of tampering. In detection of tampering the function is a Message Authentication Code (MAC) that maintains its security when the key is partially leaked. We prove the secrecy of the established key and robustness of the protocol, and discuss our results.

arXiv:2302.13176•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•3 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

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 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 work 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.

arXiv:1411.0735•Nov 3, 2014•10 citations
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-message secret key agreement where the key is established by Alice sending a single message to Bob. We propose a one-message SKA (OM-SKA) protocol, prove that it achieves the one-way secret key capacity, and derive finite blocklength approximations of the achievable secret key length. We compare our results with existing OM-SKAs and show the protocol has a unique combination of desirable properties.
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.
In a one-way secret key agreement (OW-SKA) protocol in source model, Alice and Bob have private samples of two correlated variables X and Y that are partially leaked to Eve through the variable Z, and use a single message from Alice to Bob to obtain a shared secret key. We propose an efficient secure OW-SKA when the sent message over the public channel can be tampered with by an active adversary. Our construction uses a specially designed hash function that is used for reconciliation, as well as detection of tampering. In detection of tampering the function is a Message Authentication Code (MAC) that maintains its security when the key is partially leaked. We prove the secrecy of the established key and robustness of the protocol, and discuss our results.
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.
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 work 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.