基于可拆分倒排索引的可搜索加密方案

doi:10.11772/j.issn.1001-9081.2021010112

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (11): 3288-3294.DOI: 10.11772/j.issn.1001-9081.2021010112

基于可拆分倒排索引的可搜索加密方案

孙晓玲(), 杨光, 沈焱萍, 杨秋格, 陈涛

防灾科技学院信息工程学院，河北三河 065201

收稿日期:2021-01-22 修回日期:2021-05-13 接受日期:2021-05-14 发布日期:2021-11-29 出版日期:2021-11-10
通讯作者: 孙晓玲
作者简介:孙晓玲（1983—），女，山东莱阳人，讲师，硕士，CCF会员，主要研究方向：密码学、信息安全
杨光（1984—），女，吉林洮南人，副教授，博士，主要研究方向：数据分析、图像处理
沈焱萍（1986—），河北三河人，讲师，博士，CCF 会员，主要研究方向：网络安全
杨秋格（1981—），女，山东聊城人，讲师，硕士，主要研究方向：数据分析
陈涛（1998—），男，四川绵阳人，主要研究方向：数据分析。
基金资助:
廊坊市科技局科学研究与发展计划项目(2020011024);国家自然科学基金资助项目(42007422);中央高校基本科研业务费专项基金资助项目(2020011024)

Searchable encryption scheme based on splittable inverted index

Xiaoling SUN(), Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN

School of Information Engineering，Institute of Disaster Prevention，Sanhe Hebei 065201，China

Received:2021-01-22 Revised:2021-05-13 Accepted:2021-05-14 Online:2021-11-29 Published:2021-11-10
Contact: Xiaoling SUN
About author:SUN Xiaoling， born in 1983， M. S.， lecturer. Her research interests include cryptography，information security
YANG Guang，born in 1984，Ph. D.，associate professor. Her research interests include data analysis，image processing
SHEN Yanping，born in 1986，Ph. D.，lecturer. Her research interests include network security
YANG Qiuge， born in 1981， M. S.， lecturer. Her research interests include data analysis
CHEN Tao，born in 1998. His research interests include data analysis.
Supported by:
the Scientific Research and Development Program of Langfang Science and Technology Bureau(2020011024);the National Natural Science Foundation of China(42007422);the Fundamental Research Funds for the Central Universities(2020011024)

摘要/Abstract

摘要：

为快速检索云环境下的加密数据，提出了一种高效的适用于批量数据处理场合的可搜索加密方案。首先，由客户端创建两个倒排索引，分别是存储了文件-关键词映射的文件索引和用于存储关键词-文件映射的空的搜索索引；然后，将这两个索引提交给云服务器。搜索索引是在用户检索过程中由云端根据搜索凭证和文件索引逐渐更新建立的，记录了已被检索关键词的检索结果，该方法将搜索索引的构建时间有效分摊了到了每次检索过程中并节省了存储空间。索引采用基于key-value结构的集合存储方式，支持索引的同时合并和拆分，即在添加和删除文件时，由客户端根据要添加或删除的文件集生成对应的文件索引和搜索索引，然后服务器对索引进行合并和拆分，从而实现文件的快速批量添加和删除。测试结果表明，所提方案极大提高了文件更新的效率，适用于批量数据处理。通过泄露函数证明了该方案能满足自适应动态选择关键词攻击下的不可区分性安全标准。

关键词: 云计算, 可搜索加密, 倒排索引, 索引合并和拆分, 动态更新

Abstract:

For retrieving the encrypted data in cloud environment quickly， an efficient searchable encryption scheme for batch data processing scenarios was proposed. Firstly， two inverted indexes were built by the client， one file index was used to store the file-keyword mapping， another empty search index was used to store keyword-file mapping. Then， these two indexes were submitted to the cloud server. The search index_{was gradually updated and constructed according to the search tokens and file indexesduring the user’s search by the cloud， and the search results of the searched keywords were recorded by this search index. In this way， the search index construction time was shared to each retrieval process effectively and the storage space of search index was reduced. A set storage method based on key-value structure was adopted by the indexes， which supported the at-the-same-time merging and splitting of index， which means when adding and deleting files， the corresponding file index and search index were generated by the client according to the file set to be added or deleted， then the server merged or split the indexes， so that the files were able to be added and deleted in batch quickly. Testing results show that the proposed scheme greatly improves the updating efficiency of files and is suitable for batch data processing. Through leakage function， it is proved that the proposed scheme can meet the indistinguishability security standard against adaptive dynamic keyword selection attack.}

Key words: cloud computing, searchable encryption, inverted index, index merging and splitting, dynamic update

中图分类号:

TP309.7

孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 计算机应用, 2021, 41(11): 3288-3294.

Xiaoling SUN, Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN. Searchable encryption scheme based on splittable inverted index[J]. Journal of Computer Applications, 2021, 41(11): 3288-3294.

图/表 10

表1 不同方案的性能比较

Tab.1 Performance comparison of different schemes

方案	动态	索引大小	搜索时间	更新消耗
文献［12］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (m / n)$
文献［13］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (m / n)$
文献［14］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (m)$
文献［15］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (r)$
文献［20］方案	是	$Ο ((m + \| F \| + 1) \| F \|)$	$Ο (m r l g \| F \|)$	$Ο ((m + \| F \| + 1) 2)$
文献［21］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο r + m a x w I w$
本文方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (r)$

表1 不同方案的性能比较

Tab.1 Performance comparison of different schemes

方案	动态	索引大小	搜索时间	更新消耗
文献［12］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (m / n)$
文献［13］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (m / n)$
文献［14］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (m)$
文献［15］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (r)$
文献［20］方案	是	$Ο ((m + \| F \| + 1) \| F \|)$	$Ο (m r l g \| F \|)$	$Ο ((m + \| F \| + 1) 2)$
文献［21］方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο r + m a x w I w$
本文方案	是	$Ο (m + n)$	$Ο (m / n)$	$Ο (r)$

图1 云环境下密文检索系统模型

Fig. 1 Ciphertext retrieval system model in cloud environment

表2 所用到的变量和相应定义

Tab. 2 Used variables and corresponding definitions

变量	定义
${0,1} n$	长度为 $n$ 的二进制序列
｛ $0,1} *$	长度任意的二进制序列
\|u\|	二进制序列 $u$ 的比特长度
$u v$	二进制序列 $u$ 和 $v$ 的连接
$x ← A$	$x$ 是概率算法 $A$ 的输出
$λ$	安全参数
$f = {w 1, w 2, …, w f}$	文件f由关键词w_i组成， $w i ∈ {0,1} *$
$i d (f)$	文件f的标识符
$f$	文件f中关键词的个数
F	文件集合 $F = {f 1, f 2, … f n}$
\|F\|	文件集合 $F$ 中文件的个数
ID_w	包含w的文件的标识符构成的集合
F_w	包含w的文件构成的集合
C_w	包含w的文件的密文集合
$f ¯$	文件f的唯一关键词集合
c	文件f加密后的密文
$c ¯$	文件f唯一关键词密文集合
C	文件密文集合 $C = {c 1, c 2, …, c n}$
F_a	批量添加的文件集合
F_d	批量删除的文件集合
C_a	批量添加的文件密文集合
W_a	集合F_a总的唯一关键词集合
W_d	集合F_d总的唯一关键词集合

表2 所用到的变量和相应定义

Tab. 2 Used variables and corresponding definitions

变量	定义
${0,1} n$	长度为 $n$ 的二进制序列
｛ $0,1} *$	长度任意的二进制序列
\|u\|	二进制序列 $u$ 的比特长度
$u v$	二进制序列 $u$ 和 $v$ 的连接
$x ← A$	$x$ 是概率算法 $A$ 的输出
$λ$	安全参数
$f = {w 1, w 2, …, w f}$	文件f由关键词w_i组成， $w i ∈ {0,1} *$
$i d (f)$	文件f的标识符
$f$	文件f中关键词的个数
F	文件集合 $F = {f 1, f 2, … f n}$
\|F\|	文件集合 $F$ 中文件的个数
ID_w	包含w的文件的标识符构成的集合
F_w	包含w的文件构成的集合
C_w	包含w的文件的密文集合
$f ¯$	文件f的唯一关键词集合
c	文件f加密后的密文
$c ¯$	文件f唯一关键词密文集合
C	文件密文集合 $C = {c 1, c 2, …, c n}$
F_a	批量添加的文件集合
F_d	批量删除的文件集合
C_a	批量添加的文件密文集合
W_a	集合F_a总的唯一关键词集合
W_d	集合F_d总的唯一关键词集合

图2 文件索引If示意图

Fig. 2 Schematic diagram of file index If

图3 搜索索引Iw示意图

Fig. 3 Schematic diagram of search index Iw

图4 历史搜索关键词及新增关键词与总搜索次数关系

Fig.4 Relationship between historical search keywords，new keywords and total search times

图5 平均每次搜索耗时与总搜索次数关系

Fig.5 Relationship between average time cost in each search and total search times

图6 Iw添加文件在本文方案与文献［14-15］方案的耗时对比

Fig.6 Time consumption comparison of adding files in Iw between proposed scheme and scheme in literature ［14-15］

图7 Iw删除文件在本文方案与文献［14］方案的耗时对比

Fig.7 Time consumption comparison of deleting files in Iw between proposed scheme and scheme in literature ［14］

图8 Iw删除文件在本文方案与文献［15］方案的耗时对比

Fig. 8 Time consumption comparison of deleting files in Iw between proposed scheme and scheme in literature ［15］

参考文献 22

1	工业和信息化部电信研究院.云计算白皮书（2012年）［R/OL］.［2020-12-13］. ［R/OL］.［2020-12-13］.）. 10.32894/kujss.2019.15.2.1
2	ARMBRUST M，FOX A， GRIFFITH R，et al. A view of cloud computing ［J］. Communications of the ACM， 2010， 53（4）： 50-58. 10.1145/1721654.1721672
3	GOLDREICH O，OSTROVSKY R.Software protection and simulation on oblivious RAMs ［J］. Journal of the ACM， 1996， 43（3）： 431-473. 10.1145/233551.233553
4	SONG D X， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data ［C］// Proceedings of the 2000 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2000： 44-55. 10.1109/secpri.2000.848445
5	GOH E J. Secure indexes： report2003/216 ［R/OL］. （2004-03-16）［2020-12-13］. . 10.1023/a:1021928209813
6	CHANG Y C， MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data： report2004/051 ［R/OL］. （2004-03-16）［2020-12-13］. . 10.1007/11496137_30
7	WATANABE C， ARAI Y. Privacy-preserving queries for a DAS model using encrypted bloom filter ［C］// Proceedings of the 2009 International Conference on Database Systems for Advanced Applications， LNCS5463. Berlin： Springer， 2009： 491-495.
8	CURTMOLA R， GARAY J， KAMARA S， et al. Searchable symmetric encryption： improved definitions and efficient constructions ［C］// Proceedings of the 2006 13th ACM Conference on Computer and Communications Security. New York： ACM， 2006： 79-88. 10.1145/1180405.1180417
9	KAMARA S， PAPAMANTHOU C， ROEDER T. Dynamic searchable symmetric encryption ［C］// Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York： ACM， 2012： 965-976. 10.1145/2382196.2382298
10	KAMARA S， PAPAMANTHOU C. Parallel and dynamic searchable symmetric encryption ［C］// Proceedings of the 2013 International Conference on Financial Cryptography and Data Security， LNCS7859. Berlin： Springer， 2013： 258-274.
11	STEFANOV E， PAPAMANTHOU C， SHI E. Practical dynamic searchable encryption with small leakage ［C］// Proceedings of the 2014 21st Annual Network and Distributed System Security Symposium. Reston： Internet Society， 2014： Article No.23298. 10.14722/ndss.2014.23298
12	CASH D， JAEGER J， JARECKI S， et al. Dynamic searchable encryption in very large databases： data structures and implementation ［C］// Proceedings of the 2014 21st Annual Network and Distributed System Security Symposium. Reston： Internet Society， 2014： Article No.23264. 10.14722/ndss.2014.23264
13	NAVEED M， PRABHAKARAN M， GUNTER C A. Dynamic searchable encryption via blind storage： report2014/219 ［R/OL］. （2014-03-26）［2020-12-17］. . 10.1109/sp.2014.47
14	HAHN F， KERSCHBAUM F. Searchable encryption with secure and efficient updates ［C］// Proceedings of the 2014 21st ACM Conference on Computer and Communications Security. New York： ACM， 2014： 310-320. 10.1145/2660267.2660297
15	孙晓玲，杨秋格，沈焱萍，等.改进的高效动态可搜索加密方案［J］.计算机应用研究，2020，37（8）：2472-2476.
	SUN X L， YANG Q G， SHEN Y P， et al. Improved efficient dynamic searchable encryption ［J］. Application Research of Computers， 2020， 37（8）： 2472-2476.
16	杜军强，杨波.云计算中加密数据的模糊关键字搜索方法［J］.计算机工程与应用，2015，51（5）：146-152， 227. 10.3778/j.issn.1002-8331.1303-0508
	DU J Q， YANG B. Fuzzy keyword search method over encrypted data in cloud computing ［J］. Computer Engineering and Applications， 2015， 51（5）： 146-152， 227. 10.3778/j.issn.1002-8331.1303-0508
17	XIA Z H， WANG X H， SUN X M， et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data ［J］. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（2）： 340-352. 10.1109/tpds.2015.2401003
18	FU Z J， WU X L， GUAN C W， 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. 10.1109/tifs.2016.2596138
19	严小龙，庞晓琼，任孟琦.支持动态更新的多关键词密文排序检索［J］.计算机工程与设计，2018，39（4）：901-906. 10.16208/j.issn1000-7024.2018.04.001
	YAN X L， PANG X Q， REN M Q. Multi-keyword ranked search method supporting dynamic update ［J］. Computer Engineering and Design， 2018， 39（4）： 901-906. 10.16208/j.issn1000-7024.2018.04.001
20	杨旸，刘佳，蔡圣暐，等.云计算中保护数据隐私的快速多关键词语义排序搜索方案［J］.计算机学报，2018，41（6）：1346-1359. 10.11897/SP.J.1016.2018.01346
	YANG Y， LIU J， CAI S W， et al. Fast multi-keyword semantic ranked search in cloud computing ［J］. Chinese Journal of Computers， 2018， 41（6）： 1346-1359. 10.11897/SP.J.1016.2018.01346
21	吴志强，李肯立，郑蕙.高效可扩展的对称密文检索架构［J］.通信学报，2017，38（8）：79-93. 10.11959/j.issn.1000-436x.2017166
	WU Z Q， LI K L， ZHENG H. Efficient and scalable architecture for searchable symmetric encryption ［J］. Journal on Communications， 2017， 38（8）：79-93. 10.11959/j.issn.1000-436x.2017166
22	贾强，张帅，周福才.一种面向密文大型数据集的可搜索加密方案［J］.东北大学学报（自然科学版），2019，40（7）：913-919. 10.12068/j.issn.1005-3026.2019.07.001
	JIA Q， ZHANG S， ZHOU F C. A searchable encryption scheme for encrypted large data sets ［J］. Journal of Northeastern University （Natural Science）， 2019， 40（7）： 913 -919. 10.12068/j.issn.1005-3026.2019.07.001

[1]	吴悦, 雒江涛, 刘锐, 胡钟尹. 基于感知哈希和切块的视频相似度检测方法[J]. 计算机应用, 2021, 41(7): 2070-2075.
[2]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[3]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[4]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[5]	姜琨, 刘征, 朱磊, 李晓星. 基于有向无环图的倒排链等字长划分压缩算法[J]. 计算机应用, 2021, 41(3): 727-732.
[6]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[7]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[8]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[9]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[10]	王庆永, 毛莺池, 王绎超, 王龙宝. 基于多微云协作的计算任务卸载[J]. 计算机应用, 2020, 40(2): 328-334.
[11]	刘福鑫, 李劲巍, 王熠弘, 李琳. 基于Kubernetes的云原生海量数据存储系统设计与实现[J]. 计算机应用, 2020, 40(2): 547-552.
[12]	杨哂哂, 吴慧珍, 庄黎丽, 吕宏武. 基于Markov过程的IaaS系统可用性建模与分析方法[J]. 计算机应用, 2020, 40(10): 3013-3018.
[13]	张恩, 侯缨盈, 李功丽, 李会敏, 李钰. 基于错误学习的自适应等级可搜索加密方案[J]. 计算机应用, 2020, 40(1): 148-156.
[14]	林立, 熊金波, 肖如良, 林铭炜, 陈秀华. Gaming@Edge:基于边缘节点的低延迟云游戏系统[J]. 计算机应用, 2019, 39(7): 2001-2007.
[15]	徐雅斌, 彭宏恩. 基于需求预测的PaaS平台资源分配方法[J]. 计算机应用, 2019, 39(6): 1583-1588.

基于可拆分倒排索引的可搜索加密方案

Searchable encryption scheme based on splittable inverted index

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 22

相关文章 15

编辑推荐

Metrics