# PKDIP: Efficient Public-Key-Based Data Integrity Protection for Wireless Image Sensors

Authors: Changsheng Wan; Juan Zhang; Jie Huang
Journal: Journal of Sensors
 (2015)

---

## Abstract

Due to limited energy of “wireless image sensors (WISs),” existing data integrity protection mechanisms typically employ a hash-function-based signing algorithm to generate “message authentication codes (MACs)” for long image frames. However, hash-function-based signing algorithm requires the WIS and the “end user (EU)” sharing a secret, which leads to a new security issue: Once the EU becomes malicious due to some reasons, it will be able to forge the WIS’s data since it holds the shared secret. Therefore, public-key cryptography is desirable. Unfortunately, public-key cryptographic operations are quite time-consuming for energy-restrained WISs. Facing this dilemma, we present a novel data integrity protection protocol named PKDIP in this paper. Similar to the mechanisms of this field, PKDIP generates MACs for data integrity protection. However, different from other well-known approaches, PKDIP introduces the “Montgomery Modular Multiplication (MontMM)” technique to current public-key-based signing algorithms. Since MontMM is much more efficient than hash functions, PKDIP can reduce the signing cost significantly. Experimental results show PKDIP can even be more efficient than hash-function-based schemes.


---

## Body

## 1. Introduction

Nowadays, “wireless image sensors (WISs)” are being widely deployed in military, environmental, and other commercial applications [1]. Examples include (i) visually monitoring the environment. WISs have been widely deployed in many situations (e.g., toxic areas, disaster locations, and natural environments such as forests and deserts) to visually detect unusual events or to acquire environmental data over long periods of time. Moreover, a recent report has shown that “Jet Propulsion Laboratory (JPL)” [2] of NASA even deployed WISs to detect surface of Mars. Examples also include (ii) visually monitoring the combat field. To improve the perceptibility of command state and to reliably make correct estimation about menace and track it, many countries have developed some military scientific research on WISs to improve the combat and command ability of army.In the above applications, WISs are deployed on a remote land, which collect image frames and send them to “end users (EUs)” over the wireless sensor network (WSN) and Internet. And EUs process those frames to visually monitor a remote area.(A) Motivation. To transport image frames from WIS to EU, data integrity protection modules have been deployed, ensuring that the image frames are not forged by attackers between WIS and EU. In our network model, as shown in Figure 1, a data integrity protection scenario includes three parties: WIS, EU, and a “trusted third-party (TTP),” which are defined as follows.Figure 1
Data integrity protection overview.(1)
The TTP (e.g., a computer controlled by a commander in the command center) is the key server for WIS and EU. Before image-transmitting, the TTP deploys keys to WIS and EU for signing and verification, respectively.
(2)
The WIS is deployed in a remote area (e.g., the monitored combat field). During image-transmitting, the WIS acquires environmental image frames and generates a “message authentication code (MAC) [3]” for each frame. Then it sends image frames and their MACs to the EU over the WSN and Internet.
(3)
The EU (e.g., a cloud server controlled by employees in the command center) processes image frames. Upon receiving data from WIS, EU checks MACs to ensure that the image frames are not forged by attackers (e.g., enemies in the monitored combat field).In the above scenario, the TTP and the EU have enough computational resources, while the WIS has limited energy.Computation cost is a serious concern for the above data integrity protection system. Due to limited energy, WIS is deeply concerned about the extremely high computation cost arising from generating MACs for long image frames (e.g., a typical RGB mode image after interpolation is around hundreds and thousands of kilobytes in length [1]). Therefore, to increase the lifetime of the WIS, current data integrity protection techniques mainly use hash functions [4–6] for generating MACs, instead of public-key-based signing algorithms [7].Unfortunately, hash-function-based schemes require that the WIS and the EU share a secret and use this secret for signing and verification, respectively. This will lead to a new security issue as illustrated by the following example: If the EU is under attack and becomes malicious (e.g., a military spy succeeds in logging in EU, or an employee is dismissed), the attacker may get the shared secret key and forge image frames of WIS. And then it can hide the forgery action by generating a new MAC using the shared key. In this case, the commander will not be able to know the real situation of the combat field, resulting in wrong commands. Therefore, to avoid such attacks, a public-key-based data integrity protection protocol for WIS is desired, where WIS generates MACs using its private key and EU verifies MACs using the corresponding public key. By doing so, the attacker is unable to forge the WIS’s image frames even though it can log in the EU, because the EU does not know the private key. However, public-key-based cryptographic operations are quite time-consuming. For example, as discussed in Section2, the computation cost of modular exponentiation operation is around 1
0
2


~


1
0
3 times that of hash functions. This will lead to short lifetime of the WIS. Facing this dilemma, this paper aims to design a public-key-based data integrity protection protocol for WISs, where the signing cost is low and the verification cost is at a practical level.A data integrity protection protocol for WISs should satisfy the following requirements.(1) Correctness. It should be ensured that no one can forge WIS’s image frames. Specifically, it should be guaranteed that even when the EU is under attack, the attacker cannot forge image frames.(2) Strong Resistance to Replay Attacks. It should be ensured that WIS’s data transmission is not fraudulently repeated by an attacker. This requirement is very important for many scenarios. For example, if the attacker keeps replaying an old frame of image to the EU, the EU will not be able to know the visual change of the monitored field (i.e., the EU is blinded).(3) Strong Resistance to Sequence Errors. It should be ensured that the sequence of WIS’s image frames is not disordered. This requirement has vital significance too. For example, if the first frame contains a standing soldier, and the second frame contains a lying soldier, the EU may assess the situation that this soldier is killed. But if the attacker changes the sequence of these two frames, the EU may assess the situation that this soldier stands up after falling down.(4) The Signing Cost of the WIS Is Low. Due to limited energy, in WIS, it should be ensured that the signing cost is low, especially when processing long image frames with the length of hundreds and thousands of kilobytes (KBs).(5) The Verification Cost of the EU Is at a Practical Level. The EU is typically a cloud server with thousands of computers. And hence it has powerful computational resources. However, it is too wasteful for thousands of computers to verify just one image frame, because the EU may have to process frames from multiple WISs. Therefore, it should be guaranteed that it is efficient for only a few computers to do the verification work.(6) The Communication Cost Is at a Practical Level. Transmitting data to the EU will consume the WIS’s energy too. So, for WIS, it should be ensured that the communication cost is at a practical level.Obviously, designing a data integrity protection protocol for WIS is a nontrivial task, because the resource-restrained WIS is not competent to sign and transmit long image frames. Current hash-function-based schemes can satisfy requirements (2), (3), (4), (5), and (6) but cannot perfectly satisfy requirement (1) (e.g., if the EU is under attack due to some reasons, the attacker will be able to forge image frames from the WIS). On the other hand, public-key-based schemes can satisfy requirements (1), (2), (3), (5), and (6) but cannot satisfy requirement (4). More importantly, when considering this research issue, we observe that none of the existing cryptographic primitives can be directly applied to achieve the goals discussed above. The detailed analysis to arrive at these conclusions will be given in Section2. This becomes a more severe issue given the trend that more and more WISs are being deployed.(B) Contributions. Motivated by the above observation, this paper makes three main contributions:(1)
We first identify the characteristics of data integrity protection for WISs and then present a comprehensive set of requirements for the protocol of this kind. We show some security and efficiency problems of current data integrity protection schemes.
(2)
We propose a novel approach to ensure data integrity for WISs called PKDIP, which is built on public-key cryptography, and hence it can fulfill requirement (1). However, different from current public-key-based mechanisms, PKDIP mainly uses the Montgomery Modular Multiplication (MontMM) algorithm [8] for processing image frames and only uses few scalar multiplication operations for each frame. Since MontMM is much more efficient than hash functions, the signing cost of PKDIP can even be much lower than those of hash-function-based schemes.
(3)
In addition to the security analysis which demonstrates that PKDIP indeed enforces its security guarantees, this paper also analyzes the efficiency of PKDIP, showing it can even be much more efficient than current hash-function-based schemes.(C) Organization. The remainder of this paper is organized as follows. In the next section, we survey the related work. Section 3 describes PKDIP in detail, followed by the security analysis and efficiency evaluation in Sections 4 and 5, respectively. Finally, we draw our conclusions in Section 6.


## 2. Related Work

Due to the openness of wireless channel, attackers can easily intercept data from WIS and establish efficient attacks on the data stream. Therefore, security has vital significance for WIS.There are a lot of security challenges for WIS [9–19], including authentication, authorization, key distribution, data integrity, data confidentiality, data aggregation, and source tracing. Among all those challenges, data integrity [17–19] is the most important one, which ensures that data transmitted over the hostile network is not forged by attackers. Without data integrity protection, EUs may get a wrong result when processing the received data [17].All current data integrity protection protocols for WISs can be classified into three types: traditional hash-function-based protocols [20–24], watermarking-based protocols [25–27], and public-key-based protocols [28, 29].(1) Traditional Hash-Function-Based Protocols. Traditional hash-function-based protocols use a shared key and a hash function for generating MACs. Perrig et al. [20, 21] introduced the SPINS protocol, which uses the μTESLA technique for data integrity. In μTESLA, the key server creates a one-way key chain (i.e., a sequence of shared keys), and each key of the chain is used within a time interval for generating MACs (i.e., they mainly focus on the key management topic of data integrity). Albath and Madria [22] introduced the PADS protocol, which shows how to support both data integrity and confidentiality together. TinySec [23] investigates data integrity problems in the link-layer. LEAP [24] is a key management solution too.(2) Watermarking-Based Protocols. Similar to traditional hash-function-based protocols, watermarking-based protocols use a shared key and a hash function for generating MACs. They are different from traditional hash-function-based protocols only in the transmitting method of MACs. In watermarking-based protocols [25–27], MACs replace the least significant bits of image frames. By doing so, the communication cost is saved, and the lifetime of WIS is increased.(3) Public-Key-Based Protocols. Due to the high computation cost, public-key cryptography has been deprecated from being used in WSN as a data integrity protection algorithm. In the previous work [28–30], a lot of experiments have been done to test the time costs of cryptographic operations. The results show computation costs of public-key-based algorithms (e.g., scalar multiplication and modular exponentiation) are around 1
0
2
~
1
0
3 times those of hash-function-based algorithms (e.g., SHA1).


## 3. PKDIP: The Protocol

In this section, we will give the system model of PKDIP and then present a bilinear-map-based data integrity protection construction, which can reduce the signing cost significantly.


### 3.1. Preliminaries

Definition 1.
LetG and G
T be two cyclic groups with the same prime order q (i.e., G
=
G
T
=
q). Let g be the generator of G. Then, a bilinear map group is defined as e
^
:
G
×
G
→
G
T, where e
^ has the following properties.(1) Bilinearity. ∀
a
,
b
∈
Z
q, e
^
(
g
a
,
g
b
)
=
e
^
(
g
,
g
)
a
b
=
e
^
(
g
a
b
,
g
)
=
e
^
(
g
,
g
a
b
)
=
e
^
(
g
b
,
g
a
). ∀
A
,
B
∈
G, e
^
(
A
B
,
g
)
=
e
^
(
A
,
g
)
e
^
(
B
,
g
).(2) Nondegeneracy. ∃
A
,
B
∈
G such that e
^
(
A
,
B
)
≠
1
G
T.(3) Computability. ∀
A
,
B
∈
G, it is efficient to calculate e
^
(
A
,
B
).The abovee
^ can be constructed by the Weil or Tate pairings [31, 32] on elliptic curves.


### 3.2. System Model

The system model of PKDIP is shown in Figure2, which includes three phases as illustrated below.Figure 2
System model of PKDIP.


#### 3.2.1. The Preconfiguration Phase

During this phase, the TTP generates a public-private key pair and deploys it on the WIS. Then it distributes the public key to the EU. To ensure the EU and the WIS get the correct keys and the keys are not leaked to attackers, the key distributing channels should provide integrity/confidentiality/replay-resistance protection. The key generating algorithm is shown below.(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
1
λ
). This algorithm is run by the TTP for initializing cryptographic parameters of PKDIP. It takes as input the security parameter (i.e., λ) and outputs a public key (i.e., p
k) and a private key (i.e., s
k). In this algorithm, λ is the length of s
k, which determines the security level of PKDIP.After the preconfiguration phase, the WIS holds(
p
k
,
s
k
) for signing image frames, whereas the EU holds p
k for verifying image frames.


#### 3.2.2. The Signing Phase

During this phase, the WIS splits the frame of image (M
i) into n data blocks m
i
1
,
m
i
2
,
…
,
m
i
n
∈
Z
q, and it generates a MAC for it using the following signing algorithm.τ
i
←
G
e
n
S
i
g
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
s
k
). This algorithm is run by the WIS for generating a MAC for the frame of image (M
i). It takes as input (
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
s
k
) and outputs a MAC τ
i, where w
I
D is used for identifying the WIS, and S
e
q
i is a sequence number used for identifying this frame of image. In addition, a sequence number is a nondecreasing number, and the EU uses it for avoiding replay attacks and sequence errors. This is illustrated by the following two examples: (i) If the sequence number of the received frame is the same as a previous one, the EU will know this is a replayed frame and discard it. (ii) If the sequence number of the received frame is less than the previous one, the EU will know this is a disordered frame and re-sort it.Then, the WIS sendsF
i
=
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
τ
i
) to the EU.


#### 3.2.3. The Verification Phase

Upon receivingF
i from the WIS, the EU first checks S
e
q
i to make sure the received image frame is neither a replayed nor a disordered one and then verifies the image frame using the following verification algorithm.{
T
r
u
e
,
F
a
l
s
e
}
←
V
e
r
S
i
g
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
τ
i, p
k
). This algorithm is run by the EU to make sure that the frame of image is not forged by the attacker. It takes as input (
w
I
D
,
S
e
q
i
,
m
i
1, m
i
2
,
…
,
m
i
n
,
τ
i
,
p
k
) and outputs T
r
u
e for a correct frame or F
a
l
s
e for a forged frame.From the aboveG
e
n
S
i
g algorithm, it can be seen that WIS generates the MAC using its private key (i.e., s
k). In Section 4, we will show that, without knowing s
k, the adversary cannot generate correct MACs for forged image frames. From the above V
e
r
S
i
g algorithm, it can be seen that the EU verifies the MAC using the WIS’s public key (i.e., p
k), without knowing s
k. Therefore, even if the adversary can log in the EU, it cannot forge image frames and generate correct MACs. In other words, this system model can fulfill requirement (1) of Section 1.In addition, from the above verification phase, it can be seen that the EU can avoid replay attacks and sequence errors by checkingS
e
q
i. Therefore, the system model can fulfill requirements (2) and (3) of Section 1.


### 3.3. Construction

The construction of PKDIP is a tuple(
K
e
y
G
e
n
,
G
e
n
S
i
g
,
V
e
r
S
i
g
) of probabilistic polynomial time algorithms.K
e
y
G
e
n. The TTP first creates a bilinear map group e
^
:
G
×
G
→
G
T with the prime order q and the generator g
∈
G. Then it randomly generates a set {
s
k
1
,
…
,
s
k
n
∈
Z
q
,
u
∈
G
} and computes {
p
k
1
=
g
s
k
1
,
…
,
p
k
n
=
g
s
k
n
∈
G
,
s
k
r
=
∑
j
=
1
n
‍
s
k
j
∈
Z
q
,
p
k
r
=
g
s
k
r
∈
G
}. Finally, it gets the private key s
k
=
{
s
k
r
,
s
k
1
,
…
,
s
k
n
∈
Z
q
} and the public key p
k
=
{
p
k
r
,
p
k
1
,
…
,
p
k
n
,
u
}.G
e
n
S
i
g. The WIS signs the image frame (i.e., M
i) as τ
i
=
H
(
w
I
D
∥
S
e
q
i
)
s
k
r
u
∑
j
=
1
n
‍
m
i
j
s
k
j
∈
G.V
e
r
S
i
g. The EU verifies the image frame as e
^
(
τ
i
,
g
)
=
?
∏
j
=
1
n
‍
e
^
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
j
,
p
k
j
). This verification equation holds because(1)
e
^
τ
i
,
g
=
e
^
H
w
I
D
∥
S
e
q
i
s
k
r
u
∑
j
=
1
n
m
i
j
s
k
j
,
g
=
e
^
∏
j
=
1
n
H
w
I
D
∥
S
e
q
i
u
m
i
j
s
k
j
,
g
=
∏
j
=
1
n
e
^
H
w
I
D
∥
S
e
q
i
u
m
i
j
s
k
j
,
g
=
∏
j
=
1
n
e
^
H
w
I
D
∥
S
e
q
i
u
m
i
j
,
p
k
j
.From the aboveG
e
n
S
i
g algorithm, it can be seen that PKDIP processes (
m
i
1
,
…
,
m
i
n
) mainly using the MontMM algorithm. In contrast, hash-function-based schemes (e.g., Kamel’s scheme [27]) process (
m
i
1
,
…
,
m
i
n
) using hash functions. Since MontMM is much more efficient than hash functions, PKDIP can reduce the signing cost significantly. In Section 5, we will further show, though two scalar multiplication operations are used, the total signing cost of PKDIP can be much lower than those of hash-function-based schemes.From the aboveV
e
r
S
i
g algorithm, it can be seen that PKDIP verifies (
m
i
1
,
…
,
m
i
n
) using multiple pairing operations. In Section 5, we will show the verification cost is at a practical level.


## 3.1. Preliminaries

Definition 1.
LetG and G
T be two cyclic groups with the same prime order q (i.e., G
=
G
T
=
q). Let g be the generator of G. Then, a bilinear map group is defined as e
^
:
G
×
G
→
G
T, where e
^ has the following properties.(1) Bilinearity. ∀
a
,
b
∈
Z
q, e
^
(
g
a
,
g
b
)
=
e
^
(
g
,
g
)
a
b
=
e
^
(
g
a
b
,
g
)
=
e
^
(
g
,
g
a
b
)
=
e
^
(
g
b
,
g
a
). ∀
A
,
B
∈
G, e
^
(
A
B
,
g
)
=
e
^
(
A
,
g
)
e
^
(
B
,
g
).(2) Nondegeneracy. ∃
A
,
B
∈
G such that e
^
(
A
,
B
)
≠
1
G
T.(3) Computability. ∀
A
,
B
∈
G, it is efficient to calculate e
^
(
A
,
B
).The abovee
^ can be constructed by the Weil or Tate pairings [31, 32] on elliptic curves.


## 3.2. System Model

The system model of PKDIP is shown in Figure2, which includes three phases as illustrated below.Figure 2
System model of PKDIP.


### 3.2.1. The Preconfiguration Phase

During this phase, the TTP generates a public-private key pair and deploys it on the WIS. Then it distributes the public key to the EU. To ensure the EU and the WIS get the correct keys and the keys are not leaked to attackers, the key distributing channels should provide integrity/confidentiality/replay-resistance protection. The key generating algorithm is shown below.(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
1
λ
). This algorithm is run by the TTP for initializing cryptographic parameters of PKDIP. It takes as input the security parameter (i.e., λ) and outputs a public key (i.e., p
k) and a private key (i.e., s
k). In this algorithm, λ is the length of s
k, which determines the security level of PKDIP.After the preconfiguration phase, the WIS holds(
p
k
,
s
k
) for signing image frames, whereas the EU holds p
k for verifying image frames.


### 3.2.2. The Signing Phase

During this phase, the WIS splits the frame of image (M
i) into n data blocks m
i
1
,
m
i
2
,
…
,
m
i
n
∈
Z
q, and it generates a MAC for it using the following signing algorithm.τ
i
←
G
e
n
S
i
g
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
s
k
). This algorithm is run by the WIS for generating a MAC for the frame of image (M
i). It takes as input (
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
s
k
) and outputs a MAC τ
i, where w
I
D is used for identifying the WIS, and S
e
q
i is a sequence number used for identifying this frame of image. In addition, a sequence number is a nondecreasing number, and the EU uses it for avoiding replay attacks and sequence errors. This is illustrated by the following two examples: (i) If the sequence number of the received frame is the same as a previous one, the EU will know this is a replayed frame and discard it. (ii) If the sequence number of the received frame is less than the previous one, the EU will know this is a disordered frame and re-sort it.Then, the WIS sendsF
i
=
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
τ
i
) to the EU.


### 3.2.3. The Verification Phase

Upon receivingF
i from the WIS, the EU first checks S
e
q
i to make sure the received image frame is neither a replayed nor a disordered one and then verifies the image frame using the following verification algorithm.{
T
r
u
e
,
F
a
l
s
e
}
←
V
e
r
S
i
g
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
τ
i, p
k
). This algorithm is run by the EU to make sure that the frame of image is not forged by the attacker. It takes as input (
w
I
D
,
S
e
q
i
,
m
i
1, m
i
2
,
…
,
m
i
n
,
τ
i
,
p
k
) and outputs T
r
u
e for a correct frame or F
a
l
s
e for a forged frame.From the aboveG
e
n
S
i
g algorithm, it can be seen that WIS generates the MAC using its private key (i.e., s
k). In Section 4, we will show that, without knowing s
k, the adversary cannot generate correct MACs for forged image frames. From the above V
e
r
S
i
g algorithm, it can be seen that the EU verifies the MAC using the WIS’s public key (i.e., p
k), without knowing s
k. Therefore, even if the adversary can log in the EU, it cannot forge image frames and generate correct MACs. In other words, this system model can fulfill requirement (1) of Section 1.In addition, from the above verification phase, it can be seen that the EU can avoid replay attacks and sequence errors by checkingS
e
q
i. Therefore, the system model can fulfill requirements (2) and (3) of Section 1.


## 3.2.1. The Preconfiguration Phase

During this phase, the TTP generates a public-private key pair and deploys it on the WIS. Then it distributes the public key to the EU. To ensure the EU and the WIS get the correct keys and the keys are not leaked to attackers, the key distributing channels should provide integrity/confidentiality/replay-resistance protection. The key generating algorithm is shown below.(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
1
λ
). This algorithm is run by the TTP for initializing cryptographic parameters of PKDIP. It takes as input the security parameter (i.e., λ) and outputs a public key (i.e., p
k) and a private key (i.e., s
k). In this algorithm, λ is the length of s
k, which determines the security level of PKDIP.After the preconfiguration phase, the WIS holds(
p
k
,
s
k
) for signing image frames, whereas the EU holds p
k for verifying image frames.


## 3.2.2. The Signing Phase

During this phase, the WIS splits the frame of image (M
i) into n data blocks m
i
1
,
m
i
2
,
…
,
m
i
n
∈
Z
q, and it generates a MAC for it using the following signing algorithm.τ
i
←
G
e
n
S
i
g
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
s
k
). This algorithm is run by the WIS for generating a MAC for the frame of image (M
i). It takes as input (
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
s
k
) and outputs a MAC τ
i, where w
I
D is used for identifying the WIS, and S
e
q
i is a sequence number used for identifying this frame of image. In addition, a sequence number is a nondecreasing number, and the EU uses it for avoiding replay attacks and sequence errors. This is illustrated by the following two examples: (i) If the sequence number of the received frame is the same as a previous one, the EU will know this is a replayed frame and discard it. (ii) If the sequence number of the received frame is less than the previous one, the EU will know this is a disordered frame and re-sort it.Then, the WIS sendsF
i
=
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
τ
i
) to the EU.


## 3.2.3. The Verification Phase

Upon receivingF
i from the WIS, the EU first checks S
e
q
i to make sure the received image frame is neither a replayed nor a disordered one and then verifies the image frame using the following verification algorithm.{
T
r
u
e
,
F
a
l
s
e
}
←
V
e
r
S
i
g
(
w
I
D
,
S
e
q
i
,
m
i
1
,
m
i
2
,
…
,
m
i
n
,
τ
i, p
k
). This algorithm is run by the EU to make sure that the frame of image is not forged by the attacker. It takes as input (
w
I
D
,
S
e
q
i
,
m
i
1, m
i
2
,
…
,
m
i
n
,
τ
i
,
p
k
) and outputs T
r
u
e for a correct frame or F
a
l
s
e for a forged frame.From the aboveG
e
n
S
i
g algorithm, it can be seen that WIS generates the MAC using its private key (i.e., s
k). In Section 4, we will show that, without knowing s
k, the adversary cannot generate correct MACs for forged image frames. From the above V
e
r
S
i
g algorithm, it can be seen that the EU verifies the MAC using the WIS’s public key (i.e., p
k), without knowing s
k. Therefore, even if the adversary can log in the EU, it cannot forge image frames and generate correct MACs. In other words, this system model can fulfill requirement (1) of Section 1.In addition, from the above verification phase, it can be seen that the EU can avoid replay attacks and sequence errors by checkingS
e
q
i. Therefore, the system model can fulfill requirements (2) and (3) of Section 1.


## 3.3. Construction

The construction of PKDIP is a tuple(
K
e
y
G
e
n
,
G
e
n
S
i
g
,
V
e
r
S
i
g
) of probabilistic polynomial time algorithms.K
e
y
G
e
n. The TTP first creates a bilinear map group e
^
:
G
×
G
→
G
T with the prime order q and the generator g
∈
G. Then it randomly generates a set {
s
k
1
,
…
,
s
k
n
∈
Z
q
,
u
∈
G
} and computes {
p
k
1
=
g
s
k
1
,
…
,
p
k
n
=
g
s
k
n
∈
G
,
s
k
r
=
∑
j
=
1
n
‍
s
k
j
∈
Z
q
,
p
k
r
=
g
s
k
r
∈
G
}. Finally, it gets the private key s
k
=
{
s
k
r
,
s
k
1
,
…
,
s
k
n
∈
Z
q
} and the public key p
k
=
{
p
k
r
,
p
k
1
,
…
,
p
k
n
,
u
}.G
e
n
S
i
g. The WIS signs the image frame (i.e., M
i) as τ
i
=
H
(
w
I
D
∥
S
e
q
i
)
s
k
r
u
∑
j
=
1
n
‍
m
i
j
s
k
j
∈
G.V
e
r
S
i
g. The EU verifies the image frame as e
^
(
τ
i
,
g
)
=
?
∏
j
=
1
n
‍
e
^
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
j
,
p
k
j
). This verification equation holds because(1)
e
^
τ
i
,
g
=
e
^
H
w
I
D
∥
S
e
q
i
s
k
r
u
∑
j
=
1
n
m
i
j
s
k
j
,
g
=
e
^
∏
j
=
1
n
H
w
I
D
∥
S
e
q
i
u
m
i
j
s
k
j
,
g
=
∏
j
=
1
n
e
^
H
w
I
D
∥
S
e
q
i
u
m
i
j
s
k
j
,
g
=
∏
j
=
1
n
e
^
H
w
I
D
∥
S
e
q
i
u
m
i
j
,
p
k
j
.From the aboveG
e
n
S
i
g algorithm, it can be seen that PKDIP processes (
m
i
1
,
…
,
m
i
n
) mainly using the MontMM algorithm. In contrast, hash-function-based schemes (e.g., Kamel’s scheme [27]) process (
m
i
1
,
…
,
m
i
n
) using hash functions. Since MontMM is much more efficient than hash functions, PKDIP can reduce the signing cost significantly. In Section 5, we will further show, though two scalar multiplication operations are used, the total signing cost of PKDIP can be much lower than those of hash-function-based schemes.From the aboveV
e
r
S
i
g algorithm, it can be seen that PKDIP verifies (
m
i
1
,
…
,
m
i
n
) using multiple pairing operations. In Section 5, we will show the verification cost is at a practical level.


## 4. Security Analysis

We analyze the security of PKDIP with respect to the security requirements given in Section1. As discussed in Section 3.2, PKDIP can meet requirements (2) and (3) by using the sequence number technique. So, in this section, we mainly focus on how PKDIP meets requirement (1) in the random oracle model [33]. Our security analysis includes three parts: security assumption, adversary model, and security proof. Security assumption defines a well-known mathematical problem that cannot be efficiently solved. Adversary model defines what the adversary can see and what it can do. Security proof shows that the adversary cannot establish an efficient attack on PKDIP. Otherwise, there exists an algorithm, which can use the adversary for breaking the security assumption. In other words, existence of such an adversary contradicts the security assumption. Therefore, if the security assumption holds, the adversary does not exist.


### 4.1. Security Assumption

#### 4.1.1. Difficult Mathematical Problems onG

(1) The “Computational Diffie-Hellman (CDH)” Problem. For randomly distributed unknown a
,
b
∈
Z
q, one wants to compute g
a
b from (
g
,
g
a
,
g
b
).(2) The “Decisional Diffie-Hellman (DDH)” Problem. For randomly distributed unknown a
,
b
,
c
∈
Z
q, one wants to decide whether c
=
a
b
m
o
d
q from (
g
,
g
a
,
g
b
,
g
c
).(3) The “Gap Diffie-Hellman (GDH)” Group. G is a GDH group if the DDH problem on it can be solved in polynomial time but no probabilistic polynomial time algorithm can solve the CDH problem. Note that, in PKDIP, the DDH problem can be solved by verifying e
^
(
g
c
,
g
)
=
?
e
^
(
g
a
,
g
)
e
^
(
g
b
,
g
), because e
^
(
g
c
,
g
)
=
e
^
(
g
,
g
)
c
=
e
^
(
g
,
g
)
a
b
=
e
^
(
g
a
,
g
)
e
^
(
g
b
,
g
). Therefore, a GDH group is to ensure that the CDH problem holds on G.


#### 4.1.2. Security Assumption of PKDIP

We assume the proposed groupG is a GDH group. Specifically, we have the following assumption.Assumption 2 ((
t
,
ϵ
)-GDH group assumption).
Given(
g
,
g
a
,
g
b
)
∈
G for randomly distributed unknown (
a
,
b
)
∈
Z
q, there is no t-time algorithm, which has the nonnegligible probability ϵ in computing g
a
b
∈
G (i.e., the CDH problem holds on G).


### 4.2. Adversary Model

To satisfy requirement (1), it must be ensured that no one (including the compromised EU) can forge the WIS’s image frames. Therefore, the potential adversary is a compromised EU. In addition, since the adversary can obtain a number of image frames and the corresponding signatures, we need to prove that PKDIP is secure in the “chosen-ciphertext attack (CCA)” model [3]. In the CCA model, the adversary (A) can interact with a challenger (C) as follows:(1)
Initialization. C first generates parameters of e
^ (e.g., g and q). Then, it generates the WIS’s public key p
k, while the private key s
k is unknown. Finally, it sends p
k and parameters of e
^ to A.
(2)
Hash Query. A issues a series of hash queries, and C returns the hash values.
(3)
Signing Query. A issues a series of signing queries by sending M
i to C, and C returns the MAC (i.e., τ
i).
(4)
A outputs a forged block-MAC pair (
M
f
,
τ
f
), where the query for M
f has never been issued.In the above interactions, we sayA wins the game if the V
e
r
S
i
g algorithm returns T
r
u
e for the forged (
M
f
,
τ
f
).


### 4.3. Security Proof

In this subsection, we will show thatA cannot efficiently forge the WIS’s image frames. Otherwise, C can use it for solving the GDH problem. Our proof includes two scenarios. We first consider the n
=
1 scenario (i.e., the WIS splits the image frame into one block). Then, we extend it to the n
>
1 scenario.Scenario 1 (then
=
1 scenario).
For then
=
1 scenario, the signing algorithm becomes τ
i
=
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
1
)
s
k
1, and we have the following.Theorem 3.
Afterq
s signing queries, if A can forge the WIS’s image frame with the probability ϵ in time t, C can solve the GDH problem with the probability ϵ
′
=
(
1
-
1
/
q
s
+
1
)
q
s
∗
ϵ
∗
1
/
q
s
+
1 in time t
′
=
t
+
(
3
q
s
+
2
)
T
s
m, where T
s
m is the time cost of scalar multiplication.Proof.
The proof is given in the Appendix.Scenario 2 (then
>
1 scenario).
For then
>
1 scenario, the signing algorithm can be written as τ
i
=
H
(
w
I
D
∥
S
e
q
i
)
s
k
r
u
∑
j
=
1
n
‍
m
i
j
s
k
j
=
∏
j
=
1
n
‍
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
j
)
s
k
j
=
∏
j
=
1
n
‍
τ
i
j, where τ
i
j
=
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
j
)
s
k
j. That is to say, the MAC of the n
>
1 scenario can be seen as a combination of multiple MACs of the n
=
1 scenario. Therefore, to forge τ
i, A has to forge multiple τ
i
j’s. Assuming A can forge τ
i
j with the probability ϵ, it can forge τ
i with the probability p
r
=
ϵ
n
<
ϵ (keep in mind that ϵ
<
1). In other words, it is much harder for A to forge τ
i than to forge τ
i
j. So, in the n
>
1 scenario, A can forge τ
i only with a negligible probability too.


## 4.1. Security Assumption

### 4.1.1. Difficult Mathematical Problems onG

(1) The “Computational Diffie-Hellman (CDH)” Problem. For randomly distributed unknown a
,
b
∈
Z
q, one wants to compute g
a
b from (
g
,
g
a
,
g
b
).(2) The “Decisional Diffie-Hellman (DDH)” Problem. For randomly distributed unknown a
,
b
,
c
∈
Z
q, one wants to decide whether c
=
a
b
m
o
d
q from (
g
,
g
a
,
g
b
,
g
c
).(3) The “Gap Diffie-Hellman (GDH)” Group. G is a GDH group if the DDH problem on it can be solved in polynomial time but no probabilistic polynomial time algorithm can solve the CDH problem. Note that, in PKDIP, the DDH problem can be solved by verifying e
^
(
g
c
,
g
)
=
?
e
^
(
g
a
,
g
)
e
^
(
g
b
,
g
), because e
^
(
g
c
,
g
)
=
e
^
(
g
,
g
)
c
=
e
^
(
g
,
g
)
a
b
=
e
^
(
g
a
,
g
)
e
^
(
g
b
,
g
). Therefore, a GDH group is to ensure that the CDH problem holds on G.


### 4.1.2. Security Assumption of PKDIP

We assume the proposed groupG is a GDH group. Specifically, we have the following assumption.Assumption 2 ((
t
,
ϵ
)-GDH group assumption).
Given(
g
,
g
a
,
g
b
)
∈
G for randomly distributed unknown (
a
,
b
)
∈
Z
q, there is no t-time algorithm, which has the nonnegligible probability ϵ in computing g
a
b
∈
G (i.e., the CDH problem holds on G).


## 4.1.1. Difficult Mathematical Problems onG

(1) The “Computational Diffie-Hellman (CDH)” Problem. For randomly distributed unknown a
,
b
∈
Z
q, one wants to compute g
a
b from (
g
,
g
a
,
g
b
).(2) The “Decisional Diffie-Hellman (DDH)” Problem. For randomly distributed unknown a
,
b
,
c
∈
Z
q, one wants to decide whether c
=
a
b
m
o
d
q from (
g
,
g
a
,
g
b
,
g
c
).(3) The “Gap Diffie-Hellman (GDH)” Group. G is a GDH group if the DDH problem on it can be solved in polynomial time but no probabilistic polynomial time algorithm can solve the CDH problem. Note that, in PKDIP, the DDH problem can be solved by verifying e
^
(
g
c
,
g
)
=
?
e
^
(
g
a
,
g
)
e
^
(
g
b
,
g
), because e
^
(
g
c
,
g
)
=
e
^
(
g
,
g
)
c
=
e
^
(
g
,
g
)
a
b
=
e
^
(
g
a
,
g
)
e
^
(
g
b
,
g
). Therefore, a GDH group is to ensure that the CDH problem holds on G.


## 4.1.2. Security Assumption of PKDIP

We assume the proposed groupG is a GDH group. Specifically, we have the following assumption.Assumption 2 ((
t
,
ϵ
)-GDH group assumption).
Given(
g
,
g
a
,
g
b
)
∈
G for randomly distributed unknown (
a
,
b
)
∈
Z
q, there is no t-time algorithm, which has the nonnegligible probability ϵ in computing g
a
b
∈
G (i.e., the CDH problem holds on G).


## 4.2. Adversary Model

To satisfy requirement (1), it must be ensured that no one (including the compromised EU) can forge the WIS’s image frames. Therefore, the potential adversary is a compromised EU. In addition, since the adversary can obtain a number of image frames and the corresponding signatures, we need to prove that PKDIP is secure in the “chosen-ciphertext attack (CCA)” model [3]. In the CCA model, the adversary (A) can interact with a challenger (C) as follows:(1)
Initialization. C first generates parameters of e
^ (e.g., g and q). Then, it generates the WIS’s public key p
k, while the private key s
k is unknown. Finally, it sends p
k and parameters of e
^ to A.
(2)
Hash Query. A issues a series of hash queries, and C returns the hash values.
(3)
Signing Query. A issues a series of signing queries by sending M
i to C, and C returns the MAC (i.e., τ
i).
(4)
A outputs a forged block-MAC pair (
M
f
,
τ
f
), where the query for M
f has never been issued.In the above interactions, we sayA wins the game if the V
e
r
S
i
g algorithm returns T
r
u
e for the forged (
M
f
,
τ
f
).


## 4.3. Security Proof

In this subsection, we will show thatA cannot efficiently forge the WIS’s image frames. Otherwise, C can use it for solving the GDH problem. Our proof includes two scenarios. We first consider the n
=
1 scenario (i.e., the WIS splits the image frame into one block). Then, we extend it to the n
>
1 scenario.Scenario 1 (then
=
1 scenario).
For then
=
1 scenario, the signing algorithm becomes τ
i
=
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
1
)
s
k
1, and we have the following.Theorem 3.
Afterq
s signing queries, if A can forge the WIS’s image frame with the probability ϵ in time t, C can solve the GDH problem with the probability ϵ
′
=
(
1
-
1
/
q
s
+
1
)
q
s
∗
ϵ
∗
1
/
q
s
+
1 in time t
′
=
t
+
(
3
q
s
+
2
)
T
s
m, where T
s
m is the time cost of scalar multiplication.Proof.
The proof is given in the Appendix.Scenario 2 (then
>
1 scenario).
For then
>
1 scenario, the signing algorithm can be written as τ
i
=
H
(
w
I
D
∥
S
e
q
i
)
s
k
r
u
∑
j
=
1
n
‍
m
i
j
s
k
j
=
∏
j
=
1
n
‍
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
j
)
s
k
j
=
∏
j
=
1
n
‍
τ
i
j, where τ
i
j
=
(
H
(
w
I
D
∥
S
e
q
i
)
u
m
i
j
)
s
k
j. That is to say, the MAC of the n
>
1 scenario can be seen as a combination of multiple MACs of the n
=
1 scenario. Therefore, to forge τ
i, A has to forge multiple τ
i
j’s. Assuming A can forge τ
i
j with the probability ϵ, it can forge τ
i with the probability p
r
=
ϵ
n
<
ϵ (keep in mind that ϵ
<
1). In other words, it is much harder for A to forge τ
i than to forge τ
i
j. So, in the n
>
1 scenario, A can forge τ
i only with a negligible probability too.


## 5. Efficiency Evaluation

In the previous work [28, 29], Watro and Gura et al. have performed a lot of experiments to measure the computation costs of cryptographic operations on multiple kinds of processors. The results have shown, though the computation costs on different processors are different, the time ratio among various cryptographic operations is the same. So, in this paper, we aimed to investigate the time ratio between PKDIP and other hash-function-based schemes (e.g., Kamel’s scheme [27]).All our experiments were conducted on an Intel i7 processor system with the clock frequency 3.40 GHz. To achieve the 80-bit security parameter, we choose the 160-bit elliptic curve group. Hash function used in PKDIP and other hash-function-based schemes is SHA1 [4].Section5.1 investigates the time costs of basic cryptographic operations (i.e., SHA1, MontMM, scalar multiplication, and pairing), and Section 5.2 shows the time ratio of PKDIP to Kamel’s scheme [27]. Then, in Section 5.3, we discuss the communication cost of PKDIP. Finally, we further discuss the applicability of PKDIP on realistic sensors in Section 5.4.


### 5.1. Investigation of Basic Cryptographic Operations

We investigated the time costs of basic cryptographic operations using the OPENSSL library [34]. The results are shown in Table 1 (note that when processing a long image frame, SHA1 will split it into multiple 64-byte blocks and perform a set of permutation operations on each block. Therefore, in Table 1, the time cost for SHA1 is the time for each 64-byte data).Table 1
Time costs of basic cryptographic operations (unit:μs).
T
p
T
sm
T
h
T
mm
8120.1
329.4
0.5
0.1
T
p: time cost of Tate pairing; T
sm: time cost of scalar multiplication; T
h: time cost of SHA1 per 64-byte data; T
mm: time cost of MontMM.From Table1, it can be seen that (i) the time cost of scalar multiplication is significantly higher than those of SHA1 and MontMM, because T
sm
/
T
h
=
329.4
/
0.5
=
658.8 and T
sm
/
T
mm
=
329.4
/
0.1
≈
3.3
×
1
0
3. (ii) The time cost of SHA1 is much higher than that of MontMM, because T
h
/
T
sm
=
0.5
/
0.1
=
5. These two results imply that (i) if a public-key-based scheme only uses the T
sm operation for generating MACs, the signing cost will be quite higher than those of hash-function-based schemes. (ii) However, if a public-key-based scheme uses both T
sm and T
mm operations for generating MACs, the signing cost may be lower than hash-function-based schemes. This is because each data block is processed by one highly efficient T
m
m operation, and multiple data blocks are processed by only two time-consuming T
s
m operations.


### 5.2. Comparison of Computation Costs

The computation costs of WIS and EU are defined as the total time of cryptographic operations inG
e
n
S
i
g and V
e
r
S
i
g algorithms, respectively. In Table 2, we mainly compare the computation costs between PKDIP and Kamel’s scheme [27], because other hash-function-based schemes [20–26] enjoy similar efficiency to Kamel’s scheme [27].Table 2
Comparison of computation costs (unit:μs).
PKDIP
Kamel’s scheme [27]
T
WIS
2
T
sm
+
T
h
+
L
20
T
mm  =
0.005
L
+
659.3
L
64
T
h
=
0.008
L
T
EU
L
20
+
1
T
p
+
L
20
T
sm
+
T
h  =
422.5
L
+
8120.1
L
64
T
h
=
0.008
L
T
WIS: computation cost on the WIS; T
EU: computation cost on the EU; L: frame length in byte.From Table2, the following can be seen.(1) PKDIP Fulfills Requirement (4) of Section1. This is illustrated by the following three scenarios. (i) Scenario 1: for long image frames, the signing cost of PKDIP can be much lower than those of hash-function-based schemes, because lim
L
→
∞
⁡
(
0.005
L
+
659.3
)
/
0.008
L
=
0.625
<
1. (ii) Scenario 2: for more than 220.0 KB image frames, the signing cost of PKDIP is more efficient than hash-function-based schemes. This conclusion can be arrived at by solving the equation 0.005
L
+
659.3
=
0.008
L
⇒
L
=
659.3
/
0.008
-
0.005
=
220.0 KB. (iii) Scenario 3: for tens-of-KBs-level image frames, the signing cost of PKDIP and those of hash-function-based schemes are at the same level. For example, setting L
=
50 KB, we get that the signing costs of PKDIP and hash-function-based schemes are 909.3 μs and 400 μs, respectively (i.e., they are both hundreds of microseconds). In summary, when processing image frames with the length of hundreds and thousands of KBs, PKDIP is much more efficient than hash-function-based schemes on the WIS’s side. Additionally, when processing image frames with the length of tens of KBs, PKDIP and hash-function-based schemes enjoy similar efficiency on the WIS’s side.(2) PKDIP Fulfills Requirement (5) of Section1. For example, if L
=
100 KB, the verification cost of PKDIP is 42 s (i.e., the verification cost is at second level). Currently, the clock frequencies of most computers are at GHz level (i.e., similar to our experimental environment). Therefore, PKDIP is suitable for being deployed on most computers. Moreover, since the EU (i.e., the computing center) is typically composed of thousands of computers and processors, it can distribute the verification work to tens of computers or processors. In this case, the verification cost can even be less than one second.


### 5.3. Discussions on the Communication Cost of PKDIP

The communication cost of PKDIP is defined as the total length of frames and MACs transmitted between WIS and EU. The frame length can be shortened by image compression algorithms, which is out of scope of this paper. The MAC length of PKDIP (i.e., length ofτ
i) is equal to the length of the elliptic curve point, regardless of the length of image frames. For example, if the curve is 160 bits, the MAC length will be 160
∗
2
=
320 bits. Compared with the frame length, this MAC length can be omitted. Therefore, PKDIP fulfills requirement (6).Further, to reduce the communication cost, WIS can use the watermarking technique in a similar way as shown in the previous work [25–27]. That is, WIS can replace the least significant bits of M
i with τ
i. By doing so, the communication cost is reduced and hence the energy consumed by the frame-transmitting process is saved.


### 5.4. Discussions on the Applicability of PKDIP on Realistic Sensors

The CPU speed of most realistic sensors is typically lower than that of the Intel i7 CPU, resulting in higher computation cost. However, as discussed above, the ratio among various cryptographic operations is the same on different CPUs. So, the computation costs of PKDIP can be lower than those of hash-function-based schemes on realistic sensors too.PKDIP requires the WIS to storen
+
1 private keys (i.e., s
k
r
,
s
k
1
,
…
,
s
k
n), resulting in higher storage cost than those of current schemes. From Section 3.3, it can be seen that the total length of those private keys is the same as that of one image frame. This implies the WIS needs to use KB-level memory to store those keys. In contrast, in the current scheme [27], the WIS needs to have KB-level memory to store at least one image frame too. Therefore, though PKDIP requires a little more memories, its storage cost is at the same level as that of current schemes.From the above discussions, it can be seen that PKDIP is feasible to be deployed on realistic sensors.


## 5.1. Investigation of Basic Cryptographic Operations

We investigated the time costs of basic cryptographic operations using the OPENSSL library [34]. The results are shown in Table 1 (note that when processing a long image frame, SHA1 will split it into multiple 64-byte blocks and perform a set of permutation operations on each block. Therefore, in Table 1, the time cost for SHA1 is the time for each 64-byte data).Table 1
Time costs of basic cryptographic operations (unit:μs).
T
p
T
sm
T
h
T
mm
8120.1
329.4
0.5
0.1
T
p: time cost of Tate pairing; T
sm: time cost of scalar multiplication; T
h: time cost of SHA1 per 64-byte data; T
mm: time cost of MontMM.From Table1, it can be seen that (i) the time cost of scalar multiplication is significantly higher than those of SHA1 and MontMM, because T
sm
/
T
h
=
329.4
/
0.5
=
658.8 and T
sm
/
T
mm
=
329.4
/
0.1
≈
3.3
×
1
0
3. (ii) The time cost of SHA1 is much higher than that of MontMM, because T
h
/
T
sm
=
0.5
/
0.1
=
5. These two results imply that (i) if a public-key-based scheme only uses the T
sm operation for generating MACs, the signing cost will be quite higher than those of hash-function-based schemes. (ii) However, if a public-key-based scheme uses both T
sm and T
mm operations for generating MACs, the signing cost may be lower than hash-function-based schemes. This is because each data block is processed by one highly efficient T
m
m operation, and multiple data blocks are processed by only two time-consuming T
s
m operations.


## 5.2. Comparison of Computation Costs

The computation costs of WIS and EU are defined as the total time of cryptographic operations inG
e
n
S
i
g and V
e
r
S
i
g algorithms, respectively. In Table 2, we mainly compare the computation costs between PKDIP and Kamel’s scheme [27], because other hash-function-based schemes [20–26] enjoy similar efficiency to Kamel’s scheme [27].Table 2
Comparison of computation costs (unit:μs).
PKDIP
Kamel’s scheme [27]
T
WIS
2
T
sm
+
T
h
+
L
20
T
mm  =
0.005
L
+
659.3
L
64
T
h
=
0.008
L
T
EU
L
20
+
1
T
p
+
L
20
T
sm
+
T
h  =
422.5
L
+
8120.1
L
64
T
h
=
0.008
L
T
WIS: computation cost on the WIS; T
EU: computation cost on the EU; L: frame length in byte.From Table2, the following can be seen.(1) PKDIP Fulfills Requirement (4) of Section1. This is illustrated by the following three scenarios. (i) Scenario 1: for long image frames, the signing cost of PKDIP can be much lower than those of hash-function-based schemes, because lim
L
→
∞
⁡
(
0.005
L
+
659.3
)
/
0.008
L
=
0.625
<
1. (ii) Scenario 2: for more than 220.0 KB image frames, the signing cost of PKDIP is more efficient than hash-function-based schemes. This conclusion can be arrived at by solving the equation 0.005
L
+
659.3
=
0.008
L
⇒
L
=
659.3
/
0.008
-
0.005
=
220.0 KB. (iii) Scenario 3: for tens-of-KBs-level image frames, the signing cost of PKDIP and those of hash-function-based schemes are at the same level. For example, setting L
=
50 KB, we get that the signing costs of PKDIP and hash-function-based schemes are 909.3 μs and 400 μs, respectively (i.e., they are both hundreds of microseconds). In summary, when processing image frames with the length of hundreds and thousands of KBs, PKDIP is much more efficient than hash-function-based schemes on the WIS’s side. Additionally, when processing image frames with the length of tens of KBs, PKDIP and hash-function-based schemes enjoy similar efficiency on the WIS’s side.(2) PKDIP Fulfills Requirement (5) of Section1. For example, if L
=
100 KB, the verification cost of PKDIP is 42 s (i.e., the verification cost is at second level). Currently, the clock frequencies of most computers are at GHz level (i.e., similar to our experimental environment). Therefore, PKDIP is suitable for being deployed on most computers. Moreover, since the EU (i.e., the computing center) is typically composed of thousands of computers and processors, it can distribute the verification work to tens of computers or processors. In this case, the verification cost can even be less than one second.


## 5.3. Discussions on the Communication Cost of PKDIP

The communication cost of PKDIP is defined as the total length of frames and MACs transmitted between WIS and EU. The frame length can be shortened by image compression algorithms, which is out of scope of this paper. The MAC length of PKDIP (i.e., length ofτ
i) is equal to the length of the elliptic curve point, regardless of the length of image frames. For example, if the curve is 160 bits, the MAC length will be 160
∗
2
=
320 bits. Compared with the frame length, this MAC length can be omitted. Therefore, PKDIP fulfills requirement (6).Further, to reduce the communication cost, WIS can use the watermarking technique in a similar way as shown in the previous work [25–27]. That is, WIS can replace the least significant bits of M
i with τ
i. By doing so, the communication cost is reduced and hence the energy consumed by the frame-transmitting process is saved.


## 5.4. Discussions on the Applicability of PKDIP on Realistic Sensors

The CPU speed of most realistic sensors is typically lower than that of the Intel i7 CPU, resulting in higher computation cost. However, as discussed above, the ratio among various cryptographic operations is the same on different CPUs. So, the computation costs of PKDIP can be lower than those of hash-function-based schemes on realistic sensors too.PKDIP requires the WIS to storen
+
1 private keys (i.e., s
k
r
,
s
k
1
,
…
,
s
k
n), resulting in higher storage cost than those of current schemes. From Section 3.3, it can be seen that the total length of those private keys is the same as that of one image frame. This implies the WIS needs to use KB-level memory to store those keys. In contrast, in the current scheme [27], the WIS needs to have KB-level memory to store at least one image frame too. Therefore, though PKDIP requires a little more memories, its storage cost is at the same level as that of current schemes.From the above discussions, it can be seen that PKDIP is feasible to be deployed on realistic sensors.


## 6. Conclusion

In this paper, we have identified the characteristics of data integrity protection for wireless image sensors and concluded 6 properties that a secure and efficient data integrity protection scheme for wireless image sensors should satisfy. Moreover, we have proposed a novel public-key-based protocol named PKDIP. The protocol satisfies a set of important requirements which have not been addressed by earlier works. The experimental results show that the proposed approach can even be much more efficient than hash-function-based schemes.



---

*Source: 570185-2015-06-25.xml*