MMKFB: multi-client and multi-keyword searchable symmetric encryption with forward and backward privacy

Abstract

Data outsourcing has become an industry trend with the popularity of cloud computing. How to search data securely and efficiently has received unprecedented attention. Dynamic Searchable Symmetric Encryption (DSSE) is an effective method to solve this problem, which supports file updates and keyword-based searches over encrypted data. Unfortunately, most existing DSSE schemes have privacy leakages during the addition and deletion phases, thus proposing the concepts of forward and backward privacy. At present, some secure DSSE schemes with forward and backward privacy have been proposed, but most of these DSSE schemes only achieve single-keyword query in the single-client setting, which seriously limits the application in practice. To solve this problem, we propose a multi-client and multi-keyword searchable symmetric encryption scheme with forward and backward privacy (MMKFB). Our scheme focuses on the multi-keyword threshold queries in the multi-client setting, which is a new pattern of multi-keyword search realized with the help of additive homomorphism. And performance analysis and experiments demonstrate that our scheme is more practical for use in small and medium size databases. Especially when a large number of files are updated at once, our scheme has advantages over some existing DSSE schemes in terms of computational efficiency and client storage overhead.

Graphical abstract

Keywords

searchable symmetric encryption / multi-client / multi-keyword search / forward security / backward security

References

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

[2] Cash D, Jaeger J, Jarecki S, Jutla C, Krawczyk H, Roşu M C, Steiner M. Dynamic searchable encryption in very-large databases: data structures and implementation. In: Proceedings of 2014 Network and Distributed System Security Symposium. 2014

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

[4] Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption. In: Proceedings of the 17th International Conference on Financial Cryptography and Data Security. 2013, 258−274

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

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

[7] Papamanthou C, Stefanov E, Shi E. Practical dynamic searchable encryption with small leakage. In: Proceedings of Network and Distributed System Security Symposium. 2014, 23–26

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

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

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

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

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

[13] Chen L, Li J, Li J . Toward forward and backward private dynamic searchable symmetric encryption supporting data deduplication and conjunctive queries. IEEE Internet of Things Journal, 2023, 10( 19): 17408–17423

[14] Jiang Q, Chang E C, Qi Y, Qi S, Wu P, Wang J . Rphx: result pattern hiding conjunctive query over private compressed index using Intel SGX. IEEE Transactions on Information Forensics and Security, 2022, 17: 1053–1068

[15] Patranabis S, Mukhopadhyay D. Forward and backward private conjunctive searchable symmetric encryption. In: Proceedings of 2021 Network and Distributed System Security Symposium. 2021

[16] Tahir S, Steponkus L, Ruj S, Rajarajan M, Sajjad A . A parallelized disjunctive query based searchable encryption scheme for big data. Future Generation Computer Systems, 2020, 109: 583–592

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

[18] Goh E J. Secure indexes. Cryptology ePrint Archive, Paper 2003/216, 2003

[19] Bloom B H . Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13( 7): 422–426

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

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

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

[23] Li J, Wang Q, Wang C, Cao N, Ren K, Lou W. Fuzzy keyword search over encrypted data in cloud computing. In: Proceedings of 2010 Proceedings IEEE INFOCOM. 2010, 1−5

[24] Wang B, Yu S, Lou W, Hou Y T. Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud. In: Proceedings of the IEEE INFOCOM 2014-IEEE Conference on Computer Communications. 2014, 2112−2120

[25] Fu Z, Wu X, Guan C, Sun X, Ren K . Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. IEEE Transactions on Information Forensics and Security, 2016, 11( 12): 2706–2716

[26] Popa R A, Redfield C M S, Zeldovich N, Balakrishnan H. CryptDB: protecting confidentiality with encrypted query processing. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. 2011, 85−100

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

[28] Hu S, Cai C, Wang Q, Wang C, Luo X, Ren K. Searching an encrypted cloud meets blockchain: a decentralized, reliable and fair realization. In: Proceedings of the IEEE INFOCOM 2018-IEEE Conference on Computer Communications. 2018, 792−800

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

[30] Goldreich O, Ostrovsky R . Software protection and simulation on oblivious RAMs. Journal of the ACM, 1996, 43( 3): 431–473

[31] Stefanov E, Van Dijk M, Shi E, Chan T H H, Fletcher C, Ren L, Yu X, Devadas S . Path ORAM: an extremely simple oblivious RAM protocol. Journal of the ACM, 2018, 65( 4): 18

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

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

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

[35] Najafi A, Javadi H H S, Bayat M . Efficient and dynamic verifiable multi-keyword searchable symmetric encryption with full security. Multimedia Tools and Applications, 2021, 80( 17): 26049–26068

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

[37] Wang Q, Guo Y, Huang H, Jia X. Multi-user forward secure dynamic searchable symmetric encryption. In: Proceedings of the 12th International Conference on Network and System Security. 2018, 125−140

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

[39] Shamir A . How to share a secret. Communications of the ACM, 1979, 22( 11): 612–613

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

RIGHTS & PERMISSIONS

Higher Education Press