Searchable encryption scheme based on splittable inverted index

doi:10.11772/j.issn.1001-9081.2021010112

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (11): 3288-3294.DOI: 10.11772/j.issn.1001-9081.2021010112

• Cyber security • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP309.7

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.

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

Figures/Tables 10

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)$

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)$

Fig. 1 Ciphertext retrieval system model in cloud environment

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总的唯一关键词集合

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总的唯一关键词集合

Fig. 2 Schematic diagram of file index If

Fig. 3 Schematic diagram of search index Iw

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

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

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

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

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

References 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]	Xiaoling SUN, Danhui WANG, Shanshan LI. Dynamic ciphertext sorting and retrieval scheme based on blockchain [J]. Journal of Computer Applications, 2024, 44(8): 2500-2505.
[2]	Zheng WANG, Jingwei WANG, Xinchun YIN. Searchable electronic health record sharing scheme with user revocation [J]. Journal of Computer Applications, 2024, 44(2): 504-511.
[3]	Gaimei GAO, Mingbo DUAN, Yaling XUN, Chunxia LIU, Weichao DANG. SM9-based attribute-based searchable encryption scheme with cryptographic reverse firewall [J]. Journal of Computer Applications, 2024, 44(11): 3495-3502.
[4]	Xiaoyu DU, Shuaiqi LIU, Zhijie HAN, Zhenxiang HUO, Yujing WANG. Patient-centric medical information sharing scheme based on IPFS and blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3122-3133.
[5]	Ting YANG, Ruoyu MO, Xiujuan ZHANG, Zhousen ZHU. Enhancement and expansion of full-text search in relational databases based on lightweight caching strategy [J]. Journal of Computer Applications, 2023, 43(8): 2431-2438.
[6]	Jiaxing LU, Hua DAI, Yuanlong LIU, Qian ZHOU, Geng YANG. Dictionary partition vector space model for ciphertext ranked search in cloud environment [J]. Journal of Computer Applications, 2023, 43(7): 1994-2000.
[7]	Kun YOU, Qinhui WANG, Xin LI. General multi-unit false-name-proof auction mechanism for cloud computing [J]. Journal of Computer Applications, 2023, 43(11): 3351-3357.
[8]	PANG Xiaoqiong, WANG Yunting, CHEN Wenjun, JIANG Pan, GAO Yanan. Fair and verifiable multi-keyword ranked search over encrypted data based on blockchain [J]. Journal of Computer Applications, 2023, 43(1): 130-139.
[9]	Jingyu SUN, Jiayu ZHU, Ziqiang TIAN, Guozhen SHI, Chuanjiang GUAN. Attribute based encryption scheme based on elliptic curve cryptography and supporting revocation [J]. Journal of Computer Applications, 2022, 42(7): 2094-2103.
[10]	Jinquan ZHANG, Shouwei XU, Xincheng LI, Chongyang WANG, Jingzhi XU. Cloud computing task scheduling based on orthogonal adaptive whale optimization [J]. Journal of Computer Applications, 2022, 42(5): 1516-1523.
[11]	Li LI, Yi WU, Zhikun YANG, Yunpeng CHEN. Medical electronic record sharing scheme based on sharding-based blockchain [J]. Journal of Computer Applications, 2022, 42(1): 183-190.
[12]	WU Yue, LUO Jiangtao, LIU Rui, HU Zhongyin. Video similarity detection method based on perceptual hashing and dicing [J]. Journal of Computer Applications, 2021, 41(7): 2070-2075.
[13]	CHEN Jiahao, YIN Xinchun. Traceable and revocable ciphertext-policy attribute-based encryption scheme based on cloud-fog computing [J]. Journal of Computer Applications, 2021, 41(6): 1611-1620.
[14]	GE Lina, HU Yugu, ZHANG Guifen, CHEN Yuanyuan. Reverse hybrid access control scheme based on object attribute matching in cloud computing environment [J]. Journal of Computer Applications, 2021, 41(6): 1604-1610.
[15]	YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998.

Searchable encryption scheme based on splittable inverted index

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 22

Related Articles 15

Recommended Articles

Metrics