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.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 ApplicationsOct 24, 20206 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.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, 20212 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.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.13176IEEE International Symposium on Information Theory (ISIT)Jun 25, 20233 citations

The Bare Bounded-Storage Model: The Tight Bound on the Storage Requirement for Key Agreement

Stefan Dziembowski, Ueli M. Maurer

In the bounded-storage model (BSM) for information-theoretic secure encryption and key agreement, one makes use of a random string whose length is greater than the assumed bound on the adversary Eve's storage capacity. The legitimate parties, Alice and Bob, execute a protocol, over an authenticated channel accessible to Eve, to generate a secret key about which Eve has essentially no information even if she has infinite computing power. The string is either assumed to be accessible to all parties or communicated publicly from Alice to Bob. While in the BSM one often assumes that Alice and Bob initially share a short secret key, and the goal of the protocol is to generate a much longer key, in this communication, we consider the bare BSM without any initially shared secret key. It is proved that in the bare BSM, secret key agreement is impossible unless Alice and Bob have themselves very high storage capacity, namely, . This proves the optimality of a scheme proposed by Cachin and Maurer.In the bounded-storage model (BSM) for information-theoretic secure encryption and key agreement, one makes use of a random string whose length is greater than the assumed bound on the adversary Eve's storage capacity. The legitimate parties, Alice and Bob, execute a protocol, over an authenticated channel accessible to Eve, to generate a secret key about which Eve has essentially no information even if she has infinite computing power. The string is either assumed to be accessible to all parties or communicated publicly from Alice to Bob. While in the BSM one often assumes that Alice and Bob initially share a short secret key, and the goal of the protocol is to generate a much longer key, in this communication, we consider the bare BSM without any initially shared secret key. It is proved that in the bare BSM, secret key agreement is impossible unless Alice and Bob have themselves very high storage capacity, namely, . This proves the optimality of a scheme proposed by Cachin and Maurer.

IEEE Transactions on Information TheoryMay 29, 200813 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.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, 20180 citations

Information-theoretic Key Encapsulation and its Application to Secure Communication

Setareh Sharifian, Reihaneh Safavi–Naini

A hybrid encryption scheme consists of a public-key part called the key encapsulation mechanism (KEM), that is used to generate and establish a shared secret key between two parties, and a (symmetric) secret-key part called the data encapsulation mechanism (DEM) that encrypts the data using the shared key. Hybrid encryption schemes are widely used for securing Internet communication. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper), and define information-theoretic KEM (iKEM) that together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define security of each building block, and prove a composition theorem that guarantees (computational) q-chosen-plaintext attack (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy q-chosen-encapsulation attack security and one-time security, respectively. We show that an iKEM can be realized by an information-theoretic one-way secret key agreement (OW-SKA) protocol where a single message is transmitted from Alice to Bob, with a new security definition that allows $q$ queries to Alice. Using a OW-SKA that satisfies this new definition of security, effectively allows the established secret key to be used with a onetime symmetric key encryption system that can be implemented, for example, by XORing the output of a (computationally) secure pseudorandom generator with the message, to provide secure encryption of $q$ arbitrary messages (polynomially bounded length). We discuss our results and directions for future work.A hybrid encryption scheme consists of a public-key part called the key encapsulation mechanism (KEM), that is used to generate and establish a shared secret key between two parties, and a (symmetric) secret-key part called the data encapsulation mechanism (DEM) that encrypts the data using the shared key. Hybrid encryption schemes are widely used for securing Internet communication. In this paper, we initiate the study of hybrid encryption in preprocessing model which assumes access to initial correlated variables by all parties (including the eavesdropper), and define information-theoretic KEM (iKEM) that together with a (computationally) secure DEM, results in a hybrid encryption scheme in preprocessing model. We define security of each building block, and prove a composition theorem that guarantees (computational) q-chosen-plaintext attack (CPA) security of the hybrid encryption system if the iKEM and the DEM satisfy q-chosen-encapsulation attack security and one-time security, respectively. We show that an iKEM can be realized by an information-theoretic one-way secret key agreement (OW-SKA) protocol where a single message is transmitted from Alice to Bob, with a new security definition that allows$q$queries to Alice. Using a OW-SKA that satisfies this new definition of security, effectively allows the established secret key to be used with a onetime symmetric key encryption system that can be implemented, for example, by XORing the output of a (computationally) secure pseudorandom generator with the message, to provide secure encryption of$q$arbitrary messages (polynomially bounded length). We discuss our results and directions for future work.

IEEE International Symposium on Information Theory (ISIT)Jul 12, 20216 citations

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.

q

queries to Alice. Using a OW-SKA that satisfies this new definition of security, effectively allows the established secret key to be used with a onetime symmetric key encryption system that can be implemented, for example, by XORing the output of a (computationally) secure pseudorandom generator with the message, to provide secure encryption of

q

arbitrary messages (polynomially bounded length). We discuss our results and directions for future work.