基于比特切片的高效动态可搜索加密方案

doi:10.3969/j.issn.1671-1122.2024.09.001

信息网络安全 ›› 2024, Vol. 24 ›› Issue (9): 1309-1316.doi: 10.3969/j.issn.1671-1122.2024.09.001

基于比特切片的高效动态可搜索加密方案

周健聪¹^,², 朱晓杰³(), 陈驰¹^,²

1.中国科学院信息工程研究所，北京 100085
2.中国科学院大学网络空间安全学院，北京 100049
3.阿卜杜拉国王科技大学，吉达 23955-6900

收稿日期:2024-04-29 出版日期:2024-09-10 发布日期:2024-09-27
通讯作者: 朱晓杰 xiaojie.zhu@kaust.edu.sa
作者简介:周健聪（1992—），男，北京，工程师，博士研究生，主要研究方向为动态可搜索加密|朱晓杰（1989—），男，浙江，博士，主要研究方向为云安全、应用密码学及分布式系统|陈驰（1978—），男，山东，正高级工程师，博士，主要研究方向为数据安全、云计算安全

Efficient Dynamic Searchable Encryption Scheme Based on Bitslicing

ZHOU Jiancong¹^,², ZHU Xiaojie³(), CHEN Chi¹^,²

1. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, China
2. School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
3. King Abdullah University of Science and Technology University, Jeddah 23955-6900, Saudi Arabia

Received:2024-04-29 Online:2024-09-10 Published:2024-09-27

摘要/Abstract

摘要：

可搜索加密作为提升云存储中数据安全性的重要技术，得到学界和产业界的持续关注。动态可搜索加密方案指支持数据集合更新的可搜索加密方案。在大型数据集场景中，由于更新操作会造成大量数据的重加密及索引重构，因此更新效率低下成为制约该技术应用的关键瓶颈。文章提出了一种基于比特切片的高效动态可搜索加密方案（BSSE），该方案采用分块并行加密的思想，利用比特切片技术将每个数据块加密单元由字转置为比特，消除了加密过程中的移位操作，并通过将S盒化简为逻辑电路，提升了大数据集场景下的并行效率。实验结果表明，BSSE方案较现有方案更新速度提升59倍，有效地提升了可搜索加密方案的更新效率，具有广泛的应用前景。

关键词: 可搜索加密, 比特切片, 并行

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

中图分类号:

TP309

周健聪, 朱晓杰, 陈驰. 基于比特切片的高效动态可搜索加密方案[J]. 信息网络安全, 2024, 24(9): 1309-1316.

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

图/表 4

参考文献 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	√	√

基于比特切片的高效动态可搜索加密方案

Efficient Dynamic Searchable Encryption Scheme Based on Bitslicing

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 24

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张学旺, 陈思宇, 罗欣悦, 雷志滔, 谢昊飞. 面向云辅助工业物联网的高效可搜索属性基加密方案[J]. 信息网络安全, 2024, 24(9): 1352-1363.
[2]	李强, 沈援海, 刘天旭, 黄晏瑜, 孙建国. 面向尺寸模式保护的高效对称可搜索加密方案[J]. 信息网络安全, 2024, 24(6): 843-854.
[3]	叶清, 何俊霏, 杨智超. 基于格的可搜索公钥加密研究进展[J]. 信息网络安全, 2024, 24(6): 903-916.
[4]	王南, 袁也, 杨浩然, 文周之, 苏明, 刘晓光. 环保大数据在区块链中的隐私计算[J]. 信息网络安全, 2024, 24(10): 1515-1527.
[5]	秦宝东, ，陈从正, ，何俊杰, 郑东. 基于可验证秘密共享的多关键词可搜索加密方案[J]. 信息网络安全, 2023, 23(5): 32-40.
[6]	李春晓, 王耀飞, 徐恩亮, 赵钰. 基于双线性映射的区块链安全范围搜索技术研究[J]. 信息网络安全, 2023, 23(3): 22-34.
[7]	王健, 黄俊. 基于智能合约的日志安全存储与公平访问方法[J]. 信息网络安全, 2022, 22(7): 27-36.
[8]	涂国庆, 杨延浩, 刘树波. Geohash编码抗k近邻攻击的脆弱性分析[J]. 信息网络安全, 2021, 21(2): 10-15.
[9]	张应辉, 朱甜, 郑东. 基于区块链的多关键字细粒度可搜索加密方案[J]. 信息网络安全, 2021, 21(2): 34-44.
[10]	李秀滢, 吉晨昊, 段晓毅, 周长春. GPU上SM4算法并行实现[J]. 信息网络安全, 2020, 20(6): 36-43.
[11]	周权, 杨宁滨, 许舒美. 基于FBDH算法的容错可验证公钥可搜索加密方案[J]. 信息网络安全, 2020, 20(3): 29-35.
[12]	张玉磊, 刘祥震, 郎晓丽, 王彩芬. 云环境下基于无证书的多服务器可搜索加密方案[J]. 信息网络安全, 2019, 19(3): 72-80.
[13]	陈亚楠, 梅倩, 熊虎, 徐维祥. 适用于工业物联网的无证书并行密钥隔离签名[J]. 信息网络安全, 2018, 18(10): 1-9.
[14]	马军岩, 曾国荪. 基于MapReduce的开源代码并行爬取方法研究与实现[J]. 信息网络安全, 2018, 18(1): 58-66.
[15]	陈兰香, 邱林冰. 基于Merkle哈希树的可验证密文检索方案[J]. 信息网络安全, 2017, 17(4): 1-8.