一种支持属性撤销的top-k多关键词密文检索方案

doi:10.19665/j.issn1001-2400.2022.01.003

摘要/Abstract

摘要：

近年来,云计算的推广使得可搜索加密技术得到极大发展。然而,现有的大部分可搜索加密技术普遍只支持单关键字搜索和遍历密文检索,搜索过程不能根据用户需求进行筛选和检索,不支持属性撤销,会返回大量无关数据以至于影响搜索用户体验。为了解决以上问题,提出一种支持属性撤销的top-k多关键词密文检索方案。在支持多关键字检索的基础上,通过属性基算法的访问策略和语义模型,构建属性-文件集映射的索引表,实现对密文的细粒度访问控制和权限管理,支持top-k排序和高效检索;引入同态加密模糊数据参数,保证加密数据隐私和多用户属性授权,多层数据压缩降低存储开销,能够低计算开销实现属性撤销。通过理论分析表明,该方案具有前后向安全性和关键词隐藏,能够抵抗共谋攻击,并且与同类方案进行功能和实验评估,结果证明该方案在功能和效率方面具有较好的综合性能。

关键词: 可搜索加密, 同态加密, 属性基加密, 属性撤销, top-k排序

Abstract:

In recent years,the promotion of cloud computing has led to the great development of searchable encryption technology.However,most of the existing searchable encryption technologies generally only support single-keyword search and traversal ciphertext retrieval.The search process cannot be filtered and retrieved according to user needs,and does not support attribute revocation,which will return a large amount of irrelevant data and affect search users' experience.In order to solve the above problems,a top-k multi-keyword ciphertext retrieval scheme for supporting attribute revocation is proposed.On the basis of supporting multi-keyword retrieval,through the access strategy and semantic model of the attribute-based algorithm,the index table of attribute-file set mapping is constructed to realize fine-grained access control and authority management of the ciphertext,and supports top-k sorting and efficient retrieval.Homomorphic encrypted fuzzy data parameters are introduced to ensure encrypted data privacy and multi-user attribute authorization.Multi-layer data compression reduces the storage overhead,and can achieve attribute revocation with a low computational overhead.Theoretical analysis shows that the scheme has forward and backward security and keyword hiding,and can resist collusion attacks.The function and experimental evaluation of similar schemes have been carried out.The results prove that the scheme has a better comprehensive performance in terms of function and efficiency.

Key words: searchable encryption, homomorphic encryption, attribute based encryption, attribute revocation, top-k sorting

中图分类号:

TN918.4

王凯文,王树兰,王海燕,丁勇. 一种支持属性撤销的top-k多关键词密文检索方案[J]. 西安电子科技大学学报, 2022, 49(1): 26-34.

WANG Kaiwen,WANG Shulan,WANG Haiyan,DING Yong. Top-k multi-keyword ciphertext retrieval scheme supporting attribute revocation[J]. Journal of Xidian University, 2022, 49(1): 26-34.

图/表 12

图1

图2

表1

表2

表3

存储开销"

方案	KeyGen(\|SK\|)	IndexGen(\|I\|)	Token(\|I'\|)
Jin	(4+\|A_u\|)L_G	\|ω $k e y$ \|3L_G	(∏_\|_k_\|L_G+2)L_G
CAO	(3+2\|A_u\|)L_G	\|ω $k e y$ \|L_G $∏ \| A c \|$ L_G	(\|k\|+2\|A_u\|)L_G
Fateh	(1+2\|A_u\|)L_G	\|ω $k e y$ \|2 $L Z P$	3\|k\| $L Z P$
TKRS	(1+2\|A_u\|)L_G	\|ω $k e y$ \| $L Z P$	\|k\| $L Z P$

表3

表4

图3

图4

图5

图6

图7

图8

参考文献 20

[1]	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.Piscataway:IEEE, 2000:44-55.
[2]	GOH E J. Secure Indexes (2003)[J/OL]. [2003-10-07]. https://eprint.iacr.org/2003/216.
[3]	CAO N, WANG C, LI M, et al. Privacy-Preserving Multi-Keyword Ranked Search over Encrypted Cloud Data[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1):222-233. doi: 10.1109/TPDS.2013.45
[4]	MIAO Y, MA J, LIU X, et al. Practical Attribute-Based Multi-Keyword Search Scheme in Mobile Crowdsourcing[J]. IEEE Internet of Things Journal, 2018, 5(4):3008-3018. doi: 10.1109/JIOT.2017.2779124
[5]	SAHAI A, WATERS B. Fuzzy Identity-Based Encryption[C]// Advances in Cryptoloty-EUROCRYPT 2005. New York: ACM, 2005,457-473.
[6]	ZHAO Y, REN M, JIANG S, et al. An Efficient and Revocable Storage CP-ABE Scheme in the Cloud Computing[J]. Computing, 2019, 101(8):1041-1065. doi: 10.1007/s00607-018-0637-2
[7]	WATERS B. Ciphertext-Policy Attribute-Based Encryption (2011)[J/OL]. [2011-12-31]. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=07869BBF42253321C865E1EE1EFC6FC2?doi=10.1.1.119.2179&rep=rep1&type=pdf.
[8]	JUNBEOM H. Improving Security and Efficiency in Attribute-Based Data Sharing[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10):2271-2282. doi: 10.1109/TKDE.2011.78
[9]	CHEN N, LI J, ZHANG Y, et al. Efficient CP-ABE Scheme with Shared Decryption in Cloud Storage[J]. IEEE Transactions on Computers, 2020 ( Early Access ):1-11.
[10]	HUI C, DENG R H, LAI J, et al. An Efficient and Expressive Ciphertext-Policy Attribute-Based Encryption Scheme with Partially Hidden Access Structures,Revisited[J]. Computer Networks, 2018, 133:157-165. doi: 10.1016/j.comnet.2018.01.034
[11]	GENTRY C. A Fully Homomorphic Encryption Scheme[M]. Stanford: Stanford University, 2009:1-209.
[12]	COMINETTI E L, SIMPLICIO M A. Fast Additive Partially Homomorphic Encryption From the Approximate Common Divisor Problem[J]. IEEE Transactions on Information Forensics and Security, 2020, 15:2988-2998. doi: 10.1109/TIFS.2020.2981239
[13]	孙霓刚, 朱浩然, 汪伟昕. 一种适用于n bit的整数上全同态加密方案[J]. 计算机应用研究, 2018, 35(4):1179-1181.
	SUN Nigang, ZHU Haoran, WANG Weixin. Fully Homomorphic Encryption Scheme Applied to n bit[J]. Application Research of Computers, 2018, 35(4):1179-1181.
[14]	DUMAIS S T. Latent Semantic Analysis[J]. Annual Review of Information Science & Technology, 2013, 4(6):683-692.
[15]	ZHU Z, LIANG J, LI D, et al. Hot Topic Detection Based on a Refined TF-IDF Algorithm[J]. IEEE Access, 2019, 7:26996-27007. doi: 10.1109/ACCESS.2019.2893980
[16]	SUN J, REN L, WANG S, et al. Multi-Keyword Searchable and Data Verifiable Attribute-Based Encryption Scheme for Cloud Storage[J]. IEEE Access, 2019, 7:66655-66667. doi: 10.1109/ACCESS.2019.2917772
[17]	CAO L, KANG Y, WU Q, et al. Searchable Encryption Cloud Storage with Dynamic Data Update to Support Efficient Policy Hiding[J]. China Communications, 2020, 17(6):153-163. doi: 10.23919/JCC.2020.06.013
[18]	BOUCENNA F, NOUALI O, KECHID S, et al. Secure Inverted Index Based Search over Encrypted Cloud Data with User Access Rights Management[J]. Journal of Computer Science and Technology, 2019, 34(1):133-154. doi: 10.1007/s11390-019-1903-2
[19]	李涵, 张晨, 黄荷姣, 等. 一种支持前向安全更新和验证的加密搜索算法[J]. 西安电子科技大学学报, 2020, 47(5):48-56.
	LI Han, ZHANG Chen, HUANG Hejiao, et al. Algorithm for Encrypted Search with Forward Secure Updates and Verification[J]. Journal of Xidian University, 2020, 47(5):48-56.
[20]	ZHOU Y, ZHENG S, WANG L. Privacy-Preserving and Efficient Public Key Encryption with Keyword Search Based on CP-ABE in Cloud[J]. Cryptography, 2020, 4(4):28. doi: 10.3390/cryptography4040028

方案	加密算法	密文检索	访问控制	属性撤销	检索聚类	前后向安全性
Jin	Cp-abe	限制关键字遍历	信任第三方	YES	NO	NO
CAO	Cp-abe+paillier	满足最低关键字	链表结构+签名集	NO	NO	NO
Fateh	Cp-abe+homo	文档-用户双表	同态+倒排索引	NO	YES	NO
TKRS	Cp-abe+homo	属性-文档表	同态+策略树	YES	YES	YES

符号	含义	符号	含义
G	群上的运算操作	A_c	出现在密文CT中的属性
S	满足一个访问结构最少的内部节点	A_u	用户U的属性
Z_P	素数秩为P的群{0,1,...,p-1}	L_*	元素在*上的比特长度
C_e	e操作,e表示双线性对	\|*\|	元素在*上的个数
ωkey	待加密明文中的关键字集合	n	待加密明文文件数
M	大素数乘法运算	k	用户检索的关键字集合
d	系统中的属性个数

方案	KeyGen(\|SK\|)	IndexGen(\|I\|)	Token(\|I'\|)
Jin	(4+\|A_u\|)L_G	\|ω $k e y$ \|3L_G	(∏_\|_k_\|L_G+2)L_G
CAO	(3+2\|A_u\|)L_G	\|ω $k e y$ \|L_G $∏ \| A c \|$ L_G	(\|k\|+2\|A_u\|)L_G
Fateh	(1+2\|A_u\|)L_G	\|ω $k e y$ \|2 $L Z P$	3\|k\| $L Z P$
TKRS	(1+2\|A_u\|)L_G	\|ω $k e y$ \| $L Z P$	\|k\| $L Z P$

方案	KeyGen	Search	DecDU	Update
Jin	(4+\|A_u\|)G	C_enM	2∏_SC_e+C_eM	dG
CAO	(4+2\|A_u\|)G	(4+S)nM	C_eM	dG
Fateh	(1+2\|A_u\|)G	3nM	∏_SC_e+C_eM
TKRS	(1+2\|A_u\|)G	nM	C_eM	dM