基于穿刺伪随机函数的动态可搜索加密方案

doi:10.11772/j.issn.1001-9081.2024071011

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (8): 2612-2621.DOI: 10.11772/j.issn.1001-9081.2024071011

• 网络空间安全 • 上一篇

基于穿刺伪随机函数的动态可搜索加密方案

刘运东¹^,², 汪学明¹^,²()

^1.公共大数据国家重点实验室（贵州大学），贵阳 550025
^2.贵州大学计算机科学与技术学院，贵阳 550025

收稿日期:2024-07-17 修回日期:2024-10-15 接受日期:2024-10-16 发布日期:2024-11-19 出版日期:2025-08-10
通讯作者: 汪学明
作者简介:刘运东（1999—），男，贵州六盘水人，硕士研究生，主要研究方向：密码学
基金资助:
国家自然科学基金资助项目(61163049)

Dynamic searchable encryption scheme based on puncturable pseudorandom function

Yundong LIU¹^,², Xueming WANG¹^,²()

^1.State Key Laboratory of Public Big Data （Guizhou University），Guiyang Guizhou 550025，China
^2.College of Computer Science and Technology，Guizhou University，Guiyang Guizhou 550025，China

Received:2024-07-17 Revised:2024-10-15 Accepted:2024-10-16 Online:2024-11-19 Published:2025-08-10
Contact: Xueming WANG
About author:LIU Yundong， born in 1999， M. S. candidate. His research interests include cryptography.
Supported by:
National Natural Science Foundation of China(61163049)

摘要/Abstract

摘要：

动态可搜索加密由于在云服务器上提供添加、删除与搜索数据的功能而受到广泛关注。现有的动态可搜索加密方案通常须由较高安全性的密码学原语构造，在方案搜索时需要进行多次双线性对运算。针对动态可搜索加密方案在服务器中搜索时较大的计算开销，将穿刺伪随机函数（PPRF）引入动态可搜索加密中，设计并提出一种基于PPRF的动态可搜索加密方案。该方案不必使用对称加密算法来加密文件标识符，同时也不必在服务器搜索时解密密文获取文件标识符，而客户端与服务器仅需一次交互即能完成数据搜索。而且，该方案在删除关键字时标记密钥，在搜索时使用标记密钥计算PPRF，并使用前向安全方案实现后向安全，在保证安全性的同时提高搜索效率。根据动态可搜索加密方案的安全模型，证明了该方案的安全性。仿真实验结果表明，与基于密钥可更新伪随机函数（KUPRF）构建的方案ROSE、基于对称穿刺加密（SPE）构建的方案Janus++和基于对称可撤销加密（SRE）构建的方案Aura相比，所提方案的每个关键字的平均搜索时间分别降低了17%、65%和58%。可见，所提方案有效且可行，有效地降低了服务器的搜索成本，提高了方案的搜索效率，增强了方案实用性。

关键词: 可搜索加密, 伪随机函数, 穿刺伪随机函数, 前向安全, 后向安全

Abstract:

Dynamic searchable encryption has attracted wide attention due to its ability to add， delete， and search data on cloud servers. The existing dynamic searchable encryption schemes are usually constructed using highly secure cryptographic primitives， and multiple bilinear pairing operations need to be performed during scheme searching. In view of the large computational overhead of dynamic searchable encryption schemes when searching on servers， a Puncturable PseudoRandom Function （PPRF） was introduced into dynamic searchable encryption， and a dynamic searchable encryption scheme based on PPRF was designed and proposed. In this scheme， file identifiers did not need to be encrypted using symmetric encryption algorithms， and it is also not necessary to decrypt ciphertext to obtain file identifiers during server searches， and the client and the server were able to complete data search with only one interaction. At the same time， in the scheme， the key was marked when deleting keywords， the marked key was used to calculate the PPRF during search， and backward security was implemented with a forward-secure scheme， thereby ensuring security while improving search efficiency. According to security model of the dynamic searchable encryption scheme， the security of the scheme was verified. Simulation results show that compared with ROSE （RObust Searchable Encryption） scheme built on Key-Updatable Pseudorandom Function （KUPRF）， Janus++ scheme built on Symmetric Puncturable Encryption （SPE）， and Aura scheme built on Symmetric Revocable Encryption （SRE）， the proposed scheme has the average search time of each keyword reduced by 17%， 65%， and 58%， respectively. It can be seen that the proposed scheme is effective and feasible， and reduces the search cost of the server effectively， improves the search efficiency of the scheme， and increases the practicality of the scheme.

Key words: searchable encryption, pseudorandom function, Puncturable PseudoRandom Function (PPRF), forward security, backward security

中图分类号:

TP309.7

刘运东, 汪学明. 基于穿刺伪随机函数的动态可搜索加密方案[J]. 计算机应用, 2025, 45(8): 2612-2621.

Yundong LIU, Xueming WANG. Dynamic searchable encryption scheme based on puncturable pseudorandom function[J]. Journal of Computer Applications, 2025, 45(8): 2612-2621.

图/表 9

图1 穿刺伪随机函数模型

Fig. 1 Puncturable pseudorandom function model

图2 本文方案模型

Fig. 2 Proposed scheme model

表1 方案符号说明

Tab. 1 Description of scheme symbols

符号	描述	符号	描述
$Σ$	动态可搜索加密方案	$b$	二进制变量
$Σ a d d$ ， $Σ d e l$	前向安全方案	$λ$	安全参数
$E D B a d d$ ， $E D B d e l$	数据表	$H$	伪随机函数
$E D B c a c h e$	缓存数据表	$F$	穿刺伪随机函数
$N e w$ ， $O l d$	临时数据表	$K a d d$ ， $K d e l$	前向安全方案密钥
$S C$	搜索次数表	$K s$ ， $K t$ ， $K m s k$ ， $K p s k$	密钥
$P S K$	密钥表	$σ$	查询状态
$o p$	操作类型	$i$	搜索次数
$w$	关键字	$p$	陷门
$i n d$	文件标识符	$t$	标记
$V$	循环群	$u$	密文
$v$	循环群元素

表1 方案符号说明

Tab. 1 Description of scheme symbols

符号	描述	符号	描述
$Σ$	动态可搜索加密方案	$b$	二进制变量
$Σ a d d$ ， $Σ d e l$	前向安全方案	$λ$	安全参数
$E D B a d d$ ， $E D B d e l$	数据表	$H$	伪随机函数
$E D B c a c h e$	缓存数据表	$F$	穿刺伪随机函数
$N e w$ ， $O l d$	临时数据表	$K a d d$ ， $K d e l$	前向安全方案密钥
$S C$	搜索次数表	$K s$ ， $K t$ ， $K m s k$ ， $K p s k$	密钥
$P S K$	密钥表	$σ$	查询状态
$o p$	操作类型	$i$	搜索次数
$w$	关键字	$p$	陷门
$i n d$	文件标识符	$t$	标记
$V$	循环群	$u$	密文
$v$	循环群元素

表2 方案比较

Tab. 2 Comparison of schemes

方案	密码学原语	正确性
文献［9］方案	穿刺加密	√
文献［28］方案	可更新伪随机函数	√
文献［29］方案	对称穿刺加密	√
文献［30］方案	可撤销穿刺加密	×
文献［31］方案	可撤销穿刺加密	√
本文方案	穿刺伪随机函数	√

图3 GGM二叉树

Fig. 3 GGM binary tree

表3 密码学原语在搜索阶段的耗时 ( μs)

Tab. 3 Time consumption of cryptographic primitives in search phase

方案	耗时	方案	耗时
ROSE^［28］	51.64	Aura^［30］	116.41
Janus++^［29］	143.37	本文方案	38.86

表4 方案更新时间 ( ms)

Tab. 4 Update time of schemes

方案	平均添加耗时	平均删除耗时
ROSE^［28］	5.162	8.526
Janus++^［29］	0.154	2.063
Aura^［30］	0.308	0.004
本文方案	0.127	1.882

图4 方案搜索时间

Fig. 4 Search time of schemes

表5 方案平均搜索时间 (μs)

Tab. 5 Average search time of schemes

方案	每个关键字平均搜索时间
ROSE^［28］	66.89
Janus++^［29］	158.23
Aura^［30］	131.69
本文方案	55.48

参考文献 34

[1]	SONG D X， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data［C］// Proceedings of the 2000 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2000： 44-55.
[2]	BONEH D， DI CRESCENZO G， OSTROVSKY R， et al. Public key encryption with keyword search［C］// Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 3027. Berlin： Springer， 2004： 506-522.
[3]	CHANG Y C， MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data［C］// Proceedings of the 2005 International Conference on Applied Cryptography and Network Security， LNCS 3531. Berlin： Springer， 2005： 442-455.
[4]	CURTMOLA R， GARAY J， KAMARA S， et al. Searchable symmetric encryption： improved definitions and efficient constructions［C］// Proceedings of the 13th ACM Conference on Computer and Communications Security. New York： ACM， 2006： 79-88.
[5]	KAMARA S， PAPAMANTHOU C. Parallel and dynamic searchable symmetric encryption［C］// Proceedings of the 2013 International Conference on Financial Cryptography and Data Security， LNCS 7859. Berlin： Springer， 2013： 258-274.
[6]	STEFANOV E， PAPAMANTHOU C， SHI E. Practical dynamic searchable encryption with small leakage［C］// Proceedings of the 2014 Network and Distributed System Security Symposium. Reston， VA： Internet Society， 2014： 1-15.
[7]	NAVEED M， PRABHAKARAN M， GUNTER C A. Dynamic searchable encryption via blind storage［C］// Proceedings of the 2014 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2014： 639-654.
[8]	BOST R. ∑oϕoς： forward secure searchable encryption［C］// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 1143-1154.
[9]	BOST R， MINAUD B， OHRIMENKO O. Forward and backward private searchable encryption from constrained cryptographic primitives［C］// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2017： 1465-1482.
[10]	KIM K S， KIM M， LEE D， et al. Forward secure dynamic searchable symmetric encryption with efficient updates［C］// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2017： 1449-1463.
[11]	CHAMANI J G， PAPADOPOULOS D， PAPAMANTHOU C， et al. New constructions for forward and backward private symmetric searchable encryption［C］// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2018： 1038-1055.
[12]	LI M， JIA C， DU R， et al. Forward and backward secure searchable encryption scheme supporting conjunctive queries over bipartite graphs［J］. IEEE Transactions on Cloud Computing， 2023， 11（1）： 1091-1102.
[13]	YANG Y， LI H， LIU W， et al. Secure dynamic searchable symmetric encryption with constant document update cost［C］// Proceedings of the 2014 IEEE Global Communications Conference. Piscataway： IEEE， 2014： 775-780.
[14]	WANG W， LIU D， XU P， et al. Keyword search shareable encryption for fast and secure data replication［J］. IEEE Transactions on Information Forensics and Security， 2023， 18： 5537-5552.
[15]	CHEN L， LI J， LI J. Toward forward and backward private dynamic searchable symmetric encryption supporting data deduplication and conjunctive queries［J］. IEEE Internet of Things Journal， 2023， 10（19）： 17408-17423.
[16]	QIN G， LIU P， HU C， et al. Retrieval transformation： dynamic searchable symmetric encryption with strong security［J］. IEEE Systems Journal， 2023， 17（4）： 5519-5530.
[17]	DOU H， DAN Z， XU P， et al. Dynamic searchable symmetric encryption with strong security and robustness［J］. IEEE Transactions on Information Forensics and Security， 2024， 19： 2370-2384.
[18]	GAO C， LV S， WEI Y， et al. M-SSE： an effective searchable symmetric encryption with enhanced security for mobile devices［J］. IEEE Access， 2018， 6： 38860-38869.
[19]	CUI S， ASGHAR M R， GALBRAITH S D， et al. P-McDb： privacy-preserving search using multi-cloud encrypted databases［C］// Proceedings of the IEEE 10th International Conference on Cloud Computing. Piscataway： IEEE， 2017： 334-341.
[20]	ZHENG Y， LU R， SHAO J， et al. Achieving practical symmetric searchable encryption with search pattern privacy over cloud［J］. IEEE Transactions on Services Computing， 2022， 15（3）： 1358-1370.
[21]	WU Z， CAI Z， TANG X， et al. A forward and backward private oblivious RAM for storage outsourcing on edge-cloud computing［J］. Journal of Parallel and Distributed Computing， 2022， 166： 1-14.
[22]	XU C， WANG R， ZHU L， et al. Efficient strong privacy-preserving conjunctive keyword search over encrypted cloud data［J］. IEEE Transactions on Big Data， 2023， 9（3）： 805-817.
[23]	AMJAD G， KAMARA S， MOATAZ T. Forward and backward private searchable encryption with SGX［C］// Proceedings of the 12th European Workshop on Systems Security. New York： ACM， 2019： No.4.
[24]	VO V， LAI S， YUAN X， et al. Accelerating forward and backward private searchable encryption using trusted execution［C］// Proceedings of the 2020 International Conference on Applied Cryptography and Network Security， LNCS 12147. Cham： Springer， 2020： 83-103.
[25]	VO V， LAI S， YUAN X， et al. Towards efficient and strong backward private searchable encryption with secure enclaves［C］// Proceedings of the 2021 International Conference on Applied Cryptography and Network Security， LNCS 12726. Cham： Springer， 2021： 50-75.
[26]	BAKAS A， MICHALAS A. Nowhere to leak： a multi-client forward and backward private symmetric searchable encryption scheme［C］// Proceedings of the 2021 IFIP Annual Conference on Data and Applications Security and Privacy， LNCS 12840. Cham： Springer， 2021： 84-95.
[27]	CHATTERJEE S， PURIA S K P， SHAH A. Backward private DSSE： alternative formulations of information leakage and efficient constructions［EB/OL］. ［2024-01-05］..
[28]	XU P， SUSILO W， WANG W， et al. ROSE： robust searchable encryption with forward and backward security［J］. IEEE Transactions on Information Forensics and Security， 2022， 17： 1115-1130.
[29]	SUN S F， YUAN X， LIU J K， et al. Practical backward-secure searchable encryption from symmetric puncturable encryption［C］// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2018： 763-780.
[30]	SUN S F， STEINFELD R， LAI S， et al. Practical non-interactive searchable encryption with forward and backward privacy［C］// Proceedings of the 2021 Network and Distributed System Security Symposium. Reston： Internet Society， 2021： 1-18.
[31]	黄一才，郁滨，李森森. 一种基于SRE的对称可搜索加密方案［J］. 计算机研究与发展， 2023， 60（12）： 2725-2736.
	HUANG Y C， YU B， LI S S. A searchable symmetric encryption scheme based on SRE［J］. Journal of Computer Research and Development， 2023， 60（12）： 2725-2736.
[32]	RIZOMILIOTIS P， GRITZALIS S. Simple forward and backward private searchable symmetric encryption schemes with constant number of roundtrips［C］// Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop. New York： ACM， 2019： 141-152.
[33]	GREEN M D， MIERS I. Forward secure asynchronous messaging from puncturable encryption［C］// Proceedings of the 2015 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2015： 305-320.
[34]	HOHENBERGER S， KOPPULA V， WATERS B. Adaptively secure puncturable pseudorandom functions in the standard model［C］// Proceedings of the 2015 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 9452. Berlin： Springer， 2015： 79-102.

基于穿刺伪随机函数的动态可搜索加密方案

Dynamic searchable encryption scheme based on puncturable pseudorandom function

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 34

相关文章 15

编辑推荐

Metrics

[1]	孙晓玲, 王丹辉, 李姗姗. 基于区块链的动态密文排序检索方案[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2500-2505.
[2]	王政, 王经纬, 殷新春. 支持用户撤销的可搜索电子健康记录共享方案[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 504-511.
[3]	高改梅, 段明博, 荀亚玲, 刘春霞, 党伟超. 支持密码逆向防火墙的基于SM9的属性基可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3495-3502.
[4]	杜晓玉, 刘帅起, 韩志杰, 霍振祥, 王玉璟. 以患者为中心基于IPFS和区块链的医疗信息共享方案[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3122-3133.
[5]	陆佳行, 戴华, 刘源龙, 周倩, 杨庚. 面向云环境密文排序检索的字典划分向量空间模型[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 1994-2000.
[6]	庞晓琼, 王云婷, 陈文俊, 姜攀, 高亚楠. 基于区块链的公平可验证的多关键词密文排序检索[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 130-139.
[7]	李莉, 吴怡, 杨祉坤, 陈云鹏. 基于分区型区块链医疗电子病历共享方案[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 183-190.
[8]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[9]	张恩, 侯缨盈, 李功丽, 李会敏, 李钰. 基于错误学习的自适应等级可搜索加密方案[J]. 计算机应用, 2020, 40(1): 148-156.
[10]	庞晓琼, 严小龙, 陈文俊, 余本国, 聂梦飞. 支持语义扩展的动态多关键词密文排序检索[J]. 计算机应用, 2019, 39(4): 1059-1065.
[11]	戴厚乐, 杨庚, 闵兆娥. 分布式环境下多关键词并行密文检索方案[J]. 计算机应用, 2019, 39(10): 2948-2954.
[12]	白平, 张薇, 李聪, 王绪安. 支持用户撤销的可验证密文检索方案[J]. 计算机应用, 2018, 38(6): 1640-1643.
[13]	王洁, 卢建朱, 曾小飞. 可及时确定受攻击节点的无线传感器网络数据聚合方案[J]. 计算机应用, 2016, 36(9): 2432-2437.
[14]	项文, 杨晓元, 王绪安, 吴立强. 前向安全的格上基于身份签密方案[J]. 计算机应用, 2016, 36(11): 3077-3081.
[15]	屈娟, 李艳平, 伍习丽. 对两个基于智能卡的多服务器身份认证方案的密码学分析与改进[J]. 计算机应用, 2015, 35(8): 2199-2204.