An efficient conjunctive keyword searchable encryption for cloud-based IoT systems^✩

Abstract

Data privacy leakage has always been a critical concern in cloud-based Internet of Things (IoT) systems. Dynamic Symmetric Searchable Encryption (DSSE) with forward and backward privacy aims to address this issue by enabling updates and retrievals of ciphertext on untrusted cloud server while ensuring data privacy. However, previous research on DSSE mostly focused on single keyword search, which limits its practical application in cloud-based IoT systems. Recently, Patranabis (NDSS 2021) [1] proposed a groundbreaking DSSE scheme for conjunctive keyword search. However, this scheme fails to effectively handle deletion operations in certain circumstances, resulting in inaccurate query results. Additionally, the scheme introduces unnecessary search overhead. To overcome these problems, we present CKSE, an efficient conjunctive keyword DSSE scheme. Our scheme improves the oblivious shared computation protocol used in the scheme of Patranabis, thus enabling a more comprehensive deletion functionality. Furthermore, we introduce a state chain structure to reduce the search overhead. Through security analysis and experimental evaluation, we demonstrate that our CKSE achieves more comprehensive deletion functionality while maintaining comparable search performance and security, compared to the oblivious dynamic cross-tags protocol of Patranabis. The combination of comprehensive functionality, high efficiency, and security makes our CKSE an ideal choice for deployment in cloud-based IoT systems.

Keywords

Symmetric searchable encryption / Conjunctivesearch / Forward and backward privacy / Cloud server

References

[1] S. Patranabis, D. Mukhopadhyay, Forward and backward private conjunctive search-able symmetric encryption, in: 28th Annual Network and Distributed System Secu-rity Symposium (NDSS 2021), The Internet Society, 2021.

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

[3] G.S. Poh, P. Gope, J. Ning, Privhome: privacy-preserving authenticated communi-cation in smart home environment, IEEE Trans. Dependable Secure Comput. 18 (3)(2019) 1095-1107.

[4] Y. Li, B. Cao, M. Peng, L. Zhang, L. Zhang, D. Feng, J. Yu, Direct acyclic graph-based ledger for Internet of things: performance and security analysis, IEEE/ACM Trans. Netw. 28 (4) (2020) 1643-1656.

[5] W. Liu, B. Cao, M. Peng, Web 3 technologies: challenges and opportunities, IEEE Netw. 38 (3) (2024) 187-193.

[6] J. Shu, X. Jia, K. Yang, H. Wang, Privacy-preserving task recommendation services for crowdsourcing, IEEE Trans. Serv.comput. 14 (1) (2018) 235-247.

[7] C. Zhang, L. Zhu, C. Xu, J. Ni, C. Huang, X. Shen, Location privacy-preserving task recommendation with geometric range query in mobile crowdsensing, IEEE Trans. Mob.comput. 21 (12) (2021) 4410-4425.

[8] B. Cao, Z. Wang, L. Zhang, D. Feng, M. Peng, L. Zhang, Z. Han, Blockchain systems, technologies, and applications: a methodology perspective, IEEE Commun. Surv. Tu-tor. 25 (1) (2022) 353-385.

[9] Y. Zhang, J. Katz, C. Papamanthou, All your queries are belong to us: the power of {file-injection} attacks on searchable encryption, in: 25th USENIX Security Sympo-sium (USENIX Security, vol. 16, 2016, pp. 707-720.

[10] C.B. Papamanthou, E. Stefanov, E. Shi,Practical dynamic searchable encryption with small leak ge, in:Proc. Netw. Distrib. Syst. Secur, Symp, 2014, pp. 23-26.

[11] R. Bost, ∑ 𝑜𝜙𝑜𝜉: forward secure searchable encryption,in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016, pp. 1143-1154.

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

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

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

[15] C. Zuo, S.-F. Sun, J.K. Liu, J. Shao, J. Pieprzyk, Dynamic searchable symmetric en-cryption with forward and stronger backward privacy, in: European Symposium on Research in Computer Security, Springer, 2019, pp. 283-303.

[16] I. Demertzis, J.G. Chamani, D. Papadopoulos, C. Papamanthou,Dynamic searchable encryption with small client storage, Cryptology ePrint Archive.

[17] S.-F. Sun, R. Steinfeld, S. Lai, X. Yuan, A. Sakzad, J.K. Liu, S. Nepal, D. Gu,Prac-tical non-interactive searchable encryption with forward and backward privacy, in:Usenix Network and Distributed System Security Symposium 2021, The Internet So-ciety, 2021.

[18] P. Xu, W. Susilo, W. Wang, T. Chen, Q. Wu, K. Liang, H. Jin, ROSE: robust searchable encryption with forward and backward security, IEEE Trans. Inf. Forensics Secur. 17 (2022) 1115-1130.

[19] P. Zhang, Y. Chui, H. Liu, Z. Yang, D. Wu, R. Wang, Efficient and privacy-preserving search over edge-cloud collaborative entity in IoT, IEEE Internet Things J. 10 (4)(2021) 3192-3205.

[20] R. Zhou, X. Zhang, X. Wang, G. Yang, H.-N. Dai, M. Liu, Device-oriented keyword-searchable encryption scheme for cloud-assisted industrial IoT, IEEE Internet Things J. 9 (18) (2021) 17098-17109.

[21] C. Zuo, S.-F. Sun, J.K. Liu, J. Shao, J. Pieprzyk, G. Wei,Forward and backward private dynamic searchable symmetric encryption for conjunctive queries, Cryptology ePrint Archive.

[22] 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: Advances in Cryptology-CRYPTO 2013: 33 rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, Springer, 2013, pp. 353-373.

[23] M. Haus, M. Waqas, A.Y. Ding, Y. Li, S. Tarkoma, J. Ott, Security and privacy in device-to-device (d2d) communication: a review, IEEE Commun. Surv. Tutor. 19 (2)(2017) 1054-1079.

[24] M. Waqas, S. Tu, Z. Halim, S.U. Rehman, G. Abbas, Z.H. Abbas, The role of artificial intelligence and machine learning in wireless networks security: principle, practice and challenges, Artif. Intell. Rev. 55 (7) (2022) 5215-5261.

[25] D.X. Song, D. Wagner, A. Perrig,Practical techniques for searches on encrypted data, in: Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, IEEE, 2000, pp. 44-55.

[26] R. Curtmola, J. Garay, S. Kamara, R. Ostrovsky, Searchable symmetric encryption: improved definitions and efficient constructions, J.comput. Secur. 19 (5) (2011) 895-934.

[27] M. Chase, S. Kamara, Structured encryption and controlled disclosure, in: Advances in Cryptology-ASIACRYPT 2010: 16 th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010., in: Proceedings, vol. 16, Springer, 2010, pp. 577-594.

[28] S. Kamara, C. Papamanthou, T. Roeder,Dynamic searchable symmetric encryption, in:Proceedings of the 2012 ACM Conference on Computer and Communications Security, 2012, pp. 965-976.

[29] S. Liu, J. Yu, Y. Xiao, Z. Wan, S. Wang, B. Yan, BC-SABE: blockchain-aided search-able attribute-based encryption for cloud-IoT, IEEE Internet Things J. 7 (9) (2020) 7851-7867.

[30] J. Yu, S. Liu, M. Xu, H. Guo, F. Zhong, W. Cheng, An efficient revocable and search-able MA-ABE scheme with blockchain assistance for C-IoT, IEEE Internet Things J. 10 (3) (2022) 2754-2766.

[31] H. Yin, W. Zhang, H. Deng, Z. Qin, K. Li, An attribute-based searchable encryption scheme for cloud-assisted IIoT, IEEE Internet Things J. 10 (12) (2023) 11014-11023.

[32] Y.-C. Chang, M. Mitzenmacher, Privacy preserving keyword searches on remote en-crypted data, in: International Conference on Applied Cryptography and Network Security, Springer, 2005, pp. 442-455.

[33] Y. Wei, S. Lv, X. Guo, Z. Liu, Y. Huang, B. Li, FSSE: forward secure searchable en-cryption with keyed-block chains, Inf. Sci. 500 (2019) 113-126.

[34] X. Song, C. Dong, D. Yuan, Q. Xu, M. Zhao, Forward private searchable symmetric encryption with optimized I/O efficiency, IEEE Trans. Dependable Secure Comput. 17 (5) (2018) 912-927.

[35] H. Dou, Z. Dan, P. Xu, W. Wang, S. Xu, T. Chen, H. Jin, Dynamic searchable symmet-ric encryption with strong security and robustness, IEEE Trans. Inf. Forensics Secur., https://doi.org/10.1109/TIFS.2024.3350330.

[36] B. Chen, T. Xiang, D. He, H. Li, K.-K.R. Choo, BPVSE: publicly verifiable searchable encryption for cloud-assisted electronic health records, IEEE Trans. Inf. Forensics Secur. 18 (2023) 3171-3184.

[37] 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 the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018, pp. 745-762.

[38] S. Kamara, T. Moataz, Boolean searchable symmetric encryption with worst-case sub-linear complexity, in: Advances in Cryptology-EUROCRYPT 2017: 36 th Annual International Conference on the Theory and Applications of Cryptographic Tech-niques, Paris, France, April 30-May 4, 2017, Proceedings, Part III 36, Springer, 2017, pp. 94-124.

[39] Z. Wu, K. Li, VBTree: forward secure conjunctive queries over encrypted data for cloud computing, VLDB J. 28 (1) (2019) 25-46.

[40] D. Zeng, A. Badshah, S. Tu, M. Waqas, Z. Han, A security-enhanced ultra-lightweight and anonymous user authentication protocol for telehealthcare information systems, IEEE Trans. Mob.comput. (2025), https://doi.org/10.1109/TMC.2025.3526519.

[41] C. Guo, W. Li, X. Tang, K.-K.R. Choo, Y. Liu, Forward private verifiable dynamic searchable symmetric encryption with efficient conjunctive query, IEEE Trans. De-pendable Secure Comput. 21 (2) (2023) 746-763.

[42] M. Li, C. Jia, R. Du, W. Shao, Forward and backward secure searchable encryp-tion scheme supporting conjunctive queries over bipartite graphs, IEEE Trans. Cloud Comput. 11 (1) (2021) 1091-1102.

[43] D. Yuan, C. Zuo, S. Cui, G. Russello,Result-pattern-hiding conjunctive searchable symmetric encryption with forward and backward privacy, in:Proceedings on Pri-vacy Enhancing Technologies, https://doi.org/10.56553/popets-2023-0040.

[44] R. Li, A.X. Liu, Adaptively secure and fast processing of conjunctive queries over encrypted data, IEEE Trans. Knowl. Data Eng. 34 (4) (2020) 1588-1602.

[45] Y. Li, J. Ning, J. Chen, Secure and practical wildcard searchable encryption system based on inner product, IEEE Trans. Serv.comput. 16 (3) (2022) 2178-2190.

[46] F. Liu, K. Xue, J. Yang, J. Zhang, Z. Huang, J. Li, D.S. Wei, Volume-hiding range searchable symmetric encryption for large-scale datasets, IEEE Trans. Dependable Secure Comput., https://doi.org/10.1109/TDSC.2023.3335304.

[47] M. Xie, X. Yang, H. Hong, G. Wei, Z. Zhang, A novel verifiable Chinese multi-keyword fuzzy rank searchable encryption scheme in cloud environments, Future Gener. Com-put. Syst. 153 (2024) 287-300.

[48] B. Gong, G. Zheng, M. Waqas, S. Tu, S. Chen, Lcdma: lightweight cross-domain mu-tual identity authentication scheme for Internet of things, IEEE Internet Things J. 10 (14) (2023) 12590-12602.

[49] B. Gong, C. Guo, C. Guo, Y. Sun, M. Waqas, S. Chen, Slim: a secure and lightweight multi-authority attribute-based signcryption scheme for iot, IEEE Trans. Inf. Foren-sics Secur. 19 (2023) 1299-1312.

[50] S. Feghhi, D.J. Leith, A web traffic analysis attack using only timing information, IEEE Trans. Inf. Forensics Secur. 11 (8) (2016) 1747-1759.

[51] G. Chen, S. Chen, Y. Xiao, Y. Zhang, Z. Lin, T.H. Lai, Sgxpectre: stealing intel secrets from sgx enclaves via speculative execution, in: 2019 IEEE European Symposium on Security and Privacy (EuroS&P), IEEE, 2019, pp. 142-157.

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

[53] D.J. Bernstein, Curve25519: new Diffie-Hellman speed records,in: Public Key Cryptography-PKC 2006: 9th International Conference on Theory and Practice in Public-Key Cryptography, New York, NY, USA, April 24-26, 2006. Proceedings 9, Springer, 2006, pp. 207-228.

[54] Z. Shang, S. Oya, A. Peter, F. Kerschbaum, Obfuscated access and search patterns in searchable encryption, preprint, arXiv:2102.09651.

[55] M.S. Islam, M. Kuzu, M. Kantarcioglu, Access pattern disclosure on searchable en-cryption: ramification, attack and mitigation, in: Ndss, vol. 20, Citeseer, 2012, p. 12.