Advanced
EMRQ: An Efficient Multi-keyword Range Query Scheme in Smart Grid Auction Market
EMRQ: An Efficient Multi-keyword Range Query Scheme in Smart Grid Auction Market
KSII Transactions on Internet and Information Systems (TIIS). 2014. Nov, 8(11): 3937-3954
Copyright © 2014, Korean Society For Internet Information
  • Received : August 11, 2014
  • Accepted : September 18, 2014
  • Published : November 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hongwei Li
School of Computer Science & Engineering, UESTC Chengdu, 610054 - China
Yi Yang
School of Computer Science & Engineering, UESTC Chengdu, 610054 - China
Mi Wen
College of Computer Science and Technology, Shanghai University of Electric Power Shanghai, 200090 - China
Hongwei Luo
China Academy of Telecom Research, MIIT Beijing, 100191 - China
Rongxing Lu
School of Electrical and Electronics Engineering, Nanyang Technological University 639798 - Singapore

Abstract
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 multi-keyword range query (EMRQ) scheme, which can support range query, ranked search and personalized search simultaneously. Based on the homomorphic Paillier cryptosystem, we use two super-increasing 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.
Keywords
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 multi-keyword 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 super-increasing 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 fine-grained weight strategy to provide personalized search for buyers. Moreover, the privacy-preservation 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.
PPT Slide
Lager Image
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 fine-grained 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 fine-grained 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
PPT Slide
Lager Image
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 non-degenerated, 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
PPT Slide
Lager Image
, 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 xi 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 selleri , there are totally l types of auction keywords ( m i,1 , m i,2 ,⋯, mi,l ) ( mi,j ∈ ℤ n ), and the value of each type mi,j ( j = 1,2,⋯, l ) is less than a constant d . Then, FC chooses a super-increasing sequence
PPT Slide
Lager Image
= ( a 1 , a 2 ,⋯, al ), where a 1 , a 2 ,⋯, al are integers, a 1 = 1 and
PPT Slide
Lager Image
aj d < ai /2 for ( i = 2,⋯, l ). The reason why we choose ai /2 will be described in Section 4.4. Then, FC computes ( g 1 , g 2 ,⋯, gl ), where gi = gai ( i = 1,2,⋯, l ).
Then we define selleri ’s aggregated number of multidimensional keywords is no more than a constant D , e.g.,
PPT Slide
Lager Image
aj · d < D , and FC further chooses another super-increasing sequence
PPT Slide
Lager Image
= ( b 1 , b 2 ,⋯, bI ) ( I is the number of sellers ), where b 1 = 1 and
PPT Slide
Lager Image
bj D < = bi /2. The reason why we choose bi /2 will also be described in Section 4.4.
For identity-based signature, we also choose master key s
PPT Slide
Lager Image
, and the associated public key Ppub = 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
PPT Slide
Lager Image
and keeps the master keys ( λ , μ ,
PPT Slide
Lager Image
, s ) secretly.
Auction Message Creating
The auction message creating process is shown in Fig. 2 .
PPT Slide
Lager Image
Auction message creating
(1) Tag creating
Selleri selects auction keywords ( m i,1 , m i,2 ,⋯, mi,l ) according to corresponding auction information, then he chooses a random number ri
PPT Slide
Lager Image
and computes his tag:
PPT Slide
Lager Image
where Mi = a 1 m i,1 + a 2 m i,2 + ⋯ + almi,l .
(2) Delivery
Selleri uses identity-based signature algorithm [11] to sign Ci . Firstly, pick r
PPT Slide
Lager Image
, compute U = rP G 1 , then H = H 2 ( IDSi , Ci TS , U ) ∈ G 1 (where IDSi is selleri ’s identity) and V = dSi + rH G 1 . Finally, output the pair: σ = 〈 U , V 〉 ∈ G 1 × G 1 .
Therefore, the signed message can be generated as msgselleri DC = ( Ci IDSi 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 ( IDSi , Ci TS , U ), and then accept it only if ê( P , V ) = ê( Ppub , H 1 ( IDSi ))ê( U , H ). Then DC computes total tag as Csel = C 1 C 2 ∙ ⋯ ∙ CI , where
PPT Slide
Lager Image
Trapdoor aggregating
The trapdoor aggregating process is shown in Fig. 3 .
PPT Slide
Lager Image
Trapdoor aggregating
(1) Trapdoor creation and delivery
When buyerj wants to bid the energy, he first generates filtering keywords ( m j,1 , m j,2 ,⋯ , mj,l ) (0 < mj,k < d ,1 ≤ k l ) and randomly chooses rj
PPT Slide
Lager Image
, then computes his trapdoor
PPT Slide
Lager Image
where Mj = a 1 m j,1 + a 2 m j,2 + ⋯ + almj,l . And then buyerj calculates the total trapdoor as Cbuy = Cj b1+b2+⋯+bI , where
PPT Slide
Lager Image
After that, buyerj generates a matching rule sequence R = ( R 1 , R 2 , … , Rl ). If buyerj defines the range of auction keyword as v 1 mi,k v 2 ( v 1 , v 2 ∈ ℤ n ), then Rk should be a pair: g v1mj,k , g v2mj,k . Based on the filtering rules, buyerj can define a keyword weight sequence ( W 1 , W 2 , … , Wl ) for all auction keywords mi,k ( k = 1,2,⋯, l ), the keyword weight Wk represents the keyword importance defined by buyerj . The fine-grained 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 super-increasing 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 ,⋯, gWl ). Then buyerj signs ( Cbuy R W TS ) using the identity-based signature algorithm [11] . The alogrithm is as follow: pick r
PPT Slide
Lager Image
, compute U = rP G 1 , H = H 2 ( IDBi , Cbuy R W TS , U ) (where IDBj is buyerj ’s identity) and V = dBj + rH G 1 . Finally, output the pair: σ = 〈 U , V 〉∈ G 1 × G 1 . Then, buyerj sends the signed message msgbuyerj DC =( Cbuy R W IDBj TS σ ) to DC , and DC accepts it after verifying asê( P , V )=ê( Ppub , H 1 ( IDBi ))ê( U , H ), where H = H 2 ( IDBi , Cbuy R W TS , U ).
(2) Homomorphic computing for comparison
When DC wants to compare sellers ’ tags with buyerj ’s trapdoor. It can compute C = Csel Cbuy . Then, DC sends the signed message msgDC→FC =( C R IDDC IDBj TS σ ) to FC , where σ is the signature of ( C R IDDC IDBj TS ) using the identity-based signature algorithm [11] .
Filtering
The filtering process is shown in Fig. 4 .
PPT Slide
Lager Image
Filtering
(1) Decrypting the result of comparison
After receiving the message ( C R IDDC IDBj TS σ ), check the signature σ using the identity-based signature algorithm [11] , if it is valid, FC decrypts C , where C is formed by
PPT Slide
Lager Image
where Mi,j = Mi Mj = a 1 ( m i,1 m j,1 ) + a 2 ( m i,2 m j,2 ) + ⋯ + al ( mi,l mj,l ) and Mtotal =
PPT Slide
Lager Image
bi Mi,j . FC uses sk to recover Mtotal as Section 3.3. After that, FC gets ( M 1,j , M 2,j ,⋯, MI,j ) by running Algorithm 1 with input
PPT Slide
Lager Image
and SUM = Mtotal .
PPT Slide
Lager Image
As shown in Algorithm 1 , we define sumi = b 1 M 1,j + b 2 M 2,j + ⋯ + biMi,j ( i = 1,2,⋯, I ). We compute sum i−1 = sumi mod xi , hence we have 0 ≤ sum i−1 xi . Since we have defined
PPT Slide
Lager Image
bj D < bi /2, we have − xi /2 ≤ sum i−1 xi /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 xi /2, this is the right result; else if xi /2 < sum i−1 < xi , we must correct it as sum i−1 = sum i−1 xi , the true result is − xi /2 < sum i−1 < 0. That is why we choose bi /2 in
PPT Slide
Lager Image
bj D < bi /2 and ai /2 in
PPT Slide
Lager Image
aj d < ai /2, it can split the aggregation including negative numbers.
After getting ( M 1,j , M 2,j ,⋯, MI,j ), FC can use Algorithm 1 with input
PPT Slide
Lager Image
and SUM = Mi,j ( i = 1,2,⋯, I ) to gain all differences of the multidimensional keywords DIFi,j = ( dif i,j,1 , dif i,j,2 ,⋯, difi,j,l ) between selleri and buyerj .
(2) Choosing winners
With the keyword difference DIFi,j = ( dif i,j,1 , dif i,j,2 ,⋯, difi,j,l ) and filtering rules ( R 1 , R 2 , … , Rl ), we can achieve range query. If each difi,j,k ( k = 1,2,⋯, l ) satisfies the filtering rule Rk (i.e., v 1 mj,k difi,j,k v 2 mj,k ), k will be stored in an array Ki [].
After getting the array Ki [] ( i = 1,2,⋯, I ), FC further sends it to DC . Then, randomly chooses r′
PPT Slide
Lager Image
, DC generates the weight of selleri as follows:
PPT Slide
Lager Image
All weighti ( i = 1,2,⋯, I ) will be sent to FC and decrypted according to Paillier cryptosystem [9] as shown in equation (8).
PPT Slide
Lager Image
According to the weight of each selleri , i.e., ∑ kKi[] Wk , the ranked result array winner′ [] = ( ID′ 1 , ID′ 2 , ID′ 3 , ⋯) can be obtained. Finally, FC sends the message ( winner′ []║ IDFC TS ), i.e., the ranked result, to DC through a secure channel.
Theorem 1 . For the keyword weight sequence W ′=( W k1 , W k2 , … , Wkl ) which is ordered by the ascending weights, where Wkl = cl . 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
PPT Slide
Lager Image
cj < ci , we have
PPT Slide
Lager Image
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 ( mi,1 , mi,2 ,⋯, mi,l ) ( mi,j ∈ ℤ n ) are aggregated to ci as
PPT Slide
Lager Image
That means that Ci is a ciphertext of Paillier cryptosystem, similarly, Cj , Cbuy and Csel 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 Cbuy and Csel , 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., Mi,j = Mi Mj , FC cannot recover the corresponding Mi and Mj . In addition, with the super-increasing sequence
PPT Slide
Lager Image
= ( b 1 , b 2 ,⋯, bI ), 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 Ci ( i = 1 , 2 , ⋯) and total trapdoor Cbuy 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 weighti =∏ kKi[] gWk are sent to the filter center, where Ki [] is an array storing the keywords which satisfy the corresponding matching rules. The filter center can only get the total weight of selleri , i.e., ∑ kKi[] Wk , 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
PPT Slide
Lager Image
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 multi-keyword search in smart grid auction market, PaRQ further achieves range query, but only EMRQ scheme can achieve multi-keyword, range query, ranked search and personalized search simultaneously.
Comparison of Functionalities
PPT Slide
Lager Image
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 Cp , Cm , C en2 and Cen , respectively. Compared with above operations, other operations in EMRQ and SESA are negligible [13] .
In EMRQ, it costs 2 Cm to sign a message, and 2 Cp to verify if we adopt precomputed technology [11] . For selleri , he needs ( l + 1) C en2 + Cen to create tags Ci and 2 Cm to sign it. Therefore, all sellers’ cost is (2 Cm +( l + 1) C en2 + Cen ) I . For buyerj , he costs lC en2 + Cen 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 Cm to sign it. Hence, all buyers ’ cost is (2 Cm + (4 l + 1) C en2 + Cen ) J (assume J is the number of buyers ). For DC , it needs 2( I + J ) Cp to verify all messages of sellers and buyers . For every buyerj , DC needs to sign a message msgDC→FC = ( C R W IDDC IDBj TS ) to FC , the signature costs 2 JCm . Therefore, DC ’s cost is 2 JCm + (2 I + 2 J ) Cp . For FC , it needs total 2 JCp to verify the messages from DC , then decrypts C , R and weighti with JC en2 , 2 lJC en2 and JC en2 . Hence, FC ’s cost is (2 l + 2) JC en2 + 2 JCp . Therefore, in our proposed EMRQ, the total computation overhead is (4 J + 2 I ) Cm + (( l + 1) I + (6 l + 3) J ) C en2 + ( J + I ) Cen + (4 J + 2 I ) Cp .
In the SESA scheme, we assume it adopts the same signature technology and two cyclic addition groups G 1 , G 2 . EBj makes a bid to EDRi which costs 3 Cm + 2 Cp , and the corresponding signature needs 2 Cm , thus all energy buyers ’ cost is 5 IJCm + 2 IJCp where each EB expects to make a bid to each EDR because EB cannot know which bid will be accepted; EDRi needs Cm to create a trapdoor and 2 Cm to sign it, therefore EDRi ’s cost is 3 ICm ; AS needs 2 Cp to verify a message which will be IJ + I times, and Cp to compare each tag which will be IJ times, hence AS ’s cost is (3 IJ + 2 I ) Cp ; RS needs Cm + Cp 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 ( Cm + Cp ). Therefore, in SESA the total computation overhead is (5 IJ + 3 I + IN ) Cm + (2 IJ + 2 I + IN ) Cp .
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.
PPT Slide
Lager Image
Computation overhead of EMRQ
PPT Slide
Lager Image
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 msgselleri→DC = ( Ci IDSi TS σ ) where the signature σ includes two elements in G 1 , therefore if we choose 1024-bit
PPT Slide
Lager Image
and 161-bit 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 msgbuyerj→DC =( Cbuy R W IDBj TS ), each Rk ( k = 1,2,⋯, l ) includes two ciphertexts of Paillier Cryptosystem, and Wk 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 msgDC→FC =( C R IDDC IDBj TS ) and ( weighti IDDC IDBj 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 Cj 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.
PPT Slide
Lager Image
Communication overhead of EMRQ
PPT Slide
Lager Image
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 supply-side 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 privacy-preserving 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 increasing-sequence 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 multi-keyword top-k 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 multi-keyword search and it can achieve efficient query. In our scheme, with a super increasing-sequence, we achieve the efficient multi-keyword range query of the encrypted auction.
8. CONCLUSION
In this paper, we have proposed an efficient multi-keyword 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 Peer-to-Peer 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 Peer-to-Peer 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 Peer-to-Peer 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 ITU-T Q.5/17, countering spam by technical means and has published 3 ITU-T 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.
References
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 privacy-preserving 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 store-carry-and-deliver 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. “Public-key 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. “Identity-based 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 single-phase high-frequency 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/CJFDTOTAL-ZGDC200312004.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 supply-side 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 non-cooperative 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 self-healing 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 “Energy-theft 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 multi-authority 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 “Privacy-preserving multi-keyword 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 multi-keyword top-k 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 privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking,” IEEE Transactions on Parallel and Distributed Systems