An efficient multi-user multi-keyword fuzzy search scheme over encrypted cloud storage

doi:10.52396/JUST-2021-0071

Abstract

Abstract: As more and more enterprises and individuals choose to outsource their encrypted private data to the cloud, Searchable Encryption (SE), which solves the issue of keyword-searching over encrypted data, is becoming much more important. To overcome typos and semantic diversity existing in query requests, fuzzy search is introduced to achieve a misspelling-tolerate search-supported encryption scheme. However, current schemes of fuzzy search over encrypted data not only bring in high computing and communication overhead in multi-user scenarios but also are unable to cover all kinds of error types under the premise of an effective accuracy. In this paper, we thus propose a multi-user multi-keyword fuzzy searchable encryption scheme. Specifically, we introduce the permuterm index to support multi-keyword wildcard search which can solve more kinds of misspelling with a higher degree of correctness. Moreover, by letting the cloud server re-encrypt indexes user encrypt, our scheme supports unshared-key multi-user fuzzy search, reducing users' computing overhead effectively and improving the level of privacy-preserving. The results of experiments demonstrate that, compared with existing schemes, our scheme not only has a better accuracy rate, but also supports more varieties of misspelling keyword search with acceptable computational overhead.

Key words: encrypted cloud storage, proxy re-encryption, privacy preservation, searchable encryption

CLC Number:

TU459

LING Huaze, XUE Kaiping, David S.L. WEI, LI Ruidong. An efficient multi-user multi-keyword fuzzy search scheme over encrypted cloud storage[J]. Journal of University of Science and Technology of China, 2021, 51(7): 562-576.

References

[1] Wang B, Yu S, Lou W, et al. Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud. Proceedings of the International Conference on Computer Communications (INFOCOM). IEEE, 2014: 2112-2120.
[2] Fu Z, Wu X, Guan C,et al. 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.
[3] Kim M, Lee H T, Ling S,et al. Private compound wildcard queries using fully homomorphic encryption. IEEE Transactions on Dependable and Secure Computing,2019, 16(5): 743-756.
[4] Yang Y, Liu X, Deng R H,et al. Flexible wildcard searchable encryption system. IEEE Transactions on Services Computing, 2020, 13(3): 464-477.
[5] Yang Y, Liu X, Deng R. Multi-user multi-keyword rank search over encrypted data in arbitrary language. IEEE Transactions on Dependable and Secure Computing, 2017, 17(2): 320-334.
[6] Wang X, Ma J, Liu X, et al. Search in my way: Practical outsourced image retrieval framework supporting unshared key. Proceedings of the International Conference on Computer Communications (INFOCOM). IEEE, 2019: 2485-2493.
[7] Cheng K, Shen Y, Wang Y,et al. Strongly secure and efficient range queries in cloud databases under multiple keys. Proceedings of the International Conference on Computer Communications (INFOCOM). IEEE, 2019: 2494-2502.
[8] Curtmola R, Garay J, Kamara S,et al. Searchable symmetric encryption: Improved definitions and efficient constructions. Journal of Computer Security, 2011, 19(5): 895-934.
[9] Bloom B H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13(7): 422-426.
[10] Mitzenmacher M. Compressed bloom filters. IEEE/ACM Transactions on Networking, 2002, 10(5): 604-612.
[11] Broder A Z, Mitzenmacher M. Network applications of bloom filters: A survey. Internet Mathematics, 2004, 1(4): 485-509.
[12] Wong W K, Cheung D W-L, Kao B, et al. Secure kNN computation on encrypted databases. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). Rhode Island, USA: ACM, 2009: 139-152.
[13] Blaze M, Bleumer G, Strauss M. Divertible protocols and atomic proxy cryptography. International Conference on the Theory and Application of Cryptographic Techniques. Espoo, Finland: Springer, 1998: 127-144.
[14] Ateniese G, Fu K, Green M. Improved proxy reencryption schemes with applications to secure distributed storage. ACM Transactions on Information and System Security, 2006, 9(1): 1-30.
[15] Yuan J, Tian Y. Practical privacy-preserving MapReduce based k-means clustering over large-scale dataset. IEEE Transactions on Cloud Computing, 2017, 7(2): 568-579.
[16] Yao B, Li F F, Xiao X K. Secure nearest neighbor revisited. International Conference on Data Engineering. Brisbane, Australia: IEEE, 2013: 733-744.
[17] RFC Index. https://www.rfc-editor.org/rfc-index.html/.
[18] Song D X,. Wagner D, Perrig A. Practical techniques for searches on encrypted data. Proceedings of IEEE Symposium on Security and Privacy (S&P). Berkeley, USA: IEEE, 2000: 44-55.
[19] Cash D, Jarecki S, Jutla C.et al. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. Berlin Heidelberg: Springer, 2013.
[20] Cao N, Wang C, Li M,et al. Privacy preserving multi-keyword ranked search over encrypted cloud data. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 222-233.
[21] Fu Z, Sun X, Linge N,et al. Achieving effective cloud search services: Multi-keyword ranked search over encrypted cloud data supporting synonym query. IEEE Transactions on Consumer Electronics,2014, 60(1): 164-172.
[22] Sun W, Wang B, Cao N,et al. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking. IEEE Transactions on Parallel Distributed Systems, 2014, 25(11): 3025-3035.
[23] Yu J, Lu P, Zhu Y,et al. Toward secure multikeyword top-k retrieval over encrypted cloud data. IEEE Transactions on Dependable Secure Computing, 2013, 10(4): 239-250.
[24] Sun S F, Yuan X, Liu J K, et al. Practical backward-secure searchable encryption from symmetric puncturable encryption. Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS). Toronto, Canada: ACM, 2018: 763-780.
[25] Chamani J G, Papadopoulos D, Papamanthou C, et al. New constructions for forward and backward private symmetric searchable encryption. Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS). Toronto, Canada: ACM, 2018: 1038-1055.
[26] Bost R. ∑oφoς: Forward secure searchable encryption. Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS). Vienna Austria: ACM, 2016: 1143-1154.
[27] Song X, Dong C, Yuan D,et al. Forward private searchable symmetric encryption with optimized I/O efficiency. IEEE Transactions on Dependable and Secure Computing, 2020, 17(5): 912-927.
[28] Ding X, Liu P, Jin H. Privacy-preserving multi-keyword top-k similarity search over encrypted data. IEEE Transactions on Dependable and Secure Computing, 2017, 16(2): 344-357.
[29] Sun W, Yu S, Lou W,et al. Protecting your right: Attribute-based keyword search with fine-grained owner enforced search authorization in the cloud. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(4): 1187-1198.
[30] Xu L, Chen X, Zhang F,et al. ASBKS: Towards attribute set based keyword search over encrypted personal health records. IEEE Transactions on Dependable and Secure Computing, 2020, https://doi.org/10.1109/TDSC.2020.2970928.
[31] Yang Y, Liu X, Deng R H,et al. Lightweight sharable and traceable secure mobile health system. IEEE Transactions on Dependable and Secure Computing, 2020, 17(1): 78-91.
[32] Liu X, Yang G, Mu Y,et al. Multi-user verifiable searchable symmetric encryption for cloud storage. IEEE Transactions on Dependable and Secure Computing, 2020,17(6): 1322-1332.
[33] Zhang K, Wen M, Lu R, aet al. Multi-client sublinear boolean keyword searching for encrypted cloud storage with owner-enforced authorization. IEEE Transactions on Dependable and Secure Computing, 2020, PP(99): 1-1.
[34] Kermanshahi S K, Liu J K, Steinfeld R,et al. Multi-client cloud-based symmetric searchable encryption. IEEE Transactions on Dependable and Secure Computing. 2021, 18(5): 2419-2437.
[35] Li J, Wang Q, Wang C,et al. Fuzzy keyword search over encrypted data in cloud computing. Proceeding of the 2010 International Conference on Computer Communications (INFOCOM). San Diego, USA: IEEE, 2010: 1-5.