Less leakage and more precise: Efficient wildcard keyword search over encrypted data

Abstract

Wildcard searchable encryption allows the server to efficiently perform wildcard-based keyword searches over encrypted data while maintaining data privacy. A promising solution to achieve wildcard SSE is to extract the characteristics of the queried keyword and check the existence based on a membership test structure. However, existing schemes have false positives of character order, that is, the server cannot identify the order between the first and the last wildcard character. Besides, the schemes also suffer from characteristic matching pattern leakage due to the one-by-one membership testing. In this paper, we present the first efficient wildcard SSE scheme to eliminate the false positives of character order and characteristic matching pattern leakage. To this end, we design a novel characteristic extraction technique that enables the client to exact the characteristics of the queried keyword maintaining the order between the first and the last wildcard character. Then, we utilize the primitive of Symmetric Subset Predicate Encryption, which supports checking if one set is a subset of another in one shot to reduce the characteristic matching pattern leakage. Finally, by performing a formal security analysis and implementing the scheme on a real-world database, we demonstrate that the desired security properties are achieved with high performance.

Keywords

Symmetric searchable encryption / Wildcardsearch / Symmetric subset predicate encryption

CRediT authorship contribution statement

Yunling Wang: Project administration. Chenyang Gao: Formal analysis. Yifei Huang: Data curation. Lei Fu: Data curation. Yong Yu: Project administration.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

This work is supported by the National Cryptologic Science Fund of China (2025NCSF02025), National Natural Science Foundation of China (U24B20149, 62272385, U23A20302, 62311540156 and 62102313), the Key Research and Development Program of Shaanxi (2024GX-ZDCYL-01-09, 2022KWZ-01), and Major Program of Shandong Provincial Natural Science Founda- tion for the Fundamental Research (ZR2022ZD03).

References

[1] D.X. Song, D.A. Wagner, A. Perrig,Practical techniques for searches on encrypted data, in: 2000 IEEE Symposium on Security and Privacy, Berkeley, California, USA, May 14-17, 2000, IEEE Computer Society, 2000, pp. 44-55.

[2] G. Amjad, S. Kamara, T. Moataz, Injection-secure structured and searchable symmetric encryption, in: Advancesin Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security,in: LNCS, vol. 14443, Springer, 2023, pp. 232-262.

[3] Z. Gui, K.G. Paterson, S. Patranabis,Rethinking searchable symmetric encryption, in: 44th IEEE Symposium on Security and Privacy, SP 2023, IEEE, 2023, pp. 1401-1418.

[4] S. Kamara, A. Kati, T. Moataz, J. DeMaria, A. Park, A. Treiber, MAPLE: Markov process leakage attacks on encrypted search, Proc. Priv. Enhancing Technol. 2024 (1) (2024) 430-446.

[5] J. Wang, S.-F. Sun, T. Li, S. Qi, X. Chen, Practical volume-hiding encrypted multi-maps with optimal overhead and beyond, in:Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, pp. 2825-2839.

[6] K. Du, J. Wang, J. Wu, Y. Wang, Scalable equi-join queries over encrypted database, in:Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security, 2024, pp. 4002-4016.

[7] X. Zhang, W. Wang, P. Xu, L.T. Yang, K. Liang, High recovery with fewer injections: Practical binary volumetric injection attacks against dynamic searchable encryption,in:32nd USENIX Security Symposium, USENIX Security 2023, USENIX Association, 2023, pp. 5953-5970.

[8] X. Zhang, D. Mu, J. Zhao, Attribute-based keyword search encryption for power data protection, High-Confidence Comput. 3 (2) (2023) 100115.

[9] T. Suga, T. Nishide, K. Sakurai, Secure keyword search using bloom filter with specified character positions, in:Provable Security - 6th International Conference, ProvSec 2012, Chengdu, China, September 26-28, 2012. Proceedings,in:Lecture Notes in Computer Science, vol. 7496, Springer, 2012, pp. 235-252.

[10] B.H. Bloom, Space/time trade-offs in hash coding with allowable errors, Commun. ACM 13 (7) (1970) 422-426.

[11] C. Hu, L. Han, Efficient wildcard search over encrypted data, Int. J. Inf. Secur. 15 (2016) 539-547.

[12] J. Wu, K. Du, J. Wang, S.-F. Sun, Y. Wang, Y. Li, W. Tian, Y. Wang, Compressed cookies: Practical wildcard symmetric searchable encryption with optimized storage, in: ProvSec 2024, 2024.

[13] B. Fan, D.G. Andersen, M. Kaminsky, M. Mitzenmacher, Cuckoo filter: Practically better than bloom,in:Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT 2014, ACM, 2014, pp. 75-88.

[14] L. Blackstone, S. Kamara, T. Moataz, Revisiting leakage abuse attacks, in:27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23-26, 2020, The Internet Society, 2020.

[15] S. Sun, R. Steinfeld, S. Lai, X. Yuan, A. Sakzad, J.K. Liu, S. Nepal, D. Gu, Practical non-interactive searchable encryption with forward and backward privacy, in:28th Annual Network and Distributed System Security Symposium, NDSS 2021, The Internet Society, 2021.

[16] S. Sun, C. Zuo, J.K. Liu, A. Sakzad, R. Steinfeld, T.H. Yuen, X. Yuan, D. Gu, Non-interactive multi-client searchable encryption: Realization and implementation, IEEE Trans. Dependable Secur. Comput. 19 (1) (2022) 452-467.

[17] X. Jiang, L. Li, Efficient secure and verifiable KNN set similarity search over outsourced clouds, High-Confidence Comput. 3 (1) (2023) 100100.

[18] R. Guo, B. Qin, Y. Wu, H. Chen, C. Li, Search geometric ranges efficiently as keywords over encrypted spatial data, High-Confidence Comput. 2 (2) (2022) 100058.

[19] S. Sedghi, P. Van Liesdonk, S. Nikova, P. Hartel, W. Jonker, Searching keywords with wildcards on encrypted data, in:Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010. Proceedings 7, Springer, 2010, pp. 138-153.

[20] C. Bösch, R. Brinkman, P. Hartel, W. Jonker, Conjunctive wildcard search over encrypted data, in:Secure Data Management: 8th VLDB Workshop, SDM 2011, Seattle, WA, USA, September 2, 2011, Proceedings 8, Springer, 2011, pp. 114-127.

[21] F. Zhao, T. Nishide,Searchable symmetric encryption supporting queries with multiple-character wildcards, in:Network and System Security - 10th International Conference, NSS 2016, Taipei, Taiwan, September 28-30, 2016, Proceedings,in:Lecture Notes in Computer Science, vol. 9955, Springer, 2016, pp. 266-282.

[22] X. Zhang, B. Zhao, J. Qin, W. Hou, Y. Su, H. Yang, Practical wildcard searchable encryption with tree-based index, Int. J. Intell. Syst. 36 (12) (2021) 7475-7499.

[23] 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.

[24] Q. Wang, D. Hu, M. Li, G. Yang, Secure and flexible wildcard queries, IEEE Trans. Inf. Forensics Secur. (2024).

[25] Y. Wang, S.F. Sun, J. Wang, X. Chen, J.K. Liu, D. Gu, Practical non-interactive encrypted conjunctive search with leakage suppression, in:Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security, 2024, pp. 2825-2839.