JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (9): 28-38.doi: 10.6040/j.issn.1671-9352.0.2022.471

Previous Articles     Next Articles

An encryption scheme supporting wildcard and fuzzy search

Bo ZHAO1,2(),Jing QIN1,3,*(),Jinlu LIU1   

  1. 1. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
    2. Chip and Security Department, Hua Kong Qing Jiao Information Technology Co., Ltd., Beijing 100093, China
    3. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
  • Received:2022-09-03 Online:2023-09-20 Published:2023-09-08
  • Contact: Jing QIN E-mail:zhaobomath@163.com;qinjing@sdu.edu.cn

RichHTML

9

PDF (PC)

352

Abstract:

Based on n-gram technology, this paper proposes an encryption scheme that can support both wildcard and fuzzy search. In addition, using the Bloom filter optimization scheme, it reduces the index storage overhead and search time. The given security analysis shows that the scheme is non-adaptive semantic security. The performance analysis shows that the optimized scheme has less overhead in storage, communication and trapdoor generation than the previous schemes.

Key words: wildcard search, fuzzy search, keyword feature, vector space model, Bloom filter

CLC Number: 

  • TP309

Fig.1

The index that supports wildcard and fuzzy searches"

Table 1

Complexity analysis"

对比项 文献[8] 文献[15] 文献[21] 方案1 方案2
索引存储开销 O(m) O(n) O(n) O(n) O(n)
索引生成时间 O(m) O(n) O(n) O(n) O(n)
陷门生成时间 O(1) O(1) O(n) O(1) O(1)
通信复杂度 O(1) O(1) O(n) O(1) O(1)
搜索时间 O(m) O(n) O(n) O(n) O(n)
支持模糊搜索 是 否 是 是 是
支持通配符搜索 否 是 是 是 是

Fig.2

Storage overhead"

Fig.3

Index generation time"

Fig.4

Trapdoor generation time"

Fig.5

Communication complexity"

Fig.6

Search time"

Fig.7

Search accuracy"

1 冯登国, 张敏, 张妍, 等. 云计算安全研究[J]. 软件学报, 2011, 22 (1): 71- 83.
FENG Dengguo , ZHANG Min , ZHANG Yan , et al. Study on cloud computing security[J]. Journal of Software, 2011, 22 (1): 71- 83.
2 SONG D X, WAGNER D, PERRIG A. Practical techniques for searches on encrypted data[C]//Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000. Berkeley: IEEE, 2000: 44-55.
3 李颖, 马春光. 可搜索加密研究进展综述[J]. 网络与信息安全学报, 2018, 4 (7): 13- 21.
LI Ying , MA Chunguang . Overview of searchable encryption research[J]. Chinese Journal of Network and Information Security, 2018, 4 (7): 13- 21.
4 李经纬, 贾春福, 刘哲理, 等. 可搜索加密技术研究综述[J]. 软件学报, 2015, 26 (1): 109- 128.
LI Jingwei , JIA Chunfu , LIU Zheli , et al. Survey on the searchable encryption[J]. Journal of Software, 2015, 26 (1): 109- 128.
5 刘晋璐, 秦静, 汪青, 等. 复杂语义可搜索加密研究[J]. 密码学报, 2022, 9 (1): 1- 22.
LIU Jinlu , QIN Jing , WANG Qing , et al. On complex semantic searchable encryptions[J]. Journal of Cryptologic Research, 2022, 9 (1): 1- 22.
6 LI Jin, WANG Qian, WANG Cong, et al. Fuzzy keyword search over encrypted data in cloud computing[C]//2010 Proceedings IEEE INFOCOM. San Diego: IEEE, 2010: 1-5.
7 KUZU M, ISLAM M S, KANTARCIOGLU M. Efficient similarity search over encrypted data[C]//2012 IEEE 28th International Conference on Data Engineering. Arlington: IEEE, 2012: 1156-1167.
8 WANG Bing, YU Shucheng, LOU Wenjing, et al. Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud[C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications. Toronto: IEEE, 2014: 2112-2120.
9 杨旸, 杨书略, 柯闽. 加密云数据下基于Simhash的模糊排序搜索方案[J]. 计算机学报, 2017, 40 (2): 431- 444.
YANG Yang , YANG Shulue , KE Min . Ranked fuzzy keyword search based on Simhash over encrypted cloud data[J]. Chinese Journal of Computers, 2017, 40 (2): 431- 444.
10 FU Zhangjie , WU Xinle , GUAN Chaowen , et al. Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement[J]. IEEE Transactions on Information Forensics and Security, 2016, 11 (12): 2706- 2716.
11 CAO Jinkun, ZHU Jinhao, Lin Liwei, et al. A novel fuzzy search approach over encrypted data with improved accuracy and efficiency[EB/OL]. arXiv: 1904.12111, 2019. https://doi.org/10.48550/arXiv.1904.12111.
12 ZHANG M W , CHEN Y , HUANG J J . SE-PPFM: a searchable encryption scheme supporting privacy-preserving fuzzy multi-keyword in cloud systems[J]. IEEE Systems Journal, 2021, 15 (2): 2980- 2988.
13 LIU Qin , PENG Yu , PEI Shuyu , et al. Prime inner product encoding for effective wildcard-based multi-keyword fuzzy search[J]. IEEE Transactions on Services Computing, 2020, 15 (4): 1799- 1812.
14 BÖSCH C, BRINKMAN R, HARTEL P, et al. Conjunctive wildcard search over encrypted data[C]//Workshop on Secure Data Management. Berlin: Springer, 2011: 114-127.
15 HU Changhui , HAN Lidong . Efficient wildcard search over encrypted data[J]. International Journal of Information Security, 2016, 15 (5): 539- 547.
16 LIU Jinlu , ZHAO Bo , QIN Jing , et al. Multi-keyword ranked searchable encryption with the wildcard keyword for data sharing in cloud computing[J]. The Computer Journal, 2023, 66 (1): 184- 196.
17 ZHANG Xi , ZHAO Bo , QIN Jing , et al. Practical wildcard searchable encryption with tree-based index[J]. International Journal of Intelligent Systems, 2021, 36 (12): 7475- 7499.
18 赵博, 刘晋璐, 秦静. 无假阳性的可验证通配符可搜索加密[J]. 密码学报, 2022, 9 (5): 899- 909.
ZHAO Bo , LIU Jinlu , QIN Jing . Verifiable wildcard searchable encryption without false positive[J]. Journal of Cryptologic Research, 2022, 9 (5): 899- 909.
19 LI Yu , NING Jianting , CHEN Jie . Secure and practical wildcard searchable encryption system based on inner product[J]. IEEE Transactions on Services Computing, 2022, 99, 1- 14.
20 SUGA T, NISHIDE T, SAKURAI K. Secure keyword search using Bloom filter with specified character positions[C]//International Conference on Provable Security. Berlin: Springer, 2012: 235-252.
21 HU Changhui , HAN Lidong , YIU S M . Efficient and secure multi-functional searchable symmetric encryption schemes[J]. Security and Communication Networks, 2016, 9 (1): 34- 42.
22 WONG W K, CHEUNG D W L, KAO B, et al. Secure kNN computation on encrypted databases[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. Providence: ACM, 2009: 139-152.
23 CURTMOLA R , GARAY J , KAMARA S , et al. Searchable symmetric encryption: improved definitions and efficient constructions[J]. Journal of Computer Security, 2011, 19 (5): 895- 934.
[1] SUO Hong-guang,WANG Yu-wei . An improved k-means algorithm for document clustering [J]. J4, 2008, 43(1): 60-64 .
[2] WANG Wei-dong,SONG Dan,SONG Ren-jie . Web news retrieval based on splited vector space model [J]. J4, 2006, 41(3): 135-138 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[2] YANG Yong-wei1, 2, HE Peng-fei2, LI Yi-jun2,3. On strict filters of BL-algebras#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 63 -67 .
[3] LI Min1,2, LI Qi-qiang1. Observer-based sliding mode control of uncertain singular time-delay systems#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 37 -42 .
[4] TANG Feng-qin1, BAI Jian-ming2. The precise large deviations for a risk model with extended negatively upper orthant dependent claim  sizes[J]. J4, 2013, 48(1): 100 -106 .
[5] CHENG Zhi1,2, SUN Cui-fang2, WANG Ning1, DU Xian-neng1. On the fibre product of Zn and its property[J]. J4, 2013, 48(2): 15 -19 .
[6] TANG Xiao-hong1, HU Wen-xiao2*, WEI Yan-feng2, JIANG Xi-long2, ZHANG Jing-ying2, SHAO Xue-dong3. Screening and biological characteristics studies of wide wine-making yeasts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 12 -17 .
[7] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[8] TIAN Xue-gang, WANG Shao-ying. Solutions to the operator equation AXB=C[J]. J4, 2010, 45(6): 74 -80 .
[9] HUO Yu-hong, JI Quan-bao. Synchronization analysis of oscillatory activities in a biological cell system[J]. J4, 2010, 45(6): 105 -110 .
[10] YANG Jun. Characterization and structural control of metalbased nanomaterials[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 1 -22 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd