Multi-source multi-client searchable symmetric encryption with post-compromise security

Abstract

As multi-source data sharing becomes increasingly prevalent in the digital economy, multi-source multi-client dynamic searchable symmetric encryption (MM-DSSE) has received significant attention. However, the complex key management of MM-DSSE exacerbates the cascading effect of key compromise risks. Existing MM-DSSE schemes only satisfy forward privacy and rely on the ideal “key non-compromised” assumption. We study the key compromise threat in the MM-DSSE and formally define the post-compromise security for MM-DSSE with respect to leakage functions. We introduce a framework for MM-DSSE that supports non-interactive key updates for data sources and clients, named Mosaic. Mosaic ensures data security even in the event of key compromise at any client, data source, or management center. Additionally, we construct an instance Mosaic_R based on Mosaic that supports range search. Both Mosaic and Mosaic_R satisfy forward and type-II backward privacy. We conduct comprehensive experimental evaluations using real-world datasets. The results show that Mosaic and Mosaic_R ensure strong security and competitive performance. Compared with the state-of-the-art single-user DSSE scheme with post-compromise security Bamboo, Mosaic achieves a 79.21% improvement in total search efficiency. The index storage overhead of Mosaic_R is reduced by 49.98% compared with the range search scheme (RS)².

Graphical abstract

Keywords

multi source / multi client / dynamic searchable symmetric encryption / key compromise / forward and backward privacy

References

[1] Song D X, Wagner D A, Perrig A. Practical techniques for searches on encrypted data. In: Proceedings of IEEE Symposium on Security and Privacy. S&P 2000. 2000, 44–55

[2] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: Proceedings of ACM Conference on Computer and Communications Security. 2012, 965–976

[3] Zhang Y, Katz J, Papamanthou C. All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: Proceedings of the 25th USENIX Conference on Security Symposium. 2016, 707–720

[4] Chang Y C, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data. In: Proceedings of the 3rd international conference on Applied Cryptography and Network Security. 2005, 442–455

[5] Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage. In: Proceedings of the 21st Annual Network and Distributed System Security Symposium. 2014, 1143–1154

[6] Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1465–1482

[7] Chamani J G, Papadopoulos D, Karbasforushan M, Demertzis I. Dynamic searchable encryption with optimal search in the presence of deletions. In: Proceedings of the 31st USENIX Security Symposium. 2022, 2425–2442

[8] Sun S F, Yuan X, Liu J K, Steinfeld R, Sakzad A, Vo V, Nepal S. Practical backward-secure searchable encryption from symmetric puncturable encryption. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 763–780

[9] Chen T, Xu P, Wang W, Zheng Y, Susilo W, Jin H. Bestie: very practical searchable encryption with forward and backward security. In: Proceedings of the 26th European Symposium on Research in Computer Security. 2021, 3–23

[10] Zhao C, Du R, He K, Chen J, Li J, Liu X, Ning J . Efficient verifiable dynamic searchable symmetric encryption with forward and backward security. IEEE Internet of Things Journal, 2025, 12( 3): 2633–2645

[11] Research A M. Cloud storage market size, share, competitive landscape and trend analysis report, 2025. Accessed: Apr. 5, 2025

[12] Mei L, Xu C, Xu L, Yuan X, Liu J K . Practical multi-source multi-client searchable encryption with forward privacy: refined security notion and new constructions. IEEE Transactions on Dependable and Secure Computing, 2024, 21( 1): 63–77

[13] Luis Corrons. Android app signing keys leaked and used to sign malware. See blog.avast.com/android-app-signing-keys-leaked?utm_source=chatgpt.com website, 2025

[14] Muncaster P. Stolen cloud API key to blame for Imperva breach. See infosecurity-magazine.com/news/stolen-cloud-api-key-to-blame-for/, 2025

[15] Chen T, Xu P, Picek S, Luo B, Susilo W, Jin H, Liang K. The power of bamboo: on the post-compromise security for searchable symmetric encryption. In: Proceedings of the 30th Annual Network and Distributed System Security Symposium. 2023, 1–18

[16] Wang X, Zhang K, Gong J, Sun S F, Ning J . Updatable searchable symmetric encryption: definitions and constructions. Theoretical Computer Science, 2024, 983: 114304

[17] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006, 79–88

[18] 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 European Symposium on Research in Computer Security. 2016, 154–172

[19] 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

[20] Wu P, Shen J, Cao Z, Dong X . MMKFB: multi-client and multi-keyword searchable symmetric encryption with forward and backward privacy. Frontiers of Computer Science, 2025, 19( 3): 193804

[21] Zhao C, Du R, Chen J, He K, Xu L, Li J. Practical multiuser dynamic searchable symmetric encryption with collusion resistance. IEEE Transactions on Reliability, 2025: 1−14

[22] Liang J, Qin Z, Xiao S, Zhang J, Yin H, Li K . Privacy-preserving range query over multi-source electronic health records in public clouds. Journal of Parallel and Distributed Computing, 2020, 135: 127–139

[23] Zhang W, Lin Y, Xiao S, Wu J, Zhou S . Privacy preserving ranked multi-keyword search for multiple data owners in cloud computing. IEEE Transactions on Computers, 2016, 65( 5): 1566–1577

[24] Wang J, Chow S S M. Omnes pro uno: practical multi-writer encrypted database. In: Proceedings of the 31st USENIX Security Symposium. 2022, 2371–2388

[25] Wang J, Chow S S M. Unus pro omnibus: multi-client searchable encryption via access control. In: Proceedings of Network and Distributed System Security Symposium. 2024, 1–18

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

[27] Kim K S, Kim M, Lee D, Park J H, Kim W H. Forward secure dynamic searchable symmetric encryption with efficient updates. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1449–1463

[28] Etemad M, Küpçü A, Papamanthou C, Evans D. Efficient dynamic searchable encryption with forward privacy. In: Proceedings of the 17th Privacy Enhancing Technologies Symposium. 2017, 5-10

[29] Song X, Dong C, Yuan D, Xu Q, Zhao M . Forward private searchable symmetric encryption with optimized I/O efficiency. IEEE Transactions on Dependable and Secure Computing, 2020, 17( 5): 912–927

[30] Demertzis I, Chamani J G, Papadopoulos D, Papamanthou C. Dynamic searchable encryption with small client storage. In: Proceedings of Network and Distributed System Security Symposium. 2020, 1–18

[31] Sun S F, Steinfeld R, Lai S, Yuan X, Sakzad A, Liu J K, Nepal S, Gu D. Practical non-interactive searchable encryption with forward and backward privacy. In: Proceedings of Network and Distributed System Security Symposium. 2021, 1–18

[32] Ghareh Chamani J, Papadopoulos D, Papamanthou C, Jalili R. New constructions for forward and backward private symmetric searchable encryption. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 1038–1055

[33] 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

[34] 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

[35] Wang B, Fan X . Search ranges efficiently and compatibly as keywords over encrypted data. IEEE Transactions on Dependable and Secure Computing, 2018, 15( 6): 1027–1040

[36] Liu F, Xue K, Yang J, Zhang J, Huang Z, Li J, Wei D S L . Volume-hiding range searchable symmetric encryption for large-scale datasets. IEEE Transactions on Dependable and Secure Computing, 2024, 21( 4): 3597–3609

[37] Li J, Ji L, Zhang Y, Lu Y, Ning J . Response-hiding and volume-hiding verifiable searchable encryption with conjunctive keyword search. IEEE Transactions on Computers, 2025, 74( 2): 455–467

[38] Ji L, Li J, Zhang Y, Lu Y . Verifiable searchable symmetric encryption over additive homomorphism. IEEE Transactions on Information Forensics and Security, 2025, 20: 1320–1332

[39] Zuo C, Sun S F, Liu J K, Shao J, Pieprzyk J. Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security. In: Proceedings of the 23rd European Symposium on Research in Computer Security. 2018, 228–246

[40] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques. 1999, 223–238

[41] Zuo C, Sun S F, Liu J K, Shao J, Pieprzyk J, Xu L . Forward and backward private DSSE for range queries. IEEE Transactions on Dependable and Secure Computing, 2022, 19( 1): 328–338

[42] Wang J, Chow S S M. Forward and backward-secure range-searchable symmetric encryption. In: Proceedings of the 22nd Privacy Enhancing Technologies Symposium. 2022, 28-48

[43] Yang X, Li K, Qi S, Zhao H . Practical volume-hiding range searchable symmetric encryption using trusted execution. Future Generation Computer Systems, 2026, 174: 107930

[44] Zhang H, Zheng Y, Xu C, Zhu L, Wang J . Revocable DSSE in healthcare systems with range query support. IEEE Transactions on Big Data, 2025, 11( 5): 2764–2778

[45] Boneh D, Waters B. Constrained pseudorandom functions and their applications. In: Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information. 2013, 280–300

[46] Porter M F . An algorithm for suffix stripping. Program, 1980, 14( 3): 130–137

RIGHTS & PERMISSIONS

Higher Education Press