# On Key Evolution over Wireless Channels

Authors: Zhihong Liu; Yong Zeng; Pingjuan Zhang; Qiping Huang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Noise is a powerful resource for the implementation of cryptographic primitives, especially in wireless networks. In general, a key agreement protocol is tailored to the channels and relies on the assumption that knowledge on the eavesdropper’s channel is available. This is not practical. In this paper, we focus on the problem of developing key agreement schemes for secure communication across wireless channels and propose a key evolution scheme to alleviate the assumption. Keys evolve continuously based on the transmitted messages over the noisy wireless channel. Even if the eavesdropper’s channel is superior to the legitimate receiver, the legitimate parties can establish secret keys. To further confuse the eavesdropper, we present a strategy for legitimate parties to send artificial noise if the eavesdropper cannot distinguish the sources of messages. Finally, we propose ak-resistant encryption scheme that can use different keys to encrypt and decrypt messages if there are no more than k bits which differ between the encryption and decryption keys.


---

## Body

## 1. Introduction

Traditionally, security in wireless channels is regarded as an independent feature addressed above the physical layer, and all widely used cryptographic protocols are designed and implemented assuming the physical layer has already been established. An alternative notion of communication security,information theoretic security, was introduced by Wyner [1] and later by Csiszar and Korner [2]. The basic principle of information theoretic security calls for the combination of cryptographic scheme with channel coding techniques that exploit the randomness of communication channels to guarantee that the messages sent cannot be decoded by a third party maliciously eavesdropping on the wireless channel. In a wiretap channel, the honest parties Alice and Bob are separated by a channel called the main channel; any eavesdropper Eve observes information transmitted by Alice through another channel called the wiretapper’s channel. Suppose Alice and Bob try to communicate a k-bit message M across the main channel; Alice encodes M into an n-bit codeword X. The legitimate receiver Bob and an eavesdropper Eve receive X through two different channels and their observations are denoted as Y and Z, respectively. Alice’s encoding should achieve two objectives: (1)security: Z should provide no information about M; (2)reliability: Y can be decoded into M with negligibly small probability of error. Wyner showed that both objectives can be attained if the channels satisfy some conditions. The advent of wireless communication, which is particularly susceptible to eavesdropping, has motivated a renewed interest for information theoretic security, which has recently emerged as a very active research area, such as in [3–13].The key distribution problem in wiretap channels has been studied in [14, 15]. The objective of key distribution is for Alice and Bob to agree on a common k-bit key about which Eve’s entropy is maximal. Most key agreement protocols require some level of interactive communications between Alice and Bob to arrive at a common yet secret key [14], where the exchange of information is by way of a parallel, error-free public channel between Alice and Bob used during the key agreement phase [16].In general, the lower bound of the eavesdropper’s equivocation about the key generated by a key agreement protocol is valid only if the protocol is tailored to the channels, which requires knowledge of the channel statistics. The assumption that the main channel is known is usually reasonable; however, it is hardly realistic to assume that the eavesdropper’s channel statistics are known exactly. In this paper, we propose a key evolution scheme which can alleviate the stringent requirement. The basic idea of key evolution is that keys evolve continuously based on the transmitted messages over the noisy wireless channel. If Eve cannot avoid at least a small bit error probability, her equivocation about the current key will be accumulated, and eventually she has no information about the new key. On the other hand, as the keys are continuously refreshed, the on-going cryptanalytic attacks can be thwarted. It also forces Eve to keep monitoring communications all the time after compromising a key; otherwise, she will lose control of it. We begin by discussing a special wiretap channel with a noiseless main channel and a binary symmetric channel (BSC) as the wiretapper’s channel and then extend it to a more generalized wiretap channel that have BSCs as both the main and wiretapper’s channel. We show that Alice and Bob can transform a wiretap channel that is advantageous to Eve into a channel in which Eve suffers more errors than Alice and Bob.Cooperative jamming techniques, by which one or more legitimate transmitters send jamming signals to increase the confusion of Eve, can be used to increase the secrecy capacity in multiuser channels [17, 18]. If Bob can impersonate Alice to send forged messages, Alice and Bob can exploit the reciprocity of the channel to their advantage to further confuse the eavesdropper. Finally, we propose a k-resistant encryption scheme (k-RES) that can use different keys to encrypt and decrypt messages. Consider that Alice and Bob use a symmetric encryption algorithm to exchange confidential messages, but some errors occur to Bob’s secret key during storage or transmission. In general, Bob cannot recover the message encrypted by Alice and they need to negotiate a new shared key. The objective of k-RES is to utilize the slightly different keys to encrypt a relatively small size message. If a pair of keys only has at most k-bit different, the receiver can recover the message; otherwise, he obtains no information about the message. In this setting, a k-RES can be viewed as a conceptual wiretap channel that has a main channel and a worse wiretap channel.Key evolution can be used in sensor networks. The large number of sensors makes it hard to change code or data stored in every sensor; it is much easier to mass-produce sensors that are identical even on fireware and data level and are deployed in batches. To secure the communication between sensors, they can use key evolution scheme to obtain a relatively secret key and refresh it as quickly as possible.


## 2. Preliminaries

Throughout the sequel, a random variableX induces a probability distribution P
X over an alphabet X. Random variables are denoted by capital letters. Furthermore, we let [
x
]
+
=
m
a
x
{
0
,
x
}. All logarithms in this paper are to base 2. The cardinality of a set S is denoted by S. H
(
X
) is the entropy function of a random variable X, and h
(
p
) is the binary entropy function defined as h
(
p
)
=
-
p
l
o
g
p
-
(
1
-
p
)
l
o
g
(
1
-
p
).In general wiretap channel, the main channel and the wiretap channel are discrete memoryless channels (DMCs). The main channel is denoted asX
→
Y, where X is a random variable denoting an input symbol to the main channel and Y is a random variable denoting an output symbol from the main channel. Similarly, the wiretapper’s channel is denoted as X
→
Z.The notion of secrecy introduced by Wyner [1] has an operational meaning of being the maximum possible rate of information transmission between Alice and Bob that still enables Eve to be kept totally ignorant. The secrecy capacity C
S for a wiretap channel can be calculated as follows [2]:(1)
C
S
=
m
a
x
V
→
X
→
Y
,
Z
I
V
;
Y
-
I
V
;
Z
+
,where the inner maximum is over all possible random variables V in joint distribution with X, Y, and Z such that V
→
X
→
(
Y
,
Z
) is a Markov chain.IfI
(
V
;
Y
)
≥
I
(
V
;
Z
) for all Markov chains V
→
X
→
(
Y
,
Z
), the main channel is said to be less noisy than the wiretap channel. If the main channel is less noisy than the wiretap channel, then(2)
C
S
=
m
a
x
P
X
x
I
X
;
Y
-
I
X
;
Z
,where the maximum is over all possible distributions P
X
(
x
) of X. If I
(
X
;
Y
) and I
(
X
;
Z
) are individually maximized by the same P
X
(
x
) and the main channel (
X
→
Y
) is less noisy than the wiretap channel (
X
→
Z
), then(3)
C
S
=
C
a
p
a
c
i
t
y
X
⟶
Y
-
C
a
p
a
c
i
t
y
X
⟶
Z
,where C
a
p
a
c
i
t
y
(
·
) refers to the usual channel capacity.


## 3. Key Evolution

### 3.1. Noiseless Main Channel and Binary Symmetric Wiretapper’s Channel WTC(
ϵ
=
0
,
δ
>
0
)

We begin with a simpler wiretap channel with a binary symmetric channel as the wiretapper’s channel and a noiseless main channel, that is, WTC(
ϵ
=
0
,
δ
>
0
).The heart of key evolution is a rekeying protocol that continuously refreshes the secret key based on transactional data. Let a message setM
=
[
1
,
2
n
]. Messages are represented by random variables M
1
,
…
,
M
i uniformly distributed in M. Suppose that Alice encodes message M
i
∈
{
0,1
}
n into codeword X
i
∈
{
0,1
}
n with key K
i
∈
{
0,1
}
n as a one-time pad:(4)
X
i
=
M
i
⊕
K
i
,and let K
1 be theinitial secret key shared between Alice and Bob. The key evolution protocol, C
K
E, can be illustrated as follows:(5)
M
1
,
M
X
1
=
M
1
⊕
K
1
,
M
K
1
=
0
M
1
,
M
X
1
=
M
1
⊕
K
1
,
M
K
2
=
K
1
+
M
1
M
2
,
M
X
2
=
M
2
⊕
K
2
,
M
K
3
=
K
2
+
M
2
M
3
,
M
X
3
=
M
3
⊕
K
3
,
M
K
4
=
K
3
+
M
3
⋮
M
⋮
M
000000000
0
⋮
M
i
,
M
X
i
=
M
i
⊕
K
i
,
M
K
i
+
1
=
K
i
+
M
i
⋮
M
⋮
M
000000000
0
⋮where K
1
=
0 means that Alice and Bob do not share any secret key initially; ⊕ denotes the bit-wise sum operation, and + is modulo addition with respect to the corresponding alphabet size.Remarks 1.
(
1
) In the key evolution protocol, Alice and Bob compute a new key K
i
+
1
=
K
i
+
M
i
=
M
1
+
⋯
+
M
i as a function of M
i
=
[
M
1
,
…
,
M
i
]. In general, any universal hash function G
:
K
i
×
M
i
→
K
i
+
1 can be chosen to compute the new key.
(
2
) As will be discussed later, under certain condition,(6)
H
M
1
∣
Z
1
≤
H
M
2
∣
Z
1
Z
2
≤
⋯
≤
H
M
i
∣
Z
1
,
…
,
Z
imeans that as more messages are transmitted, Eve’s equivocation on messages increases. From a practical perspective, before transmitting confidential messages, we could transmit some random messages to confuse Eve and generate a relatively secret key.
(
3
)  M
i is uniformly distributed over M and is independent of M
1
,
…
,
M
i
-
1. Based on the crypto lemma [19], K
i
=
M
1
+
⋯
+
M
i
-
1 is uniformly distributed over M.The objective of key evolution is for Alice and Bob to distill a secret key about which Eve has negligible information. Note that, ifK
1
=
0, X
1
=
M
1
⊕
K
1
=
M
1, and K
2
=
M
1
+
K
1
=
M
1, X
2
=
M
2
⊕
K
2
=
M
1
⊕
M
2. From Fano’s inequality, H
(
X
1
∣
Z
1
)
=
H
(
X
2
∣
Z
2
)
≤
n
h
(
δ
); that is, H
(
M
1
∣
Z
1
)
=
H
(
M
1
⊕
M
2
∣
Z
2
)
≤
n
h
(
δ
). Intuitively, H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
), which means that key evolution can increase Eve’s uncertainty about messages as more messages are transmitted. Before we investigate the key evolution protocol, we first show that H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
) is achievable under certain condition.Suppose Alice generates random bit stringsM
1 and M
2 and then transmits M
1 and the bit-wise sum M
1
⊕
M
2 over a noisy channel. The receiver, Eve, uses her observations Z
1 and Z
2 (with a and b bits errors, resp.) to recover M
1
,
M
2. The optimal strategy of Eve is to compute Z
1
⊕
Z
2 as the estimation of M
2.LetM
1
=
[
m
1
1
,
m
2
1
,
…
,
m
n
1
], M
1
⊕
M
2
=
[
m
1
2
,
m
2
2
,
…
,
m
n
2
], M
2
=
[
m
1
3
,
m
2
3
,
…
,
m
n
3
], and Z
1
⊕
Z
2
=
[
z
1
,
z
2
,
…
,
z
n
], where m
i
1, m
i
2, m
i
3, and z
i are the ith bit of M
1, M
1
⊕
M
2, M
2, and Z
1
⊕
Z
2, respectively. If m
i
1 in M
1 and m
i
2 in M
1
⊕
M
2 are correctly received, or both of them are error, then z
i
=
m
i
3, which means that Eve recovers the ith bit of M
2 successfully. Let A
i be a random variable that denotes the event that Eve can successfully recover the ith bit of message M
2. For a
,
b
≪
n, we use balls and bins model to estimate the probability P
(
A
i
) as follows:(7)
P
A
i
=
1
-
1
n
a
1
-
1
n
b
+
1
-
1
-
1
n
a
1
-
1
-
1
n
b
.ForP
(
A
-
i
)
=
1
-
P
(
A
i
), the expectation of A
-
i (the event that the ith bit of M
2 the receiver obtains is error) is(8)
E
A
-
i
=
1
-
P
A
i
.Therefore, the uncertainty ofM
2 on the condition of the observations Z
1 and Z
2 can be estimated as(9)
H
M
2
∣
Z
1
Z
2
M
=
n
E
A
-
i
=
n
1
-
1
-
1
n
a
1
-
1
n
b
M
M
M
M
M
M
M
M
-
1
-
1
-
1
n
a
1
-
1
-
1
n
b
M
=
n
1
-
1
n
a
+
1
-
1
n
b
-
2
1
-
1
n
a
1
-
1
n
b
.In the same way, we can estimateH
(
M
1
∣
Z
1
) as(10)
H
M
1
∣
Z
1
=
n
1
-
1
-
1
n
a
.LetΔ
=
H
(
M
2
∣
Z
1
Z
2
)
-
H
(
M
1
∣
Z
1
)
≥
0; we have(11)
2
1
-
1
n
a
-
1
≥
0
,so we obtain the result a
≤
1
/
l
o
g
n
/
n
-
1.IfX
1
=
M
1
⊕
K
1
=
M
1 is chosen uniformly at random, we have H
(
M
1
∣
Z
1
)
=
n
h
(
δ
). Additionally, since the receiver’s observation Z
1 has a-bit different from M
1, we can also represent the value H
(
M
1
∣
Z
1
) as H
(
M
1
∣
Z
1
)
=
n
h
(
δ
)
=
a. Therefore,(12)
a
=
n
h
δ
≤
1
l
o
g
n
/
n
-
1
.Letf
(
δ
)
=
1
/
l
o
g
n
/
n
-
1
-
n
h
(
δ
). If f
(
δ
)
>
0, H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
) holds. As expected, as long as δ is small, the function f
(
δ
) is positive, which implies H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
). For instance, if n
=
1000, f
(
δ
) is positive provided that 0
<
δ
<
0.1859; for n = 10,000, when 0
<
δ
<
0.1860, f
(
δ
)
>
0. Since the key obtained in the first round of key evolution is used as the one-time pad key for the sequence round, Eve’s uncertainty about the message transmitted will increase.BecauseH
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
) and M
1
,
…
,
M
i are independent and uniformly distributed over M, we can have the following result by similar derivation:(13)
H
M
i
∣
Z
1
,
…
,
Z
i
≤
H
M
i
+
1
∣
Z
1
,
…
,
Z
i
Z
i
+
1
.As to the key K
i, we exploit a hash function G to distill a secret key K
i
=
G
(
M
1
,
…
,
M
i
-
1
), where G is a hash function chosen uniformly at random from a universal family of hash function. Consequently, by virtue of (13), we can obtain(14)
H
K
i
∣
Z
1
,
…
,
Z
i
-
1
≤
H
K
i
+
1
∣
Z
1
,
…
,
Z
i
,which ensures that as more messages are transmitted, Eve gradually loses her ability to estimate the messages transmitted, as well as the keys distilled. In other words, for sufficiently large number of rounds of key evolution, we get an equivocation approximate to the entropy of the message as well as the entropy of the key.Next we want to analyze the secrecy performance of key evolution in terms of advantage distillation rate. Since hash functionG can be chosen arbitrarily, it is difficult to model and analyze C
K
E directly. We focus on a simpler protocol C
K
E
^ as follows:(15)
M
1
,
M
X
1
′
=
M
1
,
M
K
1
′
=
0
M
1
,
M
X
1
′
=
M
1
,
M
K
2
′
=
M
1
M
2
,
M
X
2
′
=
M
2
,
M
K
3
′
=
M
1
⊕
M
2
⋮
M
0
⋮
M
00000
⋮
M
i
,
M
X
i
′
=
M
i
,
M
K
i
+
1
′
=
M
1
⊕
⋯
⊕
M
i
⋮
M
0
⋮
M
0000
⋮InC
K
E
^, the main channel is noiseless, and the wiretapper’s channel is a binary symmetric channel with crossover probability δ
∈
(
0,1
). Alice generates message M
i and transmits X
i
′
=
M
i to Bob. The observations of Bob and Eve are Y
i
′
=
X
i
′
=
M
i and Z
i
′, respectively. The key is computed as K
i
′
=
M
1
⊕
⋯
⊕
M
i
-
1.Note that the wiretap channel inC
K
E
^ is discrete memoryless channel:(16)
H
M
1
∣
Z
1
′
=
H
M
2
∣
Z
2
′
=
⋯
=
H
M
i
∣
Z
i
′
.However, inC
K
E, we have H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
)
=
H
(
M
2
∣
Z
2
), for Z
1 and M
2 are independent of each other. Therefore,(17)
H
M
1
∣
Z
1
≤
H
M
2
∣
Z
2
≤
⋯
≤
H
M
i
∣
Z
i
.BecauseH
(
M
1
∣
Z
1
′
)
=
H
(
M
1
∣
Z
1
), then(18)
H
M
2
∣
Z
2
′
≤
H
M
2
∣
Z
2
,
H
M
3
∣
Z
3
′
≤
H
M
3
∣
Z
3
,
⋮
H
M
i
∣
Z
i
′
≤
H
M
i
∣
Z
i
.Notice thatM
1
,
M
2
,
…
,
M
i are mutually independent and uniformly distributed over M, so we can obtain(19)
H
M
1
,
…
,
M
i
-
1
∣
Z
1
′
,
…
,
Z
i
-
1
′
M
≤
H
M
1
,
…
,
M
i
-
1
∣
Z
1
,
…
,
Z
i
-
1
.For the secret key is a function ofM
1
,
M
2
,
…
,
M
i
-
1, that is, K
i
=
G
(
M
1
,
…
,
M
i
-
1
), we have(20)
H
K
i
′
∣
Z
1
′
,
…
,
Z
i
-
1
′
≤
H
K
i
∣
Z
1
,
…
,
Z
i
-
1
,which implies that the key evolution C
K
E has an advantage over the protocol C
K
E
^ in terms of the secrecy of key.The protocolC
K
E
^ can be viewed as an advantage distillation protocol; for example, Alice and Bob exchange messages over the public channel to process their observations and to “distill” observations for which they have an advantage over Eve. By repeating the process multiple times, Alice and Bob distill a new realization of the channels with components X
′, Y
′, and Z
′ with an advantage over Eve in the sense that(21)
I
X
′
;
Y
′
≥
I
X
′
;
Z
′
M
o
r
M
I
X
′
;
Y
′
≥
I
Y
′
;
Z
′
.Hence, it is natural to measure the performance of the protocol C
K
E
^ in terms of the quantity R
(
C
K
E
^
); that is,(22)
1
n
m
a
x
I
X
′
;
Y
′
-
I
X
′
;
Z
′
,
M
M
M
M
I
X
′
;
Y
′
-
I
Y
′
;
Z
′
,which is called the advantage distillation rate.InC
K
E
^, after t messages M
1
,
…
,
M
t have been exchanged, X
′
=
Y
′
=
{
X
1
′
,
…
,
X
t
′
}
=
{
M
1
,
…
,
M
t
}, Z
′
=
{
Z
1
′
,
…
,
Z
t
′
}, and K
t
=
M
1
⊕
⋯
⊕
M
t. Hence, the advantage distillation rate satisfies(23)
l
i
m
n
→
∞
R
C
K
E
^
M
=
l
i
m
n
→
∞
1
n
I
X
′
;
Y
′
-
I
X
′
;
Z
′
M
=
l
i
m
n
→
∞
1
n
H
X
′
∣
Z
′
M
=
t
·
h
δ
,for H
(
X
′
∣
Z
′
)
=
n
·
t
·
h
(
δ
), if M
1
,
…
,
M
t are chosen uniformly at random. Note that, on choosing t large enough (t
>
1
/
h
(
δ
)), the protocol achieves an advantage distillation rate of approximately 1. However, if δ is quite low, the advantage distillation rate is relatively low. On the other hand, we can also estimate the equivocation of key K
t in terms of(24)
E
C
K
E
^
M
=
l
i
m
n
→
∞
1
n
H
K
t
∣
Z
1
′
,
…
,
Z
t
′
M
≈
a
l
i
m
n
→
∞
1
n
n
1
-
1
-
1
n
n
t
δ
M
≈
b
t
δ
.Here, (a) holds because the optimal strategy for Eve to guess K
t
=
M
1
⊕
⋯
⊕
M
t is to compute Z
^
=
Z
1
′
⊕
⋯
⊕
Z
t
′. For each Z
i
′ differs from M
i in n
δ positions on average, by balls and bins model, Z
^ has about n
[
1
-
(
1
-
1
/
n
)
n
t
δ
] different positions from K
t. So we have H
(
K
t
∣
Z
1
′
,
…
,
Z
t
′
)
=
n
[
1
-
(
1
-
1
/
n
)
n
t
δ
]; (b) follows from 1
-
(
1
-
1
/
n
)
x
→
x
/
n as n
→
∞.Remark 2.
E
(
C
K
E
^
)
≈
t
δ means that Eve can get approximately no information about K
t as t is large enough (t
>
1
/
δ).


### 3.2. Noisy Main Channel and Wiretapper’s Channel WTC(
ϵ
>
0
,
δ
>
0
)

In this subsection, we consider a realistic wireless communication system where both the wiretapper’s channel and the main channel are BSCs. More specifically, the wiretapper’s channel is a BSC with crossover probabilityδ, and the main channel is another BSC with crossover probability ϵ.As discussed in Section3.1, if the main channel is noiseless, Bob can receive messages sent by Alice without any bit error and refresh their secret key in the same way as Alice does. If the main channel is noisy, Alice and Bob can use an appropriate error-detecting code C and a repeating transmission strategy to alleviate the transmission error. Consider now Alice sending X
i
=
(
M
i
,
C
i
) to Bob over the noisy channel, where M
i is the message to be sent and C
i is the error-detecting code of M
i. If a transmission error is detected, Alice retransmits it again until Bob receives the message correctly.Assume the length of a message isn bits. The probability that a message is received correctly by Bob is (
1
-
ϵ
)
n. Let random variable T be the number of transmissions required until the message is correctly received by Bob; T is a geometric random variable with parameter p
=
(
1
-
ϵ
)
n. Its probability mass function is(25)
P
T
=
i
=
1
-
1
-
ϵ
n
i
-
1
1
-
ϵ
n
,
i
=
1,2
,
…
,and its expectation is(26)
t
=
E
T
=
1
1
-
ϵ
n
.Eve, on the other hand, eavesdrops messages sent by Alice via the wiretapper’s channel with bit error probabilityδ. The probability that a message is correctly eavesdropped by Eve is (
1
-
δ
)
n. If Alice retransmits a message M to Bob t times, Eve will get t noisy versions of the message M over the wiretapper’s channel. Hence, the probability P
(
t
) that a message is correctly eavesdropped by Eve after it is retransmitted t times is(27)
P
t
=
1
-
1
-
1
-
δ
n
t
.The main channel from Alice to Bob may be viewed as a noiseless channel after the message is transmittedt times, since after t times of retransmission on average Bob will get the message correctly; the wiretapper’s channel thus corresponds to a BSC with bit error probability δ
′ which satisfies(28)
1
-
δ
′
n
=
1
-
1
-
1
-
δ
n
t
.Therefore,(29)
δ
′
=
1
-
1
-
1
-
1
-
δ
n
t
1
/
n
,where t
=
1
/
(
1
-
ϵ
)
n.Obviously,δ
′
<
δ, which means a WTC (ϵ
>
0, δ
>
0) can be transformed into a WTC (ϵ
=
0, δ
′
>
0) with a noiseless conceptual main channel and a conceptual wiretapper’s channel with smaller bit error probability δ
′
<
δ. Even when the wiretapper’s channel is much more reliable than the main channel, Eve cannot avoid at least a small bit error probability.Examples 3.
Assumen
=
10000 and ϵ
=
1
×
1
0
-
4. When δ
=
1
×
1
0
-
4, then δ
′
=
3.3887
×
1
0
-
5; when δ
=
1
×
1
0
-
3, δ
′
=
9.0009
×
1
0
-
4; when δ
=
1
×
1
0
-
5, δ
′
=
1.6727
×
1
0
-
7.However, for each messagem, Eve can get t
=
1
/
(
1
-
ϵ
)
n received strings, the noisy versions of the message m. Any n-bit string can be reconstructed with high probability by using sufficient traces [20]. In a BSC with bit error probability δ, to reconstruct an unknown sequence x
=
(
x
1
,
…
,
x
n
)
∈
{
0,1
,
…
,
q
-
1
}
n when knowing N different sequences y
1
,
…
,
y
N
∈
{
0,1
,
…
,
q
-
1
}
n, where each of which differs from x in at most k components, the minimum number N equals(30)
N
=
q
∑
i
=
1
k
-
1
n
-
1
i
q
-
1
i
+
1
.Therefore, if Eve has eavesdroppedN different traces of message m and satisfies the condition(31)
1
1
-
ϵ
n
<
∑
i
=
1
k
-
1
n
-
1
i
+
1
,
w
h
e
r
e
k
≃
n
δ
,then Eve cannot reconstruct the message with high probability.


## 3.1. Noiseless Main Channel and Binary Symmetric Wiretapper’s Channel WTC(
ϵ
=
0
,
δ
>
0
)

We begin with a simpler wiretap channel with a binary symmetric channel as the wiretapper’s channel and a noiseless main channel, that is, WTC(
ϵ
=
0
,
δ
>
0
).The heart of key evolution is a rekeying protocol that continuously refreshes the secret key based on transactional data. Let a message setM
=
[
1
,
2
n
]. Messages are represented by random variables M
1
,
…
,
M
i uniformly distributed in M. Suppose that Alice encodes message M
i
∈
{
0,1
}
n into codeword X
i
∈
{
0,1
}
n with key K
i
∈
{
0,1
}
n as a one-time pad:(4)
X
i
=
M
i
⊕
K
i
,and let K
1 be theinitial secret key shared between Alice and Bob. The key evolution protocol, C
K
E, can be illustrated as follows:(5)
M
1
,
M
X
1
=
M
1
⊕
K
1
,
M
K
1
=
0
M
1
,
M
X
1
=
M
1
⊕
K
1
,
M
K
2
=
K
1
+
M
1
M
2
,
M
X
2
=
M
2
⊕
K
2
,
M
K
3
=
K
2
+
M
2
M
3
,
M
X
3
=
M
3
⊕
K
3
,
M
K
4
=
K
3
+
M
3
⋮
M
⋮
M
000000000
0
⋮
M
i
,
M
X
i
=
M
i
⊕
K
i
,
M
K
i
+
1
=
K
i
+
M
i
⋮
M
⋮
M
000000000
0
⋮where K
1
=
0 means that Alice and Bob do not share any secret key initially; ⊕ denotes the bit-wise sum operation, and + is modulo addition with respect to the corresponding alphabet size.Remarks 1.
(
1
) In the key evolution protocol, Alice and Bob compute a new key K
i
+
1
=
K
i
+
M
i
=
M
1
+
⋯
+
M
i as a function of M
i
=
[
M
1
,
…
,
M
i
]. In general, any universal hash function G
:
K
i
×
M
i
→
K
i
+
1 can be chosen to compute the new key.
(
2
) As will be discussed later, under certain condition,(6)
H
M
1
∣
Z
1
≤
H
M
2
∣
Z
1
Z
2
≤
⋯
≤
H
M
i
∣
Z
1
,
…
,
Z
imeans that as more messages are transmitted, Eve’s equivocation on messages increases. From a practical perspective, before transmitting confidential messages, we could transmit some random messages to confuse Eve and generate a relatively secret key.
(
3
)  M
i is uniformly distributed over M and is independent of M
1
,
…
,
M
i
-
1. Based on the crypto lemma [19], K
i
=
M
1
+
⋯
+
M
i
-
1 is uniformly distributed over M.The objective of key evolution is for Alice and Bob to distill a secret key about which Eve has negligible information. Note that, ifK
1
=
0, X
1
=
M
1
⊕
K
1
=
M
1, and K
2
=
M
1
+
K
1
=
M
1, X
2
=
M
2
⊕
K
2
=
M
1
⊕
M
2. From Fano’s inequality, H
(
X
1
∣
Z
1
)
=
H
(
X
2
∣
Z
2
)
≤
n
h
(
δ
); that is, H
(
M
1
∣
Z
1
)
=
H
(
M
1
⊕
M
2
∣
Z
2
)
≤
n
h
(
δ
). Intuitively, H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
), which means that key evolution can increase Eve’s uncertainty about messages as more messages are transmitted. Before we investigate the key evolution protocol, we first show that H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
) is achievable under certain condition.Suppose Alice generates random bit stringsM
1 and M
2 and then transmits M
1 and the bit-wise sum M
1
⊕
M
2 over a noisy channel. The receiver, Eve, uses her observations Z
1 and Z
2 (with a and b bits errors, resp.) to recover M
1
,
M
2. The optimal strategy of Eve is to compute Z
1
⊕
Z
2 as the estimation of M
2.LetM
1
=
[
m
1
1
,
m
2
1
,
…
,
m
n
1
], M
1
⊕
M
2
=
[
m
1
2
,
m
2
2
,
…
,
m
n
2
], M
2
=
[
m
1
3
,
m
2
3
,
…
,
m
n
3
], and Z
1
⊕
Z
2
=
[
z
1
,
z
2
,
…
,
z
n
], where m
i
1, m
i
2, m
i
3, and z
i are the ith bit of M
1, M
1
⊕
M
2, M
2, and Z
1
⊕
Z
2, respectively. If m
i
1 in M
1 and m
i
2 in M
1
⊕
M
2 are correctly received, or both of them are error, then z
i
=
m
i
3, which means that Eve recovers the ith bit of M
2 successfully. Let A
i be a random variable that denotes the event that Eve can successfully recover the ith bit of message M
2. For a
,
b
≪
n, we use balls and bins model to estimate the probability P
(
A
i
) as follows:(7)
P
A
i
=
1
-
1
n
a
1
-
1
n
b
+
1
-
1
-
1
n
a
1
-
1
-
1
n
b
.ForP
(
A
-
i
)
=
1
-
P
(
A
i
), the expectation of A
-
i (the event that the ith bit of M
2 the receiver obtains is error) is(8)
E
A
-
i
=
1
-
P
A
i
.Therefore, the uncertainty ofM
2 on the condition of the observations Z
1 and Z
2 can be estimated as(9)
H
M
2
∣
Z
1
Z
2
M
=
n
E
A
-
i
=
n
1
-
1
-
1
n
a
1
-
1
n
b
M
M
M
M
M
M
M
M
-
1
-
1
-
1
n
a
1
-
1
-
1
n
b
M
=
n
1
-
1
n
a
+
1
-
1
n
b
-
2
1
-
1
n
a
1
-
1
n
b
.In the same way, we can estimateH
(
M
1
∣
Z
1
) as(10)
H
M
1
∣
Z
1
=
n
1
-
1
-
1
n
a
.LetΔ
=
H
(
M
2
∣
Z
1
Z
2
)
-
H
(
M
1
∣
Z
1
)
≥
0; we have(11)
2
1
-
1
n
a
-
1
≥
0
,so we obtain the result a
≤
1
/
l
o
g
n
/
n
-
1.IfX
1
=
M
1
⊕
K
1
=
M
1 is chosen uniformly at random, we have H
(
M
1
∣
Z
1
)
=
n
h
(
δ
). Additionally, since the receiver’s observation Z
1 has a-bit different from M
1, we can also represent the value H
(
M
1
∣
Z
1
) as H
(
M
1
∣
Z
1
)
=
n
h
(
δ
)
=
a. Therefore,(12)
a
=
n
h
δ
≤
1
l
o
g
n
/
n
-
1
.Letf
(
δ
)
=
1
/
l
o
g
n
/
n
-
1
-
n
h
(
δ
). If f
(
δ
)
>
0, H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
) holds. As expected, as long as δ is small, the function f
(
δ
) is positive, which implies H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
). For instance, if n
=
1000, f
(
δ
) is positive provided that 0
<
δ
<
0.1859; for n = 10,000, when 0
<
δ
<
0.1860, f
(
δ
)
>
0. Since the key obtained in the first round of key evolution is used as the one-time pad key for the sequence round, Eve’s uncertainty about the message transmitted will increase.BecauseH
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
) and M
1
,
…
,
M
i are independent and uniformly distributed over M, we can have the following result by similar derivation:(13)
H
M
i
∣
Z
1
,
…
,
Z
i
≤
H
M
i
+
1
∣
Z
1
,
…
,
Z
i
Z
i
+
1
.As to the key K
i, we exploit a hash function G to distill a secret key K
i
=
G
(
M
1
,
…
,
M
i
-
1
), where G is a hash function chosen uniformly at random from a universal family of hash function. Consequently, by virtue of (13), we can obtain(14)
H
K
i
∣
Z
1
,
…
,
Z
i
-
1
≤
H
K
i
+
1
∣
Z
1
,
…
,
Z
i
,which ensures that as more messages are transmitted, Eve gradually loses her ability to estimate the messages transmitted, as well as the keys distilled. In other words, for sufficiently large number of rounds of key evolution, we get an equivocation approximate to the entropy of the message as well as the entropy of the key.Next we want to analyze the secrecy performance of key evolution in terms of advantage distillation rate. Since hash functionG can be chosen arbitrarily, it is difficult to model and analyze C
K
E directly. We focus on a simpler protocol C
K
E
^ as follows:(15)
M
1
,
M
X
1
′
=
M
1
,
M
K
1
′
=
0
M
1
,
M
X
1
′
=
M
1
,
M
K
2
′
=
M
1
M
2
,
M
X
2
′
=
M
2
,
M
K
3
′
=
M
1
⊕
M
2
⋮
M
0
⋮
M
00000
⋮
M
i
,
M
X
i
′
=
M
i
,
M
K
i
+
1
′
=
M
1
⊕
⋯
⊕
M
i
⋮
M
0
⋮
M
0000
⋮InC
K
E
^, the main channel is noiseless, and the wiretapper’s channel is a binary symmetric channel with crossover probability δ
∈
(
0,1
). Alice generates message M
i and transmits X
i
′
=
M
i to Bob. The observations of Bob and Eve are Y
i
′
=
X
i
′
=
M
i and Z
i
′, respectively. The key is computed as K
i
′
=
M
1
⊕
⋯
⊕
M
i
-
1.Note that the wiretap channel inC
K
E
^ is discrete memoryless channel:(16)
H
M
1
∣
Z
1
′
=
H
M
2
∣
Z
2
′
=
⋯
=
H
M
i
∣
Z
i
′
.However, inC
K
E, we have H
(
M
1
∣
Z
1
)
≤
H
(
M
2
∣
Z
1
Z
2
)
=
H
(
M
2
∣
Z
2
), for Z
1 and M
2 are independent of each other. Therefore,(17)
H
M
1
∣
Z
1
≤
H
M
2
∣
Z
2
≤
⋯
≤
H
M
i
∣
Z
i
.BecauseH
(
M
1
∣
Z
1
′
)
=
H
(
M
1
∣
Z
1
), then(18)
H
M
2
∣
Z
2
′
≤
H
M
2
∣
Z
2
,
H
M
3
∣
Z
3
′
≤
H
M
3
∣
Z
3
,
⋮
H
M
i
∣
Z
i
′
≤
H
M
i
∣
Z
i
.Notice thatM
1
,
M
2
,
…
,
M
i are mutually independent and uniformly distributed over M, so we can obtain(19)
H
M
1
,
…
,
M
i
-
1
∣
Z
1
′
,
…
,
Z
i
-
1
′
M
≤
H
M
1
,
…
,
M
i
-
1
∣
Z
1
,
…
,
Z
i
-
1
.For the secret key is a function ofM
1
,
M
2
,
…
,
M
i
-
1, that is, K
i
=
G
(
M
1
,
…
,
M
i
-
1
), we have(20)
H
K
i
′
∣
Z
1
′
,
…
,
Z
i
-
1
′
≤
H
K
i
∣
Z
1
,
…
,
Z
i
-
1
,which implies that the key evolution C
K
E has an advantage over the protocol C
K
E
^ in terms of the secrecy of key.The protocolC
K
E
^ can be viewed as an advantage distillation protocol; for example, Alice and Bob exchange messages over the public channel to process their observations and to “distill” observations for which they have an advantage over Eve. By repeating the process multiple times, Alice and Bob distill a new realization of the channels with components X
′, Y
′, and Z
′ with an advantage over Eve in the sense that(21)
I
X
′
;
Y
′
≥
I
X
′
;
Z
′
M
o
r
M
I
X
′
;
Y
′
≥
I
Y
′
;
Z
′
.Hence, it is natural to measure the performance of the protocol C
K
E
^ in terms of the quantity R
(
C
K
E
^
); that is,(22)
1
n
m
a
x
I
X
′
;
Y
′
-
I
X
′
;
Z
′
,
M
M
M
M
I
X
′
;
Y
′
-
I
Y
′
;
Z
′
,which is called the advantage distillation rate.InC
K
E
^, after t messages M
1
,
…
,
M
t have been exchanged, X
′
=
Y
′
=
{
X
1
′
,
…
,
X
t
′
}
=
{
M
1
,
…
,
M
t
}, Z
′
=
{
Z
1
′
,
…
,
Z
t
′
}, and K
t
=
M
1
⊕
⋯
⊕
M
t. Hence, the advantage distillation rate satisfies(23)
l
i
m
n
→
∞
R
C
K
E
^
M
=
l
i
m
n
→
∞
1
n
I
X
′
;
Y
′
-
I
X
′
;
Z
′
M
=
l
i
m
n
→
∞
1
n
H
X
′
∣
Z
′
M
=
t
·
h
δ
,for H
(
X
′
∣
Z
′
)
=
n
·
t
·
h
(
δ
), if M
1
,
…
,
M
t are chosen uniformly at random. Note that, on choosing t large enough (t
>
1
/
h
(
δ
)), the protocol achieves an advantage distillation rate of approximately 1. However, if δ is quite low, the advantage distillation rate is relatively low. On the other hand, we can also estimate the equivocation of key K
t in terms of(24)
E
C
K
E
^
M
=
l
i
m
n
→
∞
1
n
H
K
t
∣
Z
1
′
,
…
,
Z
t
′
M
≈
a
l
i
m
n
→
∞
1
n
n
1
-
1
-
1
n
n
t
δ
M
≈
b
t
δ
.Here, (a) holds because the optimal strategy for Eve to guess K
t
=
M
1
⊕
⋯
⊕
M
t is to compute Z
^
=
Z
1
′
⊕
⋯
⊕
Z
t
′. For each Z
i
′ differs from M
i in n
δ positions on average, by balls and bins model, Z
^ has about n
[
1
-
(
1
-
1
/
n
)
n
t
δ
] different positions from K
t. So we have H
(
K
t
∣
Z
1
′
,
…
,
Z
t
′
)
=
n
[
1
-
(
1
-
1
/
n
)
n
t
δ
]; (b) follows from 1
-
(
1
-
1
/
n
)
x
→
x
/
n as n
→
∞.Remark 2.
E
(
C
K
E
^
)
≈
t
δ means that Eve can get approximately no information about K
t as t is large enough (t
>
1
/
δ).


## 3.2. Noisy Main Channel and Wiretapper’s Channel WTC(
ϵ
>
0
,
δ
>
0
)

In this subsection, we consider a realistic wireless communication system where both the wiretapper’s channel and the main channel are BSCs. More specifically, the wiretapper’s channel is a BSC with crossover probabilityδ, and the main channel is another BSC with crossover probability ϵ.As discussed in Section3.1, if the main channel is noiseless, Bob can receive messages sent by Alice without any bit error and refresh their secret key in the same way as Alice does. If the main channel is noisy, Alice and Bob can use an appropriate error-detecting code C and a repeating transmission strategy to alleviate the transmission error. Consider now Alice sending X
i
=
(
M
i
,
C
i
) to Bob over the noisy channel, where M
i is the message to be sent and C
i is the error-detecting code of M
i. If a transmission error is detected, Alice retransmits it again until Bob receives the message correctly.Assume the length of a message isn bits. The probability that a message is received correctly by Bob is (
1
-
ϵ
)
n. Let random variable T be the number of transmissions required until the message is correctly received by Bob; T is a geometric random variable with parameter p
=
(
1
-
ϵ
)
n. Its probability mass function is(25)
P
T
=
i
=
1
-
1
-
ϵ
n
i
-
1
1
-
ϵ
n
,
i
=
1,2
,
…
,and its expectation is(26)
t
=
E
T
=
1
1
-
ϵ
n
.Eve, on the other hand, eavesdrops messages sent by Alice via the wiretapper’s channel with bit error probabilityδ. The probability that a message is correctly eavesdropped by Eve is (
1
-
δ
)
n. If Alice retransmits a message M to Bob t times, Eve will get t noisy versions of the message M over the wiretapper’s channel. Hence, the probability P
(
t
) that a message is correctly eavesdropped by Eve after it is retransmitted t times is(27)
P
t
=
1
-
1
-
1
-
δ
n
t
.The main channel from Alice to Bob may be viewed as a noiseless channel after the message is transmittedt times, since after t times of retransmission on average Bob will get the message correctly; the wiretapper’s channel thus corresponds to a BSC with bit error probability δ
′ which satisfies(28)
1
-
δ
′
n
=
1
-
1
-
1
-
δ
n
t
.Therefore,(29)
δ
′
=
1
-
1
-
1
-
1
-
δ
n
t
1
/
n
,where t
=
1
/
(
1
-
ϵ
)
n.Obviously,δ
′
<
δ, which means a WTC (ϵ
>
0, δ
>
0) can be transformed into a WTC (ϵ
=
0, δ
′
>
0) with a noiseless conceptual main channel and a conceptual wiretapper’s channel with smaller bit error probability δ
′
<
δ. Even when the wiretapper’s channel is much more reliable than the main channel, Eve cannot avoid at least a small bit error probability.Examples 3.
Assumen
=
10000 and ϵ
=
1
×
1
0
-
4. When δ
=
1
×
1
0
-
4, then δ
′
=
3.3887
×
1
0
-
5; when δ
=
1
×
1
0
-
3, δ
′
=
9.0009
×
1
0
-
4; when δ
=
1
×
1
0
-
5, δ
′
=
1.6727
×
1
0
-
7.However, for each messagem, Eve can get t
=
1
/
(
1
-
ϵ
)
n received strings, the noisy versions of the message m. Any n-bit string can be reconstructed with high probability by using sufficient traces [20]. In a BSC with bit error probability δ, to reconstruct an unknown sequence x
=
(
x
1
,
…
,
x
n
)
∈
{
0,1
,
…
,
q
-
1
}
n when knowing N different sequences y
1
,
…
,
y
N
∈
{
0,1
,
…
,
q
-
1
}
n, where each of which differs from x in at most k components, the minimum number N equals(30)
N
=
q
∑
i
=
1
k
-
1
n
-
1
i
q
-
1
i
+
1
.Therefore, if Eve has eavesdroppedN different traces of message m and satisfies the condition(31)
1
1
-
ϵ
n
<
∑
i
=
1
k
-
1
n
-
1
i
+
1
,
w
h
e
r
e
k
≃
n
δ
,then Eve cannot reconstruct the message with high probability.


## 4. Artificial Noise to Confuse Adversaries

Cooperative jamming, or artificial noise [17, 18], by which one or more legitimate transmitters send jamming signals to increase the confusion of the adversaries, can be used effectively to increase the secrecy capacity in multiuser channels.Along this line, if Bob can impersonate Alice to send forged messages and Eve cannot distinguish the sources of messages, Bob can cause further confusion of Eve. Eve receives a mixture of messages from Alice and forged messages from Bob. From her perspective, every message is equally likely and she cannot do better than randomly guessing the sources of each message.For simplicity, letϵ
=
δ
=
0. If Alice has transmitted i messages M
=
{
M
1
,
…
,
M
i
} and Bob has injected j forged messages M
-
=
{
M
-
1
,
…
,
M
-
j
}, the legitimate parties can distill a secret key K
=
M
1
+
⋯
+
M
i. Let t
=
i
+
j; Eve has to guess K out of T
=
∑
k
=
1
t
t
k alternative keys. For instance, if t
=
3 and i
=
1, T
=
9, Eve only has to guess 9 times to get the secret keys, that is, H
(
K
∣
M
M
-
)
=
l
o
g
9 bits. Hence, it is natural to increase T to enhance the security.ForT
=
∑
k
=
1
t
t
k
=
2
t
-
1,(32)
H
K
∣
M
M
-
=
l
o
g
2
t
-
1
≈
t
.Therefore, if t
>
n and the forged messages M
- are distributed uniformly among all messages M
+
M
-, the secret key is perfect secret.For some cases, Eve may not choose all subset of messages received to construct secret keys. Without loss of optimality she can choose all subset of messages whose cardinality is less thant
/
2 if she knows apriori that there are at most t
/
2 forged messages in M
+
M
-. For example, if i
=
M
=
1, she can obtain the secret key with probability 1
/
t; that is, H
(
K
∣
M
M
-
)
=
l
o
g
t.For simplicity, leti
≤
t
/
3, T
i
=
∑
k
=
1
i
t
k
<
n. It is straightforward that n
i
-
1
=
i
/
n
-
i
+
1
n
i and therefore n
i
-
1
<
1
/
2
n
i for i
≤
n
/
3. This implies n
i
-
j
<
2
j
n
i for i
≤
n
/
3 and 0
≤
j
≤
i, from which the bound(33)
∑
i
=
1
k
n
i
<
n
k
∑
i
=
1
k
2
-
i
<
2
n
k
,for any k
≤
n
/
3, holds. The approximation of n
i, by the binary entropy function(34)
1
8
i
1
-
i
/
n
≤
n
i
2
-
n
h
i
/
n
≤
1
π
i
1
-
i
/
n
,implies that 1
/
3
n
2
n
h
i
/
n
≤
n
i
≤
2
n
h
(
i
/
n
) for i
≤
n
/
3. Thus,(35)
∑
i
=
1
k
n
i
<
2
n
k
≤
2
·
2
n
h
i
/
n
=
2
n
h
i
/
n
+
1
.By applying result (35), we have(36)
T
i
=
∑
k
=
1
i
t
k
<
2
t
h
i
/
t
+
1
.Therefore,(37)
H
K
∣
M
M
-
<
l
o
g
T
i
<
t
h
i
t
+
1
.In general, Bob’s optimal strategy to generate noise is to injectj forged messages M
-
1
,
…
,
M
-
j into messages M
1
,
…
,
M
i uniformly and let i
=
j on average. Consequently, on reception of a message M
i from Alice, Bob chooses a random value q
∈
(
2
,
t
) and generates F forged messages, where F is a random variable, taking on one of the values 0,1
,
2
,
…
,
t
-
1 and P
{
F
=
i
}
=
1
/
q for i
=
0,1
,
2
,
…
,
t
-
1.


## 5.k-Resistant Encryption

Symmetric encryption algorithm uses a secret key shared between the legitimate parties to encrypt and decrypt messages. If some bit errors occur to the secret key held by one of parties, we have to discard it and negotiate a new secret key. Unlike a symmetric encryption scheme, in which the legitimate parties are in possession of a shared secret key, ak-resistant encryption scheme (k-RES) uses different keys to encrypt and decrypt messages provided there are at most k discrepancies of n-bit between two keys.


### 5.1. Problem Description

LetV
=
{
0,1
} and let V
n be the set of n-tuples over V; that is,(38)
V
n
=
x
1
,
x
2
,
…
,
x
n
∣
x
i
∈
V
,
i
=
1,2
,
…
,
n
.For X
=
[
x
1
,
x
2
,
…
,
x
n
]
∈
V
n and Y
=
[
y
1
,
y
2
,
…
,
y
n
]
∈
V
n, the Hamming distance d
H
(
X
,
Y
) between X and Y is the number of coordinates in which they differ; that is, d
H
(
X
,
Y
)
=
{
i
∣
x
i
≠
y
i
}.Formally, ak-resistant encryption scheme (k-RES) is defined as follows.Definition 4 (k-resistant encryption scheme).
An encryption scheme is calledk-resistant if the following conditions are satisfied.(1)
Decodable Condition. Alice encrypts a plaintext message M
∈
{
0,1
}
m to a ciphertext C
∈
{
0,1
}
q using her secret key K
A
∈
{
0,1
}
n (n
>
m), and Bob can decrypt C with his key K
B
∈
{
0,1
}
nif there are at most k bits which differ between K
A and K
B; that is,(39)
H
M
∣
K
A
C
=
H
M
∣
K
B
C
=
0
ifd
H
(
K
A
,
K
B
)
≤
k
.
(2)
Security Condition. Eve can only obtain a negligible amount of information about M if her key K
E satisfies d
H
(
K
A
,
K
E
)
>
k; that is,(40)
H
M
∣
K
E
C
=
H
M
M
i
f
d
H
K
A
,
K
E
>
k
.The decodable condition guarantees that anyone with a keyK satisfying d
H
(
K
A
,
K
)
≤
k can recover the message. The security condition, on the other hand, ensures that Eve can obtain no information about the message if d
H
(
K
A
,
K
E
)
>
k.Intuitively, ak-RES can be viewed as a wiretap channel in which Alice sends secret information to Bob virtually in the main channel, and the adversary Eve receives Alice’s output through an independent wiretapper channel.To send a messageX to Bob, Alice sends X
⊕
K
A instead. Bob computes Y
=
X
⊕
K
A
⊕
K
B and thus obtains X with error pattern K
A
⊕
K
B and bit error probability ϵ
=
a
/
n for d
H
(
K
A
,
K
B
)
=
a. Eve, on the other hand, can compute Z
=
X
⊕
K
A
⊕
K
E, which is equivalent to receiving X over a wiretapper’s channel with bit error probability δ
=
b
/
n (for d
H
(
K
A
,
K
E
)
=
b). Thus, the bit error probabilities of the conceptual main channel and Eve’s conceptual channel are ϵ
=
a
/
n and δ
=
b
/
n, respectively. Because a
≤
k and b
>
k, then ϵ
<
δ, which implies that the main channel is less noisy than the wiretapper’s channel; therefore, the secrecy capacity C
S of the conceptual wiretap channel [2](41)
C
S
=
m
a
x
P
X
x
I
X
;
Y
-
I
X
;
Z
.It was further shown in [21] that if I
(
X
;
Y
) and I
(
X
;
Z
) are individually maximized by the same P
X
(
x
), and the main channel is less noisy than the wiretapper’s channel, C
S
=
C
a
p
a
c
i
t
y
(
X
→
Y
)
-
C
a
p
a
c
i
t
y
(
X
→
Z
). Consider a k-RES; it can be viewed as a broadcast channel in which the main channel and the wiretapper’s channel are binary symmetric channels with bit error probabilities ϵ and δ, respectively, and ϵ
<
δ. The secrecy capacity is C
S
=
h
(
δ
)
-
h
(
ϵ
)
.Suppose Alice and Bob try to securely communicate am-bit message M across the main channel; Alice encodes M
∈
{
0,1
}
m into an n-bit word X
∈
{
0,1
}
n. We have(42)
m
n
=
C
S
=
h
δ
-
h
ϵ
,and then(43)
m
=
n
h
δ
-
h
ϵ
=
n
h
b
n
-
h
a
n
.Notice thatk
<
b
≤
n
/
2, h
(
k
/
n
)
<
h
(
b
/
n
); we have(44)
m
>
n
h
k
n
-
h
a
n
.The secrecy capacity ofk-RES depends on parameters a and k. The less the value d
H
(
K
A
,
K
B
)
=
a is, the more the information can be encrypted. On the other hand, there are situations in which the bound is tighter. If we know the value b exactly, we can get the upper bound of m; that is, m
≤
n
[
h
(
b
/
n
)
-
h
(
a
/
n
)
], since h
(
δ
)
-
h
(
ϵ
) is the upper bound of C
S.


### 5.2. Construction Methods

A trivialk-RES can be constructed by a classic error-correcting code. We can choose (n, m) error-correcting code, which maps a message M
∈
{
0,1
}
m to a codeword C
∈
{
0,1
}
n and can correct at most k-bit errors. In order to encrypt a message M of m-bit, Alice transmits C
⊕
K
A to Bob. Bob computes C
-
=
C
⊕
K
A
⊕
K
B which differs from C in d
H
(
K
A
,
K
B
) bits. If d
H
(
K
A
,
K
B
)
<
k, Bob can correct the errors and recover the message M.Eve, on the other hand, cannot get the message correctly, since what she can obtain isC
^
=
C
⊕
K
A
⊕
K
E which differs from C in d
H
(
K
A
,
K
E
)
>
k bits.Next we estimate the amount of information that this solution ofk-RES can handle. In general, a linear (n
,
m) block code, such as Hamming code, which can correct k-bit errors should satisfy the following bound:(45)
n
-
m
≥
l
o
g
∑
i
=
0
k
n
i
.Hence, ifk
≪
n, n
k
-
1
<
n
k, and 2
n
k
>
∑
i
=
1
k
n
i
>
n
k, we obtain(46)
m
≤
n
-
l
o
g
∑
i
=
0
k
n
i
<
n
-
l
o
g
n
k
≈
a
n
-
n
h
k
n
=
n
1
-
h
k
n
,where (a) follows from n
k
~
2
n
h
(
k
/
n
) for k
≪
n.This solution can be used to constructk-RES when few errors are more likely to occur. The error-correcting code may also give some side information to Eve. From a practical perspective, the design of a k-RES turns out to be a problem of the construction of codes for a wiretap channel, so we can use the method that was introduced by Wyner and Ozarow [1, 22] to construct k-RES.Consider a stochastic coding method consisting of a linear code and its cosets. To transmitm-bit message, we first select a (n
,
n
-
m) linear binary code C; let each message correspond to a chosen coset out of the 2
m cosets of C. The overall encoding operation can be described as a matrix multiplication. Suppose G
∈
G
F
(
2
)
(
n
-
m
)
×
n is a generator matrix for C, and its parity-check matrix is H
∈
G
F
(
2
)
m
×
n. We select m linearly independent vector h
1
,
…
,
h
m from {
0,1
}
n
∖
C. A m-bit message S
=
[
s
1
,
…
,
s
m
] is encoded into a n-bit word randomly selected from the coset C corresponding to S. Formally, an encoder maps S to a word as(47)
S
⟼
G
′
T
G
T
S
V
,where the transpose of G is denoted by G
T, the vector V
∈
G
F
(
2
)
n
-
m is chosen uniformly at random, and G
′ is a matrix whose rows are the vectors h
1
T
,
…
,
h
m
T.A decoder maps a wordX to a message as x
↦
H
x.Though the above correspondence is deterministic, the encoding procedure has a random component in the selection of the transmitted word. The messageS can be determined without error across the main channel, and every S is equally likely across the wiretapper’s channel. For an eavesdropper who can observe a set of μ bits, if all submatrices of G with μ columns have rank μ, the above coset coding guarantees perfect secrecy against the eavesdropper [22]. Guided by this result, we could choose C as a capacity-achieving code to design a k-RES.Remarks 5.
A binary wiretap channel model in which the wiretapper is known to access no more thanμ of n transmitted bits is called a wiretap channel of type II. The equivalent wiretap channel of k-RES differs from wiretap channel of type II in that the eavesdropper cannot in principle choose which μ bits are observed. In a k-RES, for K
A
⊕
K
E is constant, the eavesdropper can only observe μ
=
n
-
b bits in fixed positions (i
1
,
…
,
i
μ).According to [22], let C
0 be a (n, n
-
m) binary linear code with generator matrix G, and let g
i denote the ith column of G. Let z be an observation of the eavesdropper with μ unerased bits in positions (i
1
,
…
,
i
μ); then z is secured by C
0 if and only if the matrix G
μ
≜
(
g
i
1
,
…
,
g
i
μ
) has rank μ.Theoretically, if we use coset coding to construct ak-RES, we only need to select a generator matrix G whose submatrix G
μ has rank μ
=
n
-
k. Nevertheless, for we do not know the error pattern K
A
⊕
K
E of Eve, that is, the positions (i
1
,
…
,
i
μ) are unknown, we have to select a generator matrix G whose submatrices with μ
=
n
-
k columns all have rank μ.Note that Eve’s observation contains a number of bits in fixed positions; her ability is restricted compared with the eavesdropper in a wiretap channel of type II. Intuitively, a code designed for this wiretap channel may achieve rates arbitrarily approximate to the secrecy capacity, but how to design such code is still unknown.In [23, 24], Dodis et al. considered a notion of fuzzy extractor. Their construction can be rephrased to give a construction of k-RES. fuzzy extractors allow one to extract some randomness R from ω and then successfully reproduce R from any string ω
′ that is close to ω. The reproduction uses the helper string P produced during the initial extraction; yet P need not remain secret, because R looks truly random even given P.Construction of
k
-RES from Fuzzy Extractors. On input of a message M
∈
{
0,1
}
m, and K
A
,
K
B
∈
{
0,1
}
n, select an (
n
,
e
,
q
,
k
,
ε
)-fuzzy extractor with a pair of randomized procedures, Gen and Rep.(i)
The generation procedure Gen on inputK
A
∈
{
0,1
}
n outputs an extracted string R
∈
{
0,1
}
q and a helper string P
∈
{
0,1
}
∗. Then we obtain the encrypted message M
¯
=
M
⊕
R and a public string P.
(ii)
To decryptM
¯, the reproduction procedure Rep takes K
B
∈
{
0,1
}
n and the public string P
∈
{
0,1
}
∗ as inputs. If d
H
(
K
A
,
K
B
)
≤
k, then Rep(
K
B
,
P
)
=
R; otherwise, no guarantee is provided about the output of Rep. Then we get message M
=
M
¯
⊕
R.
(iii)
The security property of fuzzy extractor guarantees that, for any distributionK
A or K
B
∈
{
0,1
}
n of min-entropy e, the string R is nearly uniform even for those who observe P: if (
R
,
P
)
← Gen(
K
A
), then S
D
(
(
R
,
P
)
,
(
U
l
,
P
)
)
<
ε, where S
D
(
A
,
B
)
=
1
/
2
∑
v
P
r
(
A
=
v
)
-
P
r
(
B
=
v
) is the statistical distance between two probability distributions A and B and U
l denotes the uniform distribution on l-bit binary strings.


## 5.1. Problem Description

LetV
=
{
0,1
} and let V
n be the set of n-tuples over V; that is,(38)
V
n
=
x
1
,
x
2
,
…
,
x
n
∣
x
i
∈
V
,
i
=
1,2
,
…
,
n
.For X
=
[
x
1
,
x
2
,
…
,
x
n
]
∈
V
n and Y
=
[
y
1
,
y
2
,
…
,
y
n
]
∈
V
n, the Hamming distance d
H
(
X
,
Y
) between X and Y is the number of coordinates in which they differ; that is, d
H
(
X
,
Y
)
=
{
i
∣
x
i
≠
y
i
}.Formally, ak-resistant encryption scheme (k-RES) is defined as follows.Definition 4 (k-resistant encryption scheme).
An encryption scheme is calledk-resistant if the following conditions are satisfied.(1)
Decodable Condition. Alice encrypts a plaintext message M
∈
{
0,1
}
m to a ciphertext C
∈
{
0,1
}
q using her secret key K
A
∈
{
0,1
}
n (n
>
m), and Bob can decrypt C with his key K
B
∈
{
0,1
}
nif there are at most k bits which differ between K
A and K
B; that is,(39)
H
M
∣
K
A
C
=
H
M
∣
K
B
C
=
0
ifd
H
(
K
A
,
K
B
)
≤
k
.
(2)
Security Condition. Eve can only obtain a negligible amount of information about M if her key K
E satisfies d
H
(
K
A
,
K
E
)
>
k; that is,(40)
H
M
∣
K
E
C
=
H
M
M
i
f
d
H
K
A
,
K
E
>
k
.The decodable condition guarantees that anyone with a keyK satisfying d
H
(
K
A
,
K
)
≤
k can recover the message. The security condition, on the other hand, ensures that Eve can obtain no information about the message if d
H
(
K
A
,
K
E
)
>
k.Intuitively, ak-RES can be viewed as a wiretap channel in which Alice sends secret information to Bob virtually in the main channel, and the adversary Eve receives Alice’s output through an independent wiretapper channel.To send a messageX to Bob, Alice sends X
⊕
K
A instead. Bob computes Y
=
X
⊕
K
A
⊕
K
B and thus obtains X with error pattern K
A
⊕
K
B and bit error probability ϵ
=
a
/
n for d
H
(
K
A
,
K
B
)
=
a. Eve, on the other hand, can compute Z
=
X
⊕
K
A
⊕
K
E, which is equivalent to receiving X over a wiretapper’s channel with bit error probability δ
=
b
/
n (for d
H
(
K
A
,
K
E
)
=
b). Thus, the bit error probabilities of the conceptual main channel and Eve’s conceptual channel are ϵ
=
a
/
n and δ
=
b
/
n, respectively. Because a
≤
k and b
>
k, then ϵ
<
δ, which implies that the main channel is less noisy than the wiretapper’s channel; therefore, the secrecy capacity C
S of the conceptual wiretap channel [2](41)
C
S
=
m
a
x
P
X
x
I
X
;
Y
-
I
X
;
Z
.It was further shown in [21] that if I
(
X
;
Y
) and I
(
X
;
Z
) are individually maximized by the same P
X
(
x
), and the main channel is less noisy than the wiretapper’s channel, C
S
=
C
a
p
a
c
i
t
y
(
X
→
Y
)
-
C
a
p
a
c
i
t
y
(
X
→
Z
). Consider a k-RES; it can be viewed as a broadcast channel in which the main channel and the wiretapper’s channel are binary symmetric channels with bit error probabilities ϵ and δ, respectively, and ϵ
<
δ. The secrecy capacity is C
S
=
h
(
δ
)
-
h
(
ϵ
)
.Suppose Alice and Bob try to securely communicate am-bit message M across the main channel; Alice encodes M
∈
{
0,1
}
m into an n-bit word X
∈
{
0,1
}
n. We have(42)
m
n
=
C
S
=
h
δ
-
h
ϵ
,and then(43)
m
=
n
h
δ
-
h
ϵ
=
n
h
b
n
-
h
a
n
.Notice thatk
<
b
≤
n
/
2, h
(
k
/
n
)
<
h
(
b
/
n
); we have(44)
m
>
n
h
k
n
-
h
a
n
.The secrecy capacity ofk-RES depends on parameters a and k. The less the value d
H
(
K
A
,
K
B
)
=
a is, the more the information can be encrypted. On the other hand, there are situations in which the bound is tighter. If we know the value b exactly, we can get the upper bound of m; that is, m
≤
n
[
h
(
b
/
n
)
-
h
(
a
/
n
)
], since h
(
δ
)
-
h
(
ϵ
) is the upper bound of C
S.


## 5.2. Construction Methods

A trivialk-RES can be constructed by a classic error-correcting code. We can choose (n, m) error-correcting code, which maps a message M
∈
{
0,1
}
m to a codeword C
∈
{
0,1
}
n and can correct at most k-bit errors. In order to encrypt a message M of m-bit, Alice transmits C
⊕
K
A to Bob. Bob computes C
-
=
C
⊕
K
A
⊕
K
B which differs from C in d
H
(
K
A
,
K
B
) bits. If d
H
(
K
A
,
K
B
)
<
k, Bob can correct the errors and recover the message M.Eve, on the other hand, cannot get the message correctly, since what she can obtain isC
^
=
C
⊕
K
A
⊕
K
E which differs from C in d
H
(
K
A
,
K
E
)
>
k bits.Next we estimate the amount of information that this solution ofk-RES can handle. In general, a linear (n
,
m) block code, such as Hamming code, which can correct k-bit errors should satisfy the following bound:(45)
n
-
m
≥
l
o
g
∑
i
=
0
k
n
i
.Hence, ifk
≪
n, n
k
-
1
<
n
k, and 2
n
k
>
∑
i
=
1
k
n
i
>
n
k, we obtain(46)
m
≤
n
-
l
o
g
∑
i
=
0
k
n
i
<
n
-
l
o
g
n
k
≈
a
n
-
n
h
k
n
=
n
1
-
h
k
n
,where (a) follows from n
k
~
2
n
h
(
k
/
n
) for k
≪
n.This solution can be used to constructk-RES when few errors are more likely to occur. The error-correcting code may also give some side information to Eve. From a practical perspective, the design of a k-RES turns out to be a problem of the construction of codes for a wiretap channel, so we can use the method that was introduced by Wyner and Ozarow [1, 22] to construct k-RES.Consider a stochastic coding method consisting of a linear code and its cosets. To transmitm-bit message, we first select a (n
,
n
-
m) linear binary code C; let each message correspond to a chosen coset out of the 2
m cosets of C. The overall encoding operation can be described as a matrix multiplication. Suppose G
∈
G
F
(
2
)
(
n
-
m
)
×
n is a generator matrix for C, and its parity-check matrix is H
∈
G
F
(
2
)
m
×
n. We select m linearly independent vector h
1
,
…
,
h
m from {
0,1
}
n
∖
C. A m-bit message S
=
[
s
1
,
…
,
s
m
] is encoded into a n-bit word randomly selected from the coset C corresponding to S. Formally, an encoder maps S to a word as(47)
S
⟼
G
′
T
G
T
S
V
,where the transpose of G is denoted by G
T, the vector V
∈
G
F
(
2
)
n
-
m is chosen uniformly at random, and G
′ is a matrix whose rows are the vectors h
1
T
,
…
,
h
m
T.A decoder maps a wordX to a message as x
↦
H
x.Though the above correspondence is deterministic, the encoding procedure has a random component in the selection of the transmitted word. The messageS can be determined without error across the main channel, and every S is equally likely across the wiretapper’s channel. For an eavesdropper who can observe a set of μ bits, if all submatrices of G with μ columns have rank μ, the above coset coding guarantees perfect secrecy against the eavesdropper [22]. Guided by this result, we could choose C as a capacity-achieving code to design a k-RES.Remarks 5.
A binary wiretap channel model in which the wiretapper is known to access no more thanμ of n transmitted bits is called a wiretap channel of type II. The equivalent wiretap channel of k-RES differs from wiretap channel of type II in that the eavesdropper cannot in principle choose which μ bits are observed. In a k-RES, for K
A
⊕
K
E is constant, the eavesdropper can only observe μ
=
n
-
b bits in fixed positions (i
1
,
…
,
i
μ).According to [22], let C
0 be a (n, n
-
m) binary linear code with generator matrix G, and let g
i denote the ith column of G. Let z be an observation of the eavesdropper with μ unerased bits in positions (i
1
,
…
,
i
μ); then z is secured by C
0 if and only if the matrix G
μ
≜
(
g
i
1
,
…
,
g
i
μ
) has rank μ.Theoretically, if we use coset coding to construct ak-RES, we only need to select a generator matrix G whose submatrix G
μ has rank μ
=
n
-
k. Nevertheless, for we do not know the error pattern K
A
⊕
K
E of Eve, that is, the positions (i
1
,
…
,
i
μ) are unknown, we have to select a generator matrix G whose submatrices with μ
=
n
-
k columns all have rank μ.Note that Eve’s observation contains a number of bits in fixed positions; her ability is restricted compared with the eavesdropper in a wiretap channel of type II. Intuitively, a code designed for this wiretap channel may achieve rates arbitrarily approximate to the secrecy capacity, but how to design such code is still unknown.In [23, 24], Dodis et al. considered a notion of fuzzy extractor. Their construction can be rephrased to give a construction of k-RES. fuzzy extractors allow one to extract some randomness R from ω and then successfully reproduce R from any string ω
′ that is close to ω. The reproduction uses the helper string P produced during the initial extraction; yet P need not remain secret, because R looks truly random even given P.Construction of
k
-RES from Fuzzy Extractors. On input of a message M
∈
{
0,1
}
m, and K
A
,
K
B
∈
{
0,1
}
n, select an (
n
,
e
,
q
,
k
,
ε
)-fuzzy extractor with a pair of randomized procedures, Gen and Rep.(i)
The generation procedure Gen on inputK
A
∈
{
0,1
}
n outputs an extracted string R
∈
{
0,1
}
q and a helper string P
∈
{
0,1
}
∗. Then we obtain the encrypted message M
¯
=
M
⊕
R and a public string P.
(ii)
To decryptM
¯, the reproduction procedure Rep takes K
B
∈
{
0,1
}
n and the public string P
∈
{
0,1
}
∗ as inputs. If d
H
(
K
A
,
K
B
)
≤
k, then Rep(
K
B
,
P
)
=
R; otherwise, no guarantee is provided about the output of Rep. Then we get message M
=
M
¯
⊕
R.
(iii)
The security property of fuzzy extractor guarantees that, for any distributionK
A or K
B
∈
{
0,1
}
n of min-entropy e, the string R is nearly uniform even for those who observe P: if (
R
,
P
)
← Gen(
K
A
), then S
D
(
(
R
,
P
)
,
(
U
l
,
P
)
)
<
ε, where S
D
(
A
,
B
)
=
1
/
2
∑
v
P
r
(
A
=
v
)
-
P
r
(
B
=
v
) is the statistical distance between two probability distributions A and B and U
l denotes the uniform distribution on l-bit binary strings.


## 6. Conclusions

Key evolution seems realistic because current wireless communication is prevailing and the channel is noisy. Even if Eve uses a much better receiving antenna she cannot avoid at least a small bit error probability. The noise allows for the construction of information theoretically secure cryptographic protocols.



---

*Source: 592848-2015-07-02.xml*