A ciphertext - Policy attribute-based searchable encryption scheme in non - interactive model

 returns yij to A.
• Regarding the second type of query: A first sends Wi = (w˜i1 , . . . , w˜ik) and B(u) to
simulator with the requirement that Wi doesn’t satisfy KF∗0 or KF∗1. To program
each tds0,j , j ∈ [k], the simulator first checks whether w˜ij , j ∈ [k] has been queried
before. If not, he/she chooses yij
$← Zp and adds triple (w˜ij , gyij , yij ) into L. In
both ways, simulator knows yij from L, and H(w˜ij ) = gyij since Wi doesn’t
satisfy KF∗0 or KF∗1. Next, simulator first chooses su, rj $← Zp then computes
tds0,j = g
α′gasugarj (gλ)yij = gαgasugarj (gaH(w˜ij ))λ.
Note that gα
′
= gα
′ · gaq+1 · g−aq+1 = gα · gaλ, since gλ = g−aq . Since simulator
knows su, rj , j ∈ [k], he/she can easily computes the rest of the trapdoor for any
set B(u). Finally, simulator returns tds to A.
• Regarding the third type of query: A first sends Wi = (w˜i1 , . . . , w˜ik) and B(u) to
simulator with the requirement that B(u) doesn’t satisfy β∗ and Wi “satisfies”
KF∗0 or KF∗1. The simulator first finds a vector −→x = (x1, . . . , xn∗) ∈ Zn∗p such
that x1 = −1 and for all i where ρ∗(i) ∈ B(u) the product 〈−→x ·M∗i 〉 = 0. The
simulator continues to pick ζ
$← Zp and implictly define the value su as
su = ζ + x1a
q + x2a
q−1 + · · ·+ xn∗aq−n∗+1.
The simulator computes
du0 = g
α′gaζ
∏
i=2,...,n∗
(ga
q+1−i
)xi = gα · ga·su ; d′u0 = gζ
∏
i=1,...,n∗
(ga
q+1−i
)xi = gsu .
For j ∈ B(u) such that there is no i ∈ [`∗] satisfying ρ∗(i) = j. The simulator
knows values zj and computes h
su
j = (g
su)zj . For j ∈ B(u) such that there is an
indice i ∈ [`∗] satisfying ρ∗(i) = j. The simulator computes
hsuj = (g
su)zj · g(ζ+x1aq+···+xn∗aq−n
∗+1)ωi
∑
k∈[n∗]M
∗
i,kta
k
.
A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME 245
Note that the product 〈−→x ·M∗i 〉 = 0 thus the simulator doesn’t need to know the
unknown term of form ga
q+1t to compute hsuj , all other terms he/she knows from
the assumption. Simulator simply sets gsu and {hsuj }j∈Bu as tds0 and {tdsi}i∈Bu ,
respectively. To program {tds0,j , tds1,j , {tds2,j,`}`∈Bu}j∈[k], the simulator consi-
ders two cases:
1. w˜ij “satisfies” KF∗0 or KF∗1, that means there exists at least a triple (ij , b, b′)
such that w˜ij = kf
∗
b,b′ . Simulator checks whether w˜ij has been queried
before. If not, he/she chooses yij
$← Zp and adds triple (w˜ij , g−agyij , yij )
into L. In both ways, simulator knows yij from L, and H(w˜ij ) = g−agyij .
Next, simulator chooses rj
$← Zp then computes
tds0,j = g
αgasugarj (g−a
q
)yij = gαgasugarj (gaH(w˜ij ))λ.
Note that λ = −aq. With known rj , simulator can easily compute tds1,j ,
{tds2,j,`}`∈Bu .
2. w˜ij doesn’t “satisfy” KF∗0 or KF∗1. Simulator checks whether w˜ij has been
queried before. If not, he/she chooses yij
$← Zp and adds triple (w˜ij , gyij , yij )
into L. In both ways, simulator knows yij from L, and H(w˜ij ) = gyij . Next,
simulator picks ζj
$← Zp and implicitly defines the value rj as
rj = ζj + x1a
q + x2a
q−1 + · · ·+ xn∗aq−n∗+1,
then similarly computes gαgarj , grj , {h˜`rj}`∈Bu as above (note that rj now
plays the role as su). He/she then sets g
−rj , {h˜`−rj}`∈Bu as tds1,j , {tds2,j,`}`∈Bu
respectively, and computes
tds0,j = g
αgasug−αg−arjgα
′
(g−a
q
)yij = gαgasug−arj (gaH(w˜ij ))λ.
Note that gα = gα
′
ga
q+1
and (gaH(w˜ij ))λ = g−a
q+1
(g−aq)yij .
Finally, simulator returns tds to A.
• Regarding the fourth and fifth types of query: It is straightforward since the
unknown value gα only appears in the tds0,j and du0 , therefore simulator can
simply choose su, {rj}j∈[k] $← Zp and then computes tds, or choose su, $← Zp and
then computes du.
Challenge: The simulator picks a random bit b, computes C∗0 = gs and
(C∗1 , . . . , C∗m) = I, (C˜∗1 , . . . , C˜∗m) = J , where
I =
(
gs(a+at)g
∑
i∈I1 szρ∗(i) , . . . , gs(a+at)g
∑
i∈Im szρ∗(i)
)
=
gs, (ga ∏
i∈β∗1
hi)
s, . . . , (ga
∏
i∈β∗m
hi)
s
 ,
246 VAN ANH TRINH, VIET CUONG TRINH
J =
(
gs(a+at)g
∑
i∈I1 sz˜ρ∗(i) , . . . , gs(a+at)g
∑
i∈Im sz˜ρ∗(i)
)
=
(ga ∏
i∈β∗1
h˜i)
s, . . . , (ga
∏
i∈β∗m
h˜i)
s
 .
To computes {K∗i }i∈[m′], simulator first checks whether kf∗b,i has been queried before.
If not, he/she chooses yi
$← Zp and adds triple (kf∗b,i, g−agyi , yi) into L. Otherwise,
he/she finds (kf∗b,i, g
−agyi , yi) from L. In both ways, simulator knows yi from L, and
H(kf∗b,i) = g−agyi . He/she computes
X∗i = T · e(gs, gα
′
) · e(gs, (gλ)yi) = T · e(gs, gα′) · e(gλ, gaH(kf∗b,i))s
then computes K∗i = H˜(X∗i , kf∗b,i). Finally, he/she outputs
ct′∗ = (C∗0 , {C∗i }i∈[m], {C˜∗i }i∈[m], {K∗i }i∈[m′]).
Note that if T = e(g, g)a
q+1s then ct′∗ is in valid form.
Query phase 2. Similar to phase 1.
Guess: A gives his guess b′ to S, S will output its guess 0 corresponding to T = e(g, g)aq+1s
if b′ = b; otherwise, S outputs its guess 1 corresponding to T is a random element.
When T = e(g, g)a
q+1s, S gives a perfect simulation so
Pr
[
S(~Y , T = e(g, g)aq+1s) = 0
]
=
1
2
+ AdvISA .
When T is a random element {K∗i }i∈[m′] are completely hidden from the A, so
Pr[S(~Y , T = R) = 0] = 1
2
. As a result, S is able to play the Modified - BDHE game
with non-negligible advantage (equal to AdvISA ) or S is able to break the security of
Modified-BDHE assumption.

Outsider Security. Outsider security is similar to the case of Insider Security, due to the
space limitations we omit it here.
5. COMPARISON
Regarding PEKS scheme supporting both expressive searching predicate and multi-writer
/multi-reader, to our knowledge [6, 8, 9, 11, 14] are the best schemes to date. In these
schemes, the authors in [9] proposed a PEKS schemes scheme with constant size of ciphertext,
however their scheme only supports limited AND-gates access policy. The authors in [6, 8,
11, 14] managed to transform from existing KP-ABE or CP-ABE schemes to PEKS schemes,
these schemes enjoy some interesting properties such as fast keyword search or outsourcing
decryption or partially trapdoor security. Other properties such as fined-grain access policy,
public key-size, ciphertext-size are similar to ones in our scheme, but our scheme has constant
A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME 247
size of secret key while they haven’t, moreover our model is different to their model. We give
in Fig 1 the comparison between our model and the model in [6, 8, 11, 14]. We can easily
see from Fig 1 that there is no TTG in our model, user relies solely on his/her secret key to
generate a trapdoor. In contrast, in their model, TTG takes charge of generating trapdoors
and therefore should be always online. Compare to their model, our model has two following
advantages:
• There is no TTG in our model, we therefore can save the system resource and the
communication overhead between user and TTG.
• In our model, user uses his/her secret key to generate trapdoors, cloud server relies on
such trapdoors to search corresponding ciphertexts, user therefore is able to decrypt all
the resulted ciphertexts. In contrast, in their model, TTG takes charge of generating
trapdoors and user’s secret key is not involved in this process, this leads to the fact that
the resulted ciphertexts may contain ciphertexts for which the user cannot decrypt. We
argue that our model is more useful in practice since it is waste time and communication
overhead if user receives the ciphertexts for which he/she cannot decrypt.
Cloud 
server 
Cloud 
server 
Trusted 
Trapdoor 
Generator 
Data 
owner 
User 
Encrypt documents 
and corresponding 
keywords 
1.Trapdoor 
2.Resulted 
ciphertexts 
Encrypt documents 
and corresponding 
keywords 
Data 
owner 
User 
3.Trapdoor 
4.Resulted 
ciphertexts 
1.Trapdoor request 
2.Trapdoor 
Figure 1. Our model on the left and their model on the right
We also note that the scheme in [15] can deal with well the problem of trapdoor secu-
rity, and moreover this scheme is very efficient in term of both communication and com-
putation. However, this scheme is in the different type to our scheme since our scheme
supports expressive searching while the scheme in [15] supports equality queries. Consi-
der the example in [6], W = (w1, w2, w3) where w1 = “Diabetes
′′, w2 = “Age : 30′′ and
w3 = “Weight : 150 − 200′′, user in our scheme can search for ciphertexts which has key-
word either “Diabetes′′ or “Weight : 150− 200′′. While the user in the scheme in [15] must
specify the keyword search is ”Diabetes” or “Weight : 150 − 200′′ and then receives only
the ciphertext corresponding to the keyword search. For example, if the keyword search is
“Diabetes′′, user only receives the ciphertext corresponding to “Diabetes′′. This is similar
to the difference between traditional public key encryption and attribute-based encryption.
248 VAN ANH TRINH, VIET CUONG TRINH
6. CONCLUSION
In this paper, we propose a CP-ABSE scheme which supports both expressive searching
predicate and multi-writer/multi-readers. To our knowledge, our scheme has some interesting
properties such as constant-size of secret key and in the non-interactive model. Our scheme
will become very efficient when the number of combinations of keywords to which a user
would like to search is small. Our scheme is therefore very suitable for a large class of
applications in practice for which the aforementioned case falls into.
ACKNOWLEDGMENTS
This research is funded by Vietnam National Foundation for Science and Technology
Development (NAFOSTED) under grant number 102.01-2018.301.
REFERENCES
[1] M. R. Asghar, G. Russello, B. Crispo, and M. Ion, “Supporting complex queries and access
policies for multi-user encrypted databases,” in Proceeding CCSW ’13 Proceedings of the
2013 ACM workshop on Cloud computing security workshop, Berlin, Germany, November
4, 2013, pp 77–88. Doi 10.1145/2517488.2517492
[2] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword
search,” Advances in Cryptology - EUROCRYPT 2004 International Conference on the
Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6,
2004, pp 506–522.
[3] D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner, “Highly-scalable
searchable symmetric encryption with support for Boolean queries”, in Advances in Cryptology
CRYPTO 2013 33rd Annual Cryptology Conference, Proceedings, Part I, Santa Barbara,
CA, USA, August 18-22, 2013.
[4] S. Canard and V. C. Trinh, “Constant-size ciphertext attribute-based encryption from multi-
channel broadcast encryption,” Information Systems Security. 12th International Confe-
rence, ICISS 2016, Proceedings, Jaipur, India, December 16-20, 2016.
[5] H. Cui, R. Deng, J. Liu, and Y. Li, “Attribute-based encryption with expressive and authorized
keyword search,” Information Security and Privacy. 22nd Australasian Conference, ACISP
2017, Proceedings, Auckland, New Zealand, July 35, 2017, Part I, pp. 106–126.
[6] H. Cui, Z. Wan, R. Deng, G. Wang, and Y. Li, “Efficient and expressive keyword search over
encrypted data in the cloud,” IEEE Transactions on Dependable and Secure Computing,
vol. 15, no. 3, pp. 409–422, 2018. Doi 10.1109/TDSC.2016.2599883
[7] S. Hohenberger and B. Waters, “Attribute-based encryption with fast decryption,” Public-
Key Cryptography PKC 2013. 16th International Conference on Practice and Theory
in Public-Key Cryptography, Proceedings, Nara, Japan, February 26 March 1, 2013, pp.
162–179.
[8] Jianting Ning, Zhenfu Cao, Xiaolei Dong, Kaitai Liang, Hui Ma, Lifei Wei, “Auditable σ-
Time Outsourced Attribute-Based Encryption for Access Control in Cloud Computing,” IEEE
Transactions on Information Forensics and Security, vol. 13, no. 1, pp. 94–105, 2018. Doi
10.1109/TIFS.2017.2738601
A CIPHERTEXT-POLICY ATTRIBUTE-BASED SEARCHABLE ENCRYPTION SCHEME 249
[9] Jinguang Han, Ye Yang, Joseph K. Liu, Jiguo Li,Kaitai Liang,Jian Shen, “Expressive attribute-
based keyword search with constant-size ciphertext,” In Soft Computing Journal, vol. 22, no.
15, pp 5163-5177, August 2018.
[10] A. Kiayias, O. Oksuz, A. Russell, Q. Tang, and B. Wang, “Efficient encrypted keyword search for
multi-user data sharing,” Computer Security ESORICS 2016. 21st European Symposium
on Research in Computer Security, Proceedings, Heraklion, Greece, September 26-30, 2016,
Part I, pp 173–195.
[11] J. Lai, X. Zhou, R. H. Deng, Y. Li, and K. Chen, “Expressive search on encrypted data,” ASIA
CCS ’13 Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and
Communications Security, Hangzhou, China, May 8-10, 2013, pp 243–251.
[12] Z. Lv, C. Hong, M. Zhang, and D. Feng, “Expressive and secure searchable encryption in the
public key setting,” Information Security 17th International Conference, ISC 2014, Pro-
ceedings, Hong Kong, China, October 12-14, 2014, pp 364–376.
[13] Q. M. Malluhi, A. Shikfa, and V. C. Trinh, “A ciphertext-policy attribute-based encryption
scheme with optimized ciphertext size and fast decryption,” Proceeding ASIA CCS ’17 Procee-
dings of the 2017 ACM on Asia Conference on Computer and Communications Security,
Abu Dhabi, United Arab Emirates, April 02 - 06, 2017, pp. 230–240.
[14] R. Meng, Y. Zhou, J. Ning, K. Liang, J. Han, and W. Susilo, “An efficient key-policy attribute-
based searchable encryption in prime-order groups,” Provable Security 11th International
Conference, ProvSec 2017, Proceedings, Xi’an, China, October 23-25, 2017, pp. 39–56.
[15] Qiong Huang and Hongbo Li, “An efficient public-key searchable encryption scheme secure
against inside keyword guessing attacks,” Information Sciences Journal, vol. 403–404, pp.
1–14, September 2017. Doi.org/10.1016/j.ins.2017.03.038
[16] D. X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,”
Proceeding 2000 IEEE Symposium on Security and Privacy, Berkeley, CA, USA, May 14–17,
2000, pp. 44–55. Doi 10.1109/SECPRI.2000.848445
[17] S. Sun, J. K. Liu, A. Sakzad, R. Steinfeld, and T. H. Yuen, “An efficient non-interactive multi-
client searchable encryption with support for boolean queries,” Computer Security ESORICS
2016. 21st European Symposium on Research in Computer Security, Proceedings, Part I,
Heraklion, Greece, September 26–30, 2016, pp. 154–172.
[18] Y. Wang, J. Wang, S. Sun, J. Liu, W. Susilo, and X. Chen, “Towards multi-user searchable en-
cryption supporting boolean query and fast decryption,” Provable Security 11th International
Conference, ProvSec 2017, Proceedings, Xi’an, China, October 23–25, 2017, pp. 24–38.
[19] Y. Yang, H. Lu, and J. Weng, “Multi-user private keyword search for cloud computing,”
2011 IEEE Third International Conference on Cloud Computing Technology and Science,
Athens, Greece, 29 Nov.- Dec. 01, 2011, pp. 264–271. Doi 10.1109/CloudCom.2011.43
Received on March 05, 2019
Revised on April 18, 2019