支持多关键字搜索的条件代理重加密

秦璐璐，周李京，王 敏

(河海大学计算机与信息学院,江苏 南京 211100)

0 引 言

云计算技术的快速发展极大地促进了互联网云服务的发展[1]，为了保护用户数据的隐私性，用户在云中存储的数据都是以加密的形式存在的。但是，云环境中存在着大量数据共享的情况。由于数据拥有者不完全信任云服务提供商，因此无法将用于解密密文的密钥发送到云端，并且再由云端来解密并分享出去。但是，如果数据所有者下载密文并对其进行解密，再用需要接收这些消息的用户的公钥加密并分享给这些用户，这无疑给数据所有者带来了很多麻烦，失去了云数据共享的意义。这个问题的一个很好的解决方案是使用代理重新加密。Blaze等人[2]在1998年首先提出了代理重加密(Proxy Re-Encryption, PRE)的概念，该技术可以实现云端密文数据的共享，而且是在不泄露数据所有者解密密钥的情况下。

在实际问题中，数据所有者并不希望接收数据的用户解密所有的密文，所以如果数据所有者可以选择由代理重新加密的密文，这当然是可取的。Weng等人[3]首次提出了条件代理重加密(Conditional Proxy Re-Encryption, CPRE)的概念，只有满足特定条件的密文才能被代理转化，对密文实现了细粒度委托。Fang等人[4]提出了一种新的、高效的、满足匿名条件的CPRE方案，这是Weng等人的遗留问题。随后，Weng等人[5]又提出了在不需要随机预言机的情况满足选择密文攻击(Chosen Cipher-text Attack， CCA)安全性的代理重加密。虽然双线性对是构建PRE方案的一个很重要的元素，但是它在资源受限的设备中实现的速度慢，所以文献[6-8]又提出了不使用双线性对的PRE方案。

Shao等人[9]在2010年首次提出了带关键字搜索的代理重加密(Proxy Re-Encryption with Keyword Search, PRES)的概念，将公钥加密与关键字搜索与代理重加密相结合，并证明该方案是安全的。但是，Shao等人的方案不能抵抗合谋攻击。Chen等人[10]在2011年指出Shao等人的方案是在牺牲计算效率的前提下提高了安全性的。2014年，Lee等人[11]改进了文献[10]中的PRES方案，并将它应用于存储外包环境中，虽然搜索速度有所提高，但方案的安全性却没有证明。Guo等人[12]构造了一个有效的单向PRE方案，不使用一次性强不可伪造签名，并证明该方案是CCA安全的。文献[13]提出了一种细粒度访问控制的PRES方案，以限制用户的权限，从而抵抗合谋攻击。文献[14]提出了一种新的可证明安全的PRES方案，证明了方案对适应性选择关键字攻击具有不可区分语义安全性，而且在计算效率上也有所提高。

在目前的PRES方案中，大多数方案都处理了一个关键字搜索的问题，在文献[15-17]中，虽然提出了在加密的数据中实现多个关键字搜索，但是计算代价实在是太高了。同时，大部分方案中的代理都能够转换授权者的所有的原始密文。在实际环境中，希望仅将满足特定条件的密文转化为受理者公钥加密的密文[18]。假设A是银行的负责人，现在仅想让B阅读具有关键字“紧急，重要”的邮件，让C阅读具有关键字“保险”的文件，但是在传统的代理重加密中做不到这一点。Wang等人[19]提出了一种带联合关键字搜索的有约束的代理重加密，但是计算效率很低。本文引入一种使用满足条件树构造的带多关键字搜索的条件代理重加密(Conditional Proxy Re-Encryption with Multi-keyword Search, CPRES)的方案，只有满足授权者指定条件的密文，才能由代理进一步处理，这种先搜索再重加密的构造更加符合实际环境，而且提高了计算效率。

1 预备知识

1.1 双线性映射

令G1和G2是具有素数阶p的乘法循环群，g1和g2是G1的生成元。e:G1×G1→G2是具有以下性质的双线性映射：

非退化性：e(g1,g2)≠1。

可计算性：对任意的g1,g2∈G1，存在高效的算法计算e(g1,g2)。

1.2 3-QDBDH假设

e:G1×G1→G2是一个双线性对，g是G1的生成元，x,y∈Zp。敌手B解决3-QDBDH问题的优势定义为：

1.3 满足访问树

设T是表示访问结构的树，树的每个非叶节点代表一个陷门[20]。如果numx是节点x的子节点数，kx是其陷门值，则kx∈(0,numx]。当kx=1时，陷门为或门，当kx=numx时，陷门为和门。为了便于使用访问树，定义函数att(x)，不过只有当x是叶节点并且表示与叶节点x相关联的条件时才定义[21]。以Tx表示根植于节点x的T的子树，如果一组关键字W满足访问树Tx，则将其表示为Tx(W)=1。递归地计算Tx(W)。如果x是一个非叶节点，则对节点x所有的子节点x′计算Tx′(W)，当且仅当至少kx个子节点返回1时，Tx(W)才返回1。如果x是叶节点，则当且仅当att(x)∈W时，Tx(W)才返回1。

2 支持多关键字搜索的条件代理重加密方案的定义及其构造

2.1 方案的定义

CPRES方案由如下7个多项式时间算法组成：

系统建立GlobSetup(1K)：输入安全参数1K，生成系统参数GlobSetup(1K)→param。

密钥生成KeyGen(1K)：系统为用户i生成公私钥对Keygen(param)→(pki,ski)。

条件重加密密钥生成ReKeyGen(ski,W,pkj)：输入发送方的私钥ski，条件关键字W和接收方的公钥pkj，生成条件重加密密钥ReKeyGen(ski,W,pkj)→rki→j。

陷门生成算法Trapdoor(ski,W)：由发送方i执行。输入私钥ski和条件关键字W，输出条件关键字W的陷门Trapdoor(ski,W)→Tw。

加密算法Enc(pki,W,m):输入用户i公钥pki，消息m∈M，条件关键字W，此算法生成原始密文Enc(pki,W,m)→Ci。

重加密算法ReEnc(Ci,rki→j)：输入重加密密钥rki→j和密文Ci，重加密算法ReEnc输出用公钥pkj加密的重加密密文Cj。

解密Dec(Cj,skj)：输入公钥pkj下的密文Cj和对应的私钥skj，输出消息m或⊥。

2.2 安全模型

支持多关键字搜索的条件代理重加密方案的选择密文安全性可通过敌手B和挑战者C之间的游戏来定义[22]：

系统建立：挑战者C模拟算法Globstepup(1K)，生成系统参数param并发送给敌手B。

第1阶段：敌手B可以询问C以下的预言机：

未攻陷密钥询问Opk：挑战者运行KeyGen(1K)获得(pk,sk)，但是只把pk返回给敌手。

攻陷密钥询问Osk：挑战者运行KeyGen(1K)获得(pk,sk)，把(pk,sk)返回给敌手B。

当进行重加密密钥Ork、重加密Ore、解密Odec询问时，要求输入的密钥都是在之前的Opk或者Osk中产生。

挑战阶段：当敌手决定结束阶段1，它输出2个等长的明文m0,m1∈M，条件关键字W和目标公钥pk*。限制是pk*由Opk生成，而且如果敌手以(pk*,pkj,W)询问Ork，则不能以pkj询问Osk。挑战者选择一个随机比特b∈{0,1}，设置C*=Enc(pk*,W,mb)返回给敌手。

第2阶段：和第1阶段相同，限制是如果敌手以(Ci,pk*,pkj,W)询问Ore，则pkj没有询问过Osk。而且敌手也不能对(Ci,pk*,W)做解密询问。

猜测：敌手B输出猜测b′∈{0,1}，若b′=b，则B赢得游戏。敌手B获胜的优势为Adv=|Pr [b=b′-1/2]|。

2.3 方案的具体描述

Globstepup(1K)：全局设置算法以安全参数1K作为输入，p是长度为K的参数，G1和G2是素数阶为p的循环群，g是G1中的生成元，e:G1×G1→G2是一个双线性映射。哈希函数H:{0,1}n→G1，其中n根据K确定，消息空间M={0,1}n。Sig=(G,S,V)是一个强大且不可伪造的一次性签名方案。最后输出系统全局参数param=(p,G1,G2,e,g,n,H,Sig)。

ReKeyGen(ski,W,pkj)：输入用户i的私钥ski、用户j的公钥pkj、条件关键字W，并输出重加密密钥rki→j=H(pkj1/ski,W)。

Trapdoor(ski,W)：根据输入，调用满足访问树进行陷门搜索，当且仅当TDw=1时，用户i将陷门TDw和条件重加密密钥rki→j发送给代理，否则返回。

Enc(pki,W,m)：输入用户i的公钥pki、条件关键字W和消息m∈M。

1)选择一对一次签名的公私钥对G(1K)→(svk,ssk)，并设置A=svk。

3)运行签名算法S(ssk,(C,D,E))，要签名的信息元组为(C,D,E)，签名结果表示成S。

4)输出密文Ci=(A,B,C,D,E,S)。

ReEnc(Ci,rki→j)：输入一个重加密密钥rki→j=H(pkj1/ski,W)和密文Ci=(A,B,C,D,S)。

1)首先执行以下步骤：

①运行V(A,(C,D,E),S)，以验证签名S是否是在公钥A下加密的消息(C,D,E)的签名。

②检查e(D,pki)=e(B,gA)。

③这些检查中任何一个失败，则输出0，否则输出1。

2)计算B′=e(g,g)r·w，输出一个新的密文Cj=(A,B′,C,D,E,S)。

Dec(skj,Cj)：重加密密文解密。输入私钥skj和密文Cj=(A,B′,C,D,E,S)，首先验证V(A,(C,D,E),S)=1和e(D,gw)=e(g,g)A·B′，如果这2个等式都为真，就输出m=C/B′1/w；若有一个等式不成立，就输出⊥。原始密文解密：输入私钥ski和密文Ci=(A,B,C,D,E,S)，输出m=C/e(B,g)1/ski。

3 方案分析

3.1 正确性分析

密文的正确性：

对于重加密密文Cj，C/B′1/w=e(g,g)r·m/e(g,g)r·w·1/w=m；

所以密文都是有效的。

3.2 安全性分析

在随机预言模型下将方案的安全性规约到3-QDBDH问题，证明支持多关键字搜索的条件代理重加密方案是满足选择密文攻击不可区分(Indistinguishability against Chosen Ciphertext Attack, IND-CCA)安全性的。

本文的密文不可区分性的证明是基于3-QDBDH困难性问题的。给定一个3-QDBDH实例(g,ga,ga2,ga3,gb)，然后将ga、gb分别嵌入到发送者的公钥pki和挑战密文C中，将敌手的优势规约到3-QDBDH困难性问题上，证明出该方案满足IND-CCA安全性。

3.3 性能分析

将本文提出的CPRES方案与文献[14]和文献[19]提出的2个有代表性的PRES方案进行比较。设Tp为一个双线性配对运算，Te为一个模指数运算，比较结果如表1所示。

表1 方案性能比较

对比内容文献[14]方案文献[19]方案本文方案加密2Tp+Te6TeTp+3Te重加密Tp+Te2Tp+Te2Tp+Te解密Tp2Tp+5Te2Tp+3Te困难假设HDHq-BDHI3-QDBDH安全性CKAWCCACCA

由表1可知，本文方案在计算代价上明显低于文献[19]方案，和文献[14]方案在计算代价上不相上下。但本文利用满足访问树实现了多关键字搜索，并且该方案是先搜索后重加密，也更具有实用性，因此本文的方案优于文献[14]和文献[19]的方案。

4 CPRES的应用

目前，对数据加密是保护数据隐私安全的一种重要的方法，但是只要一个数据集包括了敏感数据，这整个数据集都会被加密[23]。本文提出的CPRES方案对解决实际环境问题起着很大作用。比如在金融业中，不同职责的部门只能阅读关于自己职责所在的数据信息；在政府机关中，不同部门只能阅读需要处理的公文，这种先搜索后重加密的结构既保护了数据隐私，也提高了数据利用率。

5 结束语

本文介绍了支持多关键字搜索的代理重加密的概念，提出了一种特定的CPRES方案，并将其效率与以前的经典方案进行了比较。此外，还给出了CPRES在金融业等行业中的应用。但是支持多关键字搜索的代理重加密仍然有一些问题需要解决，例如设计不使用双线性对的CPRES方案和旨在证明在标准模型中安全的CPRES方案。