Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage

doi:10.1007/s11704-021-0601-8

Front. Comput. Sci.

2022, Vol. 16

Issue (6) : 166820 https://doi.org/10.1007/s11704-021-0601-8

RESEARCH ARTICLE

Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage

Qingqing GAN^1,², Joseph K. LIU³(

), Xiaoming WANG², Xingliang YUAN³, Shi-Feng SUN³, Daxin HUANG², Cong ZUO³, Jianfeng WANG⁴

¹. Guangzhou Key Laboratory of Multilingual Intelligent Processing, School of Information Science and Technology/ School of Cyber Security, Guangdong University of Foreign Studies, Guangzhou 510006, China
². Department of Computer Science, Jinan University, Guangzhou 510632, China
³. Faculty of Information Technology, Monash University, Clayton 3168, Australia
⁴. State Key Laboratory of Integrated Service Networks (ISN), Xidian University, Xi’an 710071, China

Download: PDF(27346 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Searchable symmetric encryption (SSE) has been introduced for secure outsourcing the encrypted database to cloud storage, while maintaining searchable features. Of various SSE schemes, most of them assume the server is honest but curious, while the server may be trustless in the real world. Considering a malicious server not honestly performing the queries, verifiable SSE (VSSE) schemes are constructed to ensure the verifiability of the search results. However, existing VSSE constructions only focus on single-keyword search or incur heavy computational cost during verification. To address this challenge, we present an efficient VSSE scheme, built on OXT protocol (Cash et al., CRYPTO 2013), for conjunctive keyword queries with sublinear search overhead. The proposed VSSE scheme is based on a privacy-preserving hash-based accumulator, by leveraging a well-established cryptographic primitive, Symmetric Hidden Vector Encryption (SHVE). Our VSSE scheme enables both correctness and completeness verifiability for the result without pairing operations, thus greatly reducing the computational cost in the verification process. Besides, the proposed VSSE scheme can still provide a proof when the search result is empty. Finally, the security analysis and experimental evaluation are given to demonstrate the security and practicality of the proposed scheme.

Keywords searchable symmetric encryption verifiability conjunctive keyword queries hash-based accumulator cloud storage

Corresponding Author(s): Joseph K. LIU

Just Accepted Date: 26 July 2021 Issue Date: 28 January 2022

Cite this article:

Qingqing GAN,Joseph K. LIU,Xiaoming WANG, et al. Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage[J]. Front. Comput. Sci., 2022, 16(6): 166820.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-021-0601-8
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I6/166820

Notation	Meaning
$λ$	Security parameter
$i d i$	Identifier of the $i$ -th file where $i d i ∈ {0, 1} λ$
$d$	Number of files in the database
$w$	Keyword where $w ∈ {0, 1} λ$
$W i$	Keyword list of $i d i$
$W$	Keyword set $∪ i = 1 d W i$ where $W ≤ p$
$D B$	Database $(i d i, W i) i = 1 d$
$D B (w)$	File identifiers containing $w$ where $D B (w) < p$
$F$	Pseudo-random function (PRF) ${0, 1} λ × {0, 1} λ ? {0, 1} λ$
$F p$	PRF ${0, 1} λ × {0, 1} ? ? Z p ?$
$F q$	PRF ${0, 1} λ × {0, 1} ? ? Z q ?$
$S$	Subset of integer set ${1, 2, . . ., (q ? 1)}$
$S$	Number of elements in set $S$
$H$	Collision-resistant hash function ${0, 1} ? ? {0, 1} λ$
$H ~$	Collision-resistant hash function ${0, 1} λ × {0, 1} λ ? {0, 1} λ$
${H j} 1 ≤ j ≤ k$	$k$ independent collision-resistant hash functions ${0, 1} λ ? Z p ?$
$Acc$	Accumulator value
$AccT$	Accumulator tree
$R w 1$	Search result containing $w 1$
$R$	Search result for a conjunctive query
prf	Proof information

Tab.1 Notations

Fig.1

Fig.2

Fig.3 Accumulator tree model

Algorithm	Computation overhead
$AccTCon$	$C o m p (SHVE.Setup) + (2 n + 1) (C o m p (SHVE.Enc) + H a s h)$
$AccTCon$	$+ 2 (n + 1) C o m p (Sym.Enc) + k (? l o g (n + 1) ? + 1) H a s h$
$TokenGen$	$C o m p (SHVE.KeyGen) + k ? H a s h$
$AccTRetr$	$(? l o g (n + 1) ? + 1) ? C o m p (SHVE.Query)$
$Belongs$	$2 C o m p (Sym.Dec) + (? l o g (n + 1) ? + 1) ? H a s h$

Tab.2 Computation overhead of the proposed accumulator

	The size of $S$
	$10$	$102$	$103$
$AccTCon$ .Time/s	8.5934922	73.2162735	684.6005188
$TokenGen$ .Time/s	0.9434835	10.4222397	103.9404878
$AccTRetr$ .Time/s	0.0009242	0.004147	0.0212089
$Belongs$ .Time/s	0.0004828	0.0031381	0.0149017

Tab.3 Time cost of the proposed accumulator

Fig.4

Fig.5

Fig.6 Overview of the proof generation procedure

Fig.7

Fig.8

Fig.9 The process from the keyword to an accumulator

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Tab.4 Functionality comparison with existing VSSE schemes

		Wang et al. [19]	Our Scheme
Setup		$(D B + 3 W + 2) ? E x p$	$D B ? E x p + C o m p (AccTCon S) + C o m p (AccTCon X)$
TdGen		$(R w 1 ? (m ? 1) + (m + 1)) ? E x p$	$2 (R w 1 ? (m ? 1)) ? E x p + C o m p TokenGen S + R w 1 ? (m ? 1) ? C o m p TokenGen X$
Search (Server)	$R w 1 = ?$	$(W ? 1) ? E x p$	$AccTRetr S$
	$(R w 1 ≠ ?)$	$(R w 1 ? (m ? 1)) ? E x p + (W ? 1) ? E x p$
	$∧ (R = ?)$	$+ k^(D B ? 2) ? E x p$	$(R w 1 ? (m ? 1) ? E x p + C o m p AccTRetr S$
	$R ≠ ?$	$(R w 1 ? (m ? 1)) ? E x p + (W ? 1) ? E x p + (D B ? R ? 1) ? E x p + k^(D B ? 2) ? E x p$	$+ (R w 1 ? (m ? 1) ? C o m p AccTRetr X$
Verify (Client)	$R w 1 = ?$	$2 E x p + 2 P a i r$	$C o m p Belongs S$
	$(R w 1 ≠ ?)$	$(k^? (m ? 1) + (m ? 1)) ? E x p$	$C o m p Belongs S + (R w 1 ? (m ? 1)) ? C o m p Belongs X$
	$∧ (R = ?)$	$+ E x p + 2 P a i r + k^? (2 E x p + 2 P a i r)$
	$R ≠ ?$	$(k^? (m ? 1) + (m ? 1)) ? E x p + 2 E x p + 4 P a i r + k^? (2 E x p + 2 P a i r)$

Tab.5 Computation overhead comparison for the conjunctive query

w = (w 1 ∧ ? ∧ w m)

Fig.16 The performance comparison with related works. (a) Time cost of

Search

with real-world data; (b) time cost of

Search

with synthetic data; (c) time cost of

Verify

algorithm

1	P Sun . Security and privacy protection in cloud computing: discussions and challenges. Journal of Network and Computer Applications, 2020, 160 : 102642–
2	J K Liu , K Liang , W Susilo , J Liu , Y Xiang . Two-factor data security protection mechanism for cloud storage system. IEEE Transactions on Computers, 2016, 65( 6): 1992– 2004
3	R Bost. Σoφoς: forward secure searchable encryption. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 1143−1154
4	D Cash, J Jaeger, S Jarecki, C Jutla, H Krawczyk, M C Ros, M Steiner. Dynamic searchable encryption in very-large databases: data structures and implementation. In: Proceedings of the 21st Annual Network and Distributed System Security Symposium. 2014, 23– 26
5	R Curtmola , J Garay , S Kamara , R Ostrovsky . Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895– 934
6	S Lai, S Patranabis, A Sakzad, J K Liu, D Mukhopadhyay, R Steinfeld, S F Sun, D Liu, C Zuo. Result pattern hiding searchable encryption for conjunctive queries. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 745– 762
7	C Zuo, S F Sun, J K Liu, J Shao, J Pieprzyk. Dynamic searchable symmetric encryption schemes supporting range queries with forward/backward privacy. 2019, arXiv preprint arXiv: 1905.08561
8	D Cash, S Jarecki, C Jutla, H Krawczyk, M C Roşu, M Steiner. Highly-scalable searchable symmetric encryption with support for Boolean queries. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 353– 373
9	S F Sun, J K Liu, A Sakzad, R Steinfeld, T H Yuen. An efficient non-interactive multi-client searchable encryption with support for Boolean queries. In: Proceedings of the 21st European Symposium on Research in Computer Security. 2016, 154– 172
10	S K Kermanshahi , J K Liu , R Steinfeld , S Nepal , S Lai , R Loh , C Zuo . Multi-client cloud-based symmetric searchable encryption. IEEE Transactions on Dependable and Secure Computing, 2021, 18( 5): 2419– 2437
11	C Zuo, J Macindoe, S Yang, R Steinfeld, J K Liu. Trusted Boolean search on cloud using searchable symmetric encryption. In: Proceedings of 2016 IEEE Trustcom/BigDataSE/ISPA. 2016, 113– 120
12	S Faber, S Jarecki, H Krawczyk, Q Nguyen, M Rosu, M Steiner. Rich queries on encrypted data: beyond exact matches. In: Proceedings of the 20th European Symposium on Research in Computer Security. 2015, 123– 145
13	R Bost , P A Fouque , D Pointcheval . Verifiable dynamic symmetric searchable encryption: optimality and forward security. IACR Cryptology ePrint Archive, 2016, 2016 : 62–
14	R Cheng, J Yan, C Guan, F Zhang, K Ren. Verifiable searchable symmetric encryption from indistinguishability obfuscation. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security. 2015, 621– 626
15	Kurosawa K, Ohtaki Y. How to update documents verifiably in searchable symmetric encryption. In: Proceedings of the 12th International Conference on Cryptology and Network Security. 2013, 309–328
16	W Ogata , K Kurosawa . No-dictionary searchable symmetric encryption. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2019, 102( 1): 114– 124
17	A Soleimanian , S Khazaei . Publicly verifiable searchable symmetric encryption based on efficient cryptographic components. Designs, Codes and Cryptography, 2019, 87( 1): 123– 147
18	J Zhu , Q Li , C Wang , X Yuan , Q Wang , K Ren . Enabling generic, verifiable, and secure data search in cloud services. IEEE Transactions on Parallel and Distributed Systems, 2018, 29( 8): 1721– 1735
19	J Wang, X Chen, S F Sun, J K Liu, M H Au, Z H Zhan. Towards efficient verifiable conjunctive keyword search for large encrypted database. In: Proceedings of the 23rd European Symposium on Research in Computer Security. 2018, 83−100
20	D X Song, D Wagner, A Perrig. Practical techniques for searches on encrypted data. In: Proceedings of 2000 IEEE Symposium on Security and Privacy. 2000, 44−55
21	E J Goh . Secure indexes. IACR Cryptology ePrint Archive, 2003, 2003 : 216–
22	C Liu , L Zhu , J Chen . Efficient searchable symmetric encryption for storing multiple source dynamic social data on cloud. Journal of Network and Computer Applications, 2017, 86 : 3– 14
23	Q Gan , X Wang , D Huang , J Li , D Zhou , C Wang . Towards multi-client forward private searchable symmetric encryption in cloud computing. IEEE Transactions on Services Computing, 2021, DOI: 10.1109/TSC.2021.3087155,
24	Y Miao , X Liu , R H Deng , H Wu , H Li , J Li , D Wu . Hybrid keyword-field search with efficient key management for industrial internet of things. IEEE Transactions on Industrial Informatics, 2019, 15( 6): 3206– 3217
25	Y Miao , Q Tong , K K R Choo , X Liu , R H Deng , H Li . Secure online/offline data sharing framework for cloud-assisted industrial internet of things. IEEE Internet of Things Journal, 2019, 6( 5): 8681– 8691
26	Kurosawa K, Ohtaki Y. UC-secure searchable symmetric encryption. In: Proceedings of the 16th International Conference on Financial Cryptography and Data Security. 2012, 285−298
27	Q Chai, G Gong. Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers. In: Proceedings of 2012 IEEE International Conference on Communications (ICC). 2012, 917−922
28	S Taketani, W Ogata. Improvement of UC secure searchable symmetric encryption scheme. In: Proceedings of the 10th International Workshop on Advances in Information and Computer Security. 2015, 135−152
29	Z Zhang, J Wang, Y Wang, Y Su, X Chen. Towards efficient verifiable forward secure searchable symmetric encryption. In: Proceedings of the 24th European Symposium on Research in Computer Security. 2019, 304−321
30	K Yoneyama, S Kimura. Verifiable and forward secure dynamic searchable symmetric encryption with storage efficiency. In: Proceedings of the 19th International Conference on Information and Communications Security. 2017, 489−501
31	X Ge , J Yu , H Zhang , C Hu , Z Li , Z Qin , R Hao . Towards achieving keyword search over dynamic encrypted cloud data with symmetric-key based verification. IEEE Transactions on Dependable and Secure Computing, 2021, 18( 1): 490– 504
32	M Miao , Y Wang , J Wang , X Huang . Verifiable database supporting keyword searches with forward security. Computer Standards & Interfaces, 2020, 77 : 103491–
33	M Miao , J Wang , S Wen , J Ma . Publicly verifiable database scheme with efficient keyword search. Information Sciences, 2019, 475 : 18– 28
34	Y Miao , X Liu , K K R Choo , R H Deng , H Wu , H Li . Fair and dynamic data sharing framework in cloud-assisted internet of everything. IEEE Internet of Things Journal, 2019, 6( 4): 7201– 7212
35	Shao J, Lu R, Guan Y, Wei G. Achieve efficient and verifiable conjunctive and fuzzy queries over encrypted data in cloud. IEEE Transactions on Services Computing, 2019, DOI: 10.1109/TSC.2019.2924372
36	X Liu , G Yang , Y Mu , R H Deng . Multi-user verifiable searchable symmetric encryption for cloud storage. IEEE Transactions on Dependable and Secure Computing, 2020, 17( 6): 1322– 1332
37	D Sharma , D Jinwala . Simple index based symmetric searchable encryption with result verifiability. Frontiers of Computer Science, 2021, 15( 2): 152805–
38	M Azraoui, K Elkhiyaoui, M Önen, R Molva. Publicly verifiable conjunctive keyword search in outsourced databases. In: Proceedings of 2015 IEEE Conference on Communications and Network Security (CNS). 2015, 619−627
39	S Jiang , X Zhu , L Guo , J Liu . Publicly verifiable Boolean query over outsourced encrypted data. IEEE Transactions on Cloud Computing, 2019, 7( 3): 799– 813
40	W Sun, X Liu, W Lou, Y T Hou, H Li. Catch you if you lie to me: efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data. In: Proceedings of 2015 IEEE Conference on Computer Communications (INFOCOM). 2015, 2110−2118
41	J Benaloh, M de Mare. One-way accumulators: a decentralized alternative to digital signatures. In: Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology. 1993, 274−285
42	P Camacho , A Hevia , M Kiwi , R Opazo . Strong accumulators from collision-resistant hashing. International Journal of Information Security, 2012, 11( 5): 349– 363
43	A Broder , M Mitzenmacher . Network applications of bloom filters: a survey. Internet Mathematics, 2004, 1( 4): 485– 509

[1]

Download

[1]	Bowen ZHAO, Shaohua TANG, Ximeng LIU, Yiming WU. Return just your search: privacy-preserving homoglyph search for arbitrary languages[J]. Front. Comput. Sci., 2022, 16(2): 162801-.
[2]	Abhishek MAJUMDAR, Arpita BISWAS, Atanu MAJUMDER, Sandeep Kumar SOOD, Krishna Lal BAISHNAB. A novel DNA-inspired encryption strategy for concealing cloud storage[J]. Front. Comput. Sci., 2021, 15(3): 153807-.

Viewed

Full text

Abstract

Cited

Shared

Discussed