支持用户撤销的可验证密文检索方案

白 平，张 薇，李 聪， 王绪安

(1.武警工程大学密码工程学院，西安710086; 2.网络与信息安全武警部队重点实验室，西安710086)(*通信作者电子邮箱bp15771937011@163.com)

0 引言

随着云计算技术［1］快速发展，越来越多用户倾向于将个人隐私数据存储在云端，以便减少用户的本地计算和维护开销。然而，用户在享受云端带来高效快捷服务的同时，如何才能保证这些隐私数据不被窃取或者破坏也成为人们关注的问题。现如今，对于外包的隐私数据主要是通过各类加密［2－4］手段进行保障，在一定程度上可以达到保护隐私数据的目的。然而，在保护了数据机密性的同时，却引发出另一个问题，即用户如何能准确无误地对这些外包的密文数据进行检索呢?由于云端上储存的数据是密文数据，故用户无法按照传统的检索方法进行检索，即服务器在明文上进行搜索操作。此外，假如我们将所有密文数据重新下载到本地解密后进行检索查询，固然可以实现安全检索，但这样会极大地增加用户开销，同时也削弱了外包的价值。因此，寻找一种能够在不可信的云环境下实现密文安全精确的检索成为人们亟待解决的问题。

基于上述提出的问题，Boneh等［5］最早提出基于关键词的公钥搜索(Public Key Encryption with Keyword Search，PEKS)算法，并在Boneh和Franklin设计的IBE(Identity-Based Encryption)加密方案——BF-IBE加密方案的基础上构造了第1个基于公钥的可搜索加密方案，随后不同功能的搜索加密方案［6－9］应运而生。这些方案从构造模型上大体可以分为以下四类:单用户单关键词模型、单用户多关键词模型、多用户单关键词模型，以及多用户多关键词模型，它们均不同程度地存在一些缺陷。例如，文献［10］提出的基于混合结构可实现单关键词精确检索的可搜索加密系统，优点在于能够实现对密文的精确检索，但方案中用户关键词信息对于外部服务器是公开透明的，从而极大降低了用户数据的安全系数。为了增强用户数据的安全性，Golle等［11］在单关键词基础上进行改进优化，提出了多关键词的构想。文献［12］首次提出非结构化文本的多关键词可搜索加密方案，相比单关键词的方案而言，优点在于无需事先指定关键词的位置，每次搜索遍历所有关键词，但这样带来的后果是延长搜索时间，影响检索效率。

为了保证用户数据的安全性和隐私性，同时使外包数据的利用率达到最大化，本文主要进行如下的工作:

1)提出了一种多服务器多关键词方案，用户可以将数据分别存储在不同的云服务器，有效防止了单个云服务器的某些恶意行为，提高了用户隐私数据的安全性。此外，多关键词的设定缩短了用户搜索时间，提高了检索效率。

2)提供了一种可验证返回结果是否具有完整性的算法，实现对云服务器返回结果的有效验证，提高了检索准确率。

3)通过重加密方法实现了用户撤销，从而灵活地控制了用户对密文的访问权限，防止授权用户的非法操作，有效解决云端共享数据的安全问题。

1 预备知识

1.1 双线性映射

G、GT是两个阶为p的循环群，g为生成元，则双线性映射e:G×G→GT满足下列性质:

1)双线性性:对任意 r，s∈ G 和 a，b∈ Zp，都有e(ra，sb)=e(r，s)ab。

2) 非退化性:存在 r，s∈ G，使得 e(r，s) ≠1。

3)可计算性:存在有效的多项式算法对任意r，s∈GT，都可以计算出e(r，s)。

1.2 选择关键词攻击IND-CKA安全模型

初始化 设定安全参数为k，运用初始化算法Setup(k)生成密钥s'并将其发给挑战者C;同时，将生成的参数h'发给攻击者A。

阶段1 攻击者A不断对关键词W*={w1，w2，…，wn}进行询问，挑战者C自适应地选择多项式个关键词密文索引Ii(i=1，2，…，n)。

挑战 攻击者A随机选择两个关键词w'0、w'1发送给挑战者C，要求这两个关键词w'0、w'1在阶段1中未向挑战者C查询过。C随机选取一个比特值b∈{0，1}，计算密文索引Ib发送给攻击者A。

阶段2 攻击者A向挑战者C适应性地选择除w'0、w'1外的其余关键词的密文索引，挑战者C按照阶段1中的方式进行回应。

猜测 攻击者A输出猜测结果，如果b=b'，则A攻击成功。A赢得游戏的概率定义为 AdvA(k)=|Pr［bA=b'］－1/2|。

2 系统模型及索引结构

2.1 支持用户撤销的可验证密文检索方案的系统模型

本文的系统模型主要由五部分组成:授权用户(Authorized Users，AU)、密钥授权中心(Key Authorized Center，KAC)、中心服务器(Central Server，CS)、审计服务器(Audit Server，AS)和存储服务器 S1，S2，…，SN。授权用户(AU)是数据的实际操作者，主要担负两项任务:一是加密文档后上传至存储服务器S1，S2，…，SN;二是加密关键词索引后上传至中心服务器，同时负责和密钥授权中心和审计服务器的交互。密钥授权中心(KAC)负责为授权用户生成密钥以及上传密钥至中心服务器。中心服务器(CS)负责存储用户密文文档和关键词索引结构。审计服务器(AS)负责验证搜索结果的完整性。存储S1，S2，…，SN负责存储密文文档和中心服务器重加密后的密文索引。支持用户撤销的可验证密文检索方案的系统模型如图1所示。

图1 系统模型示意图Fig.1 Schematic diagram of system model

通过图1可以看出，本文方案的中心服务器不要求必须是诚实可信的。假如中心服务器返回的检索结果是错误或者伪造的，授权用户是可以通过和审计服务器的交互成功识别这些错误反馈。此外，对于授权用户也不要求必须始终是诚实可信的，当授权用户完成其任务后，可以通过用户撤销机制删除该授权用户的检索权限，从而防止其进行一些恶意的操作行为。

2.2 关键词索引结构

假设有m个授权用户具有访问权限，即AU={v1，v2，…，vm}，被加密上传到中心服务器(CS)的密文文档有n个，即Files={f1，f2，…，fn}，取文档Files中的一部分作为其关键词信息，即 W={w1，w2，…，wd}。为了更精确地实现密文检索，需要创建关键词的索引结构，具体过程如下:首先、关键词被上传到中心服务器之前，授权用户会对这些关键词进行签名及加密以形成关键词的索引I;其次，授权用户将索引I上传给中心服务器(CS)，CS对这些索引再进行一次加密操作;最后，为这些最新生成的文件关键词索引创建索引结构，如表1所示，并发送给存储服务器S1，S2，…，SN进行存储。这样就完成了对用户文档、关键词的加密保护，同时，也为将来实现精确检察外包密文文档打下基础，云服务器可以通过表1中关键词进行检索查询，从而找出用户想要检索的文档。

表1 关键词索引结构Tab.1 Index structure of keywords

3 方案的构造

云环境下支持多服务器多关键词的可验证密文检索及用户撤销方案主要包括以下8个算法。

1)初始化算法Setup(k):选择一个完全可信的授权用户执行该算法，输入安全参数k，输出一个由g生成阶为p的循环群G，随机选取两个密钥s，s'∈，计算 h=gs，h'=gs－s';并选取防碰撞的哈希函数H1:{0，1}*→，H2:{0，1}*→和分组加密算法AES(·)的对称密钥K，此密钥仅被可信授权用户所拥有。公开参数 params=(G，g，H1，H2，h)，用户私钥 sk=(K，s，s')。

2)密钥生成算法KeyGen(AU，r):授权用户(AU)执行该算法，随机选取参数r，计算gr，h″=(h')r和hr，并将h″发送给中心服务器(CS)作为其私钥SKCS=h″。

3)加密算法Encrypt(K，ID，D，W):授权用户执行该算法，输入密钥 s和 s'，身份标识列表 ID={id1，id2，…，idn} ∈G，文档D、分组密钥K及其关键词列表W={w1，w2，…，wd}，对关键词进行签名 δi=［H1(wi)idi］s，加密关键词为E(wi)=gr(s'+δi)，其中1 ≤i≤n。令索引为I=(gr，hr，E(w1)，E(w2)，…，E(wn))。将索引I和加密后的文档关键词索引结构发送给中心服务器，中心服务器接收到索引I后，随即用其拥有的私钥 SKCS=h″再一次对关键词进行如下计算:E'(w1) =gr(s'+δi)·h″=(h·gδi)r，E'(w2) =gr(s'+δ2)·h″=(h·gδ2)r，…，E'(wn) =gr(s'+δn)·h″=(h·gδn)r，并更新索引为 I'=(gr，hr，E'(w1)，E'(w2)，…，E'(wn))，将表 1 中原有对 应 的 关 键 词 用 {H2［E'(w1)］，H2［E'(w2)］，…，H2［E'(wn)］}进行替换;将新文档关键词索引结构发送给存储服务器 S1，S2，…，SN;最后，运用分组加密算法 AES(·)加密文档D，即C=AESK(D)。

4) 陷门生成算法 GenerateTrapdoor(s，s'，t″，w'1，w'2，…，w'd):授权用户执行该算法，生成陷门的主要作用是允许任意一个授权用户均可以对密文文档进行搜索，输入密钥s，s'和需要检索的关键词 w'1，w'2，…，w'd，随机选择参数 t″∈，计算 Y = (gr)t″。对每个关键词 w'i，计算 Ti= t″+［H1(w'i)idi］s+s'，其中 1 ≤ i≤ d，将陷门 T=(T1，T2，…，Td，Y)发送给中心服务器。

5) 密文搜索算法Search(T，I，h″):中心服务器(CS) 执行该算法，输入陷门T=(T1，T2，…，Td，Y)，索引I和私钥SKCS=h″，计算(gr)TI·h″/Y=(gr［t″+［H1(w'i)idi)］s+s'］·(gs－s')r)/(gr)t″=(h·gδ'i)r，其中 δ'i= ［H1(w'i)idi］s，再计算 H'i=H2［(h·gδ'i)r］，其中1 ≤ i≤ d，将 I″=(H'1，H'2，…，H'd) 发送给存储服务器 S1，S2，…，SN。

接下来存储服务器S1，S2，…，SN开始进行匹配检索，具体过程是将I″=(H'1，H'2，…，H'd)中计算所得的哈希值与关键词索引结构中(见表1)中每个id(fi)中所包含的关键词的哈希值H2［E'(wi)］进行比较。如果匹配成功，则表明搜索成功，中心服务器把相关密文C'(C'表示通过密文搜索算法搜索到的密文)发送给审计服务器;否则，重新进行搜索操作。

6) 验证算法 Verify({id1，id2，…，ids}，C'):审计服务器(AS)执行该算法，为了验证返回结果的正确性，审计服务器首先生成随机数 z1，z2，…zs∈，然后把{(τ，zτ)|1 ≤ τ ≤s}发给中心服务器。中心服务器得到挑战信息(τ，zτ)后，计，并把回复信息{π，ID'={idr，1≤τ≤s}} 发给审计服务器(AS)，最后 AS通过验证等式 e(π，g) =来进行判断。假如验证等式成立，则发送C'给授权用户;否则，重新进行搜索匹配。

7)用户撤销算法UserRevocation(SK'CS):授权中心(KAC)执行该算法，当授权用户完成其任务后，为了防止授权用户的某些恶意行为，系统会将其系统权限收回。此时，授权中心(KAC)会选择新的随机值，通过安全途径发送给其他合法的用户。随后合法授权用户将向中心服务器请求重加密操作以便可以正常解密，同时更新中心服务器私钥为SK'CS=(h″)a，具体步骤如下:

a) 生成新的签名 γi= ［H1(wi)idi］as，E(wi) =gar(s'+γi)，其中1≤ i≤n。

b)中心服务器通过更新的私钥 SK'CS=(h″)a，计算E'(wi) =gar(s'+γi)·(h″)a=(h·gγi)ar，其中 1 ≤ i≤ n。

c)更新后关键词索引:(gar)Ti·SK'CS/(gar)t″={gar(t″+［H1(w'i)idi］as+s')·(gs－s')ar}/(gar)t″=(h·gγi)ar。

8)解密算法Decrypt(K，C'):输入分组密钥K和通过验证算法的密文 C'，对于任意的 fi∈ C'，计算 fi=DecK(AESK(fi))。

4 方案的分析

4.1 安全性分析

定义1 判定Diffe-Hellman问题(Decisional Diffe-Hellman Problem，DDHP)假设:由g生成的循环群为G且阶为 p，对于 a，b，c ∈ Z*p，给定(ga，gb，gab) 和(ga，gb，gc)，则DDHP问题为判断是否c=ab mod p成立。

定义2 多项式函数μ(x):N→R，如果对于任何一个正多项式 poly(n)，有一个自然数 c，使得对于所有 G，有μ(x) ＜1/poly(x)，则称函数μ是可忽略的，记为negl(x)。

定理1 假如DDHP假设成立，那么攻击者不可能选择关键词攻击成功该系统，因此方案是IND-CKA安全的。

证明 如果攻击者A能够以不可忽略的概率ε赢得游戏IND-CPA，则挑战者C能以不可忽略的概率ε解决DDHP问题，具体过程如下:

初始化 设定参数h1=ga，h2=gb，h3=gc，随机选取参数t∈{0，1}k和哈希函数H(x):{0，1}*→;令h=h1=ga，公开参数为 params=(G，g，p，H，h)。

阶段1 攻击者A向挑战者C询问关键词列表Wi={w'1，w'2，…，w'd}的密文索引，而后挑战者C将Wi加密后发送给A。具体加密方式:挑战者C随机选择r∈，计算 gr和hr，对于任意的 w'i，计算 δ'i= ［H(w'i)idi］s，E(w'n) =gr(s'+δ'n)·h″=(h·gδ'n)r，输出 I'=(gr，hr，E(w'1)，E(w'2)，…，E(w'n))。

挑战 攻击者A随机选择两个关键词w'0、w'1发送给挑战者C，要求这两个关键词w'0、w'1未向挑战者C查询过。挑战者C随机选择b∈{0，1}，计算δ'b=［H(w'b)idb］s，同时随机选择 r'∈，计算 E(w'b)=(h3·)r'，输出密文索引Ib=(，E(w'b)) 并返回给 A。

阶段2 挑战者A向攻击者C查询除了w'0、w'1其余关键词的密文索引。

猜测 攻击者A输出密文索引Ib中对b的猜测bA∈{0，1}。如果bA=b，则称A攻击成功，此时攻击者C回答DDHP挑战中c=ab，否则C回答c≠ab。

若敌手A想要赢得游戏，必定存在c=ab，则w'b的关键词索引密文 Ib=(，，(h3·hδ'b2)) =(gbr'，gabr'，(gabr'·gδ'b)) =(gbr'，hbr'，(h·gδ'b)br') 是一个正确的关键词密文;若A无法赢得游戏，必定存在c≠ab，则Ib不是一个正确关键词列表的密文。综上所述，如果A能够赢得游戏，则挑战者C就能够以不可忽略概率解决DDHP挑战。故本文满足IND-CKA安全。

此外，方案使用哈希函数和用户私钥s来共同对关键词进行签名，运用随机参数r和私钥s'完成对关键词的加密，故关键词的安全性取决于私钥s、s'和参数r，敌手只有同时获取这三个参数，才能解密得到完整的关键词信息。此外，关于数据完整性的验证，由于挑战信息{(τ，zτ)|1≤τ≤s}是审计服务器随机产生的，如果服务器返回错误的结果，则无法通过等式的验证，因此恶意云服务器是无法伪造检索结果来通过审计服务器的验证的。

4.2 效率分析

表2中:n表示用户文档数目，m表示文档中关键词数量，ω表示用户检索的关键词数目，ξ表示授权用户的数目;pr表示双线性运算，exp表示指数运算。下面分别从关键词加密运算量、搜索运算量、是否支持多用户、是否支持多服务器、是否支持对搜索结果验证以及是否支持授权用户撤销等方面与文献［13－15］方案展开比较。由于双线性运算的时间消耗要远高于指数运算，从表2可以看到，本文方案对关键词的加密只要(m+ξ+4)次指数运算，其余运算均由服务器来完成，故效率要高于其他方案。本文方案中可以提供多关键词的检索，因此检索的准确率要高于其他方案。另外，本文方案可以支持多用户和多服务器模型，可以极大提高检索效率;同时，可以对检索的结果提供有效的验证，对于已经完成检索任务的授权用户可以对他们的检索权限进行撤销，从而极大地提高了用户数据的安全性。

表2 不同方案效率对比Tab.2 Efficiency comparison of different schemes

5 结语

针对云环境中数据检索过程中所存在的伪造查询结果和密钥信息泄露问题，提出支持用户撤销的可验证密文检索方案，可以通过运用多个关键词对用户外包的密文数据进行精确检索查询，并能够对最终检索结果的完整性进行有效验证，有效防止了恶意服务器的不诚实操作。此外，该方案通过用户撤销机制可以防止不诚实授权用户的某些非法操作，从而保护了隐私数据的安全性。在下一步工作中，我们将尝试改进文中方案，使其拥有更高效的检索效率以及更灵活的搜索方式。