Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage

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.

Graphical abstract

Keywords

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

References

[1] Sun P . Security and privacy protection in cloud computing: discussions and challenges. Journal of Network and Computer Applications, 2020, 160 : 102642–

[2] Liu J K , Liang K , Susilo W , Liu J , Xiang Y . Two-factor data security protection mechanism for cloud storage system. IEEE Transactions on Computers, 2016, 65( 6): 1992– 2004

[3] Bost R. Σoφoς: forward secure searchable encryption. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 1143−1154

[4] Cash D, Jaeger J, Jarecki S, Jutla C, Krawczyk H, Ros M C, Steiner M. 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] Curtmola R , Garay J , Kamara S , Ostrovsky R . Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895– 934

[6] Lai S, Patranabis S, Sakzad A, Liu J K, Mukhopadhyay D, Steinfeld R, Sun S F, Liu D, Zuo C. Result pattern hiding searchable encryption for conjunctive queries. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 745– 762

[7] Zuo C, Sun S F, Liu J K, Shao J, Pieprzyk J. Dynamic searchable symmetric encryption schemes supporting range queries with forward/backward privacy. 2019, arXiv preprint arXiv: 1905.08561

[8] Cash D, Jarecki S, Jutla C, Krawczyk H, Roşu M C, Steiner M. Highly-scalable searchable symmetric encryption with support for Boolean queries. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 353– 373

[9] Sun S F, Liu J K, Sakzad A, Steinfeld R, Yuen T H. 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] Kermanshahi S K , Liu J K , Steinfeld R , Nepal S , Lai S , Loh R , Zuo C . Multi-client cloud-based symmetric searchable encryption. IEEE Transactions on Dependable and Secure Computing, 2021, 18( 5): 2419– 2437

[11] Zuo C, Macindoe J, Yang S, Steinfeld R, Liu J K. Trusted Boolean search on cloud using searchable symmetric encryption. In: Proceedings of 2016 IEEE Trustcom/BigDataSE/ISPA. 2016, 113– 120

[12] Faber S, Jarecki S, Krawczyk H, Nguyen Q, Rosu M, Steiner M. Rich queries on encrypted data: beyond exact matches. In: Proceedings of the 20th European Symposium on Research in Computer Security. 2015, 123– 145

[13] Bost R , Fouque P A , Pointcheval D . Verifiable dynamic symmetric searchable encryption: optimality and forward security. IACR Cryptology ePrint Archive, 2016, 2016 : 62–

[14] Cheng R, Yan J, Guan C, Zhang F, Ren K. 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] Ogata W , Kurosawa K . No-dictionary searchable symmetric encryption. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2019, 102( 1): 114– 124

[17] Soleimanian A , Khazaei S . Publicly verifiable searchable symmetric encryption based on efficient cryptographic components. Designs, Codes and Cryptography, 2019, 87( 1): 123– 147

[18] Zhu J , Li Q , Wang C , Yuan X , Wang Q , Ren K . Enabling generic, verifiable, and secure data search in cloud services. IEEE Transactions on Parallel and Distributed Systems, 2018, 29( 8): 1721– 1735

[19] Wang J, Chen X, Sun S F, Liu J K, Au M H, Zhan Z H. 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] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In: Proceedings of 2000 IEEE Symposium on Security and Privacy. 2000, 44−55

[21] Goh E J . Secure indexes. IACR Cryptology ePrint Archive, 2003, 2003 : 216–

[22] Liu C , Zhu L , Chen J . Efficient searchable symmetric encryption for storing multiple source dynamic social data on cloud. Journal of Network and Computer Applications, 2017, 86 : 3– 14

[23] Gan Q , Wang X , Huang D , Li J , Zhou D , Wang C . Towards multi-client forward private searchable symmetric encryption in cloud computing. IEEE Transactions on Services Computing, 2021, DOI: 10.1109/TSC.2021.3087155,

[24] Miao Y , Liu X , Deng R H , Wu H , Li H , Li J , Wu D . Hybrid keyword-field search with efficient key management for industrial internet of things. IEEE Transactions on Industrial Informatics, 2019, 15( 6): 3206– 3217

[25] Miao Y , Tong Q , Choo K K R , Liu X , Deng R H , Li H . 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] Chai Q, Gong G. 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] Taketani S, Ogata W. 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] Zhang Z, Wang J, Wang Y, Su Y, Chen X. Towards efficient verifiable forward secure searchable symmetric encryption. In: Proceedings of the 24th European Symposium on Research in Computer Security. 2019, 304−321

[30] Yoneyama K, Kimura S. 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] Ge X , Yu J , Zhang H , Hu C , Li Z , Qin Z , Hao R . 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] Miao M , Wang Y , Wang J , Huang X . Verifiable database supporting keyword searches with forward security. Computer Standards & Interfaces, 2020, 77 : 103491–

[33] Miao M , Wang J , Wen S , Ma J . Publicly verifiable database scheme with efficient keyword search. Information Sciences, 2019, 475 : 18– 28

[34] Miao Y , Liu X , Choo K K R , Deng R H , Wu H , Li H . 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] Liu X , Yang G , Mu Y , Deng R H . Multi-user verifiable searchable symmetric encryption for cloud storage. IEEE Transactions on Dependable and Secure Computing, 2020, 17( 6): 1322– 1332

[37] Sharma D , Jinwala D . Simple index based symmetric searchable encryption with result verifiability. Frontiers of Computer Science, 2021, 15( 2): 152805–

[38] Azraoui M, Elkhiyaoui K, Önen M, Molva R. Publicly verifiable conjunctive keyword search in outsourced databases. In: Proceedings of 2015 IEEE Conference on Communications and Network Security (CNS). 2015, 619−627

[39] Jiang S , Zhu X , Guo L , Liu J . Publicly verifiable Boolean query over outsourced encrypted data. IEEE Transactions on Cloud Computing, 2019, 7( 3): 799– 813

[40] Sun W, Liu X, Lou W, Hou Y T, Li H. 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] Benaloh J, de Mare M. 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] Camacho P , Hevia A , Kiwi M , Opazo R . Strong accumulators from collision-resistant hashing. International Journal of Information Security, 2012, 11( 5): 349– 363

[43] Broder A , Mitzenmacher M . Network applications of bloom filters: a survey. Internet Mathematics, 2004, 1( 4): 485– 509

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 61932010 and 62072357), and the Zhuhai Top Discipline-Information Security. This work was also supported by the China Scholarship Council (CSC) and the Australian Research Council (ARC).

RIGHTS & PERMISSIONS

2022 Higher Education Press