ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC

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

  • 1.

    School of Cyber Security, University of Science and Technology of China, Hefei, Anhui 230027, China

  • 2.

    Computer and Information Science Department, Fordham University, NY 10458, USA

  • 3.

    College of Science and Engineering, Kanazawa University, Kakuma-machi, Kanazawa 920-1192, Japan

Cite this:
https://doi.org/10.52396/JUST-2021-0071
  • Received Date: 12 March 2021
  • Rev Recd Date: 28 March 2021
  • Publish Date: 31 July 2021
    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.

    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.
    • FullText(HTML)
  • loading
    • References(35)
  • [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.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    Get Citation
    PDF
    XML
    [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.
    Recommended articles
    TrendMD
    Volume 51 Issue 7 page: 562-576
    Cover

    Article Metrics

    Article views (282) PDF downloads(336)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return