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

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

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 11

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

方案	存储开销	通信开销	查询开销
直接填充	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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 28

Related Articles 15

Metrics

Recommended 0

[1]	Xinhua CUI, Youliang TIAN, Qijia ZHANG. Efficient certificateless searchable encryption scheme with verifiability [J]. Journal on Communications, 2023, 44(8): 61-77.
[2]	Tao FENG, Liqiu CHEN, Junli FANG, Jianming SHI. Blockchain data sharing scheme based on localized difference privacy and attribute-based searchable encryption [J]. Journal on Communications, 2023, 44(5): 224-233.
[3]	Qingqing XIE, Nianmin YANG, Xia FENG. Blockchain-based noisy data sharing control protocol [J]. Journal on Communications, 2023, 44(10): 198-212.
[4]	Guanxiong HA, Qiaowen JIA, Hang CHEN, Chunfu JIA. Data popularity-based encrypted deduplication scheme without third-party servers [J]. Journal on Communications, 2022, 43(8): 17-29.
[5]	Tao FENG, Fanqi KONG, Chunyan LIU, Rong MA, Albettar Maher. Dual verifiable cloud storage scheme based on blockchain [J]. Journal on Communications, 2021, 42(12): 192-201.
[6]	Chunfu JIA, Guanxiong HA, Shaoqiang WU, Hang CHEN, Ruiqi LI. AONT-and-NTRU-based rekeying scheme for encrypted deduplication [J]. Journal on Communications, 2021, 42(10): 67-80.
[7]	Dong ZHENG, Tianze ZHU, Rui GUO. Public key searchable encryption scheme in blockchain-enabled multi-user environment [J]. Journal on Communications, 2021, 42(10): 140-152.
[8]	Shufen NIU,Wenke LIU,Lixia CHEN,Caifen WANG,Xiaoni DU. Electronic medical record data sharing scheme based on searchable encryption via consortium blockchain [J]. Journal on Communications, 2020, 41(8): 204-214.
[9]	Ruizhong DU,Ailun TAN,Junfeng TIAN. Public key searchable encryption scheme based on blockchain [J]. Journal on Communications, 2020, 41(4): 114-122.
[10]	Junfeng TIAN,Yanbiao WANG,Xinfeng HE,Juntao ZHANG,Wanhe YANG,Ya’nan PANG. Survey on the causal consistency of data [J]. Journal on Communications, 2020, 41(3): 154-167.
[11]	Xixi YAN,Xiaohan YUAN,Yongli TANG,Yanli CHEN. Verifiable attribute-based searchable encryption scheme based on blockchain [J]. Journal on Communications, 2020, 41(2): 187-198.
[12]	Wenlong KE,Yong WANG,Miao YE,Junqi CHEN. Priority differentiated multicast flow scheduling method in Ceph cloud storage network [J]. Journal on Communications, 2020, 41(11): 40-51.
[13]	Lei SUN,Zhiyuan ZHAO,Jianhua WANG,Zhiqiang ZHU. Attribute-based encryption scheme supporting attribute revocation in cloud storage environment [J]. Journal on Communications, 2019, 40(5): 47-56.
[14]	Miaomiao TIAN,Chuang GAO,Jie CHEN. Identity-based cloud storage integrity checking from lattices [J]. Journal on Communications, 2019, 40(4): 128-139.
[15]	Xiangsong ZHANG,Chen LI,Zhenhua LIU. Key-exposure resilient integrity auditing scheme with encrypted data deduplication [J]. Journal on Communications, 2019, 40(4): 95-106.