Random Secure Comparator Selection Based Privacy-Preserving MAX/MIN Query Processing in Two-Tiered Sensor Networks

Abstract

Privacy-preserving data queries for wireless sensor networks (WSNs) have drawn much attention recently. This paper proposes a privacy-preserving MAX/MIN query processing approach based on random secure comparator selection in two-tiered sensor network, which is denoted by RSCS-PMQ. The secret comparison model is built on the basis of the secure comparator which is defined by 0-1 encoding and HMAC. And the minimal set of highest secure comparators generating algorithm MaxRSC is proposed, which is the key to realize RSCS-PMQ. In the data collection procedures, the sensor node randomly selects a generated secure comparator of the maximum data into ciphertext which is submitted to the nearby master node. In the query processing procedures, the master node utilizes the MaxRSC algorithm to determine the corresponding minimal set of candidate ciphertexts containing the query results and returns it to the base station. And the base station obtains the plaintext query result through decryption. The theoretical analysis and experimental result indicate that RSCS-PMQ can preserve the privacy of sensor data and query result from master nodes even if they are compromised, and it has a better performance on the network communication cost than the existing approaches.

Hua Dai 1, 2 and Tianyi Wei 3 and Yue Huang 1 and Jia Xu 1, 2 and Geng Yang 1, 2

Academic Editor:Gwanggil Jeon

1, College of Computer Science & Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
2, Jiangsu High Technology Research Key Lab for Wireless Sensor Networks, Nanjing 210003, China
3, Bell Honors School, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

Received 7 May 2015; Revised 4 August 2015; Accepted 24 August 2015; 8 December 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

As wireless sensor networks (WSNs) have been widely used in a variety of important areas such as environment monitoring, medical care, national defense, and military, various security problems of data privacy are becoming more and more critical. For example, in the rare animal monitoring, the location of rare animals could be obtained for illegal hunting; in the application of smart home, the information for use of family hydroelectricity could be stolen for burglary. Therefore, privacy-preserving has become a very important issue in WSNs.

Most large-scale WSNs are expected to apply a two-tiered architecture with the resource-limit sensor nodes at the lower layer and resource-abundant master nodes at the upper layer, and this architecture is used to construct our concerned two-tiered wireless sensor networks (TWSNs) in this paper, as shown in Figure 1. The master nodes have abundant resources of energy, computation, communication, and so forth, while the sensor nodes only have limited resources. The sensor nodes are only responsible of collecting data and periodically submitting it to a nearby master node for storage, which responds to the query requests from the base station (BS) and then returns the query results. Due to the simplicity of topological structure which contains multiple independent cells and the resource abundance of master nodes, TWSNs have a lot of advantages, such as stable link quality, simple route structure, and higher network scalability [1, 2].

Figure 1: Architecture of TWSNs.

[figure omitted; refer to PDF]

However, because the master nodes are not only responsible of storing all the data from the sensor nodes, but also processing the query requests from BS, they are much more attractive and vulnerable to attackers in a hostile environment. Once a master node is compromised, serious threats could be brought to the data privacy of TWSNs. The attackers could utilize the compromised master nodes to obtain all the collected data of sensor nodes and the query results. Thus, it is necessary to investigate the privacy-preserving problems in TWSNs and develop efficient and effective solutions.

MAX/MIN query is a useful data query method to obtain the maximum or minimum data in the areas and epochs of interest. It can be utilized in event monitoring. For example, it can be applied to monitor the highest temperature in a warehouse so as to alarm the fire risk. The challenges to achieve privacy-preserving MAX/MIN query processing in TWSNs include the following:

(i) How to make the master nodes realize secure comparisons of data items without knowing their real values and then determine the maximum or minimum value, that is, the query result.

(ii) How to maximally reduce the communication cost of network, especially that of the sensor nodes due to their limited resources.

In this paper, we propose a privacy-preserving MAX/MIN query processing approach based on random secure comparator selection in TWSNs, which is denoted by RSCS-PMQ. The basic idea is as follows: once finishing data collection, the sensor nodes will encrypt the collected data into ciphertext and select the corresponding random secure comparators generated by using the 0-1 encoding [3] and hashed message authentication coding (HMAC) [4]. Then the ciphertext and the corresponding random secure comparators are submitted to the nearby master node. When the master node processes a query request from BS, it will utilize the algorithm MaxRSC to determine the minimal set of highest secure comparators, further determine the corresponding minimal set of candidate ciphertexts containing the query result, and return it to BS. After decrypting the received ciphertext, BS will obtain the query result in plaintext. Since the data storage and query response procedures in the master node do not involve the plaintext of collected data, the adversaries cannot read any hosted data or query result from the master node even if it is compromised. Thus, the proposed RSCS-PMQ can achieve the privacy protection in MAX/MIN query processing. In addition, the evaluation indicates that RSCS-PMQ has better performance than other existing works on the network communication cost.

The main contributions of this paper are as follows:

(i) We propose a comparison model based on random secure comparator selection through the 0-1 encoding and hashed message authentication coding, which supports data comparison without real values in master nodes.

(ii) We design an algorithm to generate the minimal set of highest secure comparators based on the former comparison model, MaxRSC, which is the key algorithm to accomplish RSCS-PMQ.

(iii): We provide the concrete protocols of achieving RSCS-PMQ, which consist of the data collection protocol and the query response protocol, and the latter protocol can protect data privacy from master nodes even if they are compromised.

(iv) We analyze the privacy protection and communication cost of RSCS-PMQ and conduct performance evaluation through comprehensive simulation.

The rest of this paper is organized as follows. Section 2 gives an overview of related works. Section 3 describes related models and problem statement. In Section 4, we present the privacy-preserving MAX/MIN query protocols based on random secure comparator selection. Then, Section 5 analyzes the privacy and communication costs of our approach. We evaluate the performance through simulation in Section 6 and conclude this paper in Section 7.

2. Related Works

Data query is an important operation for events monitoring or data analysis in TWSN. The security issues are the hot spots in data query researches, such as privacy protection, integrity, or completeness verification. Recently, the secure range query [5-11] and top-k query [12-17] have been broadly studied. However, there are limited researches on MAX/MIN query, and only [18, 19] propose solutions of privacy-preserving MAX/MIN query in TWSN.

Regarding the range query, a secure range query processing in TWSN is firstly proposed in [5], which employs bucket partition and symmetric encryption to achieve the privacy protection of collected data, and uses MAC to accomplish the completeness verification of query results. Based on [5], the spatiotemporal cross-check is introduced in [6, 7] to improve the efficiency of energy consumption. Furthermore, the spatiotemporal cross-check procedure of [6, 7] is optimized in [8], which balances the security and energy consumption and applies this method in multidimensional range query. A secure and energy-efficient range query processing protocol SafeQ is proposed in [9, 10], which is based on Prefix Membership Verification (PMV) [20] and neighborhood chain mechanism. In addition, the Bloom-Filter [21] is introduced to optimize the energy consumption. And a secure range query protocol based on order-preserving function and link watermarking QuerySec is proposed in [11], which is capable of saving energy during query processing. However, these secure range query methods are not suitable for solving the privacy-preserving MAX/MIN query.

For top-k query, the fine-grained verifiable top-k query methods are proposed in [12, 13], whereby the network owner can verify the completeness and authenticity of query results in TWSNs. The verification code which embeds ordered and adjacent relationships of the collected data by HMAC is utilized in [14] to achieve the verifiable top-k query processing. The symmetric encryption is applied in [15] to reduce the communication cost in verifiable top-k query processing. Works in [12-15] merely support the completeness and authenticity verification of query results, but they cannot achieve privacy protection. To preserve privacy, the privacy-preserving top-k query processing approaches based on Order Preserving Encryption [22] are proposed in [16, 17]. Though the top-k query can be transformed into MAX/MIN query when k = 1, it is wasteful in energy consumption. The reason is that each sensor node should submit all the data collected in every epoch since top-k is designed for obtaining the highest k data, where k is variable. In contrast, MAX/MIN query only has to submit the sole maximum or minimum value. Therefore, taking top-k query as MAX/MIN query will result in high unnecessary data communication. In conclusion, the secure top-k query methods are not suitable for solving the privacy-preserving MAX/MIN query.

For MAX/MIN query, the same PMV as in [9, 10], the symmetric encryption and HMAC are used in [18] to achieve the privacy-preserving MAX/MIN query processing. Since more codes are transmitted in data submission, which are generated by using the PMV and HMAC functions, the energy consumption of [18] is high, which will reduce the lifetime of whole network. In contrast, our former work [19] adapts 0-1 encoding verification instead of PMV to achieve an energy-efficient privacy-preserving MAX/MIN query which is denoted by EMQP. In EMQP, the codes generated by using 0-1 encoding and HMAC of same data are significantly less than those generated in [18], which can reduce the energy consumption of sensor nodes. Furthermore, in this paper, we will adopt random selection of codes on the basis of EMQP to save much more energy and accomplish better privacy-preserving MAX/MIN query processing.

There are also many secure aggregation methods, such as [23-26]. However, most of these works adapt the traditional multihop wireless sensor networks, and they are not suitable for TWSNs.

3. Models and Problem Statement

3.1. Network Models

We consider a similar TWSN model as in [5-17], as shown in Figure 1. The network is divided into multiple cells, each containing master node [figure omitted; refer to PDF] and several sensor nodes [figure omitted; refer to PDF] , which is named after [figure omitted; refer to PDF] . In particular, the master nodes are powerful devices, which have abundant resources of energy, storage, and computation. Additionally, they are also responsible for receiving and storing data collected by the sensor nodes and processing the query requests from BS, while the sensor nodes are cheap devices with limited resources. Each sensor node merely submits its collected data to the master node in the same cell. The master node can apply its long-distance and high-frequency communication capacity to communicate with the nearby nodes, which should then construct the upper-tier multihop networks. The query results will be returned from the queried master nodes to BS through the above networks. There is an on-demand wireless link (e.g., satellite) between the master nodes and BS to interact with each other. However, such wireless link is usually unstable and is of high consumption and low speed.

We assume that the time is divided into nonoverlapping epochs, and in every epoch [figure omitted; refer to PDF] , the sensor node [figure omitted; refer to PDF] collects [figure omitted; refer to PDF] sensor data [figure omitted; refer to PDF] . In TWSNs, BS owns the global network topological information, while a master node owns the network topological information of its located cell, and a sensor node only knows the locations of the master node in the same cell and 1-hop neighboring sensor nodes.

3.2. MAX/MIN Query Models

A MAX/MIN query in TWSN is a kind of query operation aimed at obtaining the maximum or minimum data among the data items collected in the specified epochs and area. Therefore, the following MAX/MIN query will be considered, which is denoted by a triple tuple: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] refers to the query type, [figure omitted; refer to PDF] is the set of queried epoch numbers, and [figure omitted; refer to PDF] denotes the set of queried sensor nodes IDs which indicate a query region. For example, query [figure omitted; refer to PDF] is aimed at getting the maximum data collected by sensor nodes [figure omitted; refer to PDF] in the epoch [figure omitted; refer to PDF] .

For simplicity, we focus on the simple MAX query aimed at one cell [figure omitted; refer to PDF] and one epoch [figure omitted; refer to PDF] ; that is [figure omitted; refer to PDF] , where, [figure omitted; refer to PDF] . For other complicated queries covering multiple epochs and cells, it can be easily achieved by decomposing them into multiple simple ones. And we will conduct discussion in Section 4.5. Additionally, the MIN query is similar to the MAX query.

3.3. Problem Statement

In TWSNs, [figure omitted; refer to PDF] is too vulnerable and tends to be easily under attacks from adversaries, since they are not only responsible for storing all the data collected by the sensor nodes, but also responsible for processing the query requests from BS. If the collected data is in plaintext and [figure omitted; refer to PDF] is compromised, any data stored in [figure omitted; refer to PDF] and the query results generated by [figure omitted; refer to PDF] will be exposed to attackers, which tends to lead to privacy leakage. Therefore, it is necessary to take efficient and effective measures for privacy protection.

We adopt the same honest-but-curious threat model as in [27], where [figure omitted; refer to PDF] may try to breach privacy to steal sensitive data but faithfully obey protocols while processing the query requests. Additionally, BS and sensor nodes are also assumed to be credible in contrast to [figure omitted; refer to PDF] . Based on the above assumption, for the sake of achieving privacy-preserving MAX/MIN query processing, the following conditions should be satisfied:

(1) For the data collected by any sensor node in the network, only this sensor node and BS can obtain its real value in contrast to [figure omitted; refer to PDF] .

(2) For the real value of query results, only BS can obtain it in contrast to [figure omitted; refer to PDF] .

Moreover, [figure omitted; refer to PDF] have abundant energy resources, while the sensor nodes are energy-limited, which results in the fact that the lifetime of the whole network totally relies on the energy consumption of sensor nodes. And most energy is consumed by communications according to [19]. Therefore, the communication cost of sensor nodes is a key metric for performance evaluation of query processing method in TWSN. We will conduct concrete evaluations of in-cell communication cost [figure omitted; refer to PDF] and query response communication cost ( [figure omitted; refer to PDF] ) in Section 6. The former represents the total energy consumption in bits incurred by data transmissions between the sensor nodes and [figure omitted; refer to PDF] per epoch, while the later refers to the total information in bits transmitted between [figure omitted; refer to PDF] and BS.

4. MAX/MIN Query Processing with Random Secure Comparator Selection

We use the 0-1 encoding verification [3], which can be utilized to compare data items without knowing their values. Let [figure omitted; refer to PDF] be a binary string with [figure omitted; refer to PDF] bits. The 0-encoding and 1-encoding of [figure omitted; refer to PDF] are denoted by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively, where [figure omitted; refer to PDF] . For two data items [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , [figure omitted; refer to PDF] if and only if [figure omitted; refer to PDF] ; otherwise [figure omitted; refer to PDF] . Obviously, if codes of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are of different types, they can be compared; otherwise they are incomparable.

In order to improve the efficiency of intersection computing, the numeralization functions are usually applied to convert the 0-1 encoding binary strings into numbers. Thus we adopt the same numeralization function [figure omitted; refer to PDF] as in [19], which satisfies the idea that, for any two 0-encoding or 1-encoding binary strings, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , [figure omitted; refer to PDF] if and only if [figure omitted; refer to PDF] . Additionally, we utilize HMAC to realize one-wayness and collision resistance of encoding data. We denote HMAC function by [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the secret key of HMAC, which is only shared in sensor nodes.

4.1. Comparison Model Based on Random Secure Comparator Selection

Definition 1.

For data [figure omitted; refer to PDF] , after applying 0-1 encoding, numeralization, and HMAC, the two generated code sets are denoted by the secure comparators of [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are type 0 and type 1 secure comparators, respectively; that is, [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .

According to the data comparison property of 0-1 encoding verification, we do not have to compare any two data items based on their values, but only the corresponding secure comparators. Thus, Lemma 2 is established.

Lemma 2.

For data [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] , then [figure omitted; refer to PDF] ; otherwise [figure omitted; refer to PDF] .

Definition 3.

The random secure comparator of data [figure omitted; refer to PDF] is denoted by [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the random selection function of a set. Its value is denoted by [figure omitted; refer to PDF] ; that is, [figure omitted; refer to PDF] , and its type is denoted by [figure omitted; refer to PDF] , which is shown as follows: [figure omitted; refer to PDF]

Given the random secure comparators of two different data items, we propose the rsc _compare algorithm, as shown in Algorithm 1, to conduct secure comparisons according to Lemma 2 and Definition 3.

Algorithm 1: rsc_compare .

Input : secure comparators [figure omitted; refer to PDF] and [figure omitted; refer to PDF]

Output : if [figure omitted; refer to PDF] , 1 is returned, if [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] is returned, and [figure omitted; refer to PDF] , 0 is resturned,

Procedures :

If [figure omitted; refer to PDF] , then return 0;

If [figure omitted; refer to PDF] , then

If [figure omitted; refer to PDF] , then return 1; //means [figure omitted; refer to PDF] ;

Else, return [figure omitted; refer to PDF] ; //means [figure omitted; refer to PDF] ;

Else

If [figure omitted; refer to PDF] , then return [figure omitted; refer to PDF] ; //means [figure omitted; refer to PDF] ;

Else, return 1; //means [figure omitted; refer to PDF] ;

Definition 4.

For two secure comparators, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , if and only if [figure omitted; refer to PDF] , then [figure omitted; refer to PDF] is higher than [figure omitted; refer to PDF] , and we denote it by [figure omitted; refer to PDF] , which means [figure omitted; refer to PDF] ; if and only if [figure omitted; refer to PDF] , then [figure omitted; refer to PDF] is smaller than [figure omitted; refer to PDF] , and we denote it by [figure omitted; refer to PDF] , which means [figure omitted; refer to PDF] ; otherwise, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are incomparable.

According to Definition 4, only if two secure comparators are of different types, they are comparable. It is remarkable that the relations [figure omitted; refer to PDF] and [figure omitted; refer to PDF] do not have transitivity.

4.2. Algorithm for Generating Minimal Set of Highest Secure Comparators

In this section, we firstly give the definition of the minimal set of highest secure comparators, which is the theoretical basis to achieve RSCS-PMQ. Then, we provide the generation algorithm of this set and analyze the probability of the amount of its elements.

Definition 5.

Assume that [figure omitted; refer to PDF] is the corresponding set of random secure comparators of [figure omitted; refer to PDF] . The minimal set of highest secure comparators is denoted by Ψ, where

(1) [figure omitted; refer to PDF] ;

(2) [figure omitted; refer to PDF] , [figure omitted; refer to PDF] ;

(3) [figure omitted; refer to PDF]

According to Definition 5, the secure comparators in [figure omitted; refer to PDF] are of the same type; therefore, they are incomparable. Moreover, for secure comparators [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , if they are of different types, the former is obviously larger than the latter; if they are of the same type, there must exist another secure comparator [figure omitted; refer to PDF] with different type from [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , which satisfies the idea that [figure omitted; refer to PDF] is larger than [figure omitted; refer to PDF] , while [figure omitted; refer to PDF] is larger than [figure omitted; refer to PDF] .

Lemma 6.

Assume that [figure omitted; refer to PDF] is the minimal set of highest secure comparators of the data set [figure omitted; refer to PDF] ; then we have [figure omitted; refer to PDF]

Lemma 6 can be easily deduced from Definition 5, which indicates that the maximum of [figure omitted; refer to PDF] must exist in the corresponding data set of [figure omitted; refer to PDF] .

Lemma 7.

Given data set [figure omitted; refer to PDF] , its corresponding secure comparator set is [figure omitted; refer to PDF] ; then we have the probability of [figure omitted; refer to PDF] containing [figure omitted; refer to PDF] elements as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

Proof.

Assume that [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] has [figure omitted; refer to PDF] secure comparators; then [figure omitted; refer to PDF] . According to Definition 5, all the secure comparators in [figure omitted; refer to PDF] are of the same type. And [figure omitted; refer to PDF] must be of different type from the ones in [figure omitted; refer to PDF] ; otherwise [figure omitted; refer to PDF] also belongs to [figure omitted; refer to PDF] , which contradicts to the given assumption. Therefore, the probability of [figure omitted; refer to PDF] having [figure omitted; refer to PDF] secure comparators is equivalent to the probability that [figure omitted; refer to PDF] are of the same type while differing from [figure omitted; refer to PDF] . Apparently, the probability of all [figure omitted; refer to PDF] being type 0 and [figure omitted; refer to PDF] being type 1 is [figure omitted; refer to PDF] . Similarly, the probability is also [figure omitted; refer to PDF] under the reverse circumstance. Thus, the probability of [figure omitted; refer to PDF] having [figure omitted; refer to PDF] secure comparators is [figure omitted; refer to PDF] .

The generation algorithm of the minimal set of highest secure comparatorsis given as Algorithm 2, denoted by MaxRSC.

Algorithm 2: MaxRSC.

Input : The set of random secure comparators, S

Output : The minimal set of highest secure comparators, Ψ

Procedures :

(1) Initialize [figure omitted; refer to PDF] , [figure omitted; refer to PDF] which are used to store type 0 and 1 secure comparators, respectively;

(2) Fetch the first secure comparator from S into the variable a , and set the variable [figure omitted; refer to PDF] ;

(3) If [figure omitted; refer to PDF] , add [figure omitted; refer to PDF] into [figure omitted; refer to PDF] , otherwise add it into [figure omitted; refer to PDF] ;

(4) For each [figure omitted; refer to PDF] ,

If [figure omitted; refer to PDF] , then

If [figure omitted; refer to PDF] , then add item into [figure omitted; refer to PDF] ;

Else

If [figure omitted; refer to PDF] , then add item into [figure omitted; refer to PDF] ;

Else, delete every [figure omitted; refer to PDF] if [figure omitted; refer to PDF] ;

If [figure omitted; refer to PDF] , then

If [figure omitted; refer to PDF] , then add item into [figure omitted; refer to PDF] ;

Else if [figure omitted; refer to PDF] ,

then clear [figure omitted; refer to PDF] , add item into [figure omitted; refer to PDF] and set flag = 0;

Else, delete every [figure omitted; refer to PDF] if [figure omitted; refer to PDF] ;

If [figure omitted; refer to PDF] , then

If [figure omitted; refer to PDF] , then add item into [figure omitted; refer to PDF] ;

Else

If [figure omitted; refer to PDF] , then add item into [figure omitted; refer to PDF] ;

Else, delete every [figure omitted; refer to PDF] if [figure omitted; refer to PDF] ;

If [figure omitted; refer to PDF] , then

If [figure omitted; refer to PDF] , then add item into [figure omitted; refer to PDF] ;

Else If [figure omitted; refer to PDF] ,

then clear [figure omitted; refer to PDF] , add item into [figure omitted; refer to PDF] and set flag = 1;

Else, delete every [figure omitted; refer to PDF] if [figure omitted; refer to PDF] ;

End For

(5) If flag = 0, then set Ψ = [figure omitted; refer to PDF] ; otherwise, set Ψ = [figure omitted; refer to PDF] ;

As shown in algorithm MaxRSC, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are used to store the current sets of the highest and second highest secure comparators. The variable flag is to indicate the higher set between [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] indicates [figure omitted; refer to PDF] is higher; otherwise [figure omitted; refer to PDF] is higher. When the algorithm ends, the final minimal set of highest secure comparators is [figure omitted; refer to PDF] if [figure omitted; refer to PDF] ; otherwise it is [figure omitted; refer to PDF] . The algorithm is concise and direct, and its time complexity is only [figure omitted; refer to PDF] .

4.3. Data Collection Protocol

The data collection protocol is concerned with how a sensor node transmits its collected data items to [figure omitted; refer to PDF] . For each sensor node [figure omitted; refer to PDF] , after collecting [figure omitted; refer to PDF] data items [figure omitted; refer to PDF] in epoch [figure omitted; refer to PDF] , it performs the following procedure:

(i) Determine the maximum data among the collected data items; that is, [figure omitted; refer to PDF] .

(ii) Compute the random secure comparator [figure omitted; refer to PDF] , and set its type according to the random selection.

(iii): Encrypt [figure omitted; refer to PDF] by using the key [figure omitted; refer to PDF] shared with BS. The output ciphertext is denoted by [figure omitted; refer to PDF] .

(iv) Submit the following message to [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the ID of [figure omitted; refer to PDF] : [figure omitted; refer to PDF]

(v) Once [figure omitted; refer to PDF] receives the above message from [figure omitted; refer to PDF] , it will store the data of the message.

As shown in the above protocol, since the HMAC function is one-way and collision-resistant and sensor nodes only share the encryption and HMAC keys with BS, it is computationally infeasible to reveal the exact value to [figure omitted; refer to PDF] . Therefore, we can see that the data collection protocol can preserve data privacy from [figure omitted; refer to PDF] .

4.4. Query Response Protocol

The query response protocol is concerned with how [figure omitted; refer to PDF] cooperates with BS to accomplish the query requests from users. The main idea is that [figure omitted; refer to PDF] uses the MaxRSC algorithm to generate the minimal set of highest secure comparators on the basis of submitted random secure comparators of the queried sensor nodes and further determines the corresponding minimal set of candidate ciphertexts which is denoted by [figure omitted; refer to PDF] . Then, [figure omitted; refer to PDF] returns it to BS. And the final query result will be determined after BS performs decryption on [figure omitted; refer to PDF] . The concrete steps of query response protocol are as follows:

(i) BS transmits the query request [figure omitted; refer to PDF] to [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] .

(ii) Once [figure omitted; refer to PDF] receives the query request, it firstly loads the ciphertext [figure omitted; refer to PDF] and the corresponding random secure comparator [figure omitted; refer to PDF] received from each sensor node [figure omitted; refer to PDF] in epoch [figure omitted; refer to PDF] . Assume that the loaded random secure comparators are [figure omitted; refer to PDF] . With them as the input, then [figure omitted; refer to PDF] generates the minimal set of highest secure comparators [figure omitted; refer to PDF] by using the MaxRSC algorithm, and the corresponding minimal set of candidate ciphertexts [figure omitted; refer to PDF] is determined, where [figure omitted; refer to PDF]

(iii): Finally, [figure omitted; refer to PDF] constructs the following message and sends it to BS: [figure omitted; refer to PDF]

(iv) When BS receives the response message from [figure omitted; refer to PDF] , it uses the key shared with the sensor nodes to decrypt the ciphertext in [figure omitted; refer to PDF] , and then the final query result will be determined.

Similar to data collection protocol, it is also computationally infeasible for [figure omitted; refer to PDF] to get the real values and the query result in the query response protocol. Therefore, this protocol can also preserve data privacy from [figure omitted; refer to PDF] .

Lemma 8.

For the determined minimal set of highest secure comparators [figure omitted; refer to PDF] and the corresponding minimal set of candidate ciphertexts [figure omitted; refer to PDF] in the query response protocol, we have the following:

(1) [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] means the number of elements in the set [figure omitted; refer to PDF] .

(2) The query result of [figure omitted; refer to PDF] must be embedded in the ciphertext of [figure omitted; refer to PDF] .

Proof.

According to the construction of [figure omitted; refer to PDF] in (6), we can easily have [figure omitted; refer to PDF] , and the values of secure comparators in [figure omitted; refer to PDF] are all embedded in the ciphertext of [figure omitted; refer to PDF] . And Lemma 6 indicates that the maximum data among the data items collected by the queried sensor nodes (i.e., query result) must exist in the corresponding data set of [figure omitted; refer to PDF] . Therefore, the query result must be embedded in the ciphertext of [figure omitted; refer to PDF] as well.

Lemma 9.

Assume that there are [figure omitted; refer to PDF] elements in [figure omitted; refer to PDF] ; then we have its probability as follows: [figure omitted; refer to PDF]

Proof.

From Lemma 7, we can obtain the idea that the probability of [figure omitted; refer to PDF] containing [figure omitted; refer to PDF] secure comparators is [figure omitted; refer to PDF] . Additionally, Lemma 8 indicates [figure omitted; refer to PDF] . Thus, the probability of [figure omitted; refer to PDF] having [figure omitted; refer to PDF] elements is also [figure omitted; refer to PDF] .

According to Lemma 9, we can easily deduce Lemma 10.

Lemma 10.

The mean quantity of elements in [figure omitted; refer to PDF] is the mathematical expectation [figure omitted; refer to PDF] of the ciphertext quantity in [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] when [figure omitted; refer to PDF] is very large.

4.5. Complicated Query Processing Method

If complicated query [figure omitted; refer to PDF] involving multiple cells and epochs is applied, we can achieve it based on the basic ideas of the data collection and query response protocols. We give the overview of the complicated query processing method through an example.

As shown in Figure 2, there are four master nodes, A, B, C, and D, and BS composing the upper-tier tree-routing networks. Assume that the current query [figure omitted; refer to PDF] involves A, B, C, and D and several epochs. The main idea of processing [figure omitted; refer to PDF] is as follows. Firstly, A, B, C, and D use MaxRSC algorithm to determine their own minimal sets of highest secure comparators and the corresponding minimal set of candidate ciphertexts, which can be denoted by four pairs: [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , respectively. Then, A, B, and C submit [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] to D on their own. And D takes [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and its own [figure omitted; refer to PDF] as inputs into MaxRSC algorithm to determine the global minimal set of highest secure comparators and the global corresponding minimal set of candidate ciphertexts [figure omitted; refer to PDF] . Obviously, the global query result is embedded in [figure omitted; refer to PDF] , and then D submits [figure omitted; refer to PDF] to BS. Consequently, BS decrypts the ciphertext in [figure omitted; refer to PDF] and gets the final query result of the complicated query [figure omitted; refer to PDF] .

Figure 2: Complicated query example.

[figure omitted; refer to PDF]

5. Protocol Analysis

5.1. Privacy-Preserving Analysis

(1) Collected data privacy preservation: on the premise that BS and sensor nodes are credible in this paper, the privacy of data collected by the sensor nodes can be preserved from [figure omitted; refer to PDF] only if it is ensured that it is impossible for [figure omitted; refer to PDF] has to obtain the real value of any collected data. According to the data collection protocol, the data submitted by sensor nodes which are stored in [figure omitted; refer to PDF] are the ciphertext and HMAC codes instead of the plaintext. Since the HMAC algorithm is one-way and collision-resistant and the encryption and HMAC keys are only shared by the sensor nodes and BS, given a random secure comparator [figure omitted; refer to PDF] and ciphertext [figure omitted; refer to PDF] , it is computationally infeasible for [figure omitted; refer to PDF] to obtain the value of the collected data [figure omitted; refer to PDF] . And, for [figure omitted; refer to PDF] , the complexity to peek the privacy is equal to cracking the HMAC and encryption. Thus, our proposed RSCS-PMQ can protect the privacy of the collect data from master nodes.

(2) Query result privacy preservation: as shown in the query response protocol, [figure omitted; refer to PDF] cooperates with BS to achieve the MAX/MIN query processing. During the procedure, [figure omitted; refer to PDF] takes the secure comparators as inputs to determine the minimal set of candidate ciphertexts embedding the plaintext query result through MaxRSC algorithm and then transmits it to BS. Consequently, BS decrypts the received ciphertext and gets the plaintext query result. Obviously, [figure omitted; refer to PDF] has no chance to touch any plaintext query result except for cracking encryption or HMAC. Therefore, RSCS-PMQ can protect the privacy of query results from the master nodes.

5.2. Communication Cost Analysis

To analyze the communication costs of data collection and query response protocols, we present the parameters as follows:

: [figure omitted; refer to PDF] : the number of sensor nodes.

: [figure omitted; refer to PDF] : the bit-length of a sensor node ID.

: [figure omitted; refer to PDF] : the bit-length of an epoch.

: [figure omitted; refer to PDF] : the bit-length of an encrypted data item.

: [figure omitted; refer to PDF] : the bit-length of a HMAC data item.

: [figure omitted; refer to PDF] : the bit-length of a query request.

: [figure omitted; refer to PDF] : the bit-length of a collected data item.

: [figure omitted; refer to PDF] : the average hops from a sensor node to [figure omitted; refer to PDF] .

According to the 0-1 encoding properties, there are [figure omitted; refer to PDF] type 0 and type 1 secure comparators for every [figure omitted; refer to PDF] bits data. Thus, the random secure comparator of a [figure omitted; refer to PDF] -bits data item contains [figure omitted; refer to PDF] HMAC data on average.

As shown in the data collection protocol, each sensor node submits a node ID, an epoch number, a ciphertext, and a secure comparator to [figure omitted; refer to PDF] . Therefore, the communication cost of data collection in the cell, denoted by in-cell communication cost [figure omitted; refer to PDF] , can be calculated with [figure omitted; refer to PDF]

As shown in the query response protocol, the communication cost for executing a query consists of two parts: one part is the communication cost of BS for sending query requests to [figure omitted; refer to PDF] and the other part is of [figure omitted; refer to PDF] for returning the feedback messages to BS. Additionally, Lemma 10 indicates that the mean quantity of ciphertext returned to BS is the mathematical expectation [figure omitted; refer to PDF] of the ciphertext quantity in [figure omitted; refer to PDF] . As a result, the calculation of query response communication cost is as shown which is denoted by [figure omitted; refer to PDF] : [figure omitted; refer to PDF] According to Lemma 10, we have [figure omitted; refer to PDF] when [figure omitted; refer to PDF] is very large.

Then, we have the total communication cost [figure omitted; refer to PDF] as follows: [figure omitted; refer to PDF]

5.3. Computation Cost Analysis

We analyze the computation cost of proposed RSCS-PMQ and compare it with other privacy-preserving MAX/MIN query methods: PMV-PMQ [18] and EMQP [19]. First of all, since all of the three methods use the complex algorithms of encryption and HMAC in sensor nodes, the computation cost of sensor nodes is mainly caused by the encryption and HMAC. Secondly, the storage node [figure omitted; refer to PDF] determines the encrypted query results according to the intersections of paired code sets. To find out whether the intersection of two sets is null or not, many comparison operations are needed. As a result, the computation cost analysis of the three works is given in Table 1 on two aspects: the quantity of encryption and HMAC operations of a sensor node in an epoch and the quantity of comparison operations of [figure omitted; refer to PDF] in a query.

Table 1: Computation cost analysis of PMV-PMQ, EMQP, and RSCS-PMQ.

Privacy-preserving MAX/MIN query methods	The quantity of operations in sensor nodes	The quantity of comparison operations in a storage node
Encryption	HMAC
PMV-PMQ	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
EMQP	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
RSCS-PMQ	1	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]

Note: [figure omitted; refer to PDF] is an interval range between the low-bound [figure omitted; refer to PDF] and the upper-bound [figure omitted; refer to PDF] .

As shown in Table 1, PMV-PMQ, EMQP, and RSCS-PMQ perform the same quantity of encryption operations in a sensor node, but RSCS-PMQ performs less HMAC operations than the other two methods. RSCS-PMQ and EMQP perform the similar quantity of comparison operations, but they have general better performance than PMV-PMQ. Therefore, the RSCS-PMQ approach proposed by us is more efficient in computation cost than PMV-PMQ and EMQP.

We will not discuss the robustness of our method since it is not the focus of this paper. And we assume that the robustness is supported by the low-layer protocols.

6. Performance Evaluations

To analyze and compare the performance of protocols, we implement the proposed RSCS-PMQ, PMV-PMQ, and EMQP on the improved simulator of [28]. According to the experimental results of [19], we know that the energy consumed by data communication is much larger than that by the computation of encryption and HMAC. Therefore, this paper will focus on the evaluation of communication cost. We perform the evaluations on the following two aspects:

(1) We firstly measure and analyze the in-cell communication cost ( [figure omitted; refer to PDF] ) of these three methods. Since the amount of codes for each collected data item constructed in PMV-PMQ is within a certain range, we consider the upper and lower bounds of PMV-PMQ in our evaluations, respectively, that is, the highest and lowest in-cell communication costs, which are denoted by PMV-PMQ-T and PMV-PMQ-B, respectively. Additionally, since the hash-based optimization in EMQP is also suitable for RSCS-PMQ and PMV-PMQ, which is aimed at reducing the length of HMAC data, this paper only compares the [figure omitted; refer to PDF] of three methods without the hash-based optimization.

(2) To evaluate the query response communication cost ( [figure omitted; refer to PDF] ) generated by [figure omitted; refer to PDF] and BS, we firstly measure the probability of [figure omitted; refer to PDF] containing [figure omitted; refer to PDF] ciphertext and the average quantity of ciphertext in [figure omitted; refer to PDF] in the RSCS-PMQ method. Then, we measure [figure omitted; refer to PDF] of the three methods and calculate their proportions in the whole network communication costs while processing the MAX query.

The evaluations are performed on a PC with an Intel Core i5-3230M (quad-core 2.6 GHz) CPU and 8 G memory, running Windows 7 operating system, Eclipse, and Matlab. In addition, the experimental data set is randomly generated. In this simulation, the sensor nodes are assumed to be uniformly distributed in a cell covering a 100 × 100 m² area, and the communication radius of a sensor is 20 m. The default setting of other parameters is as shown in Table 2.

Table 2: Default values of parameters.

Parameter	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Value	32 bits	32 bits	200	16 bits	128 bits	128 bits	256 bits

6.1. In-Cell Communication Cost Evaluations

In each measurement, we randomly distribute the sensor nodes and generate 10 networks with different topologies represented by different network IDs. Then, we can determine the communication cost of a MAX/MIN query by computing the average communication cost of these 10 networks.

(1) [figure omitted; refer to PDF] versus network ID: Figure 3 shows that the [figure omitted; refer to PDF] of RSCS-PMQ, EPRQ, and PMV-PMQ are all uniformly distributed in different topology networks. And the [figure omitted; refer to PDF] of PMV-PMQ is the highest, and EPRQ has the mediate [figure omitted; refer to PDF] , while RSCS-PMQ has the lowest. Under the experiment setting, the [figure omitted; refer to PDF] of RSCS-PMQ is 32.23% lower than the lower bound of PMV-PMQ and 24.54% lower than the lower bound of EPRQ, since the amount of HMAC data used for secure comparison submitted from the sensor nodes to [figure omitted; refer to PDF] in the former method is smaller than that in the latter.

(2) [figure omitted; refer to PDF] versus [figure omitted; refer to PDF] and [figure omitted; refer to PDF] : as shown in Figure 4, when the amount of sensor nodes [figure omitted; refer to PDF] increases, the [figure omitted; refer to PDF] of RSCS-PMQ, EPRQ, and PMV-PMQ also increase, since the amounts of ciphertext and HMAC data transmitted in the network both increase. In accordance with Figure 5, we can see that the [figure omitted; refer to PDF] of three methods also increase as [figure omitted; refer to PDF] increases, because the amount of HAMC data used for secure comparison is in proportion to [figure omitted; refer to PDF] . In addition, Figures 4 and 5 indicate that the [figure omitted; refer to PDF] of three methods are in linear proportion to [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , which is consistent with the theoretical analysis result shown in (10). Moreover, we have the idea that the [figure omitted; refer to PDF] of RSCS-PMQ is significantly lower than that of EPRQ and PMV-PMQ, and the former is about 30% lower than the lower bound of PMV-PMQ and about 25% lower than the lower bound of EPRQ.

(3) [figure omitted; refer to PDF] versus [figure omitted; refer to PDF] and [figure omitted; refer to PDF] : we adopt different encryption and HMAC algorithms to set different [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. For example, [figure omitted; refer to PDF] could be 64, 128, and 256 bits if DES, IDEA, and AES-256 are adopted, respectively, while [figure omitted; refer to PDF] could be 128, 160, and 256 bits if HMAC-MD5, HMAC-SHA1, and HMAC-SHA256 are adopted, respectively.

Figure 3: [figure omitted; refer to PDF] versus network ID.

[figure omitted; refer to PDF]

Figure 4: [figure omitted; refer to PDF] versus [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Figure 5: [figure omitted; refer to PDF] versus [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Figure 6 shows that the [figure omitted; refer to PDF] of RSCS-PMQ, EPRQ, and PMV-PMQ have slow and unapparent increase as [figure omitted; refer to PDF] increases, while they increase obviously as [figure omitted; refer to PDF] increases. The reason is that there is only one encrypted data item in the message submitted from each sensor node to [figure omitted; refer to PDF] , but the amount of HMAC data is in proportion to the length of collected data [figure omitted; refer to PDF] , which is obviously bigger than the former one. And the increasing of [figure omitted; refer to PDF] has a more obvious influence on [figure omitted; refer to PDF] . Similar to the results of evaluations [figure omitted; refer to PDF] and [figure omitted; refer to PDF] in this section, Figures 6 and 7 indicate that RSCS-PMQ is significantly lower than EPRQ and PMV-PMQ in [figure omitted; refer to PDF] , and the former one is about 30% lower than the lower bound of PMV-PMQ and about 25% lower than the lower bound of EPRQ.

Figure 6: [figure omitted; refer to PDF] versus [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Figure 7: [figure omitted; refer to PDF] versus [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

6.2. Query Response Communication Cost Evaluations

[figure omitted; refer to PDF] Assume that the sensor nodes collect data in 10000 epochs and transmit the corresponding ciphertext and HMAC data to [figure omitted; refer to PDF] . And [figure omitted; refer to PDF] executes 10000 MAX queries aimed at each epoch mentioned above. We measure the probability and mean value of the amount of ciphertext in [figure omitted; refer to PDF] returned from [figure omitted; refer to PDF] to BS. We repeat the experimental process 10 times and get the results as shown in Figures 8 and 9.

Figure 8: The probability of [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Figure 9: The mean of ciphertext in [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

From Figure 8, we can see that the probability of [figure omitted; refer to PDF] containing [figure omitted; refer to PDF] ciphertexts in the practical experiment totally corresponds to the theoretical probability computed with (8) in Lemma 9, which also proves the correctness of Lemma 9 from the point of experimental statistics. Additionally, based on a large amount of experimental statistics, Figure 9 indicates that the mean quantity of ciphertext in [figure omitted; refer to PDF] is in agreement with the mathematical expectation [figure omitted; refer to PDF] computed with (9) in Lemma 10, and it is close to 2 as the amount of test samples becomes very large. The result verifies the correctness of Lemma 10 from the point of experimental statistics.

[figure omitted; refer to PDF] Based on the 10 groups of data transmitted from the sensor nodes [figure omitted; refer to PDF] under the 10 networks with random topologies in Section 6.1, we process 10 MAX queries, respectively. We test the query response communication costs ( [figure omitted; refer to PDF] ) and the average proportion of them in the total network communication costs ( [figure omitted; refer to PDF] ) for PMV-PMQ, EPRQ, and RSCS-PMQ, respectively. The experimental results are shown in Figures 10 and 11.

Figure 10: [figure omitted; refer to PDF] versus network ID.

[figure omitted; refer to PDF]

Figure 11: The average of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Figure 10 indicates that the [figure omitted; refer to PDF] of EPRQ and PMV-PMQ are constant and equal, while the [figure omitted; refer to PDF] of RSCS-PMQ is about 20% higher than the former two methods. The reason is as follows: [figure omitted; refer to PDF] can only determine the ciphertext as the query result in EPRQ and PMV-PMQ, while the result returned by [figure omitted; refer to PDF] in RSCS-PMQ is the set [figure omitted; refer to PDF] containing multiple candidate ciphertext. The probability statistics of the amount of ciphertext in [figure omitted; refer to PDF] is as shown in Figure 8, and the mean quantity of [figure omitted; refer to PDF] is about 2 according to Figure 9.

However, as shown in Figure 11, in the average [figure omitted; refer to PDF] of PMV-PMQ, EPRQ, and RSCS-PMQ where [figure omitted; refer to PDF] , the mean value of [figure omitted; refer to PDF] is significantly smaller than that of [figure omitted; refer to PDF] , and they merely account for a very small proportion of [figure omitted; refer to PDF] , only 0.22 [figure omitted; refer to PDF] , 0.24 [figure omitted; refer to PDF] , and 0.38 [figure omitted; refer to PDF] on average, respectively. Here, [figure omitted; refer to PDF] of PMV-PMQ is the lower bound of its in-cell communication cost. In addition, [figure omitted; refer to PDF] is generated by the resource-abundant master nodes and BS. As a result, [figure omitted; refer to PDF] has little impact on [figure omitted; refer to PDF] which is mainly determined by [figure omitted; refer to PDF] in contract, and [figure omitted; refer to PDF] of RSCS-PMQ is lower than that of PMV-PMQ and EPRQ.

From the above experimental results and analyses, we can obtain the following: compared with the existing EPRQ and PMV-PMQ, the in-cell communication cost of RSCS-PMQ is lower, which is about 30% lower than the lower bound of EPRQ and about 25% lower than the lower bound of PMV-PMQ. Additionally, although the query response communication cost of RSCS-PMQ is higher than that EPRQ and PMV-PMQ, it only accounts for a very small proportion of the total network communication cost, lower than 1%, and so do the later methods. And the total communication cost of RSCS-PMQ is lower than EPRQ and PMV-PMQ. Thus, the RSCS-PMQ proposed in this paper has a better performance than the existing works.

7. Conclusion

In this paper, we propose a novel random secure compactor selection scheme and a minimal set of highest secure comparators generating algorithm to achieve privacy-preserving MAX/MIN queries in two-tiered wireless sensor networks. Our technique can prevent the compromised master node from peeking at the hosted data and also ensure high query efficiency in network communication cost. Moreover, the efficacy and efficiency of our method are confirmed through detailed evaluations and analysis. In the future works, we will focus on the verification of query result completeness and further develop the key technique of this paper to support other types of data queries.

Acknowledgments

This research was supported by the National Natural Science Foundation of China under the Grants nos. 61300240, 61402014, 61572263, 61502251, 61472193, 61302157, 61373138, 61201163, and 61272084, the Natural Science Foundation of Jiangsu Province under the Grants nos. BK20151511 and BK20141429, the Project of Natural Science Research of Jiangsu University under Grants nos. 11KJA520002 and 14KJB520027, the Postdoctoral Science Foundation of China under the Grant no. 2013M541703, the Postdoctoral Science Foundation of Jiangsu Province under the Grant no. 1301042B, and Scientific & Technological Support Project (Society Development) of Lianyungang under the grant no. SH1306.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] O. Gnawali, K.-Y. Jang, J. Paek, M. Vieira, R. Govindan, B. Greenstein, A. Joki, D. Estrin, E. Kohler, "The tenet architecture for tiered sensor networks," in Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys '06), pp. 153-166, ACM, Boulder, Colo, USA, November 2006.

[2] Y. Diao, D. Ganesan, G. Mathur, P. Shenoy, "Rethinking data management for storage-centric sensor networks," in Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research (CIDR '07), pp. 22-31, Asilomar, Calif, USA, January 2007.

[3] H.-Y. Lin, W.-G. Tzeng, "An efficient solution to the millionaires' problem based on homomorphic encryption," Applied Cryptography and Network Security: Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005. Proceedings , vol. 3531, of Lecture Notes in Computer Science, pp. 456-466, Springer, Berlin, Germany, 2005.

[4] H. Krawczyk, R. Canetti, M. Bellare, "HMAC: keyed-hashing for message authentication,", no. RFC 2104, Internet Society, Reston, Va, USA, 1997.

[5] B. Sheng, Q. Li, "Verifiable privacy-preserving range query in two-tiered sensor networks," in Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM '08), pp. 46-50, Phoenix, Ariz, USA, 2008.

[6] J. Shi, R. Zhang, Y. C. Zhang, "Secure range queries in tiered sensor networks," in Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM '09), pp. 945-953, Rio de Janeiro, Brazil, April 2009.

[7] J. Shi, R. Zhang, Y. Zhang, "A spatiotemporal approach for secure range queries in tiered sensor networks," IEEE Transactions on Wireless Communications , vol. 10, no. 1, pp. 264-273, 2011.

[8] B. Sheng, Q. Li, "Verifiable privacy-preserving sensor network storage for range query," IEEE Transactions on Mobile Computing , vol. 10, no. 9, pp. 1312-1326, 2011.

[9] F. Chen, A. X. Liu, "SafeQ: secure and efficient query processing in sensor networks," in Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM '10), pp. 1-9, IEEE, San Diego, Calif, USA, March 2010.

[10] F. Chen, A. X. Liu, "Privacy and integrity-preserving range queries in sensor networks," IEEE/ACM Transactions on Networking , vol. 20, no. 6, pp. 1774-1787, 2012.

[11] Y. Yi, R. Li, F. Chen, A. X. Liu, Y. Lin, "A digital watermarking approach to secure and precise range query processing in sensor networks," in Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM '13), pp. 1950-1958, IEEE, Turin, Italy, April 2013.

[12] R. Zhang, J. Shi, Y. Liu, Y. Zhang, "Verifiable fine-grained top-k queries in tiered sensor networks," in Proceedings of 29th IEEE International Conference on Computer Communications (INFOCOM '10), pp. 1199-1207, IEEE, San Diego, Calif, USA, March 2010.

[13] R. Zhang, J. Shi, Y. Zhang, X. Huang, "Secure top-k query processing in unattended tiered sensor networks," IEEE Transactions on Vehicular Technology , vol. 63, no. 9, pp. 4681-4693, 2014.

[14] H. Dai, G. Yang, H. P. Huang, "Efficient verifiable top-k queries in two-tiered wireless sensor networks," KSII Transactions on Internet and Information Systems , vol. 9, no. 6, pp. 2111-2131, 2015.

[15] X. Ma, H. Song, J. Wang, J. Gao, G. Min, "A novel verification scheme for fine-grained top-k queries in two-tiered sensor networks," Wireless Personal Communications , vol. 75, no. 3, pp. 1809-1826, 2014.

[16] C.-M. Yu, G.-K. Ni, I.-Y. Chen, E. Gelenbe, S.-Y. Kuo, "Top-k query result completeness verification in tiered sensor networks," IEEE Transactions on Information Forensics and Security , vol. 9, no. 1, pp. 109-124, 2014.

[17] X. Liao, J. Li, "Privacy-preserving and secure top-k query in two-tier wireless sensor network," in Proceedings of the IEEE Global Communications Conference (GLOBECOM '12), pp. 335-341, Anaheim, Calif, USA, December 2012.

[18] Y. Yao, N. Xiong, J. H. Park, L. Ma, J. Liu, "Privacy-preserving max/min query in two-tiered wireless sensor networks," Computers & Mathematics with Applications , vol. 65, no. 9, pp. 1318-1325, 2013.

[19] H. Dai, G. Yang, X. Qin, "EMQP: an energy-efficient privacy-preserving MAX/MIN query processing in tiered wireless sensor networks," International Journal of Distributed Sensor Networks , vol. 2013, 2013.

[20] J. Cheng, H. Yang, S. H. Y. Wong, P. Zerfos, S. Lu, "Design and implementation of cross-domain cooperative firewall," in Proceedings of the 15th IEEE International Conference on Network Protocols (ICNP '07), pp. 284-293, Beijing, China, October 2007.

[21] O. Rottenstreich, I. Keslassy, "The Bloom Paradox: when not to use a bloom filter," IEEE/ACM Transactions on Networking , vol. 23, no. 3, pp. 703-716, 2015.

[22] R. Agrawal, J. Kiernan, R. Srikant, Y. Xu, "Order preserving encryption for numeric data," in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD '04), pp. 563-574, Paris, France, June 2004.

[23] M. Rezvani, A. Ignjatovic, E. Bertino, S. Jha, "Secure data aggregation technique for wireless sensor networks in the presence of collusion attacks," IEEE Transactions on Dependable and Secure Computing , vol. 12, no. 1, pp. 98-110, 2015.

[24] S. Roy, M. Conti, S. Setia, S. Jajodia, "Secure data aggregation in wireless sensor networks: filtering out the attacker's impact," IEEE Transactions on Information Forensics and Security , vol. 9, no. 4, pp. 681-694, 2014.

[25] Q. Zhou, G. Yang, L. He, "A secure-enhanced data aggregation based on ECC in wireless sensor networks," Sensors , vol. 14, no. 4, pp. 6701-6721, 2014.

[26] G. Yang, S. Li, X. Xu, H. Dai, Z. Yang, "Precision-enhanced and encryption-mixed privacy-preserving data aggregation in wireless sensor networks," International Journal of Distributed Sensor Networks , vol. 2013, 2013.

[27] V. Bozovic, D. Socek, R. Steinwandt, V. I. Villanyi, "Multi-authority attribute-based encryption with honest-but-curious central authority," International Journal of Computer Mathematics , vol. 89, no. 3, pp. 268-283, 2012.

[28] A. Coman, M. A. Nascimento, J. Sander, "A framework for spatio-temporal query processing over wireless sensor networks," in 1st International Workshop on Data Management for Sensor Networks, DMSN '04, in Conjunction with VLDB 2004, pp. 104-110, can, August 2004.