多关键词动态可搜索加密方案_袁承昊.pdf

2023 年 4 月 Chinese Journal of Network and Information Security April 2023 第 9 卷第 2 期 网络与信息安全学报 Vol.9 No.2 多关键词动态可搜索加密方案 袁承昊1，李勇1，任爽2 （1北京交通大学电子信息工程学院，北京 100044；2北京交通大学计算机与信息技术学院，北京 100044）摘 要：云存储用户将数据外包存储至云服务器以节省本地存储资源。然而，云存储数据脱离了用户的物理控制范围，可导致云端隐私数据被恶意窃取或泄露。目前动态可搜索加密方案多以对称可搜索加密为主，需要预先建立安全的密钥共享信道，难以直接应用于云存储数据共享场景。针对云存储多方数据的安全共享场景，提出了一种多关键词动态可搜索加密方案。该方案通过引入布谷鸟过滤器构建正向索引，实现数据拥有者对文档及索引的动态添加和删除。同时结合双线性对与拉格朗日插值多项式，可支持多关键词的联合搜索。为降低密文检索阶段的计算开销，采用倒排索引与正向索引结合的构造，以提高云服务器的检索效率。基于判定线性 Diffie-Hellman 问题，在适应性选择关键词攻击下可证明方案的安全性。通过实验分析所提方案在不同数据集中进行关键词搜索及索引更新的执行效率，结果表明所提方案可有效避免检索时间与密文数量的线性相关性，降低了数据量较大情况下更新操作中的计算开销。关键词：可搜索加密；云存储；布谷鸟过滤器；倒排索引 中图分类号：TP393 文献标志码：A DOI:10.11959/j.issn.2096109x.2023028 Dynamic multi-keyword searchable encryption scheme YUAN Chenghao1,LI Yong1,REN Shuang2 1.School of Electronic and Information Engineering,Beijing Jiaotong University,Beijing 100044,China 2.School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China Abstract:Users of cloud storage often outsource their data to cloud servers to save local storage resources.However,cloud storage data is out of the users physical control,which may lead to malicious theft or disclosure of private data on cloud.At present,dynamic searchable encryption schemes are mostly based on symmetric searchable encryption,which need to establish a secure key sharing channel in advance,and cannot be directly applied to data sharing in cloud storage scenarios.For the secure sharing scenario of multi-party data in cloud storage,a dynamic multi-keyword searchable encryption scheme was proposed.The forward index was constructed by a cuckoo filter to enable data owners to perform documents and index dynamic updates.The conjunctive multi-keywords search 收稿日期：20220721；修回日期：20230219 通信作者：李勇， 基金项目：国家自然科学基金（62072025）；2020 年工业互联网创新发展工程项目（TC200H01V）Foundation Items:The National Natural Science Foundation of China(62072025),2020 Innovative Development Project ofthe Industrial Internet(TC200H01V)引用格式：袁承昊,李勇,任爽.多关键词动态可搜索加密方案J.网络与信息安全学报,2023,9(2):143-153.Citation Format:YUAN C H,LI Y,REN S.Dynamic multi-keyword searchable encryption schemeJ.Chinese Journal ofNetwork and Information Security,2023,9(2):143-153.144 网络与信息安全学报 第 9 卷 was supported by combining bilinear pairing with Lagrangian interpolation polynomials.To reduce the computational overhead in the ciphertext retrieval phase,a combination of inverted index and forward index was constructed to improve the retrieval efficiency of cloud server.This scheme is provably secure with the indistinguishability in adaptively chosen keyword attack under decision linear Diffie-Hellman problem.Simulation experiments were conducted to analyze the execution efficiency of the scheme for keyword search and index update in different datasets.The results show that the scheme effectively avoids the linear correlation between the retrieval time and the number of ciphertexts,and reduces the computational overhead in the update operation with a large amount of data.Keywords:searchable encryption,cloud storage,cuckoo filter,inverted index 0 引言 云存储技术可为各类互联网应用提供灵活便捷的智能化服务，帮助用户低成本、高效率地按需外包存储个人数据1。虽然云存储技术具有灵活性、可靠性、高可扩展性等优势，但仍然面临着较为突出的安全问题，其中数据安全问题是云存储技术面临的最为严峻的问题之一2。攻击者可在未经授权的情况下查看、窃取甚至恶意篡改云平台中存储的敏感数据，导致用户或企业的隐私信息泄露，造成无法挽回的损失。为提高云存储数据的安全性及可用性，动态可搜索加密技术允许用户对云存储数据进行动态管理，同时保证加密数据的搜索功能，在云存储环境中具有重要的应用价值。1 相关工作 Song 等3提出了第一个对称可搜索加密方案。早期的可搜索加密方案主要围绕静态可搜索加密，默认对一个不可更改的数据库进行加密搜索。若存储数据需要更新时，静态可搜索加密方案需要对整个数据库重新构建加密索引，庞大的计算开销无法适应云存储用户对数据添加或删除的需求。为解决该问题，Kamara 等4提出动态可搜索加密方案，该方案以对称可搜索加密为基础，在索引构建过程设置一个删除矩阵，删除矩阵中存储各文档包含的关键词列表。倒排索引中的“关键词文档”对均存在一个指针指向删除矩阵中的对应条目。当用户对某文档提交删除操作时，删除矩阵中该文档的关键词列表将会被删除。然而，删除操作通常仅针对小范围的文档，而该方案需要对全部文档重新建立一个用于判断删除操作的矩阵，这将带来较高的存储开销，但并未分析文档的动态更新带来的安全风险。对于动态更新可搜索加密方案的安全性，Stefanov 等5定义了对称可搜索加密前向安全性，并给出满足该安全性的具体构造。前向安全性是指云服务器无法获知添加的文档是否包含已被检索的关键词。但该方案要求用户使用若干个密钥计算文件的动态添加后的索引，因此其计算开销较大，且不支持文档的删除操作。Bost 等6定义文档删除场景的后向安全性，即云服务器仅可获知关键词匹配的文档以及该关键词和文档的更新时间。在二者的研究基础上，Chamani 等7提出一种同时满足前向及后向安全性的对称可搜索加密方案，并且该方案通过不经意映射将文档更新的复杂度降低至亚线性，有效提升了检索效率。Demertzis 等8同样使用不经意映射，从减轻更新过程用户端存储开销的角度提出了具体的方案，但该方案需要进行多次信息交互，带来较高的计算开销。近年来，加密云场景下支持动态更新的多关键词搜索问题，得到了广泛关注。Zhong 等9提出了一种支持文件动态更新的多关键词模糊搜索方案，通过局部敏感哈希和布隆过滤器构建索引及查询向量，并利用索引树提升了方案的检索效率。Zhang 等10结合索引树及连接多关键词的搜索模式，提出了一种支持动态添加及删除的可搜索加密方案 T-PECK。该方案将算法复杂度降低至亚线性，一定程度上提升了检索效率。但随着索引数量增加，在更新过程中，数据拥有者需要重新生成一个新的索引树，再由云服务器进行合并，因此对于更新阶段的效率仍有进一步研究及优化的空间。第 2 期 袁承昊等：多关键词动态可搜索加密方案 145 2 方案概述 2.1 系统模型 多关键词动态可搜索加密系统模型包含以下3 种实体：数据拥有者、数据使用者和云服务器，如图 1 所示。数据拥有者可以是个人、企业或者组织，其希望将部分文档外包存储于云服务器，以节约本地的存储资源开销。数据使用者由数据拥有者指定，可通过关键词查询方式获取数据拥有者上传的文档。云服务器具有海量的存储资源、高效的计算能力，可完成加密文件的检索任务。图 1 多关键词动态可搜索加密系统模型 Figure 1 Dynamic multi-keyword searchable encryption system model 云存储数据的动态更新包括文档及索引的添加和删除两个过程，更新过程示意如图 2 所示。在添加过程中，数据拥有者发送给云服务器请求更新的消息，包括待添加的加密文档标签及其加密正向索引，以及倒排索引条目。云服务器将正向索引添加至布谷鸟过滤器11中，更新加密的倒排索引和文档。同时，数据拥有者将更新的关键词计数器信息发送给数据使用者。图 2 云存储数据更新过程示意 Figure 2 Diagram of cloud storage data update process 对于删除过程，数据拥有者向云服务器发送请求删除的消息，提交待删除文档的标签、该文档对应的正向索引和更新的倒排索引条目。删除过程与添加过程类似，不同之处在于云服务器需要在布谷鸟过滤器和文档存储路径中删除正向索引和密文。2.2 方案形式化定义 本文方案由以下多项式时间算法组成