# Code-Hopping Based Transmission Scheme for Wireless Physical-Layer Security

Authors: Liuguo Yin; Wentao Hao
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Due to the broadcast and time-varying natures of wireless channels, traditional communication systems that provide data encryption at the application layer suffer many challenges such as error diffusion. In this paper, we propose a code-hopping based secrecy transmission scheme that uses dynamic nonsystematic low-density parity-check (LDPC) codes and automatic repeat-request (ARQ) mechanism to jointly encode and encrypt source messages at the physical layer. In this scheme, secret keys at the transmitter and the legitimate receiver are generated dynamically upon the source messages that have been transmitted successfully. During the transmission, each source message is jointly encoded and encrypted by a parity-check matrix, which is dynamically selected from a set of LDPC matrices based on the shared dynamic secret key. As for the eavesdropper (Eve), the uncorrectable decoding errors prevent her from generating the same secret key as the legitimate parties. Thus she cannot select the correct LDPC matrix to recover the source message. We demonstrate that our scheme can be compatible with traditional cryptosystems and enhance the security without sacrificing the error-correction performance. Numerical results show that the bit error rate (BER) of Eve approaches 0.5 as the number of transmitted source messages increases and the security gap of the system is small.


---

## Body

## 1. Introduction

Information security and reliability are two crucial issues in wireless communications. Traditionally, communication systems correct transmission errors at the physical layer based on channel codes and cope with eavesdropping at the application layer based on cryptographic algorithms. In practical scenarios, there will be residual errors in the decoded messages due to the time-varying nature of wireless channels, which may cause severe error diffusion in the decryption. In addition, with the rapid increase of the eavesdropper’s computing power, these computational-complexity based encryption algorithms will be easier to break, such as A5/1 in the GSM.Alternatively, the schemes based on physical-layer security aim to tackle these two crucial issues at the physical layer. Shannon [1] first studied secure communication from an information theoretic perspective in which a preshared secret key between the legitimate parties is used to encrypt the source message. To avoid the key agreement and exploit the inherent randomness of wireless channels, Wyner [2] presented the degraded wiretap channel model in which a transmitter wants to send a secret message to a legitimate receiver through the main channel. This message is also perceived by an eavesdropper through the degraded wiretap channel. The secrecy capacity is defined as the supremum of all the achievable secure and reliable transmission rates. Then, Wyner’s original work was generalized to broadcast channels [3] and Gaussian channels [4]. Moreover, the secrecy capacity of fading wiretap channels [5], MIMO wiretap channels [6], and multiuser wiretap channels [7, 8] has been derived in the literature. In these works, the equivocation of Eve is a widely accepted metric for security, which is defined as the conditional entropy of the source message given her noisy observation [9].Many coding techniques are applied to wiretap channels to make the secrecy transmission rate approach the secrecy capacity, in other words, for the equivocation of Eve to approximate the entropy of the source message. For binary erasure wiretap channels, Thangaraj et al. [10] proposed a coding technique based on the dual of LDPC codes and showed that the secrecy capacity can be achieved by this technique. For symmetric discrete memoryless wiretap channels, Andersson et al. [11] proved that nested polar codes can achieve the whole rate-equivocation region. In addition, this coding technique is further applied to relay-eavesdropper channels [12], block fading channels [13], and multiuser channels [14]. These schemes are really effective when the code length is sufficient, but may be difficult to implement in practical systems.When we consider the design of practical coding schemes, another valuable metric is the BER [15, 16]. In fact, it is difficult for the eavesdropper to recover any information from the decoded message when she experiences a BER of about 0.5 and the errors are randomly distributed. Security gap is defined as the quantity difference between Bob’s and Eve’s channels required to achieve a sufficient level of physical-layer security, while ensuring that Bob reliably receives the information [17]. In [17], punctured systematic LDPC codes were exploited to obtain a small security gap. Furthermore, a nonsystematic solution based on scrambled systematic LDPC codes was proposed in [18]. It was proved that the achievable security gap of the scrambled scheme is smaller than that of the punctured method. In [19], scrambling, concatenation, and hybrid automatic repeat-request (HARQ) were combined to reduce the security gap even further. In addition, dynamic LDPC codes are used to enhance the security of the communication system [20]. And protograph LDPC codes [21, 22] can also be used to guarantee the security of the transmission.In this paper, we propose a scheme based on code-hopping for secrecy transmission over wireless wiretap channels. In the proposed scheme, with ARQ mechanism, the transmitter and the legitimate receiver can select the source messages in real time to distill the secret key. This secret key is then mapped into the parity-check matrix of LDPC codes, which is used to encode the source message. As for the eavesdropper, the uncorrectable decoding errors prevent her from generating the same secret key as the transmitter and the legitimate receiver. Therefore, she cannot obtain the correct parity-check matrix to recover the source message. Theoretical analysis demonstrates that it is difficult for the eavesdropper to generate the same secret key as legitimate parties. Simulation results show that the BER of Eve approaches 0.5 as the number of transmissions increases and the security gap of the system is small.The remainder of the paper is organized as follows. We introduce our system model and the design of the encoder and decoder in Section2. In Section 3, the dynamic secret key generation algorithm is proposed and the security of the secret key is well examined. In Section 4, we construct a large number of parity-check matrices of LDPC codes based on the technique we called structured-random protograph expanding. Encoder and Decoder implementation of structured-random LDPC codes are discussed in Section 5. In Section 6, we analyze the reliability and the security performance of our scheme. And some numerical results are given in Section 7. Finally, concluding remarks are provided in Section 8.


## 2. The Proposed Secrecy Transmission Scheme

In this section, we will first introduce the wiretap channel model with public feedback and the concept of security gap. Then, we will propose our secrecy transmission scheme along with the design of encoder and decoder.


### 2.1. System Model

As shown in Figure1, for i=1,2,…, message mi is a sequence of uncoded bits and the length of mi is s. A transmitter named Alice wants to send mi to a legitimate receiver named Bob through the main channel, but her transmission is also perceived by an eavesdropper named Eve through the wiretap channel. To keep mi as secret as possible, Alice encodes each length-s message mi to a length-n codeword xi by her encoder. The corresponding received codewords by Bob and Eve are denoted by yi and zi, which are recovered by the decoder as m^i and m¯i, respectively. Additionally, in our model, Bob can use a public feedback channel to inform Alice whether the current codeword is decoded successfully with a feedback signal fi. If there occurs a decoding error at Bob, Alice will retransmit the source message until Bob successfully recovers it or the number of retransmissions reaches the maximum. Taking into account the application in practical scenarios, both channels are assumed to be Gaussian or fading channels:(1)yi=hiBxi+niB,zi=hiExi+niE,where hiB and hiE are the fading coefficients, which are equal to one for Gaussian scenario and follow a certain distribution for fading scenario and niB and niE are zero mean Gaussian noise; niB~N(0,σB2) and niE~N(0,σE2).Figure 1
Wiretap channel model with public feedback.LetPeB and PeE denote the average BER of Bob and Eve, respectively. As shown in Figure 2, to guarantee the reliability, PeB should be lower than a given threshold Perr,maxB (≈0). And to achieve the confidentiality, PeE should be larger than a given threshold Perr,minE (≈0.5). Particularly, if PeE is close to 0.5 and the errors are randomly distributed, Eve cannot extract any information from the decoded messages. Based on this observation, the reliability and security of the transmission are guaranteed if conditions (2) and (3) can be satisfied [17], respectively:(2)PeB≤Perr,maxB=PeSNRminB,(3)PeE≥Perr,minE=PeSNRmaxE,where SNRminB is the lowest signal-to-noise ratio at Bob to guarantee reliability, SNRmaxE is the highest signal-to-noise ratio at Eve to guarantee security, and Pe(·) denotes the BER as the function of SNR. Then, the security gap is defined as follows [17]:(4)Sg=SNRminB-SNRmaxE,where the SNRs are expressed in decibels (dB). Without sacrificing the error-correcting performance of the transmission system, our design targets are making the BER of Eve approach 0.5 and reducing the security gap as much as possible.Figure 2
Security gap established by the BER curve.


### 2.2. Design of the Coding Scheme

To exploit the inherent randomness of wireless channels and the uncorrectable decoding errors of Eve, our scheme is implemented such that the secret keys are distilled from the un-retransmitted source messages, which are then used to generate the parity-check matrices of LDPC codes. During the transmission, the source messages are encoded and decoded by these dynamic parity-check matrices. The block diagrams of the encoder and the decoder are illustrated in Figures3 and 4, respectively.Figure 3
Block diagram of the encoder. Note that thez-1 block denotes a delay unit.Figure 4
Block diagram of the decoder. Note that thez-1 block denotes a delay unit.In the encoder of Alice, the secret keyKi is updated dynamically according to the received feedback signal fi-1 and the source message mi-1. If fi-1=ACK, then Ki will be updated according to mi-1. If fi-1=NACK, Ki will remain unchanged. The detailed procedure of key update will be discussed in Section 3. Then, the secret key Ki will be used to generate the parity-check matrix of LDPC codes as follows:(5)Hi=fHKi,where fH(·) is the mapping from the secret key to the parity-check matrix. For each source message mi, it will be encoded by the corresponding Hi.In the decoder of Bob, the integrity of the decoded source messagem^i will be checked. If m^i is recovered without errors, the public feedback signal fi=ACK; otherwise, fi=NACK. Instead of using the syndrome of the decoded codeword to determine the correctness of m^i, we use the cyclic redundancy check (CRC) algorithm to perform integrity check. This is because when the decoded codeword converges to another valid codeword of Hi, the method based on the syndrome cannot detect errors. As for the symmetric key Ki and the parity-check matrix Hi, they will be generated as in Alice’s encoder.


## 2.1. System Model

As shown in Figure1, for i=1,2,…, message mi is a sequence of uncoded bits and the length of mi is s. A transmitter named Alice wants to send mi to a legitimate receiver named Bob through the main channel, but her transmission is also perceived by an eavesdropper named Eve through the wiretap channel. To keep mi as secret as possible, Alice encodes each length-s message mi to a length-n codeword xi by her encoder. The corresponding received codewords by Bob and Eve are denoted by yi and zi, which are recovered by the decoder as m^i and m¯i, respectively. Additionally, in our model, Bob can use a public feedback channel to inform Alice whether the current codeword is decoded successfully with a feedback signal fi. If there occurs a decoding error at Bob, Alice will retransmit the source message until Bob successfully recovers it or the number of retransmissions reaches the maximum. Taking into account the application in practical scenarios, both channels are assumed to be Gaussian or fading channels:(1)yi=hiBxi+niB,zi=hiExi+niE,where hiB and hiE are the fading coefficients, which are equal to one for Gaussian scenario and follow a certain distribution for fading scenario and niB and niE are zero mean Gaussian noise; niB~N(0,σB2) and niE~N(0,σE2).Figure 1
Wiretap channel model with public feedback.LetPeB and PeE denote the average BER of Bob and Eve, respectively. As shown in Figure 2, to guarantee the reliability, PeB should be lower than a given threshold Perr,maxB (≈0). And to achieve the confidentiality, PeE should be larger than a given threshold Perr,minE (≈0.5). Particularly, if PeE is close to 0.5 and the errors are randomly distributed, Eve cannot extract any information from the decoded messages. Based on this observation, the reliability and security of the transmission are guaranteed if conditions (2) and (3) can be satisfied [17], respectively:(2)PeB≤Perr,maxB=PeSNRminB,(3)PeE≥Perr,minE=PeSNRmaxE,where SNRminB is the lowest signal-to-noise ratio at Bob to guarantee reliability, SNRmaxE is the highest signal-to-noise ratio at Eve to guarantee security, and Pe(·) denotes the BER as the function of SNR. Then, the security gap is defined as follows [17]:(4)Sg=SNRminB-SNRmaxE,where the SNRs are expressed in decibels (dB). Without sacrificing the error-correcting performance of the transmission system, our design targets are making the BER of Eve approach 0.5 and reducing the security gap as much as possible.Figure 2
Security gap established by the BER curve.


## 2.2. Design of the Coding Scheme

To exploit the inherent randomness of wireless channels and the uncorrectable decoding errors of Eve, our scheme is implemented such that the secret keys are distilled from the un-retransmitted source messages, which are then used to generate the parity-check matrices of LDPC codes. During the transmission, the source messages are encoded and decoded by these dynamic parity-check matrices. The block diagrams of the encoder and the decoder are illustrated in Figures3 and 4, respectively.Figure 3
Block diagram of the encoder. Note that thez-1 block denotes a delay unit.Figure 4
Block diagram of the decoder. Note that thez-1 block denotes a delay unit.In the encoder of Alice, the secret keyKi is updated dynamically according to the received feedback signal fi-1 and the source message mi-1. If fi-1=ACK, then Ki will be updated according to mi-1. If fi-1=NACK, Ki will remain unchanged. The detailed procedure of key update will be discussed in Section 3. Then, the secret key Ki will be used to generate the parity-check matrix of LDPC codes as follows:(5)Hi=fHKi,where fH(·) is the mapping from the secret key to the parity-check matrix. For each source message mi, it will be encoded by the corresponding Hi.In the decoder of Bob, the integrity of the decoded source messagem^i will be checked. If m^i is recovered without errors, the public feedback signal fi=ACK; otherwise, fi=NACK. Instead of using the syndrome of the decoded codeword to determine the correctness of m^i, we use the cyclic redundancy check (CRC) algorithm to perform integrity check. This is because when the decoded codeword converges to another valid codeword of Hi, the method based on the syndrome cannot detect errors. As for the symmetric key Ki and the parity-check matrix Hi, they will be generated as in Alice’s encoder.


## 3. Dynamic Secret Key Generation Scheme

In this section, we will introduce the dynamic secret key generation algorithm and the mathematical rationales behind it. With this algorithm, Alice and Bob can select the appropriate source messages during the transmission and then distill the secret key based on the universal hashing family.


### 3.1. Automatic Source Message Selection

In this subsection, we will show how Alice and Bob select appropriate source messages in real time during the transmission, which is then hashed into the dynamic secret key. We defineψit and ψir as the source message set that is used to generate the secret key Ki at Alice and Bob, respectively. To give Alice and Bob an advantage over Eve, only un-retransmitted source messages will be included in ψit and ψir. Before the communication begins, ψ0t=ψ0r=(ψ0,0,ψ0,1,…,ψ0,D-1), where D is the number of source messages in the set and ψ0,j is the public agreed initialized binary vector of length-s, j=0,1,…,D-1.As illustrated in Figure5, during the transmission, Alice transmits a source message mi and waits for the corresponding feedback signal fi before transmitting any new source message. If the received feedback signal fi=NACK, ψi+1t will remain unchanged compared to ψit:(6)ψi+1t=ψi+1,0,ψi+1,1,…,ψi+1,D-1=ψi,0,ψi,1,…,ψi,D-1.If the received feedback signal fi=ACK, ψi+1t will be updated as follows:(7)ψi+1t=ψi+1,0,…,ψi+1,D-2,ψi+1,D-1=ψi,1,…,ψi,D-1,mi.Figure 5
The process of automatic source massage selection.As for Bob, if he recovers the source message successfully, he will also update the setψi+1r in the same way and send a feedback signal fi=ACK. If he fails, he will keep ψi+1r=ψir and send a feedback signal fi=NACK. This strategy guarantees that ψit=ψir=ψi.Because there are totallyD elements in ψi and the length of each element is s bits, the space complexity of storing ψi is O(Ds). The update of ψi is similar to that of a queue. In the update process, the first element in ψi will be removed and discarded. The second element in ψi will be moved to the first location and so on. As for the new element, that is, the source message that has been successfully transmitted, it will be moved to the last location. Considering that the length of each element is s bits, only additional s bits of space are needed to store the element that is being moved. Therefore, the space complexity of updating ψi is O(s).It is very difficult for Eve to reproduceψi. She must eavesdrop on not only every source message, but also all of the feedback signals. Whenever the eavesdropper has uncertainty about ψi, the uncertainty is reflected in the corresponding secret key.


### 3.2. Secret Key Distillation

In this subsection, we will introduce how to distill a secret key from the source message setψi. Our target is retaining as much of the eavesdropper’s information loss as possible in the secret key. The theory of universal hash family (UHF) provides a powerful solution for us. A UHF is a family of functions such that the random mapping obtained by uniformly choosing a function from this family is almost invertible [23]. In other words, regardless of the actual input distribution, by uniform-randomly choosing a function from a universal hash family, the expected hash output distribution will be close to the uniform. In our considered scenario, ψi is hashed into a secret key Ki by using a function fkey that is selected from the universal hash function families F. And the conditional distribution of Ki given the eavesdropper’s knowledge about ψi can be close to the uniform distribution. Because a nearly uniform distribution means nearly maximum entropy, the eavesdropper knows almost nothing about Ki. Based on the generalized result from [24], the security of Ki can be evaluated by(8)HKi∣F,Ei=ei≥H2Ki∣F,Ei=ei(9)≥l-log21+2l-lr(10)≥l-2l-lrln⁡2,where Ei=ei is the eavesdropper’s knowledge about ψi, l is the length of Ki in bits, and H2(·) is the Renyi entropy of order 2 [24]. When the probability that Ei=ei is at least (1-δ), formula (9) can be generalized as(11)HKi∣F,Ei≥1-δl-log21+2l-lr. Formulas (9) and (11) show that if the length of the secret key does not exceed lr, Ki is secure because averagely Eve will have less than one-bit information about Ki. And lr can be estimated as follows:(12)lr≤H2ψi∣Ei=ei. It is noteworthy that (9) and (11) are averaged over all uniformly choices of hash functions. It is possible that, for some specific values of F, H(Ki∣F,Ei) is not negligible when l≤lr. However, it appears with negligible probability [24].Because of the randomness of the wireless channel, it is impossible for Eve to recover each source message inψi. H2(ψi∣Ei=ei) can be calculated as follows [24]:(13)H2ψi∣Ei=ei=-d·log21-PeE2+PeE2, where d=Ds is the length of ψi in bits.Figure6 illustrates the relationship between Eve’s BER and the number of secret key bits we can distill from each source message bit. We can see that, with the increase of Eve’s BER, we can distill more secret key bits averagely from each source message bit. It shows that the eavesdropper’s information loss is retained in the secret key.Figure 6
The number of secret key bits we can distill from each source message bit versus Eve’s BER.In our considered wiretap channel model, Eve’s BER can be calculated by Bob’s maximum BER and the security gap:(14)PeE=PeSNRE=PeSNRB-Sg=PePe-1PeB-Sg.Then, we can calculatelr as follows:(15)lr=-d·log21-PeE2+PeE2(16)=-d·log21-PePe-1PeB-Sg2+PePe-1PeB-Sg2.Considering thatd=Ds, according to (16), we can choose the value of D as follows:(17)D=-lrlog21-PePe-1PeB-Sg2+PePe-1PeB-Sg2s.


### 3.3. Implementation of UHF

In this subsection, we will show how to implement the universal hash functionfkey(·) in practical scenarios. A Toeplitz matrix is a matrix in which each descending diagonal from left to right is constant and is a kind of UHF that can be implemented with low complexity [25]. In our proposed scheme, we try to generate secret key Ki with length l from the source message set ψi with length d. The corresponding Toeplitz matrix is as follows:(18)T=tltl+1⋯tl+d-2tl+d-1tl-1tl⋯tl+d-3tl+d-2⋮tl-1⋱⋮⋮t2⋮⋱tdtd+1t1t2⋯td-1td,where t1,t2,…,tl,…,tl+d-1 is the randomly generated element over GF(2). The secret key can be generated by multiplying T and ψ:(19)Ki=fkeyψi=T×ψiT.The computational complexity of (19) is O(d2). To reduce the computational complexity, we can use the improved algorithm based on fast Fourier transformation (FFT) [26]. Based on the Toeplitz matrix T, we can obtain a new circular matrix TC as follows:(20)TC=TR1R2R3=Circutl,tl+1,…,tl+d-1,t1,…,tl-1,where R1, R2, and R3 are the submatrices defined in [26], which make the extended matrix TC a circular matrix. Circu(·) denotes the circular matrix, which can be represented by its first row.Then, we generate a new vectorψ^i=(ψi,0) by combining ψi with a zero vector 0, where the length of ψ^i equals the columns of TC. The secret key can be generated by multiplying TC and ψ^i, which can be calculated using the FFT-based method:(21)Ki=TC×ψ^iT=F-1FTC1∘Fψ^i,where F(·) is the Fourier transform and F-1(·) is the inverse, TC(1) is the first row of TC, and ∘ denotes the operation that multiplies the corresponding elements in the vector. The computational complexity of (21) is O(dlog⁡d).


## 3.1. Automatic Source Message Selection

In this subsection, we will show how Alice and Bob select appropriate source messages in real time during the transmission, which is then hashed into the dynamic secret key. We defineψit and ψir as the source message set that is used to generate the secret key Ki at Alice and Bob, respectively. To give Alice and Bob an advantage over Eve, only un-retransmitted source messages will be included in ψit and ψir. Before the communication begins, ψ0t=ψ0r=(ψ0,0,ψ0,1,…,ψ0,D-1), where D is the number of source messages in the set and ψ0,j is the public agreed initialized binary vector of length-s, j=0,1,…,D-1.As illustrated in Figure5, during the transmission, Alice transmits a source message mi and waits for the corresponding feedback signal fi before transmitting any new source message. If the received feedback signal fi=NACK, ψi+1t will remain unchanged compared to ψit:(6)ψi+1t=ψi+1,0,ψi+1,1,…,ψi+1,D-1=ψi,0,ψi,1,…,ψi,D-1.If the received feedback signal fi=ACK, ψi+1t will be updated as follows:(7)ψi+1t=ψi+1,0,…,ψi+1,D-2,ψi+1,D-1=ψi,1,…,ψi,D-1,mi.Figure 5
The process of automatic source massage selection.As for Bob, if he recovers the source message successfully, he will also update the setψi+1r in the same way and send a feedback signal fi=ACK. If he fails, he will keep ψi+1r=ψir and send a feedback signal fi=NACK. This strategy guarantees that ψit=ψir=ψi.Because there are totallyD elements in ψi and the length of each element is s bits, the space complexity of storing ψi is O(Ds). The update of ψi is similar to that of a queue. In the update process, the first element in ψi will be removed and discarded. The second element in ψi will be moved to the first location and so on. As for the new element, that is, the source message that has been successfully transmitted, it will be moved to the last location. Considering that the length of each element is s bits, only additional s bits of space are needed to store the element that is being moved. Therefore, the space complexity of updating ψi is O(s).It is very difficult for Eve to reproduceψi. She must eavesdrop on not only every source message, but also all of the feedback signals. Whenever the eavesdropper has uncertainty about ψi, the uncertainty is reflected in the corresponding secret key.


## 3.2. Secret Key Distillation

In this subsection, we will introduce how to distill a secret key from the source message setψi. Our target is retaining as much of the eavesdropper’s information loss as possible in the secret key. The theory of universal hash family (UHF) provides a powerful solution for us. A UHF is a family of functions such that the random mapping obtained by uniformly choosing a function from this family is almost invertible [23]. In other words, regardless of the actual input distribution, by uniform-randomly choosing a function from a universal hash family, the expected hash output distribution will be close to the uniform. In our considered scenario, ψi is hashed into a secret key Ki by using a function fkey that is selected from the universal hash function families F. And the conditional distribution of Ki given the eavesdropper’s knowledge about ψi can be close to the uniform distribution. Because a nearly uniform distribution means nearly maximum entropy, the eavesdropper knows almost nothing about Ki. Based on the generalized result from [24], the security of Ki can be evaluated by(8)HKi∣F,Ei=ei≥H2Ki∣F,Ei=ei(9)≥l-log21+2l-lr(10)≥l-2l-lrln⁡2,where Ei=ei is the eavesdropper’s knowledge about ψi, l is the length of Ki in bits, and H2(·) is the Renyi entropy of order 2 [24]. When the probability that Ei=ei is at least (1-δ), formula (9) can be generalized as(11)HKi∣F,Ei≥1-δl-log21+2l-lr. Formulas (9) and (11) show that if the length of the secret key does not exceed lr, Ki is secure because averagely Eve will have less than one-bit information about Ki. And lr can be estimated as follows:(12)lr≤H2ψi∣Ei=ei. It is noteworthy that (9) and (11) are averaged over all uniformly choices of hash functions. It is possible that, for some specific values of F, H(Ki∣F,Ei) is not negligible when l≤lr. However, it appears with negligible probability [24].Because of the randomness of the wireless channel, it is impossible for Eve to recover each source message inψi. H2(ψi∣Ei=ei) can be calculated as follows [24]:(13)H2ψi∣Ei=ei=-d·log21-PeE2+PeE2, where d=Ds is the length of ψi in bits.Figure6 illustrates the relationship between Eve’s BER and the number of secret key bits we can distill from each source message bit. We can see that, with the increase of Eve’s BER, we can distill more secret key bits averagely from each source message bit. It shows that the eavesdropper’s information loss is retained in the secret key.Figure 6
The number of secret key bits we can distill from each source message bit versus Eve’s BER.In our considered wiretap channel model, Eve’s BER can be calculated by Bob’s maximum BER and the security gap:(14)PeE=PeSNRE=PeSNRB-Sg=PePe-1PeB-Sg.Then, we can calculatelr as follows:(15)lr=-d·log21-PeE2+PeE2(16)=-d·log21-PePe-1PeB-Sg2+PePe-1PeB-Sg2.Considering thatd=Ds, according to (16), we can choose the value of D as follows:(17)D=-lrlog21-PePe-1PeB-Sg2+PePe-1PeB-Sg2s.


## 3.3. Implementation of UHF

In this subsection, we will show how to implement the universal hash functionfkey(·) in practical scenarios. A Toeplitz matrix is a matrix in which each descending diagonal from left to right is constant and is a kind of UHF that can be implemented with low complexity [25]. In our proposed scheme, we try to generate secret key Ki with length l from the source message set ψi with length d. The corresponding Toeplitz matrix is as follows:(18)T=tltl+1⋯tl+d-2tl+d-1tl-1tl⋯tl+d-3tl+d-2⋮tl-1⋱⋮⋮t2⋮⋱tdtd+1t1t2⋯td-1td,where t1,t2,…,tl,…,tl+d-1 is the randomly generated element over GF(2). The secret key can be generated by multiplying T and ψ:(19)Ki=fkeyψi=T×ψiT.The computational complexity of (19) is O(d2). To reduce the computational complexity, we can use the improved algorithm based on fast Fourier transformation (FFT) [26]. Based on the Toeplitz matrix T, we can obtain a new circular matrix TC as follows:(20)TC=TR1R2R3=Circutl,tl+1,…,tl+d-1,t1,…,tl-1,where R1, R2, and R3 are the submatrices defined in [26], which make the extended matrix TC a circular matrix. Circu(·) denotes the circular matrix, which can be represented by its first row.Then, we generate a new vectorψ^i=(ψi,0) by combining ψi with a zero vector 0, where the length of ψ^i equals the columns of TC. The secret key can be generated by multiplying TC and ψ^i, which can be calculated using the FFT-based method:(21)Ki=TC×ψ^iT=F-1FTC1∘Fψ^i,where F(·) is the Fourier transform and F-1(·) is the inverse, TC(1) is the first row of TC, and ∘ denotes the operation that multiplies the corresponding elements in the vector. The computational complexity of (21) is O(dlog⁡d).


## 4. Design of Structure-Random LDPC Codes

In this section, we will show how to construct a large number of parity-check matrices of LDPC codes based on the technique we called structured-random protograph expanding. A protograph is a Tanner graph with a relatively small number of nodes [27], which can be used to construct the parity-check matrix of LDPC codes. Because systematic codes directly expose the secret message bits, all of the s information bits will be punctured and the n parity bits will be transmitted.We use the code doping method in [28] to design and optimize our protograph to ensure that the iterative decoding of the designed LDPC codes can be triggered successively. Figure 7 shows our optimized protograph P=(V,C,E) for a rate-1/2 nonsystematic LDPC code. We denote V as the set of variable nodes {v1,v2,…,v6}, C as the set of check nodes {c1,c2,…,c4}, and E as the set of edges {e1,e2,…,e16}. In the designed protograph, we will puncture the information nodes denoted by v1 and v2 among all the variable nodes to avoid systematic transmission.Figure 7
ProtographP for the nonsystematic LDPC code. The rate is 1/2.To guarantee the convergence of the brief propagation (BP) decoding algorithm, the connection relationship of the check nodec4 is specially designed. In our designed protograph, the check node c4 is connected to only one punctured variable node v2. Equivalently, we can use a base parity-check matrix HB,0 with size 4×6 to represent this protograph.(22)HB,0=110010110001311100011200.A “copy-and-permute” operation can be applied to the protographP to obtain a large derived Tanner graph. We define T as the expanded factor; the “copy-and-permute” operation firstly makes T copies of the protograph P and then permutes the endpoints of each edge among the T variable nodes and T check nodes connected to the set of T edges copied from the same edge from the original protograph P.After this operation, we can obtain a large Tanner graph, where theT copies of the original protograph are connected to each other. Equivalently, we can expand each element of value w in the base matrix HB,0 to a T×T matrix with w ones in each row or column. As a result, we can obtain a large matrix with size 4T×6T.Because random permutation is not easy to describe and implement efficiently, in our scheme, we adopt the structured type of permutation, such as cyclic permutation. In other words, we expand each element of valuew in the base matrix HB,0 to T×T circulant permutation matrices IT(t). As a result, the expanded parity-check matrix will become a T-circulant matrix.To construct a large number of parity-check matrices of LDPC codes, it is not enough to expand the protographP with just one single stage. Therefore, we develop a structured-random protograph expanding technique. This technique expands the protograph P with L>1 stages. We denote T1,T2,…,TL as the expanding factors for stages 1,2,…,L, respectively. The total expanding factor T can be calculated as T=T1T2⋯TL. Finally, the base matrix HB,0 is expanded to the parity-check matrix HB,L.(i)
Structured expanding: in the procedure of structured expanding, we expand the protograph P in the first L-1 stages to avoid parallel edges, short cycles, and low-weight codewords. As a result, all the nonzero elements in HB,L-1 will be equal to 1.(ii)
Random expanding: in the procedure of random expanding, we expand HB,L-1 in the L stage based on the value of the dynamic secret key Ki. For each zero element in HB,L-1, we will expand it by a TL×TL zero matrix 0TL×TL. For each nonzero element, we will expand it by a TL×TL circulant permutation matrix ITL(t). The total number of zero and nonzero elements is J=ET/TL.As for the parameters that are used in the procedure of structured expanding, that is, all the shift values and expanding factors, they are constant and will be shared between Alice and Bob publicly in advance. Now, we rewrite the dynamic secret keyKi as a binary vector:(23)Ki=ki,0,ki,1,…,ki,j,…,ki,J-1, where each element ki,j∈0,TL-1 is represented by log2TL bits. Regarding the parameters that are used in the procedure of random expanding, that is, all the random shift values, they are controlled by the dynamic secret key Ki, whose length is required to be l=Jlog2TL bits.After expanding the protographP with L>1 stages, the base matrix HB,0 is expanded to an n×(n+s) parity-check matrix Hi, where n=4T and s=2T. As mentioned above, Hi is a TL-circulant matrix and can be written as Hi=A(Ki),B(Ki) such that(24)AKi=Aαβw2×4=A111A121A211A221A313A3210A421,BKi=Bαβw4×4=00B1310000B241B311B32100B411B42200. The first s=2T nodes are punctured as information nodes among all the n+s=6T variable nodes.


### 4.1. An Example

In this subsection, we construct a large number of nonsystematic (2048, 1024) LDPC codes viaL=3 stages. The total expanding factor T=T1T2T3=4×4×32=512. With the factor T1=4, the first stage aims to separate all the parallel edges. With the factor T2=4, the second stage aims to avoid the existence of the cycle of girth 4. With the factor T3=32, the third stage aims to randomly expand all the ET/T3=256 edges. Finally, we get a set of parity-check matrices H={H(r):r∈0,2256-1}.During the transmission, we randomly select a parity-check matrix for each source message. The number of iterations is restricted by63. In Figure 8, we show the average BER of the structured-random nonsystematic (2048, 1024) LDPC codes with different number of retransmissions r.Figure 8
The average BER of the nonsystematic (2048, 1024) LDPC codes with different maximum retransmission numberr.


## 4.1. An Example

In this subsection, we construct a large number of nonsystematic (2048, 1024) LDPC codes viaL=3 stages. The total expanding factor T=T1T2T3=4×4×32=512. With the factor T1=4, the first stage aims to separate all the parallel edges. With the factor T2=4, the second stage aims to avoid the existence of the cycle of girth 4. With the factor T3=32, the third stage aims to randomly expand all the ET/T3=256 edges. Finally, we get a set of parity-check matrices H={H(r):r∈0,2256-1}.During the transmission, we randomly select a parity-check matrix for each source message. The number of iterations is restricted by63. In Figure 8, we show the average BER of the structured-random nonsystematic (2048, 1024) LDPC codes with different number of retransmissions r.Figure 8
The average BER of the nonsystematic (2048, 1024) LDPC codes with different maximum retransmission numberr.


## 5. Encoder and Decoder Implementation of Structured-Random LDPC Codes

### 5.1. Encoder Implementation

To implement the encoder of structured-random LDPC codes, we need to derive thes×n nonsystematic generator matrix Gi according to the parity-check matrix Hi. According to (24), Gi can be derived by(25)Gi=BKi-1·AKiT=Gi11Gi12Gi13Gi14Gi21Gi22Gi23Gi24=A313TD1A313TD3A111TB13A211TB24A321TD1⊕A421TD2A321TD3⊕A421TCTA121TB13A221TB13, where D1=(I⊕B311(B411)TCT(B321)T)B311, D2=CT(B321)TB311, D3=B311(B411)TCT, and C=((B422)T⊕(B321)TB311(B411)T)-1.The multiplication betweenmi and Gi can be calculated in blocks:(26)mi·Gi=mi11mi12×Gi11Gi12Gi13Gi14Gi21Gi22Gi23Gi24=xi11xi12xi13xi14,where (xi)11=(mi)11(Gi)11+(mi)12(Gi)21, (xi)12=(mi)11(Gi)12+(mi)12(Gi)22, (xi)13=(mi)11(Gi)13+(mi)12(Gi)23, and (xi)14=(mi)11(Gi)14+(mi)12(Gi)24. The multiplication between (mi)ab and (Gi)a´b´ can be further divided as in [29]. For example, to multiply by (Gi)12 can be divided into four steps by successively multiplying by (A313)T, B311, (B411)T, and CT. Because all those submatrices are circulant, all the required multiplications in the encoding process can be finished in O(n) time. The additional computational complexity is from the inversion operation to derive C. In [30], authors have shown the inversion of a binary matrix can be finished in O(n) time by using a parallel hardware architecture. Therefore, the encoding process can be finished in O(n) time.Consider that the size ofC is about 1/8 of the size of Gi. Thus, the designed encoder for structured-random LDPC codes will increase by 1/8 of the storage compared to the traditional encoder for QC-LDPC codes with a fixed parity-check matrix [31, 32].


### 5.2. Decoder Implementation

As for the decoder of structured-random LDPC codes, it can be extended from the conventional decoder of quasi-cyclic LDPC codes with a fixed parity-check matrix [33, 34]. This is because the parity-check matrix Hi of structured-random LDPC codes is also quasi-cyclic as shown in Section 4. The only difference is that the shift values of the circulant permutation matrices in Hi will be updated according to the dynamic secret key Ki. When the shift values are successfully updated, the iterative decoding process is the same. Therefore, the decoder implementation complexity of structured-random LDPC codes will be the same as that of quasi-cyclic LDPC codes with a fixed parity-check matrix.


## 5.1. Encoder Implementation

To implement the encoder of structured-random LDPC codes, we need to derive thes×n nonsystematic generator matrix Gi according to the parity-check matrix Hi. According to (24), Gi can be derived by(25)Gi=BKi-1·AKiT=Gi11Gi12Gi13Gi14Gi21Gi22Gi23Gi24=A313TD1A313TD3A111TB13A211TB24A321TD1⊕A421TD2A321TD3⊕A421TCTA121TB13A221TB13, where D1=(I⊕B311(B411)TCT(B321)T)B311, D2=CT(B321)TB311, D3=B311(B411)TCT, and C=((B422)T⊕(B321)TB311(B411)T)-1.The multiplication betweenmi and Gi can be calculated in blocks:(26)mi·Gi=mi11mi12×Gi11Gi12Gi13Gi14Gi21Gi22Gi23Gi24=xi11xi12xi13xi14,where (xi)11=(mi)11(Gi)11+(mi)12(Gi)21, (xi)12=(mi)11(Gi)12+(mi)12(Gi)22, (xi)13=(mi)11(Gi)13+(mi)12(Gi)23, and (xi)14=(mi)11(Gi)14+(mi)12(Gi)24. The multiplication between (mi)ab and (Gi)a´b´ can be further divided as in [29]. For example, to multiply by (Gi)12 can be divided into four steps by successively multiplying by (A313)T, B311, (B411)T, and CT. Because all those submatrices are circulant, all the required multiplications in the encoding process can be finished in O(n) time. The additional computational complexity is from the inversion operation to derive C. In [30], authors have shown the inversion of a binary matrix can be finished in O(n) time by using a parallel hardware architecture. Therefore, the encoding process can be finished in O(n) time.Consider that the size ofC is about 1/8 of the size of Gi. Thus, the designed encoder for structured-random LDPC codes will increase by 1/8 of the storage compared to the traditional encoder for QC-LDPC codes with a fixed parity-check matrix [31, 32].


## 5.2. Decoder Implementation

As for the decoder of structured-random LDPC codes, it can be extended from the conventional decoder of quasi-cyclic LDPC codes with a fixed parity-check matrix [33, 34]. This is because the parity-check matrix Hi of structured-random LDPC codes is also quasi-cyclic as shown in Section 4. The only difference is that the shift values of the circulant permutation matrices in Hi will be updated according to the dynamic secret key Ki. When the shift values are successfully updated, the iterative decoding process is the same. Therefore, the decoder implementation complexity of structured-random LDPC codes will be the same as that of quasi-cyclic LDPC codes with a fixed parity-check matrix.


## 6. Performance Analysis

In this section, we will analyze the security and reliability performances of our proposed scheme. As shown in the previous section, we can construct a large number of nonsystematic LDPC codes that have good error-correction performance. Therefore, we can guarantee that Bob’s BERPeB will be lower than the given threshold by utilizing these nonsystematic LDPC codes. It guarantees the reliability of the transmission. We will analyze the security of our scheme in two aspects: the complexity when Eve tries to crack the dynamic secret key and Eve’s average BER during the whole transmission.Different from the traditional cryptosystems that have to distribute the secret key before communication begins, our scheme generates the secret keyKi dynamically from the source message set ψi. During the transmission, an event which is referred to as synchronization error may happen. That is, there exists an index iTH∈N, such that ziTH is not correctly decoded by Eve, but yiTH is successfully recovered by Bob. At this moment, Eve’s source message set ψ¯i+1 will be different from Alice’s and Bob’s source message set ψi+1. Therefore, Eve cannot generate the same secret key as Alice and Bob.As analyzed in Section3, universal hash function makes the conditional distribution of Ki close to the uniform distribution as follows:(27)PKi=ki∣Ei=ei≈1Ki,∀ki∈Ki. From the information theoretic perspective, (27) means that the conditional entropy of Ki is close to its self-information(28)HKi∣Ei=ei≈HKi=log2Ki. Therefore, the computational complexity of Eve to crack a dynamic secret key is approximated to 2Ki=2l. Even if Eve cracks the secret key by the exhaustive search, the similar synchronization error may happen again and she has to repeat the cracking process.To evaluate the probability that the synchronization error happens, we denotePf(·) as the frame error rate (FER) as the function of SNR. Bob’s FER and Eve’s FER can be expressed as PfB=Pf(SNRB) and PfE=Pf(SNRE), respectively. And iTH is distributed geometrically; iTH~G(p0), where p0=(1-PfB)PfE. Thus, the probability distribution of iTH can be calculated as(29)PriTH=i=1-1-PfBPfEi-11-PfBPfE.As analyzed above, it is difficult for Eve to generate the same secret key as Alice and Bob once the synchronization error happens. In other words, Eve cannot generate the correct parity-check matrix to decodeziTH. To evaluate Eve’s BER during the whole transmission, we can divide the source messages that Eve fails to recover into two categories. The first category contains the source messages that Eve fails to recover before the synchronization error happens. For the messages in the first category, they are recovered by Eve using the correct parity-check matrix. The number of messages in the first category N1(iTH) obeys the binomial distribution, N1(iTH)~B(iTH-1,p1), where p1=PfBPfE/1-(1-PfB)PfE. Thus, the average of N1(iTH) can be calculated as(30)N¯1iTH=iTHp1=iTH-1PfBPfE1-1-PfBPfE. And the average number of error bits in each error message can be calculated as(31)kER=PeSNRE·sPfSNRE.For the messages in the second category, half of their bits are wrong, because Eve cannot generate the correct parity-check matrix as Alice and Bob. Finally, Eve’s BER can be calculated as(32)PeE=∑i=1NkER·N¯1i+0.5s·N-i+1k·N·PriTH=i+kER·N¯1N+1k·N·PriTH≥N+1. Based on (30), PeE can be further calculated as(33)PeE=∑i=1NkER·i-1·p1+0.5s·N-i+1s·N·PriTH=i+kER·N·p1s·N·PriTH≥N+1≥∑i=1NkER·i-1·p1+0.5s·N-i+1s·N·PriTH=i=0.5s·N∑i=1NPr⁡iTH=is·N+kER·p1-0.5s∑i=1Ni-1·Pr⁡iTH=is·N≥0.5·1-PriTH≥N+1-0.5·∑i=1∞i·Pr⁡iTH=iN=0.5·1-PriTH≥N+1-0.5·i¯THN=0.5·1-1-p0N-i¯THN, where i¯TH is defined as follows:(34)i¯TH=∑i=1∞i·PriTH=i=1p0=11-pfBpfE. Finally, PeE can be lower bounded as follows:(35)PeE≥0.5·1-1-p0N-1N·p0→N→∞0.5. From the above analysis, we can know that Eve’s BER PeE will approach 0.5 when the number of the transmitted messages goes to infinity. In addition, when the security gap of the system increases, (1-PfB) and PfE will increase, and thus p0 will increase. Therefore, we can make Eve’s BER PeE approach 0.5 with faster speed by increasing the security gap of the system.


## 7. Simulation Results

In this section, we will evaluate the performance of our proposed scheme by Monte-Carlo simulations.Figure9 illustrates the number of secret key bits we can distill averagely from each transmitted source message bit. In the region with very low or very high Eb/N0, we can see that the number of secret key bits decreases. The reasons are as follows: in the region with very low Eb/N0, the retransmission happens frequently and the proportion of un-retransmitted source messages is small; in the region with very high Eb/N0, the BER of Eve is very low and therefore the number of secret key bits we can distill averagely from each source message bit is small. In addition, we can see that the more the channel of Eve is degraded compared to that of Bob, the more secret key bits we can distill.Figure 9
The number of secret key bits we can distill averagely from each transmitted source message bit using (2048, 1024) nonsystematic LDPC codes.In Figure10, the BER of Eve versus the number of transmitted source messages N for different security gaps Sg is plotted. We can see from Figure 8 that Bob’s BER will be lower than 10-6 in four conditions: r=0 and Eb/N0=2.2dB, r=1 and Eb/N0=1.7dB, r=2 and Eb/N0=1.5dB, or r=3 and Eb/N0=1.4dB. Therefore, to guarantee the reliability of the transmission (Pe,maxB<10-6), the quality of the main channel can be fixed to Eb/N0=1.7dB and the maximum transmission number can be fixed to r=1. For different security gaps, we can see that the BER of Eve will always approach 0.5 as the number of transmitted source messages increases. This is owing to the fact that the secret keys generated by Eve are the same as the keys generated by Alice and Bob before the first synchronization error happens. Therefore, she can recover the corresponding source messages successfully. After the first synchronization error happens, Eve can no longer decode the following source messages anymore, because the uncorrected decoding errors prevent her from generating the correct secret key. Thus, as the number of transmitted source messages increases, Eve’s average BER will approach 0.5.Figure 10
The BER of eavesdropper versus the number of transmitted source messages whenN=1,2,…,15000.In Figure11(a), the BER curves of Bob and Eve are plotted when N=1000 for different security gaps Sg. The maximum retransmission number is fixed to r=3. If Bob’s BER threshold is set to Pe,maxB<10-6 and Eve’s BER threshold is set to Pe,minE=0.49, the security gap Sg=0dB can be achieved. In Figure 11(b), the BER curves of Bob and Eve are plotted when N=10000. We can see that security gap Sg can be further reduced to lower than 0dB. It means that security of the source message can be guaranteed even when the wiretap channel is better than the main channel. We can see that the security gap performance of our scheme is really small and can be improved by increasing N.Figure 11
BER of our framework for Gaussian wiretap channel using (2048, 1024) nonsystematic LDPC codes for different security gaps whenN=1000 and N=10000 source message are transmitted with maximum retransmission number r=3.
(a) (b)


## 8. Conclusions

In this paper, we have proposed a secrecy transmission scheme based on code-hopping to encrypt and encode the source messages at the physical layer for wireless communications. First, we present a dynamic secret key generation algorithm based on ARQ mechanism. With this algorithm, Alice and Bob can distill the secret keys from the un-retransmitted source messages based on the universal hash families. Second, we present a structured-random LDPC codes design algorithm. Based on this algorithm, we generate a large amount of parity-check matrices of LDPC codes. During the transmission, Alice and Bob dynamically select the parity-check matrices of LDPC codes to encode and recover the source messages based on the dynamic secret keys. Theoretical analysis demonstrates that it is difficult for Eve to generate the same secret key as Alice and Bob. Simulation results show that the BER of Eve will approach 0.5 as the number of transmitted source messages increases and the security gap of our system is small.



---

*Source: 7063758-2018-04-03.xml*