为满足用户对云端文档动态更新的需求, 支持动态更新的可搜索加密方案成为了研究热点. 但目前已知方案对于索引结构的更新多采用尾部直接插入的方法, 造成了新添加关键字和文档之间关联性的泄露. 为此本文提出一种基于语义分组的动态可搜索加密方案. 首先构建分组平衡二叉树作为索引结构, 通过语义分组减少搜索时访问的节点数, 提高搜索效率. 然后结合分区矩阵的思想, 在矩阵中添加虚拟关键字保证更新时的安全性. 最后通过形式化的证明分析了本文方案的安全性.
Searchable encryption scheme supporting dynamic update has become a research hotspot to meet the needs of users for dynamic update of cloud documents. However, most of the known schemes update the index structure by the direct insertion at the tail, which leads to the leakage of the relationship between the newly added keywords and the document. Therefore, this study proposes a dynamic searchable encryption scheme based on semantic grouping. Firstly, the balanced binary tree is constructed as the index structure, and the number of nodes is reduced by semantic grouping for search efficiency improvement. Then, in light of the idea of partition matrix, virtual keywords are added to the matrix to ensure the security of update. Finally, the security of the scheme is analyzed by formal proof.
为了降低本地资源的计算开销, 越来越多的人选择将个人数据上传到不可信的云存储服务器中, 然而云服务器存在泄露用户隐私的诸多威胁. 权衡云环境既存在安全威胁又具备便利性的特点, 很多人将本地信息加密后在上传到云服务器中从而起到保护数据安全的作用. 随着用户和企业数据存储量逐年增长, 如果将全部数据不加区分地放在一起进行加密和搜索, 不仅增加加密复杂度, 而且影响搜索效率.
可搜索加密(Searchable Encryption, SE)技术[
上述方案基本解决了SSE方案搜索需求的问题. 但是本地数据的大量产生, 用户急需对云端的文档进行更新从而保证文档的完整性. 这使得支持动态更新的SE方案成为新的研究热点. 然而Zhang等人[
为应对恶意服务器环境, Wang等人[
为提高搜索效率, 2019年Xu等人[
为提高更新效率, 2020年Huang等人[
在多用户场景下, Wang等人[
上述方案虽然在性能和效率方面取得巨大提升, 但对索引结构的更新大多采用在已有索引的尾部直接添加的方法, 泄露了新添加关键字和已有文档的信息, 以及新添加关键字在字典中排列的位置. 这造成更新时极大的安全隐患.
为此本文提出了基于语义分组的动态更新可搜索加密方案(Scheme of Dynamic Searchable Encryption based on semantic grouping, SDSE). 首先通过TF-IDF和空间向量模型构建节点向量, 根据计算节点的相关性进行语义分组构建索引树. 然后向节点向量中添加虚拟关键字完成向量扩充, 保证字典排布的安全性. 最后结合分区矩阵思想提出一种更新方法. 实现了在原有关键字字典的基础上能够动态更新云端文件.
(1) 数据拥有者DO创建关键词字典、加密文档、构建安全索引, 将它们上传到云服务器.
(2) 用户DU生成查询陷门, 并将陷门和想要返回的结果数量
(3)云服务器收到DU的搜索请求后, CS对加密索引进行搜索, 并计算返回用户最希望的前
系统模型图
Left, right:
ResultNodeSet:
本文方案的安全性主要有如下两个概率游戏验证
定义1. 泄露函数
1)
2)
3)
定义2.
如果方案SDSE对于自适应关键字搜索是安全的, 那么对于任意多项式时间内的敌手, 一定存在模拟器
空间向量模型和TF-IDF规则是解决传统搜索领域的有效手段, 通过建立关键词字典集合与查询文档之间的关系, 实现多关键词的有效排序搜索.
其中,
向量空间模型将文档和查询都看成是关键词的集合, 是关键词的有序排列. 我们可以根据倒排序列构建关键词的字典, 用二进制向量来表示文档和查询. 把查询抽象化为数学形式表示, 用0和1表示查询文档中是否存在词典对应位置的关键词.
ASPS算法由Wang等人[
定义3. 非对称保内积加密. 对于加密算法
SDSE方案由如下5个算法组成: (初始化(
(1)
(2)
(3)
(4)
(5)
(1)
初始化阶段DO根据关键词字典产生用于拆分索引和查询向量的
(2)
构建索引分为如下5个步骤.
1) 抽取关键词 : 数据拥有者对文档集
2) 构建明文形式的二进制索引: 根据空间向量模型数据拥有者为文档
3) 生成加权索引: 本文中关键词的权重由关键词出现的概率以及它出现的位置决定. TF-IDF的方法来计算关键词和文档之间的相关度. 在根据关键词在文中所处的位置分别赋予不同的权重, 本文把关键词的位置分为如下3类: 标题, 摘要, 正文. 分别使得标题占0.6, 摘要占0.3, 正文占0.1的权重. 假设某文档
其中,
4) 构建索引树: 本方案设计了一种新的索引结构-分组平衡二叉树, 构建这种树型索引时, 以自下而上的策略对每一层的树节点进行分组, 使得主题越接近的文档尽可能地分布于索引树的同一分支.
所有叶子结点生成完毕后, 采用自下而上的策略, 基于分组构造索引树. 每一层的非叶子结点都是由分组算法生成, 把加权索引的余弦值较小的两个结点组成一对.
为完成节点分组, 设计了算法1.
算法1. 树节点分组算法
输入: 当前需要处理的节点集PendingNodeSet
输出: 节点分组完的集合ResultNodeSet
1. while PendingNodeSet中的节点大于1do
2. 在PendingNodeSet里边随机选择节点
3. 寻找一个非
4. 将节点对(
5. 将
6. end while
7. if PendingNodeSet非空 then
8. 将PendingNodeSet中唯一的节点插入到ResultNodeSet集合的末尾
9. end if
10. return ResultNodeSet
树节点分组完成后, 如果节点总数为2
由算法1构成的索引树如
由6个文件、5个关键词构成的索引树
5) 加密明文索引树: 索引树构建完成后把节点向量动态扩充为
(3)
1) 首先根据查询的关键词
2) DO通过ASPE加密算法对向量
(4)
收到DU的搜索请求后, CS使用深度贪婪优先算法在上传的加密安全索引树上进行搜索. 具体形式如算法2.
算法2. 深度贪婪优先搜索算法
输入: 索引树
输出: top
1. if
2. if score(
3. search (
4. search (
5. end if
6. else
7. if score(
8. 更新结果列表result和
9. end if
10. end if
在分组平衡二叉树中是如何执行贪婪深度优先搜索的过程如
分组平衡二叉树查询
当计算加密索引和安全陷门相关后, 返回得分前
(5)
DO根据本地文档更新需求, 对云端的文档进行更新. 为避免动态更新时泄露关键字和文档相关性信息, 本文采用分区矩阵的思想. 在更新关键字字典时同时添加
为完成加密生成
分区矩阵保证了已有的节点向量不变的基础上, 仅对更新文档进行构建加密. 既不会泄露新添加关键字在字典中的分布, 也减少了更新时产生的计算开销.
本节进行证明即使矩阵扩展到
根据定义1可知, 本文方案执行搜索和更新时会泄露相关的信息. 在分析SDSE方案的安全性之前, 我们假设加密明文文档的对称加密算法是满足选择明文攻击(CPA)的.
根据定义2可得, 如果本文方案满足对于任意多项式时间内的敌手都能使得式(14)成立:
那么我们认为本文方案在自适应不可区分的意义上是安全的. 敌手可以通过分析密钥、索引、密文、陷门的不相关、关键字字典来获得模拟游戏的胜利.
具体的证明过程如下:
本文方案中的安全密钥是由两个(
本文方案中的索引是由关键字字典加虚拟关键字在ASPE加密算法加密后得到. 通过添加虚拟关键字模糊真实关键字的数量起到隐藏与关键字有关的标识符. 由于ASPE算法加密结果的不确定性使得即使得相同明文加密得出的密文也不同. 故在计算上也是不可区分的. 故式(17)成立:
根据前提假设可知本文加密算法是满足CPA安全的, 故式(18)成立:
本文方案中陷门是由关键字请求向量加虚拟关键字构成. 即使搜索相同的关键字在不同的时间段产生的请求向量也是不同的. 然后通过ASPE加密算法进行加密更加无法判断. 故式(19)成立:
本文方案中初始的关键字字典的安全性是由虚拟关键字和ASPE加密保证的. 着重介绍更新时关键字字典的安全性. 对于新产生的关键字通过添加虚拟关键字来模糊其在字典中的位置, 然后通过分区矩阵的思想使其添加到原始字典中. 这使得在判断新添加关键字在字典中的位置以及相关文档的概率可以忽略不计. 故式(20)成立:
综上所述可得:
使得式(22)成立:
因此本文方案在泄露信息
本节从构建加密索引、搜索、更新3个方面进行效率分析, 将本文方案与文献[
在构建索引上, 本文方案和文献[
在关键词搜索方面, 其搜索的时间取决于访问的叶子节点数, 假设实际访问的叶子节点数为
在文档更新方面. 本文采用分区矩阵思想进行更新, 保持原有字典不变的基础上通过构建
通过与最新成果对比可得, 本文在搜索和更新方面具备较高效率.
本文提出了一种基于语义分组的动态关键词可搜索加密方案. 提出平衡分组二叉树作为索引结构使得返回的文档更符合用户的请求. 结合分区矩阵思想进行文档更新. 在保证关键字字典安全性的同时, 减少了更新时的计算开销. 与现有的方案相比, 本文方案具备更高的搜索效率和更新效率. 但本文方案只考虑了单用户模型, 为更贴近云服务工作的实际情况. 接下来的工作把本文方案拓展到多用户场景下.
效率分析对比
方案 | Index | Search | Update |
文献[ |
O( |
O( |
O( |
文献[ |
O(3 |
O( |
O( |
文献[ |
O( |
O( |
O( |
文献[ |
O( |
O( |
O(2 |
文献[ |
O( |
O( |
O( |
本文 | O( |
<O( |
O( |
吴志强, 李肯立, 郑蕙. 高效可扩展的对称密文检索架构. 通信学报, 2017, 38(8): 79–93.
et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data. Proceedings of the 30th IEEE International Conference on Computer Communications. Shanghai: IEEE, 2011. 829–837.]]>
Xia ZH, Chen L, Sun XM,
Wang HY, Fan K, Li H,
Xu GW, Li HW, Dai YS,
Huang K, Dong XL, Cao ZF,
et al. Geometric range search on encrypted data with Forward/Backward security. IEEE Transactions on Dependable and Secure Computing, 2020.]]>
孙晓玲, 杨秋格, 沈焱萍, 等. 改进的高效动态可搜索加密方案. 计算机应用研究, 2020, 37(8): 2472–2476.
et al. Multi-user forward secure dynamic searchable symmetric encryption. Proceedings of the 12th International Conference on Network and System Security. Cham: Springer, 2018. 125–140.]]>
卢冰洁, 周俊, 曹珍富. 一种增强的多用户前向安全动态对称可搜索加密方案. 计算机研究与发展, 2020, 57(10): 2104–2116.
et al. Secure kNN computation on encrypted databases. Proceedings of 2009 ACM SIGMOD International Conference on Management of Data. Providence: ACM, 2009. 139–152.]]>