多关键词动态可搜索加密方案

doi:10.11959/j.issn.2096-109x.2023028

网络与信息安全学报 ›› 2023, Vol. 9 ›› Issue (2): 143-153.doi: 10.11959/j.issn.2096-109x.2023028

多关键词动态可搜索加密方案

袁承昊¹, 李勇¹, 任爽²

¹ 北京交通大学电子信息工程学院，北京 100044
² 北京交通大学计算机与信息技术学院，北京 100044

修回日期:2023-02-19 出版日期:2023-04-25 发布日期:2023-04-01
作者简介:袁承昊（1998- ），男，山东东营人，北京交通大学硕士生，主要研究方向为云计算安全
李勇（1973- ），男，山东无棣人，北京交通大学副教授，主要研究方向为数据安全与隐私保护、区块链安全
任爽（1981- ），男，吉林长春人，北京交通大学副教授，主要研究方向为人工智能、区块链、虚拟现实技术
基金资助:
国家自然科学基金(62072025);2020年工业互联网创新发展工程项目(TC200H01V)

Dynamic multi-keyword searchable encryption scheme

Chenghao YUAN¹, Yong LI¹, Shuang REN²

¹ School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China
² School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China

Revised:2023-02-19 Online:2023-04-25 Published:2023-04-01
Supported by:
The National Natural Science Foundation of China(62072025);2020 Innovative Development Project of the Industrial Internet(TC200H01V)

摘要/Abstract

摘要：

云存储用户将数据外包存储至云服务器以节省本地存储资源。然而，云存储数据脱离了用户的物理控制范围，可导致云端隐私数据被恶意窃取或泄露。目前动态可搜索加密方案多以对称可搜索加密为主，需要预先建立安全的密钥共享信道，难以直接应用于云存储数据共享场景。针对云存储多方数据的安全共享场景，提出了一种多关键词动态可搜索加密方案。该方案通过引入布谷鸟过滤器构建正向索引，实现数据拥有者对文档及索引的动态添加和删除。同时结合双线性对与拉格朗日插值多项式，可支持多关键词的联合搜索。为降低密文检索阶段的计算开销，采用倒排索引与正向索引结合的构造，以提高云服务器的检索效率。基于判定线性 Diffie-Hellman 问题，在适应性选择关键词攻击下可证明方案的安全性。通过实验分析所提方案在不同数据集中进行关键词搜索及索引更新的执行效率，结果表明所提方案可有效避免检索时间与密文数量的线性相关性，降低了数据量较大情况下更新操作中的计算开销。

关键词: 可搜索加密, 云存储, 布谷鸟过滤器, 倒排索引

Abstract:

Users of cloud storage often outsource their data to cloud servers to save local storage resources.However, cloud storage data is out of the user’s physical control, which may lead to malicious theft or disclosure of private data on cloud.At present, dynamic searchable encryption schemes are mostly based on symmetric searchable encryption, which need to establish a secure key sharing channel in advance, and cannot be directly applied to data sharing in cloud storage scenarios.For the secure sharing scenario of multi-party data in cloud storage, a dynamic multi-keyword searchable encryption scheme was proposed.The forward index was constructed by a cuckoo filter to enable data owners to perform documents and index dynamic updates.The conjunctive multi-keywords search was supported by combining bilinear pairing with Lagrangian interpolation polynomials.To reduce the computational overhead in the ciphertext retrieval phase, a combination of inverted index and forward index was constructed to improve the retrieval efficiency of cloud server.This scheme is provably secure with the indistinguishability in adaptively chosen keyword attack under decision linear Diffie-Hellman problem.Simulation experiments were conducted to analyze the execution efficiency of the scheme for keyword search and index update in different datasets.The results show that the scheme effectively avoids the linear correlation between the retrieval time and the number of ciphertexts, and reduces the computational overhead in the update operation with a large amount of data.

Key words: searchable encryption, cloud storage, cuckoo filter, inverted index

中图分类号:

TP393

袁承昊, 李勇, 任爽. 多关键词动态可搜索加密方案[J]. 网络与信息安全学报, 2023, 9(2): 143-153.

Chenghao YUAN, Yong LI, Shuang REN. Dynamic multi-keyword searchable encryption scheme[J]. Chinese Journal of Network and Information Security, 2023, 9(2): 143-153.

图/表 9

图1

图2

表1

表2

表3

表4

图3

图4

图5

参考文献 16

[1]	CHAUDHARI S , KUMAR PATHURI S . A comprehensive survey on public auditing for secure cloud storage[J]. International Journal of Engineering ＆ Technology, 2018,7: 565-569.
[2]	SUN P J . Privacy protection and data security in cloud computing:a survey,challenges,and solutions[J]. IEEE Access, 2019,7: 147420-147452.
[3]	SONG D X , WAGNER D , PERRIG A . Practical techniques for searches on encrypted data[C]// Proceedings of Proceeding 2000 IEEE Symposium on Security and Privacy. 2002: 44-55.
[4]	KAMARA S , PAPAMANTHOU C , ROEDER T . Dynamic searchable symmetric encryption[C]// Proceedings of the 2012 ACM Conference on Computer and Communications Security. 2012: 965-976.
[5]	STEFANOV E , PAPAMANTHOU C , SHI E ,et al. Practical dynamic searchable encryption with small leakage[EB]. Cryptology ePrint Archive, 2013.
[6]	BOST R , MINAUD B , OHRIMENKO O . Forward and backward private searchable encryption from constrained cryptographic primitives[C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 1465-1482.
[7]	CHAMANI J G , PAPADOPOULOS D , PAPAMANTHOU C ,et al. New constructions for forward and backward private symmetric searchable encryption[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 1038-1055.
[8]	DEMERTZIS I , CHAMANI J G , PAPADOPOULOS D ,et al. Dynamic searchable encryption with small client storage[EB]. Cryptology ePrint Archive, 2019.
[9]	ZHONG H , LI Z F , CUI J ,et al. Efficient dynamic multi-keyword fuzzy search over encrypted cloud data[J]. Journal of Network and Computer Applications, 2020,149:102469.
[10]	ZHANG Y , YOU L , LI Y . Tree-based public key encryption with conjunctive keyword search[J]. Security and Communication Networks, 2021,2021: 1-16.
[11]	FAN B , ANDERSEN D G , KAMINSKY M ,et al. Cuckoo filter:practically better than bloom[C]// Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. 2014: 75-88.
[12]	HE D B , MA M M , ZEADALLY S ,et al. Certificateless public key authenticated encryption with keyword search for industrial Internet of Things[J]. IEEE Transactions on Industrial Informatics, 2018,14(8): 3618-3627.
[13]	ZHANG R , XUE R . Efficient keyword search for public-key setting[C]// Proceedings of MILCOM 2015-2015 IEEE Military Communications Conference. 2015: 1236-1241.
[14]	YE F H , DONG X L , SHEN J C ,et al. A verifiable dynamic multi-user searchable encryption scheme without trusted third parties[C]// Proceedings of 2019 IEEE 25th International Conference on Parallel and Distributed Systems (ICPADS). 2020: 896-900.
[15]	GUO C , ZHUANG R H , CHANG C C ,et al. Dynamic multi-keyword ranked search based on bloom filter over encrypted cloud data[J]. IEEE Access, 2019,7: 35826-35837.
[16]	SONG C G , LIU X , YAN Y L . Efficient Public key encryption with field-free conjunctive keywords search[C]// Proceedings of International Conference on Trusted Systems. 2015: 394-406.

符号	含义
CT	上传的加密文档集合
label={ID₁,…,ID_n}	各文档标签
W ={w ₁,…,w_k}	某文档包含的关键词集合
CF	布谷鸟过滤器
G	有阶循环群
g	循环群G的生成元
Z _P*	整数加法群
H ₁,H₂,H₃	3个不同的抗碰撞哈希函数
H_F,H_C	构造布谷鸟过滤器哈希函数
H_λ,P_key	构造倒排索引的伪随机函数
（sk,pk）	数据使用者的公私钥对
S_n	加密正向索引
T	查询陷门
Inv	加密倒排索引
L_W	构造正向索引的映射函数

方案	多关键词搜索	动态添加	动态删除	IND-CKA
文献[12]				√
文献[13]	√			√
文献[14]		√		√
文献[15]	√	√	√	√
本文	√	√	√	√

符号	运算类型	执行耗时ms
t_p	双线性对运算	9.9
t_e	群G 中的幂运算	0.028
t_m	群G 中的乘法运算	0.003
t_a	群G 中的加法运算	0.001
t_h	哈希运算	0.017

方案	构建索引	生成陷门	密文搜索
文献[12]	mn（2t_h+3t_m+3t_a）=0.046mn	k（t _p+2t_m+2t_a+3t_h）=9.959 k	m（2t _p+t_h+3t_m+2t_a）=19.828m
文献[13]	2 mt_e+mn（2t_h+2t_a）=0.056m+0.036 mn	k（t_a+t_h）+3t_e=0.018k+0.084	3mt _p=29.7 m
文献[14]	2 mt_e+mn（t_h+t_m）=0.056 m+0.02 mn	k（t_m+t_h+t_e）=0.048k	3mt _p+t_e=29.7 m+0.028
本文	2 mt_e+mn（3t_h+t_m）=0.056 m+0.054 mn	t_e+k（3t_h+2t_m）=0.051k+0.028	（l+2）t _p+nlt_e=9.9l+0.028nl+18.8

多关键词动态可搜索加密方案

Dynamic multi-keyword searchable encryption scheme

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 16

相关文章 11

Metrics

推荐阅读 0

[1]	姜涛, 徐航, 王良民, 马建峰. 支持受损数据定位与恢复的动态群用户可证明存储[J]. 网络与信息安全学报, 2022, 8(5): 75-87.
[2]	周艺华, 扈新宇, 李美奇, 杨宇光. 云环境下基于属性策略隐藏的可搜索加密方案[J]. 网络与信息安全学报, 2022, 8(2): 112-121.
[3]	宋甫元, 秦拯, 张吉昕, 刘羽. 基于访问控制安全高效的多用户外包图像检索方案[J]. 网络与信息安全学报, 2021, 7(5): 29-39.
[4]	吴颖,李璇,金彪,金榕榕. 隐私保护的图像内容检索技术研究综述[J]. 网络与信息安全学报, 2019, 5(4): 14-28.
[5]	李颖, 马春光. 可搜索加密研究进展综述[J]. 网络与信息安全学报, 2018, 4(7): 13-21.
[6]	喻潇,田里,刘喆,王捷. 基于USBKEY的网络存储用户数据保护的研究与实现[J]. 网络与信息安全学报, 2018, 4(6): 62-69.
[7]	王元昊,李宏博,崔钰钊,郭庆文,黄琼. 具有密文等值测试功能的公钥加密技术综述[J]. 网络与信息安全学报, 2018, 4(11): 13-22.
[8]	朱智强,苏航,孙磊,李作辉. 云存储中基于属性的关键词搜索加密方案研究[J]. 网络与信息安全学报, 2017, 3(11): 1-11.
[9]	梁蛟,刘武,韩伟力,王晓阳,甘似禹,沈烁. 安卓云备份模块的代码安全问题分析[J]. 网络与信息安全学报, 2017, 3(1): 68-78.
[10]	冯涛,殷潇雨. 基于属性加密的云存储隐私保护机制研究[J]. 网络与信息安全学报, 2016, 2(7): 8-17.
[11]	徐鹏,金海. 可搜索加密的研究进展[J]. 网络与信息安全学报, 2016, 2(10): 8-16.