VP 2 RQ: Efficient verifiable privacy-preserving range query processing in two-tiered wireless sensor networks

Abstract

In the field of wireless sensor networks, the secure range query technique is a challenging issue. In two-tiered wireless sensor networks, a verifiable privacy-preserving range query processing method is proposed that is based on bucket partition, information identity authentication, and check-code fusion. During the data collection process, each sensor node puts its collected data into buckets according to the bucket partition strategy, encrypts the non-empty buckets, generates the check-codes for the empty buckets, and fuses them. Then, the check-codes and the encrypted buckets are submitted to the parent node until they reach the storage node. During query processing, the base station converts the queried range into the interested bucket tag set and sends it to the storage node. The storage node determines the candidate-encrypted buckets, generates the check-code through code fusion, and sends them to the base station. The base station obtains query results and verifies the completeness of the result with the check-code. Both the theoretical analysis and experimental results show that verifiable privacy-preserving range query is capable of protecting the privacy sensor data, query result, and query range, which also supports the completeness verification of the query result. Compared to existing methods, verifiable privacy-preserving range query performs better on communication cost.

Keywords

Two-tiered wireless sensor networks privacy-preserving completeness verification range query bucket partition

Introduction

In recent years, the emerging technologies such as Internet of things (IoT) technology, cloud computing,^1–4 image recognition,^5,6 and video processing^7,8 have developed rapidly. The wireless sensor networks (WSNs), as one of key technology in IoT technology, have been widely applied in various fields, such as battlefield surveillance, environment monitoring, and health monitoring. Based on the traditional multi-hop sensor network, the two-tiered WSN⁹ introduced the storage node (S_M) as the intermediate; the architecture of its model is shown in Figure 1, in which the calculation, storage, and energy resources of the S_M are sufficient, and it is responsible for collecting and storing the data from the adjacent sensor nodes and executing the query request from the base station (BS). Due to limited resources, the sensor node is only in charge of collecting data and sending it to the adjacent S_M. The advantages of two-tiered WSNs mainly include the following: the sensor node only needs to submit the data to the adjacent S_M, which can reduce the transmission energy consumption and extend the lifetime; the data are stored in the S_M, and the sensor node does not need to store the data, which can reduce the manufacturing cost of the node; when the query command is executed at the BS, it only needs to communicate with the S_M, which can improve the execution efficiency of query processing (QP).^9,10

Figure 1.

Model of two-tiered wireless sensor network.

The development and application of WSNs face various security threats, including disclosure of privacy and compromised data. Security problems are particularly more prominent in two-tiered WSNs because the S_M not only stores a large amount of sensor data but also executes the query request from the BS, and due to the importance of its location, it is a primary target. Once the S_M is compromised, the attacker can use the S_M to spy on the data privacy in the network, for example, illegally obtain sensor data, QP results, and the query intentions of upper-layer user or application. In addition, the attacker can also use the S_M to tamper with or falsify query results and data to mislead or disturb the upper-layer application or decision. Therefore, studying secure data QP technology with privacy protection and query result completeness verification has important realistic significance for two-tiered wireless networks.

Due to the universal application of range queries among current studies of QP technology for two-tiered WSNs, range QP technology with privacy-preserving and query result completeness verification has attracted a great deal of attention.^11–22 However, current studies show deficiencies in terms of network communication cost, although the communication cost directly impacts the lifetime and application costs of the entire network. The objective of this article is to protect the privacy of sensor data, query results, and the query range and to verify the completeness of query results in two-tiered WSNs; thus, a verifiable privacy-preserving range query (VP²RQ) method based on bucket partition is proposed in this article.

The main contributions of this article include the following: (1) by introducing bucket partitioning and symmetric encryption technology, plaintext data can be hidden in encrypted buckets, and the Hash-based message authentication coding (HMAC) method can be used to build the check-code information that supports the completeness verification of the query result; (2) during the process in which the sensor node uploads data to the S_M, fusion processing of the check-code is conducted in accordance with the bucket tag to reduce the communication cost of data. Thus, data collection (DC) protocol and QP-protocol are proposed to realize the VP²RQ; (3) under this protocol framework, efforts are made to analyze the privacy security, query result verifiability, and network communication cost of the VP²RQ method; and (4) experimental comparison and analysis are also conducted by comparing this method with the existing technology and methods from the perspective of the communication cost of the sensor node within the cell and the communication cost between the S_M and BS. The theoretical analysis and experiment results show that compared with existing methods, VP²RQ has better performance in terms of communication cost efficiency.

In section “Related works” of this article, related studies are introduced. Related models and problem description are provided in section “Models and problem statement,” and the bucket partition method is introduced in section “Bucket partition mechanism.” In section “VP²RQ protocols,” the specific protocol content of VP²RQ is provided, and analysis of the security and communication cost is conducted. The experimental results and analyses are presented in section “Performance evaluation,” and the article is summarized in section “Conclusion.”

Related works

Researches on the secure range query technologies for two-tiered WSNs mainly include the following two types:

Secure range queries^11–13 based on the bucket partition.^23,24 These methods rely on same assumption: sensor nodes and the BS share the bucket partition strategy; that is, the mapping relation between the partitioned bucket intervals and the random tags is shared by the sensor nodes and BS and is unknown to the S_M. The randomness of tags ensures the security of the bucket partition strategy. In Sheng and Li,¹¹ the bucket partition is first introduced in the VP²RQ method, denoted as S&L. In S&L, sensor nodes put their collected data into buckets according to the bucket partition strategy. For any bucket, if it is empty, a code is generated; otherwise, the bucket is encrypted. Then, the encrypted buckets and codes are submitted to the S_M. When the BS applies a range query, it determines the smallest bucket set covered by the queried range and then sends the corresponding bucket tags as the query command to the S_M. And, the S_M returns the corresponding encrypted data and codes to the BS in accordance with the bucket tags in the query command. Finally, the BS obtains the query result by decrypting the encrypted data and verifies the completeness of the query result using the received codes. Because S&L requires generating one code for each empty bucket and transferring it to the S_M, with the increase in the number of empty buckets, the communication cost of the sensor nodes rapidly grows in large-scale sensor networks. To reduce the communication cost of sensor nodes, an optimized method (denoted as NSC) based on a spatial–temporal crosscheck is proposed in Shi et al.^12,13 This method uses the bitmap index to replace the codes in S&L, so that the communication cost of the sensor node is saved; however, the communication cost between the S_M and BS is higher than that in S&L.

Secure range queries based on secure comparison.^14–22 The basic idea of these methods is that the sensor nodes encrypt their collected data and generate the corresponding secure-comparing-codes, which can be used to compare the encrypted data. The encrypted data and the corresponding secure-comparing-codes are uploaded to the S_M. When the BS processes a range query, it first transforms the queried range into the secure-comparing-codes and then sends them to the S_M as a query command. Then, the S_M can determine the qualified encrypted data that satisfy the query range by performing the secure comparison scheme between the corresponding secure-comparing-codes, and the S_M returns the qualified encrypted data to the BS. After decryption, the BS can obtain the query result. In Chen and Liu,^14,15 a secure range query method named SafeQ is proposed based on the prefix membership verification (PMV)^25,26 mechanism. SafeQ utilizes the PMV coding technique, which can realize the secrete comparison between the collected data and queried range without their plaintext; in this way, SafeQ can determine whether the corresponding encrypted data satisfy the query range. To achieve the query result completeness verification, SafeQ introduces the neighborhood chain mechanism during data encryption and adopts the Bloom-Filter²⁷ to reduce the cost of the secure-comparing-codes. In Bu et al.,¹⁶ an efficient range query method named SEF is proposed. Order-preserving symmetric encryption is employed in SEF to preserve privacy. In addition, a novel data structure called the Authenticity & Integrity tree is proposed to preserve integrity, and the NAND flash is used for the first time to achieve high storage utilization and QP efficiency in this article. In Tsou et al.,¹⁷ a range query method named EQ is proposed for protecting data privacy and completeness. The EQ method presents an order encryption mechanism by adopting stream cipher to protect the privacy of data and uses a data structure of the XOR-linked list to verify the completeness of the query result. In Nguyen et al.,¹⁸ a novel model based on a d-disjunct matrix, an order function, and a permutation function is proposed to preserve the privacy of sensitive data and the completeness of result. In Yi et al.,¹⁹ a secure range query protocol named QuerySec is proposed, which uses the order-preserving function to realize the secret comparison between the collected data and the query range. By embedding the link watermarking information into the encrypted data block, QuerySec can realize the completeness verification of the query result. The performance evaluations of the QuerySec show that it is more efficient in terms of communication cost than SafeQ. ESRQ, which was proposed in Zhang et al.,²⁰ also realizes an efficient range query by adopting Bloom-Filter to generate the encoding code for privacy-preserving and completeness verification. An extended version of ESRQ is provided in Zhang et al.²¹ that expands the focus on collusion attacks on range queries in two-tiered WSNs. To reduce the communication cost during the query, secRQ is proposed in Dong et al.,²² as it has a very low false positive rate. secRQ adopts generalized inverse matrices and the distance-based range query mechanism to protect the security of data and proposes a mutual verification scheme to verify the completeness of the query result.

Comparing secure range query methods (1) and (2), we can observe the following: (1) in terms of security, the former mainly depends on the bucket partition strategy, while the latter depends on the complexity of the secure comparison functions; (2) if the same encryption is adopted, the encrypted data produced by the former are smaller than the latter; (3) in terms of the communication cost of sensor nodes, which affects the network lifetime, the former depends on the granularity of bucket partition and the distribution of collected data in buckets, while the latter relies on the quantity of the collected data items and the corresponding secure-comparing-codes.

Models and problem statement

Network model

We use a similar network model used in previous works,^11–22 as shown in Figure 1. The network consists of multiple cells, while each cell consists of one storage node S_M and n sensor nodes Γ = {s₁, s₂, …, s_n}. The S_M is a type of power node with sufficient computation, storage, and energy and is responsible for storing the data collected by all sensor nodes within its cell, and it is also responsible for executing the query requests from the BS and returning the query result. On the other hand, due to limited resources, the sensor node is only responsible for collecting data and sending it to the S_M within its cell. The S_M has the location information for all sensor nodes within its cell, while the sensor nodes have the location information of the S_M and the neighbor sensor nodes within the scope of one hop, and the BS has the topological information for the entire network.

In a cell, with the S_M as the storage node, the tree routing topology²⁸ between the sensor node and the S_M is built in accordance with the TAG protocol.²⁹ When a sensor node uploads its collected data to the S_M, it transmits hop by hop in accordance with the routing tree, which is finally gathered to S_M. As shown in Figure 2, it is a routing tree with the S_M as the storage node, and the data collected by sensor nodes s₁, s₂, and s₃ within the epoch t are D₁, D₂, and D₃, respectively; during the data uploading process, s₂ and s₃ would transmit D₂ and D₃ to the parent node s₁; then, s₁ combines the received D₂, D₃, and its own D₁ and transmits it to the S_M.

Figure 2.

Tree routing based on TAG.

Range query model

A range query Q can be described by the following triple

Q = (t, c, [low, high])

where t, c, and [low, high] are the epoch number, network cell, and range, respectively. The query result of Q refers to all data in the range [low, high] collected by the sensor node within epoch t in cell c. Obviously, the above query only involves one epoch and one cell, and we name it atomic range query. A complicated range query involving multiple epochs and/or multiple cells can be divided into multiple atomic queries, and its query result is the union of the query results of those atomic queries. As a result, this article focuses on the atomic range query.

Problem statement

In two-tiered sensor network, the S_M stores the data collected by all sensor nodes within its cell, and it is in charge of responding to the query requests from the BS, computing and returning the query result. If no protection is conducted, once the S_M is compromised by malicious attackers, the collected data, the query results, and the query interests are threatened. Specifically, the attacker could manipulate the compromised S_M for the following reasons:

To obtain the data collected by any sensor node at any moment within the cell and determine the query result in accordance with [low, high] to spy on the privacy of the collected data and the query result.

To obtain the query range [low, high] in the query command to spy on the privacy of upper-layer user’s query intentions.

To tamper or falsify the query result during QP and disturb the completeness of the query result to disturb and mislead the upper-layer application or decision.

Although the sensor node could also be captured, because the amount of data generated by a single sensor node is small compared to the entire network and although a few sensor nodes are captured, it will not have significant impact on the entire network.⁷ Therefore, this article focuses on the protections measured for the situation where the S_M is compromised. Similar to the existing works,¹¹ we also assume that the BS and sensor node can be trusted and that the S_M cannot be trusted and it has the intention of spying on, destroying, or falsifying data.

To achieve a VP²RQ in two-tiered WSNs, efforts must be made to ensure that QP satisfies the following:

For data collected by any sensor node in the network and the query results, only the BS can obtain its value in plaintext, while the S_M cannot.

For the query range [low, high] in the query command, because it reflects the query objective and intention of the upper-layer user, it is also the privacy information that requires protection. Therefore, it is necessary to ensure that the S_M cannot obtain the real values of low and high.

The BS can verify the query result returned by the S_M, which means any falsified or incomplete result caused by any malicious tampering or falsification will be detected.

In addition, this article adopts two metrics of communication cost to conduct a performance evaluation and analysis of the QP method:

Sensor node communication cost (C_I). The communication cost generated by all sensor nodes to submit their collected data to the S_M in the cell within an epoch.

QP communication cost (C_Q). The communication cost generated between the BS and the S_M to process one query, which includes the two parts of the BS sending the query command and the S_M feeding back the query result.

Bucket partition mechanism

To realize the VP²RQ, this article introduces the bucket partition method,²³ which is used in QP for encrypted database.

Definition 1

Bucket partition. For a given domain $D = [α, β]$ , divide it into m continuous and non-overlapping intervals [σ₁, σ₂), [σ₂, σ₃), …, [σ_m, σ_m₊₁], where α = σ₁ and β = σ_m₊₁, which satisfies the following:

$[σ_{1}, σ_{2}) \cup [σ_{2}, σ_{3}) \cup \dots \cup [σ_{m}, σ_{m + 1}] = D$

$\forall i, j \in [1, m] \land i \neq j \to [σ_{i}, σ_{i + 1}) [σ_{j}, σ_{j + 1}) = \emptyset$

where [σ_i, σ_i+₁) is a bucket, while α and β are the lower and upper bound of D, respectively.

Definition 2

Tag. For any bucket $[σ_{i}, σ_{i} + 1) D$ , there is a mapping relation f

f : [σ_{i}, {σ_{i}}_{+ 1}) \to T_{i}, i \in [1, m], T_{i} \in N^{+}

which satisfies the following

\forall i, j \in [1, m] \land i \neq j \to T_{i} \neq T_{j}

T_i is the corresponding tag of bucket [σ_i, σ_i+₁), which could be a pseudo-random number in practice. For convenience of description, we use $T_{i}^{*}$ to represent the corresponding bucket with the tag of T_i.

For example, the domain [0, 30] shown in Figure 3 is divided into three buckets of [0, 10], [10, 20], and [20, 30], and the corresponding tags are T₁, T₂, and T₃, respectively.

Figure 3.

Example of bucket partition.

There are many schemes to realize a bucket partition, such as equi-width, equi-depth, and max-diff partitions.²³ And, Figure 3 shows an example of an equi-width partition. Bucket partition methods differ in terms of complexity, security, and space-time performance. Because the bucket partition strategy is not a focus of this article, we will not elaborate on it and refer to Hore et al.²⁴ for a related analysis and algorithm. To make our article easier to follow, we summarize the primary notations used in this article as shown in Table 1.

Table 1.

Primary notations.

Notation	Description
Q,Q′	Real range query command and the query command sent to storage nodes
t	Epoch
s_i	Sensor node
S_M	Storage node
low, high	Lower bound and upper bound of query range
m	Number of buckets
NDB, EDB	Non-empty bucket set and an empty bucket set
D_i	Data set collected by sensor node s_i within t
$D_{i, j}^{1}, D_{i, j}^{0}$	$D_{i, j}^{1} \in NDB$ , $D_{i, j}^{0} \in EDB$ , a non-empty bucket and empty bucket with tag T_j
T_j	Tag for bucket D_i,j
Ψ_i, Θ_i	Non-empty bucket tag set and empty bucket tag set of sensor node s_i
$ℑ_{j}^{1}, ℑ_{j}^{0}$	Set of tags for non-empty and empty bucket among D_j
h_i,v	Check-code for empty buckets, which means no data collected by s_i in bucket T_v
k_i,t	Secret key of s_i, $()_{k_{i, t}}$ means an encryption function using k_i,t*
g_i,t	HMAC key of the sensor node s_i, $()_{g_{i, t}}$ means an encryption function using g_i,t*
⊕	XOR operation, $\oplus_{i \in {1, 2, \dots, n}} x_{i}$ represents $x_{1} \oplus x_{2} \oplus \dots \oplus x_{n}$
ℜ	Query result
C_I	Communication cost for sensor nodes
C_Q	Communication cost for query processing

HMAC: Hash-based message authentication coding.

VP²RQ protocols

Definitions and assumptions

Assume that the domain of sensor data in the network is D, divide it into m buckets, and the corresponding tag set of various buckets is Ω = {T₁, T₂, …, T_m}.

Definition 3

For any range $[a, b] \subseteq D$ , the minimum coverage bucket set is the minimum set of buckets covering this interval. The set of corresponding tags is named the minimum coverage tag set, which is denoted as tag([a, b]), and it satisfies the following

[a, b] \subseteq ⋃_{T_{i} \in tag ([a, b])} T_{i}^{*}

(1)

\forall T_{i} \in tag ([a, b]) \to [a, b] ⊈ ⋃_{T_{j} \in (tag ([a, b]) - T_{i})} T_{j}^{*}

(2)

For example, in the bucket partition example shown in Figure 3, the corresponding minimum coverage bucket set of [15, 25] is {[10, 20], [20, 30]], and the minimum coverage tag set is tag ([15, 25]) = {T₂, T₃}.

Assume that the data set collected by sensor node s_i within t is D_i, and after the bucket partition, the data set in bucket T_j is denoted as D_i,j. If D_i,j ≠ ∅, it is called the non-empty bucket, which is denoted as $D_{i, j}^{1}$ ; otherwise, it is called the empty bucket, which is denoted as $D_{i, j}^{0}$ . The tag sets of non-empty bucket and empty bucket among D_i are denoted as $ℑ_{i}^{1}$ and $ℑ_{i}^{0}$ , respectively. Then, we have the following observations:

\begin{array}{l} Observation 1 : \cup_{T_{j} \in ℑ_{i}^{1}} D_{i, j}^{1} = D_{i} \\ Observation 2 : ℑ_{i}^{1} \cup ℑ_{i}^{0} = Ω \end{array}

We assume that the bucket partition strategy is only shared by the sensor node and BS, while the S_M has nothing about it. It is difficult for the S_M to reverse deduce the corresponding range based on a given tag. In addition, k_i,t and g_i,t represent the encryption key and HMAC key of the sensor node s_i within the epoch t, respectively, k_i,t = key₁(id(s_i), t, k_i,t₋₁) and g_i,t = key₂(id(s_i), t, g_i,t₋₁). Here, key₁ and key₂ are different key generators, and the initial keys k_i,0 and g_i,0 and the key generators are only shared with the BS. The data encrypted using k_i,t are denoted as $(*)_{k_{i, t}}$ , while the HMAC code generated using g_i,t is denoted as $H_{g_{i, t}} (*)$ . Here, encryption is used to protect data privacy, while the HMAC code is used to build the check-code information for completeness verification.

Next, to realize VP²RQ, we provide two core protocols: the first is the DC-protocol, in which the sensor nodes transmit the collected data to the S_M for storage and the second is the QP-protocol, in which the BS and the S_M cooperate to complete the query task.

DC-protocol

In the DC-protocol, the sensor node conducts a bucket partition to the collected data within each epoch and then encrypts the non-empty buckets and calculates the check-codes of the empty buckets. During the data submission route path from the sensor nodes to the S_M, the check-codes within the same bucket are fused to reduce the communication cost. We provide details of the DC-protocol as follows.

According to the DC-protocol, we can see that the intermediate sensor node fuses check-codes uploaded by the child node and generated by itself that has the same tag; in this way, the number of check-codes that needs to be transmitted is reduced. In the meantime, the S_M will also fuse all received check-codes in accordance with the tag to form the only check-code for each tag; and in this way, it can reduce the space storage cost in the S_M.

In addition, it is easy to conclude that Properties 2 and 3 hold in accordance with Protocol 1:

Property 2. Within an epoch t, assume that the number of check-codes submitted by the sensor nodes s_i and s_j are, respectively, u_i and u_j; if s_j is in the path of s_i transmitting data to the S_M, then 0 ≤ u_i ≤ u_j ≤ m, where m is the number of buckets that domain D is divided into.

Property 3. Within an epoch t, assume that the number of check-codes finally stored in the S_M is u; then, 0 ≤ u ≤ m.

As shown in the above properties, in the path from any sensor node to the S_M, the number of check-codes submitted by various nodes exhibits a non-decreasing trend, but they should not exceed the number of bucket partitions, and this is also the case for the number of check-codes stored in the S_M.

Protocol 1. Data collection protocol (DC-protocol)

For any sensor node s_i, assume that its collected data set is D_i. The following steps are applied by s_i.

Step 1. Conduct the bucket partition to D_i. Assume that the non-empty bucket set and empty bucket set are NDB and EDB, we then have the following

\begin{array}{l} N D B = {D_{i, j}^{1} | T_{j} \in ℑ_{j}^{1}} \\ E D B = {D_{i, j}^{0} | T_{j} \in ℑ_{i}^{0}} \end{array}

Step 2. For any non-empty bucket $D_{i, w}^{1} \in NDB$ whose tag is T_w, s_i uses the key k_i,t to encrypt $D_{i, w}^{1}$ , and the encrypted bucket is $(D_{i, w}^{1})_{k_{i, t}}$ . For any empty bucket $D_{i, v}^{0} \in EDB$ whose tag is T_v, the HMAC algorithm and key g_i,t are used to calculate the check-code h_i,v, which represents that there is no data collected by s_i in bucket T_v

h_{i, v} = H_{g_{i, t}} (T_{v})

Step 3. In accordance with whether s_i is a leaf node, s_i constructs corresponding data information and transmits it to the parent node until it reaches the S_M. The detailed process is as follows:

1. If s_i is a leaf node, assume that s_j is the parent node of s_i; then, s_i generates and sends the following information to s_j, in which id(s_i) refers to the ID of s_i

s_{i} \to s_{j} : < t, id (s_{i}), {T_{w}, {(D_{i, w}^{1})}_{k_{i, t}} | T_{w} \in ℑ_{i}^{1}}, {T_{v}, h_{i, v} | T_{v} \in ℑ_{i}^{0}} >

2. If s_i is the intermediate node, assume that its parent node is s_j, and the set of its descendant nodes is $ϒ_{i}$ ; then, s_i gathers the encrypted buckets received from the descendant nodes and its own encrypted buckets and conducts the XOR operation to fuse the check-codes with the same tag. Next, s_i sends the following information to s_j

\begin{matrix} s_{i} \to s_{j} : < t, id (s_{i}), {T_{w}, {(D_{i, w}^{1})}_{k_{i, t}} | T_{w} \in ℑ_{i}^{1}} \\ ⋃_{s_{ρ} \in ϒ_{i}} {id (s_{ρ}), {T_{δ}, {(D_{ρ, δ}^{1})}_{k_{ρ}, t} | T_{δ} \in ℑ_{ρ}^{1}}} \\ {T_{v}, \oplus_{s_{λ} \in ϒ_{i} \cup {s_{i}}} h_{λ, v} | T_{v} \in ⋃_{s_{ρ} \in ϒ_{i} \cup {s_{i}}} ℑ_{ρ}^{0}} > \end{matrix}

In which, ⊕ refers to the XOR operation, and $\oplus_{i \in {1, 2, \dots n}} x_{i}$ represents $x_{1} \oplus x_{2} \oplus \dots \oplus x_{n}$ .

After receiving the data information transmitted from all sensor nodes in the cell, the S_M gathers the encrypted buckets with the same tag and fuses the check-codes with the same tag to obtain the only check-code of this tag. Finally, the following data information is formed, which is stored

\begin{matrix} S_{M} : < t, T_{1}, ⋃_{s_{i} \in Γ \land T_{1} \in ℑ_{i}^{1}} {id (s_{i}), {(D_{i, 1}^{1})}_{k_{i, t}}}, \oplus_{s_{i} \in Γ \land T_{1} \in ℑ_{i}^{0}} h_{i, 1}, \\ \dots, \\ T_{m}, ⋃_{s_{i} \in Γ \land T_{m} \in ℑ_{i}^{1}} {id (s_{i}), {(D_{i, m}^{1})}_{k_{i, t}}}, \oplus_{s_{i} \in Γ \land T_{m} \in ℑ_{i}^{0}} h_{i, m} > \end{matrix}

To clearly describe the DC-protocol, we give an example. Assume that the cell formed by sensor nodes s₁, s₂, s₃, and the S_M is as shown in Figure 4, and that the bucket partition strategy in Figure 3 is adopted. Within an epoch t, assume that the data collected by s₁, s₂, and s₃ are {16, 24}, {5, 12}, and {6, 17}, respectively.

Figure 4.

Example of DC-protocol.

According to the DC-protocol, s₁, s₂, and s₃ transmit the following data information

\begin{matrix} s_{1} \to s_{3} : < t, id (s_{1}), T_{1}, H_{k_{1, t}} (T_{1}), T_{2}, {16}_{k_{1, t}}, T_{3}, {24}_{k_{1, t}} > \\ s_{2} \to s_{3} : < t, id (s_{2}), T_{1}, {5}_{k_{2, t}}, T_{2}, {12}_{k_{2, t}}, T_{3}, H_{g_{2, t}} (T_{3}) > \\ s_{3} \to S_{M} : < t, id (s_{3}), T_{1}, {6}_{k_{3, t}}, H_{g_{1, t}} (T_{1}), T_{2}, {17}_{k_{3, t}}, \\ T_{3}, H_{g_{3, t}} (T_{3}) \oplus H_{g_{2, t}} (T_{3}) \\ id (s_{1}), T_{2}, {16}_{k_{1, t}}, T_{3}, {24}_{k_{1, t}} \\ id (s_{2}), T_{1}, {5}_{k_{2, t}}, T_{2}, {12}_{k_{2, t}} > \end{matrix}

Finally, the data collected and stored by the S_M is as follows.

< t, T_{1}, H_{g_{1, t}} (T_{1}), {5}_{k_{2, t}}, {6}_{k_{3, t}}, T_{2}, {16}_{k_{1, t}}, {12}_{k_{2, t}}, {17}_{k_{3, t}}, T_{3}, {24}_{k_{1, t}}, H_{k_{2, t}} (T_{3}) \oplus H_{k_{3, t}} (T_{3}) >

Protocol 2. Query processing protocol (QP-protocol)

Assume that the current query command is Q = (t, c, [low, high]); the BS cooperates with the S_M to complete query processing as follows:

The BS calculates the corresponding interested bucket tag set tag([low, high]) of [low, high] according to the bucket partition strategy. It then constructs the secure query command Q′ = (t, c, tag([low, high])) and sends it to the S_M, that is, as follows

BS \to S_{M} < t, c, tag ([low, high]) >

After the S_M receives the secure query command Q′, it first determines the candidate-encrypted buckets that satisfy the query requirement, t, all encrypted buckets whose tags are in tag([low, high]); then, it fuses all the corresponding check-codes into the only result check-code; finally, it generates the following message to submit to the BS

\begin{matrix} S_{M} \to BS : < t, ⋃_{T_{j} \in tag ([low, high])} {T_{j}, ⋃_{s_{i} \in Γ \land T_{j} \in ℑ_{i}^{1}} {id (s_{i}), {(D_{i, j}^{1})}_{{k_{i}}_{, t}}}} \\ \oplus_{s_{i} \in Γ \land T_{j} \in (tag [low, high] \cap ℑ_{i}^{0})} h_{i, j} > \end{matrix}

When receiving the response message from the S_M, the BS utilizes the keys shared with sensor nodes to decrypt the encrypted buckets. Assume that the obtained plaintext data set is denoted as D_Q. Then, we can determine the non-empty bucket tag set Ψ_i of any sensor node s_i in tag([low, high]) where $Ψ_{i} \subseteq tag ([low, high])$ , so the empty bucket tag set of s_i is Θ_i = tag([low, high])−Ψ_i. In addition, assume that the result check-code in the received message is h_Q. It is apparent that if each sensor node has data in each corresponding bucket of tag([low, high]), then h_Q does not exist; otherwise, h_Q uniquely exists. Here, the BS calculates and verifies the query result in the following steps:

Step 1. Obtaining the query result: The data set obtained from D_Q that satisfies the requirement of [low, high] is the query result, which is denoted as; then

ℜ = {d_{i} | d_{i} \in D_{Q} \land d_{i} \in [low, high]}

Step 2. Verifying the query result: The BS uses the decrypted data items and the HMAC key shared with sensor nodes to perform verification. Only if the following three conditions simultaneously hold, then ℜ satisfies the completeness requirement; otherwise, ℜ is abnormal:

1. Uniqueness. For the non-empty bucket $D_{i, j}^{1}$ of any sensor node s_i at any tag, it uniquely exists in the response message.

2. Coverability. All plaintext data items obtained from the received encrypted buckets are in the minimum coverage bucket of [low, high], that is, as follows

\forall d_{i} \in D_{Q} \to d_{i} \in ⋃_{T_{j} \in tag ([low, high])} T_{j}^{*}

3. Correctness. For any sensor node s_i, if its empty bucket tag set Θ_i is null, the result check-code must not exist in the response message; otherwise, the re-calculated result check-code should be completely consistent with h_Q, that is, as follows

h_{Q} = \oplus_{s_{i} \in Γ} \oplus_{T_{j} \in Θ_{i}} H_{g_{i, t}} (T_{j})

QP-protocol

Definition 4

Interested bucket tag set. Assume that the query range in query command is [low, high]; then, the minimum coverage bucket tag set tag([low, high]) is called the interested bucket tag set.

During QP, the BS first transfers the query range [low, high] into the interested bucket tag set and then sends the interested bucket tag set to the S_M as the query command. The S_M determines the candidate-encrypted buckets in accordance with the bucket tag set, fuses related check-codes, and then sends it to the BS. Then, the BS can determine the query result by decrypting the candidate-encrypted buckets, and the completeness of the query result can be verified by the received check-code. Detailed procedures are shown in Protocol 2.

From the QP-protocol, we can see that if all sensor nodes have data in each corresponding bucket of tag([low, high]), it is not necessary for the S_M to return a check-code; otherwise, it only needs to return the only fused check-code. During the query result verification phase, the uniqueness condition is used to verify whether all non-empty buckets received by BS are unique; the coverability condition is used to verify whether all these non-empty buckets satisfy the range requirement of the query, while the correctness condition is used to check the correctness of the result check-code. Under the simultaneous effects of these three conditions, any abnormal query result caused by the malicious behavior of tampering or falsification will be detected.

Based on the example shown in Figure 4, we further discuss the QP-protocol. Assume that the query command is Q = (t, c, [15, 25]); the BS will determine the corresponding interested bucket tag set of [15, 25] to be {T₂, T₃}; then, it will construct the secure query command <t, c, {T₂, T₃}> and send it to S_M; S_M will return the candidate-encrypted buckets and the result check-code to BS, that is, as follows

S_{M} \to B S : < T_{2}, {16}_{k_{1, t}}, {12}_{k_{2, t}}, {17}_{k_{3, t}}, T_{3}, {24}_{k_{1, t}}, H_{g_{2, t}} (T_{3}) \oplus H_{g_{3, t}} (T_{3}) >

After receiving the above message, the BS obtains the non-empty buckets with the tags of T₂ and T₃ generated by s₁, s₂, and s₃ within t by decrypting the encrypted buckets, as shown in Table 2. Then, it can be determined that the query result is $ℜ = {16, 17, 24}$ .

Table 2.

Non-empty bucket with the tags of T₂ and T₃.

Tag	s ₁	s ₂	s ₃
T ₂	{16}	{12}	{17}
T ₃	{24}	Nil	Nil

The BS verifies the completeness of ℜ by the following steps: first, it checks whether the formed non-empty buckets are unique; second, it checks whether all plaintext data {12, 16, 17, 24} obtained through decryption are within the corresponding minimum coverage buckets of tag[15, 25]), that is, $[10, 20] \cup [20, 30]$ ; finally, as the nodes s₂ and s₃ have not generated any data in bucket T₃, it will re-compute the result check-code $H_{g_{2, t}} (T_{3}) \oplus H_{g_{3, t}} (T_{3})$ and check whether this check-code is completely consistent with the received one. Only if the above three steps succeed, ℜ is the correct query result satisfying the completeness requirement.

Protocol analysis

Security analysis

1. Privacy of sensor data

During the QP of VP²RQ, when the sensor nodes transmit the collected data to the S_M, they first partition data into buckets and encrypt them where the keys are only shared with the BS. Since the bucket partition strategy is only shared by the BS and the sensor node, it is invisible to the S_M. And before being submitted to the S_M, all data items falling into the same bucket are encrypted as ciphertext blocks. The complexity of obtaining the sensor data for the S_M is similar to cracking the encryption algorithm, and it is very difficult for the S_M to obtain plaintext sensor data without knowing the bucket partition strategy and encryption key. Therefore, the privacy of sensor data can be preserved in VP²RQ.

2. Privacy of query result

The calculation of the query result is completed through the cooperation between the S_M and BS. According to the interested bucket tag set tag([low, high]) in the query command, the S_M sends all encrypted buckets whose tags belong to tag([low, high]) to the BS, and these encrypted buckets include the query result; then, the BS decrypts the received encrypted buckets to determine the final query result. Because the S_M only involves encrypted data during QP, similar to (1), it is infeasible for the S_M to obtain data items in the encrypted buckets that return to the BS; thus, it is hard to obtain the query result in plaintext. Therefore, we can see that VP²RQ can also preserve the privacy of the query result.

3. Privacy of query range

As indicated in the QP-protocol, we know that for the query range [low, high] in the query command, before sending the command, the BS will replace the plaintext range into the corresponding interested bucket tag set according to the bucket partition strategy. Without knowing the bucket partition strategy, it is very difficult for the S_M to use the tag information to recover the query range. Therefore, we have that VP²RQ can ensure the privacy of the range of the query command.

4. Completeness verification of query result

It is very difficult for a compromised S_M to break the completeness of query result without being detected by the BS since the encryption and HMAC keys of each sensor node change in every epoch and the S_M has no idea of them. Any falsifying or tampering responses of the S_M are checked by verifying the three conditions in the QP-protocol. For example, if the S_M drops some candidate-encrypted buckets, the BS will detect it through the verification of uniqueness and coverability conditions. If the S_M tampers with some candidate-encrypted buckets, the BS will check it through the verification of the coverability condition. Therefore, VP²RQ can verify the completeness of the query result.

Communication cost analysis

Since the S_M has rich energy resources, while the sensor nodes are limited, the lifetime of the network totally depends on the energy consumption of the sensor node. We all know that the energy consumption of the sensor node mainly comes from communications,³⁰ so the communication cost of sensor nodes directly affects the lifetime of network. In addition, for the S_M and BS, although they have rich energy resources, there is limited communication bandwidth between them. Less communication cost is preferable to improve the efficiency of QP. Therefore, the communication cost for QP between the S_M and BS is also important for the entire network. We will analyze the network communication cost of VP²RQ from two perspectives: the sensor node communication cost C_I and the QP communication cost C_Q.

In accordance with the DC-protocol, each sensor node must transmit the following data to the S_M: a node ID, a time epoch, some encrypted non-empty buckets, and their corresponding tags, as well as some check-codes for the empty buckets. Assume that there are n sensor nodes in the network, the length of node ID is l_id, the length of the time epoch is l_t, each node collects N data within each epoch, the range of sensor data is divided into m buckets, the length of a bucket tag is l_tag, the probability of each bucket being empty is P_e, the length of a piece of ciphertext is l_c, the length of a collected data item is l_d, the length of the HMAC check-code is l_h, and the average path between the sensor node and the S_M is L hops. Then, the communication cost C_I of sensor nodes is as follows.

C_{I} \approx n \cdot (l_{i d} + m \cdot (1 - P_{e}) \cdot l_{t a g} + N \cdot ⌈ l_{c} / l_{d} ⌉ \cdot l_{c}) \cdot L + n \cdot (m \cdot P_{e} \cdot l_{h} + l_{t})

According to the QP-protocol, in each QP, the BS will send the query command that contains the time epoch t and the interested bucket tag set tag([low, high]) to the S_M. Then, the S_M will return a response message to the BS, which has the time epoch, bucket tags, sensor node IDs, candidate-encrypted buckets, and result check-codes. Assume that the set tag([low, high]) contains δ tags; then, the probability of the corresponding bucket of each tag being empty is P_f. For each tag in tag([low, high]), there are λ sensor nodes generating non-empty buckets, and each non-empty bucket contains τ data items. Then, we have the following

C_{Q} \approx 2 l_{t} + δ \cdot (2 - P_{e}) \cdot l_{t a g} + δ \cdot (1 - P_{f}) \cdot (λ \cdot l_{i d} + τ \cdot ⌈ l_{c} / l_{d} ⌉ \cdot l_{c}) + l_{h}

Performance evaluation

We give the performance evaluation of C_I and C_Q of the proposed VP²RQ in this article through simulation and compare it with the existing methods S&L,¹¹ NSC,^12,13 QuerySec,¹⁹ and secRQ.²² We realized the VP²RQ, S&L, NSC, QuerySec, and secRQ in the simulator.³¹ Evaluations are performed on a PC with an Intel Core i3 (2.13GHz) CPU and 4 GB memory, Windows 7 64-bit operating system, Eclipse, and MATLAB. And, the Intel Lab Data set³² is used.

We assume that the length of a collected data item is 32 bits, and the equi-width bucket partition strategy and the Data Encryption Standard (DES) encryption algorithm are adopted. The default value settings of other parameters are shown in Table 3.

Table 3.

Evaluation parameters.

Parameter	Value
Area of network coverage	80 × 80
Communication radius of a sensor node	25
Number of network ID	10
Number of sensor nodes (n)	54
Number of bucket partitions (m)	50
Quantity of collected data per epoch (N)	30
Length of bucket tag/bit	32
Length of encrypted data/bit	64
Length of a HMAC code/bit	128
Length of an epoch/bit	32
Length of sensor node ID/bit	32

HMAC: Hash-based message authentication coding.

Sensor node communication cost evaluations

In each evaluation, 10 networks with random topologies denoted by different network IDs are generated. In each network, sensor nodes are randomly distributed. Then, we can determine the sensor node communication cost C_I by obtaining the average measurement of these 10 networks:

C_I versus network ID. Figure 5 shows that the C_I of VP²RQ, S&L, NSC, QuerySec, and secRQ are all uniformly distributed in different networks. The C_I of VP²RQ is significantly lower than that of the other four methods. Specifically, the average C_I of VP²RQ is the lowest, and it is approximately 12.79%, 21.58%, 29.67%, and 30.58% of S&L, NSC, QuerySec, and secRQ, respectively. The reason is that each sensor node in VP²RQ only needs to generate one check-code for each empty bucket and fuse the check-codes with the same tag, which ensures that no more than m check-codes are uploaded by each sensor node. However, in the other methods, each sensor node needs to send more codes for the query result verification.

C_I versus N. We vary the amount of data collected by a sensor node within one time slot N from 20 to 100 to test the impact of N on the performance of sensor nodes. As shown in Figure 6, C_I of the five methods all grow with the increase in N. In particular, the C_I of VP²RQ is obviously smaller than that of the others because the amount of encrypted data needed to be uploaded in the five methods all increase linearly with the increase in N, but the number of codes used for the result verification in VP²RQ is much smaller than in other methods.

C_I versus m. We vary the number of buckets m from 20 to 100 to test the impact of m on the performance of sensor nodes. In accordance with Figure 7, we can see that with the increase in m, the C_Is of QuerySec and secRQ remain the same, while the C_I of VP²RQ, S&L, and NSC increase accordingly. Among these, S&L and NSC present significant increase, while the increasing trend of VP²RQ is not that obvious, and the C_I of VP²RQ is the lowest among the five methods. The QuerySec and secRQ methods are irrelevant to the bucket partition, so the change in m does not have any impact on its C_I, unlike the other four methods based on bucket partition, because the amount of sensor data remains the same, the number of empty buckets increases with the increase in m. In VP²RQ, the fusion of check-codes with the same tag can significantly reduce the number of uploaded check-codes; thus, VP²RQ is more efficient in C_I than the other methods.

Figure 5.

C_I versus network ID.

Figure 6.

C_I versus N.

Figure 7.

C_I versus m.

QP communication cost evaluations

In this section, we focus on the communication cost C_Q of QP in the methods of VP²RQ, S&L, NSC, QuerySec, and secRQ:

C_Q versus N. Figure 8 reveals that the C_Q of these five methods increases with N, among which VP²RQ and S&L are equal and lower than the others. The reasons for this are as follows. With an increase in N, the sensor data that satisfy the range query increase at the same time; then, the encrypted data returned by the S_M increase in these five methods and C_Q also increase accordingly. Furthermore, compared to QuerySec, NSC, and secRQ, both VP²RQ and S&L require the S_M to upload the corresponding encrypted buckets whose tags are in the interested bucket tag set, and they only need to upload an extra code for verification of the query result; as a result, they have the lowest C_Q.

C_Q versus m. Figure 9 shows that the C_Q of NSC also increases with m, and those of QuerySec and secRQ remain the same, while VP²RQ and S&L have the lowest C_Q, first exhibiting a decreasing trend and then an increasing trend. The reasons for this are similar to those in Figure 7. For VP²RQ and S&L, when m is small, with the increase in m, the density of the bucket partition will gradually increase, and the union of the buckets whose tag are in the interested bucket tag set will increasingly get closer to the query range; therefore, the unqualified data embedded in the encrypted buckets and returned by the S_M to the BS are reduced; thus, C_Q decreases accordingly. While with further increase in m, the space to further reduce unqualified data becomes smaller, and the tag information uploaded with the encrypted buckets will increase; therefore, C_Q gradually increases.

C_Q versus cr. Here, cr is the coverage rate of the query range in the domain of the sensor data in the network. We set the lower bound of the query range to be equal with the lower bound of the domain and set the upper bound of the query range to change, which forms a different cr.

Figure 8.

N’s impact on C_Q.

Figure 9.

m’s impact on C_Q.

As shown in Figure 10, we can see that before cr = 50%, the C_Q of these five methods gradually increases with cr, and they are relatively small and close; but they experience rapid growth between 50% and 80%; and after 80%, they resume a gradual increase. In addition, before cr = 50%, the C_Q of VP²RQ is slightly higher than that of QuerySec; but after cr = 50%, the C_Q of VP²RQ and S&L is lower than those of QuerySec, NSC, and secRQ. The experiment phenomenon above is closely related to the distribution of sensor data in the whole domain, as shown in Figure 11. And, Figure 11 shows that the sensor data gradually increase in the first 50% part of the entire domain, but it is still very low; most data are concentrated between 50% and 80%; after 80%, once again, the sensor data gradually decrease; when cr is small, very few encrypted data satisfy the query requirement, so the C_Q of these five methods is small. With the continuous increase in cr, the encrypted data that satisfy the query requirement rapidly increase. For reasons similar to those in Figure 9, the C_Q of these five methods gradually increases with cr, and VP²RQ has the lowest C_Q.

Figure 10.

cr’s impact on C_Q.

Figure 11.

Distribution of sensor data.

The above experimental results show that C_I and C_Q in VP²RQ perform better than those in similar methods such as S&L, NSC, QuerySec, and secRQ. Therefore, the VP²RQ method proposed in this article shows better performance in prolonging the lifetime of sensor networks.

Conclusion

Verifiable privacy-preserving data QP is a significant issue commonly required in WSNs, and there is urgent demand for its application in various fields such as medical health, intelligent transportation, national defense, and military. It is also a hotspot problem in studies on WSNs. In this article, we propose an efficient VP²RQ method in two-tiered sensor networks. In this method, the DC-protocol and QP-protocol based on TAG routing, bucket partition, symmetrical encryption, information identity authentication, and check-code fusion are proposed to preserve data privacy and verify the completeness of query result. The theoretical analysis and experiment results show that VP²RQ can ensure the privacy security of the sensor data, query results, and query ranges, which also supports the completeness verification of query result at the same time; it also performs better than existing similar methods in terms of communication cost.

Footnotes

Academic Editor: Pardeep Kumar

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the National Natural Science Foundation of China under the grant nos 61300240, 61402014, 61572263, 61502251, 61472193, 61302157, and 61373138; the Natural Science Foundation of Jiangsu Province under the grant nos BK20151511, BK20141429, and BK20130096; the Project of Natural Science Research of Jiangsu University under grant nos 14KJB520027; CCF-Tencent Open Research Fund under grant no. CCF-Tencent RAGR20150107; the Fundamental Research Funds for the Central Universities under the grant no. NJ20160014; and Projects Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions and Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology.

References

Guan

. Towards efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. IEEE T Inf Foren Sec 2016; 11: 2706–2716.

Xia

Wang

Sun

. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE T Parall Distr 2015; 27(2): 340–352.

Ren

Shu

. Enabling personalized search over encrypted outsourced data with efficiency improvement. IEEE T Parall Distr 2016; 27: 2564–2559.

Sun

Liu

. Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE T Commun 2015; E98-B(1): 190–200.

Yang

. Segmentation-based image copy-move forgery detection scheme. IEEE T Inf Foren Sec 2015; 10(3): 507–518.

Zheng

Jeon

. Image segmentation by generalized hierarchical fuzzy C-means algorithm. J Intell Fuzzy Syst 2015; 28(2): 961–973.

Pan

Lei

Zhang

. Fast motion estimation based on content property for low-complexity H.265/HEVC encoder. IEEE T Broadcast 2016; 62: 675–684.

Pan

Zhang

Kwong

Efficient motion and disparity estimation optimization for low complexity multiview video coding. IEEE T Broadcast 2015; 61(2): 166–176.

Gnawali

Jang

Paek

. The tenet architecture for tiered sensor networks. In: Proceedings of the 4th ACM conference on embedded networked sensor systems, Boulder, Colorado, USA, 31 October–3 November 2006, pp.153–166.

10.

Fan

Teng

Huo

A pre-determined nodes deployment strategy of two-tiered wireless sensor networks based on minimizing cost. Int J Wireless Inform Network 2014; 21: 114–124.

11.

Sheng

Verifiable privacy-preserving range query in two-tiered sensor networks. In: Proceedings of the 27th IEEE international conference on computer communications (IEEE INFOCOM 2008), Phoenix, AZ, April 2008, pp.457–465. New York: IEEE.

12.

Shi

Zhang

Secure range queries in tiered sensor networks. In: Proceedings of the 28th IEEE conference on computer communications (IEEE INFOCOM 2009), Rio de Janeiro, Brazil, April 2009, pp.945–953. New York: IEEE.

13.

Shi

Zhang

A spatiotemporal approach for secure range queries in tiered sensor networks. IEEE T Wirel Commun 2011; 10(1): 264–273.

14.

Chen

Liu

AX.

SafeQ: secure and efficient query processing in sensor networks. In: Proceedings of the 29th IEEE international conference on computer communications (IEEE INFOCOM 2010), East Lansing, MI, 14–19 March 2010, pp.1–9. New York: IEEE.

15.

Chen

Liu

AX.

Privacy and integrity preserving range queries in sensor networks. IEEE ACM T Network 2012; 20(6): 1774–1787.

16.

Yin

. SEF: a secure, efficient, and flexible range query scheme in two-tiered sensor networks. Int J Distrib Sens N 2011; 2011: 126407 (12 pp.).

17.

Tsou

Kuo

SY.

Privacy- and integrity-preserving range query in wireless sensor networks. In: Proceedings of the 2012 IEEE global communications conference (GLOBECOM), Anaheim, CA, 3–7 December 2012, pp.328–334. New York: IEEE.

18.

Nguyen

Bui

Dang

. Efficiently preserving data privacy range queries in two tiered wireless sensor networks. In: Proceedings of the international conference on ubiquitous intelligence and computing and international conference on autonomic and trusted computing, Fukuoka, Japan, 4–7 September 2012, pp.973–978. New York: IEEE.

19.

Chen

. A digital watermarking approach to secure and precise range query processing in sensor networks. In: Proceedings of the 32rd IEEE international conference on computer communications (IEEE INFOCOM 2013), Turin, April 2013, pp.1950–1958. New York: IEEE.

20.

Zhang

Dong

Peng

. Achieving efficient and secure range query in two-tiered wireless sensor networks. In: Proceedings of the IEEE/ACM international symposium on quality of service, Hong Kong, 26–27 May 2014, pp.380–388. New York: IEEE.

21.

Zhang

Dong

Peng

. Collusion-aware privacy-preserving range query in tiered wireless sensor networks. Sensors 2014; 14(12): 23905–23932.

22.

Dong

Chen

Zhu

. A secure collusion-aware and probability-aware range query processing in tiered sensor networks. In: Proceedings of the IEEE 34th symposium on reliable distributed systems (SRDS), Montreal, QC, Canada, 28 September–1 October 2015, pp.110–119. New York: IEEE.

23.

Hacigümüş

Iyer

. Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD international conference on management of data, Madison, Wisconsin, 3–6 June 2002, pp.216–227.

24.

Hore

Mehrotra

Tsudik

. A privacy-preserving index for range queries. In: Proceedings of the thirtieth international conference on very large data bases, Toronto, Canada, 31 August–3 September 2004, pp.720–731.

25.

Jerry

Hao

Starsky

. Design and implementation of cross-domain cooperative firewall. In: Proceedings of the IEEE international conference on network protocols, Beijing, China, 16–19 October 2007, pp.284–293. Piscataway, NJ: IEEE.

26.

Liu

Chen

. Collaborative enforcement of firewall policies in virtual private networks. In: Proceedings of the 27th annual ACM symposium on principles of distributed computing, Toronto, ON, Canada, 18–21 August 2008, pp.95–105. New York: ACM.

27.

Bloom

BH.

Space/time trade-offs in hash coding with allowable errors. Commun ACM 1970; 13: 422–426.

28.

Xie

Wang

. Construction of tree network with limited delivery latency in homogeneous wireless sensor networks. Wireless Pers Commun78(1): 231–246.

29.

Madden

Franklin

Hellerstein

. TAG: a tiny aggregation service for ad-hoc sensor networks. ACM SIGOPS Oper Syst Rev 2002; 36(SI): 131–146.

30.

Rappaport

Wireless communications: principles and practice. Upper Saddle River, NJ: Prentice Hall, 1996.

31.

Coman

Nascimento

Sander

. Framework for spatio-temporal query processing over wireless sensor networks. In: Proceedings of the first workshop on data management for sensor networks, in conjunction with VLDB, Toronto, Canada, 30 August 2004, pp.68–77.

32.

Samuel

Intel lab data. Cambridge, MA: Massachusetts Institute of Technology, 2004, http://db.csail.mit.edu/labdata/labdata.html (accessed 31 December 2012).

VP 2 RQ: Efficient verifiable privacy-preserving range query processing in two-tiered wireless sensor networks

Abstract

Keywords

Introduction

Related works

Models and problem statement

Network model

Range query model

Problem statement

Bucket partition mechanism

Definition 1

Definition 2

VP2RQ protocols

Definitions and assumptions

Definition 3

DC-protocol

QP-protocol

Definition 4

Protocol analysis

Security analysis

Communication cost analysis

Performance evaluation

Sensor node communication cost evaluations

QP communication cost evaluations

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

VP²RQ protocols