【支持通配符的常用技术分析4300字】

支持通配符的常用技术分析综述目录TOC\o"1-3"\h\u20921支持通配符的常用技术分析综述 1104811.1布隆过滤器 1147061.1.1布隆过滤器的构造 1126421.1.2支持单个通配符查询的可搜索加密 2187961.1.3支持多个通配符查询的可搜索加密 3197541.2关键词索引树 4153741.2.1基本介绍 4102341.2.2关键词索引树的构建 514351.2.3关键词索引树的搜索过程 8263621.3安全KNN方案 91.1布隆过滤器1.1.1布隆过滤器的构造1970年，布隆过滤器被首次提出来，该技术可以用来判断一个集合中是否拥有某个元素[26]，其主要思想是：将该元素输入至若干个哈希函数中，经过哈希运算后，会分别输出若干个值，将布隆过滤器上这几个值对应的位置设为“1”。当需要判断该元素是否在集合中时，只要判断这几个位置上的值是不是为“1”即可。因此布隆过滤器的详细构造流程可描述为以下几个步骤：首先先定义一些符号，符号及相对应的说明如表1.1所示表1.1布隆过滤器相关符号及说明符号说明含有n个元素的集合m布隆过滤器的长度k哈希函数的个数，每个哈希函数均不同第i个哈希函数，其中首先将布隆过滤器上m比特的值初始化为0，然后将集合中的某个元素，分别输入至k个哈希函数中，输出k个哈希值，同时把布隆过滤器中对应位置设为1。如此往复n次，将n个元素依次插入到布隆过滤器中。最后，当要查询集合S中是否拥有元素q时，则将q分别输入至k个哈希函数中，输出k个哈希值，观察布隆过滤器上这k个哈希值对应位置的值是否全为1，若是，则q存在集合S中，反之则反。下面给出一个生成布隆过滤器的例子。假设，布隆过滤器长度为10，独立选择三个不同的哈希函数。示例如图1.1所示图1.1布隆过滤器构造示例1.1.2支持单个通配符查询的可搜索加密本节将介绍支持单个通配符查询的可搜索加密，先考虑关键词中只含一个通配符的情况。其搜索的基本思想是首先为所有关键词分别生成一个布隆过滤器，并将其存储至数据库中作为索引。当需要搜索关键词时，用户再为待搜索的关键词构建一个布隆过滤器，然后将此布隆过滤器与数据库中的索引逐一进行比较得到符合要求的结果。在建立索引的过程中，假设某个长度为l个字符的关键词w，该关键词中每个字符可以记为，然后将得到一个索引集合其中表示字符在关键词中的正序位置，表示字符在关键词中的逆序位置。比如关键词为“drag”，那么它的索引集合为。在生成陷门的过程中，假设某个含有一个通配符且长度为l的搜索关键词w，其中每个字符分别记为，其中*表示通配符，且通配符在关键词中所处位置为i。对于通配符之前的字符，记录其正向顺序，即。对于通配符之后的字符，记录其逆向顺序，因此将得到一个陷门集合 比如含有一个通配符的搜索关键词为“d*g”，那么它的陷门集合为。由此容易观察到，如果含有通配符的搜索关键词与索引中的关键词相匹配的话，则陷门集合应该是索引集合的子集。容易观察到，该通配符能够表示若干个字符。最后再分别对陷门集合和索引集合生成两个布隆过滤器，并且比较两个布隆过滤器相应位置的值，判断两者是否匹配。图1.2给出了匹配过程的一个示例。图1.2单个通配符查询过程示例1.1.3支持多个通配符查询的可搜索加密一般来说，一个关键词中可能存在多个通配符，下面考虑含有若干通配符的情形，将对拥有两个通配符的搜索关键词“c*o*d”作为样例来进行阐释。此时，如果仍然使用上文提到的方法，则不能准确地描述字符“o”的位置，因此在生成陷门的时候需要考虑每个字符的存在性，所以可以在陷门布隆过滤器中添加字符“c、o、d”的存在性，约定用比特“0”表示该字符的存在性，将添加到陷门集合中。另外，陷门集合还需要记录第一个通配符之前所有字符的正向顺序和最后一个通配符后所有字符的逆向顺序。比如，含有两个通配符的搜索关键词“c*o*d”，其陷门集合为。与此同时，在建立索引的过程中，也要将关键词中每一个字符的存在性添加到索引布隆过滤器中。比如关键词“cloud”，它的索引集合为：图1.3给出了匹配过程的样例。图1.3多个通配符查询过程示例1.2关键词索引树1.2.1基本介绍通常来说，数据使用者希望能从云服务器中快速找到自己需要的文件，因此遍历文件集合中所有文件的方法一般是不可取的，所以需要考虑文件和查询关键词间的相关系数，从而对搜索结果进行排序，并将最满足搜索条件的前k个文件传输给用户。可以利用TF-IDF值来判断密文文件与搜索关键词之间的相关程度。下面将详细地介绍一种计算TF-IDF值来建立关键词向量的方案。首先需要从文件集合中提取m个关键词，并且为每一个文件构建一个m维的关键词向量，将其每一维都用一个确定的关键词来表示，并且将每一个元素的值都设置成对应关键词在文件中的TF-IDF值。TF值可由以下公式求得：（1.1）其中，是归一化因子，是关键词在文件中出现的频率。文件的逆文档频率IDF可用如下公式计算：（1.2）其中n表示文件总数目，表示包含关键词的文件个数，是归一化因子。1.2.2关键词索引树的构建文献[25]提出的REMKS方案构造了一个关键词索引树来加快搜索速度。索引树本质是一个平衡二叉树，其每一个叶子节点均分别代表一个文件，其中存放了向量形式的关键词的TF-IDF值。如图1.4为关键词索引树结构构造的一个样例，其中为文档集合。首先REMKS方案将内容相似的文件放在树中相邻的位置来节省不必要的计算开销。即先提取每个文档的TF-IDF值，比如的TF-IDF值为(0,0.2,0.6,0.7)，的TF-IDF值为(0,0,0.5,0.6)等，并且将TF-IDF值相差最小的两个文件放在相邻的位置，比如的TF-IDF值与的TF-IDF值相差为（0.1，0.1，0.1，0），但与的TF-IDF值相差为（0.1，0.3，0.2，0.2）,与的TF-IDF值相差为(0.2,0.3,0.2,0.1)，同样与其他文件的TF-IDF值相比，的TF-IDF值与的TF-IDF值相差最小，因此将文件和文件放在了相邻位置，同理将和，和，和放在了相邻位置，由此往复得到了如图1.4的文件顺序。然后每次选取两个相关性最高的文件相应的叶子节点，并且构造父节点，父节点也表示为向量形式，其每一维的值等于左右子节点中向量相应位置较大的值。比如父节点由子节点和子节点构造的，记为节点（可以为叶子节点也可以为父节点）TF-IDF向量第k维元素的值。分别比较和TF-IDF向量各个维度元素的大小，比如，因此；，因此；，因此；，因此。重复以上操作至构造至根节点。图1.4关键词索引树构建数据拥有者为了把文件集合外包给云服务器，并且让其他用户能够从中搜索到符合要求的文件，因此需要构造一个索引树结构，并且加密该索引树结构外包给云服务器来完成搜索操作。首先从每个文件中提取对应的关键词，并且分别计算每个关键词和对应文档之间的相关程度，即TF-IDF，同时将每个关键词TF-IDF值的向量形式作为文档的索引。为了加快索引树的搜索速度，REMKS方案还将相关程度最高的两个文档放在相邻的位置。树中的每个节点记为U，其由五个部分构成，分别是节点的id值，左右子节点，，所对应文件的索引码fid，以及向量，即。如果节点U为叶子节点，为从所有文件中提取的各关键词以及和该叶子节点相应文件的TF-IDF值，fid的值为该文件的文件标识符。否则每一维的值等于左右子节点每一维元素向量中中较大的值，且fid记为null。此外，还使用索引节点集INX（IndexNodeSet）来存储叶子节点。索引树可以用如下算法来构造：算法1：关键词搜索树构造算法输入：文件集合，文档的标识符，以及关键词向量。输出：关键词索引树TStep1：将文件集合F中的每个文件都与索引树中的叶子节点一一对应，其中叶子节点的id值可由id生成函数GenID来生成。因为该节点是叶子节点，所以左右子节点；存储了从文件中提取的关键词以及和该叶子节点相应密文文件的TF-IDF值。最后将节点相关信息存储到索引节点集合INX中。Step2:计算文件与文件的相关程度，当有偶数个文件时，每次从INX中取出两个相关程度最大的文件节点，如果以为子节点，为它们构造父节点，由id生成函数GenID()生成；为这个节点的左子节点，为这个节点的右子节点；向量中的第i维为两个子节点向量中第i维元素的较大值，即因为只有叶子节点才能代表特定的文件，而父节点无法代表文件，因此fid=null。当有奇数个文件时，转到Step3。Step3:当有奇数个文件时，即n为奇数，每次从INX中选取两个相关程度最高的文件所对应的节点，并为它们构造父节点，直到INX中只剩下最后三个节点，之后再选取两个相关程度最大的文件，为它们构建父节点，并将它们的父节点和INX中最后的那个节点构造父节点。Step4:依据Step2，自下向上依次构造父节点直到根节点，并由此获得一个关键词索引树T。1.2.3关键词索引树的搜索过程构建关键词索引树能够很大程度加快了查询的速度，将查询的时间复杂度优化到了。我们将通过这一节详细介绍在关键词索引树上进行搜索的方法，并迅速找到最符合匹配条件的前k个文件。我们采用可剪枝的深度优先搜索算法对索引树进行搜索，得到搜索结果，即最符合查询条件的前k个文件，根据文件和关键词相关分数按降序排序[25]。由和fid两部分构成，表示文件与查询关键词之间的相关分数，其中fid表示文件的文件标识符。算法2：关键词的搜索树搜索算法输入：关键词索引树T，搜索令牌token输出：前k个最相关的文档集合RSTStep1:使用深度优先搜索对索引树进行搜索。首先分别计算左右子节点与查询的关键词之间内容相关分数Score，并且记录Score较大的节点的相关信息。如果该节点不是叶子节点，那么递归向下一直搜索到叶子节点，否则将节点信息存入到集合RST中。Step2:一直递归使用Step1的方法，直到集合RST中已经存储了k个叶子节点的信息为止，然后按照RST中的结果按降序进行排序。Step3:继续递归。如果RST中第k个节点的相关分数大于子节点的相关分数，则将这个节点剪枝，也就是不搜索这个节点所对应的子树，否则依次递归至叶子节点，同时将集合RST中最后一个元素的节点信息作为新的叶子节点信息插入其中。Step4:此时最满足搜索条件的k个文件与集合RST中的节点一一对应，同时将这些密文文件返回给数据使用者。1.3安全KNN方案安全KNN方案（Securek-NearestNeighborScheme）允许对加密数据集上k个连续的数据进行高效计算，一般应用于加密索引和查询。本文在后续提到的PIPE方案则是基于安全KNN思想提出来的方案。下面定义一些参数。设表示安全参数，该参数应足够长，以防止暴力攻击（例如，128位）。给定向量v，它的第i个元素用v[i]表示。用符号“*”和“·”分别表示矩阵乘法和向量内积。用和分别表示M的逆矩阵和转置矩阵。如下为KNN方案的构造：：将安全参数作为输入产生一个私钥，其中表示可逆矩阵，s是一个d维的二进制向量。在向量s中，0的数量应该和1的数量近似一样，最大地保证随机化：将一个索引向量分裂为两个向量，分裂规则如下所示，对于i从1到d的范围内变化时，如果s[i]=1，那么p[i]