A Secure and Dynamic Multi-Keywo

系统框架

image.png

数据拥有者DO构建加密索引树，将加密文档和索引外包给云服务。
云存储服务根据数据使用者Data User发来的数据搜索token和已经存好的加密索引树进行搜索，返回top K个排序结果。
排序的计量方法根据TF-IDF公式计算相似度。
Term Frequency: the number of times a given term appears within a document
Inverse Document Frequency: dividing the cardinality of document collection by the number of documents containing the keyword.

创新点

• 设计了一个树状的加密索引结构，可以支持更加灵活的动态更新操作，并且支持多关键字的排序Top K查询。
• 检索时间和树高度相关，即对数级别，使用贪心的深度优先遍历搜索方法，达到搜索的高效性。
• 保证了隐私：索引和查询的隐私；存储关键字的隐私；搜索token的隐私；数据文档的隐私

关注非加密索引树的构建：

• 根据每个文档，建立对应的叶子结点。每个叶子结点都包含有信息：<ID,D,Pl,Pr,FID>. ID是叶子结点的标识符，D为规定m维度关键字向量，每一个维度是所包含对应关键字的规范化的TF值。

• 中间结点的生成：中间节点是基于叶子结点计算而成。关于第i维度向量的计算，根据下面的公式：

  
  image.png
  

  两个叶子结点生成一个上层中间节点。两个中间节点进一步生成上层中间节点。所以索引树为一颗二叉树。
  上层节点中存储向量的对应位置为其两个子节点对应位置的最大值，这样过构建之后可以更加方便Top-K贪心算法的执行。
  观察这个例子，设定关键字的最大维度为4；一共有6个文件。

  
  image.png
  树需要确定对应关键字的最大维度，并且每一个节点都包含了对应维度大小的向量。（是否需要优化对应存储代价？）

利用非加密索引树的Top-K检索

搜索算法为一个基于递归的‘贪心深度优先搜索’算法。需要使用RList作为存储找到结果前的当前结果列表。RList中记录了对应文件的<RScore,FID>. RScore为文件和查询Q之间的相似度，FID为文件的编号。

Formula of the Relevance Score

在RList中，tuple是按照对应RScore降序排列的。在搜索的过程中可以动态更新RList以寻求Top-K结果。

非加密的搜索算法
步骤十分简单

• 如果当前的搜索节点不是一个叶子结点，需要计算出此节点和查询Q之间的相似度RScore，如果RScore大于当前RList当中最小的相似度，则进一步搜索其两个子节点。注意，要先搜索对应相似度高的子节点，再搜索相似度低的子节点。这符合贪心算法的基本做法。

可能改进或应用到科研场景中的因素

• 需要预先确定关键字的维度大小，即最多有多少关键字。这对于搜索树的构建有直接的影响。（考虑动态的关键字库将会导致对于IDF值的计算，每一次增加或删除文件都会导致关键字的变化，IDF的变化）
• 尽管此系统支持数据的动态更新，数据拥有者必须预先对搜索树进行维护，将构建好的更新子树发送给服务提供者SP进行下一步更新。这对数据拥有者的计算资源是有要求的。
• 应该考虑到非加密搜索树的Top-K搜索和传统的基于inverted index的Top-K 搜索之间的相同点和不同点。对构建索引的时间复杂度、搜索的时间复杂度、存储的空间复杂度都应有相应的分析。
  下一篇将会对加密算法进行理解。