A Multi-Keyword Dynamic Symmetric Searchable Encryption Scheme Based on SGX

doi:10.3969/j.issn.1671-1122.2026.06.003

Abstract

Abstract:

With the widespread adoption of cloud computing, user data security faces significant challenges, especially during data storage and processing, where privacy protection has become a critical issue. Although existing searchable encryption techniques can ensure data privacy, most of them only support single-keyword queries, while the few schemes that support multi-keyword queries still suffer from efficiency and security issues. To address these problems, this paper proposed an SGX-based multi-keyword dynamic symmetric searchable encryption scheme. The scheme introduce a dynamic cross-tagging technique to achieve efficient multi-keyword search. Combined with a result-hiding filter, it eliminate the risk of information leakage. The client relie on SGX to generate trapdoors, significantly reducing computational burden and communication overhead. Furthermore, by leveraging SGX technology, the scheme achieved forward and backward security within a trusted execution environment, effectively defending against threats such as file injection attacks. Finally, theoretical analysis and experimental simulations demonstrate the security of the proposed scheme, as well as its superior search efficiency and overall performance.

Key words: cloud storage, SGX, multi-search, dynamic searchable encryption

CLC Number:

TP309

LIU Peishun, LI Xinyue, CHEN Ping, MO Wenqing, LI Shuangying. A Multi-Keyword Dynamic Symmetric Searchable Encryption Scheme Based on SGX[J]. Netinfo Security, 2026, 26(6): 870-885.

Figures/Tables 11

References 30

[1]	SONG Xiaodong, 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]	CURTMOLA R, GARAY J, KAMARA S, et al. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions[C]//ACM. The 13th ACM Conference on Computer and Communications Security. New York: ACM, 2006: 79-88.
[3]	KAMARA S, PAPAMANTHOU C, ROEDER T. Dynamic Searchable Symmetric Encryption[C]//ACM. The 2012 ACM Conference on Computer and Communications Security. New York: ACM, 2012: 965-976.
[4]	CASH D, JAEGER J, JARECKI S, et al. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation[C]//Internet Society. The 2014 Network and Distributed System Security Symposium. San Diego: Internet Society, 2014: 1-12.
[5]	STEFANOV E, PAPAMANTHOU C, SHI E. Practical Dynamic Searchable Encryption with Small Leakage[C]//Internet Society. The 2014 Network and Distributed System Security Symposium. San Diego: Internet Society, 2014: 48-55.
[6]	BOST 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.
[7]	LYU Sichun. Research on Multi-Keyword Dynamic Searchable Encryption Scheme Supporting Forward and Backward Security[D]. Nanjing: Nanjing University of Information Science and Technology, 2024.
	吕思纯. 支持前后向安全的多关键字动态可搜索加密方案研究[D]. 南京: 南京信息工程大学, 2024.
[8]	ZHENG Chengfu. Research and Application of Forward Secure Searchable Encryption Schemes[D]. Jiaozuo: Henan Polytechnic University, 2024.
	郑丞甫. 前向安全可搜索加密方案的研究与应用[D]. 焦作: 河南理工大学, 2024.
[9]	HOANG T, YAVUZ A A, GUAJARDO J. A Secure Searchable Encryption Framework for Privacy-Critical Cloud Storage Services[J]. IEEE Transactions on Services Computing, 2019, 14(6): 1675-1689.
[10]	GHAREH-CHAMANI 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.
[11]	STEFANOV E, VAN-DIJK M, SHI E, et al. Path ORAM: An Extremely Simple Oblivious RAM Protocol[J]. Journal of the ACM, 2018, 65(4): 1-26.
[12]	ZUO Cong, SUN Shifeng, LIU J K, et al. Forward and Backward Private DSSE for Range Queries[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 19(1): 328-338.
[13]	ZHU Xinran, ZHOU Jian, DAI Yue, et al. A Verifiable and Efficient Symmetric Searchable Encryption Scheme for Dynamic Dataset with Forward and Backward Privacy[J]. IEEE Transactions on Dependable and Secure Computing, 2024, 22(3): 2741-2755.
[14]	CHEN Tianyang, XU Peng, WANG Wei, et al. Bestie: Very Practical Searchable Encryption with Forward and Backward Security[C]//Springer. European Symposium on Research in Computer Security. Heidelberg: Springer, 2021: 3-23.
[15]	CHAMANI J G, PAPADOPOULOS D, KARBASFORUSHAN M, et al. Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions[C]//USENIX. 31st USENIX Security Symposium. Berkeley: USENIX, 2022: 2425-2442.
[16]	CASH D, JARECKI S, JUTLA C, et al. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries[C]// Springer. Advances in Cryptology-CRYPTO 2013: 33rd Annual Cryptology Conference. Heidelberg: Springer, 2013: 353-373.
[17]	LAI S, PATRANABIS S, SAKZAD A, et al. Result Pattern Hiding Searchable Encryption for Conjunctive Queries[C]// ACM. The 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 745-762.
[18]	LI Li, ZHU Jiangwen, YANG Chunyan. Overview of Research on the Revocable Mechanism of Attribute-Based Encryption[J]. Netinfo Security, 2023, 23(4): 39-50.
	李莉, 朱江文, 杨春艳. 基于属性加密的可撤销机制研究综述[J]. 信息网络安全, 2023, 23(4): 39-50.
[19]	LIU Yining. Research on Searchable Encryption Technology against Malicious Participants[D]. Qufu: Qufu Normal University, 2025.
	刘怡宁. 抵御恶意参与方的可搜索加密技术研究[D]. 曲阜: 曲阜师范大学, 2025.
[20]	XU Dequan. Access Control Searchable Encryption Scheme and Algorithm[D]. Guiyang: Guizhou University, 2024.
	许德权. 访问控制可搜索加密方案与算法[D]. 贵阳: 贵州大学, 2024.
[21]	YUAN Dongliang, CUI Shujie, RUSSELLO G. Result Pattern Hiding Boolean Searchable Encryption: Achieving Negligible False Positive Rates in Low Storage Overhead[R]. San Francisco: IACR, 2024/1156, 2024.
[22]	ZHANG Yupeng, KATZ J, PAPAMANTHOU C. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption[C]// USENIX. 25th USENIX Security Symposium. Berkeley: USENIX, 2016: 707-720.
[23]	ZHAO Chen, DU Ruxian, CHEN Jie, et al. Lightweight Dynamic Conjunctive Keyword Searchable Encryption with Result Pattern Hiding[J]. IEEE Transactions on Information Forensics and Security, 2025, 20: 9492-9506.
[24]	COSTAN V, DEVADAS S. Intel SGX Explained[R]. San Francisco: IACR, 2016/086, 2016.
[25]	REN Yongmao, LI Jin, YANG Zhen, et al. Accelerating Encrypted Deduplication via SGX[C]// USENIX. 2021 USENIX Annual Technical Conference. Berkeley: USENIX, 2021: 957-971.
[26]	OLEKSENKO O, TRACH B, KRAHN R, et al. Varys: Protecting SGX Enclaves from Practical Side-Channel Attacks[C]// USENIX. 2018 USENIX Annual Technical Conference. Berkeley: USENIX, 2018: 227-240.
[27]	PATRANABIS S, MUKHOPADHYAY D. Forward and Backward Private Conjunctive Searchable Symmetric Encryption[R]. San Francisco: IACR, 2020/805, 2020.
[28]	XU Chang, WANG Ruijuan, ZHU Liehuang, et al. Efficient Strong Privacy-Preserving Conjunctive Keyword Search over Encrypted Cloud Data[J]. IEEE Transactions on Big Data, 2023, 9(3): 805-817.
[29]	PATEL S, PERSIANO G, SEO J Y, et al. Efficient Boolean Search over Encrypted Data with Reduced Leakage[C]// Springer. Advances in Cryptology-ASIACRYPT 2021. Heidelberg:Springer. 2021: 577-607.
[30]	COHEN W W. Enron Email Dataset[EB/OL]. (2015-05-08)[2025-03-01]. https://www.cs.cmu.edu/-./enron/.

符号	含义
λ	安全参数（本文设定为128）
$l $	伪随机函数输入或输出的长度
p	一个大素数
$Z_{p}^{*} $	模p的乘法群
F	$\{0,1\}^{\lambda} \times\{0,1\}^{l} \rightarrow\{0,1\}^{l} $
F_p	${{\{0,1\}}^{\lambda }}\times {{\{0,1\}}^{l}}\to Z_{p}^{*} $
g	循环群 $G $的生成元
op	op∈{add, del},表示数据的插入或删除操作
w	关键字
W	关键字集合
w₁	出现频率最低的关键字
UpdateCnt	存储每个关键字更新次数的映射
DB(w)	包含关键字w的文件标识集合
α	随机盲因子
val	对数据(w, id, op)加密后的密文
TSet	存储α和val的集合
addr	TSet的键（索引）
xtag	动态交叉标签
XSet	存储xtag的集合
ES	XSet对应的加密结构
ρ	XSet的最大容量（本文设定为1000）
etok	结果隐藏过滤器生成的加密令牌
cnt	搜索结果的数量
sIdList	解密后的搜索结果

文档标识符	关键字
id₁	w₁,w₂,w₃
id₂	w₁,w₂
id₃	w₁,w₃

可搜索加密方案	多关键字搜索	动态更新	前向安全	后向安全	KPRP 隐藏	发表年份
HXT^[17]方案	√	×	无	无	√	2018
HBS^[21]方案	√	×	无	无	√	2024
ConjFilter^[29]方案	√	×	无	无	√	2021
ESP-CKS^[28]方案	√	√	√	II型	√	2023
ODXT^[27]方案	√	√	√	II型	×	2020
本文方案	√	√	√	II型	√	-

ρ	更新延迟 /ms	加密次数	通信轮次	单次通信 /KB	总通信开销 /MB	每轮平均更新数
50	4.0654	1306	1306	40.45	51.5861	3.83
100	3.1995	733	733	47.26	33.8267	6.82
200	2.6492	399	399	61.02	23.7777	12.53
500	2.0589	173	173	88.97	15.0310	28.90
1000	1.3107	88	88	125.15	10.7551	56.82
2000	0.8689	45	45	183.26	8.0533	111.11
5000	0.7218	18	18	331.65	5.8297	277.78