基于改进Merkle-Tree认证方法的可验证多关键词搜索方案

doi:10.11959/j.issn.1000-436x.2020146

通信学报 ›› 2020, Vol. 41 ›› Issue (9): 118-129.doi: 10.11959/j.issn.1000-436x.2020146

基于改进Merkle-Tree认证方法的可验证多关键词搜索方案

田有亮^1,^2,³,骆琴^1,^3,⁴

¹ 公共大数据国家重点实验室（贵州大学），贵州贵阳 550025
² 贵州大学计算机科学与技术学院，贵州贵阳 550025
³ 贵州大学密码学与数据安全研究所，贵州贵阳 550025
⁴ 贵州大学数学与统计学院，贵州贵阳 550025

修回日期:2020-06-19 出版日期:2020-09-25 发布日期:2020-10-12
作者简介:田有亮（1982- ），男，贵州盘县人，博士，贵州大学教授、博士生导师，主要研究方向为算法博弈论、密码学与安全协议、大数据安全与隐私保护等|骆琴（1994- ），女，贵州贵阳人，贵州大学硕士生，主要研究方向为可搜索加密协议
基金资助:
教育部—中国移动科研基金资助项目(MCM20170401);国家自然科学基金资助项目(61772008);国家自然科学基金资助项目(U1836205);贵州省科技重大专项计划基金资助项目(20183001);贵州省科技计划基金资助项目（黔科合基础）([2019]1098);贵州省科技计划基金资助项目（黔科合平台人才）([2017]5788);贵州省科学技术基金资助项目（黔科合J字）([2008]2121)

Verifiable multi-keyword search scheme based on improved Merkle-Tree authentication method

Youliang TIAN^1,^2,³,Qin LUO^1,^3,⁴

¹ State Key Laboratory of Public Big Data (Guizhou University),Guiyang 550025,China
² College of Computer Science and Technology,Guizhou University,Guiyang 550025,China
³ Institute of Cryptography ＆Data Security,Guizhou University,Guiyang 550025,China
⁴ College of Mathematics and Statistics,Guizhou University,Guiyang 550025,China

Revised:2020-06-19 Online:2020-09-25 Published:2020-10-12
Supported by:
Ministry of Education-China Mobile Research Fund Project(MCM20170401);The National Natural Science Foundation of China(61772008);The National Natural Science Foundation of China(U1836205);Science and Technology Major Support Program of Guizhou Province(20183001);Guizhou Provincial Science and Technology Plan Project([2019]1098);Guizhou Provincial Science and Technology Plan Project([2017]5788);Science and Technology Foundation of Guizhou Province([2008]2121)

摘要/Abstract

摘要：

针对可搜索加密方案中的结果验证方法复杂，搜索成本高且效率低，难以满足多关键词搜索结果高效验证和安全性需求的问题，提出了基于改进的 Merkle-Tree 认证方法的多关键词搜索方案。首先，利用双线性映射构造多关键词的可搜索算法，实现高效精准的多关键词搜索；其次，基于Bawa改进的Merkle-Tree认证方法构造搜索方案的验证及动态更新算法，将计算成本从经典的MHT的O(n)降低到O(log n)，防止数据篡改、删除和伪造等不法操作的高效验证。在决策线性假设和CDH假设下，所提方案满足密文不可区分性和签名不可伪造性。

关键词: 云计算, 搜索隐私性, 有效验证, 动态更新

Abstract:

Aiming at the problem that the result verification method in the searchable encryption scheme was complicated,the search cost was high and the efficiency was low,it was difficult to meet the requirements of efficient verification and security of multi-keyword search results,a multi-keyword search scheme based on the improved Merkle-Tree authentication method was proposed.Firstly,a multi-keyword searchable algorithm was built to achieve efficient and accurate multi-keyword search by the bilinear mapping.Secondly,based on the improved Merkle-Tree authentication method of Bawa,the verification and dynamic update algorithm of the search scheme was constructed to reduce the calculation cost of the classic MHT to prevent the efficient verification and update of illegal operations such as data tampering,deletion,and forgery.Under the decision-type linear hypothesis and CDH hypothesis,the proof scheme meets the indistinguishability and unforgeability of ciphertext.

Key words: cloud computing, search privacy, valid verification, dynamic update

中图分类号:

TP309

田有亮,骆琴. 基于改进Merkle-Tree认证方法的可验证多关键词搜索方案[J]. 通信学报, 2020, 41(9): 118-129.

Youliang TIAN,Qin LUO. Verifiable multi-keyword search scheme based on improved Merkle-Tree authentication method[J]. Journal on Communications, 2020, 41(9): 118-129.

图/表 10

图1

图2

图3

图4

表1

表2

表3

图5

图6

图7

参考文献 25

[1]	MELL P , GRANCE T . The NIST definition of cloud computing[J]. National Institute of Standards and Technology, 2009,53(6): 50-53.
[2]	ARMBRUST M , FOX A , GRIFFITH R ,et al. A view of cloud computing[J]. Communications of the ACM, 2010,53(4): 50-58.
[3]	SAHAI A , WATERS B . Fuzzy identity-based encryption[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2005: 457-473.
[4]	SONG D X , WAGNER D , PERRIG A . Practical techniques for searches on encrypted data[C]// Proceeding 2000 IEEE Symposium on Security and Privacy. Piscataway:IEEE Press, 2000: 44-55.
[5]	GOH E J . Secure indexes[J]. IACR Cryptology ePrint Archive, 2003,6(12): 12-22.
[6]	CHANG Y C , MITZENMACHER M . Privacy preserving keyword searches on remote encrypted data[C]// Applied Cryptography and Network Security. Berlin:Springer, 2005: 442-455.
[7]	CURTMOLA R , GARAY J A , KAMARA S ,et al. Searchable symmetric encryption:improved definitions and efficient constructions[C]// ACM Conference Computer and Communication Security.New York:ACM Press. 2006: 376-379.
[8]	GOLLE P , STADDON J , WATERS B . Secure conjunctive keyword search over encrypted data[C]// International Conference on Applied Cryptography and Network Security. Berlin:Springer, 2004: 31-45.
[9]	ZHENG Q , LI X , AZGIN A . CLKS:certificateless keyword search on encrypted data[C]// International Conference on Network and System Security. Berlin:Springer, 2015: 239-253.
[10]	ZHANG W , LIN Y , XIAO S ,et al. Privacy preserving ranked multi-keyword search for multiple data owners in cloud computing[J]. IEEE Transactions on Computers, 2015,65(5): 1566-1577.
[11]	YANG Y , MA M . Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for e-health clouds[J]. IEEE Transactions on Information Forensics and Security, 2015,11(4): 746-759.
[12]	SHEN J , SHEN J , CHEN X ,et al. An efficient public auditing protocol with novel dynamic structure for cloud data[J]. IEEE Transactions on Information Forensics and Security, 2017,12(10): 2402-2415.
[13]	SUN W , WANG B , CAO N ,et al. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,25(11): 3025-3035.
[14]	WANG J , CHEN X , HUANG X ,et al. Verifiable auditing for outsourced database in cloud computing[J]. IEEE Transactions on Computers, 2015,64(11): 3293-3303.
[15]	CHUM C S , ZHANG X . A new bloom filter structure for searchable encryption schemes[C]// Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy. New York:ACM Press, 2017: 143-145.
[16]	MIAO Y , WENG J , LIU X ,et al. Enabling verifiable multiple keywords search over encrypted cloud data[J]. Information Sciences, 2018,465(10): 21-37.
[17]	BONEH D , CRESCENZO G D , OSTROVSKY R ,et al. Public key encryption with keyword search[C]// International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2004: 506-522.
[18]	GUO Y , LI J , ZHANG Y ,et al. Hierarchical attribute-based encryption with continuous auxiliary inputs leakage[J]. Security ＆ Communication Networks, 2016,9(18): 4852-4862.
[19]	MIAO Y , MA J , LIU X ,et al. Practical attribute-based multi-keyword search scheme in mobile crowdsourcing[J]. IEEE Internet of Things Journal, 2017,5(4): 3008-3018.
[20]	KUROSAWA K , OHTAKI Y . How to update documents verifiably in searchable symmetric encryption[C]// International Conference on Cryptology and Network Security. Berlin:Springer, 2013: 309-328.
[21]	KUROSAWA K , . Garbled searchable symmetric encryption[C]// International Conference on Financial Cryptography and Data Security. Berlin:Springer, 2014: 234-251.
[22]	GARG N , BAWA S . RITS-MHT:relative indexed and time stamped Merkle Hash tree based data auditing protocol for cloud computing[J]. Journal of Network and Computer Applications, 2017,84: 1-13.
[23]	杨波 . 密码学中的可证明安全性[M]. 北京: 清华大学出版社, 2017.
	YANG B . Provable security in cryptography[M]. Beijing: Tsinghua University PressPress, 2017.
[24]	ZHENG Q , LI X , AZGIN A . CLKS:certificateless keyword search on encrypted data[C]// International Conference on Network and System Security. Berlin:Springer, 2015: 239-253.
[25]	MIAO Y , MA J , LIU X ,et al. VMKDO:verifiable multi-keyword search over encrypted cloud data for dynamic data-owner[J]. Peer-to-peer Networking and Applications, 2018,11(2): 287-297.

符号	含义
\|u\|	数据用户的大小
E	幂指数操作
n	数据块的大小
m	每条记录的关键词字段的大小
P	配对操作
l	关键词数量
d	搜索结果的数量

方案	KeyGen	Enc	Trap	Search	Verify
文献[9]方案	2\|u\|E	(8+m)E	(9+l)E	lP+ 3P	—
文献[16]方案	2\|u\|E+ E2	(10+m)E+H_o	10E	lP+ 3P	lP+ 3P
文献[25]方案	(\|DO\|+1)E	(m+5+2n)E+nH ₁+3P	2E	2P+3E	(d+1)E+dH ₁+2P
本文方案	\|n\|E+ E3	10 E+nE	(9+l)E	4P	nE+ P 4

方案	数据保密性	可验证查询完整性	支持多关键词搜索	搜索隐私性	支持动态更新
文献[9]方案	是	否	是	是	否
文献[16]方案	是	是	是	是	否
文献[25]方案	是	是	是	是	是
本文方案	是	是	是	是	是

基于改进Merkle-Tree认证方法的可验证多关键词搜索方案

Verifiable multi-keyword search scheme based on improved Merkle-Tree authentication method

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 25

相关文章 15

Metrics

推荐阅读 0

[1]	马玲, 樊漆亮, 许婷, 郭冠琛, 张圣林, 孙永谦, 张玉志. 基于强化学习的在线离线混部云环境下的调度框架[J]. 通信学报, 2023, 44(6): 90-102.
[2]	王化群, 刘哲, 何德彪, 李继国. 公有云中身份基多源IoT终端数据PDP方案[J]. 通信学报, 2021, 42(7): 52-60.
[3]	张键红, 武梦龙, 王晶, 刘沛, 姜正涛, 彭长根. 云环境下安全的可验证多关键词搜索加密方案[J]. 通信学报, 2021, 42(4): 139-149.
[4]	李瑞琪, 贾春福, 王雅飞. 基于NTRU的多密钥同态代理重加密方案及其应用[J]. 通信学报, 2021, 42(3): 11-22.
[5]	张嘉伟, 马建峰, 马卓, 李腾. 云计算中基于时间和隐私保护的可撤销可追踪的数据共享方案[J]. 通信学报, 2021, 42(10): 81-94.
[6]	王文娟, 杜学绘, 单棣斌. 基于动态概率攻击图的云环境攻击场景构建方法[J]. 通信学报, 2021, 42(1): 1-17.
[7]	王娜,郑坤,付俊松,李剑. 基于分块的移动边缘计算密文检索方法[J]. 通信学报, 2020, 41(7): 95-102.
[8]	赵临东,庄文芹,陈建新,周亮. 异构蜂窝网络中分层任务卸载：建模与优化[J]. 通信学报, 2020, 41(4): 34-44.
[9]	梁冰,纪雯. 基于次模优化的边云协同多用户计算任务迁移方法[J]. 通信学报, 2020, 41(10): 25-36.
[10]	苏命峰,王国军,李仁发. 基于利益相关视角的多维QoS云资源调度方法[J]. 通信学报, 2019, 40(6): 102-115.
[11]	陈兴蜀,滑强,王毅桐,葛龙,朱毅. 云环境下SDN网络低速率DDoS攻击的研究[J]. 通信学报, 2019, 40(6): 210-222.
[12]	王万良, 臧泽林, 陈国棋, 屠杭垚, 王宇乐, 陆琳彦. 大规模云计算服务器优化调度问题的最优二元交换算法研究[J]. 通信学报, 2019, 40(5): 180-191.
[13]	王田,沈雪微,罗皓,陈柏生,王国军,贾维嘉. 基于雾计算的可信传感云研究进展[J]. 通信学报, 2019, 40(3): 170-181.
[14]	何欣枫,田俊峰,刘凡鸣. 可信云平台技术综述[J]. 通信学报, 2019, 40(2): 154-163.
[15]	朱智强,林韧昊,胡翠云. 基于数字证书的openstack身份认证协议[J]. 通信学报, 2019, 40(2): 188-196.