基于分层结构的匹配量隐藏加密多重映射方案

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

通信学报 ›› 2024, Vol. 45 ›› Issue (1): 94-105.doi: 10.11959/j.issn.1000-436x.2024002

• 学术论文 • 上一篇

基于分层结构的匹配量隐藏加密多重映射方案

陈晶, 李瀚星, 何琨, 加梦, 李雨晴, 杜瑞颖

武汉大学国家网络安全学院，湖北武汉 430040

修回日期:2023-10-19 出版日期:2024-01-01 发布日期:2024-01-01
作者简介:陈晶（1981- ），男，湖北武汉人，博士，武汉大学教授、博士生导师，主要研究方向为网络安全、应用密码学、分布式系统安全等
李瀚星（1999- ），男，天津人，武汉大学硕士生，主要研究方向为网络安全、应用密码学等
何琨（1986- ），男，湖北武汉人，博士，武汉大学副教授、博士生导师，主要研究方向为应用密码学、网络安全、云计算安全、人工智能安全、区块链安全等
加梦（1996- ），女，湖北随州人，武汉大学博士生，主要研究方向为区块链、应用密码学等
李雨晴（1991- ），女，江苏徐州人，博士，武汉大学副研究员、硕士生导师，主要研究方向为隐私计算、分布式学习、网络安全等
杜瑞颖（1964- ），女，河南新乡人，博士，武汉大学教授、博士生导师，主要研究方向为网络安全、隐私保护等
基金资助:
国家重点研发计划基金资助项目(2021YFB2700200);中央高校基本科研业务费专项资金资助项目(2042022kf1195);中央高校基本科研业务费专项资金资助项目(2042022kf0046);国家自然科学基金资助项目(62076187);国家自然科学基金资助项目(62172303);湖北省重点研发计划基金资助项目(2022BAA039);山东省重点研发计划基金资助项目(2022CXPT055)

Volume-hiding encrypted multi-map scheme based on hierarchical structure

Jing CHEN, Hanxing LI, Kun HE, Meng JIA, Yuqing LI, Ruiying DU

School of Cyber Science and Engineering, Wuhan University, Wuhan 430040, China

Revised:2023-10-19 Online:2024-01-01 Published:2024-01-01
Supported by:
The National Key Research and Development Program of China(2021YFB2700200);The Fundamental Research Funds for the Central Universities(2042022kf1195);The Fundamental Research Funds for the Central Universities(2042022kf0046);The National Natural Science Foundation of China(62076187);The National Natural Science Foundation of China(62172303);The Key Research and Development Program of Hubei Province(2022BAA039);The Key Research and Development Program of Shandong Province(2022CXPT055)

摘要/Abstract

摘要：

匹配量隐藏的加密多重映射（EMM）方案可以防止攻击者利用匹配量泄露推理搜索的明文，但是现有方案存在查询计算开销较大的问题。基于被检索数据的匹配量往往服从齐夫定律的特性，设计了一种分层结构的匹配量隐藏EMM方案。相对将全部键值匹配量填充至相等的朴素设计，所提方案将对整体数据的填充转为对多块子数据的填充，减少了存储开销，并实现了常数复杂度的查询开销。安全性分析表明，所提方案能够在查询结果无损的情况下实现匹配量隐藏。仿真结果表明，与当前最高效的方案XorMM相比，所提方案能够以增加10%的存储开销为代价，减小90%的查询计算开销，显著提高查询效率。

关键词: 云存储, 可搜索加密, 匹配量隐藏, 结构化加密, 分层结构

Abstract:

The volume-hiding encrypted multi-map (EMM) scheme is able to prevent attackers from inferring plaintext through the volume leakage, but existing solutions have problems with large storage and search computational costs.Based on the characteristic that the volume of the searched data often follows Zipf’s law, a hierarchical volume-hiding EMM scheme was proposed.Compared to the plain scheme that filled all keys’ volumes equally, converting the filling of the overall data into the filling of multiple sub-data blocks could reduce storage costs, and also achieved constant level complexity query overhead.Security analysis shows that the proposed scheme can achieve hidden matching volume without loss of query results.Simulation results show that compared with the most efficient scheme XorMM, the proposed scheme can increase the storage overhead by 10%, reduce the search computing overhead by 90%, and significantly improve the search efficiency.

Key words: cloud storage, searchable encryption, volume-hiding, structured encryption, hierarchical structure

中图分类号:

TP309

陈晶, 李瀚星, 何琨, 加梦, 李雨晴, 杜瑞颖. 基于分层结构的匹配量隐藏加密多重映射方案[J]. 通信学报, 2024, 45(1): 94-105.

Jing CHEN, Hanxing LI, Kun HE, Meng JIA, Yuqing LI, Ruiying DU. Volume-hiding encrypted multi-map scheme based on hierarchical structure[J]. Journal on Communications, 2024, 45(1): 94-105.

图/表 11

表1

图1

表2

图2

图3

表3

图4

图5

图6

图7

图8

参考文献 28

[1]	CHASE M , KAMARA S . Structured encryption and controlled disclosure[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2010: 577-594.
[2]	SONG D X , WAGNER D , PERRIG A . Practical techniques for searches on encrypted data[C]// Proceedings of IEEE Symposium on Security and Privacy. Piscataway:IEEE Press, 2002: 44-55.
[3]	CURTMOLA R , GARAY J , KAMARA S ,et al. Searchable symmetric encryption:improved definitions and efficient constructions[C]// Pro ceedings of the 13th ACM conference on Computer and communications security. New York:ACM Press, 2006: 79-88.
[4]	KAMARA S , MOATAZ T , OHRIMENKO O . Structuredencryption and leakage suppression[C]// Annual International Cryptology Conference. Cham:Springer, 2018: 339-370.
[5]	KAMARA S , MOATAZ T . SQL on Structurally-encrypted databases[C]// International Conference on the Theory and Application of Cryptology and Information Security. Cham:Springer, 2018: 149-180.
[6]	ISLAM M S , KUZU M , KANTARCIOGLU M . Access pattern disclosure on searchable encryption:ramification,attack and mitigation[C]// Network and Distributed System Security Symposium. Piscataway:IEEE Press, 2012: 1-15.
[7]	CASH D , GRUBBS P , PERRY J ,et al. Leakage-abuse attacks against searchable encryption[C]// Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2015: 668-679.
[8]	KELLARIS G , KOLLIOS G , NISSIM K ,et al. Generic attacks on secure outsourced databases[C]// Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2016: 1329-1340.
[9]	OYA S , KERSCHBAUM F . Hiding the access pattern is not enough:exploiting search pattern leakage in searchable encryption[J]. arXiv Preprint,arXiv:2010.03465, 2020.
[10]	BLACKSTONE L , KAMARA S , MOATAZ T . Revisiting leakage abuse attacks[C]// Network and Distributed System Security Symposium. Piscataway:IEEE Press, 2020: 1-18.
[11]	PODDAR R , WANG S , LU J N ,et al. Practical volume-based attacks on encrypted databases[C]// Proceedings of 2020 IEEE European Symposium on Security and Privacy (EuroS＆P). Piscataway:IEEE Press, 2020: 354-369.
[12]	GRUBBS P , LACHARITE M S , MINAUD B ,et al. Pump up the volume:practical database reconstruction from volume leakage on range queries[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2018: 315-331.
[13]	GUI Z C , PATERSON K G , PATRANABIS S . Rethinking searchable symmetric encryption[C]// Proceedings of 2023 IEEE Symposium on Security and Privacy (SP). Piscataway:IEEE Press, 2023: 1401-1418.
[14]	GARG S , MOHASSEL P , PAPAMANTHOU C . TWORAM:efficient oblivious ram in two rounds with applications to searchable encryption[C]// Annual International Cryptology Conference. Berlin:Springer, 2016: 563-592.
[15]	DEMERTZIS I , PAPADOPOULOS D , PAPAMANTHOU C ,et al. SEAL:attack mitigation for encrypted databases via adjustable leakage[C]// Proceedings of the 29th USENIX Conference on Security Symposium. New York:ACM Press, 2020: 2433-2450.
[16]	CHEN G X , LAI T H , REITER M K ,et al. Differentially private access patterns for searchable symmetric encryption[C]// Proceedings of IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2018: 810-818.
[17]	SHANG Z , OYA S , PETER A ,et al. Obfuscated access and search patterns in searchable encryption[J]. arXiv Preprint,arXiv:2102.09651, 2021.
[18]	REN K , GUO Y , LI J Q ,et al. HybrIDX:new hybrid index for volume-hiding range queries in data outsourcing services[C]// Proceedings of 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2021: 23-33.
[19]	KAMARA S , MOATAZ T . Computationally Volume-Hiding Structured Encryption[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham:Springer, 2019: 183-213.
[20]	PATEL S , PERSIANO G , YEO K ,et al. Mitigating leakage in secure cloud-hosted data structures:volume-hiding for multi-maps via hashing[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2019: 79-93.
[21]	JOOS M , ZIPF G K . The psycho-biology of language[J]. Language, 1936,12(3): 196.
[22]	GOLDREICH O , GOLDWASSER S , MICALI S . How to construct random functions[J]. Journal of the ACM, 1986,33(4): 792-807.
[23]	WANG J F , SUN S F , LI T C ,et al. Practical volume-hiding encrypted multi-maps with optimal overhead and beyond[C]// Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2022: 2825-2839.
[24]	GRAF T M , LEMIRE D . Xor filters:faster and smaller than bloom and cuckoo filters[J]. ACM Journal of Experimental Algorithmics, 2020,25: 1-16.
[25]	DEMERTZIS I , PAPADOPOULOS S , PAPAPETROU O ,et al. Practical private range search revisited[C]// Proceedings of the 2016 International Conference on Management of Data. New York:ACM Press, 2016: 185-198.
[26]	刘文心, 高莹 . 对称可搜索加密的安全性研究进展[J]. 信息安全学报, 2021,6(2): 73-84.
	LIU W X , GAO Y . A survey on security development of searchable symmetric encryption[J]. Journal of Cyber Security, 2021,6(2): 73-84.
[27]	NING J T , HUANG X Y , POH G S ,et al. LEAP:leakage-abuse attack on efficiently deployable,efficiently searchable encryption with partially known dataset[C]// Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2021: 2307-2320.
[28]	GUI Z C , JOHNSON O , WARINSCHI B . Encrypted databases:new volume attacks against range queries[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2019: 361-378.

方案	存储开销	通信开销	查询开销
直接填充	O(ml)	O(l)	O(1)
AVLH^[19]	O(n)	O(llogn)	O(llogn)
dprfMM^[20]	O(2(1+α)n)	O(2l)	O(2l)
XorMM^[23]	O(1.23n)	O(l)	O(l)
HEMM	O(1.35n)	O(l)	O(1)

键值	相关数据
key₁	v₁, v₂,v₃, v₄,v₅
key₂	v₆, v₇
key₃	v₈,v₉,v₁₀,v₁₁
key₄	v₁₂

分层数	键值个数
分层数	1×10³	5×10³	3×10⁴	1×10⁵	1×10⁷
m	7.49	9.09	10.90	12.09	16.69
3	19.51	30.65	49.64	68.13	221.93
5	13.98	19.82	28.46	35.88	83.07
10	10.63	13.89	18.13	21.33	37.67
15	9.71	12.23	15.31	17.82	28.81
20	9.26	11.54	14.36	16.35	25.33
25	9.07	11.20	14.05	15.63	23.35
30	8.94	10.96	13.40	15.17	22.21
40	8.80	10.70	12.95	14.54	20.97

基于分层结构的匹配量隐藏加密多重映射方案

Volume-hiding encrypted multi-map scheme based on hierarchical structure

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 28

相关文章 15

Metrics

推荐阅读 0

[1]	崔新华, 田有亮, 张起嘉. 高效的可验证无证书可搜索加密方案[J]. 通信学报, 2023, 44(8): 61-77.
[2]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[3]	谢晴晴, 杨念民, 冯霞. 基于区块链的噪声化数据分享控制协议[J]. 通信学报, 2023, 44(10): 198-212.
[4]	哈冠雄, 贾巧雯, 陈杭, 贾春福. 无第三方服务器的基于数据流行度的加密去重方案[J]. 通信学报, 2022, 43(8): 17-29.
[5]	杜瑞忠, 张玉晴, 李明月. 基于双向索引的高效连接关键字查询动态可搜索加密方案[J]. 通信学报, 2022, 43(5): 123-132.
[6]	冯涛, 孔繁琪, 柳春岩, 马蓉, Maher Albettar. 基于区块链的双重可验证云存储方案[J]. 通信学报, 2021, 42(12): 192-201.
[7]	郑东, 朱天泽, 郭瑞. 基于区块链的多用户环境中公钥可搜索加密方案[J]. 通信学报, 2021, 42(10): 140-152.
[8]	贾春福, 哈冠雄, 武少强, 陈杭, 李瑞琪. 加密去重场景下基于AONT和NTRU的密钥更新方案[J]. 通信学报, 2021, 42(10): 67-80.
[9]	牛淑芬,刘文科,陈俐霞,王彩芬,杜小妮. 基于联盟链的可搜索加密电子病历数据共享方案[J]. 通信学报, 2020, 41(8): 204-214.
[10]	杜瑞忠,谭艾伦,田俊峰. 基于区块链的公钥可搜索加密方案[J]. 通信学报, 2020, 41(4): 114-122.
[11]	田俊峰,王彦骉,何欣枫,张俊涛,杨万贺,庞亚南. 数据因果一致性研究综述[J]. 通信学报, 2020, 41(3): 154-167.
[12]	闫玺玺,原笑含,汤永利,陈艳丽. 基于区块链且支持验证的属性基搜索加密方案[J]. 通信学报, 2020, 41(2): 187-198.
[13]	柯文龙,王勇,叶苗,陈俊奇. Ceph云存储网络中一种业务优先级区分的多播流调度方法[J]. 通信学报, 2020, 41(11): 40-51.
[14]	孙磊,赵志远,王建华,朱智强. 云存储环境下支持属性撤销的属性基加密方案[J]. 通信学报, 2019, 40(5): 47-56.
[15]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.