3650 IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 14, NO. 8, AUGUST 2018
β
2
γ
1
α
t
fH
2
=(β
2
γ
1
f)(α
t
)H
2
, one of d
i
and d
j
must be α
t
.
However, the α
t
is not in D. Hence, there are no coefficients
{x
i,j
}, {y
k
},z
1
such that the equation Σx
i,j
d
i
d
j
=Σy
k
d
k
p
1
+
z
1
holds.
Therefore, the (2n, n, 1)-MSE-DDH Problem is intractable.
Definition 2 ((2n, n, 2)-MSE-DDH Problem): Let n be an
integer and (p, G, G
T
,e) be a bilinear map group sys-
tem. Let g be the generators of G and h
1
= g
γ
1
,h
2
= g
γ
2
.
α, β
1
,β
2
,H
1
,H
2
∈ Z
∗
p
. Set f is random coprime with α, whose
order is deg(f)=1, Z ∈ G, and given the following sequences
of group elements:
g, g
β
2
,g
x
g
β
2
α
1
, ..., g
β
2
α
n −#
g
β
2
α
n + 2−#
, ..., g
β
2
α
n
g
γ
1
α
1
, ..., g
γ
1
α
n
g
γ
1
f
,g
γ
1
β
2
f
g
(β
2
H
2
+γ
2
α
1
)f
, ..., g
(β
2
H
2
+γ
2
α
# −1
)f
g
(β
2
H
2
+γ
2
α
#+1
)f
, ..., g
(β
2
H
2
+γ
2
α
n
)f
g
(β
2
H
1
+γ
2
α
1
)f
, ..., g
(β
2
H
1
+γ
2
α
n
)f
g
γ
2
α
1
, ..., g
γ
2
α
2n
where # means a random number chosen from {1,...,n}.The
problem is to distinguish whether Z equals to g
β
2
(α
n + 1−#
H
2
+x)
or some random element in G.
Intractability of (2n, 1, 2)-MSE-DDH Problem: The intract-
ability of (2n, n, 2)-MSE-DDH problem can be proved similarly
as the intractability of (2n, n, 1)-MSE-DDH problem. Therefore,
the (2n, n, 2)-MSE-DDH Problem is intractable.
III. N
EW INSIDER ATTACK TO CUI’S KEY-AGGREGATE
SEARCHABLE ENCRYPTION
A. Cui’s Key-Aggregate Searchable Encryption
We simply describe Cui’s scheme [14].
1) Setup(κ, n): The cloud server does the work as follows.
a) Generate a bilinear map group system B =
(p, G, G
1
,e(·, ·)), where p is the order of G and
2
κ
≤ p ≤ 2
κ+1
.
b) Set n as the maximum possible number of documents,
which belong to the data owner.
c) Randomly pick g ∈Gand α ∈ Z
∗
p
, and compute g
i
=
g
(α)
i
∈Gfor i =(1, 2,...,n,n+ 2,...,2n).
d) Select a one-way hash function H : {0, 1}
∗
→G.
e) Keep (α, g
1
,...,g
n
,g
n+2
,...,g
2n
) secretly, and
publicize the public parameters Params =
{p, G, G
1
,e(·, ·)),g,H(·)}.
2) KeyGen: The data owner chooses a random γ ∈ Z
∗
p
and
sets the data owner’s master-key as msk = γ and public
key as pk = v = g
γ
.
3) Encrypt(i, k, w):Forthei-th document (i ∈
{1,...,n}), the data owner picks a random t ∈
Z
p
and computes the ciphertext (c
1
,c
2
,c
w
)=(g
t
, (v ·
g
i
)
t
,
e(g,H(w ))
t
e(g
1
,g
n
)
t
).
4) Extract(msk, S): For any subset S ⊆{1,...,n},the
data owner computes k
agg
=
j∈S
g
γ
n+1−j
and sends
(k
agg
,S) to the user through a secure channel.
5) Tra pd oo r(k
agg
,w): The user generates the trapdoor
Tr = k
agg
· H(w) and sends (Tr,S) to the cloud server.
6) Adjust(i, S, T r): the cloud server adjusts the right trap-
door for all i ∈ S as Tr
i
= Tr·
j∈S,j=i
g
n+1−j + i
.
7) Tes t(Tr
i
,i):Forthei-th document, the cloud server
computes pub =
j∈S
g
n+1−j
and outputs true if c
w
=
e(Tr
i
,c
1
)
e(pub,c
2
)
holds, and false otherwise.
B. New Attack to Cui’s Scheme
Aggelos Kiayias’s attacks win the games as keyword dictio-
nary guessing. In Aggelos Kiayias’s attack, the size of guessing
keyword dictionary is same as the size of whole keyword space.
We show a new attack to Cui’s scheme, which can be done by
inside unauthorized users. In our attack, the size of guessing
keyword dictionary equals to the number of keywords in the
attacked file. Therefore, our attack is much more efficient. We
describe our attack as follows.
Assume that A is a user to be attacked whose authorized
private key is k
agg
and access set is S
A
, and B is an inside
attacker whose access set is S
B
. We assume that S
A
= S
B
,
S
A
∩ S
B
= ∅, and S
A
S
B
. To simplify our description, let
F
l
∈ (S
A
∩ S
B
) and the keywords in F
l
be {w
1
,w
2
,w
3
}.
A submits a trapdoor Tr = k
agg
· H(w
∇
) for keyword
search and the cloud server returns this keyword search result
after testing. The document F
l
is one of the results.
B eavesdrops the trapdoor Tr submitted from A, and he
computes an aggregation key set K = {k
agg
1
,k
agg
2
,k
agg
3
} =
Tr
H (w
1
)
,
Tr
H (w
2
)
,
Tr
H (w
3
)
}. Then, k
agg
∈{k
agg
1
,k
agg
2
,k
agg
3
}.
B can correctly guess k
agg
as follows: First, B guesses
w
∇
= w
1
and k
agg
= k
agg
1
, and computes Tr
= k
agg
1
· H(w
2
)
or Tr
= k
agg
1
· H(w
3
). Then, B sends Tr
to the cloud server
to do search query. Unfortunately, the cloud server cannot dis-
tinguish that the search query is submitted by A or B. Therefore,
it responds the result honestly. If F
l
is in the returned result, the
trapdoor Tr
is valid and k
agg
= k
agg
1
; otherwise, the trapdoor
Tr
is invalid. B continues to try k
agg
2
and k
agg
3
and does the
similar test until he finds the correct k
agg
. B performs the test
at most three runs to obtain A’s private key k
agg
.
In the above attack, the attacker B can only be successful if he
shares the access of F
l
. Upon obtaining A’s private key k
agg
,
B can further do the same attack to those who share file access
with A.
IV. S
YSTEM DEFINITION AND SECURITY MODEL OF
FC-MKA-KSE IN DATA SHARING
A. Formal System Definition of Fc-MKA-KSE in Data
Sharing
Definition 3: As shown in Fig. 2, the Fc-MKA-KSE system
in data sharing consists of the following eight algorithms.
1) Setup(κ): The algorithm generates the system parame-
ter GP .
Authorized licensed use limited to: University of Electronic Science and Tech of China. Downloaded on March 21,2020 at 15:13:22 UTC from IEEE Xplore. Restrictions apply.