JMedSyst (2016) 40:255 Page 3 of 11 255
Generally, a SSE scheme can be constructed by Fully
Homomorphic Encryption(FHE, first achieved by Gentry
[10] in 2009), Oblivious RAM(ORAM, proposed by Ostro-
vsky [19] in 1990), and Private Information Retrieval(PIR,
proposed by Ostrovsky [7] in 1998). Those methods can
get a high level security in theory, but they are too ineffi-
cient for practice. There are also other ways to build SSE
scheme, for example, the CryptDB [20]. The CryptDB is
proposed by Popa et al. in 2011, which is based on the con-
ception of Order-Preserving symmetric Encryption(OPE,
introduced by Agrawal et al. [1] in 2004), it is practical but
has significant information leakage [18].
There are many works make trade-offs among secu-
rity,functionality and performance, the more details can be
seen in the work of BOSCH et al. [4], which reviews the SE
works before 2014. There are also many works such as [9,
22, 23] after 2014.
The papers mentioned above focused on single-keyword
searches, extending single-keyword SSE to search by con-
junctions of keywords was considered in [2, 5, 11], but all
these schemes has O(|DB|) search complexity.
In 2013, Cash et al. [6] provided a Oblivious Cross-Tags
(OXT) Protocol, and use it to build a SSE schemes for
boolean keyword search, which supports arbitrary boolean
queries on encrypted index, and it is practical for large
databases. But in their scheme, only the data owner can
make a query to cloud server, so it is single writer/single
reader architecture. Based on [6], Jarecki et al. make some
improvements [15], one of them is Multi-Client OXT(MC-
OXT) protocol, which can be used to construct a Multi-
Client SSE(MC-SSE) scheme. Our work is main based
these two works and make some improvement.
Our work
Both [6]and[15] suppose boolean query. In their scheme,
they bind the keyword w and document identifier
ind
together to justify that document ind contains keyword w,
and encrypt pair (w,
ind) by a blind factor. The blind fac-
tor is derivated by a counter c that denote the serial no.
of
ind in the list of documents which contain the keyword
w. In the case of boolean query, for example a conjunctive
w
1
∧ w
2
∧ w
2
,
1
they finds the inds that contains the w
1
,and
for each
ind in inds, verifies if both (w
2
, ind) and (w
3
, ind)
are existed. Then they must eliminate the blind factor. The
data user encrypting the (w, ind) has no ideal of blind fac-
tor c, moreover, the blind factor c
2
for (w
2
, ind) and c
3
for
(w
3
, ind) are often defferent, because the serial no. of ind) in
the list of documents which contain the keyword w is often
diffrent in lists of documents which contain keyword w
3
’s.
So the user has to try c = 1, 2, ··· one by one until he meets
1
handle arbitrary Boolean query expressions is decribed in [6]
the correct one. Those attemptions significantly increase the
computation and communication costs of the scheme. We
improve their scheme by asign a random number as blind
factor for each (w,
ind) pair, and upload those blind factor
to the cloud server. In the search phase in our scheme, we
design two round interaction b etween server and user, which
allow cloud server sends back necessary blinder factors,
then the data user can generate the exactly search tokens.
This will decreate the computation and comunication cost
remarkable.
Preliminaries and notations
Notions of boolean queries
Database
DB(Forward Index) Suppose that the data
owner has d documents. Let
IND ={ind
1
, ind
2
, ··· , ind
d
}
denotes the set of the document identifiers. Each document
ind
i
is comprised of a set of keywords W
ind
i
={w
ind
i
1
, w
ind
i
2
,
···, w
ind
i
|W
ind
i
|
},where|·|denotes the order of the set. We
will take identifiers and keywords as bit strings. Let λ be the
security parameter, then for i = 1, ···, d,
ind
i
∈{0, 1}
λ
and
W
ind
i
⊆{0, 1}
∗
. A database DB = (ind
i
, W
ind
i
)
d
i=1
is a list of
identifier/keyword-set pairs. By this definition, the database
DB is actually a forward index of the documents set. Table 1
shows the structure of
DB.
Inverted index I From the DB, we can figure out the set
of all keywords W =∪
d
i=1
W
ind
i
. Suppose that |W|=m,
then we can write W ={w
1
,w
2
, ··· ,w
m
}. For each w
i
∈
W,letI
w
i
={ind
w
i
1
, ind
w
i
2
, ··· , ind
w
i
|I
w
i
|
} denotes the iden-
tifier set of documents that contain the keyword w
i
.Then
the inverted index of the documents set is a list of keyword/
identifier-set pairs that can be written as
I = (w
i
,I
w
i
)
m
i=1
.
Table 2 shows the structure of the inverted index
I.
Boolean query ψ(
¯
w) Suppose ¯w = ( ¯w
1
, ··· , ¯w
n
) is a
n-tuple of keywords, where ¯w
i
∈ W for i = 1, ··· ,n. ψ is
Tabl e 1 The data structure of Database
DB(Forward Index)
Document identifier List of keywords in the document
ind
1
W
ind
1
={w
ind
1
1
, w
ind
1
2
, ···, w
ind
1
|W
ind
1
|
}
ind
2
W
ind
2
={w
ind
2
1
, w
ind
2
2
, ···, w
ind
2
|W
ind
2
|
}
.
.
.
.
.
.
ind
i
W
ind
i
={w
ind
i
1
, w
ind
i
2
, ···, w
ind
i
|W
ind
i
|
}
.
.
.
.
.
.
ind
d
W
ind
d
={w
ind
d
1
, w
ind
d
2
, ···, w
ind
d
|W
ind
d
|
}