Secret Key Establishment over Noisy Channels

Mirko Bottarelli, Gregory Epiphaniou, Dhouha Kbaier Ben Ismail +2 more

Hadi Ahmadi, Reihaneh Safavi–Naini

Abstract. We study the problem of unconditionally secure Secret Key Establishment (SKE) when Alice and Bob are connected by two noisy channels in opposite directions, and the channels are eavesdropped by Eve. We consider the case that Alice and Bob do not have any sources of initial randomness at their disposal. We start by discussing special cases of interest where SKE is impossible, and then provide a simple SKE construction over a binary symmetric channel that achieves some rates of secret key. We next focus on the Secret Key (SK) capacity, i.e., the highest rate of secure and reliable key establishment (in bits per channel use) that the parties can achieve. Relying on the existence of capacity-achieving coding schemes, we propose a multi-round SKE protocol, called the main protocol, that proves a lower bound on the SK capacity. The main protocol consists of an initialization round, followed by repeated use of a two-round SKE protocol, called the basic protocol. We also provide an upper bound on the SK capacity and show that the two bounds coincide when channels do not leak information to the adversary. We apply the results to the case that communicants are connected by binary symmetric channels. 1

Hadi Ahmadi, Reihaneh Safavi–Naini

Tatsuya Tomaru

Albert Guan, Wen-Guey Tzeng

An efficient protocol for establishing secret keys for neighboring nodes in a wireless network is presented in this paper. The security of the key generated by our protocol is based on the unpredictability of the noises in binary symmetric communication channels. The two nodes which try to establish a common secret key receive messages from a common source of random bit strings. Due to noises in the communication channel, the messages received by them, and most importantly the messages received by the eavesdropper, are not the same. We show that the two nodes can modify their messages in an efficient way to obtain a common string which contains enough uncertainty to the eavesdropper. Then, a secure universal hash function is applied to compute a secret key for extracting randomness from the common string. We prove that the probability for the eavesdropper to know the value of the key is negligible. One advantage of our proposed protocol is that the secret key rate is better than the known scheme in other models, such as the bounded storage model. Furthermore, our proposed protocol needs only to perform exclusive-or operations and compute hash values. Thus, it is a computationally light-weight protocol and suitable for devices with limited computing resources, such as sensors in sensor networks.

Hadi Ahmadi, Reihaneh Safavi–Naini