ROSA: robust non-interactive search in dynamic searchable encryption

Abstract

Dynamic Searchable Symmetric Encryption (DSSE) serves as an important cryptographic tool in cloud-based applications, with which a client can delegate secure keyword searches to a semi-honest cloud server over a constantly updated encrypted database. A practical DSSE scheme must achieve three fundamental properties: security, efficiency, and robustness. Forward and backward security is a popular notion that significantly restricts the information leakage of DSSE. Search performance is one of the most important efficiency metrics to measure whether a DSSE scheme can be applied to large-scale databases. Robustness plays a crucial role in correctly processing irrational update queries in DSSE, such as inserting duplicate or removing non-existent entries. In this work, we extend forward and Type-II-backward security definitions to incorporate robustness and present \mathtt{R}\mathtt{O}\mathtt{S}\mathtt{A}, the first DSSE scheme that simultaneously achieves forward and Type-II-backward security, non-interactive search, and robustness. \mathtt{R}\mathtt{O}\mathtt{S}\mathtt{A} achieves the same search complexity as \mathtt{A}\mathtt{u}\mathtt{r}\mathtt{a} (NDSS’21), the only DSSE scheme with equivalent security as \mathtt{R}\mathtt{O}\mathtt{S}\mathtt{A} and non-interactive search. But \mathtt{A}\mathtt{u}\mathtt{r}\mathtt{a} is not robust. Finally, we empirically evaluate \mathtt{R}\mathtt{O}\mathtt{S}\mathtt{A} using real-world data, comparing it against existing DSSE schemes that offer non-interactive search, forward and Type-II-backward security, or robustness. Experimental outcomes demonstrate that \mathtt{R}\mathtt{O}\mathtt{S}\mathtt{A} achieves competitive or better search efficiency than previous works, especially when the network connection is unstable and slow.

Graphical abstract

Keywords

dynamic searchable symmetric encryption / forward/backward security / robustness / non-interactive search

References

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

[2] 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, 1−15

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

[4] Chamani J G, 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

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

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

[7] He K, Chen J, Zhou Q, Du R, Xiang Y . Secure dynamic searchable symmetric encryption with constant client storage cost. IEEE Transactions on Information Forensics and Security, 2021, 16: 1538–1549

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

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

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

[11] Hoang T, Yavuz A A, Guajardo J . A secure searchable encryption framework for privacy-critical cloud storage services. IEEE Transactions on Services Computing, 2021, 14( 6): 1675–1689

[12] Zheng Y, Xu P, Wang M, Xu W, Wang W, Chen T, Jin H . Themis: robust and light-client dynamic searchable symmetric encryption. IEEE Transactions on Information Forensics and Security, 2024, 19: 8802–8816

[13] Xu P, Susilo W, Wang W, Chen T, Wu Q, Liang K, Jin H . ROSE: robust searchable encryption with forward and backward security. IEEE Transactions on Information Forensics and Security, 2022, 17: 1115–1130

[14] Wang X S, Nayak K, Liu C, Chan T H H, Shi E, Stefanov E, Huang Y. Oblivious data structures. In: Proceedings of 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014, 215−226

[15] Roche D S, Aviv A, Choi S G. A practical oblivious map data structure with secure deletion and history independence. In: Proceedings of 2016 IEEE Symposium on Security and Privacy. 2016, 178−197

[16] Bird S, Klein E, Loper E. Natural Language Processing with Python. Sebastopol: O’Reilly, 2009

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

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

[19] Hahn F, Kerschbaum F. Searchable encryption with secure and efficient updates. In: Proceedings of 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014, 310−320

[20] 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, 1−16

[21] Xu P, Liang S, Wang W, Susilo W, Wu Q, Jin H. Dynamic searchable symmetric encryption with physical deletion and small leakage. In: Proceedings of the 22nd Australasian Conference on Information Security and Privacy. 2017, 207−226

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

[23] Wang W, Liu D, Xu P, Yang L T, Liang K . Keyword search shareable encryption for fast and secure data replication. IEEE Transactions on Information Forensics and Security, 2023, 18: 5537–5552

[24] Li F, Ma J, Miao Y, Jiang Q, Liu X, Choo K K R . Verifiable and dynamic multi-keyword search over encrypted cloud data using bitmap. IEEE Transactions on Cloud Computing, 2023, 11( 1): 336–348

[25] Tong Q, Miao Y, Liu X, Choo K K R, Deng R H, Li H . VPSL: verifiable privacy-preserving data search for cloud-assisted internet of things. IEEE Transactions on Cloud Computing, 2022, 10( 4): 2964–2976

[26] Wang Y, Papadopoulos D . Multi-user collusion-resistant searchable encryption for cloud storage. IEEE Transactions on Cloud Computing, 2023, 11( 3): 2993–3008

[27] Wu A, Yang A, Luo W, Wen J . Enabling traceable and verifiable multi-user forward secure searchable encryption in hybrid cloud. IEEE Transactions on Cloud Computing, 2023, 11( 2): 1886–1898

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

[29] Bost R. ∑oϕoς: Forward secure searchable encryption. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 1143−1154

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

[31] Wei Y, Lv S, Guo X, Liu Z, Huang Y, Li B . FSSE: forward secure searchable encryption with keyed-block chains. Information Sciences, 2019, 500: 113–126

[32] Etemad M, Küpçü A, Papamanthou C, Evans D . Efficient dynamic searchable encryption with forward privacy. Proceedings on Privacy Enhancing Technologies, 2018, 2018( 1): 5–20

[33] Garg S, Mohassel P, Papamanthou C. TWORAM: efficient oblivious RAM in two rounds with applications to searchable encryption. In: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology. 2016, 563−592

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

[35] Huang Y, Lv S, Liu Z, Song X, Li J, Yuan Y, Dong C . Cetus: an efficient symmetric searchable encryption against file-injection attack with SGX. Science China Information Sciences, 2021, 64( 8): 182314

[36] Zuo C, Sun S F, Liu J K, Shao J, Pieprzyk J. Dynamic searchable symmetric encryption with forward and stronger backward privacy. In: Proceedings of the 24th European Symposium on Research in Computer Security. 2019, 283−303

[37] Li J, Huang Y, Wei Y, Lv S, Liu Z, Dong C, Lou W . Searchable symmetric encryption with forward search privacy. IEEE Transactions on Dependable and Secure Computing, 2021, 18( 1): 460–474

[38] Zheng Y, Lu R, Shao J, Yin F, Zhu H . Achieving practical symmetric searchable encryption with search pattern privacy over cloud. IEEE Transactions on Services Computing, 2022, 15( 3): 1358–1370

[39] Dou H, Dan Z, Xu P, Wang W, Xu S, Chen T, Jin H . Dynamic searchable symmetric encryption with strong security and robustness. IEEE Transactions on Information Forensics and Security, 2024, 19: 2370–2384

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

[41] Cui J, Sun Y, Xu Y, Tian M, Zhong H . Forward and backward secure searchable encryption with multi-keyword search and result verification. Science China Information Sciences, 2022, 65( 5): 159102

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

[43] Wang J, Chow S S M . Forward and backward-secure range-searchable symmetric encryption. Proceedings on Privacy Enhancing Technologies, 2022, 2022( 1): 28–48

[44] Yuan D, Zuo C, Cui S, Russello G . Result-pattern-hiding conjunctive searchable symmetric encryption with forward and backward privacy. Proceedings on Privacy Enhancing Technologies, 2023, 2023( 2): 40–58

[45] Li M, Jia C, Du R, Shao W . Forward and backward secure searchable encryption scheme supporting conjunctive queries over bipartite graphs. IEEE Transactions on Cloud Computing, 2023, 11( 1): 1091–1102

[46] Zhang H, Xu C, Lu R, Zhu L, Zhang C, Guan Y . Non-interactive multi-client searchable symmetric encryption with small client storage. IEEE Transactions on Services Computing, 2023, 16( 6): 3972–3985

[47] Blackstone L, Kamara S, Moataz T. Revisiting leakage abuse attacks. In: Proceedings of the 27th Annual Network and Distributed System Security Symposium. 2020, 1−18

[48] Oya S, Kerschbaum F. Hiding the access pattern is not enough: exploiting search pattern leakage in searchable encryption. In: Proceedings of the 30th USENIX Security Symposium. 2021, 127−142

[49] Damie M, Hahn F, Peter A. A highly accurate query-recovery attack against searchable encryption using non-indexed documents. In: Proceedings of the 30th USENIX Security Symposium. 2021, 143−160

[50] Ning J, Huang X, Poh G S, Yuan J, Li Y, Weng J, Deng R H. LEAP: leakage-abuse attack on efficiently deployable, efficiently searchable encryption with partially known dataset. In: Proceedings of 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021, 2307−2320

[51] Kornaropoulos E M, Papamanthou C, Tamassia R. Response-hiding encrypted ranges: revisiting security via parametrized leakage-abuse attacks. In: Proceedings of 2021 IEEE Symposium on Security and Privacy. 2021, 1502−1519

[52] Zhang X, Wang W, Xu P, Yang L T, Liang K. High recovery with fewer injections: practical binary volumetric injection attacks against dynamic searchable encryption. In: Proceedings of the 32nd USENIX Security Symposium. 2023, 5953−5970

[53] Nie H, Wang W, Xu P, Zhang X, Yang L T, Liang K. Query recovery from easy to hard: jigsaw attack against SSE. In: Proceedings of the 33rd USENIX Security Symposium. 2024, 2599−2616

[54] Kornaropoulos E M, Moyer N, Papamanthou C, Psomas A. Leakage inversion: towards quantifying privacy in searchable encryption. In: Proceedings of 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022, 1829−1842

[55] Amjad G, Patel S, Persiano G, Yeo K, Yung M . Dynamic volume-hiding encrypted multi-maps with applications to searchable encryption. Proceedings on Privacy Enhancing Technologies, 2023, 2023( 1): 417–436

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

[57] George M, Kamara S, Moataz T. Structured encryption and dynamic leakage suppression. In: Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2021, 370−396

[58] Li S, Jing X, Wang Y, Xu X, Zhang Z, Wang J . Practical searchable encryption scheme against response identity attacks. Information Sciences, 2025, 706: 121975

[59] Dauterman E, Feng E, Luo E, Popa R A, Stoica I. DORY: an encrypted search system with distributed trust. In: Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation. 2020, 1101−1119

[60] Hoang T, Yavuz A A, Durak F B, Guajardo J . A multi-server oblivious dynamic searchable encryption framework. Journal of Computer Security, 2019, 27( 6): 649–676

[61] Hoang T, Yavuz A A, Durak F B, Guajardo J. Oblivious dynamic searchable encryption on distributed cloud systems. In: Proceedings of the 32nd Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy XXXII. 2018, 113−130

[62] Amjad G, Kamara S, Moataz T. Forward and backward private searchable encryption with SGX. In: Proceedings of the 12th European Workshop on Systems Security. 2019, 4

[63] Hoang T, Behnia R, Jang Y, Yavuz A A. MOSE: practical multi-user oblivious storage via secure enclaves. In: Proceedings of the 10th ACM Conference on Data and Application Security and Privacy. 2020, 17−28

[64] Hoang T, Ozmen M O, Jang Y, Yavuz A A . Hardware-supported ORAM in effect: Practical oblivious search and update on very large dataset. Proceedings on Privacy Enhancing Technologies, 2019, 2019( 1): 172–191

[65] Vo V, Lai S, Yuan X, Nepal S, Liu J K. Towards efficient and strong backward private searchable encryption with secure enclaves. In: Proceedings of the 19th International Conference on Applied Cryptography and Network Security. 2021, 50−75

RIGHTS & PERMISSIONS

Higher Education Press