一种支持偏好搜索和逻辑搜索的高效可验证的多关键字排序可搜索加密方法

技术领域

本发明涉及信息安全技术领域，具体涉及一种支持偏好搜索和逻辑搜索的高效可验证的多关键字排序可搜索加密方法。

背景技术

随着云计算的日益普及，为了减少数据管理、存储和计算的开销，数据拥有者会将其所拥有的大量的数据外包到云服务器进行存储或者处理。但是这样数据拥有则就失去了对数据的有力控制，这样数据就可能被云服务器或者入侵者获取、访问，但是这些数可能是涉及机密性和隐私性的数据如医疗记录，政府文档等。虽然云服务器一般声称是安全的，但是用户对云服务器提供的安全性机制一般是存疑的，这种担忧也是云计算进一步发展普及的障碍。

常用的保护数据隐私的机制就是将数据上传到云服务器之前，先加密数据，但是，加密会极大的限制数据的可用性。而如果采用简单的下载、解密、处理的机制的话那么就需要消耗大量的带宽和用户极大的计算开销，对于云计算这种理念是不适用的。目前也有大量基于同态加密的方案或者基于公钥的可搜索加密方案被提了出来，但是这些方案的计算往往因其巨大的计算开销而变得非常的不实用。所以仍然关注的是对称可搜索加密。在对称可搜索加密中，也有很多针对单关键字和多关键字的可搜索加密方案以及相应的改进方案被提了出来，但是这些方案的功能性相对较为单一，其中不少也存在极大的效率问题。目前对称可搜索加密的功能性仍然和明文的检索存在着非常大的差距，对称可搜索加密中的功能性如个性化检索、逻辑检索、语义检索、模糊检索、动态更新等仍然有待进一步的研究。

发明内容

本发明的目的是为了解决现有技术中的上述缺陷，提供一种支持偏好搜索和逻辑搜索的高效可验证的多关键字排序可搜索加密方法。

本发明的目的可以通过采取如下技术方案达到：

一种支持偏好搜索和逻辑搜索的高效可验证的多关键字排序可搜索加密方法，所述的加密方法包括下列步骤：

数据拥有者作为数据的所有者进行可搜索加密的预处理，包括密钥的生成、文档的加密、索引的生成、摘要的生成，数据拥有者将所持有的文档数据加密得到密文文档集合E，数据拥有者基于文档集合FS构建安全索引同时数据拥有者生成消息摘要，然后，数据拥有者将加密后的密文文档集合E连同文档的消息摘要和密文索引上传到云服务器，同时，数据拥有者授权数据使用者访问其外包数据,即与数据使用者共享密钥，包括用于加密文档的对称密钥和加密陷门的秘密钥；

数据使用者作为和数据的所有者共享密钥的用户，向云服务器提交查询以进行搜索，当数据使用者想要检索文档时，首先，将查询转为查询陷门T_Q，然后，查询陷门T_Q以及数据使用者的目标文档数目被提交到云服务器；一旦云服务器接收到查询陷门T_Q，云服务器执行计算任务；计算完成，云服务器返回排序后top-K个最相关的文档以及相关的验证对象；最后，数据使用者接收到top-K个最相关的文档和相关的验证对象，执行验证算法来验证搜索结果的准确性和完全性，然后再解密得到搜索结果；

云服务器向数据拥有者提供“按需计费”的存储和计算服务，向数据使用者提供查询服务，云服务器存储有密文文档和密文索引，一旦接收到来自数据使用者发送过来的查询陷门T_Q和目标数目K，云服务器利用密文索引和查询陷门T_Q进行安全检索，得到top-K个最相关的加密文档，按与查询的相关性大小排序后生成验证对象，然后将top-K个最相关的密文文档和验证对象发送给数据使用者。

进一步地，所述的数据拥有者生成用户加密文档的对称密码和加密文档向量的秘密钥，即两个可逆矩阵和一个随机的比特向量；

所述的数据拥有者使用对称密钥来加密文档内容，同时使用向量空间模型和TF×IDF来抽象文档的内容以及相关权重，构造明文二叉树索引后，然后递归加密整个二叉树索引，加密过程中根据随机比特向量将文档向量按照一定的规则切分成两个子向量，然后分别使用两个可逆矩阵的转置矩阵来加密两个子向量，同时数据拥有者根据文档内容和密钥生成文档的消息摘要用于在搜索阶段生成验证对象以保证可验证性。

进一步地，所述的数据拥有者使用二叉树来组织索引，其中，构造二叉树过程如下：首先每个文档作为一个叶子结点，然后会选择当前最相关的两个文档，然后按照一定的规则构造其父节点，然后继续选择剩余的节点最相关的两个节点，继续向上规约得到父节点，如此自底向上构造出明文二叉树索引，然后加密明文二叉树索引得到密文二叉树索引。

进一步地，所述的数据使用者根据提交的查询生成查询的向量表示形式，根据用户的历史偏好信息结合查询信息构造查询向量以支持偏好搜索，根据逻辑联结的关键词以及构造的数值序列来构造查询向量以支持逻辑搜索，在生成查询向量以后，数据使用者根据随机比特向量按照规则将查询向量分成两个子向量，然后分别使用两个可逆矩阵的逆矩阵来加密两个查询子向量得到加密后的查询陷门；

所述的数据使用者生成查询陷门后，会将查询陷门和待获取的目标文档数目发送到云服务器，获取云服务器返回的按照相关性排好序的top-K 个最相关的密文文档和验证对象以后，会通过验证算法验证搜索结果的完整性和准确性，然后解密后得到结果文档集合。

进一步地，所述的云服务器接收到数据拥有者生成的密文二叉树索引、密文文档和消息摘要以及数据使用者生成的加密查询陷门和目标文档数目后，会在密文二叉树索引上按照查询和索引，即文档之间的相关性评分获取top-K个最相关的文档，一旦检索结束，得到top-K个最相关的文档，会按照相关性评分排序，然后生成验证对象后发送到数据使用者。

进一步地，所述的加密方法包括：

密钥生成阶段GenKey(1^l(n))：

初始化阶段，数据拥有者生成一样四元组的安全密钥SK＝(S,M₁,M₂,>f)，其中S是一个(n+e)比特的随机向量，M₁和M₂是两个(n+e)×(n+>f是一个对称加密密钥，安全密钥SK仅仅在数据拥有者和数据使用者之间共享，云服务器不知道安全密钥SK的任何信息；

构造索引阶段BuildIndex(FS,SK)：

根据构造索引二叉树算法，对节点u中存储的每一个文档向量u.PV使用如下的公式计算

其中表示w_i在F_d中的TF值，是关键词w_i出现在文档F_d的频率，构造出了明文二叉树索引以后，然后加密得到密文二叉树索引，加密过程中，针对剪枝向量(叶子结点中，剪枝向量即文档向量)应用如下的切分规则得到两个随机子向量{P′,P″}，其中>

u.PV向量的加密形式是对于索引树中的每一个节点， u.PV被替换成了其加密形式

生成陷门阶段GenTrapdoor(S^q,k,SK)：

假定S^q＝{w₁,w₂,…,w_t}是用户的查询关键字集合，S^q的向量形式是>

然后，进行归一化操作，随后，Q被切分成两个随机子向量{Q′,Q"},>

Q的加密形式是然后数据拥有者将陷门T_Q传给云服务器，T_Q包括和待获取的目标文档数目K；

搜索阶段

云服务器执行一个深度优先的算法来获取结果集合R，然后构造一个可验证的对象VO，然后，云服务器返回结果集合R和VO给数据使用者，密文二叉树索引的搜索算法执行过程中，u.PV和Q向量的加密形式之间相关性评分计算下所示：

其中u.PV为未加密过的文档向量(对于叶子结点，PV就是文档向量)，Q为未加密过的查询向量，此计算结果表明索引和陷门之间的相关性评分与明文文档向量和查询之间的相关性评分相等或者成正比关系；

阶段验证阶段Verify(R,VO,SK)：

数据使用者使用密钥k_f来解密搜索结果并验证搜索结果的正确性和完整性，密文二叉树索引的每一个叶子结点都包含当前文档的消息摘要，云服务器利用获取的top-K个文档的消息摘要生成验证对象并发送到数据使用者，数据使用者接收到top-K个密文文档以及验证对象后，会解密每个文档，然后结合密钥k_f生成文档的消息摘要，根据这些新生成的文档的消息摘要生成新的验证对象VO′，通过判定云服务器返回的验证对象和数据使用者新生成的验证对象是否相等,即VO′是否等于VO，数据使用者决定是否接受此次查询的结果。

进一步地，所述的构造索引阶段和所述的生成陷门阶段分别调整如下：

所述的构造索引阶段，由文档构造文档向量的过程中，文档向量中字典中包含的关键词对应的每一个维度用如下的公式来计算

公式中，表示关键词w_i在文档F_j中的TF值，表示有多少个文档中包含了关键词w_i，N表示文档集合中文档的个数，|F_j|表示文档F_j的长度，即包含的关键词的数目，而冗余关键词对应的维度的值服从均匀分布U(θ-σ,θ+σ)，均匀分布的均值θ和方差σ需要根据实验中的数据确定；

所述的生成陷门阶段，使用用户的历史偏好和提交的查询构建查询的向量表示形式，首先用户提交的查询中的关键词按照重要性递增序排列其中，1≤n₁<n₂<…<n_l≤m，然后数据使用者随机生成一个超递增序列如下：d₁>0,d₂,…,d_l满足d_i是关键词的偏好因子，即查询向量相应关键词处的值，而查询向量中冗余关键词的位置则随机置1，

此时搜索的结果如下表示为：

其中s是因为引入的冗余关键词而引入的扰动值。

进一步地，所述的密钥生成阶段、所述的构造索引阶段、所述的生成陷门阶段分别调整如下：

所述的密钥生成阶段，数据拥有者在初始化时生成一样四元组的安全密钥SK＝(S,M₁,M₂,k_f)，其中S是一个(n+1)比特的随机向量，M₁和M₂是两个(n+1)×(n+1)的可逆矩阵，其中n是生成的字典大小，1是构造查询陷门的需要，k_f是一个对称加密密钥；

所述的构造索引阶段，将文档转为文档向量的过程中，文档向量的每一维仅表示当前文档和字典中关键词的包含关系，1表示当前文档包含特定的关键词，0表示当前文档不包含特定的关键词，其中第(n+1)维置1，其他切分规则和构造二叉树索引的机制不变；

所述的生成陷门阶段，假设查询中和“OR”,“AND”,“NO”相关的关键词集合分别是同时使用符号表示数学意义上的“OR”“AND”，“NO”，匹配规则表示为对于“OR”操作，数据使用者构造一个超递增序列a_j(j＝>1)，来赋值给“AND”搜索关键字的权重值，为了实现“AND”和“NO”操作,同样，数据使用者构造两个超递增序列b_j(j＝1,2,…,l₂)c_j(j＝1,2,…,l₃)满足条件式和条件式假设是根据重要性递增排序的，那么搜索关键词集合那么在Q相关位置中的权重值被设置为其他位置的值则被设置为0，同时查询向量中第(n+1)维设置为在查询结果，如果对于文档F_j,其结果R_j＞0,那以F_j就满足逻辑搜索的要求。

进一步地，先构造明文二叉树索引，其构造过程及基本结构如下：

(1)明文二叉树索引的节点u是一个九元组(P′,P″,PV,CV,N,PL, PR,FD,sig)，其中u.PL,u.PR是指向左右节点的指针；u.FD是文档的唯一描述符；u.sig是根据文档内容生成的消息摘要；u.CV表示聚类C_u的聚类中心向量，u.N表示聚类C_u中文档的数目，聚类C_u代表的是以u为根节点的子树中所有的叶子结点相关联的文档；需要说明的是因为u.CV,u.N和u.PV>

节点u主要有两种类型，分别是叶子结点和中间节点。

1.如果u是叶子结点，那么u.PL＝u.PR＝φ；u.FD存储的是文档的文件描述符；u.CV和u.PV都存储当前的文档向量；u.P′和u.P″分别代表 u.PV切分后的子向量的加密形式,此时都设置为默认值NULL；u.N＝1； u.sig存储当前文档的消息摘要，消息摘要主要用于搜索过程结束后生成验证对象，数据使用者用接收到的验证对象验证搜索结果的完整性和准确性。

2.如果u是一个内部的中间节点，那么u.FD＝φ,u.sig＝φ,u.PL和 u.PR指向节点u的左右孩子节点。u.N＝u.PL.N+u.PR.N，而u.PV是由节点u的两个孩子节点的各自的剪枝向量PV生成，u.CV则是从节点u的两个孩子节点的各自的聚类中心向量CV生成的，u.VC聚类中心向量主要用于构造密文二叉树索引的过程中，用于查找最相关的节点。生成规则如下：

聚类中心向量用于计算节点与节点之间的相关性评分，用于在构造二叉树索引过程中查找最相近的两个节点并构造其父节点，而剪枝向量会生成两个子向量并会利用可逆矩阵进行加密，用于在二叉树深度优先的检索过程中计算和陷门即查询之间的相关性评分以决定是否进入当前子树中进行检索；

(2)构造明文二叉树索引的过程如下：在索引二叉树的构造过程中，当前处理节点集合CPNS代表当前一轮处理的节点集合，待处理节点集合 NGNS代表下一轮处理的节点集合。首先初始化每一个文档为一个包含五元组的节点，将所有的文档节点都加入到CPNS中。当CPNS中节点个数大于 1的时候，不断的找到两个最相关的节点，即计算所有节点的聚类中心向量的相关分值最大的两个节点，也可以理解为最相似的两个文档。然后按照前面提到规则构造最大相关分值的两个节点的父节点。然后将构造出的父节点加入到NGNS中，然后从CPNS中移除刚找到的两个节点，如此处理直到CPNS中节点个数小于或等于1(因为原来CPNS中节点可能是奇数，所以可能剩余一个节点)，然后将NGNS中的节点加入到CPNS中，进行新一轮的处理，如此循环处理，直到将NGNS中的节点都加入到CPNS中后CPNS 中仍只剩下一个节点，那么此时终止构造过程，CPNS中剩下的唯一节点就是明文索引二叉树中的根节点，然后返回代表此二叉树的根节点即可。

进一步地，加密明文二叉树索引得到密文二叉树索引的过程如下：

明文二叉树索引包含这个文档集合的全部信息，所以需要先将明文二叉树索引加密成密文二叉树索引然后才能将密文二叉树索引上传到云服务器。其中，代表节点的九元组中u.P′,u.P″是剪枝向量u.PV按如下公式切分后生成的两个剪枝子向量后的加密形式，其中S向量充当切分指示器

表示节点的九元组中u.P′和u.P″向量主要用于搜索阶段，如果节点是叶子结点，那么可以利用和Secure KNN算法相同的机制计算文档和查询向量之间的相关性分值；如果节点是中间节点，那么可以利用u.P′和u.P″和查询陷门之间的相关性分值决定是否进入当前中间节点的子树中进行搜索，即进行剪枝，具体过程见搜索算法描述。

加密明文二叉树索引成密文二叉树索引的过程如下：当前根节点为空，返回；如果根节点不为空，首先需要按照如上的公式切分剪枝向量成剪枝子向量，然后使用可逆矩阵的转置矩阵加密剪枝子向量；为了避免明文文档的集合的信息泄露给云服务器，需要将节点中u.CV和u.PV字段都设置为NULL，同时将u.N字段设置为0；最后，如果当前根节点的左子树不为空，那么继续递归加密左子树，如果当前根节点的右子树不为空，继续递归加密右子树。直到整个所有的节点都加密过，此时返回密文二叉树索引的根节点即可。

进一步地，利用二叉树索引来加速查询的过程如下：

目标结果集合用R表示，threshold则表示当前结果集合中节点和查询的相关性得分的最小值，K表示要获取的文档数目，在检索阶段，如果当前节点是叶子结点，并且R中节点个数小于K-1，那么将当前节点加入到R 中，如果R中节点个数等于K-1,那么将当前节点加入到R中并且更新 threshold值，如果R中节点个数等于K，并且当前叶子节点和查询之间的相关性评分大于threshold值，那么从R中移除和查询最不相关的节点，然后加入当前叶子节点，同时更新threshold值；如果当前节点是中间节点，那么如果剪枝向量和查询陷门之间的相关性评分小于threshold值，那么当前节点所代表的子树可以直接剪枝掉，不用后续检索，否则进入子树中继续检索，如此索引树遍历完毕，返回节点集合R。

本发明相对于现有技术具有如下的优点及效果：

(1)利用SecureKNN来实现了对称多关键字密文检索，同时具备偏好搜索检索和逻辑检索的功能，还能按照和查询的相关程度排序搜索结果，同时能根据验证对象验证搜索结果的准确性和完整性，为了降低搜索的时间复杂度，数据拥有者预先构造了密文二叉树索引，利用此密文二叉树索引，能有效的剪枝子树以减小搜索空间，这样就提升了搜索的效率。

(2)利用对角矩阵来替代满矩阵，其存储开销和计算开销都降低了一个数量级，矩阵的求逆的时间也极大的减小了，这些都极大的降低了数据拥有者的预处理的开销，同时在半可信(honest-but-curious即诚实但是好奇)的模型下，采用对角矩阵的方案的安全性也没有降低，因此，本发明在提升速度的同时没有降低方案的安全性。

附图说明

图1是本发明公开的支持偏好和逻辑搜索的高效可验证多关键字排序的可搜索加密方法的结构示意图；

图2是聚类过程树形图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一

本实施例公开了一种支持偏好搜索和逻辑搜索的高效可验证的多关键字排序可搜索加密方法，包括如下三个部分：

a)数据拥有者

数据拥有者是数据的所有者，主要是进行可搜索加密的预处理，包括密钥的生成、文档的加密、索引的生成、摘要的生成等几个步骤。为了保证所持有数据的机密性，数据拥有者需要将所持有的文档数据加密得到密文文档集合E，为了使得加密后的文档可搜索同时保证搜索的高效性，数据拥有者需要基于文档集合FS构建安全索引同时数据拥有者也会生成消息摘要以便于数据使用者进行搜索结果的完整性和准确性校验，然后，数据拥有者将加密后的密文文档集合E连同文档的消息摘要和安全索引上传到云服务器。与此同时，数据拥有者可以授权数据使用者访问其外包数据,即与数据使用者共享密钥，包括用于加密文档的对称密钥和加密陷门的秘密钥。

数据拥有者会生成用户加密文档的对称密码和加密文档向量的秘密钥，即两个可逆矩阵和一个随机的比特向量。

数据拥有者使用对称密钥来加密文档内容，同时使用向量空间模型和 TF×IDF来抽象文档的内容以及相关权重，构造明文二叉树索引后，然后递归加密整个二叉树索引，加密过程中根据随机比特向量将文档向量按照一定的规则切分成两个子向量，然后分别使用两个可逆矩阵的转置矩阵来加密两个子向量，同时数据拥有者根据文档内容和密钥生成文档的消息摘要用于搜索阶段构造验证对象以保证可验证性。

为了保证搜索过程的高效性，数据拥有者使用了二叉树来组织索引。构造二叉树的时候，首先每个文档作为一个叶子结点，然后会选择当前最相关的两个文档，然后按照一定的规则构造其父节点，然后继续选择剩余的节点最相关的两个节点，继续向上规约得到父节点，如此自底向上构造出明文二叉树索引，然后加密明文二叉树索引得到密文二叉树索引。

数据拥有者生成加密文档和密文二叉树索引以及文档消息摘要后，会将这些数据外包到云服务器上，此时云服务器对外提供存储和搜索服务。

b)数据使用者

数据使用者就是和数据所有者共享密钥的用户，其可以向服务器提交查询以进行搜索。当数据使用者想要检索文档时，首先，将查询转为查询陷门T_Q，然后，查询陷门T_Q以及数据使用者的目标文档数目被提交到云服务器提供商；一旦云服务器接收到查询陷门T_Q，云服务器执行计算任务；计算完成，云服务器返回排序后top-K个最相关的文档以及相关的验证对象；最后，数据使用者接收到top-K个最相关的文档和相关的验证对象，执行验证算法来验证搜索结果的准确性和完全性，然后再解密得到搜索结果。

数据使用者会根据提交的查询生成查询的向量表示形式，但是为了支持偏好搜索，需要根据用户的历史偏好信息结合查询信息构造查询向量，为了支持逻辑搜索，需要根据逻辑联结的关键词以及构造的数值序列来构造查询向量。生成了查询向量以后，数据使用者根据随机比特向量按照一定的规则将查询向量分成两个子向量，然后分别使用两个可逆矩阵的逆矩阵来加密两个查询子向量得到加密后的查询陷门。

数据使用者生成查询陷门后，会将查询陷门和待获取的目标文档数目发送到云服务器，获取云服务器返回的按照相关性排好序的top-K个最相关的密文文档和验证对象以后，会通过验证算法验证搜索结果的完整性和准确性，然后解密后得到结果文档集合。

c)云服务器

云服务器向数据拥有者提供“按需计费”的存储和计算服务，向数据使用者提供查询服务。其存储了密文文档和密文索引，一旦云服务器接收到来自数据使用者发送过来的查询陷门T_Q和目标数目K，云服务器就会利用密文索引和查询陷门T_Q进行安全检索，得到top-K个最相关的加密文档，按与查询的相关性大小排序后生成验证对象，然后将top-K个最相关的密文文档和验证对象发送给数据使用者。

云服务器接收到数据拥有者生成的密文二叉树索引，密文文档和消息摘要以及数据使用者生成的加密查询陷门和目标文档数目后，会在密文二叉树索引上按照查询和索引，即文档和查询之间的相关性评分获取top-K 个最相关的文档，一旦检索结束，得到top-K个最相关的文档，会按照相关性评分排序，然后生成验证对象后发送到数据使用者。

下面结合数据拥有者、数据使用者、云服务器介绍一种支持偏好搜索和逻辑搜索的高效可验证的多关键字排序可搜索加密方法的几个基本过程，但是要支持偏好搜索和逻辑搜索，需要对其中的几个阶段各做一些调整，这里先阐述基本方案，紧接着是支持偏好搜索和逻辑搜索的方案以及构造二叉树索引的构造和搜索的执行过程。

(1)密钥生成阶段---数据拥有者

GenKey(1^l(n))：初始化阶段，数据拥有者生成一样四元组的安全密钥SK＝(S,M₁,M₂,k_f)，其中S是一个(n+e)比特的随机向量，M₁和M₂是两个(n+e)×(n+e)的可逆矩阵，其中n是生成的字典大小，e是为了防止陷门的不可链接性而引入的冗余关键词的数目，k_f是一个对称加密密钥(如AES，DES)。安全密钥SK仅仅在数据拥有者和数据使用者之间共享，云服务器不知道安全密钥SK的任何信息。

(2)构造索引阶段---数据拥有者

BuildIndex(FS,SK)：根据构造索引二叉树算法，对节点u中存储的每一个文档向量u.PV使用如下的公式计算

其中TF_d,wi表示w_i在F_d中的TF值，是关键词w_i出现在文档F_d的频率，构造出了明文二叉树索引以后，然后加密得到密文二叉树索引，加密过程中，针对剪枝向量(叶子结点中，剪枝向量即文档向量)应用如下的切分规则得到两个随机子向量{P′,P″}，其中>

u.PV向量的加密形式是对于索引树中的每一个节点， u.PV被替换成了其加密形式

(3)生成陷门阶段---数据使用者

GenTrapdoor(S^q,k,SK)：假定S^q＝{w₁,w₂,…,w_t}是用户的查询关键字集合，S^q的向量形式是Q,每一个维通过如下的公式进行计算，

然后，进行归一化操作。随后，Q被切分成两个随机子向量{Q′,Q″}, SK.S充当切分指示器。切分规则如下

Q的加密形式是然后数据拥有者将陷门T_Q传给云服务器，T_Q包括和待获取的目标文档数目K。

(4)搜索阶段------云服务器

云服务器执行一个深度优先的算法来获取结果集合R，然后构造一个可验证的对象VO，然后，云服务器返回结果集合R和VO 给数据使用者。密文二叉树索引的搜索算法执行过程中，u.PV和Q向量的加密形式之间相关性评分计算如下所示

其中u.PV为未加密过的文档向量，Q为未加密过的查询向量，此计算结果表明索引和陷门之间的相关性评分与明文文档向量和查询之间的相关性评分相等(或者成正比关系)。

(5)阶段验证阶段

Verify(R,VO,SK)：数据使用者使用密钥k_f来解密搜索结果并验证搜索结果的正确性和完整性。密文二叉树索引的每一个叶子结点都包含了当前文档的消息摘要，云服务器会利用获取的top-K个文档的消息摘要生成验证对象并发送到数据使用者。数据使用者接收到top-K个密文文档以及验证对象后，会解密每个文档，然后结合密钥k_f生成文档的消息摘要，根据这些新生成的文档的消息摘要生成新的验证对象VO′，通过判定服务器返回的验证对象和数据使用者新生成的验证对象是否相等,即VO′是否等于VO，数据使用者决定是否接受此次查询的结果。

要支持偏好搜索，其索引构造阶段和陷门生成阶段需要做一些调整，其他阶段保持不变。

a.索引构造阶段，由文档构造文档向量的过程中，文档向量每一个维度用如下的公式来计算,代表已排好序的字典中该位置处的关键字的权重分值。

公式中，表示关键词w_i在文档F_j中的TF值，表示有多少个文档中包含了关键词w_i，N表示文档集合中文档的个数。|F_j|表示文档F_j的长度，即包含的关键词的数目。而冗余关键词对应的维度的值服从均匀分布U(θ-σ,θ+σ)即可，均匀分布的均值θ和方差σ需要根据实验中的数据确定。我们的中实验均值置0，方差置0.01。

b.生成陷门阶段，根据用户的历史偏好和提交的查询构建查询的向量表示形式。首先用户提交的查询中的关键词根据重要性按递增序排列然后数据使用者随机生成一个超递增序列(d₁>0,d₂,…,d_l满足d_i是关键词的偏好因子，即查询向量相应关键词处的权重值，而查询向量中冗余关键词处的权重值则随机置1。

此时搜索的结果就可以如下表示为

其中s是因为引入冗余关键词而引入的总分值的扰动值。

这样的构造能保证如下两点：

(1)搜索关键词集合根据偏好程度按照递增序排列。如果文档F₁比文档F₂包含一个偏好程度更高的关键词，那么文档F₁相比文档F₂就有更高的返回优先级。

(2)搜索关键词集合 m)根据偏好程度按照递增序排列。如果文档F₁,F₂包含了相同偏好程度的关键词，那么如果文档F₁中包含了权重值更高的关键词，那么文档F₁相比文档F₂就有更高的返回优先级。

为了支持逻辑搜索，需要对密钥生成阶段，构造索引阶段，陷门生成阶段做一些调整，其他阶段保持不变。

c.密钥生成阶段

初始化阶段，数据拥有者生成一样四元组的安全密钥SK＝(S,M₁,M₂,>f)，其中S是一个(n+1)比特的随机向量，M₁和M₂是两个(n+1)×(n+>f是一个对称加密密钥(如AES，DES)。

d.构造索引阶段

构造索引阶段，将文档转为文档向量的过程中，文档向量每一维不再是分值，文档向量的每一维仅表示当前文档和字典中关键词的包含关系。1表示当前文档包含特定的关键词，0表示当前文档不包含特定的关键词，其中第(n+1)维置1，其他切分规则和构造二叉树索引的机制不变，如前所述。

e.生成陷门阶段

假设查询中和“OR”,“AND”,“NO”相关的关键词集合分别是

同时使用符号表示数学意义上的“OR”“AND”，“NO”。这样，匹配规则就可以表示为对于“OR”操作，数据使用者构造一个超递增序列来赋值给“AND”搜索关键字的权重值。为了实现“AND”和“NO”操作,同样，数据使用者构造两个超递增序列b_j(j＝1,2,…,l₂)c_j(j＝1,2,…,l₃)满足条件式和条件式假设是根据重要性递增排序的。那么搜索关键词集合那么在Q相关位置中的权重值可以被设置为其他位置的值则被设置为0。同时查询向量中第(n+1)维设置为在查询结果，如果对于文档F_j,其结果R_j>0,那么F_j就满足逻辑搜索的要求。

推论的正确性也很容易证明：

因为“NO”联结的关键词在查询向量Q中对应的值为-c_i并且所以如果w_i″′(i＝>3)关键词存在于文档中，那么肯定可以推断出P·Q<0以及R_j＝>j>0，那么w_i″′都不会存在于文档F_j中，即文档F_j满足“NO”条件。

又因为如果R_j>0，那么因为以及，那么AND相关的所有关键词都必须存在，OR相关的关键词必须有一个存在，即，文档向量P中所有 AND联结的关键字处的值都是置1的，OR联结的关键字处的值至少有一个是1的。所以，F_j满足“AND”和“OR”操作。所以，如果R_j>0,那么向量P满足“OR”“AND”,“NO”操作。反之构造出来这样的满足上述几个不等式的超递增序列，也可以推断出R_j>0。

为了加速查找需要使用树形索引，首先构造明文二叉树索引，然后加密明文二叉树索引得到密文二叉树索引,其能根据节点和陷门之间的相关性分值决定是否剪枝相关的子树以提升搜索的速度,明文二叉树索引基本的结构和构造过程如下：

(1)明文二叉树索引的节点u是一个九元组(P′,P″,PV,CV,N,PL, PR,FD,sig)，其中u.PL,u.PR是指向左右节点的指针；u.FD是文档的唯一描述符；u.sig是根据文档内容生成的消息摘要；u.CV表示聚类C_u的聚类中心向量，u.N表示聚类C_u中文档的数目，聚类C_u代表的是以u为根节点的子树中所有的叶子结点相关联的文档；需要说明的是因为u.CV,u.N和u.PV>

节点u主要有两种类型，分别是叶子结点和中间节点。

a.如果u是叶子结点，那么u.PL＝u.PR＝φ；u.FD存储的是文档的文件描述符；u.CV和u.PV都存储当前的文档向量；u.P′和u.P″分别代表 u.PV切分后的子向量的加密形式,此时都设置为默认值NULL；u.N＝1； u.sig存储当前文档的消息摘要，消息摘要主要用于搜索过程结束后生成验证对象，数据使用者用接收到的验证对象验证搜索结果的完整性和准确性。

b.如果u是一个内部的中间节点，那么u.FD＝φ,u.sig＝φ,u.PL和 u.PR指向节点u的左右孩子节点。u.N＝u.PL.N+u.PR.N，而u.PV是由节点u的两个孩子节点的各自的剪枝向量PV生成，u.CV则是从节点u的两个孩子节点的各自的聚类中心向量CV生成的，u.CV聚类中心向量主要用于构造密文二叉树索引的过程中，用于查找最相关的节点。生成规则如下：

聚类中心向量用于计算节点与节点之间的相关性评分，用于在构造二叉树索引过程中查找最相近的两个节点并构造其父节点。而剪枝向量会生成两个子向量并会利用可逆矩阵进行加密，用于在二叉树深度优先的检索过程中计算和陷门即查询之间的相关性评分以决定是否进入当前子树中进行检索。

(2)构造明文二叉树索引的过程如下：在索引二叉树的构造过程中，当前处理节点集合CPNS代表当前一轮处理的节点集合，待处理节点集合 NGNS代表下一轮处理的节点集合。首先初始化每一个文档为一个包含五元组的节点，将所有的文档节点都加入到CPNS中。当CPNS中节点个数大于 1的时候，不断的找到两个最相关的节点，即计算所有节点的聚类中心向量的相关分值最大的两个节点，也可以理解为最相似的两个文档。然后按照前面提到规则构造最大相关分值的两个节点的父节点。然后将构造出的父节点加入到NGNS中，然后从CPNS中移除刚找到的两个节点，如此处理直到CPNS中节点个数小于或等于1(因为原来CPNS中节点可能是奇数，所以可能剩余一个节点)，然后将NGNS中的节点加入到CPNS中，进行新一轮的处理，如此循环处理，直到将NGNS中的节点都加入到CPNS中后CPNS 中仍只剩下一个节点，那么此时终止构造过程，CPNS中剩下的唯一节点就是明文索引二叉树中的根节点，然后返回代表此二叉树的根节点即可。

加密明文二叉树索引得到密文二叉树索引过程如下：

明文二叉树索引包含这个文档集合的全部信息，所以需要先将明文二叉树索引加密成密文二叉树索引然后才能将密文二叉树索引上传到云服务器。其中，代表节点的九元组中u.P′,u.P″是剪枝向量u.PV按如下公式切分后生成的两个剪枝子向量后的加密形式，其中S向量充当切分指示器

表示节点的九元组中u.P′和u.P″向量主要用于搜索阶段，如果节点是叶子结点，那么可以利用和Secure KNN算法相同的机制计算文档和查询向量之间的相关性分值；如果节点是中间节点，那么可以利用u.P′和u.P″和查询陷门之间的相关性分值决定是否进入当前中间节点的子树中进行搜索，即进行剪枝。

加密明文二叉树索引成密文二叉树索引的过程如下：当前根节点为空，返回；如果根节点不为空，首选需要按照如上的公式切分剪枝向量成剪枝子向量，然后使用可逆矩阵的转置矩阵加密剪枝子向量；为了避免明文文档的集合的信息泄露给云服务器，需要将节点中u.CV和u.PV字段都设置为NULL，同时将u.N字段设置为0；最后，如果当前根节点的左子树不为空，那么继续递归加密左子树，如果当前根节点的右子树不为空，继续递归加密右子树。直到整个所有的节点都加密过，此时返回密文二叉树索引的根节点即可。

利用二叉树索引来加速查询的过程如下：

目标结果集合用R表示，threshold则表示当前结果集合中节点和查询的相关性得分的最小值，K表示要获取的文档数目。在检索阶段，如果当前节点是叶子结点，并且R中节点个数小于K-1，那么将当前节点加入到R 中，如果R中节点个数等于K-1,那么将当前节点加入到R中并且更新 threshold值，如果R中节点个数等于K，并且当前叶子节点和查询之间的相关性评分大于threshold值，那么从R中移除和查询最不相关的节点，然后加入当前叶子节点，同时更新threshold值；如果当前节点是中间节点，那么如果剪枝向量和查询陷门之间的相关性评分小于threshold值，那么当前节点所代表的子树可以直接剪枝掉，不用后续检索了，因为其相关性已经小于结果集R中最不相关的节点了，否则进入子树中继续检索。如此索引树遍历完毕。返回节点集合R。

前面所述的用于加密文档向量和陷门的都是一个(n+e)×(n+e)的可逆矩阵,其矩阵的求逆耗时非常长，而且构造索引阶段，每个切分后的文档子向量都需要左乘以一个可逆矩阵的你矩阵，其时间复杂度是O(N²),>2)(如果考虑到二叉树索引树的构建，那么时间复杂度是O(logm·m²·N²),如果将两个可逆的满矩阵变为两个可逆的对角矩阵，那么其转置矩阵就是原矩阵，其逆矩阵也是一个对角矩阵，并且对角上每一个元素的值都是原矩阵相同位置处的元素的值的倒数。这样，其存储的开销从O(N²)变为O(N)。构造索引的时间复杂度从>2)变为O(2mN)(考虑到二叉树的构建，其总的时间复杂度从>2·N²)减小为O(logm·m²·N))，因为对角矩阵的引入，矩阵和向量的乘积的时间复杂度从O(N²)变为O(N)，所以无论是时间复杂度还是空间复杂都有一个数量级的降低，同时，在半可信(honest-but-curious>

实施例二

下面以一个具体的例子来说明多关键字偏好搜索的具体过程，逻辑搜索的方案基本相似，前面也给出了其搜索正确性的形式化证明，这里不再赘述。对角矩阵主要是用于减少计算量，计算步骤基本一致，这里也不赘述。

(1)文档集合FS中各个文档的内容如下，这里方便说明程序的流程，各个文档都非常小。整个字典只有6个关键词，引入2个冗余关键词。所以整生成字典大小是8。

f1.txt:python java

f2.txt:java go

f3.txt:python go

f4.txt:cpp

f5.txt:c

f6.txt:javascript

f7.txt:python cpp c

f8.txt:python go java

(2)生成字典排好序后是：[c,cpp,go,java,javascript,mugvnxze, python,pzfv]，其中“mugvnxzeh”和“pzfv”是引入的冗余关键词。

(3)各个文档对应生成的文档向量如下，其中冗余关键词的权重值服从均匀分布U(-0.01,0.01)。构造密文二叉树索引的过程中，每个文档对应的叶子结点的中心向量设置为此文档向量。

f1.txt

python:0.5493061443340549

java:0.6496414920651304

[0.000000,0.000000,0.000000,0.649641,0.000000,-0.007514,0.549306,0.003004]

f2.txt

java:0.6496414920651304

go:0.6496414920651304

[0.000000,0.000000,0.649641,0.649641,0.000000,0.008282,0.000000,0.003478]

f3.txt

python:0.5493061443340549

go:0.6496414920651304

[0.000000,0.000000,0.649641,0.000000,0.000000,-0.008594,0.549306,-0.004946]

f4.txt

cpp:1.6094379124341003

[0.000000,1.609438,0.000000,0.000000,0.000000,-0.006176,0.000000,-0.008033]

f5.txt

c:1.6094379124341003

[1.609438,0.000000,0.000000,0.000000,0.000000,0.003996,0.000000,0.007028]

f6.txt

javascript:2.1972245773362196

[0.000000,0.000000,0.000000,0.000000,2.197225,0.002741,0.000000,0.006191]

f7.txt

python:0.3662040962227032

cpp:0.5364793041447

c:0.5364793041447

[0.536479,0.536479,0.000000,0.000000,0.000000,-0.004668,0.366204,0.000613]

f8.txt

python:0.3662040962227032

java:0.4330943280434203

go:0.4330943280434203

[0.000000,0.000000,0.433094,0.433094,0.000000,-0.006085,0.366204,-0.003783]

(4)构造明文二叉树索引的过程中，首先通过文档中心向量计算最相关的两个节点。因为总共有8个节点，所以第一轮需要迭代4次，将8个文档集合分为4个小类。此时的四个小聚类分别是(f3,f1),(f8,f2), (f4,f7),(f5,f6)。然后通过提取中心向量和剪枝向量向上构造父节点。第二轮需要迭代两次，聚类的结果是(f3f1,f8f2)，(f4f7,f5f6)，第三轮只有两个节点，聚类的结果是只有一个节点(f3f1f8f2,f4f7f5f6)，然后根据这两个节点构造根节点然后返回根节点即可，此过程生成的明文二叉树索引的附图2所示。

(5)加密明文二叉树索引得到密文二叉树索引，即根据切分规则切分每个节点中的剪枝向量得到两个子向量P′、P″，然后使用可逆矩阵的转置矩阵加密两个子向量，并将相关的字段设置为NULL。

(6)提交的查询是"java python go"，需要获取的目标文档个数是2，根据用户的搜索历史建立的用户的兴趣偏好模型，赋予不同的关键词以不同的权重，权重如下:"c":2,"cpp":5,"javascript":1,"python":8, "java":7,"go":10,"scala":6。那么根据用户提交的查询构造的查询向量 Q以及查询向量Q经切分生成的子向量的加密形式Q′和Q″分别如下所示:

[0.000000,0.000000,115.059300,1.000000,0.000000,1.000000,19.450359,0.000000]

[174.797226,-190.718486,-16.424931,118.891982,-10.095257,58.659643,11.118955,- 110.229204]

[2546.835577,-1077.082690,1838.242043,389.895225,-2904.909899,-1202.838724,1340.954562,-498.161811]

(7)检索的时候，在密文二叉树索引上采用深度优先算法向下递归检索。首先root根节点和陷门之间的相关性分值为86.08，然后继续向下遍历，遇到中间节点f3f1f8f2，此节点和陷门之间的相关性分值为86.08；在往下遍历，中间节点f3f1和陷门之间的相关性分值为86.07；继续往下遍历，遇到的第一个节点叶子结点是f3.txt所代表的节点，此节点和陷门之间的相关性分值为85.42，因为是第一个叶子结点，所以直接加入到结果集中；继续遍历，遇到第二个叶子结点是f1.txt所代表的节点，此节点和陷门之间的相关性分值为11.32，加入到结果集合中，此时结果集合中 f8.txt和f1.txt所代表的节点，阈值设置为11.32；然后回溯到中间节点 f8f2，此中间节点和陷门之间的相关性分值为82.52，大于阈值11.32；然后进入此中间节点的左子树中搜索，遇到的第三个叶子结点是f8.txt文档所代表的节点，此节点和陷门之间的相关性分值为57.38，大于阈值 11.32，所以将f1.txt所代表的节点从结果集合中移除，此时结果集合中有f3.txt和f8.txt所代表的节点，更新阈值为57.38；继续向下遍历，遇到第4个叶子节点f2.txt，此节点和陷门之间的相关性分值为75.40，大于阈值57.38，所以移除f8.txt所代表的节点，所以结果集合中只有 f3.txt和f2.txt所代表的节点更新阈值为75.40；然后回溯到中间节点f4f7f5f6，此中间节点和陷门之间的相关性分值为7.12，小于阈值75.40，所以此分支可以直接剪枝掉，所以算法运行结束，返回的结果集合中有 f3.txt和f2.txt所代表的节点集合，并且按照分值从高到低排列，然后根据节点获取文件描述符，这里假定就是节点的名字。这里简要分析一下搜索结果：f3.txt中包含的内容是“python go”，而f2.txt中包含的内容是“java go”，因为两篇文档中“go”的权重值相同，都是0.64，而f3.txt 中的“python”关键词的用户的偏好比f2.txt中包含的“java”的用户偏好值更高，所以f3.txt返回的优先级更高。而f8.txt中内容“javapython go”，其中“go”的权重值为0.43,而f2.txt中内容为“java go”，但是其中“go”的权重值更大，为0.64，所以f2.txt返回的优先级比f8.txt 高。以上，实验结果和分析是吻合的。在本例子中，剪枝了4个子节点的运算，但是也增加了几个中间节点的运算，但是在较大规模的文档集合中搜索top-K个文档时，是可以通过大量的剪枝来保证搜索的效率。

(8)要实现可验证性，需要将f3.txt和f2.txt所代表的节点的消息摘要生成可验证对象，发送到数据使用者以后，数据使用者需要解密密文文档，重新构造每篇文档的消息摘要，并根据这些消息摘要重新构造可验证对象，通过判定新生成的可验证对象和服务器发回的可验证对象是否相等以决定是否接受此次查询结果。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。