云存储安全中基于通配符的可搜索加密方法

摘要

本发明涉及一种云存储安全中基于通配符的可搜索加密方法，包括以下步骤：设置待上传文档；提取关键词集合；将所述关键词集合加密；选择随机数作为文档加密密钥，将文档加密密钥进行加密；加密待上传文档得到密文后发送给云计算平台；输入查询关键词集合，生成查询陷门并进行签名，发送给云计算平台；云计算平台对查询签名进行验证，云计算平台执行搜索算法；将关键词索引和查询陷门传入到关键词匹配协议中，得到加密的匹配结果；进行解密得到搜索结果；云计算平台根据所述搜索结果返回对应的密文；先恢复出文档加密密钥，然后恢复出文档。本发明支持至多两个通配符的关键词搜索，通配符可以出现在关键词的任何位置,且可以表示任意多个字符。

说明书

技术领域

本发明涉及一种云存储安全中基于通配符的可搜索加密方法

背景技术

云存储为用户提供无处不在的、动态的、可扩展的和按需存储的服务。云存储在给用户带来更多便利的同时也给用户的数据带来了严重的安全威胁。为了保护公有云服务器中的外包数据的隐私性，数据加密是防止内部/外部攻击者访问敏感信息的有效方法。同时，为了便于数据的使用，我们有必要支持用户在密文上进行关键词查询(无需解密)。这种机制称为可搜索加密。

把电子健康记录(EHR)存储系统作为可搜索加密的应用示例。假设用户Alice想把敏感的EHR数据存储在公共卫生云服务器中，她首先需要提取一组关键词集合来描述EHR，接着使用加密这些关键词来生成索引。接着将关键词加密索引和加密的EHR数据上传到云服务器。在数据检索阶段，用户Bob(如：Alice的医生或家属)生成陷门来进行关键词查询。云服务器使用陷门对加密的EHR数据进行搜索，最终返回匹配的文件给Bob。在搜索过程中，与关键词和EHR有关的明文信息不能泄露给云服务器。

2004年,Boneh等人提出公钥关键词可搜索加密(PEKS)的概念，来实现用户对加密数据进行关键词查询。之后，有人对不同应用场景中支持联结关键词和单关键词的PEKS进行了研究。为了实现多用户之间的查询权限共享，可搜索加密采用了不同的访问控制方法，例如代理重加密和基于属性的加密(ABE)。有人提出模糊关键词可搜索加密方案来实现对拼写错误的校正。然而这些方案只能进行精确关键词搜索或基于编辑距离的相似性搜索。

为了实现灵活的搜索功能，有人提出通配符可搜索加密的概念来支持含有通配符的关键词安全搜索。在查询阶段，用户输入关键词，关键词中包含一个通配符(可能代表一个或多个字符)。例如Alice的医生Bob可能使用关键词“05/**/2016”来搜索2016年5月Alice所有的EHR数据。他也可以使用关键词“ache”来搜索包含“headache”、“stomachache”或者“heartache”的EHR数据。然而，文献中大多数现有的通配符可搜索加密方案都是基于布隆过滤器(BF:Bloom Filter)构建的。布隆过滤器的缺点是：假阳性概率(falsepositive probability)是不可忽略的。这些基于布隆过滤器的通配符可搜索加密方案将会以不可忽略的概率向用户返回错误结果。此外，这些方案都是基于对称密钥机制设计的，因此数据拥有者必须泄露其私钥才能授予其他用户搜索权限，并且该授权是不可撤销的。

Jarecki等人研究了加密数据库的安全搜索，它支持任意的布尔查询。后来Sepehri等人提出了数据库中基于安全多方计算的查询方法和具有安全等式查询功能的代理重加密方案。Sun等人提出了数据库中支持布尔查询的多用户可搜索加密方案。除了面向数据库的可搜索加密方案，学者们也对非结构化加密数据的安全关键词查询进行了研究。

Li等人提出了云计算中加密数据的模糊关键词搜索方案。他们利用编辑距离来衡量关键词的相似度，并设计了两种构造模糊关键词集的方法，并用符号树来加速搜索算法。2013年，Li等人把方案推广到了基于ABE的多用户场景。2014年，Wang等人提出了多关键词模糊可搜索加密方案，方案构造基于布隆过滤器和局部敏感哈希函数。该方案可以校正较小的编辑距离错误，并支持多关键词搜索。随后，Fu等人提出可以校正更多拼写错误的方案。

现有的模糊可搜索加密方案的局限性在于：只能校正较小的编辑距离误差，例如拼写错误。如果查询关键词与精确关键词之间的编辑距离较大，则现有方案无法校正相关的错误。2010年，Sedghi等人在公钥密码架构中提出了带有通配符的可搜索加密方案，它的方案构造基于双线性对。隐藏向量加密(HVE)是Sedghi方案的构造核心，而HVE源于基于身份的加密。Sedghi的方案需要指定通配符的位置，每个通配符只能代表一个字符。在加密、生成陷门和测试算法中，Sedghi的方案需要大量的幂指数运算；其测试算法还需要大量耗时的双线性对运算。

2011年，Bosch等人在对称密码架构中引入了联结通配符可搜索加密方案，方案构造基于伪随机函数和布隆过滤器。与Sedghi的方案相比，Bosch的方案提高了效率。然而，它仅仅枚举了通配符关键词在词典中可以表示的常用关键词。然后，这些扩展的关键词都被插入到布隆过滤器中。由于Bosch的方案无法从有限的词典定义中提取出世界上所有的关键词，所以该方案的实用性非常有限。

2012年，Suga等人提出了基于布隆过滤器的通配符可搜索加密方案，其中每个关键词都配有单独的布隆过滤器。存储开销随着文档中提取的关键词数量的增加而增加。该方案的缺点是：一个通配符只能代表一个字符。例如，如果用户希望搜索所有以“acid”开头的关键词，他需要分别提交通配符关键词“acid**”、“acid***”和“acid********”才能够匹配关键词“acidic”、“acidity”和“acidification”。为了解决这个难题，Hu等人提出了一种改进的方案，其中一个通配符可以代表任意数量的字符。Hu的方案以Suga的方案为基础，并使用不同的方法把关键词插入到布隆过滤器中。

基于布隆过滤器的可搜索加密方案的缺点是：假阳性概率是不可忽略的。布隆过滤器是一种数据结构，可用于检测一个指定元素是否存在于一个集合中。它由一个长度为m位的数组表示，数组中每个元素初始值设置为0。布隆过滤器需要r个独立的哈希函数(h_t:{0,1}^*→[1,m](1≤t≤r))，每个哈希函数把一个元素映射到m个位置中的其中一个，也就是把集合中S＝{s₁,...s_n}的每个元素映射到布隆过滤器BF中。为了验证一个元素a是否属于S，需要检验BF中所有位置h_t(a)(1≤t≤r)的值是否被设为1。如果不是，元素a不属于S。否则，元素a可能属于S。因为哈希函数可能把一个或者多个元素映射到BF的同一位置上，因此布隆过滤器存在假阳性概率。假阳性概率f_p＝[1-(1-1/m)^rn]^r≈e^-m/nln(p)ln(1-p)，其中p＝(1-1/m)^rn≈e^-rn/m，它随着n/m的增长而增长。

发明内容

有鉴于此，本发明的目的在于提供一种云存储安全中基于通配符的可搜索加密方法支持至多两个通配符的关键词搜索，且通配符可以出现在关键词的任何位置。

为实现上述目的，本发明采用如下技术方案：

一种云存储安全中基于通配符的可搜索加密方法，其特征在于：包括上传过程和搜索过程；

所述上传过程包括以下步骤：

步骤A1：用户A设置待上传文档M的文档身份ID∈Z_N，加密所述文档身份ID为

步骤A2：提取关键词集合来描述所述待上传文档M；

步骤A3：使用K2C算法将所述关键词集合加密成

步骤A4：选择随机数K∈Z_N作为文档加密密钥，将所述文档加密密钥进行加密得到

步骤A5：加密所述待上传文档M得到密文C＝SEnc(M,K')，其中，

步骤A6：将加密索引和密文C发送给云计算平台；

所述搜索过程包括以下步骤：

步骤B1：用户B输入查询关键词集合并将其加密成

步骤B2：将所述用户B的匿名身份AID_B，签名和查询关系作为查询陷门发送给云计算平台；

步骤B3：所述云计算平台接收到查询陷门后，首先核实用户B是否有权访问数据，若有权限，则云计算平台使用公钥pk_B验证的签名若签名被验证是假的，则拒绝该查询请求，否则，云计算平台执行搜索算法；

步骤B4：云计算平台以W中的和中的Q_j为输入，将其传入到关键词匹配协议中，云计算平台和计算服务提供商交互运算得到加密的匹配结果如果果kw_i与qw_j匹配，则u_i,j＝1；否则u_i,j＝0；

步骤B5：用户B收到匹配结果后，解密得到搜索结果u^*；

步骤B6：云计算平台根据所述搜索结果u^*返回对应的密文C；

步骤B7：用户B先恢复出文档加密密钥K，然后计算并利用K'恢复出文档。

本发明与现有技术相比具有以下有益效果：首先，本发明支持多关键词搜索，任何查询关键词可以包含零个、一个或者两个通配符，其中通配符可以出现在关键词的任何位置并且代表任何数量的符号；其次，本发明支持使用一个陷门来同时搜索多个数据拥有者的数据；第三，本发明提供灵活的用户授权和撤销来有效地管理搜索和解密权限；第四，本发明是基于同态加密而不是基于布隆过滤器构建的，因此完全消除了由布隆过滤器引起的错误概率；最后，返回的匹配结果对云服务器完全保密，实现了更好的隐私保护。

附图说明

图1是本发明一实施例的系统结构框图。

图2是本发明的云服务结构。

图3是本发明K2C算法的示例图。

图4是本发明SCP协议的示例图。

图5是本发明FW协议的示例图。

图6是本发明MW协议的示例图。

图7是本发明BW协议的示例图。

图8是本发明FMW协议的示例图。

图9是本发明FBW协议的示例图。

图10是本发明MMW协议的示例图。

图11是本发明MBW协议的示例图。

图12是本发明八个协议的参数对比图。

具体实施方式

下面结合附图及实施例对本发明做进一步说明。

如图1所示为本发明一实施例的系统结构框图，其中：

密钥生成中心(KGC)是完全可信的，负责管理和分发系统中生成的公钥/私钥。KGC包括注册单元、密钥生成单元、证书单元和存储单元。注册单元为系统用户提供注册服务。密钥生成单元为系统和用户生成公钥/密钥。证书单元负责提供证书生成和吊销服务。存储单元负责存储证书和撤销列表。

云计算平台(CP)存储用户的加密文档并负责执行数据检索操作。CP包括存储单元、计算单元和元数据单元。存储单元提供存储服务，其中包括存储加密文档和安全关键词索引。计算单元提供计算服务，其中包括安全搜索操作。元数据单元提供元数据服务，其中元数据包括数据拥有者的信息、授权证书、文档位置以及文档上传和访问日期。元数据服务器还为系统用户提供通知服务，这项服务专门用于监测数据拥有者账户是否进行了更改。这些信息存储在数据库中，目的在于为用户提供更好的服务。

计算服务提供商(CSP)拥有丰富的计算资源，包括计算单元和元数据单元。CSP的计算单元与CP中的计算单元相互作用来执行安全计算。元数据单元负责存储CSP的授权证书，并通过查询授权证书来进行授权计算。假设CP和CSP不共谋。

数据拥有者加密关键词和文档，并将其发送到CP进行存储。用户生成关键词陷门，CP利用陷门来搜索加密数据。

安全套接层(SSL)或者传输层安全(TLS)协议用于保护CP和CSP、数据拥有者和CP、用户和CP以及KGC和其他实体之间的所有通信。SSL/TLS协议的主要目的在于提供两个通信实体之间的隐私保护和并保证数据完整性。

请结合图2，云计算为用户提供各种服务。最著名的服务包括基础架构即服务(IaaS)，平台即服务(PaaS)和软件即服务(SooS)。信息服务、计算服务和存储服务属于PaaS。为了向云服务器提供安全保护，安全服务是云计算中的一项重要服务。安全搜索是云服务器中的安全服务之一，被称为安全搜索即服务(secure search as a service)，它为信息服务、计算服务和存储服务提供了安全性。本发明属于云计算中安全搜索即服务的范畴。

该系统包括以下基础部件：具有门限解密功能的Paillier密码系统、关键词表示和加密、安全大于或等于协议和加密关键词等价测试协议，具体如下：

具有门限解密功能的Paillier密码系统(PCTD:Paillier Cryptosystem withThreshold Decryption)实现了同态性加密，可以在云平台中提供外包数据的隐私性性。利用同态性质，我们无需对密文进行解密，就可以直接进行各种计算，从而就能实现安全的外包计算。此外，它的计算开销低于全同态加密系统所需的计算开销。令表示X的比特长度。

密钥生成：κ是安全参数，p和q是两个大素数，计算N＝pq，λ＝lcm(p-1,q-1)/2(lcm表示两个数的最小公倍数)。定义函数选择生成元g并且g的阶为ord(g)＝(p-1)(q-1)/2。系统公共参数PP＝(g,N)，主私钥SK＝λ。系统为每位用户i分配私钥sk_i∈Z_N和公钥

加密：对于输入的明文m∈Z_N，用户随机选择r∈[1,N/4]，使用其公钥pk_i将明文m加密成密文其中C₂＝g^rmodN²。

利用用户私钥sk_i解密：对于输入的密文和私钥sk_i，我们通过计算能够得到明文

用主私钥SK进行解密：利用系统的主私钥SK＝λ，通过计算就能对所有使用公钥加密生成的密文进行解密。若gcd(λ,N)＝1(gcd表示两个数的最大公约数)成立，则有

主私钥分裂：主私钥SK＝λ可以随机分裂成两个部分SK₁＝λ₁和SK₂＝λ₂，使得λ₁+λ₂＝0modλ，λ₁+λ₂＝1modN²。

用SK₁进行部分解密(PD1)：对于输入的密文可以利用SK₁＝λ₁来计算

用SK₂进行部分解密(PD2)：对于输入的密文和可以利用SK₂＝λ₂来计算通过计算可以恢复出明文

密文更新(CR)：CR算法用于更新密文，将密文转化成新的密文且m＝m'。随机选择r'∈Z_N，计算C₂'＝C₂·g^r'modN²。

PCTD具有同态性：对于随机的r∈Z_N，

具有门限解密功能的Paillier密码系统使用到了下述协议，这些协议都需要CP和CSP交互运算执行。pk_A和pk_B是用户A和B的公钥。pk_Σ是为用户A和B定义的联合公钥。

SAD跨域安全加法协议：对于给定的和计算得到

SMD跨域安全乘法协议：对于给定的和计算得到

SLT跨域安全小于比较协议：对于给定的和计算如果X＜Y，则u＝1。如果X≥Y，则u＝0。

关键词表示和加密：请参照图3，为了把一个关键词编码成集合Z_N中的一个元素，首先把关键词中的每个字母转换成其ASCII码形式，接着把十六进制的ASCII码转化成十进制。根据每个字母在关键词中的位置，每个元素乘以一定的权重，使用PCTD算法对这些十进制数进行相加和加密。该算法称为K2C关键词转化密文算法。

SGE安全大于或等于协议：给定两个密文和(X,Y≥0，SGE协议输出来表示X和Y之间的关系：如果u^*＝1，表示X≥Y；如果u^*＝0，表示X＜Y。SGE协议的描述如下。

(1)CP计算

CP随机选取r，使其满足接着CP随机掷硬币s∈{0,1}。CP和CSP执行以下操作：

如果s＝1，计算

如果s＝0，计算

然后CP计算并把(l,l')发送给CSP。

(2)CSP解密如果L(l″)＞L(N)/2，CSP令u'＝0，否则u'＝1。接着CSP利用pk_Σ来加密u'，并把发送给CP。

(3)CP接收到后，如果s＝1，CP令否则，CP令

KET加密关键词等价测试协议：

给定的两个加密关键词和(X,Y≥0，),该协议输出加密结果来判断两个关键词是否相等。CP和CSP计算

如果u^*＝1，表示两个关键词相同。如果u^*＝0，表示两个关键词不相同。

本发明提供一种云存储安全中基于通配符的可搜索加密方法，包括上传过程和搜索过程；

所述上传过程包括以下步骤：

步骤A1：用户A设置待上传文档M的文档身份ID∈Z_N，加密所述文档身份ID为

步骤A2：提取关键词集合来描述所述待上传文档M；

步骤A3：使用K2C算法将所述关键词集合加密成

步骤A4：选择随机数K∈Z_N作为文档加密密钥，将所述文档加密密钥进行加密得到

步骤A5：加密所述待上传文档M得到密文C＝SEnc(M,K')，其中，

步骤A6：将加密索引和密文C发送给云计算平台；

所述搜索过程包括以下步骤：

步骤B1：用户B输入查询关键词集合查询关键词可能包含零个，一个或者两个通配符。如果通配符出现在关键词的头部或者中部，B指定一个正整数来表示该通配符能代表的最大字符数。B根据关键词的类型把查询关键词qw_i(1≤i≤n₂)加密成Q_i，令用户B指定查询(即AND或OR)关系来进行联结(conjunctive)或分离(disjunctive)关键词查询。

步骤B2：将所述用户B的匿名身份AID_B，签名和查询关系作为查询陷门发送给云计算平台；

步骤B3：所述云计算平台接收到查询陷门和查询关系(AND或OR)后，首先核实用户B是否有权访问数据，若有权限，则云计算平台使用公钥pk_B验证的签名若签名被验证是假的，则拒绝该查询请求，否则，云计算平台执行搜索算法；

步骤B4：根据Q_j中的参数，云计算平台以W中的和中的Q_j为输入，将其传入到关键词匹配协议中，所述关键词匹配协议包括KET,FW,MW,BW,FMW，FBW,MMW和MBW，云计算平台可根据图12选择相应的协议，云计算平台和计算服务提供商交互运算得到加密的匹配结果如果果kw_i与qw_j匹配，则u_i,j＝1；否则u_i,j＝0；

如果用户想要进行OR查询，CP首先初始化计算如果u^*＞0，表示陷门与文档中的关键词匹配；否则u^*＝0。

如果用户想要进行AND查询，CP首先初始化CP和CSP交互运算得到如果u^*＝1，表示陷门与文档中的关键词匹配；否则u^*＝0。最后，CP把发送给用户。

步骤B5：用户B收到匹配结果后，解密得到搜索结果u^*；如果B进行OR查询，B会对u^*进行排列并要求CP返回前k篇u^*值(相关度分数)较高的文档。如果B进行AND查询，B会要求CP返回所有或者部分u^*＝1的文档，B会把发送给CP来进行文档查询；

步骤B6：云计算平台根据所述搜索结果u^*返回对应的密文C；

步骤B7：用户B先恢复出文档加密密钥K，然后计算并利用K'恢复出文档。

于本实施例，所述关键词匹配协议包括KET,FW,MW,BW,FMW，FBW,MMW和MBW，其中：

FW,MW,BW属于单通配符搜索，单通配符搜索是指搜索的关键词中只含有一个通配符，并且该通配符可以表示任意数量的字符。由于单通配符可能出现在字符串的头部、中部或尾部，我们设计了三个协议来处理这些情况。CP和CSP负责执行这些协议，并且它们都不知道匹配结果的明文信息。

假设数据拥有者A的文档包含关键词X，A使用公钥pk_A将其加密成用户B生成具有通配符的关键词来进行查询。以下协议将测试提交的查询是否与匹配。我们用*表示通配符。当通配符出现在关键词的头部或者中部时，用户B指定正整数v₁来表示通配符可以代表的最大字符数。当通配符出现在关键词的尾部时，通配符可以表示任意数量的字符。

FMW，FBW,MMW，MBW属于双通配符搜索，双通配符搜索是指搜索的关键词中只含有两个通配符，并且每个通配符都可以表示任意数量的字符。由于通配符可能出现在字符串的头部、中部或尾部，我们设计了四个协议来处理不同的情况。CP和CSP负责执行这些协议，并且它们都不知道匹配结果的明文信息。当通配符出现在关键词的头部或中部时，用户B用一个正整数来表示该通配符可以替代的最大字符数。令v₁,v₂分别表示两个通配符所能替代的最大字符数。当通配符出现在关键词的尾部时，可以代表任意数量的字符。

通配符搜索中重要的工具包括：安全多比特提取协议和安全密文划分协议，

MBE安全多比特提取协议：

给定密文[X]和正整数该协议的输出是[x]，其中，x是X的比特表示的最低比特有效位。MBE协议执行如下。

(1)CP随机选取r∈Z_N，计算Y＝[X]·[r]和并把(Y,Y')发送给CSP。

(2)CSP计算和并把[y₁]发送给CP。

(3)CP计算和[x']＝[y₁]·[r₁]^N-1。

(4)CP和CSP计算

(5)然后，CP计算

MBE协议的工作原理解释说明如下。

(1)为了保护X的隐私，CP首先选择随机数r∈Z_N，然后通过计算Y＝[X]·[r]＝[X+r]来隐藏X的明文信息。

(2)CSP解密后得到y＝X+rmodN。由于X,r∈Z_N且r是随机数，因此CSP不能从y推导出X的信息。接着CSP计算来得到y的最低比特。加的目的是处理的进位。

(3)r₁是r的最低比特位。CP计算

(4)如果则

如果则

(5)如果说明则有

如果说明则有

SCP安全密文划分协议：

给定密文[X]和正整数SCP协议输出[X₁]和[X₂]，使得X₁是X的最低比特有效位，并且SCP协议执行如下。

(1)CP和CSP计算

(2)CP计算Z＝[X]·[X₁]^N-1和[X₂]＝Z^amodN，其中

SCP协议的示例如图4所示。如果[X]是关键词“privacy”的密文且SCP协议输出[X₁]和[X₂]，使得[X₁]是“pri”的加密形式，[X₂]是“vacy”的加密形式。SCP协议把加密的关键词安全地划分成两个加密的字符串。

八个关键词匹配协议的具体内容如下：

KET为加密关键词等价测试协议，给定的两个加密关键词和该协议输出加密结果来判断两个关键词是否相等，CP和CSP计算如下：

如果u^*＝1，表示两个关键词相同；如果u^*＝0，表示两个关键词不相同；

FW为安全头部通配符匹配协议，用户B首先生成一个“*+Y₁”形式的通配符型关键词，其中Y₁是字符串；用户B利用K2C算法将Y₁加密成输入和v₁，FW协议输出如果通配符关键词“*+Y₁”与X匹配，则u＝1；否则，u＝0；

首先，初始化协议包括v₁+1轮。在第i轮，被划分成两个部分和的明文包含i个字符。X₁是通配符代表的字符串。如果X₂＝Y₁，有u_i＝1；否则u_i＝0。然后，计算在v₁+1轮后，如果u＞0，协议输出否则FW的示例如图5所示。

MW为安全中部通配符匹配协议，用户B首先生成一个“Y₁+*+Y₂”形式的通配符型关键词，其中Y₁,Y₂是字符串，Y₁中包含η₁个符号，用户B利用K2C算法把Y₁，Y₂加密成输入v₁和η₁，MW协议输出密文如果通配符关键词“Y₁+*+Y₂”与X匹配，则有u＝1；否则，u＝0；

首先，初始化然后，被划分成两个部分和的明文包含η₁个符号。如果X₁＝Y₁，则有u₁＝1；否则，u₁＝0。通过FW协议检测“*+Y₂”是否与X₂匹配。如果匹配，则有u₂＝1；否则，u₂＝0。然后，计算如果u₁＝1，u₂＝1，则有u＝1，否则u＝0。MW的示例如图6所示。

BW为安全尾部通配符匹配协议，用户B生成一个“Y₁+*”形式的通配符关键词，其中，Y₁是字符串并包含η₁个符号；然后，用户B利用K2C算法将Y₁加密成输入和η₁，BW协议输出密文如果通配符关键词“Y₁+*”与X匹配，则有u＝1；否则，u＝0；

首先，被划分成两个部分和其中的明文包含η₁个字符，X₂是通配符代表的字符串。如果X₁＝Y₁，则有u＝1；否则，u＝0。BW的示例如图7所示。

FMW为安全头部和中部通配符匹配协议，用户B生成一个“*+Y₁+*+Y₂”形式的通配符关键词，其中Y₁,Y₂是字符串，Y₁包含η₁个符号，用户B利用K2C算法将Y₁，Y₂加密成输入v₁、v₂和η₁，FMW协议输出密文如果通配符关键词“*+Y₁+*+Y₂”与X匹配，则有u＝1；否则，u＝0；

首先初始化FMW协议使用两层循环来进行关键词测试：外层循环遍历第一个通配符所能代表的不同字符(或字符串)；内层循环遍历第二个通配符所能代表的不同字符(或字符串)。被划分成两个部分和其中X₁包含i个符号(0≤i≤v₁)，并且X₁是第一个通配符代表的字符串。然后，被划分成两个部分和其中X₃包含η₁个符号。如果X₃＝Y₁，则有s_i＝1；否则，s_i＝0。接着，被划分成两个部分和其中X₅包含j个符号(0≤j≤v₂)，并且X₅是第二个通配符代表的字符串。如果X₆＝Y₂，则有t_j＝1；否则，t_j＝0。计算如果s_i＝1，t_j＝1，则有u_i,j＝1；否则，u_i,j＝0。然后，将u_i,j与u相加。最后，如果u＞0，协议输出否则，FMW的示例如图8所示。

FBW为安全头部和尾部通配符匹配协议，用户B生成一个“*+Y₁+*”形式的通配符关键词，其中Y₁是字符串并且包含η₁个符号；用户B利用K2C算法将Y₁加密成输入v₁和η₁，FBW协议输出密文如果通配符关键词“*+Y₁+*”与X匹配，则有u＝1；否则，u＝0；

首先初始化FBW协议使用遍历算法来测试关键词，它遍历了第一个通配符所能代表的不同字符(或字符串)。分成两个部分和其中X₁包含i个符号(0≤i≤v₁)，X₁是第一个通配符代表的字符串。然后，分成两个部分和其中X₃包含η₁个符号。如果X₃＝Y₁，则有s_i＝1；否则，s_i＝0。然后，将s_i与u相加。如果u＞0，则协议最终输出否则，输出FBW的示例如图9所示。

MMW为安全中部和中部通配符匹配协议，用户B生成一个“Y₁+*+Y₂+*+Y₃”形式的通配符关键词，其中Y₁，Y₂，Y₃是字符串，并且Y₁，Y₂分别包含η₁，η₂个符号，用户B利用K2C算法将Y₁，Y₂加密成输入v₁、v₂、η₁和η₂，MMW协议输出密文如果通配符关键词“Y₁+*+Y₂+*+Y₃”与X匹配，则有u＝1；否则，u＝0；

首先，初始化MMW协议使用两层循环来进行关键词测试：外层循环遍历第一个通配符所能代表的不同字符(或字符串)；内层循环遍历第二个通配符所能代表的不同字符(或字符串)。被划分成两个部分和其中X₁包含η₁个符号。如果X₁＝Y₁，有u₁＝1，否则u₁＝0。被划分成两个部分和其中X₃包含i个符号(0≤i≤v₁)，X₃是第一个通配符代表的字符串。然后，被划分成两个部分和其中X₅包含η₂个符号。如果X₅＝Y₂，则有s_i＝1；否则，s_i＝0。被划分成两个部分和其中X₇包含j个符号(0≤j≤v₂)，X₇是第二个通配符代表的字符串。如果X₈＝Y₃，则有t_j＝1；否则，t_j＝0。计算如果s_i＝1，t_j＝1，则有u_i,j＝1；否则，u_i,j＝0。计算如果u_i,j＝1，t_j＝1，则否则，然后，将与相加。如果u＞0，协议最终输出否则，输出MMW的示例如图10所示。

MBW为安全中部和尾部通配符匹配协议，用户B生成一个“Y₁+*+Y₂+*”形式的通配符关键词，其中Y₁，Y₂是字符串，Y₁，Y₂分别包含η₁，η₂个符号；B利用K2C算法将Y₁，Y₂加密成输入v₁，η₁和η₂，MBW协议输出密文如果通配符关键词“Y₁+*+Y₂+*”与X匹配，则有u＝1；否则，u＝0。

首先初始化MBW协议使用循环遍历的方式来进行关键词测试：循环遍历第一个通配符所能代表的不同字符(或字符串)。被划分成两个部分和其中X₁包含η₁个符号。如果X₁＝Y₁，则有u₁＝1；否则u₁＝0。被划分成两个部分和其中X₃包含i个符号(0≤i≤v₁)，X₃是第一个通配符代表的字符串。被划分成两个部分和其中X₅包含η₂个符号。如果X₅＝Y₂，则有s_i＝1；否则，s_i＝0。计算如果s_i＝1，u₁＝1，输出否则然后，计算如果u＞0，协议最终输出否则，MBW的示例如图11所示。

本发明还涉及密钥生成算法和用户撤销和授权算法。

密钥生成算法：

SEnc/SDec是密码上安全的对称加密/解密算法对(对称密钥空间为)，Sig/Verify是一种密码上安全的签名/验证算法对。定义哈希函数H₁:{0,1}*→Z_N和

通过运行PCTD的KeyGen算法，KGC生成系统公共参数PP＝(g,N)、主私钥MSK＝λ和用户A_i的公钥/私钥对KGC计算主公钥MPK＝g^λ。KGC秘密保管MSK，公开MPK。接着KGC执行PCTD的主密钥分裂算法来生成部分主密钥SK₁＝λ₁和SK₂＝λ₂，并分别把它们秘密发送给CP和CSP，把秘密发送给用户A_i并公开为了保证用户A_i身份的隐私性，KGC为用户生成匿名身份其中是正整数并且的值大于系统中的总用户数量。

用户撤销和授权算法：

如果用户A想要把搜索和加密权限授予用户B，A会设置授权有效期VP来表示授权的开始和结束时间(例如VP＝“20170101-20180101”)。A为B生成带有证书号CN的授权证书。为了保证CN的唯一性，CN号是由AID_A开头，从而表明该该证书是由用户A生成的。生成的授权证书CER_A,B为：

<cer＝(CN,AID_B,VP,pk_Σ),Sig(cer,sk_A)>，

其中sk_Σ＝H₁(CN,sk_A)。为了简便表述，我们将Z_N的元素作为Sig算法的私钥。在实际使用中，可以使用哈希函数从Z_N的元素中计算出签名密钥。产生的授权私钥sk_Σ被秘密发送给B。授权证书CER_A,B被发送给KGC、CP、CSP和B。当VP过期时，授权将自动失效。

如果A想要在VP时间段内撤销B的授权，需要生成撤销证书RVK_A,B：<rvk＝(revoke,CN),Sig(rvk,sk_A)>。接着，RVK_A,B被发送给KGC、CP、CSP和B。

如果B想要同时对数据拥有者(A₁,...,A_m)的文档进行查询，他必须向每一位数据拥有者(A₁,...,A_m)申请授权证书然后向KGC申请授权证书。在验证证书的有效性后，KGC计算有效期VP_Σ＝VP₁∩...∩VP_m，并生成证书CER_Σ,B：<cer＝(CN,AID_B,VP_Σ,pk_Σ),Sig(cer,MSK)>,其中sk_Σ＝H₁(CN,MSK)。证书的CN号应该由KGC的身份(ID_KGC可能设置为个0)开头，表明该证书是由KGC生成。sk_Σ被秘密发送给用户B，pk_Σ对CP、CSP和B公开。

如果要在有效期VP_Σ内撤销KGC生成撤销证书RVK_Σ,B：<rvk＝(revoke,CN),Sig(rvk,MSK)>。然后，KGC把RVK_Σ,B发送给CP、CSP和B。

以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。