With the increasing electricity consumption and the wide application of renewable energy sources, energy auction attracts a lot of attention due to its economic benefits. Many schemes have been proposed to support energy auction in smart grid. However, few of them can achieve range query, ranked search and personalized search. In this paper, we propose an efficient multikeyword range query (EMRQ) scheme, which can support range query, ranked search and personalized search simultaneously. Based on the homomorphic Paillier cryptosystem, we use two superincreasing sequences to aggregate multidimensional keywords. The first one is used to aggregate one buyer’s or seller’s multidimensional keywords to an aggregated number. The second one is used to create a summary number by aggregating the aggregated numbers of all sellers. As a result, the comparison between the keywords of all sellers and those of one buyer can be achieved with only one calculation. Security analysis demonstrates that EMRQ can achieve confidentiality of keywords, authentication, data integrity and query privacy. Extensive experiments show that EMRQ is more efficient compared with the scheme in
[3]
in terms of computation and communication overhead.
1. Introduction
C
urrently, the traditional power grid, due to its inherent limitations, cannot fully satisfy today's swift development trend. As a result, it is restructured and developed to a more intelligent power system named smart grid
[1]
. The smart grid mainly consists of several parts: generator(s), transmission system operator, distributor(s), retailer(s) and aggregator(s). Many technologies have been introduced into smart grid to ensure availability and economic benefits
[2
,
3]
. For instance, energy auction maret introduces commercial auctions to the smart grid, where energy sellers publish their auction information, and then energy buyers bid for appropriate energy supplies. Thus, the energy auction market can adjust energy prices and provide strong support for the practical application of smart grid
[4]
.
Though energy auction is promising, security and privacy are seriously challenged in energy auction market. Firstly, due to the confidentiality of auction information, privacy preservation is extremely important
[5
,
6]
. One solution is to introduce encrypted keyword search to smart grid, which enables the keyword search over encrypted data. But the existing encrypted keyword search schemes in smart grid auction market (e.g.,
[3]
) cannot achieve range query of keywords, which is extremely useful in smart grid
[7]
. For example, with the range of price keyword, energy buyers can filter out the energy with reasonable price. In addition, the existing range query scheme in smart grid
[7]
cannot be directly applied to auction market, and also cannot achieve the ranked search among multidimensional keywords.
In this paper, aim at addressing the above challenges, we propose an efficient multikeyword range query (EMRQ) scheme in smart grid auction market. The proposed scheme focuses on providing secure and efficient transactions between sellers and buyers, and supports range query, ranked search, personalized search and efficient aggregation at the same time.
Our Contributions.
The contributions of this paper are twofold:

• Firstly, we propose a novel EMRQ scheme to achieve searchable encryption which not only compares whether the keywords are equal, but also accurately calculates the difference between multidimensional keywords and further achieves range query, ranked search and personalized search. Security analysis demonstrates that the EMRQ scheme can achieve confidentiality of keywords, authentication, data integrity and query privacy.

• Secondly, based on the two superincreasing sequences, the proposed scheme can compare the multidimensional keywords of one buyer with those of all sellers with only one calculation, thereby greatly reducing the computation and communication overhead. We compare EMRQ with the existing auction scheme in[3]to show its efficiency.
Compared with the preliminary conference version
[1]
of this paper, this journal version studies the finegrained weight strategy to provide personalized search for buyers. Moreover, the privacypreservation of buyers is enhanced to ensure an adversary cannot get any privacy information about the bid auction. In addition, we improve the experimental works by adding the analysis and evaluation of the new scheme.
Organization.
The remainder of the paper is organized as follows: In Section 2, the network model and security requirements are formalized. We present the notation and recall Paillier cryptosystem in Section 3. In Section 4, we propose the EMRQ scheme. We analyze the security of our scheme in Section 5, and evaluate its performance in Section 6. In Section 7, we present related works. Finally, we conclude this paper in Section 8.
2. NETWORK MODEL AND SECURITY REQUIREMENTS
In this section, we will formalize the network model, security requirements and design goals.
 2.1 Network Model
In our network model, we focus on how to secretly compare keyword tags and trapdoors generated by the sellers and buyers, respectively. Specifically, we consider that our system consists of four parts, as shown in
Fig. 1
.

•Electricity generators (sellers):Sellers generate energy and sell it to retailers. For efficient search, they generate the search tags according to their auction keywords, and then send them to data center.

•Retailers (buyers):Buyers should provide energy to their own energy consumers. For economic purposes, they generate keyword trapdoors to bid the energy and send them to data center.

•Data Center (DC):Data center in our scheme is used as a database, it stores all tags and auction messages from sellers. If one buyer computes a trapdoor to bid some auction messages, DC will compare the trapdoor with all tags through homomorphic computing. Then, DC sends the result to filtering center.

•Filtering Center (FC):Filtering center is a trusted operation center which may be a supercomputer. It initiates our whole system at the beginning of energy auction. And after the comparison in DC, FC firstly filters auction keyword tags and then selects ranked results to the buyers.
Network model for smart auction market
 2.2 Security Requirements
In our scheme, we assume all entities are untrustworthy except FC. An adversary
A
can intrude in smart grid and eavesdrop or modify the messages with private information. Specifically, we define security requirements as follows.

•Confidentiality of keywords:All keywords generated by sellers and buyers should be sent to DC for comparing and filtering. These keywords are usually trade secrets. Hence, it is necessary to guarantee the confidentiality of keywords even though the adversaryAeavesdrops the communication links or DC’s database.

•Authentication and data integrity:In the system, legitimate users should be authenticated and the messages altered or fabricated by the adversaryAshould be detected.

•Query privacy:When the range query contains sensitive information, e.g., 1.2
 2.3 Design Goals
In order to realize the auction messages filtering in our scheme, our design goals are to develop an efficient finegrained keywords comparison with privacy preservation.

•Security is indispensable in the proposed scheme:If the auction market in smart grid doesn’t consider the security, it cannot be used in practice. Hence, we should guarantee confidentiality of keywords, authentication and data integrity, and range query.

•Computation and communication efficiency should be achieved in the proposed scheme:Compared with other auction schemes, our scheme should be more efficient in terms of computation and communication overhead.

•Keywords comparison should be finegrained in the proposed scheme:General schemes can only compare whether the keywords are equal. However, the difference of keywords computing will be very useful in the energy auction market. Thus, our scheme should achieve this goal.
3. Notations and Preliminaries
In this subsection, we introduce notations (
Table 1
) used throughout the remainder of this paper and review Bilinear Pairing and Paillier Cryptosystem.
Notations
 3.1 Notations
 3.2 Bilinear Pairing
Let
G
_{1}
and
G
_{2}
be two cyclic groups of prime order
q
, and
P
be a generator of group
G
_{1}
. There must exist a nondegenerated, efficiently computable bilinear map ê:
G
_{1}
×
G
_{1}
→
G
_{2}
such that ê(
P
,
P
) ≠ 1
_{G2}
. And for all
P
_{1}
,
P
_{2}
∈
G
_{1}
and all
a
,
b
∈
, we have ê(
aP
_{1}
,
bP
_{2}
) = ê(
P
_{1}
,
P
_{2}
)
^{ab}
. We refer to
[12]
for a more comprehensive description of pairing technique, and comple
x_{i}
ty assumptions.
 3.3 Paillier Cryptosystem
The Paillier cryptosystem consists of three phases as follows (refer to
[9]
):

•Setup:Given the security parameterκ1, two large prime numbersp1,q1can be chosen, where p1 = q1 =κ1. Then calculate the RSA modulusn=p1q1andλ=lcm(p1−1,q1−1). DefineL(u) =, and choose a generatorg∈. And then computeμ= (L(gλmodn2))−1modn. After that, the public key ispk= (n,g), and the private key issk= (λ,μ).

•Encryption:Given a message m ∈ ℤn, choose a random number r0∈, the ciphertext is c = E(m) = gm∙ r0nmod n2.

•Decryption:The messagemcan be recovered asm=D(c) =L(cλmodn2) ∙μ, wherecis the ciphertext.
4. Proposed Scheme
In this section, we propose the EMRQ scheme, which mainly consists of the following four phases: system initialization, auction message creating, trapdoor aggregating and filtering.
 4.1 System Initialization
Firstly,
FC
computes the Paillier cryptosystem’s public key (
n
,
g
), and the corresponding private key (
λ
,
μ
). Considering the multidimensional keywords of auction information, we expect that all keywords (price, quantity and location, etc.) can be aggregated to one number and the difference of all keywords can be gained by only one comparison. Therefore, we transform each dimension keyword to a positive integer. Assume that for
seller_{i}
, there are totally
l
types of auction keywords (
m
_{i,1}
,
m
_{i,2}
,⋯,
m_{i,l}
) (
m_{i,j}
∈ ℤ
_{n}
), and the value of each type
m_{i,j}
(
j
= 1,2,⋯,
l
) is less than a constant
d
. Then,
FC
chooses a superincreasing sequence
= (
a
_{1}
,
a
_{2}
,⋯,
a_{l}
), where
a
_{1}
,
a
_{2}
,⋯,
a_{l}
are integers,
a
_{1}
= 1 and
a_{j}
∙
d
<
a_{i}
/2 for (
i
= 2,⋯,
l
). The reason why we choose
a_{i}
/2 will be described in Section 4.4. Then,
FC
computes (
g
_{1}
,
g
_{2}
,⋯,
g_{l}
), where
g_{i}
=
g^{ai}
(
i
= 1,2,⋯,
l
).
Then we define
seller_{i}
’s aggregated number of multidimensional keywords is no more than a constant
D
, e.g.,
a_{j}
·
d
<
D
, and
FC
further chooses another superincreasing sequence
= (
b
_{1}
,
b
_{2}
,⋯,
b_{I}
) (
I
is the number of
sellers
), where
b
_{1}
= 1 and
b_{j}
∙
D
< =
b_{i}
/2. The reason why we choose
b_{i}
/2 will also be described in Section 4.4.
For identitybased signature, we also choose master key
s
∈
, and the associated public key
P_{pub}
=
sP
, two hash functions
H
_{1}
,
H
_{2}
: {0,1}
^{∗}
→
G
_{1}
, the privacy of all entities can be generated as
d
=
sH
_{1}
(
ID
) ∈
G
_{1}
.
After all,
FC
publishes the system parameters as
and keeps the master keys (
λ
,
μ
,
,
s
) secretly.
Auction Message Creating
The auction message creating process is shown in
Fig. 2
.
Auction message creating
(1)
Tag creating
Seller_{i}
selects auction keywords (
m
_{i,1}
,
m
_{i,2}
,⋯,
m_{i,l}
) according to corresponding auction information, then he chooses a random number
r_{i}
∈
and computes his tag:
where
M_{i}
=
a
_{1}
m
_{i,1}
+
a
_{2}
m
_{i,2}
+ ⋯ +
a_{l}m_{i,l}
.
(2)
Delivery
Seller_{i}
uses identitybased signature algorithm
[11]
to sign
C_{i}
. Firstly, pick
r
, compute
U
=
rP
∈
G
_{1}
, then
H
=
H
_{2}
(
ID_{Si}
,
C_{i}
║
TS
,
U
) ∈
G
_{1}
(where
ID_{Si}
is
seller_{i}
’s identity) and
V
=
d_{Si}
+
rH
∈
G
_{1}
. Finally, output the pair:
σ
= 〈
U
,
V
〉 ∈
G
_{1}
×
G
_{1}
.
Therefore, the signed message can be generated as
msg_{selleri}
_{→}
_{DC}
= (
C_{i}
║
ID_{Si}
║
TS
║
σ
) (
TS
is the current timestamp) and it will be sent to
DC
.
(3)
All sellers
’
tags aggregation
DC
verifies all
sellers
’ tags as follows: with
σ
= 〈
U
,
V
〉, compute
H
=
H
_{2}
(
ID_{Si}
,
C_{i}
║
TS
,
U
), and then accept it only if ê(
P
,
V
) = ê(
P_{pub}
,
H
_{1}
(
ID_{Si}
))ê(
U
,
H
). Then
DC
computes total tag as
C_{sel}
=
C
_{1}
∙
C
_{2}
∙ ⋯ ∙
C_{I}
, where
Trapdoor aggregating
The trapdoor aggregating process is shown in
Fig. 3
.
Trapdoor aggregating
(1)
Trapdoor creation and delivery
When
buyer_{j}
wants to bid the energy, he first generates filtering keywords (
m
_{j,1}
,
m
_{j,2}
,⋯ ,
m_{j,l}
) (0 <
m_{j,k}
<
d
,1 ≤
k
≤
l
) and randomly chooses
r_{j}
∈
, then computes his trapdoor
where
M_{j}
=
a
_{1}
m
_{j,1}
+
a
_{2}
m
_{j,2}
+ ⋯ +
a_{l}m_{j,l}
. And then
buyer_{j}
calculates the total trapdoor as
C_{buy}
=
C_{j}
^{′b1+b2+⋯+bI}
, where
After that,
buyer_{j}
generates a matching rule sequence
R
= (
R
_{1}
,
R
_{2}
, … ,
R_{l}
). If
buyer_{j}
defines the range of auction keyword as
v
_{1}
≤
m_{i,k}
≤
v
_{2}
(
v
_{1}
,
v
_{2}
∈ ℤ
_{n}
), then
R_{k}
should be a pair:
g
^{v1−mj,k}
,
g
^{v2−mj,k}
. Based on the filtering rules,
buyer_{j}
can define a keyword weight sequence (
W
_{1}
,
W
_{2}
, … ,
W_{l}
) for all auction keywords
m_{i,k}
(
k
= 1,2,⋯,
l
), the keyword weight
W_{k}
represents the keyword importance defined by
buyer_{j}
. The finegrained weight strategy can provide personalized search for buyers. Speciafically, the weight strategy is as follows:
Weight strategy:

•Buyerjdefines the weight of each keyword, the weights of some important keywords may be larger than those of other keywords. Specially, ifbuyerjdefines all weights as the same, the more filtering rules thatsellerisatisfies, the higher prioritysellerihas.

•Buyerjsorts the keywords in ascending importance, and ifsellericontains a more important keyword compared with othersellers,sellerihas higher priority in the returned result. To achieve this goal, a superincreasing sequence= (c1,c2,⋯,cl) will be generated, wherec1,c2,⋯,cl∈,c1= 1 andW4>W5>W1>W3), there will be (W1,W2,W3,W4,W5) = (3, 20, 1, 10, 5).
Next, the keyword weight sequence can be encrypted as
W
=(
g
^{W1}
,
g
^{W2}
,⋯,
g^{Wl}
). Then
buyer_{j}
signs (
C_{buy}
║
R
║
W
║
TS
) using the identitybased signature algorithm
[11]
. The alogrithm is as follow: pick
r
, compute
U
=
rP
∈
G
_{1}
,
H
=
H
_{2}
(
ID_{Bi}
,
C_{buy}
║
R
║
W
║
TS
,
U
) (where
ID_{Bj}
is
buyer_{j}
’s identity) and
V
=
d_{Bj}
+
rH
∈
G
_{1}
. Finally, output the pair:
σ
= 〈
U
,
V
〉∈
G
_{1}
×
G
_{1}
. Then,
buyer_{j}
sends the signed message
msg_{buyerj}
_{→DC}
=(
C_{buy}
║
R
║
W
║
ID_{Bj}
║
TS
║
σ
) to
DC
, and
DC
accepts it after verifying asê(
P
,
V
)=ê(
P_{pub}
,
H
_{1}
(
ID_{Bi}
))ê(
U
,
H
), where
H
=
H
_{2}
(
ID_{Bi}
,
C_{buy}
║
R
║
W
║
TS
,
U
).
(2)
Homomorphic computing for comparison
When
DC
wants to compare
sellers
’ tags with
buyer_{j}
’s trapdoor. It can compute
C
=
C_{sel}
∙
C_{buy}
. Then,
DC
sends the signed message
msg_{DC→FC}
=(
C
║
R
║
ID_{DC}
║
ID_{Bj}
║
TS
║
σ
) to
FC
, where
σ
is the signature of (
C
║
R
║
ID_{DC}
║
ID_{Bj}
║
TS
) using the identitybased signature algorithm
[11]
.
Filtering
The filtering process is shown in
Fig. 4
.
Filtering
(1)
Decrypting the result of comparison
After receiving the message (
C
║
R
║
ID_{DC}
║
ID_{Bj}
║
TS
║
σ
), check the signature
σ
using the identitybased signature algorithm
[11]
, if it is valid,
FC
decrypts
C
, where
C
is formed by
where
M_{i,j}
=
M_{i}
−
M_{j}
=
a
_{1}
(
m
_{i,1}
−
m
_{j,1}
) +
a
_{2}
(
m
_{i,2}
−
m
_{j,2}
) + ⋯ +
a_{l}
(
m_{i,l}
−
m_{j,l}
) and
M_{total}
=
b_{i}
M_{i,j}
.
FC
uses
sk
to recover
M_{total}
as Section 3.3. After that,
FC
gets (
M
_{1,j}
,
M
_{2,j}
,⋯,
M_{I,j}
) by running
Algorithm 1
with input
and
SUM
=
M_{total}
.
As shown in
Algorithm 1
, we define
sum_{i}
=
b
_{1}
M
_{1,j}
+
b
_{2}
M
_{2,j}
+ ⋯ +
b_{i}M_{i,j}
(
i
= 1,2,⋯,
I
). We compute
sum
_{i−1}
=
sum_{i}
mod
x_{i}
, hence we have 0 ≤
sum
_{i−1}
≤
x_{i}
. Since we have defined
b_{j}
∙
D
<
b_{i}
/2, we have −
x_{i}
/2 ≤
sum
_{i−1}
≤
x_{i}
/2 (for example: 0 <
ε_{i}
,
ε_{j}
<
t
⇒ −
t
<
ε_{i}
−
ε_{j}
<
t
). Thus, in
Algorithm 1
, if the calculated
sum
_{i−1}
is 0≤
sum
_{i−1}
≤
x_{i}
/2, this is the right result; else if
x_{i}
/2 <
sum
_{i−1}
<
x_{i}
, we must correct it as
sum
_{i−1}
=
sum
_{i−1}
−
x_{i}
, the true result is −
x_{i}
/2 <
sum
_{i−1}
< 0. That is why we choose
b_{i}
/2 in
b_{j}
∙
D
<
b_{i}
/2 and
a_{i}
/2 in
a_{j}
∙
d
<
a_{i}
/2, it can split the aggregation including negative numbers.
After getting (
M
_{1,j}
,
M
_{2,j}
,⋯,
M_{I,j}
),
FC
can use
Algorithm 1
with input
and
SUM
=
M_{i,j}
(
i
= 1,2,⋯,
I
) to gain all differences of the multidimensional keywords
DIF_{i,j}
= (
dif
_{i,j,1}
,
dif
_{i,j,2}
,⋯,
dif_{i,j,l}
) between
seller_{i}
and
buyer_{j}
.
(2)
Choosing winners
With the keyword difference
DIF_{i,j}
= (
dif
_{i,j,1}
,
dif
_{i,j,2}
,⋯,
dif_{i,j,l}
) and filtering rules (
R
_{1}
,
R
_{2}
, … ,
R_{l}
), we can achieve range query. If each
dif_{i,j,k}
(
k
= 1,2,⋯,
l
) satisfies the filtering rule
R_{k}
(i.e.,
v
_{1}
−
m_{j,k}
≤
dif_{i,j,k}
≤
v
_{2}
−
m_{j,k}
),
k
will be stored in an array
K_{i}
[].
After getting the array
K_{i}
[] (
i
= 1,2,⋯,
I
),
FC
further sends it to
DC
. Then, randomly chooses
r′
∈
,
DC
generates the weight of
seller_{i}
as follows:
All
weight_{i}
(
i
= 1,2,⋯,
I
) will be sent to
FC
and decrypted according to Paillier cryptosystem
[9]
as shown in equation (8).
According to the weight of each
seller_{i}
, i.e., ∑
_{k∈Ki[]}
W_{k}
, the ranked result array
winner′
[] = (
ID′
_{1}
,
ID′
_{2}
,
ID′
_{3}
, ⋯) can be obtained. Finally,
FC
sends the message (
winner′
[]║
ID_{FC}
║
TS
), i.e., the ranked result, to
DC
through a secure channel.
Theorem 1
.
For the keyword weight sequence
W
′=(
W
_{k1}
,
W
_{k2}
, … ,
W_{kl}
)
which is ordered by the ascending weights, where W_{kl} = c_{l} . If seller
_{1}
contains a more important keyword (Suppose that the largest keyword weight for seller
_{1}
is c
_{k1}
) compared with seller
_{2}
(Suppose that the largest keyword weight for seller
_{2}
is c
_{k2}
), i.e., k
_{1}
≥
k
_{2}
+ 1,
then seller
_{1}
has higher priority in the returned winner′
[],
i.e., weight
_{1}
>
weight
_{2}
.
Proof
. Because
c_{j}
<
c_{i}
, we have
5. Security Analysis
In this section, we analyze the security properties of our proposed scheme. In particular, based on the security requirements discussed in Section 2.2, our analysis focuses on how to achieve confidentiality of keywords, authentication, data integrity and query privacy.
 5.1 Confidentiality of Keywords
In our proposed scheme, all the types of tag’s keywords (
m_{i,1}
,
m_{i,2}
,⋯,
m_{i,l}
) (
m_{i,j}
∈ ℤ
_{n}
) are aggregated to
c_{i}
as
That means that
C_{i}
is a ciphertext of Paillier cryptosystem, similarly,
C_{j}
,
C_{buy}
and
C_{sel}
are the same. Due to the security of Paillier cryptosystem
[9]
, the confidentiality of keywords is protected. And in
DC
, since it only does homomorphic computing on
C_{buy}
and
C_{sel}
, it cannot identify the tag or trapdoor. In the end,
FC
will decrypt
C
for the range comparison of keywords. But
FC
cannot gain each
seller
/
buyer’
s keywords, because the result is only a difference, e.g.,
M_{i,j}
=
M_{i}
−
M_{j}
,
FC
cannot recover the corresponding
M_{i}
and
M_{j}
. In addition, with the superincreasing sequence
= (
b
_{1}
,
b
_{2}
,⋯,
b_{I}
), the parameter
D
might be estimated. However,
D
is a large integer and it would not disclosure the specific keyword information. Therefore, the proposed scheme can achieve the confidentiality of keywords.
 5.2 Encrypted Messages’ Authentication and Data Integrity
The tags
C_{i}
(
i
=
1
,
2
, ⋯) and total trapdoor
C_{buy}
in our proposed scheme are encrypted by Paillier cryptosystem, therefore the adversary
A
cannot identify them, but if the adversary
A
fabricates a message and sends it to some entities, it cannot be detected. Hence, we also sign them by the signature algorithm
[11]
. Therefore, our proposed scheme can achieve such messages’ authentication and data integrity.
 5.3 Query Privacy
The range information and keyword weights are stored in two sequences
R
and
W
, respectively, which should be encrypted to prevent the disclosure of privacy. As shown in 4.3.1,
R
║
W
is encrypted by Paillier cryptosystem. Thus, only
FC
can use its private key
sk
= (
λ
,
μ
) to decrypt
R
║
W
. In addition, As shown in
(2) Choosing winners
of Section 4.4, only a part of keyword weights
weight_{i}
=∏
_{k∈Ki[]}
g^{Wk}
are sent to the filter center, where
K_{i}
[] is an array storing the keywords which satisfy the corresponding matching rules. The filter center can only get the total weight of
seller_{i}
, i.e., ∑
_{k∈Ki[]}
W_{k}
, it cannot identify the weight of each keyword. Therefore, the query privacy is achieved.
In
Table 2
, we compare EMRQ with PaRQ
[8]
and SESA
[3]
. We can see all schemes achieve confidentiality of keywords, authentication and data integrity, PaRQ and EMRQ further achieve query privacy.
Comparison of Security Level
Comparison of Security Level
6. Performance Evaluation
In this section, we evaluate the performance of EMRQ in terms of functionality, computation and communication overhead.
 6.1 Functionality
We compare the functionalities of EMRQ with SESA
[3]
and PaRQ
[8]
. As shown in
Table 3
, SESA achieves multikeyword search in smart grid auction market, PaRQ further achieves range query, but only EMRQ scheme can achieve multikeyword, range query, ranked search and personalized search simultaneously.
Comparison of Functionalities
Comparison of Functionalities
 6.2 Computation Overhead
For simplicity, the cost of a pairing operation, a multiplication operation in
G
_{1}
, an exponentiation operation in ℤ
_{n2}
and an exponentiation operation in ℤ
_{n}
are denoted as
C_{p}
,
C_{m}
,
C
_{en2}
and
C_{en}
, respectively. Compared with above operations, other operations in EMRQ and SESA are negligible
[13]
.
In EMRQ, it costs 2
C_{m}
to sign a message, and 2
C_{p}
to verify if we adopt precomputed technology
[11]
. For
seller_{i}
, he needs (
l
+ 1)
C
_{en2}
+
C_{en}
to create tags
C_{i}
and 2
C_{m}
to sign it. Therefore, all sellers’ cost is (2
C_{m}
+(
l
+ 1)
C
_{en2}
+
C_{en}
)
I
. For
buyer_{j}
, he costs
lC
_{en2}
+
C_{en}
to create tags
C′_{j}
and
C
_{en2}
to create
C′_{total}
. Then he encrypts (
R
║
W
) with 3
lC
_{en2}
. Finally, he costs 2
C_{m}
to sign it. Hence, all
buyers
’ cost is (2
C_{m}
+ (4
l
+ 1)
C
_{en2}
+
C_{en}
)
J
(assume
J
is the number of
buyers
). For
DC
, it needs 2(
I
+
J
)
C_{p}
to verify all messages of
sellers
and
buyers
. For every
buyer_{j}
,
DC
needs to sign a message
msg_{DC→FC}
= (
C
║
R
║
W
║
ID_{DC}
║
ID_{Bj}
║
TS
) to
FC
, the signature costs 2
JC_{m}
. Therefore,
DC
’s cost is 2
JC_{m}
+ (2
I
+ 2
J
)
C_{p}
. For
FC
, it needs total 2
JC_{p}
to verify the messages from
DC
, then decrypts
C
,
R
and
weight_{i}
with
JC
_{en2}
, 2
lJC
_{en2}
and
JC
_{en2}
. Hence,
FC
’s cost is (2
l
+ 2)
JC
_{en2}
+ 2
JC_{p}
. Therefore, in our proposed EMRQ, the total computation overhead is (4
J
+ 2
I
)
C_{m}
+ ((
l
+ 1)
I
+ (6
l
+ 3)
J
)
C
_{en2}
+ (
J
+
I
)
C_{en}
+ (4
J
+ 2
I
)
C_{p}
.
In the SESA scheme, we assume it adopts the same signature technology and two cyclic addition groups
G
_{1}
,
G
_{2}
.
EB_{j}
makes a bid to
EDR_{i}
which costs 3
C_{m}
+ 2
C_{p}
, and the corresponding signature needs 2
C_{m}
, thus all energy
buyers
’ cost is 5
IJC_{m}
+ 2
IJC_{p}
where each
EB
expects to make a bid to each
EDR
because
EB
cannot know which bid will be accepted;
EDR_{i}
needs
C_{m}
to create a trapdoor and 2
C_{m}
to sign it, therefore
EDR_{i}
’s cost is 3
IC_{m}
;
AS
needs 2
C_{p}
to verify a message which will be
IJ
+
I
times, and
C_{p}
to compare each tag which will be
IJ
times, hence
AS
’s cost is (3
IJ
+ 2
I
)
C_{p}
;
RS
needs
C_{m}
+
C_{p}
to decrypt a satisfied
bid
, assume that in SESA there are average
N
tags matching the trapdoor in once bid, therefore its total cost is
IN
(
C_{m}
+
C_{p}
). Therefore, in SESA the total computation overhead is (5
IJ
+ 3
I
+
IN
)
C_{m}
+ (2
IJ
+ 2
I
+
IN
)
C_{p}
.
We conduct detailed experiments on Pentium IV 3GHz system to study the operation cost
[13]
. For
G
_{1}
over MNT curve, a multiplication operation in
G
_{1}
with 161 bits, and the corresponding pairing operation cost 0.6 ms and 4.5 ms. And an exponentiation operation costs 11.5 ms in ℤ
_{n2}
and 2.3 ms in ℤ
_{n}
. Further, we assume
N
= 0.1 ×
J
in SESA and
l
= 10. As shown in
Fig. 5
and
Fig. 6
, the proposed scheme greatly reduces the computation overhead.
Computation overhead of EMRQ
Computation overhead of SESA
 6.3 Communication Overhead
We divide the communication overhead of our proposed scheme into three types,
seller
−
DC
,
buyer
−
DC
and
DC
−
FC
, where the delivery of winner messages are the same in SESA and our scheme, we do not compare. The message
seller
sends to
DC
is formed by
msg_{selleri→DC}
= (
C_{i}
║
ID_{Si}
║
TS
║
σ
) where the signature
σ
includes two elements in
G
_{1}
, therefore if we choose 1024bit
and 161bit
G
_{1}
, the total size of
seller
−
DC
communication overhead is (2048 + 
ID
 + 
TS
 + 2 × 161) ×
I
bits. The message of
buyer
−
DC
is formed by
msg_{buyerj→DC}
=(
C_{buy}
║
R
║
W
║
ID_{Bj}
║
TS
), each
R_{k}
(
k
= 1,2,⋯,
l
) includes two ciphertexts of Paillier Cryptosystem, and
W_{k}
includes one. Thus its total size is(2048 × (3
l
+ 1)+
ID
+
TS
 + 2 × 161) ×
J
bits. In
DC
−
FC
phase, there are
J
messages of
msg_{DC→FC}
=(
C
║
R
║
ID_{DC}
║
ID_{Bj}
║
TS
) and (
weight_{i}
║
ID_{DC}
║
ID_{Bj}
║
TS
), the total size is (2048 × (2
l
+ 2) + 4 × 
ID
 + 2 × 
TS
 + 2 × 161) ×
J
bits.
In comparison, in SESA,
EB
−
to
−
AS
phase needs
IJ
messages of 963 bits, therefore the size is 963 ×
IJ
bits;
DER
−
to
−
AS
needs to delivery a trapdoor of 160 bits and the corresponding signature of 161 × 2 bits, the total size is (160 + 2 × 161) ×
I
bits; in
AS
−
to
−
RS
phase, for each
DER
, there are
N
ciphertexts
C_{j}
of 160 bits and signatures of 161 × 2 bits, hence the total size is (160 + 2 × 161) ×
IN
bits.
We set 
ID
 + 
TS
 as 50 bits, then the comparison of total communication overhead for SESA and EMRQ are 482
I
+ 963
IJ
+ 482
IN
bits and 2420
I
+ 109388
J
bits, respectively. As shown in
Fig. 7
and
Fig. 8
, EMRQ is more efficient than SESA.
Communication overhead of EMRQ
Communication overhead of SESA
7. RELATED WORKS
The traditional auction market has been widely studied and many famous auction web sites have been applied to practice (e.g., Yahoo!, eBay, etc.)
[14
,
15]
. Recently, online auction becomes more popular, many people prefer to shop on the internet. Song et al.
[16]
estimate the behaviors of the rivals and present the bid. Chang et al.
[17]
present anonymous auction protocol with freewheeling bids.
In power market, auction technology has been extensively studied and various auction models are presented
[2
,
14
,
18
,
20]
. Nguyen et al.
[2]
propose a demand respond exchange scheme, which thinks of demand respond as a kind of virtual goods. Li et al.
[14]
propose a auction scheme with privacy, which can also achieve anonymity bidding. Bompard et al.
[18]
propose supply function models in power market, which support supplyside strategic bidding. Liaw et al.
[19]
propose an electronic online bidding auction protocol, which can achieve the corresponding security and efficiency. Based on game theory, Kanga et al.
[20]
define oligopolistic strategy to efficient auction in power market.
Auction market in smart grid has attracted a lot of attention due to the remarkable economic benefits in electricity trading
[21
,
22]
. The corresponding issues have been extensively studied and various auction market schemes have been proposed to protect its security
[3
,
8
,
23]
. Wen et al.
[3]
propose a searchable encryption scheme (SESA) for auctions between energy generators and retailers. In SESA, each buyer makes a different tag message for every seller’s energy he wants to bid. In this case, the computation and communication overheads are heavy. And Wen et al.
[8]
also propose a novel privacypreserving range query (PaRQ) scheme over encrypted metering data, which protects the privacy of financial auditing in smart grid. Lu et al.
[24]
adopt a super increasingsequence to aggregate all types of electricity data. In such a scheme, the intermediate can achieve privacy preservation and efficiency, without decrypting the received messages. Therefore, it is feasible to introduce this method into searchable encryption auction market.
In addition, querying encrypted data has been extensively studied because of its wide range of applications. The first work can refer to Song et al.
[25]
, which embeds a symmetric key setting to search on encrypted data, and its improvements and advanced security definitions are given in Goh
[26]
, Chang et al.
[27]
, and Curtmola et al.
[28]
. Recently, many searchable encryption schemes
[29

33]
have also been proposed to query outsourced data without disclosing any private information to unauthenticated entities. A relevance score scheme is presented by Wang et al.
[29]
, which uses relevance score to achieve ranked query of keyword. And Li et al.
[30]
propose a fuzzy keyword search scheme which is purposed to solve minor typos and format inconsistencies in keyword search. Cao et al.
[31]
propose a widely used searchable encryption scheme, which can return the ranked results of search according to the number of matching keywords. Then, a multikeyword topk scheme is proposed by Yu et al.
[32]
, such scheme returns ranked results and achieves high security with fully homomorphic encryption. Sun et al.
[33]
consider the multidimensional tree technique and the relevance scores of keywords, this scheme supports multikeyword search and it can achieve efficient query. In our scheme, with a super increasingsequence, we achieve the efficient multikeyword range query of the encrypted auction.
8. CONCLUSION
In this paper, we have proposed an efficient multikeyword range query (EMRQ) scheme for the auction market in smart grid. It can achieve range query, ranked search and personalized search simultaneously. Security analysis demonstrates that EMRQ can achieve confidentiality of keywords, authentication, data integrity and query privacy. Performance evaluation shows that the proposed scheme significantly improves computation and communication efficiency compared with the SESA scheme in
[3]
.
BIO
Hongwei Li received his M.S. degree in Computer Application from Southwest Jiaotong University (SWJTU) and Ph.D. degree in Computer Software and Theory from University of Electronic Science and Technology of China (UESTC) in 2004 and 2008 respectively. From 2011 to 2012, he worked as a Postdoctoral Fellow at University of Waterloo, Canada. Currently, he is an associate professor at the School of Computer Science and Engineering, UESTC, China. His research interests include cryptography, and the secure smart grid. Dr. Li serves as the Associate Editor of PeertoPeer Networking and Applications, the Guest Editor for Peer to Peer Networking and Applications Special Issue on Security and Privacy of P2P Networks in Emerging Smart City. He also serves on the technical program committees for many international conferences such as IEEE INFOCOM, IEEE ICC, IEEE GLOBECOM, IEEE WCNC, etc. He is a member of IEEE, a member of China Computer Federation and a member of China Association for Cryptologic Research.
Yi Yang received his B.S. degree in Network Engineering from Tianjin University of Science and Technology (TUST) in 2012. Currently, he is a master student at the School of Computer Science and Engineering, University of Electronic Science and Technology of China (UESTC), China. He serves as the reviewer of PeertoPeer Networking and Application, IEEE INFOCOM, IEEE ICC, IEEE GLOBECOM, IEEE ICCC, etc. His research interests include cryptography, and the secure smart grid.
Mi Wen received her M.S. degree in Computer Software and Theory from University of Electronic Science and Technology of China (UESTC) and Ph.D. degree in computer system structure from Shanghai Jiaotong University of China (SJTU) in 2004 and 2008, respectively. From 2012 to 2013, she worked as a Visting Scholar at University of Waterloo, Canada. Currently, she is an associate professor at the College of Computer Science and Technology, Shanghai University of Electric Power, China. Her research interests include applied cryptography, and the security in smart grid. Dr. Wen serves as the Associate Editor of PeertoPeer Networking and Application. She also serves on the technical program committees for many international conferences such as IEEE INFOCOM, IEEE ICC, IEEE GLOBECOM, IEEE ICCC, etc. She is a member of IEEE, a member of China Computer Federation and a member of China Association for Cryptologic Research.
Hongwei Luo received his B.S.and M.S. degrees from Beijing University of Posts and Telecommunications (BUPT), in 1998 and 2003, respectively. Now, He is a PhD candidate in BUPT, majoring in information security. From 1998 to 2003, he served as an engineer in China Telecom. He is a senior engineer and the deputy director of Department of Information Security, Telecommunication Terminal Technology Labs, China Academy of Telecom Research (CATR). He was a visiting scholar in University of Waterloo from 2011 to 2012. From 2005 till now, He has been acting as the rapporteur of ITUT Q.5/17, countering spam by technical means and has published 3 ITUT recommendations. From 2014, he has also been selected as the chairman of China Communications Standards Association (CCSA) WG3/TC11, Terminal Workgroup. He has published more than 20 national standards, 2 patents, 2 conference papers and more than 50 magazine articles. His research interests include wireless communications, routing and switching, information security and performance evaluation.
Rongxing Lu received the Ph.D degree in computer science from Shanghai Jiao Tong University, Shanghai, China in 2006 and the Ph.D. degree (awarded Canada Governor General Gold Medal) in electrical and computer engineering from the University of Waterloo, Waterloo, Ontario, Canada, in 2012. Since May 2013, he has been with the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, as an Assistant Professor. His research interests include computer, network and communication security, applied cryptography, security and privacy analysis for vehicular network, eHealthcare system, and smart grid communications. He won the IEEE Communications Society (ComSoc) Asia Pacific (AP) Outstanding Young Researcher Award in 2013.
Yang Y.
,
Li H.
,
Wen M.
,
Luo H.
,
Lu R.
“Achieving ranked range query in smart grid auction market,”
in Proc. of ICC
2014
951 
956
Li H.
,
Lin X.
,
Yang H.
,
Liang X.
,
Lu R.
,
Shen X.
2014
“Eppdr: an efficient privacypreserving demand response scheme with adaptive key evolution in smart grid,”
IEEE Transactions on Parallel and Distributed Systems
25
(8)
2053 
2064
DOI : 10.1109/TPDS.2013.124
Wen M.
,
Lu R.
,
Lei J.
,
Li H.
,
Liang X.
,
Shen X.
2014
“Sesa:an efficient searchable encryption scheme for auction in emerging smart grid marketing,”
Security and Communication Networks
7
(1)
234 
244
DOI : 10.1002/sec.699
Liang H.
,
Choi B.
,
Zhuang W.
,
Shen X.
“Towards optimal energy storecarryanddeliver for phevs via v2g system,”
in Proc. of INFOCOM
2012
1674 
1682
Liang H.
,
Choi B.
,
Abdrabou A.
,
Zhuang W.
,
Shen X.
2012
“Decentralized economic dispatch in microgrids via heterogeneous wireless networks,”
IEEE Journal on Selected Areas in Communications
30
(6)
1061 
1074
DOI : 10.1109/JSAC.2012.120705
Li H.
,
Liang X.
,
Lu R.
,
Lin X.
,
Shen X.
“Edr: an efficient demand response scheme for achieving forward secrecy in smart grid,”
in Proc. of GLOBECOM
2012
929 
934
Li H.
,
Lu R.
,
Zhou L.
,
Yang B.
,
Shen X.
2014
“An efficient merkle tree based authentication scheme for smart grid,”
IEEE Systems Journal
8
(2)
655 
663
DOI : 10.1109/JSYST.2013.2271537
Wen M.
,
Lu R.
,
Zhang K.
,
Lei J.
,
Liang X.
,
Shen X.
2013
“PaRQ: a privacy preserving range Query scheme over encrypted metering data for smart grid,”
IEEE Transactions on Emerging Topics in Computing
1
(1)
178 
191
DOI : 10.1109/TETC.2013.2273889
Paillier P.
“Publickey cryptosystems based on composite degree residuosity classes,”
in Proc. of EUROCRYPT
1999
223 
238
Ferguson N.
,
Schroeppel R.
,
Whiting D.
“A simple algebraic representation of rijndael,”
in Proc. of Selected Areas in Cryptography
2001
103 
111
Libert B.
,
Quisquater J.
“The exact security of an identity based signature and its applications,”
http://eprint.iacr.org/2004/102
Boneh D.
,
Franklin M. K.
“Identitybased encryption from the weil pairing,”
in Proc. of CRYPTO
2001
213 
229
“Multiprecision integer and rational arithmetic c/c++library,”
http://www.certivox.com/miracl/
Li M.
,
Justie S.
,
Jennifer H.
2011
“Practical electronic auction scheme with strong anonymity and bidding privacy,”
Information Science
181
(12)
2576 
2586
DOI : 10.1016/j.ins.2011.02.005
Chakraborty S.
,
Weiss M.
,
Simoes M.
2007
“Distributed intelligent energy management system for a singlephase highfrequency ac microgrid,”
IEEE Transactions on Industrial Electronics
54
(1)
97 
109
DOI : 10.1109/TIE.2006.888766
Song Y.
,
Ni Y.
,
Wen F.
“An improvement of generation firm’s bidding strategies based on conjectural variation regulation via dynamic learning,”
In Proc. of the CSEE
2003
http://en.cnki.com.cn/Article_en/CJFDTOTALZGDC200312004.htm
23 
27
Chang Y.
,
Chang C.
“Enhanced anonymous auction protocols with freewheeling bids,”
In Proc. of 20th International Conference on Advanced Information Networking and Application (AINA06)
2006
353 
358
Bompard E.
,
Lu W.
,
Napoli R.
2006
“Network constraint impacts on the competitive electrically markets under supplyside strategic bidding,”
IEEE Transactions on Power System
21
(1)
160 
170
DOI : 10.1109/TPWRS.2005.857833
Liaw H. T.
,
Juang W. S.
,
Lin C. K.
2006
“An electronic online bidding auction protocol with both security and efficiency,”
Applied Mathematics and Computation
174
(2)
1487 
1497
DOI : 10.1016/j.amc.2005.06.016
Kanga D. J.
,
Kimb B. H.
,
Hur D.
2007
“Supplier bidding strategy based on noncooperative game theory concepts in single auction power pools,”
Electric Power Systems Research
77
(5)
630 
636
DOI : 10.1016/j.epsr.2006.05.012
Jiang R.
,
Lu R.
,
Luo J.
,
Lai C.
,
Shen X.
2014
“Efficient selfhealing group key management with dynamic revocation and collusion resistance for SCADA in smart grid,”
Security and Communication Networks
Jiang R.
,
Lu R.
,
Wang Y.
,
Luo J.
,
Shen C.
,
Shen X.
2014
“Energytheft detection issues for advanced metering infrastructure in smart grid,”
TSINGHUA SCIENCE AND TECHNOLOGY
19
(2)
105 
120
DOI : 10.1109/TST.2014.6787363
Liu D.
,
Li H.
,
Yang Y.
,
Yang H.
“Achieving multiauthority access control with efficient attribute revocation in smart grid,”
in Proc. of ICC
2014
634 
639
Lu R.
,
Liang X.
,
Li X.
,
Lin X.
,
Shen X.
2012
“Eppa: an efficient and privacy preserving aggregation scheme for secure smart grid communications,”
IEEE Transactions on Parallel and Distributed Systems
23
(9)
1621 
1631
DOI : 10.1109/TPDS.2012.86
Song D.
,
Wagner D.
,
Perrig A.
“Practical techniques for searches on encrypted data,”
in Proc. of IEEE Symp. Security and Privacy
2000
44 
55
Goh E. J.
2003
“Secure Indexes,”
http://eprint.iacr.org/2003/216
Chang Y. C.
,
Mitzenmacher M.
“Privacy preserving keyword searches on remote encrypted data,”
in Proc. of Third Int’l Conf. Applied Cryptography and Network Security
2005
442 
455
Curtmola R.
,
Garay J.A.
,
Kamara S.
,
Ostrovsky R.
“Searchable symmetric encryption: improved definitions and efficient constructions,”
in Proc. of 13th ACM Conf. Computer and Comm. Security (CCS ’06)
2006
79 
88
Wang C.
,
Cao N.
,
Ren K.
,
Lou W.
2012
“Enabling secure and efficient ranked keyword search over outsourced cloud data,”
IEEE Transactions on Parallel and Distributed Systems
23
(8)
1467 
1479
DOI : 10.1109/TPDS.2011.282
Li J.
,
Wang Q.
,
Wang C.
,
Cao N.
,
Ren K.
,
Lou W.
“Fuzzy keyword search over encrypted data in cloud computing,”
in Proc. of INFOCOM
2010
1 
5
Cao N.
,
Wang C.
,
Li M.
,
Ren K.
,
Lou W.
2014
“Privacypreserving multikeyword ranked search over encrypted cloud data,”
IEEE Transactions on Parallel and Distributed Systems
25
(1)
222 
233
DOI : 10.1109/TPDS.2013.45
Yu J.
,
Lu P.
,
Zhu Y.
,
Xue G.
,
Li M.
2013
“Towards secure multikeyword topk retrieval over encrypted cloud data,”
IEEE Transactions on Dependable and Secure Computing
10
(4)
239 
250
DOI : 10.1109/TDSC.2013.9
Sun W.
,
Wang B.
,
Cao N.
,
Li M.
,
Lou W.
,
Hou Y. T.
,
Li H.
2013
“Verifiable privacypreserving multikeyword text search in the cloud supporting similaritybased ranking,”
IEEE Transactions on Parallel and Distributed Systems