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

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

Somnath Panja, Shaoquan Jiang, Reihaneh Safavi–Naini

Published Jun 25, 2023• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit54713.2023.10206802

Related papers

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

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-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•2 citations

Secure Key Agreement over Partially Corrupted Channels

Reihaneh Safavi–Naini, Peng‐Wei Wang

Key agreement (KA) is a fundamental cryptographic primitive. Assuming that Alice and Bob do not have any prior shared correlation, it has been proved that key agreement with security against a computationally unbounded adversary is impossible if communication is either over a fully public channel, or the channel is fully controlled by the adversary. In this paper we consider a setting where communication is over a partially corrupted channel, and there is no prior shared correlation. We formalize security and reliability of key agreement protocols in this setting, derive bounds on the rate of secret key agreement, and give constructions that achieve the respective bounds. Our results show that secret key agreement, and hence secret message transmission, is possible, as long as a small fraction of the transmitted symbols in each round remain untouched by the adversary. Our results can be extended to key agreement between nodes in a network, when the two nodes are connected by a set of disjoint paths, and in each round a subset of paths is eavesdropped and another subset (possibly with overlap) is tampered with. We relate our results to previous works, and discuss future directions.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•0 citations

Non-malleable extractors and symmetric key cryptography from weak secrets

Yevgeniy Dodis, Daniel Wichs

We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•149 citations

Information-theoretically Secure Key Agreement over Partially Corrupted Channels

Reihaneh Safavi–Naini, Peng‐Wei Wang

Key agreement is a fundamental cryptographic primitive. It has been proved that key agreement protocols with security against computationally unbounded adversaries cannot exist in a setting where Alice and Bob do not have dependent variables and communication between them is fully public, or fully controlled by the adversary. In this paper we consider this problem when the adversary can "partially" control the channel. We motivate these adversaries by considering adversarial corruptions at the physical layer of communication, give a definition of adversaries that can "partially" eavesdrop and "partially" corrupt the communication. We formalize security and reliability of key agreement protocols, derive bounds on the rate of key agreement, and give constructions that achieve the bound. Our results show that it is possible to have secret key agreement as long as some of the communicated symbols remain private and unchanged by the adversary. We relate our results to the previous known results, and discuss future work.

arXiv:1604.03824•Apr 13, 2016•1 citation
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.
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.
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.
Key agreement (KA) is a fundamental cryptographic primitive. Assuming that Alice and Bob do not have any prior shared correlation, it has been proved that key agreement with security against a computationally unbounded adversary is impossible if communication is either over a fully public channel, or the channel is fully controlled by the adversary. In this paper we consider a setting where communication is over a partially corrupted channel, and there is no prior shared correlation. We formalize security and reliability of key agreement protocols in this setting, derive bounds on the rate of secret key agreement, and give constructions that achieve the respective bounds. Our results show that secret key agreement, and hence secret message transmission, is possible, as long as a small fraction of the transmitted symbols in each round remain untouched by the adversary. Our results can be extended to key agreement between nodes in a network, when the two nodes are connected by a set of disjoint paths, and in each round a subset of paths is eavesdropped and another subset (possibly with overlap) is tampered with. We relate our results to previous works, and discuss future directions.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2<k<<n.
Key agreement is a fundamental cryptographic primitive. It has been proved that key agreement protocols with security against computationally unbounded adversaries cannot exist in a setting where Alice and Bob do not have dependent variables and communication between them is fully public, or fully controlled by the adversary. In this paper we consider this problem when the adversary can "partially" control the channel. We motivate these adversaries by considering adversarial corruptions at the physical layer of communication, give a definition of adversaries that can "partially" eavesdrop and "partially" corrupt the communication. We formalize security and reliability of key agreement protocols, derive bounds on the rate of key agreement, and give constructions that achieve the bound. Our results show that it is possible to have secret key agreement as long as some of the communicated symbols remain private and unchanged by the adversary. We relate our results to the previous known results, and discuss future work.