面向尺寸模式保护的高效对称可搜索加密方案

doi:10.3969/j.issn.1671-1122.2024.06.003

信息网络安全 ›› 2024, Vol. 24 ›› Issue (6): 843-854.doi: 10.3969/j.issn.1671-1122.2024.06.003

面向尺寸模式保护的高效对称可搜索加密方案

李强¹^,², 沈援海², 刘天旭³(), 黄晏瑜³, 孙建国³

1.西安电子科技大学计算机科学与技术学院，西安 710071
2.中移（杭州）信息技术有限公司，杭州 310023
3.西安电子科技大学杭州研究院，杭州 311231

收稿日期:2024-02-28 出版日期:2024-06-10 发布日期:2024-07-05
通讯作者: 刘天旭 23151214343@stu.xidian.edu.cn
作者简介:李强（1986—），男，陕西，高级工程师，博士研究生，主要研究方向为智慧家庭、光通信和人工智能|沈援海（1986—），男，江苏，工程师，硕士，主要研究方向为智慧家庭、人工智能和信息安全|刘天旭（2000—），男，陕西，硕士研究生，主要研究方向为密码学、人工智能和信息安全|黄晏瑜（1993—），女，浙江，讲师，博士，CCF会员，主要研究方向为密码学和信息安全|孙建国（1981—），男，浙江，教授，博士，CCF高级会员，主要研究方向为工业信息安全和智能安全
基金资助:
国家自然科学基金(62302365);网络与信息安全安徽省重点实验室开放课题(AHNIS2022004);中移（杭州）2023-2024年工业互联网标识与平台互通中间件联合测试验收项目(CMHY-202300856)

Efficient Searchable Symmetric Encryption Scheme for Size Pattern Protection

LI Qiang¹^,², SHEN Yuanhai², LIU Tianxu³(), HUANG Yanyu³, SUN Jianguo³

1. School of Computer Science and Technology, Xidian University, Xi’an 710071, China
2. China Mobile (Hangzhou) Information Technology Co., Ltd., Hangzhou 310023, China
3. Hangzhou Research Institute, Xidian University, Hangzhou 311231, China

Received:2024-02-28 Online:2024-06-10 Published:2024-07-05

摘要/Abstract

摘要：

近年来，随着云服务的普及以及对数据安全保护需求的增加，动态对称可搜索加密（DSSE）由于可以在加密数据库中进行更新和查询的特点而受到学界广泛关注。由于考虑搜索和更新效率，DSSE通常需要泄露一些信息，主要包括搜索模式、访问模式和尺寸模式。目前，主要使用不经意随机访问机（ORAM）来保护搜索模式和访问模式，但ORAM无法保证尺寸模式泄露的安全性。文章说明了尺寸模式泄露的危害，并基于现有DSSE隐私概念提出了强前后向隐私，以达到对尺寸模式的保护目的。基于这种增强的安全性目标，文章提出了一种面向尺寸模式保护的高效对称可搜索加密方案Eurus，旨在解决现有方案中的尺寸模式泄露问题。Eurus通过结合多服务器ORAM架构、更新槽机制和细树路径淘汰技术，提供了强正向和反向隐私保护，防止敏感关键字和文件信息被泄露。多服务器ORAM隐藏了搜索和访问模式，更新槽机制混淆了文件标识符，细树路径淘汰技术打乱了文件的实际排列顺序。实验结果表明，Eurus在实现隐私保护的同时，提高了搜索和更新效率，搜索性能较现有方案提升了约46%，更新性能提升了4.73倍。

关键词: 可搜索加密, 尺寸模式, ORAM

Abstract:

In recent years, with the popularity of cloud services and the increasing demand for data security protection, dynamic searchable symmetric encryption (DSSE) has attracted widespread attention from academia due to its ability to update and query in encrypted databases. Due to considerations of search and update efficiency, DSSE often needs to disclose some information, mainly search pattern, access pattern, and size pattern. At present, the main use of oblivious random access machine (ORAM) is to protect search and access pattern, but ORAM cannot guarantee the security of size pattern leakage. The article explained the harm of size pattern leakage to security and extended the existing DSSE privacy concept to achieve protection of size patterns, namely proposing strong forward backward privacy. Based on this enhanced security objective, the article proposed an efficient searchable symmetric encryption scheme for size pattern protection named Eurus, aiming to solve the size pattern leakage problem in existing solutions. By combining multi-server ORAM architecture, update slot mechanism and fine tree path elimination technology, Eurus provided strong forward and reversed privacy protection to prevent the disclosure of sensitive keywords and file information. Multi-server ORAM hided search and access patterns, update slots confuse file identifiers, and fine tree path elimination techniques disrupted the actual order of files. The experimental results show that Eurus improves the search and update efficiency while maintaining privacy, improving the search performance by about 46% compared with the existing scheme, and improving the update performance by 4.73 times.

Key words: searchable encryption, size pattern, ORAM

中图分类号:

TP309

李强, 沈援海, 刘天旭, 黄晏瑜, 孙建国. 面向尺寸模式保护的高效对称可搜索加密方案[J]. 信息网络安全, 2024, 24(6): 843-854.

LI Qiang, SHEN Yuanhai, LIU Tianxu, HUANG Yanyu, SUN Jianguo. Efficient Searchable Symmetric Encryption Scheme for Size Pattern Protection[J]. Netinfo Security, 2024, 24(6): 843-854.

图/表 5

参考文献 39

[1]	SONG Xiaoding, WAGNER D, PERRIG A. Practical Techniques for Searches on Encrypted Data[C]// IEEE. 2000 IEEE Symposium on Security and Privacy. New York: IEEE, 2000: 44-55.
[2]	HAHN F, KERSCHBAUM F. Searchable Encryption with Secure and Efficient Updates[C]// ACM. 2014 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2014: 310-320.
[3]	STEFANOV E, PAPAMANTHOU C, SHI E. Practical Dynamic Searchable Encryption with Small Leakage[EB/OL]. (2014-02-23)[2024-01-13]. https://eprint.iacr.org/2013/832.
[4]	CURTMOLA R, GARAY J, KAMARA S, et al. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions[J]. Computer Security, 2011, 19(5): 895-934.
[5]	ISLAM M, KUZU M, KANTARCIOGLU M. Access Pattern Disclosure on Searchable Encryption: Ramification, Attack and Mitigation[EB/OL]. (2012-02-06)[2024-01-13]. https://personal.utdallas.edu/-mxk055100/publications/ndss2012.pdf.
[6]	CASH D, GRUBBS P, PERRY J, et al. Leakage-Abuse Attacks against Searchable Encryption[C]// ACM. The 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 668-679.
[7]	ZHANG Yupeng, KATZ J, PAPAMANTHOU C. All Your Queries are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption[C]// ACM. The 25th USENIX Conference on Security Symposium. New York: ACM, 2016: 707-720.
[8]	NING Jianting, XU Jia, ZHANG Fan, et al. Passive Attacks against Searchable Encryption[J]. IEEE Transactions on Information Forensics and Security, 2018, 14(3): 789-802.
[9]	POULIOT D, WRIGHT C V. The Shadow Nemesis: Inference Attacks on Efficiently Deployable, Efficiently Searchable Encryption[C]// ACM. 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1341-1352.
[10]	KORNAROPOULOS E M, PAPAMANTHOU C, TAMASSIA R. The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution[C]// IEEE. 2020 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2020: 118-131.
[11]	MARKATOU E A, TAMASSIA R. Full Database Reconstruction with Access and Search Pattern Leakage[C]// ACM. Information Security:22nd International Conference (ISC 2019). New York: ACM, 2019: 25-43.
[12]	BOST R. ∑oφoς: Forward Secure Searchable Encryption[C]// ACM. The 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1143-1154.
[13]	LAI R W F, CHOW S S M. Forward-Secure Searchable Encryption on Labeled Bipartite Graphs[C]// Springer. 2017 International Conference on Applied Cryptography and Network Security (ACNS 2017). Heidelberg: Springer, 2017: 478-497.
[14]	ETEMAD M, KUPCU A, PAPAMANTHOU C, et al. Efficient Dynamic Searchable Encryption with Forward Privacy[C]// ACM. The Twelfth ACM Conference on Data and Application Security and Privacy. New York: ACM, 2018: 312-323.
[15]	BOSY R, MINAUD B, OHRIMENKO O. Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1465-1482.
[16]	GHAREH J, PAPADOPOULOS D, PAPAMANTHOU C, et al. New Constructions for Forward and Backward Private Symmetric Searchable Encryption[C]// ACM. The 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1038-1055.
[17]	SONG Xiangfu, DONG Changyu, YUAN Dandan, et al. Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 17(5): 912-927.
[18]	LI Jin, HUANG Yanyu, YU Wei, et al. Searchable Symmetric Encryption with Forward Search Privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(1): 460-474.
[19]	GARG S, MOHASSEL P, PAPAMANTHOU C. TWORAM: Efficient Oblivious RAM in Two Rounds with Applications to Searchable Encryption[C]// Springer. 36th Annual International Cryptology Conference (CRYPTO 2016). Heidelberg: Springer, 2016: 563-592.
[20]	HOANG T, OZKAPTAN C D, YAVUZ A A, et al. S³ORAM: A Computation-Efficient and Constant Client Bandwidth Blowup ORAM with Shamir Secret Sharing[C]// ACM. 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 491-505.
[21]	WANG Xiao, CHAN H, SHI E. Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound[C]// ACM. 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 850-861.
[22]	DEVADAS S, VAN D M, FLETCHER C W, et al. Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM[C]// Springer. 2016 Theory of Cryptography Conference (TCC 2016). Heidelberg: Springer, 2016: 145-174.
[23]	REN Ling, FLETCHER C, KWON A, et al. Constants Count: Practical Improvements to Oblivious {RAM}[C]// USENIX. 24th USENIX Security Symposium (USENIX Security 15). Berlin:USENIX, 2015: 415-430.
[24]	STEFANOV E, VAN D M, SHI E, et al. Path ORAM: An Extremely Simple Oblivious RAM Protocol[C]// ACM. 2013 ACM SIGSAC Conference on Computer & Communications Security. New York: ACM, 2013: 299-310.
[25]	MISHRA P, PODDAR R, CHIESA A, et al. Oblix: An Efficient Oblivious Search Index[C]// IEEE. 2018 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2018: 279-296.
[26]	NAVEED M. The Fallacy of Composition of Oblivious RAM and Searchable Encryption[EB/OL]. (2015-07-05)[2024-01-13]. https://eprint.iacr.org/2015/668.pdf.
[27]	SHAFIEE A, BALASUBRAMONIAN R, TIWARI M, et al. Secure DIMM: Moving ORAM Primitives Closer to Memory[C]// IEEE. IEEE International Symposium on High Performance Computer Architecture (HPCA). New York: IEEE, 2018: 428-440.
[28]	GARG S, MOHASSEL P, PAPAMANTHOU C. TWORAM: Efficient Oblivious RAM in Two Rounds with Applications to Searchable Encryption[C]// Springer. 36th Annual International Cryptology Conference (CRYPTO 2016). Heidelberg: Springer, 2016: 563-592.
[29]	BLACKSTONE L, KAMARA S, MOATAZ T. Revisiting Leakage Abuse Attacks[EB/OL]. (2019-10-10)[2024-01-13]. https://eprint.iacr.org/2019/1175.
[30]	KELLARIS G, KOLLIOS G, NISSIM K, et al. Generic Attacks on Secure Outsourced Databases[C]// ACM. 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1329-1340.
[31]	GRUBBS P, MINAUD B, PATERSON K G. Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries[C]// ACM. 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 315-331.
[32]	GUI Zichen, JOHNSON O, WARINSCHI B. Encrypted Databases: New Volume Attacks against Range Queries[C]// ACM. 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 361-378.
[33]	PODDAR R, WANG S, LU Jianan, et al. Practical Volume-Based Attacks on Encrypted Databases[C]// IEEE. 2020 IEEE European Symposium on Security and Privacy (EuroS&P). New York: IEEE, 2020: 107-123.
[34]	SHAMIR A. How to Share a Secret[J]. Communications of the ACM, 1979, 22(11): 612-613.
[35]	LEE J, JANG J, JANG Y, et al. Hacking in Darkness: Return Oriented Programming against Secure Enclaves[C]// USENIX. The 26th USENIX Conference on Security Symposium. Berlin:USENIX, 2017: 523-539.
[36]	GOTZFRIED J, ECKERT M, SCHINZEL S, et al. Cache Attacks on Intel SGX[C]// ACM. The 10th European Workshop on Systems Security. New York: ACM, 2017: 101-106.
[37]	CHEN Hao, CHILLOTTI I, REN Lin. Onion Ring ORAM: Efficient Constant Bandwidth Oblivious RAM from (Leveled) TFHE[C]// ACM. The 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 345-360.
[38]	BINDSCHAEDLER V, NAVEED M, PAN X, et al. Practicing Oblivious Access on Cloud Storage: the Gap, the Fallacy, and the New Way Forward[C]// ACM. The 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 837-849.
[39]	CHOR B, GOLDREICH O, KUSHILEVITZ E, et al. Private Information Retrieval[C]// IEEE. Proceedings of IEEE 36th Annual Foundations of Computer Science. New York: IEEE, 1995: 41-50.

测试次数/次	搜索时间/s		更新时间/s
测试次数/次	SPS14	本文方案	本文方案	GOSSE
1	750	35740	172668	46867
2	682	36540	161435	44174
3	743	35344	232788	64278
4	800	36450	212527	57373
5	754	36193	228534	64643

面向尺寸模式保护的高效对称可搜索加密方案

Efficient Searchable Symmetric Encryption Scheme for Size Pattern Protection

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 39

相关文章 13

编辑推荐

Metrics

本文评价

[1]	叶清, 何俊霏, 杨智超. 基于格的可搜索公钥加密研究进展[J]. 信息网络安全, 2024, 24(6): 903-916.
[2]	秦宝东, ，陈从正, ，何俊杰, 郑东. 基于可验证秘密共享的多关键词可搜索加密方案[J]. 信息网络安全, 2023, 23(5): 32-40.
[3]	李春晓, 王耀飞, 徐恩亮, 赵钰. 基于双线性映射的区块链安全范围搜索技术研究[J]. 信息网络安全, 2023, 23(3): 22-34.
[4]	王健, 黄俊. 基于智能合约的日志安全存储与公平访问方法[J]. 信息网络安全, 2022, 22(7): 27-36.
[5]	涂国庆, 杨延浩, 刘树波. Geohash编码抗k近邻攻击的脆弱性分析[J]. 信息网络安全, 2021, 21(2): 10-15.
[6]	张应辉, 朱甜, 郑东. 基于区块链的多关键字细粒度可搜索加密方案[J]. 信息网络安全, 2021, 21(2): 34-44.
[7]	周权, 杨宁滨, 许舒美. 基于FBDH算法的容错可验证公钥可搜索加密方案[J]. 信息网络安全, 2020, 20(3): 29-35.
[8]	张玉磊, 刘祥震, 郎晓丽, 王彩芬. 云环境下基于无证书的多服务器可搜索加密方案[J]. 信息网络安全, 2019, 19(3): 72-80.
[9]	陈兰香, 邱林冰. 基于Merkle哈希树的可验证密文检索方案[J]. 信息网络安全, 2017, 17(4): 1-8.
[10]	张楠, 陈兰香. 一种高效的支持排序的关键词可搜索加密系统研究[J]. 信息网络安全, 2017, 17(2): 43-50.
[11]	陆海宁. 可隐藏搜索模式的对称可搜索加密方案[J]. 信息网络安全, 2017, 17(1): 38-42.
[12]	. 基于密文的中文关键词模糊搜索方案[J]. , 2014, 14(7): 69-.
[13]	王保民;何智灵;罗文俊. 基于云存储的多用户可搜索加密方案[J]. , 2013, 13(12): 0-0.