基于双向索引的高效连接关键字查询动态可搜索加密方案

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

Abstract

Abstract:

To solve the problems of complicated operation, information leakage, and inflexible query method in the update process of existing dynamic searchable encryption scheme, an efficient dynamic searchable encryption scheme (named BPC-DSSE) for conjunctive query with forward and backward privacy was proposed.A bitmap index was used to construct a bidirectional index structure to simplify the dynamic update process, and the access pattern was hidden through symmetric encryption with homomorphic addition.At the same time, since the addition and deletion operations were completed by modulo addition, the leakage of the update process could be reduced by hiding the update type.Security analysis shows that the BPC-DSSE scheme achieves forward and Type-I^- backward privacy.The simulation results show that the BPC-DSSE scheme has higher update and retrieval efficiency than other conjunctive query schemes.

Key words: dynamic searchable symmetric encryption, conjunctive query, forward privacy, backward privacy

CLC Number:

TP309

Ruizhong DU, Yuqing ZHANG, Mingyue LI. Efficient dynamic searchable encryption scheme for conjunctive queries based on bidirectional index[J]. Journal on Communications, 2022, 43(5): 123-132.

Figures/Tables 8

方案	查询	更新	前向安全	后向安全	查询类型	客户端存储	交互轮数
Moneta^[10]	$Õ ({log}^{2} N)$	$Õ (a_{w} log N + {log}^{3} N)$	√	Type-I	单关键字	O(1)	3
Orion^[12]	O(log²N)	O(log²N)	√	Type-I	单关键字	O(1)	O(logN)
Horus^[12]	O(log²N)	O(n_wlogd_wlogN+log²\|W\|)	√	Type-III	单关键字	O(1)	O(logd_w)
SD_a[13]	O(logN)	O(a_w+logN)	√	Type-II	单关键字	O(1)	1
VBTree^[20]	O(n\|Upd(w₁)\|\|D\|)	O(HT)	√	×	连接关键字	O(\|W\|)	1
FBDSSE-CQ^[21]	O(n\|Upd(w₁)\|)	O(1)	√	Type-C	连接关键字	O(\|W\|)	1
ODXT^[22]	O(n\|Upd(w₁)\|)	O(1)	√	Type-II	连接关键字	O(\|W\|logN)	1
BPC-DSSE	O(\|Upd(w₁)\|)	O(1)	√	Type-I	连接关键字	O(1)	2

References 23

[1]	董晓蕾, 周俊, 曹珍富 . 可搜索加密研究进展[J]. 计算机研究与发展, 2017,54(10): 2107-2120.
	DONG X L , ZHOU J , CAO Z F . Research advances on secure searchable encryption[J]. Journal of Computer Research and Development, 2017,54(10): 2107-2120.
[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, 2000: 44-55.
[3]	吴志强, 李肯立, 郑蕙 . 高效可扩展的对称密文检索架构[J]. 通信学报, 2017,38(8): 79-93.
	WU Z Q , LI K L , ZHENG H . Efficient and scalable architecture for searchable symmetric encryption[J]. Journal on Communications, 2017,38(8): 79-93.
[4]	杜瑞忠, 谭艾伦, 田俊峰 . 基于区块链的公钥可搜索加密方案[J]. 通信学报, 2020,41(4): 114-122.
	DU R Z , TAN A L , TIAN J F . Public key searchable encryption scheme based on blockchain[J]. Journal on Communications, 2020,41(4): 114-122.
[5]	KAMARA S , PAPAMANTHOU C , ROEDER T . Dynamic searchable symmetric encryption[C]// Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York:ACM Press, 2012: 965-976.
[6]	STEFANOV E , PAPAMANTHOU C , SHI E . Practical dynamic searchable encryption with small leakage[C]// Proceedings 2014 Network and Distributed System Security Symposium. Virginia:the Internet Society, 2014: 72-75.
[7]	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 Press, 2017: 1465-1482.
[8]	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.
[9]	ZHANG Y P , KATZ J , PAPAMANTHOU C . All your queries are belong to us:the power of file-injection attacks on searchable encryption[R]. IACR Cryptology EPrint Archive, 2016.
[10]	BOST R , . ∑oφo?:forward secure searchable encryption[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2016: 1143-1154.
[11]	SUN S F , YUAN X L , 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 Press, 2018: 763-780.
[12]	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 Press, 2018: 1038-1055.
[13]	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 Press, 2019: 141-152.
[14]	黄珂 . 前向和后向安全的动态对称可搜索加密方案的研究[D]. 上海:华东师范大学, 2019.
	HUANG K . Research on forward and backward security of dynamic symmetric searchable encryption scheme[D]. Shanghai:East China Normal University, 2019.
[15]	SARDAR L , RUJ S . FSPVDSSE:a forward secure publicly verifiable dynamic SSE scheme[C]// International Conference on Provable Security. Berlin:Springer, 2019: 355-371.
[16]	ZUO C , SUN S F , LIU J K ,et al. Dynamic searchable symmetric encryption with forward and stronger backward privacy[C]// European Symposium on Research in Computer Security. Berlin:Springer, 2019: 283-303.
[17]	ZUO C , SUN S F , LIU J K ,et al. Forward and backward private DSSE for range queries[J]. IEEE Transactions on Dependable and Secure Computing, 2022,19(1): 328-338.
[18]	CASH D , JARECKI S , JUTLA C ,et al. Highly-scalable searchable symmetric encryption with support for Boolean queries[C]// Annual Cryptology Conference. Berlin:Springer, 2013: 353-373.
[19]	LAI S Q , PATRANABIS S , SAKZAD A ,et al. Result pattern hiding searchable encryption for conjunctive queries[C]// Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2018: 745-762.
[20]	WU Z Q , LI K L . VBTree:forward secure conjunctive queries over encrypted data for cloud computing[J]. The VLDB Journal, 2019,28(1): 25-46.
[21]	ZUO C , SUN S , LIU J K ,et al. Forward and backward private dynamic searchable symmetric encryption for conjunctive queries[R]. IACR Cryptology EPrint Archive, 2020.
[22]	PATRANABIS S , MUKHOPADHYAY D . Forward and backward private conjunctive searchable symmetric encryption[C]// Proceedings 2021 Network and Distributed System Security Symposium. Virginia:the Internet Society, 2021:doi.org/10.14722/ndss.2021.23116.
[23]	FU Z J , WU X L , GUAN C W ,et al. Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement[J]. IEEE Transactions on Information Forensics and Security, 2016,11(12): 2706-2716.

Metrics

Recommended 0

No Suggested Reading articles found!

参数	含义
λ	安全参数
F	安全的伪随机函数
n	位串的长度
W	关键字空间
f_i	第i个文件（1≤i≤n）
DB	数据库
EDB	加密数据库
ST_c	当前的搜索令牌
CT	存储当前搜索令牌ST_c和更新的次数c
bs	位图索引对应的位串
E	加密后的位串
Sum_E	加密后的位串的和
sk	一次性安全密钥
Sum_sk	一次性安全密钥的和

Efficient dynamic searchable encryption scheme for conjunctive queries based on bidirectional index

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 23

Related Articles 15

Metrics

Recommended 0

后向安全	当前匹配关键字w的文件	文件插入时间	w更新总次数	w更新时间	插入后被删除文档的插入删除时间
Type-I	√	√	√	—	—
Type-II	√	√	√	√	—
Type-III	√	√	√	√	√
Type-I^-	√	—	√	√	—

[1]	Xiaoni DU, Xiangyu WANG, Lifang LIANG, Kaibin LI. Quantum cryptanalysis of lightweight block cipher Piccolo [J]. Journal on Communications, 2023, 44(6): 175-182.
[2]	Zhen ZHENG, Yingjian YAN, Juesong CAI, Yanjiang LIU. Non-specific TVLA method based on two-sample KS test [J]. Journal on Communications, 2023, 44(5): 137-147.
[3]	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.
[4]	Dacheng ZHOU, Hongchang CHEN, Weizhen HE, Guozhen CHENG, Hongchao HU. Research on multidimensional dynamic defense strategy for microservice based on deep reinforcement learning [J]. Journal on Communications, 2023, 44(4): 50-63.
[5]	Ming TANG, Yifan HU. Load-to-store: exploit the time leakage of store buffer transient window [J]. Journal on Communications, 2023, 44(4): 64-77.
[6]	Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short [J]. Journal on Communications, 2023, 44(4): 167-175.
[7]	Yuling LIU, Cuilin WANG, Zhangjie FU. Generative text steganography method based on emotional expression in semantic space [J]. Journal on Communications, 2023, 44(4): 176-186.
[8]	Baiji HU, Xiaojuan ZHANG, Yuancheng LI, Rongxin LAI. Multi-function supported privacy protection data aggregation scheme for V2G network [J]. Journal on Communications, 2023, 44(4): 187-200.
[9]	Wei FAN, Cheng PENG, Dali ZHU, Yuqing WANG. Research on intrusion response strategy based on static Bayesian game in mobile edge computing network [J]. Journal on Communications, 2023, 44(2): 70-81.
[10]	Dongyan HUANG, Kun LI. Research on multi-address time-based blockchain covert communication method [J]. Journal on Communications, 2023, 44(2): 148-159.
[11]	Shufen ZHANG, Yanling DONG, Jingcheng XU, Haoshi WANG. AdaBoost algorithm based on target perturbation [J]. Journal on Communications, 2023, 44(2): 198-209.
[12]	Shengbao WANG, Xin ZHOU, Kang WEN, Bosen WENG. Tripartite authenticated key exchange protocol for smart grid [J]. Journal on Communications, 2023, 44(2): 210-218.
[13]	Yiliang HAN, Kaiyang GUO, Riming WU, Kai LIU. Attribute-based encryption scheme against key abuse based on OBDD access structure from lattice [J]. Journal on Communications, 2023, 44(1): 75-88.
[14]	Chao XIA, Yaqi LIU, Qingxiao GUAN, Xin JIN, Yanshuo ZHANG, Shengwei XU. Steganalysis of JPEG images using non-linear residuals [J]. Journal on Communications, 2023, 44(1): 142-152.
[15]	Xiaodong FU, Xinxin QI, Li LIU, Wei PENG, Jiaman DING, Fei DAI. Detecting and preventing collusion attack in DPoS based on power index [J]. Journal on Communications, 2022, 43(12): 123-133.