Enabling Fine-grained
Multi-keyword Search Supporting Classified Sub-dictionaries over Encrypted
Cloud DataAbstract—Using cloud computing, individuals can store their data on
remote servers and allow data access to public users through thecloud servers.
As the outsourced data are likely to contain sensitive privacy information,
they are typically encrypted before uploaded tothe cloud. This, however,
significantly limits the usability of outsourced data due to the difficulty of
searching over the encrypted data. Inthis paper, we address this issue by
developing the fine-grained multi-keyword search schemes over encrypted cloud
data. Our originalcontributions are three-fold. First, we introduce the
relevance scores and preference factors upon keywords which enable the precisekeyword
search and personalized user experience. Second, we develop a practical and
very efficient multi-keyword search scheme.The proposed scheme can support
complicated logic search the mixed “AND”, “OR” and “NO” operations of keywords.
Third, we furtheremploy the classified sub-dictionaries technique to achieve
better efficiency on index building, trapdoor generating and query. Lastly,we
analyze the security of the proposed schemes in terms of confidentiality of
documents, privacy protection of index and trapdoor,and unlinkability of
trapdoor. Through extensive experiments using the real-world dataset, we
validate the performance of the proposedschemes. Both the security analysis and
experimental results demonstrate that the proposed schemes can achieve the same
securitylevel comparing to the existing ones and better performance in terms of
functionality, query complexity and efficiency.Index Terms—Searchable
encryption, Multi-keyword, Fine-grained, Cloud computing.F1 INTRODUCTIONTHE
cloud computing treats computing as a
utility andleases out the computing and storage capacities to thepublic
individuals [1], [2], [3]. In such a framework, theindividual can remotely
store her data on the cloud server,namely data outsourcing, and then make the
cloud data openfor public access through the cloud server. This represents amore
scalable, low-cost and stable way for public data accessbecause of the
scalability and high efficiency of cloud servers,and therefore is favorable to
small enterprises._ H. Li and Y. Yang are with the
School of Computer Science andEngineering, University of Electronic Science and
Technology of China,Chengdu, Sichuan, China (e-mail: hongweili@uestc.edu.cn;
yangyi.buku@gmail.com)._ H. Li is with State Key Laboratory
of Information Security (Institute ofInformation Engineering, Chinese Academy
of Sciences, Beijing 100093)(e-mail: hongweili@uestc.edu.cn)._ T.
Luan is with the School of Information Technology, Deakin University,Melbourne,
Australia(e-mail: tom.luan@deakin.edu.au)._ X. Liang is with the Department of
Computer Science, Dartmouth College,Hanover, USA(e-mail:
Xiaohui.Liang@dartmouth.edu)._ L. Zhou is with the National Key
Laboratory of Science and Technologyon Communication, University of Electronic
Science and Technology ofChina, China(e-mail: lzhou@uestc.edu.cn)._ X.
Shen is with the Department of Electrical and Computer Engineering,University
of Waterloo,Waterloo, Ontario, Canada(e-mail:sshen@uwaterloo.ca).Note that the outsourced data may
contain sensitive privacyinformation. It is often necessary to encrypt the
private databefore transmitting the data to the cloud servers [4], [5].The data
encryption, however, would significantly lower theusability of data due to the
difficulty of searching over theencrypted data [6]. Simply encrypting the data
may stillcause other security concerns. For instance, Google Searchuses SSL
(Secure Sockets Layer) to encrypt the connectionbetween search user and Google
server when private data,such as documents and emails, appear in the search
results [7].However, if the search user clicks into another website fromthe
search results page, that website may be able to identifythe search terms that
the user has used.On addressing above issues, the searchable encryption (e.g.,[8],
[9], [10]) has been recently developed as a fundamentalapproach to enable
searching over encrypted cloud data,which proceeds the following operations.
Firstly, the dataowner needs to generate several keywords according to theoutsourced
data. These keywords are then encrypted and storedat the cloud server. When a
search user needs to access theoutsourced data, it can select some relevant
keywords andsend the ciphertext of the selected keywords to the cloudserver.
The cloud server then uses the ciphertext to matchthe outsourced encrypted
keywords, and lastly returns thematching results to the search user. To achieve
the similarsearch efficiency and precision over encrypted data as that ofplaintext
keyword search, an extensive body of research hasbeen developed in literature.
Wang et al. [11] propose a rankedkeyword search scheme which considers the
relevance scores1545-5971 (c) 2015 IEEE. Personal use is
permitted, but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing2of
keywords. Unfortunately, due to using order-preservingencryption (OPE) [12] to
achieve the ranking property, theproposed scheme cannot achieve unlinkability
of trapdoor.Later, Sun et al. [13] propose a multi-keyword text searchscheme
which considers the relevance scores of keywords andutilizes a multidimensional
tree technique to achieve efficientsearch query. Yu et al. [14] propose a
multi-keyword top-kretrieval scheme which uses fully homomorphic encryption toencrypt
the index/trapdoor and guarantees high security. Caoet al. [6] propose a
multi-keyword ranked search (MRSE),which applies coordinate machine as the
keyword matchingrule, i.e., return data with the most matching keywords.Although
many search functionalities have been developedin previous literature towards
precise and efficient searchableencryption, it is still difficult for
searchable encryption toachieve the same user experience as that of the plaintextsearch,
like Google search. This mainly attributes to followingtwo issues. Firstly,
query with user preferences is very popularin the plaintext search [15], [16].
It enables personalized searchand can more accurately represent user’s
requirements, but hasnot been thoroughly studied and supported in the encrypteddata
domain. Secondly, to further improve the user’s experienceon searching, an
important and fundamental function isto enable the multi-keyword search with
the comprehensivelogic operations, i.e., the “AND”, “OR” and “NO” operationsof
keywords. This is fundamental for search users to prunethe searching space and
quickly identify the desired data.Cao et al. [6] propose the coordinate
matching search scheme(MRSE) which can be regarded as a searchable encryptionscheme
with “OR” operation. Zhang et al. [17] propose aconjunctive keyword search
scheme which can be regarded asa searchable encryption scheme with “AND”
operation withthe returned documents matching all keywords. However, mostexisting
proposals can only enable search with single logicoperation, rather than the
mixture of multiple logic operationson keywords, which motivates our work.In
this work, we address above two issues by developingtwo Fine-grained
Multi-keyword Search (FMS) schemes overencrypted cloud data. Our original
contributions can be summarizedin three aspects as follows:• We introduce the
relevance scores and the preference factorsof keywords for searchable
encryption. The relevancescores of keywords can enable more precise returnedresults,
and the preference factors of keywords representthe importance of keywords in
the search keyword setspecified by search users and correspondingly enablespersonalized
search to cater to specific user preferences. Itthus further improves the
search functionalities and userexperience.• We realize the “AND”, “OR” and “NO”
operations in themulti-keyword search for searchable encryption. Comparedwith
schemes in [6], [13] and [14], the proposedscheme can achieve more
comprehensive functionalityand lower query complexity.• We employ the
classified sub-dictionaries technique toenhance the efficiency of the above two
schemes. Extensiveexperiments demonstrate that the enhanced schemescan achieve
better efficiency in terms of index building,trapdoor generating and query in
the comparison withschemes in [6], [13] and [14].The remainder of this paper is
organized as follows. InSection 2, we outline the system model, threat model,
securityrequirements and design goals. In Section 3, we describethe
preliminaries of the proposed schemes. We present thedeveloped schemes and
enhanced schemes in details in Section4 and Section 5, respectively. Then we
carry out the securityanalysis and performance evaluation in Section 6 and
Section7, respectively. Section 8 provides a review of the relatedworks and
Section 9 concludes the paper.2
SYSTEM MODEL, THREAT MODELAND
SECURITY REQUIREMENTS2.1 System ModelAs shown in Fig. 1, we consider a system
consists of threeentities.• Data owner: The data owner outsources her data
tothe cloud for convenient and reliable data access to thecorresponding search
users. To protect the data privacy,the data owner encrypts the original data
throughsymmetric encryption. To improve the search efficiency,the data owner
generates some keywords for eachoutsourced document. The corresponding index is
thencreated according to the keywords and a secret key. Afterthat, the data
owner sends the encrypted documents andthe corresponding indexes to the cloud,
and sends thesymmetric key and secret key to search users.• Cloud
server: The cloud server
is an intermediate entitywhich stores the encrypted documents and correspondingindexes
that are received from the data owner, andprovides data access and search
services to search users.When a search user sends a keyword trapdoor to the
cloudserver, it would return a collection of matching documentsbased on certain
operations.• Search
user: A search user queries the outsourced
documentsfrom the cloud server with following three steps.First, the search
user receives both the secret key andsymmetric key from the data owner. Second,
accordingto the search keywords, the search user uses the secretkey to generate
trapdoor and sends it to the cloud server.Last, she receives the matching
document collection fromthe cloud server and decrypts them with the symmetrickey.2.2 Threat Model and Security
RequirementsIn our
threat model, the cloud server is assumed to be “honestbut-curious”, which is
the same as most related works onsecure cloud data search [13], [14], [6].
Specifically, the cloudserver honestly follows the designated protocol
specification.However, the cloud server could be “curious” to infer andanalyze
data (including index) in its storage and messageflows received during the
protocol so as to learn additionalinformation. we consider two threat models
depending on theinformation available to the cloud server, which are also usedin
[13], [6].1545-5971 (c) 2015 IEEE. Personal use is permitted,
but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing3Fig. 1.
System model• Known
Ciphertext Model: The
cloud server can onlyknow encrypted document collection C and index
collectionI,
which are both outsourced from the data owner.• Known Background Model: The cloud server can possessmore
knowledge than what can be accessed inthe known ciphertext model, such as the
correlationrelationship of trapdoors and the related statistical ofother
information, i.e., the cloud server can possess thestatistical information from
a known comparable datasetwhich bears the similar nature to the targeting
dataset.Similar to [13], [6], we assume search users are trustedentities, and
they share the same symmetric key and secretkey. Search users have pre-existing
mutual trust with thedata owner. For ease of illustration, we do not considerthe
secure distribution of the symmetric key and the secretkey between the data
owner and search users; it can beachieved through regular authentication and
secure channelestablishment protocols based on the prior security contextshared
between search users and the data owner [18]. Inaddition, to make our
presentations more focused, we donot consider following issues, including the
access controlproblem on managing decryption capabilities given to usersand the
data collection’s updating problem on inserting newdocuments, updating existing
documents, and deleting existingdocuments, are separated issues. The interested
readers onabove issues may refer to [6], [5], [10], [19].Based on the above
threat model, we define the securityrequirements as follows:• Confidentiality
of documents: The
outsourced documentsprovided by the data owner are stored in the cloud server.If
they match the search keywords, they are sent to thesearch user. Due to the
privacy of documents, they shouldnot be identifiable except by the data owner
and theauthorized search users.• Privacy protection of index and
trapdoor: As discussed inSection
2.1, the index and the trapdoor are created basedon the documents’ keywords and
the search keywords,respectively. If the cloud server identifies the content ofindex
or trapdoor, and further deduces any associationbetween keywords and encrypted
documents, it may learnthe major subject of a document, even the content of ashort
document [20]. Therefore, the content of index andtrapdoor cannot be identified
by the cloud server.• Unlinkability of trapdoor: The documents stored in thecloud
server may be searched many times. The cloudserver should not be able to learn
any keyword informationaccording to the trapdoors, e.g., to determine twotrapdoors
which are originated from the same keywords.Otherwise, the cloud server can
deduce relationship oftrapdoors, and threaten to the privacy of keywords. Hencethe
trapdoor generation function should be randomized,rather than deterministic.
Even in case that two searchkeyword sets are the same, the trapdoors should bedifferent.3 PRELIMINARIESIn this section, we define the
notation and review the securekNN computation and relevance score, which will
serve as thebasis of the proposed schemes.3.1
Notation• F—the document collection to be
outsourced, denoted asa set of N documents
F = (F1; F2; · · · ; FN).• C—the encrypted document collection
according to F,denoted as a set of N documents C = (C1;C2; · · · ;CN).• FID—the identity collection of encrypted
documents C,denoted
as FID = (FID1;
FID2; · · · ; FIDN).• W—the keyword
dictionary, including m keywords, denotedas
W = (w1;w2; · · · ;wm).• I—the index stored in the cloud server,
which is builtfrom the keywords of each document, denoted as I =(I1; I2; · · · ; IN).• fW—the query keyword
set generated by a search user,which is a subset of W.• TfW—the trapdoor for keyword set fW.• ]FID—the identity collection of documents
returned tothe search user.• FMS(CS)—the abbreviation of FMS and
FMSCS.3.2 Secure kNN
ComputationWe
adopt the work of Wong et al. [21] as our foundation.Wong et al. propose a
secure k-nearest neighbor (kNN) schemewhich
can confidentially encrypt two vectors and computeEuclidean distance of them.
Firstly, the secret key (S;M1;M2)should
be generated. The binary vector S is
a splitting indicatorto split plaintext vector into two random vectors, whichcan
confuse the value of plaintext vector. And M1 and M2 areused to encrypt the split vectors.
The correctness and securityof secure kNN computation scheme can be referred to
[21].3.3 Relevance ScoreThe relevance score between a keyword
and a documentrepresents the frequency that the keyword appears in thedocument.
It can be used in searchable encryption for returningranked results. A
prevalent metric for evaluating the relevancescore is TF × IDF, where TF (term
frequency) representsthe frequency of a given keyword in a document and IDF1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing4(inverse
document frequency) represents the importance ofkeyword within the whole
document collection. Without lossof generality, we select a widely used
expression in [22] toevaluate the relevance score asScore(fW; Fj) =Σw∈fW1|Fj |· (1 + lnfj;w) · ln(1 +Nfw) (1)where fj;w denotes the TF of keyword w in document Fj ;fw denotes
the number of documents contain keyword w;
Ndenotes the number of documents in the
collection; and |Fj |denotes the length
of Fj , obtained by counting the number ofindexed
keywords.4 PROPOSED SCHEMESIn this section, we firstly propose a
variant of the secure kNNcomputation scheme, which serves as the basic
framework ofour schemes. Furthermore, we describe two variants of ourbasic
framework and the corresponding functionalities of themin detail.4.1 Basic FrameworkThe secure kNN computation scheme uses
Euclidean distanceto select k nearest database records. In this section, we presenta
variant of the secure kNN computation scheme to achievethe searchable
encryption property.4.1.1
InitializationThe
data owner randomly generates the secret key K =(S;M1;M2),
where S is a (m+1)-dimensional binary
vector,M1 and M2 are two (m + 1) × (m + 1) invertible
matrices,respectively, and m is the number of
keywords in W. Thenthe data owner sends (K;
sk) to
search users through a securechannel, where sk is
the symmetric key used to encryptdocuments outsourced to the cloud server.4.1.2 Index buildingThe data owner firstly utilizes
symmetric encryption algorithm(e.g., AES) to encrypt the document collection(F1; F2; · · · ; FN) with
the symmetric key sk [23],
the encrypteddocument collection are denoted as Cj(j = 1; 2; · · · ;N).Then
the data owner generates an m-dimensional binaryvector
P according to Cj(j = 1; 2; · · · ;N),
where eachbit P[i] indicates whether the encrypted
document containsthe keyword wi,
i.e., P[i] = 1 indicates yes and P[i] = 0indicates no. Then
she extends P to a (m + 1)-dimensionalvector P′, where P′[m + 1] = 1. The data owner usesvector S to split P′ into two (m + 1)-dimensional
vectors(pa; pb), where the vector S functions as a splitting indicator.Namely,
if S[i] = 0(i = 1; 2; · · · ;m + 1), pa[i] and pb[i]are both set as P′[i]; if S[i] = 1(i = 1; 2; · · · ;m + 1),the value of P′[i] will be randomly split into pa[i] and pb[i](P′[i] = pa[i]+pb[i]). Then, the index of encrypted
documentCj can be calculated as Ij = (paM1; pbM2).
Finally, the dataowner sends Cj ||FIDj ||Ij (j = 1; 2; · · · ;N) to
the cloudserver.4.1.3
Trapdoor generatingThe
search user firstly generates the keyword set fW forsearching. Then, she creates a m-dimensional binary vector Qaccording to fW, where Q[i] indicates whether
the i-th keywordof dictionary wi is in fW, i.e., Q[i] = 1 indicates yes andQ[i] = 0 indicates no.
Further, the search user extends Q toa
(m + 1)-dimensional vector Q′, where Q′[m + 1] = −s(the value of −s will be defined in
the following schemesin detail). Next, the search user chooses a random numberr > 0 to generate Q′′ = r · Q′. Then she splits Q′′ into two(m + 1) vectors (qa; qb): if S[i] = 0(i = 1; 2; · · · ;m + 1),the value of Q′′[i] will be randomly split into qa[i] and qb[i];if S[i] = 1(i = 1; 2; · · · ;m + 1), qa[i] and qb[i] are bothset as Q′′[i]. Thus, the search trapdoor TfW can
be generatedas (M−11 qa;M−12 qb). Then the search user sends TfW to
thecloud server.4.1.4
QueryWith the index Ij(j = 1; 2; · · · ;N) and
trapdoor TfW,
thecloud server calculates the query result asRj = Ij · TfW = (paM1; pbM2) · (M−11 qa;M−12 qb)= pa · qa + pb · qb = P′ · Q′′= rP′ · Q′= r · (P · Q − s)(2)If
Rj > 0, the corresponding document identity FIDj willbe returned.Discussions: The Basic
Framework has defined the
fundamentalsystem structure of the developed schemes. Based onthe secure kNN
computation scheme [21], the complementaryrandom parameter r further enhances the security.
Differentvalues for parameter s and
vectors P and Q can
lead to newvariants of the Basic
Framework. This will be
elaborated inthe follows.4.2 FMS
IIn the Basic
Framework, P is a m-dimensional
binary vector,and each bit P[i] indicates whether the encrypted
documentcontains the keyword wi.
In the FMS I, the data ownerfirst calculates the relevance score between the
keyword wiand document Fj . The relevance score can be
calculated asfollows:Score(wi; Fj) =1|Fj |· (1 + lnfj;wi ) · ln(1 +Nfwi) (3)where
fj;wi denotes the TF of
keyword wi in document Fj ;fwi denotes the number of documents
contain keyword wi; Ndenotes the number of documents in the
collection; and |Fj |denotes the length
of Fj , obtained by counting the number ofindexed
keywords.Then the data owner replaces the value of P[i] with thecorresponding
relevance score. On the other hand, we alsoconsider the preference factors of
keywords. The preferencefactors of keywords indicate the importance of keywords
inthe search keyword set personalized defined by the searchuser. For a search
user, he may pay more attention to thepreference factors of keywords defined by
himself than therelevance scores of the keywords. Thus, our goal is that1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing5if a
document has a keyword with larger preference factorthan other documents, it
should have a higher priority inthe returned ]FID; and
for two documents, if their largestpreference factor keywords are the same, the
document withhigher relevance score of the keyword is the better matchingresult.As
shown in Fig. 2, we replace the values of P[i] andQ[i] by the relevance
score and the preference factor of akeyword, respectively (thus P and Q are
no longer binary).The search user can dynamically adjust the preference factorsto
achieve a more flexible search. For convenience, the scoreis rounded up, i.e., Score(wi; Fj) = ⌈10 ∗ Score(wi; Fj)⌉,and we assume the relevance score is
not more than D,i.e., Score(wi; Fj) <
D. For the search keyword set fW =(wn1 ;wn2 ; · · · ;wnl)(1 ≤ n1 < n2 < · · · < nl ≤ m) whichis ordered by
ascending importance, the search user randomlychooses a Σ super-increasing sequence (d1 >
0; d2; · · · ; dl) (i.e.,
j−1i=1 di ·D < dj(j = 2; 3; · · · ; l)), where di is
the preferencefactor of keyword wni . Then the search result would be:Rj = r · (P · Q − s) = r · (Σli=1Score(wni ; Fj) · di − s) (4)Theorem 1: (Correctness) For the search keyword
set fW =(wn1 ;wn2 ; · · · ;wnl)(1 ≤ n1 < n2 < · · · < nl ≤ m) whichis ordered by
ascending preference factors, if F1 contains alarger preference factor
keyword compared with F2,
then F1has higher priority in the returned ]FID.Proof: For the search keyword set fW =(wn1 ;wn2 ; · · · ;wnl ), assume the keyword sets F1and F2 contain in fW are denoted as fW1 =(wni ; · · · ;wnx )(n1 ≤ ni < · · · < nx ≤ nl) andfW2 = (wnj ; · · · ;wny )(n1 ≤ nj < · · · < ny ≤ nl),respectively,
where fW1 and
fW2 are
both ordered byascending preference factors, and nx > ny. As stated above,Score(wnx Σ ; Fj) ≥ 1 since the score is rounded up, and j−1i=1 di · D < dj(j = 2; 3; · · · ; l). Therefore, there will beR2 = r · (Σwnj∈gW2Score(wnj ; F2) · dj − s)<
r · (Σyj=1Score(wnj ; F2) · dj − s)<
r · (Σyj=1D · dj − s) <
r · (dx − s)< r · (Score(wnx ; F1) · dx − s)<
r · (Σwni∈gW1Score(wni ; F1) · di − s)<
R1(5)Therefore,
F1 has higher priority in the returned ]FID.Theorem 2: (Correctness) For the search keyword
set fW =(wn1 ;wn2 ; · · · ;wnl)(1 ≤ n1 < n2 < · · · < nl ≤ m)which is ordered by ascending
preference factors, if the largestpreference factor keyword F1 contains is the same as thatF2 contains, and F1 have the higher relevance score of thekeyword,
then F1 have higher priority in the returned ]FID.Proof: For the search keyword set fW =(wn1 ;wn2 ; · · · ;wnl ), assume the keyword sets F1 andF2 contain are denoted as fW1 = (wni ; · · · ;wnx )(n1 ≤ni < · · · < nx ≤ nl) and
fW2 = (wnj ; · · · ;wnx )(n1 ≤nj < · · · < nx ≤ nl),
respectively, where fW1 and fW2are both ordered by ascending
preference factors andScore(wnx ; F1) − Score(wnx ; F2) ≥ 1.
Thus, there will beR1 =r · (Σwni∈gW1Score(wni ; F1) · di − s)≥ r · (Score(wnx ; F1) · dx − s)(7)R2 =r · (Σwnj∈gW2Score(wnj ; F2) · dj − s) (8)=r · (Score(wnx ; F2) · dx+Σwnj∈gW2−wnxScore(wnj ; F2) · dj − s)<r
· (Score(wnx ; F2) · dx +Σwnj∈gW2−wnxD · dj − s)<r · (Score(wnx ; F2) · dx + dx − s)R1 − R2 > r · ((Score(wnx ; F1) − Score(wnx ; F2)) · dx − dx)>
r · (dx − dx)> 0 (9)Therefore, F1 have higher priority in the returned ]FID thanF2.Example.
We present a concrete example to help
understandTheorem 2. The example also illustrates the
workingprocess of FMS I. Specifically, we assume that thesearch keyword set is fW = (wn1 ;wn2 ; · · · ;wn5 ), and thelargest preference factor
keyword of sets F1 and
F2 is thesame, which is wn4 . In addition, we assume the keywordsets
F1 and F2 are fW1 = (wn2 ;wn3 ;wn4 ) and
fW2 =(wn1 ;wn3 ;wn4 ) respectively.
Furthermore, we assume thatthe relevance score is not more than D = 5, and specially,let
Score(wn4 ; F1) = 4 and
Score(wn4 ; F2) = 2,which
satisfy Score(wn4 ; F1) − Score(wn4 ; F2) = 2 ≥1. we randomly choose a
super-increasing sequence di ={1; 10; 60; 500; 3000}(i = 1; · · · ; 5),
for arbitrary r > 0, therewill beR1 =r · (Σwni∈gW1Score(wni ; F1) · di − s) (11)≥r · (Score(wn4 ; F1) · d4 − s)≥r · (4 · 500 − s)≥r · (2000 − s)1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing6Data owner Cloud server Search user111222 1 2 22keyword
dictionary: ( , , )keywords of document : ( , , )corresponding ( , ): ( , , )in
: ( , , , , , , , , )( 0 ,0 , , , , , , , ) ji
jw wF w wScore w F S Sw w w w wP S S SP Pa ba b= ×××= ××××××××× ××× ××× ×××= ××× ××× ×××
×××® ¢®WWW W1
2( , )( , ) j
a ab bp pI = p M p M´ jI_TW__ 2 1 211
22 1 2 2keyword dictionary: ( , , )search keyword set: (
, , )super-increasing sequence: ( , , )in : ( , , , , , , , , )( 0 , 0 , , , ,
, , l n
n nln n nw ww w wd d dw w w w wQ d d da ba b= ×××= ×××××××××
××× ××× ×××= ××× ××× ×××WWW W_ 11
21, )( , )( , ) a ab bQ Q r Q q qT M q M q – -×××® ¢® × ¢®=1 W( )( ( , ) )larger , better result. j ilj ni j iR r P Q sr
Score w F d sR== × × -= × _ × -Fig.
2. Structure of the FMS IR2 =r · (Σwnj∈gW2Score(wnj ; F2) · dj − s) (12)=r · (Score(wn4 ; F2) · d4+Σwnj∈gW2−wn4Score(wnj ; F2) · dj − s)<r
· (Score(wn4 ; F2) · dx +Σwnj∈gW2−wn4D · dj − s)<r
· (Score(wn4 ; F2) · d4 + d4 − s)<r · (2 · 500 + 500 − s)<r · (1500 − s)R1 − R2 >r · (2000 − s) − r · (1500 − s) (13)>r · (2000 − 1500)>500 · r > 04.3 FMS IIIn the FMS II, we do not change the
vector P in the BasicFramework, but replace the value of Q[i] by the weight ofsearch
keywords, as shown in Fig. 3. With the weight ofkeywords, we can also implement
some operations like “OR”,“AND” and “NO” in the Google Search to the searchableencryption.Assume
that the keyword sets corresponding to the“OR”, “AND” and “NO” operations are (w′1;w′2; · · · ;w′l1),(w′′1 ;w′′2 ; · · · ;w′′l2) and
(w′′′1 ;w′′′2 ; · · · ;w′′′l3), respectively.Denote “OR”, “AND” and “NO”
operations by ∨, ∧ and￢, respectively. Thus the matching rule
can be representedas (w′1∨ w′2∨ · · · ∨ w′l1) ∧ (w′′1∧ w′′2∧ · · · ∧ w′′l2) ∧(￢w′′′1∧ ￢w′′′2∧ · · · ∧ ￢w′′′l3).
For “OR” operation,the search user chooses a super-increasing sequence(a1 >
0; a2; · · · ; al1 )(Σj−1k=1 ak < aj(j = 2; · · · ; l1)) toachieve searching with keyword
weight. To enable searchableencryption with “AND” and “NO” operations, the
searchuser chooses a sequence (b1; b2; · · · ; bl2 ; c1; c2; · · · ; cl3 ),whereΣl1k=1 Σ ak < bh(h = 1; 2; · · · ; l2) and l1k=1 ak +Σl2h=1 bh < ci(i = 1; 2; · · · ; l3).Assume (w′1;w′2; · · · ;w′l1) are
ordered by ascendingimportance, then according to the search keyword set(w′1;w′2; · · · ;w′l1;w′′1 ;w′′2 ; · · · ;w′′l2;w′′′1 ;w′′′2 ; · · · ;w′′′l3),the
corresponding values in Q are set as(a1; a2; · · · ; al1 ; b1; b2; · · · ; bl2 ;−c1;−c2; · · · ;−cl3 ). Othervalues in Q are set as 0. Finally, the search user
setss =Σl2h=1 bh. In the Query phase, For a document Fj , ifthe corresponding Rj > 0, we claim that Fj can satisfy theabove matching rule.Theorem 3: (Correctness) Fj satisfies the above matchingrule with “OR”,
“AND” and “NO” if and only if the correspondingRj > 0.Proof: Firstly,
we proof the completeness. Since the weightof w′′′Σ i (i = 1; 2; · · · ; l3) in the vector Q is −ci and ci > l1k=1 ak +Σl2h=1 bh, if any corresponding value of w′′′i in Pof Fj is
1, we can infer P ·Q < 0 and Rj = r·(P ·Q−s) < 0.Therefore, if Rj > 0, any of w′′′i is not in the
keyword set ofFj , i.e., Fj satisfies the “NO” operation.
Moreover, if Rj > 0,then r · (P · Q − s) = r · (P · Q −Σl2h=1 bh) >
0.
Sincebh >Σl1k=1 ak(h = 1; 2; · · · ; l2), all corresponding values ofw′′h in P have to be 1 and at least one
corresponding value ofw′k(k = 1; 2; · · · ; l1) in P should
be 1. Thus, Fj satisfies the“AND”
and “OR” operations. Therefore, if Rj > 0, the vectorP satisfies the operations of “OR”, “AND”
and “NO”.Next, we show the soundness. If the vector P satisfiesthe operations of “OR”, “AND”
and “NO”, i.e., at least onecorresponding value of keyword w′k in P is
1 (assume thiskeyword is w′(1 ≤ ≤ l1)), all corresponding values ofkeywords
w′′h in P are 1 and no corresponding value ofkeyword
w′′′i in P is 1. Therefore, Rj = r · (P · Q − s) ≥r · (a + b1 + b2 + · · · + bl2− s) = r · a > 0.Example.We present a concrete example to help
understandTheorem 3. The example also illustrates the
working processof FMS II. Specifically, we assume that the keyword setscorresponding
to the “OR”, “AND” and “NO” operations are(w′1;w′2;w′3), (w′′1 ;w′′2 ;w′′3 ) and (w′′′1 ;w′′′2 ),
respectively. Thus,the matching rule can be represented as (w′1∨ w′2∨ w′3) ∧(w′′1∧ w′′2∧ w′′3 ) ∧ (￢w′′′1∧ ￢w′′′2 ).
we assume that the searchweights (a1; a2; a3), (b1; b2; b3) and
(c1; c2) for
“OR”, “AND”and “NO” are(1,5,8), (20,24,96) and (-500,-600), respectively.We
firstly prove Rj > 0 when Fj satisfies the
matchingrule. Specifically, assume that Fj satisfies
the matching rulew′2∧(w′′1∧w′′2∧w′′3 )∧(￢w′′′1∧￢w′′′2 ).
Thus the correspondingvalues of vector P are
(0; 1; 0), (1; 1; 1) and (0; 0), respectively.Thus,
the result of s =Σ3h=1 bh = 20 + 24 + 96 = 140,1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing7Data owner Cloud server Search user´ jI_T1 2 2 1 12 2 W1 2keyword dictionary: ( , , )keywords of
document : ( , , )in : ( , , , , , , , , )( 0, 0 , , 1 , , 1 , , 1 , )( , )( ,
) jj a ab bw wF w ww
w w w wPP P p pI p M p Ma b= ×××= ×××××× ××× ××× ×××= ××× ××× ××× ×××® ¢®=WWW W 12 121 2 1122 11 22 1 2keyword dictionary: ( , , )operation keyword set keyword weightOR ( ,
, , ) ( , , , )AND ( , , , ) ( , , , )NO ( , , , ll llw ww w w a a aw w w b b bw
w= ×××¢ ¢ ××× ¢ ×××¢ ¢ ××× ¢ ×××¢¢ ¢¢ ×××W_1 2 3 1 2 311 21) ( , , , )in : ( , , , , ,
, , , )( 0, 0 , , , , , , , )( , )( , ) l la ab bw c c cw w w w wQ a c bQ Q
r Q q qT M q M qa b ca b c- -¢¢ ×××××× ¢ ××× ¢¢ ××× ¢ ×××= ××× ××× – ×××
×××® ¢® × ¢®=WW( )( )0 satisfy
“OR”,”AND” and “NO”larger larger weight of
“OR” j j jR r P Q sr a c b sRRa b c= × × -= × ×××+ +×××- +×××+ + ×××-> __Fig. 3. Structure of the FMS IIfor arbitrary r > 0, the result of Rj will beRj = r · (P · Q − s)= r · (a2 + b1 + b2 + b3 − s)= r · (5 + 20 + 24 + 96 − 140)= 5r > 0(14)From the above example, we can easily see that Rj > 0when Fj satisfies
the matching rule. Next, we show thatRj < 0 when Fj does
not satisfy the matching rule. Especially,we assume that the ”AND” operation
does not satisfy thematching rule. Here, we set the first keyword does not
matchthe rule, therefore the search keyword set of ”AND” operationsare (0; 1; 1) instead of (1; 1; 1). Thus, the result
of Ri will beRj = r · (P · Q − s)= r · (a2 + b2 + b3 − s)= r · (5 + 24 + 96 − 140)= −15r
< 0(15)Obviously,
Rj < 0 when Fj does not satisfy the matchingrule.5 ENHANCED SCHEMEIn practice, apart from some common
keywords, other keywordsin dictionary are generally professional terms, and
thispart of the dictionary will rapidly increase when the dictionarybecomes
larger and more comprehensive. Simultaneously, thedata owner’s index will
become longer, although many dimensionsof keywords will never appear in her
documents.That will cause redundant computation and communicationoverhead.In
this section, we further propose a Fine-grained MultikeywordSearch scheme
supporting Classified Sub-dictionaries(FMSCS), which classifies the total
dictionary as a commonsub-dictionary and many professional sub-dictionaries.
Ourgoal is to significantly reduce the computation and communicationoverhead.
We have researched in a file set randomlychosen from the National Science
Foundation (NSF) ResearchAwards Abstracts 1990-2003 [24]. As shown in Fig. 4,
weclassify the total dictionary to many sub-dictionaries suchas common
sub-dictionary, computer science sub-dictionary,mathematics sub-dictionary and
physics sub-dictionary, etc.And the search process will only be some minor
changes inInitialization.Change
of Initialization: Compared
with theBasic Framework, in the enhanced scheme thedata owner
should firstly choose corresponding subdictionaries.Then her own dictionary can
be combined as{f1||Subdic1||f2||Subdic2|| · · · }, where Subdici representsall keywords contained in
corresponding sub-dictionary andfi is
filling factor with random length which will be 0 stringin the index, the
filling factor is used to confuse length ofthe data owner’s own dictionary and
relative positions of subdictionaries.Then, the data owner and search user will
use thisdictionary to generate the index and trapdoor, respectively.Note that
in an dictionary, two professional sub-dictionariescan even contain a same
keyword, but only the first appearedkeyword will be used to generate index and
trapdoor, anotherwill be set to 0 in the vector. And the secret key K willbe formed as (S;M1;M2; |f1|;DID1 ; |f2|;DID2 ; · · · ), whereDIDi represents the identity of
sub-dictionary and |fi| is thelength of fi. Other than these changes, the
remaining phases(i.e., Index
building, Trapdoor generating and Query)
aresame as the Basic
Framework.Dictionary Updating: In the searchable encryptionschemes
with dictionary, dictionary update is a challengeproblem because it may cause
to update massive indexesoutsourced to the cloud server. In general
dictionary-basedsearch schemes, e.g., [13] and [14], the update of dictionarywill
lead to re-generation of all indexes. In our FMSCSschemes, when it needs to
change the sub-dictionaries or addnew sub-dictionaries, only the data owners
who use the correspondingsub-dictionaries need to update their indexes, mostother
data owners do not need to do any update operations.Such dictionary update
operations are particularly lightweight.In addition, Li et al. [9] utilize the
dimension expansiontechnique to implement the efficient dictionary expansion.Such
method can also be included into our dictionary updatingprocess. And our scheme
can even be more efficient than [9]since although [9] does not need to
re-generate all indexes,but the corresponding extended operations on all
indexes arenecessary. In comparison, our schemes only need to extendthe indexes
of partial data owners.1545-5971 (c) 2015 IEEE. Personal use is
permitted, but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing8________ ______ _________ ___________ _________ _______ ___ _______ _ ____ _________ ______________ _ _______ ___ ________ __ _ __ ______ _______ ___ __
_______ _______________ ___ __
__________ __________ ______ ___ ___ ___ _________ _! _” __________1 2 3 4Dictionary: || common || ||
computer science f f || f ||mathematics
|| f 1 2 3
4Dictionary: f ¢|| physics || f ¢ || mathematics || f ¢|| common ||
f ¢ _________ __________ __Fig.
4. Classified sub-dictionaries6
SECURITY ANALYSISIn this
section, we analyze the main security properties ofthe proposed schemes. In
particular, our analysis focuseson how the proposed schemes can achieve
confidentialityof documents, privacy protection of index and trapdoor, andunlinkability
of trapdoor. Other security features are not thefocus of our concern.6.1 Confidentiality of DocumentsIn our schemes, the outsourced
documents are encrypted bythe traditional symmetric encryption algorithm (e.g.,
AES). Inaddition, the secret key sk is
generated by the data owner andsent to the search user through a secure
channel. Since theAES encryption algorithm is secure [23], any entity cannotrecover
the encrypted documents without the secret key sk.Therefore, the confidentiality of
encrypted documents can beachieved.6.2
Privacy Protection of Index and TrapdoorAs
shown in Section 4.1, both the index Ij = (paM1; pbM2)and
the trapdoor TfW = (M−11 qa;M−12 qb) are ciphertextsof
vectors (P;Q). The secret key is K = (S;M1;M2) inthe
FMS or (S;M1;M2; |f1|;DID1 ; |f2|;DID2 ; · · · ) in theFMSCS, where S functions
as a splitting indicator whichsplits P and
Q into (pa; pb) and (qa; qb), respectively, twoinvertible matrices
M1 and M2 are used to encrypt (pa; pb)and (qa; qb). The security of this encryption
algorithm has beenproved in the known ciphertext model [21]. Thus, the contentof
index and trapdoor cannot be identified. Therefore, privacyprotection of index
and trapdoor can be achieved.6.3
Unlinkability of TrapdoorTo
protect the security of search, the unlinkability of trapdoorshould be
achieved. Although the cloud server cannotdirectly recover the keywords, the
linkability of trapdoor maycause leakage of privacy, e.g., the same keyword set
may besearched many times, if the trapdoor generation function isdeterministic,
even though the cloud server cannot decryptthe trapdoors, it can deduce the
relationship of keywords. Weconsider whether the trapdoor TfW = (M−11 qa;M−12 qb) can belinked to the
keywords. We prove our schemes can achieve theunlinkability of trapdoor in a
strong threat model, i.e., knownbackground model [6].Known Background Model: In this model, the cloudserver can
possess the statistical information from a knowncomparable dataset which bears
the similar nature to thetargeting dataset.TABLE
1Structure of Q′Q′[1] _ _ _Q′[m] Q′[m + 1]FMS(CS) I _ _ _ 0 _ _ _ di _ _ _ 0 _ _ _ dj _ _ _ sFMS(CS) II _ _ _ ak _ _ _ bh _ _ _ 0 _ _ _ ci _ _ _ sAs shown in Table
1, in our FMS(CS) I, the trapdooris constituted by two parts. The values of all
dimensionsdi(i = 1; 2; · · · ; l) are the super-increasing sequence randomlychosen by the
search user (assume there are _ possiblesequences).
And the (m+ 1) dimension is −s defined by thesearch
user, where s is a positive
random number. Assumethe size of −s is _s bits,
there are 2_s possible values for−s. Further, to
generate Q′′ = r · Q′, Q′ is multiplied by apositive
random number r, there are 2_r possible values forr (if the search user chooses _r-bit r).
Finally, Q′′ is splitto (qa; qb) according the
splitting indicator S. Specifically, ifS[i] = 0(i = 1; 2; · · · ;m + 1), the value of Q′′[i] will berandomly split into qa[i] and qb[i], assume in S the numberof ‘0’ is _, and each dimension of qa and qb is
_q bits. Notethat _s, _r,
_ and _q are
independent of each other. Thenin our FMS(CS) I, we can compute the probability
that twotrapdoors are the same as follows:P1 =1_ · 2_s · 2_r · (2_q )_ =1_ · 2_s+_r+__q(16)Therefore, the larger _, _s,
_r, _ and
_q can achieve thestronger security,
e.g., if we choose 1024-bit r, then the1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing9probability
P1 <
1=21024. As a result, the
probability thattwo trapdoors are the same is negligible.And in the FMS(CS) II,
because −s = −Σl2h=1 bh,its value depends on the weight
sequence(a1; a2; · · · ; al1 ; b1; b2; · · · ; bl2 ; c1; c2; · · · ; cl3 ). Assumethe number of different
sequences is denoted as _, then wecan
compute:P2 =1_ · 2_r · (2_q )_ =1_ · 2_r+__q(17)Similarly, in
the FMS(CS) II and the FMS(CS) III, the probabilitythat two trapdoors are the
same is negligible. Therefore,in our schemes, the unlinkability of trapdoor can
be achieved.In summary, we present the comparison results of securitylevel in
Table 2, where I and II represent FMS(CS) I andFMS(CS) II, respectively. It can
be seen that all schemes canachieve confidentiality of documents and privacy
protectionof index and trapdoor, but the OPE schemes [11], [25] cannotachieve
the unlinkability of trapdoor very well because of thesimilarity relevance
mentioned in [14].TABLE 2Comparison
of Security Level[11],
[25] [6], [13], [14] I IIConfidentialityp p p pPrivacy protectionp p p pUnlinkabilityp p pDiscussions:
In MRSE [6], the values of P ·Q are equal tothe
number of matching keywords, which suffers scale analysisattack when the cloud
server is powerful and has knowledgeof some background information. To solve
this problem, itextends the index and inserts a random number “j whichfollows a normal distribution and
can confuse the values ofP ·Q. Thus, enhanced MRSE can resist scale
analysis attack.However, the introduction of “j causes
precision decrease ofthe returned results. There is a trade-off between
precisionand security in MRSE. In comparison, our schemes do notsuffer the
scale analysis attack. Because the values of P · Qin our schemes do not disclose any
information due to therandomly selected sequences mentioned in Section 4.2 andSection
4.3. Therefore, our proposal can achieve the securitywithout sacrificing
precision.7 PERFORMANCE EVALUATIONIn this section, we evaluate the
performance of the proposedschemes using simulations, and compare the
performance withthat of existing proposals in [6], [13], [14]. We apply a
realworlddataset from the National Science Foundation ResearchAwards Abstracts
1990-2003 [24], in which we random selectmultiple documents and conduct
real-world experiments on anIntel Core i5 3.2 GHz system.7.1 FunctionalityWe compare functionalities between
[6], [13], [14] and ourschemes in Table 3, where I and II represent FMS(CS) I
andFMS(CS) II, respectively.MRSE [6] can achieve multi-keyword search and
coordinatematching using secure kNN computation scheme. And [13]and [14] considers
the relevance scores of keywords. Comparedwith the other schemes, our FMS(CS) I
considers boththe relevance scores and the preference factors of keywords.Note
that if the search user sets all relevance scores andpreference factors of
keywords as the same, the FMS(CS) Idegrades to MRSE and the coordinate matching
can beachieved. And in the FMS(CS) II, if the search user sets allpreference
factors of “OR” operation keywords as the same,the FMS(CS) II can also achieve
the coordinate matchingof “OR” operation keywords. Particularly, the FMS(CS) IIachieves
some fine-grained operations of keyword search,i.e., “AND”, “OR” and “NO”
operations in Google Search,which are definitely practical and significantly
enhance thefunctionalities of encrypted keyword search.TABLE 3Comparison of Functionalities[6] [13] [14] I IIMulti-keyword searchp p p p pCoordinate
matchingp p p p pRelevance scorep p pPreference factorp pAND OR NO
operationsp7.2
Query ComplexityIn the
FMS(CS) II, we can implement “OR”, “AND” and“NO” operations by defining
appropriate weights of keywords,this scheme provides a more fine-grained search
than [6],[13] and [14]. If the keywords to perform “OR”, “AND” and“NO”
operations are (w′1;w′2; · · · ;w′l1), (w′′1 ;w′′2 ; · · · ;w′′l2)and
(w′′′1 ;w′′′2 ; · · · ;w′′′l3), respectively. Our FMS(CS) II cancomplete
the search with only one query, however, in [6],[13] and [14], they would
complete the search through thefollowing steps:• For the “OR”
operation of l1 keywords,
they need onlyone query Query(w′1;w′2; · · · ;w′l1) to
return a collectionof documents with the most matching keywords (i.e.,coordinate
matching), which can be denoted as X =Query(w′1;w′2; · · · ;w′l1).• For the “AND”
operation of l2 keywords,
[6], [13]and [14] cannot generate a query for multiple keywordsto achieve the “AND”
operation. Therefore, aftercosting l2 queries Query(w′′i )(i = 1; 2; · · · ; l2),they can do the “AND” operation, and
the correspondingdocument set can be denoted as Y =Query(w′′1 )∩Query(w′′2 )∩· · ·∩Query(w′′l2).• For the “NO” operation of l3 keywords, they need l3queries Query(w′′′i )(i = 1; 2; · · · ; l3), firstly. Then, thedocument set of
the “NO” operation can be denoted asZ = Query(w′′′1 )∩Query(w′′′2 )∩· · ·∩Query(w′′′l3).• Finally, the document collection
achieved “OR”, “AND”and “NO” operations can be represented as X∩Y∩Z.As shown in Fig. 5a, 5b and 5c, to
achieve these operations,the FMS(CS) II can outperform the existing proposals
withless queries generated.1545-5971 (c) 2015 IEEE. Personal
use is permitted, but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing102468102468100510152025Number Number of “NO” keywords of “AND” keywordsNumber of queries[6] & [13] & [14]FMS(CS)_II(a)24681024681005101520Number of “NO” keywords Number of “OR” keywordsNumber of queries[6] & [13] & [14]FMS(CS)_II(b)24681024681005101520Number of “OR” keywords Number of “AND” keywordsNumber of queries[6] & [13] & [14]FMS(CS)_II(c)Fig.
5. Time for building index. (a) Number of queriesfor the different number of “AND”
and “NO” keywordswith the same number of “OR” keywords, l1 = 5. (b)Number
of queries for the different number of “OR” and“NO” keywords with the same number
of “AND” keywords,l2 = 5. (c) Number of queries for the different
number of“AND” and “OR” keywords with the same number of “NO”keywords, l3 = 5.7.3 Efficiency7.3.1 Computation overheadIn order to easily demonstrate our
scheme computation overhead,we analysis our scheme from each phase.Index building. Note that the Index building phase of [6]is the same as our FMS II
scheme, without calculating therelevance score. And the Index building phase of the FMS Iis the same as [13],
containing the relevance score computing.Compared with the FMS I, the FMS II
does not need to calculatethe relevance score. And compared with the
computationcost of building index, the cost of calculating the relevancescore
is negligible, we do not distinguish them. Moreover,in our enhanced schemes
(FMSCS), we divide the totaldictionary into 1 common sub-dictionary and 20
professionalsub-dictionaries (assume each data owner averagely chooses 1common
sub-dictionary and 3 professional sub-dictionaries togenerate the index). As
shown in Fig. 6, we can see the time forbuilding index is dominated by both the
size of dictionary andthe number of documents. And compared with [6], [13],
[14]and our FMS schemes, the FMSCS schemes largely reducethe computation
overhead.Trapdoor
generating. In Trapdoor generating phase, [6]and [13] firstly creates a
vector according to the searchkeyword set fW, then encrypts the vector by the
secure kNNcomputation scheme. And [14] also generates a vector anduses
homomorphic encryption to encrypt each dimension. Incomparison, our FMS I and
FMS II schemes should firstly2000 4000 6000 8000 100000500100015002000Size
of dictionaryTime (s)[6] & [13] & FMS[14]FMSCS(a)2000 4000 6000 8000 100000100200300400500600Number
of documentsTime (s)[6] & [13] & FMS[14]FMSCS(b)Fig.
6. Time for building index. (a) For the different size ofdictionary with the
same number of documents, N=6000.(b) For the
different number of documents with the samesize of dictionary, |W| = 4000.2000 4000 6000 8000 10000020040060080010001200Size
of dictionaryTime (ms)[6] & [13] & FMS[14]FMSCS(a)10 20 30 40 50050100150200250300Number
of query keywordsTime (ms)[6] & [13] & FMS[14]FMSCS(b)Fig.
7. Time for generating trapdoor. (a) For the differentsize of dictionary with
the same number of query keywords,|fW|=20. (b) For the
different number of query keywordswith the same size of dictionary, |W| = 4000.generate
a super-increasing sequence and a weight sequence,respectively. But actually,
we can pre-select a correspondingsequence for each scheme, it can also achieve
search processand privacy. Because even if the vectors are the same formultiple
queries, the trapdoors will be not the same due tothe security of kNN
computation scheme. Therefore, the computationcost of [6], [13] and all FMS
schemes in Trapdoorgenerating
phase are the same. As shown in Fig. 7,
the timefor generating trapdoor is dominated by the size of dictionary,instead
of the number of query keywords. Hence, our FMSCSschemes are also very
efficient in Trapdoor
generating phase.Query. As [6], [13] and the FMS all adopt the secure kNNcomputation
scheme, the time for query is the same. Thecomputation overhead in Query phase, as shown in Fig. 8,is greatly
affected by the size of dictionary and the numberof documents, and almost has
no relation to the number ofquery keywords. Further we can see, our FMSCS
schemessignificantly reduce the computation cost in Query phase.As [14] needs to encrypt each
dimension of index/trapdoorusing full homomorphic encryption, its
index/trapdoor size isenormous. Note that, in Trapdoor generating and Queryphases, the computation overheads are
not affected by thenumber of query keywords. Thus our FMS and FMSCSschemes are
more efficient compared with some multiplekeywordsearch schemes [26], [27], as
their cost is linear withthe number of query keywords.1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing112000 4000 6000 8000 10000010203040506070Size
of dictionaryTime (s)[6] & [13] & FMS[14]FMSSCS(a)2000 4000 6000 8000 1000001020304050Number
of documentsTime (s)[6] & [13] & FMS[14]FMSCS(b)10 20 30 40 5005101520253035Number
of query keywordsTime (s)[6] & [13] & FMS[14]FMSCS(c)Fig.
8. Time for query. (a) For the different size ofdictionary with the same number
of documents and numberof search keywords, N = 6000; |fW| = 20. (b) Forthe different number of
documents with the same sizeof dictionary and number of search keywords, |W| =4000; |fW| = 20. (c) For the different number of searchkeyword
with the same size of dictionary and number ofdocuments, N = 6000; |W| = 4000.7.3.2 Storage overheadAs shown in Table 4, we provide a
comparison of storageoverhead among several schemes. Specifically, we evaluate
thestorage overhead from three parts: the data owner, the searchuser and the
cloud server.According to Table 4, in the FMS, the FMSCS as well asschemes of
[6] and [13], the storage overhead of the dataowner are the same. In these
schemes, the data owner preservesher secret key K = (S;M1;M2) and
symmetric key sklocally, where S is an (m+1)-dimensional
vector, M1 and M2are (m+1)×(m+1) invertible
matrices. All elements in S,M1and M2 are the float number. Since the size
of a float numberis 4 bytes, the size of K is
4· (m+1)+8· (m + 1)2 bytes.
Weassume that the size of sk is Ssk that is a constant. Thus, thetotal
size of storage overhead is 4·(m+1)+8·(m + 1)2+Sskbytes.
However, in [14], the storage overhead of data owneris _5=8 bytes, where the _ is the secure parameter. Thestorage
overhead is 4GB when we choose _ = 128, which ispopular in a full homomorphic
encryption scheme. However,the storage overhead of the FMS and the FMSCS are
almost763MB when we choose m = 10000,
which is large enoughfor a search scheme. Therefore, the FMS and the FMSCS aremore
efficient than scheme in [14] in terms of the storageoverhead of the data
owner.As shown in Table 4, a search user in the FMS, the FMSCSas well as the
schemes of [6] and [13] preserves the secret keyK = (S;M1;M2) and
the symmetric key sk locally.
Therefore,the total storage overhead is 4(m+1)+8(m + 1)2+Sskbytes. However, in [14], the storage
overhead is _5=8 + _2=8bytes. The storage overhead is 4GB
when we choose _ = 128,which
is popular in a full homomorphic encryption scheme.However, the storage
overhead of the FMS and the FMSCSare almost 763MB when we choose m = 10000, which islarge
enough for a search scheme. Therefore, the FMS andthe FMSCS are more efficient
than scheme in [14] in termsof the storage overhead of the search user.The
cloud server preserves the encrypted documents and theindexes. The size of
encrypted documents in all schemes arethe same, i.e., N·Ds. For the indexes,
in the FMS and schemesin [6] and [13], the storage overhead are 8 · (m+1) ·N bytes.In
the FMSCS, the storage overhead is 8·“· (m+1) ·N bytes,where
0 < ” < 1. When m = 1000 and N = 10000 whichare
large enough for a search scheme, the storage overhead ofindexes is about 132MB
in the FMSCS. And in schemes of [6]and [13] as well as the FMS, the size of
indexes is 760MB withthe same conditions. In scheme in [14], the storage
overheadof indexes is N · Ds + m · N · (_=8)5 bytes,
it is 4GB whenwe choose _ = 128,
which is popular in a full homomorphicencryption scheme. Therefore, the FMS and
the FMSCS aremore efficient than scheme in [14] in terms of the storageoverhead
of the cloud server.7.3.3
Communication overheadAs
shown in Table 5, we provide a comparison of communicationoverhead among
several schemes. Specifically,we consider the communication overhead from three
parts:the communication between the data owner and the cloudserver (abbreviated
as D-C),
the communication between thesearch user and the cloud server (abbreviated as C-S)
and thecommunication between the data owner and the search user(abbreviated as D-S).D-C. In the FMS as well as schemes of [6] and [13], the dataowner
needs to send information to cloud server in the formof Cj ||FIDj ||Ij (j = 1; 2; · · · ;N),
where the Cj representsthe encrypted documents, FIDj represents the identity of thedocument
and Ij represents the index. We assume that
theaverage size of documents is Ds,
thus the size of documentsis N ·Ds. We assume the encrypted documents
identity FIDis a 10-byte string. Thus, the total
size of the identity FIDis 10 · N bytes.
The index Ij = (paM1; pbM2) contains
two(m+1)-dimensional vectors. Each dimension is a float number(the size of each
float is 4 bytes). Thus, the total size of index is8·(m+1)·N bytes.
Therefore, the total size of communicationoverhead is 8·(m+1)·N+10·N+N·Ds bytes. In the FMSCS,the total size of
communication overhead is 8·“· (m+1)·N +10·N+N·Ds bytes. If we choose the ” as 0:2, the size of indexis 1:6 · (m+1) ·N bytes,
and the total size of communicationof FMSCS is 1:6·(m+1)·N+10·N+Ds ·N bytes. However,in [14], the
communication overhead is N ·Ds +m·N · _5=8bytes, where _ is the secure parameter. If we choose _ = 128which is popular in
a full homomorphic encryption schemeand m = 1000 and N = 10000 which are large enough fora search
scheme, the FMS and the FMSCS are more efficientthan scheme in [14] in terms of
the communication overheadof D-C.1545-5971 (c) 2015
IEEE. Personal use is permitted, but republication/redistribution requires IEEE
permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing12TABLE 4Comparison
of Storage Overhead (Bytes). (m represents
the size of dictionary; N represents the number ofdocuments;
Ds represents the average size of each
encrypted document; _ represents the secure
parameter; “represents the decrease rate of
dictionary by using our classified sub-dictionaries technology; Ssk represents the sizeof symmetric key.)[14] [6], [13] and FMS FMSCSData Owner
_5=8 4 _ (m + 1) + 8 _ (m + 1)2 + Ssk 4 _ (m + 1) + 8 _ (m + 1)2 + SskSearch User _5=8 + _2=8 4 _ (m + 1) + 8 _ (m + 1)2 + Ssk 4 _ (m + 1) + 8 _ (m + 1)2 + SskCloud Server N _ Ds + m _ N _ _5=8 N _ Ds + 8 _ (m + 1) _ N N _ Ds + 8 _ ” _ (m + 1) _ NTABLE 5Comparison of Communication
Overhead (Bytes). (m represents the size of
dictionary; N represents the number ofdocuments;
Ds represents the average size of each
encrypted document; T represents the number of
returneddocuments; _ represents the secure
parameter; ”
represents the decrease rate of
dictionary by using our classifiedsub-dictionaries technology; Ssk represents the size of symmetric key.)[14] [6], [13] and FMS FMSCSD-C N _ Ds + m _ N _ _5=8 8 _ (m + 1) _ N + 10 _ N + N _ Ds 8 _ ” _ (m + 1) _ N + 10 _ N + N _ DsC-S
m _ _5=8 + T _ Ds 8 _ (m + 1) + T _ Ds 8 _ ” _ (m + 1) + T _ DsD-S
_5=8 + _2=8 4 _ (m + 1) + 8 _ (m + 1)2 + Ssk 4 _ (m + 1) + 8 _ (m + 1)2 + SskC-S.
The C-S consists
of two phases: Query
and Resultsreturning.
In the Query phase, a search user in the FMS as
wellas the schemes in [6] and [13] sends the trapdoor to the cloudserver in the
form of TfW = (M−11 qa;M−12 qb), which containstwo (m+1)-dimensional
vectors. Thus, the communicationoverhead is 8·(m+1) bytes. In the FMSCS, the communicationoverhead
is 8 · ” · (m + 1)(0 < ” < 1) bytes. In the Resultsreturning phase, the cloud server sends the
correspondingresult to the search user. The communication overhead of CSincreases
along with the number of returned documentsat this point. We assume that the
number of the returneddocuments is T,
thus, the total communication overhead ofcloud server to search user is T · Ds bytes. Therefore,
thetotal communication overhead of C-S
is 8 ·m+T ·Ds bytes.In the FMS as well as the
schemes in [6] and [13], the totalcommunication overhead of C-S is 8 · ” · (m + 1) + T · Dsbytes. In [14], the total
communication overhead of C-S
ism·_5=8+T ·Ds bytes. If we choose
_ = 128 which is popularin
a full homomorphic encryption scheme and m = 1000 andN = 10000 which are large enough for a search
scheme, theFMS and the FMSCS are more efficient than scheme in [14]in terms of
the communication overhead of C-S.D-S.
From table 5, we can see that the
communicationoverhead of the FMS, the FMSCS as well as schemes in[6] and [13]
are the same. In the Initialization
phase, thedata owner sends the secret
key K = (S;M1;M2) andsymmetric
key sk to the search user, where S is an (m+ 1)-dimensional
vector, M1 and M2 are (m + 1) × (m + 1)invertible
matrices. Thus, the size of the secret key K is4 · (m + 1) + 8 · (m + 1)2 bytes.
Therefore, the total sizeof communication overhead is 4 · (m+1)+8 · (m + 1)2+Sskbytes, where the Ssk represents the size of symmetric key.However,
the communication overhead of scheme in [14] is_5=8+_2=8 bytes. The
communication overhead is 4GB whenwe choose _ = 128, which is popular in a full
homomorphicencryption scheme. However, the communication overhead ofthe FMS and
the FMSCS are almost 763MB when we choosem = 10000, which is large enough for a search
scheme.Therefore, the FMS and the FMSCS are more efficient thanscheme in [14]
in terms of the communication overhead ofD-S.8
RELATED WORKThere
are mainly two types of searchable encryption in literature,Searchable
Public-key Encryption (SPE) and SearchableSymmetric Encryption (SSE).8.1 SPESPE is first proposed by Boneh et al. [28], which supportssingle
keyword search on encrypted data but the computationoverhead is heavy. In the
framework of SPE, Boneh et al. [27]propose conjunctive, subset, and range
queries on encrypteddata. Hwang et al. [29] propose a conjunctive keyword
schemewhich supports multi-keyword search. Zhang et al. [17] proposean
efficient public key encryption with conjunctivesubsetkeywords search. However,
these conjunctive keywordsschemes can only return the results which match all
thekeywords simultaneously, and cannot rank the returned results.Qin et al.
[30] propose a ranked query scheme which usesa mask matrix to achieve
cost-effectiveness. Yu et al. [14]propose a multi-keyword top-k retrieval
scheme with fullyhomomorphic encryption, which can return ranked results andachieve
high security. In general, although SPE allows moreexpressive queries than SSE
[13], it is less efficient, andtherefore we adopt SPE in the work.8.2 SSEThe concept of SSE is first developed by Song et al. [8].Wang
et al. [25] develop the ranked keyword search scheme,which considers the
relevance score of a keyword. However,the above schemes cannot efficiently
support multi-keywordsearch which is widely used to provide the better
experience1545-5971 (c) 2015 IEEE. Personal use is permitted,
but republication/redistribution requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing13to the
search user. Later, Sun et al. [13] propose a multikeywordsearch scheme which
considers the relevance scoresof keywords, and it can achieve efficient query
by utilizingthe multidimensional tree technique. A widely adopted multikeywordsearch
approach is multi-keyword ranked search(MRSE) [6]. This approach can return the
ranked results ofsearching according to the number of matching keywords. Liet
al. [10] utilize the relevance score and k-nearest neighbortechniques to
develop an efficient multi-keyword searchscheme that can return the ranked
search results based on theaccuracy. Within this framework, they leverage an
efficientindex to further improve the search efficiency, and adopt theblind
storage system to conceal access pattern of the searchuser. Li et al. [19] also
propose an authorized and ranked multikeywordsearch scheme (ARMS) over
encrypted cloud databy leveraging the ciphertext policy attribute-based
encryption(CP-ABE) and SSE techniques. Security analysis demonstratesthat the
proposed ARMS scheme can achieve collusion resistance.In this paper, we propose
FMS(CS) schemes which notonly support multi-keyword search over encrypted data,
butalso achieve the fine-grained keyword search with the functionto investigate
the relevance scores and the preference factors ofkeywords and, more
importantly, the logical rule of keywords.In addition, with the classified
sub-dictionaries, our proposalis efficient in terms of index building, trapdoor
generating andquery.9 CONCLUSIONIn
this paper, we have investigated on the fine-grained multikeywordsearch (FMS)
issue over encrypted cloud data, andproposed two FMS schemes. The FMS I
includes both therelevance scores and the preference factors of keywords toenhance
more precise search and better users’ experience,respectively. The FMS II
achieves secure and efficient searchwith practical functionality, i.e., “AND”, “OR”
and “NO”operations of keywords. Furthermore, we have proposed theenhanced schemes
supporting classified sub-dictionaries (FMSCS)to improve efficiency.For the
future work, we intend to further extend the proposalto consider the
extensibility of the file set and the multi-usercloud environments. Towards
this direction, we have madesome preliminary results on the extensibility [5]
and the multiusercloud environments [19]. Another interesting topic is todevelop
the highly scalable searchable encryption to enableefficient search on large
practical databases.ACKNOWLEDGMENTThis work is supported by the National
Natural ScienceFoundation of China under Grants 61472065, 61350110238,61103207,
U1233108, U1333127, and 61272525, the InternationalScience and Technology
Cooperation and ExchangeProgram of Sichuan Province, China under Grant
2014HH0029,China Postdoctoral Science Foundation funded projectunder Grant
2014M552336, and State Key Laboratory ofInformation Security Open Foundation
under Grant 2015-MS-02.REFERENCES[1]
H. Liang, L. X. Cai, D. Huang, X. Shen, and D. Peng, “An smdpbasedservice model
for interdomain resource allocation in mobile cloudnetworks,” IEEE Transactions on Vehicular
Technology, vol. 61, no. 5,pp.
2222–2232, 2012.[2] M. M. Mahmoud and X. Shen, “A cloud-based scheme for
protectingsource-location privacy against hotspot-locating attack in wireless
sensornetworks,” IEEE
Transactions on Parallel and Distributed Systems,vol. 23, no. 10, pp. 1805–1818, 2012.[3]
Q. Shen, X. Liang, X. Shen, X. Lin, and H. Luo, “Exploiting geodistributedclouds
for e-health monitoring system with minimum servicedelay and privacy
preservation,” IEEE
Journal of Biomedical and HealthInformatics, vol. 18, no. 2, pp. 430–439, 2014.[4] T. Jung, X. Mao, X.
Li, S.-J. Tang, W. Gong, and L. Zhang, “Privacypreservingdata aggregation
without secure channel: multivariate polynomialevaluation,” in Proceedings of INFOCOM. IEEE, 2013, pp.2634–2642.[5] Y.
Yang, H. Li, W. Liu, H. Yang, and M. Wen, “Secure dynamicsearchable symmetric
encryption with constant document update cost,”in Proceedings of GLOBCOM. IEEE, 2014, to appear.[6] N. Cao, C.
Wang, M. Li, K. Ren, and W. Lou, “Privacy-preserving multikeywordranked search
over encrypted cloud data,” IEEE
Transactionson Parallel and Distributed Systems, vol. 25, no. 1, pp. 222–233, 2014.[7]
https://support.google.com/websearch/answer/173733?hl=en.[8] D. X. Song, D.
Wagner, and A. Perrig, “Practical techniques for searcheson encrypted data,” in
Proceedings of S&P. IEEE, 2000, pp. 44–55.[9] R. Li, Z.
Xu, W. Kang, K. C. Yow, and C.-Z. Xu, “Efficient multikeywordranked query over
encrypted data in cloud computing,” FutureGeneration
Computer Systems, vol.
30, pp. 179–190, 2014.[10] H. Li, D. Liu, Y. Dai, T. H. Luan, and X. Shen, “Enabling
efficientmulti-keyword ranked search over encrypted cloud data through blindstorage,”
IEEE Transactions on Emerging
Topics in Computing, 2014,DOI10.1109/TETC.2014.2371239.[11]
C. Wang, N. Cao, J. Li, K. Ren, and W. Lou, “Secure ranked keywordsearch over
encrypted cloud data,” in Proceedings
of ICDCS. IEEE,2010, pp.
253–262.[12] A. Boldyreva, N. Chenette, Y. Lee, and A. Oneill, “Order-preservingsymmetric
encryption,” in Advances
in Cryptology-EUROCRYPT.Springer,
2009, pp. 224–241.[13] W. Sun, B. Wang, N. Cao, M. Li, W. Lou, Y. T. Hou, and
H. Li,“Verifiable privacy-preserving multi-keyword text search in the cloudsupporting
similarity-based ranking,” IEEE
Transactions on Parallel andDistributed Systems, vol. DOI: 10.1109/TPDS.2013.282,
2013.[14] J. Yu, P. Lu, Y. Zhu, G. Xue, and M. Li, “Towards secure multikeywordtop-k
retrieval over encrypted cloud data,” IEEE
Transactionson Dependable and Secure Computing, vol. 10, no. 4, pp. 239–250,2013.[15]
A. Arvanitis and G. Koutrika, “Towards preference-aware relationaldatabases,”
in International Conference on Data
Engineering (ICDE).IEEE,
2012, pp. 426–437.[16] G. Koutrika, E. Pitoura, and K. Stefanidis, “Preference-based
querypersonalization,” in Advanced
Query Processing.
Springer, 2013, pp.57–81.[17] B. Zhang and F. Zhang, “An efficient public key
encryption withconjunctive-subset keywords search,” Journal of Network and ComputerApplications, vol. 34, no. 1, pp. 262–267, 2011.[18]
D. Stinson, Cryptography:
theory and practice. CRC
press, 2006.[19] H. Li, D. Liu, K. Jia, and X. Lin, “Achieving authorized and
rankedmulti-keyword search over encrypted cloud data,” in Proceedings of ICC.IEEE, 2015, to appear.[20] S. Zerr,
E. Demidova, D. Olmedilla, W. Nejdl, M. Winslett, andS. Mitra, “Zerber:
r-confidential indexing for distributed documents,” inProceedings of the 11th
international conference on Extending databasetechnology: Advances in database
technology. ACM, 2008, pp. 287–298.[21]
W. K. Wong, D. W.-l. Cheung, B. Kao, and N. Mamoulis, “Secureknn computation on
encrypted databases,” in Proceedings
of SIGMODInternational Conference on Management of data. ACM, 2009, pp.139–152.[22] J. Zobel
and A. Moffat, “Exploring the similarity space,” in ACM SIGIRForum, vol. 32, no. 1. ACM, 1998, pp. 18–34.[23]
N. Ferguson, R. Schroeppel, and D. Whiting, “A simple algebraicrepresentation
of rijndael,” in Selected
Areas in Cryptography.
Springer,2001, pp. 103–111.[24]
http://kdd.ics.uci.edu/databases/nsfabs/nsfawards.html.1545-5971
(c) 2015 IEEE. Personal use is permitted, but republication/redistribution
requires IEEE permission. Seehttp://www.ieee.org/publications_standards/publications/rights/index.html
for more information.This article has been accepted for publication in a future
issue of this journal, but has not been fully edited. Content may change prior
to final publication. Citation information: DOI10.1109/TDSC.2015.2406704, IEEE
Transactions on Dependable and Secure Computing14[25] C.
Wang, N. Cao, K. Ren, and W. Lou, “Enabling secure and efficientranked keyword
search over outsourced cloud data,” IEEE
Transactionson Parallel and Distributed Systems, vol. 23, no. 8, pp. 1467–1479,2012.[26]
P. Golle, J. Staddon, and B. Waters, “Secure conjunctive keyword searchover
encrypted data,” in Applied
Cryptography and Network Security.Springer,
2004, pp. 31–45.[27] D. Boneh and B. Waters, “Conjunctive, subset, and range
queries onencrypted data,” in Theory
of cryptography.
Springer, 2007, pp. 535–554.[28] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and
G. Persiano, “Public keyencryption with keyword search,” in Advances in Cryptology–Eurocrypt.Springer, 2004, pp. 506–522.[29] Y.
Hwang and P. Lee, “Zpublic key encryption with conjunctive keywordsearch and
its extension to a multi-user system,” in Proceeding ofPairing. Springer, 2007, pp. 2–22.[30] Q. Liu, C. C. Tan, J. Wu,
and G. Wang, “Efficient information retrievalfor ranked queries in
cost-effective cloud environments,” in Proceedingsof
INFOCOM. IEEE, 2012, pp.
2581–2585.Hongwei Li is an Associate Professor with theSchool of Computer Science
and Engineering,University of Electronic Science and Technologyof China, China.
He received the PhD degreein computer software and theory from Universityof
Electronic Science and Technology of China,China in 2008. He has worked as a
Post-Doctoral Fellow in Department of Electrical andComputer Engineering at
University of Waterloofor one year until Oct. 2012. His research interestsinclude
network security, applied cryptography,and trusted computing. Dr. Li serves as
the Associate Editor ofPeer-to-Peer Networking and Applications, the Guest
Editor for Peerto-Peer Networking and Applications Special Issue on Security
andPrivacy of P2P Networks in Emerging Smart City. He also serves onthe
technical program committees for many international conferencessuch as IEEE
INFOCOM, IEEE ICC, IEEE GLOBECOM, IEEE WCNC,IEEE SmartGridComm, BODYNETS and
IEEE DASC. He is a memberof IEEE, a member of China Computer Federation and a
member ofChina Association for Cryptologic Research.Yi Yang received
his B.S. degree in NetworkEngineering from Tianjin University of Scienceand
Technology (TUST) in 2012. Currently, he isa master student at the School of
Computer Scienceand Engineering, University of ElectronicScience and Technology
of China (UESTC), China.He serves as the reviewer of Peer-to-PeerNetworking and
Application, IEEE INFOCOM,IEEE ICC, IEEE GLOBECOM, IEEE ICCC, etc.His research
interests include cryptography, andthe secure smart grid.Tom H. Luan received
the B.Sc. degree fromXian Jiaotong University, China, in 2004, theM.Phil. degree
from Hong Kong University ofScience and Technology, Hong Kong, China, in2007,
and Ph.D. degrees from the Universityof Waterloo, Canada, in 2012. Since
December2013, he has been the Lecturer in Mobile andApps at the School of
Information Technology,Deakin University, Melbourne Burwood, Australia.His
research mainly focuses on vehicularnetworking, wireless content distribution,
peerto-peer networking and mobile cloud computing.Xiaohui Liang received
the B.Sc. degree inComputer Science and Engineering and theM.Sc. degree in
Computer Software and Theoryfrom Shanghai Jiao Tong University (SJTU), China,in
2006 and 2009, respectively. He is currentlyworking toward a Ph.D. degree in
the Departmentof Electrical and Computer Engineering,University of Waterloo,
Canada. His research interestsinclude applied cryptography, and securityand
privacy issues for e-healthcare system,cloud computing, mobile social networks,
andsmart grid.Liang Zhou is a professor with the NationalKey Lab of Science and
Technology on Communicationat University of Electronic Scienceand Technology of
China, China. His currentresearch interests include error control coding,secure
communication and cryptography.Xuemin
(Sherman) Shen is a
Professor andUniversity Research Chair, Department of Electricaland Computer
Engineering, University ofWaterloo, Canada. He was the Associate Chairfor
Graduate Studies from 2004 to 2008. Dr.Shen’s research focuses on resource
managementin interconnected wireless/wired networks,wireless network security,
vehicular ad hocand sensor networks. Dr. Shen served as theTechnical Program
Committee Chair for IEEEVTC’10 Fall and IEEE Globecom’07. He alsoserves/served
as the Editor-in-Chief for IEEE Network, Peer-to-PeerNetworking and
Application, and IET Communications; a Founding AreaEditor for IEEE
Transactions on Wireless Communications; an AssociateEditor for IEEE
Transactions on Vehicular Technology, ComputerNetworks. Dr. Shen is a
registered Professional Engineer of Ontario,Canada, an IEEE Fellow, an
Engineering Institute of Canada Fellow, aCanadian Academy of Engineering
Fellow, and a Distinguished Lecturerof IEEE Vehicular Technology Society and
Communications Society.