Return just your search: privacy-preserving homoglyph search for arbitrary languages

Abstract

Searchable encryption is an effective way to ensure the security and availability of encrypted outsourced cloud data. Among existing solutions, the keyword exact search solution is relatively inflexible, while the fuzzy keyword search solution either has a high index overhead or suffers from the false-positive. Furthermore, no existing fuzzy keyword search solution considers the homoglyph search on encrypted data. In this paper, we propose an efficient privacy-preserving homoglyph search scheme supporting arbitrary languages (POSA, in short). We enhance the performance of the fuzzy keyword search in three aspects. Firstly, we formulate the similarity of homoglyph and propose a privacy-preserving homoglyph search. Secondly, we put forward an index build mechanism without the false-positive, which reduces the storage overhead of the index and is suitable for arbitrary languages. Thirdly, POSA returns just the user’s search, i.e., all returned documents contain the search keyword or its homoglyph. The theoretical analysis and experimental evaluations on real-world datasets demonstrate the effectiveness and efficiency of POSA.

Graphical abstract

Keywords

searchable encryption / cloud storage / fuzzy search / privacy preservation / arbitrary languages

References

[1] Li X , Li J , Yiu S , Gao C , Xiong J . Privacy-preserving edge-assisted image retrieval and classification in IoT. Frontiers of Computer Science, 2019, 13( 5): 1136– 1147

[2] Shen Z , Shu J , Xue W . Preferred search over encrypted data. Frontiers of Computer Science, 2018, 12( 3): 593– 607

[3] Xu P , Wu Q , Wang W , Susilo W , Domingoferrer J , Jin H . Generating searchable public-key ciphertexts with hidden structures for fast keyword search. IEEE Transactions on Information Forensics and Security, 2015, 10( 9): 1993– 2006

[4] Chen B, Wu L, Kumar N, Choo K K R, He D. Lightweight searchable public-key encryption with forward privacy over IIoT outsourced data. IEEE Transactions on Emerging Topics in Computing, 2019, DOI:10.1109/TETC.2019.2737789

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

[6] Li J, Wang Q, Wang C, Cao N, Ren K, Lou W. Fuzzy keyword search over encrypted data in cloud computing. In: Proceedings of IEEE International Conference on Computer Communications. 2010, 1–5

[7] Yang Y, Liu X, Deng R H, Weng J. Flexible wildcard searchable encryption system. IEEE Transactions on Services Computing, 2020, 13(3): 464−477

[8] Woodbridge J, Anderson H S, Ahuja A, Grant D. Detecting homoglyph attacks with a siamese neural network. In: Procedings of IEEE Symposium on Security and Privacy Workshops. 2018, 22–28

[9] Wang C, Ren K, Yu S, Urs K M R. Achieving usable, privacy-assured similarity search over outsourced cloud data. In: Proceedings of IEEE International Conference on Computer Communications. 2012, 451–459

[10] Zhu X, Wang G, Xie D. Fuzzy and semantic search over encrypted data in the cloud. In: Proceedings of International Conference on Security Privacy and Anonymity in Computation Communication and Storage. 2016, 332–341

[11] Awad A , Matthews A , Qiao Y , Lee B . Chaotic searchable encryption for mobile cloud storage. IEEE Transactions on Cloud Computing, 2018, 6( 2): 440– 452

[12] Bringer J, Chabanne H, Kindarji B. Error-tolerant searchable encryption. In: Proceedings of IEEE International Conference on Computer Communications. 2009, 1–6

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

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

[15] Yang Y, Liu X, Deng R H. Multi-user multi-keyword rank search over encrypted data in arbitrary language. IEEE Transactions on Dependable and Secure Computing, 2020, 17(2): 320−334

[16] Yang S , Tang S , Zhang X . Privacy-preserving k nearest neighbor query with authentication on road networks. Journal of Parallel and Distributed Computing, 2019, 134 : 25– 36

[17] Wu Y , Tang S , Zhao B , Peng Z . BPTM: blockchain-based privacy-preserving task matching in crowdsourcing. IEEE Access, 2019, 7 : 45605– 45617

[18] Shu J, Yang K, Jia X, Liu X, Wang C, Deng R H. Proxy-free privacy-preserving task matching with efficient revocation in crowdsourcing. IEEE Transactions on Dependable and Secure Computing, 2021, 18(1): 117−130

[19] Park H A, Kim B H, Lee D H, Chung Y D, Zhan J. Secure similarity search. In: Proceedings of IEEE International Conference on Granular Computing. 2007, 598–598

[20] Kuzu M, Islam M S, Kantarcioglu M. Efficient similarity search over encrypted data. In: Proceedings of IEEE International Conference on Data Engineering. 2012, 1156–1167

[21] Wang J , Yu X , Zhao M . Privacy-preserving ranked multi-keyword fuzzy search on cloud encrypted data supporting range query. Arabian Journal for Science and Engineering, 2015, 40( 8): 2375– 2388

[22] Zhu X, Liu Q, Wang G. Verifiable dynamic fuzzy search over encrypted data in cloud computing. In: Proceedings of International Conference on Algorithms and Architectures for Parallel Processing. 2015, 655–666

[23] Yuan X , Wang X , Wang C , Yu C , Nutanong S . Privacy-preserving similarity joins over encrypted data. IEEE Transactions on Information Forensics and Security, 2017, 12( 11): 2763– 2775

[24] Homann D, Göge C, Wiese L. Dynamic similarity search over encrypted data with low leakage. In: Proceedings of International Workshop on Security and Trust Management. 2017, 19–35

[25] Liu Z, Jia C, Yang J, Yuan K. Format-preserving fuzzy query mechanism. In: Proceedings of IEEE International Conference on Emerging Intelligent Data and Web Technologies. 2013, 220–226

[26] Zhu H, Mei Z, Wu B, Li H, Cui Z. Fuzzy keyword search and access control over ciphertexts in cloud computing. In: Proceedings of Australasian Conference on Information Security and Privacy. 2017, 248–265

[27] Hua Y , Xiao B , Liu X , Feng D . The design and implementations of locality-aware approximate queries in hybrid storage systems. IEEE Transactions on Parallel and Distributed Systems, 2014, 26( 11): 3194– 3207

[28] Yang Y , Yang S , Ke M . Ranked fuzzy keyword search based on simhash over encrypted cloud data. Chinese Journal of Computers, 2017, 40( 2): 431– 444

[29] Raghavendra S , Girish S , Geeta C M , Buyya R , Venugopal K R , Iyengar S S , Patnaik L M . Split keyword fuzzy and synonym search over encrypted cloud data. Multimedia Tools and Applications, 2018, 77( 8): 10135– 10156

[30] Zhou W , Liu L , Jing H , Zhang C , Yao S , Wang S . K-gram based fuzzy keyword search over encrypted cloud computing. Journal of Software Engineering and Applications, 2013, 6( 1): 29– 33

[31] Ahsan M A M, Chowdhury F Z, Sabilah M, Wahab A W B A, Idris M Y I B. An efficient fuzzy keyword matching technique for searching through encrypted cloud data. In: Proceedings of IEEE International Conference on Research and Innovation in Information Systems. 2017, 1–5

[32] Krishna C R, Mittal S A. Privacy preserving synonym based fuzzy multi-keyword ranked search over encrypted cloud data. In: Proceedings of IEEE International Conference on Computing Communication and Automation. 2016, 1187–1194

[33] Shi X J, Hu S P. Fuzzy multi-keyword query on encrypted data in the cloud. In: Proceedings of IEEE Internation Conference on Applied Computing and Information Technology/Computational Science/Intelligence and Applied Informatics/Big Data Cloud Computing Data Science & Engineering. 2016, 419–425

[34] Ding W, Liu Y, Zhang J. Chinese-keyword fuzzy search and extraction over encrypted patent documents. In: Proceedings of IEEE International Joint Conference on Knowledge Discovery Knowledge Engineering and Knowledge Management. 2015, 168–176

[35] Levenshtein V . Binary codes capable of correcting spurious insertions and deletion of ones. Problems of information Transmission, 1965, 1( 1): 8– 17

[36] Ran H, Wang Q, Jiang C. Similar Chinese Characters Dictionary. 1st ed. Beijing: Foreign Language Teaching and Research Press, 2010

[37] Curtmola R , Garay J , Kamara S , Ostrovsky R . Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895– 934

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

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

[40] Wang C , Cao N , Ren K , Lou W . Enabling secure and efficient ranked keyword search over outsourced cloud data. IEEE Transactions on Parallel and Distributed Systems, 2011, 23( 8): 1467– 1479

[41] Lai J, Zhou X, Deng R H, Li Y, Chen K. Expressive search on encrypted data. In: Proceedings of ACM SIGSAC Symposium on Information Computer and Communications Security. 2013, 243–252

[42] Bösch C , Hartel P , Jonker W , Peter A . A survey of provably secure searchable encryption. ACM Computing Surveys, 2015, 47( 2): 1– 51

[43] Ning J , Xu J , Liang K , Zhang F , Chang E C . Passive attacks against searchable encryption. IEEE Transactions on Information Forensics and Security, 2019, 14( 3): 789– 802

[44] Cash D, Grubbs P, Perry J, Ristenpart T. Leakage-abuse attacks against searchable encryption. In: Proceedings of ACM Conference on Computer and Communications Security. 2015, 668–679

[45] Xu P, Tang S, Xu P, Wu Q, Hu H, Susilo W. Practical multi-keyword and boolean search over encrypted e-mail in cloud server. IEEE Transactions on Services Computing, 2019, DOI:10.1109/TSC.2019.2903502

RIGHTS & PERMISSIONS

Higher Education Press