Dynamic searchable encryption scheme based on puncturable pseudorandom function

doi:10.11772/j.issn.1001-9081.2024071011

Abstract

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

摘要：

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

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

CLC Number:

TP309.7

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

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

Figures/Tables 9

Fig. 1 Puncturable pseudorandom function model

Fig. 2 Proposed scheme model

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$	循环群元素

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$	循环群元素

Tab. 2 Comparison of schemes

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

Fig. 3 GGM binary tree

Tab. 3 Time consumption of cryptographic primitives in search phase

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

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

Fig. 4 Search time of schemes

Tab. 5 Average search time of schemes

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

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