您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (9): 28-38.doi: 10.6040/j.issn.1671-9352.0.2022.471

•   • 上一篇    下一篇

支持通配符和模糊搜索的加密方案

赵博1,2(),秦静1,3,*(),刘晋璐1   

  1. 1. 山东大学数学学院，山东 济南 250100
    2. 华控清交信息科技有限公司安全与芯片部门，北京 100093
    3. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093
  • 收稿日期:2022-09-03 出版日期:2023-09-20 发布日期:2023-09-08
  • 通讯作者: 秦静 E-mail:zhaobomath@163.com;qinjing@sdu.edu.cn
  • 作者简介:赵博(1997—)，男，硕士研究生, 研究方向为可搜索加密.E-mail: zhaobomath@163.com
  • 基金资助:
    国家自然科学基金资助项目(62072276);国家自然科学基金资助项目(61772311)

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

摘要：

基于n-gram技术，提出了一个能够同时支持通配符和模糊搜索的加密方案。另外，利用布隆过滤器优化方案，减少了索引存储开销和搜索时间。安全性分析表明本文提出的方案是非适应性语义安全的，性能分析表明优化后的方案与已有方案相比在存储、通信及陷门生成方面都有更小的开销。

关键词: 通配符搜索, 模糊搜索, 关键词特征, 向量空间模型, 布隆过滤器

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

中图分类号: 

  • TP309

图1

支持通配符和模糊搜索的索引"

表1

复杂度分析"

对比项 文献[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)
支持模糊搜索 是 否 是 是 是
支持通配符搜索 否 是 是 是 是

图2

存储开销"

图3

索引生成时间"

图4

陷门生成时间"

图5

通信复杂度"

图6

搜索时间"

图7

搜索精度"

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] 索红光,王玉伟 . 一种用于文本聚类的改进k-means算法[J]. J4, 2008, 43(1): 60-64 .
[2] 王卫东,宋 丹,宋人杰 . 基于分解的向量空间模型的Web新闻信息检索[J]. J4, 2006, 41(3): 135-138 .
[3] 吴鹏飞,孟祥增,刘俊晓,马凤娟 . 基于结构与内容的网页主题信息提取研究[J]. J4, 2006, 41(3): 131-134 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[2] 杨永伟1,2,贺鹏飞2,李毅君2,3. BL-代数的严格滤子[J]. 山东大学学报（理学版）, 2014, 49(03): 63 -67 .
[3] 李敏1,2,李歧强1. 不确定奇异时滞系统的观测器型滑模控制器[J]. 山东大学学报（理学版）, 2014, 49(03): 37 -42 .
[4] 唐风琴1,白建明2. 一类带有广义负上限相依索赔额的风险过程大偏差[J]. J4, 2013, 48(1): 100 -106 .
[5] 程智1,2,孙翠芳2,王宁1,杜先能1. 关于Zn的拉回及其性质[J]. J4, 2013, 48(2): 15 -19 .
[6] 汤晓宏1，胡文效2*，魏彦锋2，蒋锡龙2，张晶莹2，. 葡萄酒野生酿酒酵母的筛选及其生物特性的研究[J]. 山东大学学报（理学版）, 2014, 49(03): 12 -17 .
[7] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[8] 田学刚, 王少英. 算子方程AXB=C的解[J]. J4, 2010, 45(6): 74 -80 .
[9] 霍玉洪,季全宝. 一类生物细胞系统钙离子振荡行为的同步研究[J]. J4, 2010, 45(6): 105 -110 .
[10] 杨军. 金属基纳米材料表征和纳米结构调控[J]. 山东大学学报（理学版）, 2013, 48(1): 1 -22 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发