一种可高效更新权限的多用户可搜索加密方法和系统

摘要

本发明公开了一种可高效更新权限的多用户可搜索加密方法，属于云计算存储和密码学技术领域。数据拥有者先确定查询用户对文件的权限，构建出访问控制列表，然后将数据加密生成对应的密文数据以及元数据，并将它们上传到云服务端。同时数据拥有者返回给查询用户相应的访问密钥，用来从向云服务端生成查询认证。用户检索时，发送相应关键字的查询密文标识以及由认证密钥生成的认证标识。服务端接收到这些信息后，先根据认证标识进行认证，确定有权查询后再进行密文上的检索。本发明一方面避免了数据拥有者和查询用户的实时交互；另一方面使数据拥有者可以高效地更新查询用户的权限且不影响其他用户；再一方面可扩展到大规模加密数据库中。

说明书

技术领域

本发明属于云计算存储隐私保护领域，更具体地说，涉及一种可高效更新权限的多用户可搜索加密方法和系统。

背景技术

随着云计算存储技术的发展，大量数据拥有者(例如企业或个人)将数据外包到云服务端上，从而提供更好的服务。然而，云计算存储技术同样带来了数据隐私泄露的问题(如个人医疗记录泄露)。这样就造成一个矛盾：数据拥有者既想要利用云的强大计算功能，又不想自己的隐私数据被泄露。一个简单的办法是将数据加密后上传到云服务端，然而，密文虽然保证了数据的隐私，却也限制了数据的使用。因此，可搜索对称加密(Searchablesymmetric encryption，简称SSE)方法应运而生，其能够实现密文下的检索，并且不泄露查询隐私；而在医院等多用户需要共享数据、保证数据安全的场合，可使用多用户可搜索对称加密(Multi-client Searchable symmetric encryption，简称MSSE)方法。

现有的MSSE方法主要包括外包对称隐私信息检索(Outsourced symmetricprivate information retrieval，简称OSPIR)方法、以及非交互多用户可搜索加密(Non-interactive multi-client searchable encryption，简称NIMCSE)方法，其中OSPIR方法利用同态签名伪随机函数实现多用户查询，NIMCSE方法利用素数散列函数和属性加密实现多用户查询。

然而，上述现有的MSSE方法都存在一些不可忽略的技术问题：首先，OSPIR方法需要用户在每次查询操作时与数据拥有者(Data owner)进行交互，导致查询效率偏低；其次，NIMCSE方法无法对查询权限进行动态更新，进而会影响查询的准确性。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种可高效更新权限的多用户可搜索加密方法和系统，其目的在于，解决现有多用户可搜索对称加密方法中由于需要用户每次查询时与数据拥有者进行交互而导致的查询效率偏低的技术问题，以及由于无法对查询权限进行动态更新而影响查询准确性的技术问题。

为实现上述目的，按照本发明的一个方面，提供了一种可高效更新权限的多用户可搜索加密方法，包括以下步骤：

(1)用户端利用从数据拥有者处获取的密钥Ω_i生成查询关键字密文，并将其发给服务端；

(2)服务端根据来自于用户端的查询关键字密文获取满足用户端查询条件的加密文件标识符集合，并将该加密文件标识符集合发送到用户端；

(3)数据拥有者获取授权给用户的密钥，并通知服务端根据该密钥修改用户关键字索引集合以及交叉匹配集合。

优选地，步骤(1)包括以下子步骤：

(1-1)用户端利用从数据拥有者获取密钥Ω_i，其包括对关键字进行加密的密钥K_S、K_X、K_Z，第i个用户端能够查询的密文关键字的集合CSK_i＝{csk_i，w1，csk_i，w2，…，csk_i，wU}，以及数据拥有者分配给第i个用户端的标识uk_i，其中w_j表示用户端能够查询的第j个密文关键字，且j∈[1，U]，U表示第i个用户端能够查询的密文关键字总数量；

(1-2)用户端确定其所要查询的关键字集合其中表示用户端所要查询的第k个关键字，且k∈[1，n]，n表示用户端所要查询的关键字的总数量；

(1-3)在第i个用户端能够查询的密文关键字的集合CSK_i中找到与所要查询的第一个关键字对应的密文关键字用两个不同的带密钥的哈希函数分别对密文关键字和第i个用户端的标识uk_i进行计算，以分别得到第一哈希值以及第二哈希值

(1-4)对于关键字集合中除了外的所有关键字，计算其交叉查询密文值其中F_p表示伪随机函数，sk_i表示第i个用户持有的私钥；

(1-5)将步骤(1-4)得到的交叉查询密文值、第一哈希值以及第二哈希值作为查询关键字密文发送给服务端。

优选地，步骤(2)包括以下子步骤：

(2-1)服务端接收用户发来查询关键字密文，从构建好的用户关键字索引集合CSet中获取第一哈希值所对应的密文e₁，并根据第二哈希值和密文e₁计算明文

(2-2)服务端判断明文p₁的最后λ比特是否全为0，如果不是，则过程结束，如果是，则获取提取前λ比特作为第一标签值然后进入步骤(2-3)；其中λ为8到512之间的整数，优选等于128；

(2-3)服务端初始化计数器cnt＝1；

(2-4)服务端根据哈希算法对第一标签值和cnt进行计算，将得到的哈希值l作为键，判断是否能够在创建好的关键字文件标识符集合TSet中查找到该键l对应的密文对(e₂，y)，如果是则进入步骤(2-5)，否则进入步骤(2-7)；

(2-5)服务端针对所有的v∈[2，n]，判断是否所有的是否都在构建好的交叉匹配集合XSet中，如果是，则将密文对中的e₂加入加密文件标识符集合R中，并进入步骤(2-6)，否则进入步骤(2-6)；

(2-6)服务端设置计数器cnt＝cnt+1，并返回步骤(2-4)；

(2-7)服务端将加密文件标识符集合R返回给用户端。

优选地，步骤(3)包括以下子步骤：

(3-1)数据拥有者确定所要更新的用户的公钥pk以及所要更新的关键字w；

(3-2)数据拥有者根据密钥K_T、以及所要更新关键字w计算更新标签值stag＝F(K_T,w)，并将该更新后的标签值发送给服务端；

(3-3)服务端根据更新后的标签值stag查询关键字文件标识符集合TSet，以得到密文对集合{(e₂,y)}，提取其中所有的密文e₂组成索引密文集合EnInds，并将索引密文集合EnInds发送给数据拥有者；

(3-4)数据拥有者将索引密文集合EnInds保存到本地，根据密钥K_C和关键字w计算关键字密钥值K_w＝F(K_C,w)，并根据密钥K_R和用户公钥pk计算用户随机值r＝F_p(K_R,pk)；

(3-5)数据拥有者将关键字密钥值K_w作为密钥，用带该密钥的哈希函数计算用户公钥pk的哈希值csk；

(3-6)数据拥有者根据用户随机值r得到用户标识并以csk作为密钥，用两个不同的且带密钥的哈希函数分别计算第一更新哈希值ctag以及第二更新哈希值dtag；

(3-7)数据拥有者在更新标签值stag后连接λ个0，得到更新后的认证标签值stag||0^λ，并将该认证标签值stag||0^λ与第二更新哈希值dtag做异或运算得到更新密文

(3-8)数据拥有者利用密钥K_X以及关键字w计算群关键字密文值xtrap＝F_p(K_X,w)；

(3-9)对于索引密文集合EnInds中每个密文e₂，数据拥有者根据解密该密文获得标识符明文ind，并使用密钥K_I计算标识符群映射xind＝F_p(K_I,ind)，进而计算出与该ind相关的交叉匹配集合XSet中的元素并将其添加到更新交叉匹配集合XTags中；

(3-10)数据拥有者将第一更新哈希值ctag，更新密文e₁，更新交叉匹配集合XTags以及操作变量op发送给服务端；

(3-11)服务端根据来自数据所有者op的值判断对应的操作是增加还是删除，如果是增加，则执行步骤(3-12)，如果是删除，则执行步骤(3-13)；

(3-12)服务端将(ctag，e₁)加入用户关键字索引集合CSet集合中，并将更新交叉匹配集合XTags中的元素加入到交叉匹配集合XSet中。

(3-13)服务端从用户关键字索引集合CSet中删除与第一更新哈希值ctag关联的数据项，并将更新交叉匹配集合XTags中的所有元素从交叉匹配集合XSet中删除。

优选地，密钥Ω_i是通过如下步骤构建：

A、数据拥有者得到该加入用户的公钥pk_i及其可以访问的关键字集合通过密钥K_R以及公钥pk_i计算用户随机数r_i＝F_p(K_R,pk_i)，并计算用户标识初始化密钥集合CSK_i为空集；

B、对于中每个关键字w执行如下步骤，利用密钥K_C计算关键字密钥值K_w＝F(K_C,w)，并以此为密钥，计算用户公钥pk_i的哈希值csk_i,w＝H₁(K_w,pk_i)，然后将csk_i,w加入到CSK_i集合中，将公钥pk_i添加到与关键字w关联的访问控制列表KAL[w]中；

C、数据拥有者将K_S,K_X,K_Z,CSK_i,uk_i封装成Ω_i返回给该用户。

优选地，用户关键字索引集合CSet、关键字文件标识符集合TSet、以及交叉匹配集合XSet是通过如下步骤构建：

(a)数据拥有者初始化用户关键字索引集合CSet、关键字文件标识符集合TSet、以及交叉匹配集合XSet为空集；

(b)对于整个关键字集合W中的每个关键字w，数据拥有者构建用户权限索引表CSet、关键字文件标识符集合TSet以及交叉匹配集合XSet。

优选地，步骤(b)包括以下子步骤：

(b1)数据拥有者判断关键字集合W中取关键字w是否都已被取到，如果是，则进入步骤(b12)否则提取下一个关键字w，并进入步骤(b2)；

(b2)数据拥有者分别利用三个密钥K_S，K_T，K_X，K_C和关键字w计算加密关键字密钥K_e＝F(K_S,w)，索引关键字标签值stag_w＝F(K_T,w)，关键字交叉值xtrap_w＝F_p(K_X,w)以及权限关键字密钥K_w＝F(K_C,w)，并初始化公钥随机数集合K为空；

(b3)数据拥有者从访问控制列表KAL中查询出与该关键字w关联的所有用户公钥的集合PK_w.

(b4)数据拥有者判断公钥集合中的用户公钥是否全部被取到，如果是，则进入步骤(b11)，否则提取下一个用户公钥pk_i，并进入步骤(b5)；

(b5)数据拥有者计算用户随机数r_i＝F_p(K_R,pk_i)，将用户公钥随机数添加到K中；

(b6)数据拥有者以权限关键字密钥K_w为密钥，计算pk_i的带密钥的哈希函数值csk_i,w＝H₁(K_w,pk_i)；

(b7)数据拥有者以csk_i,w为密钥，利用两个不同的带密钥的哈希函数，分别计算uk_i的权限关键字哈希值和关键字混淆哈希值

(b8)数据拥有者在索引关键字标签值stag_w后添加λ位0，构成索引关键字认证标签值stag_w||0^λ；

(b9)数据拥有者对索引关键字认证标签值stag_w||0^λ和关键字混淆哈希值进行异或运算，得到权限关键字密文值

(b10)数据拥有者将添加到CSet集合中并进入步骤(b4)；

(b11)数据拥有者初始化计数器cnt值为1；

(b12)数据拥有者利用密钥K_Z和关键字w计算盲因子z＝F_p(K_Z,w)；

(b13)数据拥有者从明文数据库中获取关键字w关联的所有文件明文标识符的集合DB(w)；

(b14)数据拥有者判断文件明文标识符的集合DB(w)中的所有文件明文标识符ind是否都被取到，如果是则返回步骤(b1)，否则进入步骤(b15)；

(b15)数据拥有者利用密钥K_I和ind计算文件群标识符xind＝F_p(K_I,ind)并利用加密关键字密钥K_e和ind计算关键字标识符密文索引e₂＝Enc(K_e,ind)；

(b16)数据拥有者计算索引交叉值并利用stag_w为密钥，计算关于cnt带密钥的哈希值l＝H₄(stag_w,cnt)

(b17)数据拥有者将(e₂,y)加入到以l为索引的TSet中，并将cnt的值自增1；

(b18)数据拥有者判断用户公钥随机数集合K中的所有用户公钥随机数vk_i是否都被取到，如果是，则返回步骤(b14)，否则取下一个vk_i，并进入步骤(b19)；

(b19)数据拥有者计算交叉匹配值并将xtag加入到XSet中，并返回步骤(b18)。

按照本发明的另一方面，提供了一种可高效更新权限的多用户可搜索加密系统，包括：

第一模块，其设置于用户端中，用于利用从数据拥有者处获取的密钥Ω_i生成查询关键字密文，并将其发给服务端；

第二模块，其设置于服务端中，用于根据来自于用户端的查询关键字密文获取满足用户端查询条件的加密文件标识符集合，并将该加密文件标识符集合发送到用户端；

第三模块，其设置于数据拥有者中，用于获取授权给用户的密钥，并通知服务端根据该密钥修改用户关键字索引集合以及交叉匹配集合。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

(1)由于本发明采用了步骤(b4)到步骤(b10)、以及步骤(3-4)到步骤(3-7)，其将用户信息和可查询的关键字信息联合放入关键字索引集合CSet中，服务端只用根据用户端发来的查询密文就可以判断该用户是否有权查询该关键字，用户端不必每次征求数据拥有者的授权，因此能够解决现有多用户可搜索对称加密方法中由于需要用户每次查询时与数据拥有者进行交互而导致的查询效率偏低的技术问题；

(2)由于本发明采用了步骤(b18)和步骤(b19)、以及步骤(3-9)到(3-13)，其将用户信息、关键字信息和文件标识符信息计算出一个密文保存在交叉匹配集合XSet中，保证了每个用户有自己的关于关键字以及文件标识符的密文；在数据拥有者和服务端执行权限更新时，更新一个用户不会牵扯到另一个用户，因此能够解决现有多用户可搜索对称加密方法中由于无法对查询权限进行动态更新而影响查询准确性的技术问题；

(3)本发明的加密安全性基于双线性映射，在生成查询关键字密文时，生成时间只与待查询关键字的个数有关，因而关键字查询密文的生成效率很高，从而降低了用户端的计算开销，因此本发明可用于医疗等高机密性机构的检索系统。

附图说明

图1是本发明可高效更新权限的多用户可搜索加密方法的流程图；

图2是本发明与现有OXT和MSSE方法的性能比较，其中图2(a)是构建时间与数据集大小的关系曲线，图2(b)是构建时间与用户数的关系曲线；

图3是本发明与现有SCSSE和OSPIR方法的性能比较，其中图3(a)是查询关键字密文产生时间与查询关键字个数的关系曲线，图3(b)是查询关键字密文的产生时间与第一个关键字关联的文件数目的关系曲线；

图4是本发明与现有OXT和MSSE方法的另一个性能比较，其中图4(a)是固定第一个关键字关联的文件总数，变化总查询关键字个数，图4(b)是固定总查询关键字个数，变化第一个关键字关联的文件总数。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

如图1所示，本发明可高效更新权限的多用户可搜索加密方法包括以下步骤：

(1)用户端利用从数据拥有者处获取的密钥Ω_i生成查询关键字密文，并将其发给服务端；

本步骤包括以下子步骤：

(1-1)用户端利用从数据拥有者获取密钥Ω_i，其包括对关键字进行加密的密钥K_S、K_X、K_Z，第i个用户端能够查询的密文关键字的集合CSK_i＝{csk_i，w1，csk_i，w2，…，csk_i，wU}，以及数据拥有者分配给第i个用户端的标识uk_i，其中w_j表示用户端能够查询的第j个密文关键字，且j∈[1，U]，U表示第i个用户端能够查询的密文关键字总数量；

(1-2)用户端确定其所要查询的关键字集合其中表示用户端所要查询的第k个关键字，且k∈[1，n]，n表示用户端所要查询的关键字的总数量；

(1-3)在第i个用户端能够查询的密文关键字的集合CSK_i中找到与所要查询的第一个关键字对应的密文关键字用两个不同的带密钥的哈希函数分别对密文关键字和第i个用户端的标识uk_i进行计算，以分别得到第一哈希值以及第二哈希值

(1-4)对于关键字集合中除了外的所有关键字，计算其交叉查询密文值其中F_p表示伪随机函数；sk_i表示第i个用户持有的私钥；

(1-5)将步骤(1-4)得到的交叉查询密文值、第一哈希值以及第二哈希值作为查询关键字密文发送给服务端。

(2)服务端根据来自于用户端的查询关键字密文获取满足用户端查询条件的加密文件标识符集合，并将该加密文件标识符集合发送到用户端；

本步骤具体包括以下子步骤：

(2-1)服务端接收用户发来查询关键字密文，从构建好的用户关键字索引集合CSet中获取第一哈希值所对应的密文e₁，并根据第二哈希值和密文e₁计算明文

(2-2)服务端判断明文p₁的最后λ比特是否全为0，如果不是，则过程结束，如果是，则获取提取前λ比特作为第一标签值然后进入步骤(2-3)；其中λ为8到512之间的整数，优选等于128；

(2-3)服务端初始化计数器cnt＝1；

(2-4)服务端根据哈希算法对第一标签值和cnt进行计算，将得到的哈希值l作为键，判断是否能够在创建好的关键字文件标识符集合TSet中查找到该键l对应的密文对(e₂，y)，如果是则进入步骤(2-5)，否则进入步骤(2-7)；

(2-5)服务端针对所有的v∈[2，n]，判断是否所有的是否都在构建好的交叉匹配集合XSet中，如果是，则将密文对中的e₂加入加密文件标识符集合R中，并进入步骤(2-6)，否则进入步骤(2-6)；

(2-6)服务端设置计数器cnt＝cnt+1，并返回步骤(2-4)；

(2-7)服务端将加密文件标识符集合R返回给用户端。

(3)数据拥有者获取授权给用户的密钥，并通知服务端根据该密钥修改用户关键字索引集合以及交叉匹配集合；

本步骤包括以下子步骤：

(3-1)数据拥有者确定所要更新的用户的公钥pk以及所要更新的关键字w；

(3-2)数据拥有者根据密钥K_T、以及所要更新关键字w计算更新标签值stag＝F(K_T,w)，并将该更新后的标签值发送给服务端；

(3-3)服务端根据更新后的标签值stag查询关键字文件标识符集合TSet，以得到密文对集合{(e₂,y)}，提取其中所有的密文e₂组成索引密文集合EnInds，并将索引密文集合EnInds发送给数据拥有者；

(3-4)数据拥有者将索引密文集合EnInds保存到本地，根据密钥K_C和关键字w计算关键字密钥值K_w＝F(K_C,w)，并根据密钥K_R和用户公钥pk计算用户随机值r＝F_p(K_R,pk)；

(3-5)数据拥有者将关键字密钥值K_w作为密钥，用带该密钥的哈希函数计算用户公钥pk的哈希值csk；

(3-6)数据拥有者根据用户随机值r得到用户标识并以csk作为密钥，用两个不同的且带密钥的哈希函数分别计算第一更新哈希值ctag以及第二更新哈希值dtag；

(3-7)数据拥有者在更新标签值stag后连接λ个0，得到更新后的认证标签值stag||0^λ，并将该认证标签值stag||0^λ与第二更新哈希值dtag做异或运算得到更新密文

(3-8)数据拥有者利用密钥K_X以及关键字w计算群关键字密文值xtrap＝F_p(K_X,w)；

(3-9)对于索引密文集合EnInds中每个密文e₂，数据拥有者根据解密该密文获得标识符明文ind，并使用密钥K_I计算标识符群映射xind＝F_p(K_I,ind)，进而计算出与该ind相关的交叉匹配集合XSet中的元素并将其添加到更新交叉匹配集合XTags中；

(3-10)数据拥有者将第一更新哈希值ctag，更新密文e₁，更新交叉匹配集合XTags以及操作变量op发送给服务端；

(3-11)服务端根据来自数据所有者op的值判断对应的操作是增加还是删除，如果是增加，则执行步骤(3-12)，如果是删除，则执行步骤(3-13)；

(3-12)服务端将(ctag，e₁)加入用户关键字索引集合CSet集合中，并将更新交叉匹配集合XTags中的元素加入到交叉匹配集合XSet中。

(3-13)服务端从用户关键字索引集合CSet中删除与第一更新哈希值ctag关联的数据项，并将更新交叉匹配集合XTags中的所有元素从交叉匹配集合XSet中删除。

以上密钥Ω_i是通过如下步骤构建：

A、数据拥有者得到该加入用户的公钥pk_i及其可以访问的关键字集合通过密钥K_R以及公钥pk_i计算用户随机数r_i＝F_p(K_R,pk_i)，并计算用户标识初始化密钥集合CSK_i为空集；

B、对于中每个关键字w执行如下步骤，利用密钥K_C计算关键字密钥值K_w＝F(K_C,w)，并以此为密钥，计算用户公钥pk_i的哈希值csk_i,w＝H₁(K_w,pk_i)，然后将csk_i,w加入到CSK_i集合中，将公钥pk_i添加到与关键字w关联的访问控制列表KAL[w]中；

C、数据拥有者将K_S,K_X,K_Z,CSK_i,uk_i封装成Ω_i返回给该用户。

以上的用户关键字索引集合CSet、关键字文件标识符集合TSet、以及交叉匹配集合XSet是通过如下步骤构建：

(a)数据拥有者初始化用户关键字索引集合CSet、关键字文件标识符集合TSet、以及交叉匹配集合XSet为空集；

(b)对于整个关键字集合W中的每个关键字w，数据拥有者构建用户权限索引表CSet、关键字文件标识符集合TSet以及交叉匹配集合XSet；

本步骤(b)包括以下子步骤：

(b1)数据拥有者判断关键字集合W中取关键字w是否都已被取到，如果是，则进入步骤(b12)否则提取下一个关键字w，并进入步骤(b2)；

(b2)数据拥有者分别利用三个密钥K_S，K_T，K_X，K_C和关键字w计算加密关键字密钥K_e＝F(K_S,w)，索引关键字标签值stag_w＝F(K_T,w)，关键字交叉值xtrap_w＝F_p(K_X,w)以及权限关键字密钥K_w＝F(K_C,w)，并初始化公钥随机数集合K为空；

(b3)数据拥有者从访问控制列表KAL中查询出与该关键字w关联的所有用户公钥的集合PK_w.

(b4)数据拥有者判断公钥集合中的用户公钥是否全部被取到，如果是，则进入步骤(b11)，否则提取下一个用户公钥pk_i，并进入步骤(b5)；

(b5)数据拥有者计算用户随机数r_i＝F_p(K_R,pk_i)，将用户公钥随机数添加到K中；

(b6)数据拥有者以权限关键字密钥K_w为密钥，计算pk_i的带密钥的哈希函数值csk_i,w＝H₁(K_w,pk_i)；

(b7)数据拥有者以csk_i,w为密钥，利用两个不同的带密钥的哈希函数，分别计算uk_i的权限关键字哈希值和关键字混淆哈希值

(b8)数据拥有者在索引关键字标签值stag_w后添加λ位0，构成索引关键字认证标签值stag_w||0^λ；

(b9)数据拥有者对索引关键字认证标签值stag_w||0^λ和关键字混淆哈希值进行异或运算，得到权限关键字密文值

(b10)数据拥有者将添加到CSet集合中并进入步骤(b4)；

(b11)数据拥有者初始化计数器cnt值为1；

(b12)数据拥有者利用密钥K_Z和关键字w计算盲因子z＝F_p(K_Z,w)；

(b13)数据拥有者从明文数据库中获取关键字w关联的所有文件明文标识符的集合DB(w)；

(b14)数据拥有者判断文件明文标识符的集合DB(w)中的所有文件明文标识符ind是否都被取到，如果是则返回步骤(b1)，否则进入步骤(b15)；

(b15)数据拥有者利用密钥K_I和ind计算文件群标识符xind＝F_p(K_I,ind)并利用加密关键字密钥K_e和ind计算关键字标识符密文索引e₂＝Enc(K_e,ind)；

(b16)数据拥有者计算索引交叉值并利用stag_w为密钥，计算关于cnt带密钥的哈希值l＝H₄(stag_w,cnt)

(b17)数据拥有者将(e₂,y)加入到以l为索引的TSet中，并将cnt的值自增1；

(b18)数据拥有者判断用户公钥随机数集合K中的所有用户公钥随机数vk_i是否都被取到，如果是，则返回步骤(b14)，否则取下一个vk_i，并进入步骤(b19)；

(b19)数据拥有者计算交叉匹配值并将xtag加入到XSet中，并返回步骤(b18)。

图2是本发明与现有的OXT(即Oblivious Cross-Tags)算法和Muti-clientSearchable Symmetric Encryption(简称MSSE)算法进行对比的效果(其中DMMSE表示本发明的方法)。图2(a)表示构建时间随数据集大小的时间开销关系；图2(b)表示构建时间和用户数之间的关系。从结果可以看出，虽然本发明的构建过程比其他两个算法慢，但是依然和数据集大小成线性相关，与用户的多少也近似成线性关系。

图3是本发明与现有的单用户可搜索对称加密方法(Single-client searchablesymmetric encryption，简称SCSSE)、以及OSPIR方法的对比。图3(a)表示查询关键字密文产生时间与查询关键字个数的关系，控制第一个关键字关联的文件数是200，从图中可以看出，查询关键字密文的产生时间随查询关键字个数的增长呈线性相关。

图3(b)表示查询关键字密文产生的时间与第一个关键字关联的文件数目之间的关系，固定关键字个数是100。从图3(b)可以看出，本发明查询关键字密文的产生时间与第一个关键字关联的文件数目无关。从两幅图的效果中可以看出，相对于SCSEE和OSPIR方法而言，本发明的查询关键字密文的产生时间最少。

图4是与现有的OXT和MSSE算法进行对比。其中图4(a)是控制第一个关键字关联的文件数为200，变化总的查询关键字个数；图4(b)是控制总的连接查询的关键字个数为100，变化第一个关键字关联的文件个数。从效果可以看到本发明的查询时间几乎与查询关键字个数无关，而与第一个关键字关联的文件数近似成线性相关。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。