Efficient Dynamic Searchable Encryption Scheme Based on Bitslicing

doi:10.3969/j.issn.1671-1122.2024.09.001

Abstract

Abstract:

Searchable encryption, as a crucial technology for enhancing data security in cloud storage, attracts continuous attention both from both academia and industry. Dynamic searchable encryption schemes refer to those schemes that enable updating datasets while maintaining searchability. However, the inefficiency of updates remains a critical bottleneck that prevents the technology from practical application, particularly in large dataset scenarios, due to the expensive data re-encryption and index reconstruction overhead. Therefore, based on bitslicing, the paper proposed an efficient dynamic searchable encryption scheme called BSSE (BitSlicing-based Dynamic Searchable Encryption Scheme). The core idea of BSSE is to grouping entries into equal-sized blocks, converting such blocks from words into bits representation and encrypting them in parallel. By eliminating shift operations during the encryption process and simplifying S-box into boolean logic circuit, BSSE significantly improves update efficiency. The experimental result demonstrates that the BSSE scheme exhibits 59 times faster than existing schemes and show great potential in practical applications for updating large datasets.

Key words: searchable encryption, bitslicing, parallel

CLC Number:

TP309

ZHOU Jiancong, ZHU Xiaojie, CHEN Chi. Efficient Dynamic Searchable Encryption Scheme Based on Bitslicing[J]. Netinfo Security, 2024, 24(9): 1309-1316.

Figures/Tables 4

References 24

[1]	SONG D X, WAGNER D, PERRIG A. Practical Techniques for Searches on Encrypted Data[C]// IEEE. Proceeding 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. 13th ACM Conference on Computer and Communications Security (CCS ’06). New York: ACM, 2006: 79-88.
[3]	STEFANOV E, PAPAMANTHOU C, SHI E. Practical Dynamic Searchable Encryption with Small Leakage[EB/OL]. (2014-02-22)[2024-04-06]. https://www.ndss-symposium.org/wp-content/uploads/2017/09/07_2_1.pdf.
[4]	BOST R. Σoφoς: Forward Secure Searchable Encryption[C]// ACM. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1143-1154.
[5]	BOST R, MINAUD B, OHRIMENKO O. Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives[C]// ACM. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1465-1482.
[6]	SUN Shifeng, YUAN Xingliang, LIU J K, et al. Practical Backward-Secure Searchable Encryption from Symmetric Puncturable Encryption[C]// ACM. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 763-780.
[7]	CHAMANI J G, PAPADOPOULOS D, PAPAMANTHOU C, et al. New Constructions for Forward and Backward Private Symmetric Searchable Encryption[C]// ACM. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1038-1055.
[8]	DEMERTZIS I, CHAMANI J G, PAPADOPOULOS D, et al. Dynamic Searchable Encryption with Small Client Storage[EB/OL]. [2024-04-06]. https://www.ndss-symposium.org/wp-content/uploads/2020/02/24423.pdf.
[9]	AARAJ N, MARCOLLA C, ZHU Xiaojie. Exipnos: An Efficient Verifiable Dynamic Symmetric Searchable Encryption Scheme with Forward and Backward Privacy[C]// Springer. 22nd International Conference on Cryptology. Heidelberg: Springer, 2021: 487-509.
[10]	SUN Shifeng, STEINFELD R, LAI Shangqi, et al. Practical Non-Interactive Searchable Encryption with Forward and Backward Privacy[EB/OL]. [2024-04-06]. https://www.ndss-symposium.org/wp-content/uploads/ndss2021_2C-4_24162_paper.pdf.
[11]	CHAMANI J G, PAPADOPOULOS D, KARBASFORUSHAN M, et al. Dynamic Searchable Encryption with Optimal Search in the Presence of Deletions[EB/OL]. [2024-04-06]. https://home.cse.ust.hk/-dipapado/docs/opt.pdf.
[12]	MONDAL P, CHAMANI J G, DEMERTZIS I, et al. I/O-Efficient Dynamic Searchable Encryption meets Forward & Backward Privacy[EB/OL]. [2024-04-06]. https://www.usenix.org/conference/usenixsecurity24/presentation/mondal.
[13]	KAMARA S, PAPAMANTHOU C. Parallel and Dynamic Searchable Symmetric Encryption[C]// Springer. Financial Cryptography and Data Security:17th International Conference. Heidelberg: Springer, 2013: 258-274.
[14]	CHEN Chi, ZHU Xiaojie, SHEN Peisong, et al. A Hierarchical Clustering Method for Big Data Oriented Ciphertext Search[C]// IEEE. 2014 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). New York: IEEE, 2014: 559-564.
[15]	CHEN Chi, ZHU Xiaojie, SHEN Peisong, et al. An Efficient Privacy-Preserving Ranked Keyword Search Method[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(4): 951-963.
[16]	TIAN Xue, ZHU Xiaojie, SHEN Peisong, et al. Efficient Ciphertext Search Method Based on Similarity Search Tree[J]. Journal of Software, 2016, 27(6): 1566-1576.
	田雪, 朱晓杰, 申培松, 等. 基于相似查询树的快速密文检索方法[J]. 软件学报, 2016, 27(6): 1566-1576.
[17]	GE Xinrui, CUI Wei, HAO Rong, et al. Verifiable Keywords Ranked Search Scheme over Encrypted Cloud Data[J]. Netinfo Security, 2019, 19(7): 82-89.
	葛新瑞, 崔巍, 郝蓉, 等. 加密云数据上支持可验证的关键词排序搜索方案[J]. 信息网络安全, 2019, 19(7): 82-89.
[18]	KAMARA S, PAPAMANTHOU C, ROEDER T. Dynamic Searchable Symmetric Encryption[C]// ACM. Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York: ACM, 2012: 965-976.
[19]	LAI R W F, CHOW S S M. Forward-Secure Searchable Encryption on Labeled Bipartite Graphs[EB/OL]. (2017-06-26)[2024-04-06]. https://link.springer.com/chapter/10.1007/978-3-319-61204-1_24.
[20]	BIHAM E. A Fast New DES Implementation in Software[EB/OL]. (2006-01-01)[2024-04-06]. https://link.springer.com/chapter/10.1007/BFb0052352.
[21]	CUI Yaxin, XU Hong, QI Wenfeng. An Efficient Method to Construct Differential and Linear Characteristics of Bit-Slice Block Ciphers[J]. Journal of Cryptologic Research, 2021, 8(1): 154-166.
	崔雅馨, 徐洪, 戚文峰. 比特切片型算法差分及线性特征的快速构造[J]. 密码学报, 2021, 8(1): 154-166. doi: 10.13868/j.cnki.jcr.000428
[22]	ZHANG Xiaocong, GUO Hua, ZHANG Xiyong, et al. Fast Software Implementation of SM4[J]. Journal of Cryptologic Research, 2020, 7(6): 799-811.
	张笑从, 郭华, 张习勇, 等. SM4算法快速软件实现[J]. 密码学报, 2020, 7(6): 799-811. doi: 10.13868/j.cnki.jcr.000407
[23]	WILLIAM W. Enron Email Dataset[EB/OL]. [2024-04-06]. https://www.cs.cmu.edu/-./enron/.
[24]	NTLK P. Ntlk Project[EB/OL]. [2024-04-06]. https://www.nltk.org/.

方案	支持并行更新	支持比特切片加速	检索效率	更新效率	通信轮次	前向安全	后向安全
Fides^[5]	?	?	O(a_w)	O(1)	2	√	√
Diana_del^[5]	?	?	O(a_w)	O(d_wloga_w)	2	√	√
Janus^[5]	?	?	O(1)	O(n_wd_w)	2	√	√
Janus++^[6]	?	?	O(n_wd_w)	O(d_w)	1	√	√
Mitra^[7]	?	?	O(a_w)	O(1)	2	√	√
SD_a^[8]	?	?	O(a_w+logN)	O(logN)	1	√	√
OSSE^[11]	?	?	O(n_w+logi_w)	O(log³N)	1	√	√
LSSE^[11]	?	?	O((n_w+logi_w)loglogN)	O(log²N)	1	√	√
本文方案	√	√	O(a_w)	O(1)	2	√	√