具源隐藏特性的IB-PRE方案分析*

郑郁林 蔡沂

（1.华南理工大学 计算机科学与工程学院， 广东 广州510640； 2.华南理工大学广州学院 计算机工程学院， 广东 广州510800）

代理重加密由Blaze 等［1］提出，近年来已成为密码学研究的一个热点领域，业界提出了多种方案［2-9］.在基于身份标识的代理重加密方案（IB-PRE）［10］中，源密文使用委托者身份标识加密，代理负责将源密文转换为目标密文，目标密文使用被委托者的身份标识相应的密钥解密.随后，出现了多种IB-PRE方案［11-23］.Emura 等［22］提出了具有源隐藏特性的基于身份标识的代理重加密方案（Emura-IB-PRE 方案），要求经过重加密后的目标密文没有泄漏关于源身份的任何信息.源隐藏特性试图避免从一个目标密文泄漏信息源的身份，解决以往所有IB-PRE 方案中的信息泄漏问题，即一个源密文是否是一个目标密文的源的相关信息被泄漏的问题.需要注意的是，源隐藏特性与匿名性［23］（密文不能泄露相应的ID）和密钥保密［6］（重加密密钥不泄漏源或目的密钥）是不同的.

代理重加密模式在电子邮件系统中具有广泛的应用［10，24-27］.源隐藏特性增强了隐私保护，在商业应用中具有很高的价值.它可以被应用于邮件列表系统中，保护用户是否属于某个邮件列表的信息.对企业而言，其顾客邮件列表的成员被泄露，将可能造成严重的损失.

Emura-IB-PRE 方案的基础是Boneh-Franklin IBE 方案［28］，满足源隐藏特性，但违反了一级密文可公开验证原则，不能抵抗选择密文攻击.为此，文中提出了一种攻破该方案的选择密文安全性的方法，在此基础上提出了E-SH-IB-PRE 方案，并进行相关安全性证明.

1 Emura-IB-PRE 方案分析

1.1 源隐藏特性

Emura 等［22］提出了源隐藏特性概念，目的是为了保护源密文与目的密文的关系，经过重加密后源密文与目的密文的关系将不能被识别，即使一个攻击者知道一个邮件列表的地址（包括该邮件列表的成员地址），也不能确定一个源密文（使用邮件列表地址加密的）是否是一个目的密文（使用个人邮件地址加密的）的源；并对此概念作了形式化描述，给出基于身份标识的代理重加密方案（IB-PRE）的选择密文安全性（IND-ID-CCA）和源隐藏安全性（IND-SH-ID-CCA）定义.

定义1［22］一个单向单跳的IB-PRE 方案由以下算法组成：

●Setup（k） 输入安全参数k，返回一个主密钥msk 和一组公共参数列表params；

●KeyGen（msk，IDi） 给定用户i 的身份标识IDi，返回用户i 的私钥ski；

●Encrypt（IDi，m） 给定IDi和明文消息m，返回使用IDi加密的密文Ci；

●Decrypt（ski，Ci） 输入一个给用户i 的密文Ci和私钥ski，输出明文m 或者无意义数⊥；

●RKGen（ski，IDi，IDj）给定用户i的身份标识IDi和私钥ski以及用户j 的身份标识IDj，输出一个单向的重加密密钥rki→j；

●Re-Encrypt（Ci，rki→j） 输入一个给用户i 的一级密文Ci和一个单向的重加密密钥rki→j，输出用户j 可解密的一个重加密密文Cj或者无意义数⊥.

定义2（IND-ID-CCA）［22］如果一个有多项式能力的敌手A 在IND-ID-CCA 攻击游戏中，对于一个加密方案∏IB-PRE所具有的优势可忽略，则称该加密方案在语义上具有自适应抗选择密文攻击安全性.

∏IB-PRE的IND-ID-CCA 攻击游戏协议如下.

1）在系统建立阶段，挑战者获取安全参数k，运行Setup 算法，产生公共参数列表params 和主密钥msk，将params 传给A，保留主密钥msk.

在第1 阶段， 敌手A 可随意签发查询q1，q2，…，qm访问以下谕示机，获得输出结果，即

●私钥提取谕示机OEXT（IDi） 给定用户i 的身份标识IDi，运行KeyGen 算法，产生用户i 的私钥ski.

●重加密密钥提取谕示机ORE-EXT（IDi，IDj） 给定用户i 的身份标识IDi和用户j 的身份标识IDj，运行RKGen 算法，产生一个单向的代理重加密密钥rki→j.

●重加密谕示机ORE-ENC（IDi，IDj，Ci） 给定用户i的身份标识IDi和密文Ci、用户j 的身份标识IDj，运行Re-Encrypt 算法，使用代理重加密密钥rki→j将密文Ci转化为重加密密文Cj.

●解密谕示机ODEC（IDi，Ci） 给定用户i 的身份标识IDi和密文Ci，运行Decrypt 算法，使用用户i 的私钥ski解密密文Ci，返回明文m 或者无意义数⊥.

2）在挑战阶段，敌手A 决定第1 阶段结束时，就在未被询问过私钥的用户中挑选一个用户ID*，输出两个等长的明文（m0，m1），挑战者挑选一个随机比特b∈{0，1}，计算挑战密文C*←Encrypt（mb，ID*），然后发送C*给A.

在第2 阶段，敌手A 可以随意签发查询qm+1，qm+2，…，qn访问以下谕示机，获得输出结果，即

●OEXT（IDi） IDi≠ID*，如果不存在挑战衍生（IDi，Ci），那么挑战者的响应与第1 阶段相同.挑战衍生定义如下［9］：①（IDi，Ci）是其自身的挑战衍生；②如果（IDi，Ci）是一个挑战衍生，A已发出查询ORE-ENC（IDi，IDj，Ci），收到一个新的密文Cj，则（IDj，Cj）是一个挑战衍生；③如果（IDi，Ci）是一个挑战衍生，A 已发出重加密密钥查询ORE-EXT（IDi，IDj），获得 重加密密钥rki→j，令Cj=Re-Encrypt（Ci，rki→j），那么（IDj，Cj）是一个挑战衍生.

●ORE-ENC（IDi，IDj，Ci） 除非A 已查询OEXT（IDj），且（IDi，Ci）是挑战衍生，否则挑战者的响应与第1阶段相同.

●ORE-EXT（IDi，IDj） 除非A 已查询OEXT（IDj），且存在挑战衍生（IDi，Ci），否则挑战者的响应与第1 阶段相同.

●ODEC（IDi，Ci） 如果（IDi，Ci）不是挑战衍生，则挑战者的响应与第1 阶段相同.

3）在猜测阶段，A 输出一个猜测比特b′∈{0，1}，如果b′=b，则A 获胜.

定义3（IND-SH-ID-CCA）［22］如果一个有多项式能力的敌手A 在IND-SH-ID-CCA 攻击游戏中，对一个加密方案∏SH-IB-PRE所具有的优势可忽略，则称该加密方案在语义上具有自适应选择密文攻击源隐藏安全性.

IND-SH-ID-CCA 攻击游戏协议与IND-ID-CCA攻击游戏协议类似，但A 不管在第1 阶段还是第2阶段，都可以不受任何限制地访问OEXT、ORE-ENC、ORE-EXT和ODEC谕示机.

在挑战阶段，敌手A 决定第1 阶段结束时，就挑选两个源密文的用户身份标识（ID*0，ID*1）、挑战用户身份标识ID*和一个挑战明文m*， 计算C*0←Encrypt（m*，ID*0）和C*1←Encrypt（m*，ID*1），挑战者挑选一个随机比特b∈{0，1}，计算挑战重加密密文后发送C*给A.

在猜测阶段，A 输出一个猜测比特b'∈{0，1}，如果b'=b，则A 获胜.

Emura 的安全模型是一个自适应模型，相比于非自适应模型［3-4］，敌手可以随机确定欲攻击的目标用户，攻击能力更强［8］，该模型下CCA 安全的方案更具有吸引力.

定义4（DBDH 假设） 令（G1，GT）是一个双线性群组，P 是G1的一个产生元，e 是一个双线性配对，则〈G1，GT，e〉上的DBDH 问题是指：给定（P，Pa，Pb，Pc，w），a，b，c∈RZ*q未知，判断如果一个概率性多项式时间算法求解的DBDH 问题的优势可以忽略不计，则称该DBDH 假设成立.

1.2 Emura-IB-PRE 方案

下面介绍具有源隐藏特性的CCA 安全IB-PRE方案［22］.

●Setup（k） 选择一个k 位的素数q，令G1和GT分别是两个q 阶加法循环群和乘法循环群，且存在e：G1×G1→GT为双线性映射，g为群G1的生成元.随机选择s∈RZ*q，输出主密钥msk=s 和params=

（g，gs，{Hi}5

i=1），这里Hi为哈希函数，分别定义为H1：

{0，1}*→G1，H2：{0，1}*→G1，H3：{0，1}*→G1，H4：GT×{0，1}n→Z*q，H5：GT→{0，1}n，明文空间为M：{0，1}n.

●KeyGen（msk，IDi） 给定用户i 的身份标识IDi∈{0，1}*，输出ski=H1（IDi）s.

●Encrypt（IDi，m） 为使用标识IDi加密明文消息m，发送者随机选择σ∈RGT，令r=H4（σ，m），计算C1←gr，C2←σ·e（gs，H1（IDi）r），C3←m⊕H5（σ），输出密文C=（C1，C2，C3）.

●RKGen（ski，IDi，IDj） 随机选择X1∈RGT，X2∈R{0，1}n，令r'=H4（X1，X2），计算R1←gr'，R2←X1·e（gs，H1（IDj）r'），R3←X2⊕H5（X1），R4←H2（X2）·ski，输 出

rki→j=（R1，R2，R3，R4）.

●Re-Encrypt（rki→j，Ci） 给定一个第1 层密文Ci=（C1，C2，C3）和rki→j=（R1，R2，R3，R4），计算第2 层密文Cj：选择X'1，X'2∈RGT，令t=H4（C3，R3），t'=H4（X'1，C3），s'=H4（X'1，X'2） 和s''=H4（X'2，R3），计算C'1←C1·gt，C'2←C2·e（gs，H1（IDi）t）/e（C'1，R4），C'3←C3⊕H5（X'1），C'4←gt'，C'5←X'1·e（gs，H1（IDj）t'），C'6←gs''，C'7←X'2·e（g，H1（IDj）s''），R'1←R1·gs'，R'2←R2·e（gs，H1（IDj）s'），R'3←R3⊕H5（X'2），S'1←H3（C'1，C'2）t，S'2←H3（R'1，R'2）s'；输出Cj=（C'1，C'2，…，C'7，S'1，S'2，R'1，R'2，R'3）.

●Decrypt（ski，Ci） 令Ci为一个l（l∈{1，2}）级密文，算法执行过程如下.

✧当l=1 时，Ci表示为（C1，C2，C3），计算σ←C2/e（C1，ski）和m←C3⊕H5（σ），检查C1？= gr，这 里r=H4（σ，m）.如果检查通过，则输出m，否则输出⊥.

✧当l=2 时，Ci表示为（C'1，C'2，…，C'7，S'1，S'2，R'1，R'2，R'3），给定ski=H1（IDi）s，解密密文：

1）计算X'1←C'5/e（C'4，ski），C3←C'3⊕H5（X'1），t'=H4（X'1，C3），并检验C'4

？=gt'；

2）计算X'2←C'7/e（C'6，ski），R3←R'2⊕H5（X'2），s''=H4（X'2，R3），并检验C'6

？=gs''；

3）计算s'←H4（X1'，X'2），检验计算X1←R'2/e（R'1，ski），X2←R3⊕H5（X1），r'←H4（X1，X2），检查

5）计算t=H4（C3，R3），检验，计算σ←C'2·e（C'1，H2（X2）），m←C3⊕H5（σ）和r←H4（σ，m），检查

6）如果所有的检查通过，则输出m，否则输出⊥.

1.3 Emura-IB-PRE 方案的安全性分析

对Emura-IB-PRE 的攻击方案如下：

2）在第1 阶段，敌手A 签发提取查询OEXT（ID'），获取ID'对应的解密密钥skID'=H1（ID'）s.

3）在挑战阶段，A 输出两个长度相同的明文m0，m1∈M 和对应的ID*，然后获得挑战密文C*←Encrypt（mb，ID*），C*=（C*1，C*2，C*3），其格式为C*=（gr，σ·e（gs，H1（ID*）r），mb⊕H5（σ）），r=H4（σ，mb）.

4）在第2 阶段，

（a）A 选择长度等于m0的m'∈M， 令C'=（C'1，C'2，C'3）=（C*1，C*2，m'⊕C*3），即C'=（gr，σ·e（gs，H1（ID*）r），m'⊕mb⊕H5（σ））.

（b）A 签发重加密查询ORE-ENC（ID*，ID'，C'），获得重加密密文C''=（C''1，C''2，…，C''7，S''1，S''2，R''1，R''2，R''3）.根据安全模型，A 查询C' 的重加密密文是合法的，因为虽然A 掌握了ID' 的解密密钥，但该模型只禁止对挑战密文进行重加密查询.

（c）A 已知skID'=H1（ID'）s，计算X'1←C''5/e（C''4，skID'），t'=H4（X'1，C''3），X'2←C''7/e（C''6，skID'），R3←R''3⊕H5（X'2），X1←R''2/e（R''1，skID'），X2←R3⊕H5（X1），mb←C3⊕H5（σ）.注意这里使用C3替代C'3.

这样，不检查条件成立与否，敌手A 获得mb，攻破Emura-IB-PRE 方案的选择密文安全性.分析Emura的证明过程，发现在处理解密被篡改的重加密密文的请求时，其模拟过程调用了BE 解密谕示机解密C'，得到⊥，此时Emura-IB-PRE 解密谕示机无法给出m，模拟失败.这一情况在原文献［22］中被忽略了.

2 改进方案E-SH-IB-PRE

Emura-IB-PRE 方案中重加密代理无法验证密文，导致攻击者可构造特别密文C'，欺骗重加密代理将C'进行重加密，得到攻击者拥有私钥的ID'的重加密密文C''，从而使用ID'的私钥skID'解密重加密密文C''.针对这一问题，文中通过为密文增加可公开验证的信息来保证密文不被修改.E-SH-IB-PRE方案有如下定义.

●Setup（k） 选择一个k 位的大素数q，令G1和GT分别是两个q 阶加法循环群和乘法循环群，且存在e：G1×G1→GT为双线性映射，g 为群G1的生成元.随机选择s∈RZ*q，计算gs，令主密钥msk=s.选择随机散列函数H1：{0，1}*→G1，H2：{0，1}*→G1，H3：{0，1}*→G1，H4：GT×{0，1}n→Z*q，H5：GT→{0，1}n和H6：{0，1}*→G1，输出.明文空间为M：{0，1}n.

●KeyGen（msk，IDi） 给定用户i 的身份标识IDi∈{0，1}*，输出ski=H1（IDi）s.

●Encrypt（IDi，m） 为了使用用户i 的身份标识IDi加密一个明文消息m∈M，发送者随机选择σ∈RGT，令r=H4（σ，m），计算C1←gr，C2←σ·e（gs，H1（IDi）r），C3←m⊕H5（σ）；令u=H6（C1||C2||C3），计算C4←ur，输出密文C=（C1，C2，C3，C4）.

●RKGen（ski，IDi，IDj） 选择X1∈RGT，X2∈R{0，1}n，令r'=H4（X1，X2），计算R1←gr'，R2←X1·e（gs，H1（IDj）r'），R3←X2⊕H5（X1），R4←H2（X2）·ski，输出rki→j=（R1，R2，R3，R4）.

●Re-Encrypt（rki→j，Ci） 给定一级密文Ci=（C1，C2，C3，C4）和重加密密钥rki→j=（R1，R2，R3，R4），通过以下方法计算重加密密文Cj：

1）计算u=H6（C1||C2||C3），检查e（C1，u）？=e（g，C4），如果检查不通过，则输出⊥.

2）选择X'1，X'2∈RGT，令t=H4（C3，R3），t'=H4（X'1，C3），s'=H4（X'1，X'2）和s''=H4（X'2，R3），计算C'1←C1·gt，C'2←C2·e（gs，H1（IDi）t）/e（C'1，R4），C'3←C3⊕H5（X'1），C'4←gt'，C'5←X'1·e（gs，H1（IDj）t'），C'6←gs''，C'7←X'2·e（g，H1（IDj）s''），R'3←R3⊕H5（X'2），R'1←R1·gs'，R'2←R2·e（gs，H1（IDj）s'），X'2←H3（C'1，C'2）t，S'2←H3（R'1，R'2）s'，输出Cj=（C'1，C'2…，C'7，S'1，S'2，R'1，R'2，R'3）.

●Decrypt（ski，Ci） 令Ci为一个l（l∈{1，2}）级密文，算法执行过程如下.

✧当l=1 时，Ci=（C1，C2，C3，C4），检查e（C1，u）？=e（g，C4），这里u=H6（C1||C2||C3），如果检查不通过，则输出⊥.计算σ←C2/e（C1，ski）和m←C3⊕H5（σ），输出m.这里的检验方法与Emura-IB-PRE 方案不同，避免解密的是重加密密钥中的（R1，R2，R3）.

✧当l=2 时，Ci=（C'1，C'2…，C'7，S'1，S'2，R'1，R'2，R'3），ski=H1（IDi）s，解密密文：

1）计 算X'1←C'5/e（C'4，ski），C3←C'3⊕H5（X'1），t'=H4（X'1，C3），并检验C'4

？=gt'；

2）计算X'2←C'7/e（C'6，ski），R3←R'3⊕H5（X'2），s''=H4（X2'，R3），并检验

3）计算s'←H4（X'1，X'2），检验计算X1←R'1/e（R'1，ski），X2←R3⊕H5（X1），r'←H4（X1，X2），检 查

4）计算t=H4（C3，R3），检验计算σ←C'2·e（C'1，H2（X2）），m←C3⊕H5（σ），r←H4（σ，m），检查

5）如果所有的检查通过，则输出m，否则输出⊥.

正确性验证对于源密文，以下等式成立：

C2/e（C1，ski）=σ·e（gs，H1（IDi）r）/e（gr，H1（IDi）s）=σ，C3⊕H5（σ）=m⊕H5（σ）⊕H5（σ）=m.

对于Cj的重加密密文Ci，以下等式成立：

安全性分析文中分析了E-SH-IB-PRE 方案的安全性，给出以下两个定理，其详细证明参见附录.

定理1在DBDH 假设成立的条件下，E-SHIB-PRE 方案在随机谕示模型下是IND-ID-CCA 安全的.

定理2E-SH-IB-PRE 方案在信息论意义下是IND-SH-ID-CCA 安全的.

3 结论

文中分析了Emura-IB-PRE 方案的缺陷，提出了具体的攻击方法，并证明了该方案不能抵抗选择密文攻击.在此基础上，文中提出了改进的方案E-SHIB-PRE，该方案在随机谕示模型下具有抗选择密文攻击安全性和源隐藏特性.

Emura-IB-PRE 方案违反一级密文可公开验证原则，该原则是对代理重加密方案的普遍性要求.如果代理重加密方案没有满足该要求，则可对其进行随机化密文重放攻击，攻破方案的选择密文安全性.此攻击实例表明，一级密文可公开验证的原则对代理重加密方案设计具有重要的作用.

附录 安全性证明

Emura-IB-PRE方案的公钥加密部分是以IBE 方案［28］为基础的，将C2的计算方法改为C2←σ·e（gs，H1（IDi）r）.文中首先给出基础IBE 方案，并证明其IND-CCA 安全性，然后将敌手对改进方案的攻击归约为对基础IBE 方案的IND-CCA安全性攻击.

1）基础IBE 方案的定义和安全性证明

定义5［28］基于身份标识的公钥加密方案（IBE）方案由以下4 个算法组成：

●Setup（k） 输入安全参数k，返回一个主密钥msk 和一组公共参数列表params；

●KeyGen（msk，IDi） 给定用户i 的身份标识IDi，返回一个用户i 的私钥ski；

●Encrypt（IDi，m） 给定IDi和明文消息m，返回使用IDi加密的密文Ci；

●Decrypt （ski，Ci） 输入一个给用户i 的密文Ci和私钥ski，输出明文m 或者无意义数⊥.

定义6［28］如果一个有多项式能力的敌手A 在如下的攻击游戏中，对于一个IBE 方案所具有的优势是可以忽略的，则称该加密方案具有选择密文语义安全性（IND-CCA）.

在系统建立阶段，挑战者获取安全参数k，运行Setup 算法，产生公共参数列表params 和主密钥msk，将公共参数列表params 传给A，保留主密钥msk.

在第1 阶段，敌手A 可随意签发以下查询q1，q2，…，qm，获得输出结果：

●Extract（IDi） 给定用户i的身份标识IDi，运 行KeyGen 算法，产生用户i 的私钥ski.

●Decrypt（IDi，Ci） 给定用户i 的身份标识IDi和密文Ci，运行Decrypt 算法，使用用户i 的私钥ski解密密文Ci，返回m←Decrypt（ski，Ci）.

在挑战阶段，一旦敌手A 决定第1 阶段结束，就在未被问过私钥的ID 中挑选一个ID*，输出两个等长的明文（m0，m1），挑战者随机挑选比特b∈{0，1}，计算C*←Encrypt（ID*，mb），然后发送C*给A.

在第2 阶段，敌手A 可随意签发以下查询qm+1，qm+2，…，qn，获得输出结果：

●Extract（IDi） IDi≠ID*，B 的响应同第1 阶段.

●Decrypt（IDi，Ci）如果（IDi，Ci）不是挑战密文，则B 的响应同第1 阶段.

在猜测阶段，A 输出一个猜测比特b'∈{0，1}，如果b'=b，则A 获胜.

一个攻击者在上述攻击协议中获得的优势为

定义7基于Boneh 方案的基础IBE 方案如下：

●Setup（k） 选择k 位的素数q，令G1和GT分别是两个q 阶加法循环群和乘法循环群，g为群G1的生成元，e：G1×G1→GT为双线性映射.随机选择s∈Z*q，令msk=s.选择散列函 数H1：{0，1}*→G1，H4：GT×{0，1}n→Z*q，H5：GT→{0，1}n，输出公共参数（g，gs，H1，H4，H5）.明文空间为M：{0，1}n.

●KeyGen（msk，IDi） 给定用户i 的身份标识IDi∈{0，1}*，输出ski=H1（IDi）s.

●Encrypt（IDi，m） 为了使用IDi加密明文消息m，发送者随机选择σ∈RGT，令r=H4（σ，m），计算C1←gr，C2←σ·e（gs，H1（IDi）r），C3←m⊕H5（σ），输出密文C=（C1，C2，C3）.

●Decrypt（ski，Ci） 令密文为（C1，C2，C3），计算σ←C2/e（C1，ski）和m←C3⊕H5（σ），检查，这里r=H4（σ，m）.如果检查通过，则输出m，否则输出⊥.

下面证明基础IBE 方案在DBDH 假设和随机模型下满足IND-CCA 安全性.

证明构造一个算法B，通过能以不可忽略的概率ε 打破基础IBE 方案的IND-CCA 安全性的敌手A 来解决BDH判定性问题.

在系统建立阶段，输入BDH 判定性问题的一个实例（P，Pa，Pb，Pc，w），算法B 输出参数（P，Pa，H1，H4，H5），H1和H4为B 控制的随机谕示机.

●H1（IDi） 如果（IDi，Hi，xi，ci）已在H1中存在，则返回Hi，否则B 投掷加权硬币以概率δ 设置ci=0，随机选择xi∈RZ*q.如果ci=0，令Hi=Pxi，否则令Hi=Pbxi.B 纪录相应的值到H1中.

●H4（σ，m） 随机选择ri∈RZ*q，记录（ri，σi，mi）到H4中，返回ri.

在第1 阶段，敌手A 可随意签发以下查询，获得输出结果，B 的响应如下：

●Extract（IDi） B 调用H1（IDi），如果ci=1，则终止模拟，返回失败；否则输出ski=Paxi.

●Decrypt （IDi，Ci） 设Ci=（C1，C2，C3），B 在H4中查找满足C1=Pri的（ri，σi，mi），返回mi.

在挑战阶段，A发送挑战消息（m0，m1，ID*）到B.B 调用H1（ID*），如果ci*=0，那么B 输出一个随机位后中止；否则，挑战者挑选一个随机比特b∈{0，1}，随机选择σ∈RGT，返回C*=（Pc，σ·wxi*，mb⊕H5（σ））给A.

在第2 阶段，敌手A 可以随意签发以下查询，获得输出结果，B 的响应如下：

●Extract（IDi） 如果IDi=ID*，则返回⊥；否则B 的响应同第1 阶段.

●Decrypt（IDi，Ci） 如果（IDi，Ci）是挑战密文，则返回⊥；否则B 的响应同第1 阶段.

在猜测阶段，当A 输出b′∈{0，1}时，如果b′=b，则B 输出1，否则输出0.

若B 在模拟过程中不退出，在构造挑战密文时令r=c，则正确加密情况下C*1=gr=Pc，C*2=σ·e（gs，H1（IDi）r）=σ·e（Pa，Pcbxi）=σ·e（P，P）abcxi，即当w=e（P，P）abc时，C*是mb在ID*下的正确加密，否则C*是一个随机值的加密.故当A 给出b'=b 时，B 输出1，反之输出0.

设qE是A 发出的查询数目，则在第1 或者第2 阶段，B不中止的概率为δqE.此外，B 在挑战阶段没有中止的概率为1-δ.因此B 没有中止的概率为δqE（1－δ），此值在δ=1－1/（qE+1）时最大化.因此，B 的优势至少是ε/ln（qE+1）.

2）E-SH-IB-PRE 方案的安全性证明

定理3E-SH-IB-PRE 方案在随机谕示模型下是IND-ID-CCA 安全的.

证明构造一个算法B，通过能以不可忽略的概率ε 打破E-SH-IB-PRE 方案的IND-ID-CCA 安全性的敌手A 来打破基础IBE的IND-CCA安全性.B维护一个rk 表（α，IDi，IDj，rki→j），以决定B 是否返回伪造的密钥.设* 是B 管理的表中的通配符，C 是基础IBE 实验中的挑战者.算法B 构造如下：

在系统建立阶段，C 发送（g，gs，H1，H4，H5）给B，B 添加H2、H3、H6，并转发给A，其中H6为B 控制的随机谕示机.

●H6（C1||C2||C3） 随机选择si∈RZ*q，记录（si，C1||C2||C3）到H6表，返回gsi.

在第1 阶段，敌手A 可以随意签发查询q1，q2，…，qm访问以下谕示机，获得输出结果，B 的响应如下.

●OEXT（IDi） B 投掷加权硬币以概率δ 设置α=1.如果α=0，或者（0，IDi，*，*）或（0，*，IDj，*）已在表rk 中存在，则B输出一个随机位后中止；否则，B 签发基础IBE 游戏中定义的Extract（IDi）获得ski，在表rk 中记录（1，IDi，IDj，⊥），并返回ski给A.

●ORE-EXT（IDi，IDj） B 以概率δ 设置α=1.如果α=1，或者（1，IDi，IDi，*）或（1，IDj，IDj，*）已在 表rk 中存在，则B 签发Extract（IDi），获得ski，然后计算rki→j←RKGen（ski，IDi，IDj），返回rki→j给A，记录（1，IDi，IDj，rki→j）；否则，B 返回一个伪造的重加密密钥rki→j，即

（i）选择X1∈RGT，X2∈R{0，1}n，令r'=H4（X1，X2），计 算R1←gr'，R2←X1·e（gs，H1（IDj）r'），R3←X2⊕H5（X1）；

（ii）选择x∈RG1，令R4=x，x 可表示为H1（IDi）s·y，其中y∈G1为一个未知量，一个能够区分无效重加密密钥的敌手在仿真中也可判断（R1，R2，R3）有无加密值Y，这里Y∈GT，且H2（Y）=y.

（iii）B 输出rki→j=（R1，R2，R3，R4），在表rk 中记录（0，IDi，IDj，rki→j）.

●ORE-ENC（IDi，IDj，Ci） 计算u=H6（C1||C2||C3），检查e（g，C4），如果检查不通过，则输出⊥.如果（*，IDi，IDj，*）没在表中，则B 执行ORE-EXT（IDi，IDj）后计算Re-Encrypt（rki→j，Ci）.

●ODEC（IDi，Ci） 如果Ci=（C1，C2，C3，C4）是一个第1 层密文，B 签发基础IBE 实验中定义的Decrypt（IDi，（C1，C2，C3）），则获得m 或⊥，返回给A.

如果Ci是有效的第2 层密文，则A 应该通过以下3 种方法获得：

（1）A签发ORE-EXT（*，IDi），获得重加密密钥rk*→i，并运行Re-Encrypt 算法；

（2）A 签发ORE-ENC（*，IDi，C*），获得重加密的二级密文；

（3）A签发OEXT（ID*）得到sk*，运行RKGen 算法，获得rk*→i后执行Re-Encrypt 算法.

在第（1）、（2）种情形下，表rk 中存在（*，*，IDi，rk*→i）.若（1，*，IDi，rk*→i）在表中，则B 获得ski（由Extract（IDi）获得），使用ski解密Ci，返回明文m；否则，如果表中存在（0，*，IDi，rk*→i），则B 通过如下步骤返回m：

1）B 签发Decrypt（IDi，（C'4，C'5，C'3）），获得C3或者⊥.

2）B 签发Decrypt（IDi，（C'6，C'7，R'3）），获得R3或者⊥.

3）B 计算t=H4（C3，R3），检验，然后计算C1=C'1·g－t.

4）对于表rk 中所有的（0，IDj，IDi，rkj→i），B 执行以下过程直到m 解出来或者没有剩余的表项.

（a）设rkj→i=（0，*，*，x），则计算C2←C'2·e（C'1，x）.

（b）B 签发Decrypt（IDj，（C1，C2，C3））并获得m 或者⊥.

5）如果所有检查的条件成立，结果也没有返回⊥，那么B 返回m 给A，否则B 返回⊥.

在第（3）种情况下，表中存在（1，ID*，ID*，⊥），则B 使用skID*解密，返回明文.

在挑战阶段，A 发送挑战消息（m0，m1，ID*）到B.如果表中存在（1，ID*，*，*），那么B 输出一个随机位后中止；否则，B发送（m0，m1，ID*）到C 作为挑战消息，并由C 获得（C*1，C*2，C*3），然后执行H6（C*1||C*2||C*3），计算C*4←（C*1）si*，将挑战密文C*=（C*1，C*2，C*3，C*4）返回给A.

在第2 阶段，敌手A 可以随意签发查询，访问以下谕示机，获得输出结果，B 的响应如下.

●OEXT（IDi） IDi≠ID*，如果存在挑战衍生（IDi，Ci），则返回⊥，否则B 的响应同第1 阶段.

●ORE-EXT（IDi，IDj） 若IDi=ID*，则B 伪造一随机重加密密钥，记录（0，IDi，IDj，rki→j）到表中.若A已查询IDj的私钥，且存在挑战衍生（IDi，Ci），则返回⊥，否则B 的响应同第1 阶段.

●ORE-ENC（IDi，IDj，Ci） 若A 已查询IDj的私钥，且（IDi，Ci）是挑战衍生，则返回⊥，否则B 的响应同第1 阶段.

●ODEC（IDi，Ci） 如果（IDi，Ci）是挑战衍生，则返回⊥，否则B 的响应同第1 阶段.

在猜测阶段，当A 返回猜测位b'时，B 输出b'.

B 在模拟过程中对一些用户私钥是未知的(即α=0 的情况），但如果B 在模拟过程中不中止，那么从A 看来，他是无法发现这种情况的.因此，若A 在不区分无效重加密密钥情况下能够获得正确的猜测位，则B 能攻破基础IBE 实验.

若A 能区分伪造的重加密密钥（R1，R2，R3，x），其对应正确的重加密密钥应为（R1，R2，R3，R4），其中（R1，R2，R3）实际上是使用IDi对X2进行加密，即（R1，R2，R3）←Encypti（X2），R4=H2（X2）·ski.令x=H2（Y）·ski，Y∈GT，则A 能够判断从而赢得基础IBE 的IND-CCA 攻击游戏，攻破基础IBE.

因此，只要估计B 没有中止的概率，即可给出敌手的优势.设qE是A 发出的查询数目，则在第1 或者第2 阶段B 以概率δqE不中止，且B 在挑战阶段没有中止的概率为1-δ.因此B 没有中止的概率为δqE（1－δ），此值在δ=1－1/（qE+1）时最大化.因此，B 的优势至少是ε/ln（qE+1）.

定理4E-SH-IB-PRE 方案在信息论意义下是IND-SHID-CCA 安全的.

使用Emura 等［22］的方法可以证明定理2 是成立的.

证明令源 密文Ci=（C1，C2，C3，C4），C1=gr，C2=σ·e（gs，H1（IDi）r），C3=m⊕H5（σ），C4=（H6（C1||C2||C3））r，重加密密钥rki→j=（R1，R2，R3，R4），R1=gr'，R2=X1·e（gs，H1（IDj）r'），R3=X2⊕H5（X1），R4=H2（X2）·ski，则重加密密文Cj=（C'1，C'2，…，C'7，S'1，S'2，R'1，R'2，R'3），其中，C'1=gr+t，C'2=σ/e（gr+t，H2（X2）），C'3=m⊕H5（σ）⊕H5（X'1），C'4=gt'，C'5=X'1·e（gs，H1（IDj）t'），C'6=gs''，C'7=X'2·e（g，H1（IDj）s''），R'1←gr'+s'，R'2=X1·e（gs，H1（IDj）r'+s'），R'3=X2⊕H5（X1）⊕H5（X'2），S'1=H3（C'1，C'2）t，S'2←H3（R'1，R'2)s'，t、t'、s'、s" 和X'1、X'2都是随机值.明显地，目的密文Cj中不包括源身份IDi，故定理显然是满足的.没有源密文直接包括在目的密文中，即方案中使用一个随机值t、t'、s'、s" 来随机化源密文Ci的一部分，使得对于目的密文Cj，任何一个一级密文Ci都有可能是它的源密文.

［1］Blaze M，Bleumer G，Strauss M.Divertible protocols and atomic proxy cryptography［C］//Advances in Cryptology：EUROCRYPT’98.Berlin/Heidelberg：Springer-Verlag，1998：127-144.

［2］Ateniese Giuseppe，Fu Kevin，Green Matthew，et al.Improved proxy re-encryption schemes with applications to secure distributed storage ［J］.ACM Transactions on Information and System Security，2006，9（1）：1-30.

［3］Canetti R，Hohenberger S.Chosen-ciphertext secure proxy re-encryption ［C］//Proceedings of the 14th ACM Conference on Computer and Communications Security.Alexandria：ACM，2007：185-194.

［4］Libert Benoit，Vergnaud Damien.Unidirectional chosenciphertext secure proxy re-encryption ［J］.IEEE Transactions on Information Theory，2011，57（3）：1786-1802.

［5］Deng R H，Weng J，Liu S，et al.Chosen-ciphertext secure proxy re-encryption without pairings ［C］//Proceedings of Cryptology and Network Security.Berlin/Heidelberg：Springer-Verlag，2008：1-17.

［6］Ateniese Giuseppe，Benson Karyn，Hohenberger Susan.Keyprivate proxy re-encryption ［C］//Proceedings of the Cryptographers’ Track at the RSA Conference 2009.Berlin/Heidelberg：Springer，2009：279-294.

［7］Matsuda Toshihide，Nishimaki Ryo，Tanaka Keisuke.CCA proxy re-encryption without bilinear maps in the standard model ［C］//Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography.Berlin/Heidelberg：Springer，2010：261-278.

［8］Weng J，Chen M R，Yang Y，et al.CCA-secure unidirectional proxy re-encryption in the adaptive corruption model without random oracles ［J］.Science China：Information Science，2010，53（3）：593-606.

［9］Weng J，Deng R H，Ding X H，et al.Conditional proxy reencryption secure against chosen ciphertext attack ［C］//Proceedings of the 4th International Symposium on Information，Computer，and Communications Security.New York：ACM，2009：322-332.

［10］Green M，Ateniese G.Identity-based proxy re-encryption［C］//Proceedings of the Applied Cryptography and Network Security.Berlin/Heidelberg：Springer-Verlag，2007：288-306.

［11］Chu C-K，Tzeng W-G.Identity-based proxy re-encryption without random oracles［M］//Information Security.Berlin/Heidelberg：Springer-Verlag，2007：189-202.

［12］Hu X，Chen X，Huang S.Fully secure identity based proxy re-encryption schemes in the standard model ［C］//Proceedings of the International Conference on Computer Science and Information Technology.Singapore：IEEE，2008：53-57.

［13］Ibraimi L，Tang Q，Hartel P H，et al.A type-and-identitybased proxy re-encryption scheme and its application in healthcare ［C］//Proceedings of the Secure Data Management.Berlin/Heidelberg：Springer-Verlag，2008：185-198.

［14］Lai J Z，Zhu W T，Deng R H，et al.New constructions for identity-based unidirectional proxy re-encryption ［J］.Journal of Computer Science and Technology，2010，25（4）：793-806.

［15］Matsuo T.Proxy re-encryption systems for identity-based encryption［C］//Proceedings of Pairing 2007.Berlin/Heidelberg：Springer，2007：247-267.

［16］Wang Lihua，Wang Licheng，Mambo M，et al.New identity-based proxy re-encryption schemes to prevent collusion attacks ［C］//Proceedings of Pairing 2010.Berlin/Heidelberg：Springer，2010：327-346.

［17］Shao J，Cao Z.Multi-use unidirectional identity-based proxy re-encryption from hierarchical identity-based encryption［J］.Information Sciences，2012，206（23）：83-95.

［18］Wang H，Cao Z，Wang L.Multi-use and unidirectional identity-based proxy re-encryption schemes ［J］.Information Sciences，2010，180（20）：4042-4059.

［19］Shao J，Wei G，Ling Y，et al.Identity-based conditional proxy re-encryption ［C］//Proceedings of 2011 IEEE International Conference on Communications.Kyoto：IEEE，2011：1-5.

［20］Wang Lihua，Wang Licheng，Manbo M，et al.Identitybased proxy cryptosystems with revocability and hierarchical confidentialities ［J］.EICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2012，E95-A（1）：70-88.

［21］Liang Kaitai，Liu Zhen，Tan Xiao，et al.A CCA-secure identity-based conditional proxy re-encryption without random oracles［C］//Proceedings of the 15th International Conference on Information Security and Cryptology.Seoul：Springer，2013：231-246.

［22］Emura K，Miyaji A，Omote K.An identity-based proxy re-encryption scheme with source hiding property，and its application to a mailing-list system ［C］//Proceedings of the Public Key Infrastructures，Services and Applications.Berlin/Heidelberg：Springer-Verlag，2011：77-92.

［23］Shao J.Anonymous ID-based proxy re-encryption ［C］//Proceedings of the 17th International Conference on Information Security and Privacy.Wollongong：Springer，2012：364-377.

［24］Bobba R，Muggli J，Pant M，et al.Usable secure mailing lists with untrusted servers ［C］//Proceedings of the 8th Symposium on Identity and Trust on the Internet.New York：ACM，2009：103-116.

［25］Khurana H，Hahm H S.Certified mailing lists ［C］//Proceedings of the 2006 ACM Symposium on Information,Computer and Communications Security.New York：ACM，2006：46-58.

［26］Khurana H，Slagell A J，Bonilla R.SELS：a secure e-mail list service ［C］//Proceedings of the 2005 ACM Symposium on Applied Computing.New York：ACM，2005：306-313.

［27］Khurana H，Heo J，Pant M.From proxy encryption primitives to a deployable secure-mailing-list solution［C］//Proceedings of Information and Communications Security.Berlin/Heidelberg：Springer，2006：260-281.

［28］Boneh D，Franklin M.Identity-based encryption from the weil pairing ［C］//Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology.Santa Barbara：Springer，2001：213-229.