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 Conference on Computer Communications (INFOCOM)

Bipartite Graph Matching Based Secret Key Generation

Hongbo Liu, Yan Wang, Yanzhi Ren, Yingying Jennifer Chen

Published May 10, 2021• 26 citations
Publisher

Abstract

The physical layer secret key generation exploiting wireless channel reciprocity has attracted considerable attention in the past two decades. On-going research have demonstrated its viability in various radio frequency (RF) systems. Most of existing work rely on quantization technique to convert channel measurements into digital binaries that are suitable for secret key generation. However, non-simultaneous packet exchanges in time division duplex systems and noise effects in practice usually create random channel measurements between two users, leading to inconsistent quantization results and mismatched secret bits. While significant efforts were spent in recent research to mitigate such non-reciprocity, no efficient method has been found yet. Unlike existing quantization-based approaches, we take a different viewpoint and perform the secret key agreement by solving a bipartite graph matching problem. Specifically, an efficient dual-permutation secret key generation method, DP-SKG, is developed to match the randomly permuted channel measurements between a pair of users by minimizing their discrepancy holistically. DP-SKG allows two users to generate the same secret key based on the permutation order of channel measurements despite the non-reciprocity over wireless channels. Extensive experimental results show that DP-SKG could achieve error-free key agreement on received signal strength (RSS) with a low cost under various scenarios.

DOI
10.1109/infocom42981.2021.9488848

Related papers

Secret Key Generation Based on Manipulated Channel Measurement Matching

Yicong Du, Huan Dai, Hongbo Liu +5 more

The physical layer secret key generation exploiting wireless channel reciprocity has demonstrated its viability and effectiveness in various wireless scenarios, such as the Internet of Things (IoT) network, mobile communication network, and industrial control system. Most of the existing studies rely on the quantization technique to convert channel measurements into secret bits for confidential communications. However, non-simultaneous packet exchanges in time-division duplex systems and noise effects usually induce inconsistent quantization results and mismatched secret bits. Although recent research has spent significant effort mitigating such non-reciprocity, it is still far from practical error-free key generation. Unlike previous quantization-based approaches, we take a different viewpoint to match the randomly manipulated (i.e., permuted or edited) channel measurements between a pair of users by minimizing their discrepancy holistically. Specifically, two novel secret key generation algorithms based on bipartite graph matching (BMSKG) and edited sequence alignment (SA-SKG) are developed. BM-SKG allows two users to generate the same secret key based on the permutation order of channel measurements, while SASKG aims to align the edited channel measurements between a pair of users for secret key agreement. In both algorithms, one user can preset the secret key and embed encrypted messages in the exchanged data packets, which reduces communication overheads in key generation. Extensive experimental results show that both BM-SKG and SA-SKG algorithms achieve error-free key agreement on channel measurements at a low cost under various scenarios.

IEEE Transactions on Mobile Computing•Feb 12, 2024•6 citations

Efficient and Error-Free Secret Key Generation Leveraging Sorted Indices Matching

Yicong Du, Huan Dai, Hongbo Liu +3 more

Secret key generation exploiting inherent channel randomness stands as an important paradigm for physical-layer security in wireless networks. However, existing work relying on quantization has some difficulties in eliminating inconsistent key bits due to the impact of ambient noise. Recent studies propose to match the segmented channel samples (i.e., channel episodes) of similar variation patterns between legitimate peers to achieve error-free key generation, but they also suffer from high computational overhead and reduced accuracy for large key lengths. This work proposes a secret key generation method based on sorted indices matching (SIM-SKG), aiming at efficient and error-free key generation. Specifically, we sort the channel samples to ensure each channel episode with a unique variation pattern for accurate matching. To avoid the impact of half-duplex communication mode and ambient noise, we propose to match the indices instead of the channel samples as in existing studies. We also develop a noise perturbation scheme that further mitigates the ambiguity during indices matching. Extensive experimental studies demonstrate the high efficiency and accuracy of SIM-SKG under various scenarios for both RSS and CSI channel measurements. Specifically, SIM-SKG achieves error-free key generation with a length of 2048 bits within as little as 1.7$msec$. Moreover, theoretical analyses and experiments also confirm the security of the SIM-SKG method against various attacks.

IEEE Transactions on Mobile Computing•Sep 19, 2024•4 citations

On Quantization for Secret Key Generation From Wireless Channel Samples

Muhammad Adil, Shurjeel Wyne, Syed Junaid Nawaz

Physical layer security (PLS) techniques hold promise for augmenting secure communications in the 5thgeneration of mobile wireless networks. Secret key generation (SKG) is a PLS technique which exploits the wireless propagation channel's randomness to generate symmetric key bits for information encryption and decryption. This work proposes symmetric key generation based on non-uniform quantization of the received signal strength (RSS) samples of a Nakagami-$m$ fading channel. The proposed strategy for non-uniform quantization for SKG aims to set quantization thresholds for maximal key randomness and high values of key generation rate (KGR) and key agreement probability (KAP). Finally, a framework is proposed to use single node RSS measurements, readily available in the literature, to generate RSS samples at the other link end. This framework facilitates the testing of new SKG algorithms that require simultaneous RSS measurements by the legitimate nodes, which are not readily available in the open literature. The effectiveness of the proposed SKG scheme is validated through Monte Carlo methods and the National Institute of Standards and Technology (NIST) test suite for assessing the randomness of the generated key sequence.

IEEE Access•Jan 1, 2021•40 citations

Performance Improvement of Secret Key Generation Scheme in Wireless Indoor Environment

Mike Yuliana, Wirawan, Suwadi

The Secret Key Generation (SKG) scheme that exploits the reciprocity and uniqueness of wireless channel between two users plays a significant part in a new increasing distributed security system. The scheme performance can be distinguished based on the low value of Key disagreement Rate (KDR), the high value of Key Generation Rate (KGR), as well as the fulfillment of the NIST randomness standard. The previous SKG scheme has a high KDR due to a direct quantization of a measurement result of the Received Signal Strength (RSS). To overcome the above issue, we conduct a pre-processing of measurement result before quantization with the Kalman method. The pre-process is carried out to improve the channel reciprocity between two legitimate users with the objective to reduce the bit mismatch. Through an experiment, we propose a new quantization scheme called a Modified Multi-Bit (MMB) that uses a multi-bit system on every level of quantization. The test results show that the proposed combination of preprocessing and the MMB scheme has a better performance compared to the existing schemes in terms of KDR and KGR. The Secret Key generated by our scheme also fulfills the NIST randomness standard.

International Journal of Communication Networks and Information Security (IJCNIS)•Apr 17, 2022•20 citations

A Novel Secret Key Generation Algorithm for Secure Wireless Communications

Hafsa Jahangeer, Syed Junaid Nawaz, Shurjeel Wyne +1 more

The rapid technological advancements in wireless networks have resulted in tremendous increase in the number of connected user and machine-type wireless devices. Physical Layer Security (PLS) has a strong potential for providing security to wireless links in massively connected future wireless networks. The key-based PLS methods aim at generating secret key bits for data encryption/decryption at the legitimate communication nodes by exploiting the randomness inherent in wireless channels. This work proposes a novel secret key-bits extraction algorithm named Moving-Window Wrapped-Envelope Secret Key Generation (MWWE-SKG). The proposed algorithm uses first-order statistics from a sliding temporal window of channel samples to select the channel quantization interval for each window from circularly wrapped channel envelope samples. The differences in hardware noise conditions at the legitimate nodes lead to differences in the measurement of ideally reciprocal channels, which further leads to a mismatch in the generated secret key bits, whereas the channel statistics of the same links are more likely to remain unchanged for a reasonably large length of time window over the channel samples. An extensive analysis on the performance of the proposed algorithm is conducted, where the proposed algorithm is observed to provide a promising trade-off between the critical SKG performance metrics namely the Key Generation Rate (KGR), Bit Mismatch Probability (BMP), and the Key Randomness Property (KRP). Furthermore, a comparative performance analysis of the proposed algorithm with other notable techniques is also conducted to demonstrate the superior performance of the proposed algorithm.

•Mar 8, 2024•0 citations

On secret key generation from multiple observations of wireless channels

Kang Liu, Serguei L. Primak, Xianbin Wang

Secret key generation at physical layer has attracted more and more attentions as an emerging cryptography method. Compared to traditional security approaches, secret key generation at physical layer not only avoids the problem of key distribution, but also holds high efficiency and low complexity in application. Based on the principle of channel reciprocity, Alice and Bob both estimate the channel conditions and extract shared keys from this source of common randomness. In this paper, we first analyze the basic steps (channel estimation, sample quantization and key reconciliation) of secret key generation, key match rate with different quantization levels and key reconciliation times are also simulated. While in practical situations, different non-reciprocity factors affect the channel estimation step, key match rate can be greatly decreased and hardly meet real time cryptography requirements. In order to increase the key match rate, the unified framework of physical layer key generation has been extended to utilizing multiple observations of wireless channels to generate secret keys. An improved key generation approach with multiple observations can well deal with discrepancies between transceivers and keep increasing the key match rate. Theoretical analysis and simulation results both validate the significant improvement due to multiple observations. With an increased number of observations on both sides, the desired key match rate can be achieved much greater than with a single observation, and also the probability of key recovery by Eve can be decreased.

IEEE International Conference on Communication Systems (ICCS)•Nov 1, 2014•5 citations
The physical layer secret key generation exploiting wireless channel reciprocity has attracted considerable attention in the past two decades. On-going research have demonstrated its viability in various radio frequency (RF) systems. Most of existing work rely on quantization technique to convert channel measurements into digital binaries that are suitable for secret key generation. However, non-simultaneous packet exchanges in time division duplex systems and noise effects in practice usually create random channel measurements between two users, leading to inconsistent quantization results and mismatched secret bits. While significant efforts were spent in recent research to mitigate such non-reciprocity, no efficient method has been found yet. Unlike existing quantization-based approaches, we take a different viewpoint and perform the secret key agreement by solving a bipartite graph matching problem. Specifically, an efficient dual-permutation secret key generation method, DP-SKG, is developed to match the randomly permuted channel measurements between a pair of users by minimizing their discrepancy holistically. DP-SKG allows two users to generate the same secret key based on the permutation order of channel measurements despite the non-reciprocity over wireless channels. Extensive experimental results show that DP-SKG could achieve error-free key agreement on received signal strength (RSS) with a low cost under various scenarios.
The physical layer secret key generation exploiting wireless channel reciprocity has demonstrated its viability and effectiveness in various wireless scenarios, such as the Internet of Things (IoT) network, mobile communication network, and industrial control system. Most of the existing studies rely on the quantization technique to convert channel measurements into secret bits for confidential communications. However, non-simultaneous packet exchanges in time-division duplex systems and noise effects usually induce inconsistent quantization results and mismatched secret bits. Although recent research has spent significant effort mitigating such non-reciprocity, it is still far from practical error-free key generation. Unlike previous quantization-based approaches, we take a different viewpoint to match the randomly manipulated (i.e., permuted or edited) channel measurements between a pair of users by minimizing their discrepancy holistically. Specifically, two novel secret key generation algorithms based on bipartite graph matching (BMSKG) and edited sequence alignment (SA-SKG) are developed. BM-SKG allows two users to generate the same secret key based on the permutation order of channel measurements, while SASKG aims to align the edited channel measurements between a pair of users for secret key agreement. In both algorithms, one user can preset the secret key and embed encrypted messages in the exchanged data packets, which reduces communication overheads in key generation. Extensive experimental results show that both BM-SKG and SA-SKG algorithms achieve error-free key agreement on channel measurements at a low cost under various scenarios.
Secret key generation exploiting inherent channel randomness stands as an important paradigm for physical-layer security in wireless networks. However, existing work relying on quantization has some difficulties in eliminating inconsistent key bits due to the impact of ambient noise. Recent studies propose to match the segmented channel samples (i.e., channel episodes) of similar variation patterns between legitimate peers to achieve error-free key generation, but they also suffer from high computational overhead and reduced accuracy for large key lengths. This work proposes a secret key generation method based on sorted indices matching (SIM-SKG), aiming at efficient and error-free key generation. Specifically, we sort the channel samples to ensure each channel episode with a unique variation pattern for accurate matching. To avoid the impact of half-duplex communication mode and ambient noise, we propose to match the indices instead of the channel samples as in existing studies. We also develop a noise perturbation scheme that further mitigates the ambiguity during indices matching. Extensive experimental studies demonstrate the high efficiency and accuracy of SIM-SKG under various scenarios for both RSS and CSI channel measurements. Specifically, SIM-SKG achieves error-free key generation with a length of 2048 bits within as little as 1.7msecmsecmsec. Moreover, theoretical analyses and experiments also confirm the security of the SIM-SKG method against various attacks.
Physical layer security (PLS) techniques hold promise for augmenting secure communications in the 5thgeneration of mobile wireless networks. Secret key generation (SKG) is a PLS technique which exploits the wireless propagation channel's randomness to generate symmetric key bits for information encryption and decryption. This work proposes symmetric key generation based on non-uniform quantization of the received signal strength (RSS) samples of a Nakagami-mmm fading channel. The proposed strategy for non-uniform quantization for SKG aims to set quantization thresholds for maximal key randomness and high values of key generation rate (KGR) and key agreement probability (KAP). Finally, a framework is proposed to use single node RSS measurements, readily available in the literature, to generate RSS samples at the other link end. This framework facilitates the testing of new SKG algorithms that require simultaneous RSS measurements by the legitimate nodes, which are not readily available in the open literature. The effectiveness of the proposed SKG scheme is validated through Monte Carlo methods and the National Institute of Standards and Technology (NIST) test suite for assessing the randomness of the generated key sequence.
The Secret Key Generation (SKG) scheme that exploits the reciprocity and uniqueness of wireless channel between two users plays a significant part in a new increasing distributed security system. The scheme performance can be distinguished based on the low value of Key disagreement Rate (KDR), the high value of Key Generation Rate (KGR), as well as the fulfillment of the NIST randomness standard. The previous SKG scheme has a high KDR due to a direct quantization of a measurement result of the Received Signal Strength (RSS). To overcome the above issue, we conduct a pre-processing of measurement result before quantization with the Kalman method. The pre-process is carried out to improve the channel reciprocity between two legitimate users with the objective to reduce the bit mismatch. Through an experiment, we propose a new quantization scheme called a Modified Multi-Bit (MMB) that uses a multi-bit system on every level of quantization. The test results show that the proposed combination of preprocessing and the MMB scheme has a better performance compared to the existing schemes in terms of KDR and KGR. The Secret Key generated by our scheme also fulfills the NIST randomness standard.
The rapid technological advancements in wireless networks have resulted in tremendous increase in the number of connected user and machine-type wireless devices. Physical Layer Security (PLS) has a strong potential for providing security to wireless links in massively connected future wireless networks. The key-based PLS methods aim at generating secret key bits for data encryption/decryption at the legitimate communication nodes by exploiting the randomness inherent in wireless channels. This work proposes a novel secret key-bits extraction algorithm named Moving-Window Wrapped-Envelope Secret Key Generation (MWWE-SKG). The proposed algorithm uses first-order statistics from a sliding temporal window of channel samples to select the channel quantization interval for each window from circularly wrapped channel envelope samples. The differences in hardware noise conditions at the legitimate nodes lead to differences in the measurement of ideally reciprocal channels, which further leads to a mismatch in the generated secret key bits, whereas the channel statistics of the same links are more likely to remain unchanged for a reasonably large length of time window over the channel samples. An extensive analysis on the performance of the proposed algorithm is conducted, where the proposed algorithm is observed to provide a promising trade-off between the critical SKG performance metrics namely the Key Generation Rate (KGR), Bit Mismatch Probability (BMP), and the Key Randomness Property (KRP). Furthermore, a comparative performance analysis of the proposed algorithm with other notable techniques is also conducted to demonstrate the superior performance of the proposed algorithm.
Secret key generation at physical layer has attracted more and more attentions as an emerging cryptography method. Compared to traditional security approaches, secret key generation at physical layer not only avoids the problem of key distribution, but also holds high efficiency and low complexity in application. Based on the principle of channel reciprocity, Alice and Bob both estimate the channel conditions and extract shared keys from this source of common randomness. In this paper, we first analyze the basic steps (channel estimation, sample quantization and key reconciliation) of secret key generation, key match rate with different quantization levels and key reconciliation times are also simulated. While in practical situations, different non-reciprocity factors affect the channel estimation step, key match rate can be greatly decreased and hardly meet real time cryptography requirements. In order to increase the key match rate, the unified framework of physical layer key generation has been extended to utilizing multiple observations of wireless channels to generate secret keys. An improved key generation approach with multiple observations can well deal with discrepancies between transceivers and keep increasing the key match rate. Theoretical analysis and simulation results both validate the significant improvement due to multiple observations. With an increased number of observations on both sides, the desired key match rate can be achieved much greater than with a single observation, and also the probability of key recovery by Eve can be decreased.