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 corre-
sponding bucket tags as the query command to
the S
M
.And,theS
M
returns the corresponding
encrypted data and codes to the BS in accor-
dance with the bucket tags in the query com-
mand. 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 generat-
ing one code for each empty bucket and trans-
ferring 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 communi-
cation 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.
2. Secure range queries based on secure compari-
son.
14–22
The basic idea of these methods is that
the sensor nodes encrypt their collected data
and generate the corresponding secure-compar-
ing-codes, which can be used to compare the
encrypted data. The encrypted data and the cor-
responding 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 member-
ship verification (PMV)
25,26
mechanism. SafeQ
utilizes the PMV coding technique, which can
realize the secrete comparison between the col-
lected data and queried range without their
plaintext; in this way, SafeQ can determine
whether the corresponding encrypted data sat-
isfy the query range. To achieve the query result
completeness verification, SafeQ introduces the
neighborhood chain mechanism during data
encryption and adopts the Bloom-Filter
27
to
reduce the cost of the secure-comparing-codes.
In Bu et al.,
16
an efficient range query method
named SEF is proposed. Order-preserving sym-
metric encryption is employed in SEF to pre-
serve 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.,
17
a range query method
named EQ is proposed for protecting data pri-
vacy and completeness. The EQ method pre-
sents 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.,
18
a novel model
based on a d-disjunct matrix, an order function,
and a permutation function is proposed to pre-
serve the privacy of sensitive data and the com-
pleteness of result. In Yi et al.,
19
a secure range
query protocol named QuerySec is proposed,
which uses the order-preserving function to real-
ize 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 com-
munication cost than SafeQ. ESRQ, which was
proposed in Zhang et al.,
20
also realizes an effi-
cient 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.
21
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.,
22
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 verifica-
tion 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 encryp-
tion 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 granu-
larity of bucket partition and the distribution of
Dai et al. 3