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

Ling Huaze; Xue Kaiping; Wei David S.L.; Li Ruidong

doi:10.52396/JUST-2021-0071

JUSTC > 2021 > 51(7): 562-576. > DOI: 10.52396/JUST-2021-0071

PDF (1958 KB)

Open 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: JUSTC, 2021, 51(7): 562-576

https://doi.org/10.52396/JUST-2021-0071

More Information

Received Date: March 11, 2021
Revised Date: March 27, 2021
Published Date: July 30, 2021

Full text PDF

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)

References (35)

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.

Cited By

Track Citations

Get Citation

{{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF

XML

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.

[1]	Xuan Jin, Yuanzhi Yao, Nenghai Yu. Efficient secure aggregation for privacy-preserving federated learning based on secret sharing[J]. JUSTC, 2024, 54(1): 0104. DOI: 10.52396/JUSTC-2022-0116
[2]	TAO Tao, BAI Jianshu, LIU Heng, HOU Shudong, ZHENG Xiao. Differential privacy protection method for deep learning based on WGAN feedback[J]. JUSTC, 2020, 50(8): 1064. DOI: 10.3969/j.issn.0253-2778.2020.08.004
[3]	CHEN Jiaming, WANG Li, XIAO Yafei, FANG Xianjing. A privacy preserving measurement for query under k-anonymity mechanism[J]. JUSTC, 2018, 48(6): 512-518. DOI: 10.3969/j.issn.0253-2778.2018.06.010
[4]	CHEN Yuan, WANG Jingbin. Distributed keyword approximate search method for RDF[J]. JUSTC, 2017, 47(10): 823-836. DOI: 10.3969/j.issn.0253-2778.2017.10.004
[5]	LI Huakang, LIU Pan, YANG Yitao, SUN Guozi. A cloud storage access scheme with security proxy based on attribute mapping node[J]. JUSTC, 2017, 47(4): 304-310. DOI: 10.3969/j.issn.0253-2778.2017.04.004
[6]	ZENG Shuke, ZHANG Yang, CHENG Liang, DENG Yi, FENG Dengguo. An approach to evaluate the effectiveness of privacy protection in Android system[J]. JUSTC, 2014, 44(10): 853-861. DOI: 10.3969/j.issn.0253-2778.2014.10.009
[7]	DAI Lican, YU Nenghai. Image annotation by searching semantically related regions[J]. JUSTC, 2014, 44(1): 67-73. DOI: 10.3969/j.issn.0253-2778.2014.01.008
[8]	REN Yanli, GU Dawu, WANG Shuozhong, ZHANG Xinpeng. Anonymous identity-based encryption scheme without random oracles[J]. JUSTC, 2012, 42(4): 296-301. DOI: 10.3969/j.issn.0253-2778.2012.04.006
[9]	YANG Xiaoyuan, WANG Zhiqiang, CAI Weiyi. Multiple-authority-key KP-ABE scheme with adaptive security[J]. JUSTC, 2011, 41(7): 619-625. DOI: 10.3969/j.issn.0253-2778.2011.07.009
[10]	TANG Zhanyong, FANG Dingyi, SU Lin. A tamper-proof software watermark using code-based encryption[J]. JUSTC, 2011, 41(7): 599-606. DOI: 10.3969/j.issn.0253-2778.2011.07.006

TrendMD

Volume 51 Issue 7 PP. 562-576

Cover

Keywords

Article Metrics

Article views (354) PDF downloads (414)

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

Abstract

Abstract

References

Related Articles

Catalog

References

Related Articles

TrendMD

Article Metrics

Authors

Browse

Contact Us

About

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

Share

Tools

Abstract

Abstract

References

Related Articles

Catalog

References

Related Articles

TrendMD

Article Metrics

Authors

Browse

Contact Us

About

Export File

Citation

Format

Content