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

Secret Keys from Channel Noise.

Hadi Ahmadi, Reihaneh Safavi–Naini

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

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

Related papers

Secret key establishment over a pair of independent broadcast channels

Hadi Ahmadi, Reihaneh Safavi–Naini

We consider the problem of secret key establishment (SKE) in the presence of a passive adversary, Eve, when Alice and Bob are connected by a pair of independent discrete memoryless broadcast channels in opposite directions. We refer to this setup as 2DMBC. We define the secret-key capacity in this setup and provide a lower bound on the capacity by proposing a two-round SKE protocol. We also prove an upper bound and show that the two bounds coincide in the case of degraded 2DMBCs.

arXiv:1001.3908•International Symposium on Information Theory and its Applications•Oct 1, 2010•13 citations

Common Randomness and Secret Key Capacities of Two-way Channels.

Hadi Ahmadi, Reihaneh Safavi–Naini

Abstract. Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.

•Jan 1, 2011•0 citations

On the secret-key rate of binary random variables

Martin J. Gander, Ueli M. Maurer

Consider a scenario in which two parties Alice and Bob as well as an opponent Eve receive the output of a binary symmetric source (e,g. installed in a satellite) over individual, not necessarily independent binary symmetric channels. Alice and Bob share no secret key initially and can only communicate over a public channel completely accessible to Eve. The authors derive a lower bound on the rate at which Alice and Bob can generate secret-key bits about which Eve has arbitrarily little information, This lower bound is strictly positive as long as Eve's binary symmetric channel is not perfect, even if Alice's and Bob's channels are by orders of magnitude less reliable than Eve's channel.>

IEEE International Symposium on Information Theory (ISIT)•Dec 17, 2002•29 citations

New results on Secret Key Establishment over a pair of broadcast channels

Hadi Ahmadi, Reihaneh Safavi–Naini

Secret Key Establishment (SKE) over a pair of independent Discrete Memoryless Broadcast Channels (DMBCs) was studied in where lower and upper bounds on the secret-key capacity were provided. In this paper, we study the above setup for two cases: (1) the DMBCs have “secrecy potential”, and (2) the DMBCs are stochastically degraded with independent channels. For (1), we propose a simple SKE protocol using the novel Interactive Channel Coding (ICC) method and prove that it achieves the lower bound. For (2), we give a simplified expression for the lower bound and prove that, when one of the legitimate parties sends only i.i.d. variables, the lower bound is tight and the capacity is achieved by a two-round protocol.

arXiv:1004.4334•International Symposium on Information Theory and its Applications•Oct 1, 2010•4 citations

Information Theoretic Security over Physical-Layer Channels

Hadi Ahmadi

Wyner [96] proved that unconditionally secure communication over noisy channels is possible if the wiretapping channel is noisier than the main channel. The work has developed the following belief: Physical-channel characteristics are great resources to build security functionalities in the information-theoretic framework. We follow this belief and investigate the three problems of secret key establishment, manipulation detection, and distance bounding verification over physical-layer channels. We investigate secret key establishment (SKE) between Alice and Bob when they are connected through a pair of noisy wiretap channels with leakage to Eve. Our results show the possibility of SKE even in cases where the main channels are noisier than Eve's channels. We then notice two implicit assumptions of this work: (i) local randomness is freely available, and (ii) the wiretap channels are independent. We remove Assumption (i) by considering no local randomness for the parties. The results appreciate the role of noise as a single resource for randomness derivation and key generation in this setting. Regarding the second assumption, we consider the general two-way wiretap channel, where simultaneous data transmission can help achieve higher key rates. We show under what condition our security requirements can be strengthened without sacrificing the SK capacity. We consider manipulation detection against physical-layer adversaries noticing their limitations. We define leakage-resilient algebraic manipulation detection (LR-AMD) codes and prove optimal LR-AMD code constructions in general and special leakage scenarios. We show two applications of these codes: (i) robust nonperfect secret sharing and (ii) manipulation detection over wiretap channels. We then discuss how these codes can be composed with other primitives to guarantee bitwise manipulation detection and SKE against active adversaries over binary wiretap channels. Distance bounding verification (DBV) allows a verifier to check an upper bound on a claimed distance from a prover. We study DBV over physical channels with security against distance fraud (DFA), ma a fraud (MFA) and terrorist fraud (TFA) attacks. We show efficient DFA- and MFA-secure protocols only using physical channel properties. We further prove that TFA-security becomes feasible if the parties' communication is limited by the bounded retrieval model (BRM).

•Jan 1, 2012•0 citations

A secret key establishment protocol for wireless networks using noisy channels

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.

Journal of Computer Security•Feb 24, 2017•3 citations
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
Abstract. Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.
Consider a scenario in which two parties Alice and Bob as well as an opponent Eve receive the output of a binary symmetric source (e,g. installed in a satellite) over individual, not necessarily independent binary symmetric channels. Alice and Bob share no secret key initially and can only communicate over a public channel completely accessible to Eve. The authors derive a lower bound on the rate at which Alice and Bob can generate secret-key bits about which Eve has arbitrarily little information, This lower bound is strictly positive as long as Eve's binary symmetric channel is not perfect, even if Alice's and Bob's channels are by orders of magnitude less reliable than Eve's channel.>
Secret Key Establishment (SKE) over a pair of independent Discrete Memoryless Broadcast Channels (DMBCs) was studied in where lower and upper bounds on the secret-key capacity were provided. In this paper, we study the above setup for two cases: (1) the DMBCs have “secrecy potential”, and (2) the DMBCs are stochastically degraded with independent channels. For (1), we propose a simple SKE protocol using the novel Interactive Channel Coding (ICC) method and prove that it achieves the lower bound. For (2), we give a simplified expression for the lower bound and prove that, when one of the legitimate parties sends only i.i.d. variables, the lower bound is tight and the capacity is achieved by a two-round protocol.
Wyner [96] proved that unconditionally secure communication over noisy channels is possible if the wiretapping channel is noisier than the main channel. The work has developed the following belief: Physical-channel characteristics are great resources to build security functionalities in the information-theoretic framework. We follow this belief and investigate the three problems of secret key establishment, manipulation detection, and distance bounding verification over physical-layer channels. We investigate secret key establishment (SKE) between Alice and Bob when they are connected through a pair of noisy wiretap channels with leakage to Eve. Our results show the possibility of SKE even in cases where the main channels are noisier than Eve's channels. We then notice two implicit assumptions of this work: (i) local randomness is freely available, and (ii) the wiretap channels are independent. We remove Assumption (i) by considering no local randomness for the parties. The results appreciate the role of noise as a single resource for randomness derivation and key generation in this setting. Regarding the second assumption, we consider the general two-way wiretap channel, where simultaneous data transmission can help achieve higher key rates. We show under what condition our security requirements can be strengthened without sacrificing the SK capacity. We consider manipulation detection against physical-layer adversaries noticing their limitations. We define leakage-resilient algebraic manipulation detection (LR-AMD) codes and prove optimal LR-AMD code constructions in general and special leakage scenarios. We show two applications of these codes: (i) robust nonperfect secret sharing and (ii) manipulation detection over wiretap channels. We then discuss how these codes can be composed with other primitives to guarantee bitwise manipulation detection and SKE against active adversaries over binary wiretap channels. Distance bounding verification (DBV) allows a verifier to check an upper bound on a claimed distance from a prover. We study DBV over physical channels with security against distance fraud (DFA), ma a fraud (MFA) and terrorist fraud (TFA) attacks. We show efficient DFA- and MFA-secure protocols only using physical channel properties. We further prove that TFA-security becomes feasible if the parties' communication is limited by the bounded retrieval model (BRM).
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.