抗选择密文攻击的高效的条件代理重加密

摘要

最近，一种代理重加密的变体——条件代理重加密(C-PRE)被引入。与传统的代理重加密相比，C-PRE允许委托方实现解密权限的细粒度委托，在许多应用中更加实用。本文在仔细观察现有的C-PRE定义和安全概念的基础上，对C-PRE更严格的定义和安全概念进行了重新定义。我们进一步提出了一个更高效的C-PRE方案，并在随机预言模型的决策双线性Diffie-Hellman (DBDH)假设下证明了它的选择密文安全性。此外，我们指出最近的一个C-PRE方案无法实现选择密文的安全性。
关键词：条件代理重加密，选择密文安全，随机预言。

引言

1998年，Blaze, Bleumer和Strauss[1]引入了代理重加密(PRE)的概念。在PRE方案中，给代理一个重新加密的密钥，从而可以将Alice的公钥下的密文转换为Bob的公钥1下的密文。但是，代理无法了解使用这两个密钥加密的消息的任何信息。PRE被证明是一个有用的原语，它发现了许多需要授权解密权的应用程序，例如加密的电子邮件转发、安全的分布式文件系统和加密垃圾邮件的外包过滤。

然而，传统的PRE也存在一些难以解决的问题。例如，假设爱丽丝的一些第二级密文是高度机密的，她只希望自己能解密这些密文。不幸的是，传统的PRE使代理能够转换爱丽丝的所有第二级密文，而没有任何区别。为了解决这个问题，我们独立引入了两种PRE变体：一种是Tang[5]提出的基于类型的代理重加密(TB-PRE)，另一种是Weng等人[6]提出的条件代理重加密(C-PRE)。虽然命名不同，但C-PRE和TB-PRE在本质上是相同的(为了一致性，在本文的其余部分，我们使用C-PRE来表示这两种变体)。在这种系统中，密文是按照一定的条件生成的，只有满足相应的条件，代理才能对密文进行翻译。与传统的PRE相比，C-PRE可以使授权器实现解密权的细粒度授权，在许多应用中更加实用。

我们的动机和结果

我们首先研究了[6,5]中定义的C-PRE的定义和安全性概念。两者各有优缺点：

在Weng等人的定义中，代理需要两个密钥对（即部分重加密密钥和条件密钥）来进行转换，而Tang等人的定义中代理只有一个密钥对；
在Tang的定义中，委托者和被委托者必须处于不同的系统中，这意味着在一个给定的系统中，用户只能作为（而不是同时作为）委托者或被委托者。相比之下，在翁等人的定义中，一个用户可以是任何其他用户的委托者，也可以是任何其他用户的被委托者。
[5,6]中的两个安全概念都只考虑第二级密文的安全性，而不考虑第一级密文的安全性。

在本文中，我们结合[6,5]的优点，重新形式化了C-PRE的定义。更具体地说，在我们的形式化中，代理只持有一个用于执行转换的密钥(重新加密密钥)，用户可以充当任何其他用户的委托方或被委托方。我们还定义了C-PRE的第一级密文安全性。然后，我们提出了一个新的C-PRE方案，并在随机oracle模型中充分研究了决策双线性Diffie-Hellman (DBDH)假设下证明了它的CCA-security。我们的方案在计算和通信方面都比Tang和Weng等人的方案有更好的整体效率。此外，我们证明了Weng等人的C-PRE方案不能实现CCA-security。

条件代理重加密模型

在重新形式化C-PRE的定义和安全性概念之前，我们首先解释在本文其余部分中使用的一些符号。对于有限集S， $x\in_{R}S$ 意味着从S中选取一个均匀分布的元素x。对于字符串x， |x|表示其位长度。我们用 $A(x,y,···)$ 表示A是一个输入为 $(x,y,···)$ 的算法。通过 $z\leftarrow A(x,y,···)$ ，表示 $A(x,y,···)$ 运行，设z为输出。我们用 $A^{O_{1},O_{2},···}(x,y,···)$ 表示A是输入为 $(x,y,···)$ 的算法，可以访问预言机 $O_{1},O_{2},···$ 。通过 $z\leftarrow A^{O_{1},O_{2},···}(x,y,···)$ 表示 $A^{O_{1},O_{2},···}(x,y,···)$ 运行，设z为输出。

C-PRE系统的定义

Weng等人的定义区分了部分重加密密钥和条件密钥。一个更标准的模型应该将它们组合成一个完整的实体。在这方面，我们的定义是标准的，只有重新加密的密钥；我们允许委托者和被委托者共享相同的系统，这与唐的模型不同。形式上，C-PRE方案由以下算法组成：

$Setup(1^{k})$ ：当输入一个安全参数1^k时，该算法输出一个全局参数参数，其中包括消息空间m。为了简单起见，我们假设参数参数隐式包含在其他算法的输入中。
$KeyGen(1^{k})$ ：各方使用此随机密钥生成算法生成公钥/私钥对(pk_i, sk_i)。
$ReKeyGen(sk_{i}, w, pk_{j})$ ：输入委托方的私钥sk_i，条件w和被委托方的公钥pk_j，重加密密钥生成算法输出一个重加密密钥 $rk_{i\rightarrow j}$ 。
$Enc_{2}(pk,m,w)$ ：当输入公钥pk、明文 $m\in M$ 和条件w时，第二加密算法输出第二级密文CT，可以使用合适的重加密密钥将其重新加密为第一级密文（用于可能不同的接收方）。
$Enc_{1}(pk, m)$ ：在输入公钥pk和明文 $m\in M$ 时，第一个加密算法输出一个不能为另一方重加密的第一级密文CT。
$ReEnc(CT_{i}, rk_{i\rightarrow j})$ ：在公钥pk_i下输入与w相关联的第二级密文CT_i，再输入重加密密钥rk_i→j，该重加密算法通过代理运行，输出公钥pk_j下的第一级密文CT_j。
$Dec_{2}(CT,sk)$ ：在输入第二级密文CT和私钥sk时，该第二解密算法输出一条消息m或错误符号⊥。
$Dec_{1}(CT,sk)$ ：在输入第一级密文CT和私钥sk时，第一解密算法输出一条消息m或错误符号⊥。

C-PRE的正确性是指，对于任意条件w，任意 $m\in M$ ，任意一对私钥/公钥对(pk_i, sk_i)， (pk_j, sk_j)，均为

$Dec_{2}(Enc_{2}(pk_{i},m,w),sk_{i})=m$ ， $Dec_{1}(Enc_{1}(pk_{i},m,w),sk_{i})=m$ ，

$Dec_{1}(ReEnc(Enc_{2}(pk_{i},m,w),ReKeyGen(sk_{i},w,pk_{j})),sk_{j})=m$ 。

安全概念

在本节中，我们将定义C-PRE系统的安全概念。在给出这些安全概念之前，我们首先考虑以下的预言，它们共同模拟了对手的能力。这些神谕是挑战者C模拟运行C-PRE的环境提供给对手A的。

未损坏的密钥生成预言机 $O_{u}(i)$ ：C运行KeyGen算法生成公钥/私钥对(pk_i, sk_i)，并返回pk_i给a。
损坏密钥生成预言机Oc(i)：C运行KeyGen算法生成公钥/私钥对(pk_j, sk_j)，并返回(pk_j, sk_j)给a。
重加密密钥预言机O_rk(pk_i, w, pk_j)：挑战者C首先运行 $rk_{i\rightarrow j}\leftarrow ReKeyGen(sk_i, w, pk_j)$ ，然后返回 $rk_{i\rightarrow j}$ 到A。
重加密预言机O_re(pk_i, pk_j, (w, CT_i))：挑战者C先运行 $CT_{j}\leftarrow ReEnc(CT_i, rk_{i\rightarrow j})$ ，其中 $rk_{i\rightarrow j}=ReKeyGen(sk_i, w, pk_j)$ ，然后将CT_j返回给A。
第一级解密预言机O_1d(pk,CT)：这里CT是第一级密文。C运行Dec₁(CT, sk)，并将相应的结果返回给A。

注意，对于最后三个预言机，需要O_c或O_u预先生成pk_i、pk_j和pk。

现在我们可以定义C-PRE在特定密文攻击下的语义安全性。Libert和Vergnaud[4]区分了传统(单跳)单向PRE系统的两种语义安全:第一级密文安全和第二级密文安全。我们遵循Libert和Vergnaud的定义，为C-PREs定义了这两种安全概念。

二级密文安全。直观地说，第二级密文安全模拟了对手A面临的第二级密文CT^∗在目标公钥 $pk_{i^{∗}}$ 和目标条件w^∗下加密的场景。A可以向以上五个预言机发出一系列查询。这些查询是允许的，只要它们不允许A轻易地解密。例如，A不应该查询 $O_{rk}(pk_{i^{∗}},w^{∗},pk_{j})$ 来获得重新加密的密钥 $rk_{i^{∗}}\rightarrow j$ 当pk_j来自预言机O_c时。否则，A可以轻松地解密挑战密文，首先将其重新加密为第一级密文，然后用sk_j解密。

同样，A也不能查询 $O_{re}(pk_{i^{∗}},pk_{j},(w^{∗},CT^{∗}))$ 哪里的pk_j来自预言机O_c。同样，对于第一级密文 $CT'=ReEnc(CT^{*}，rk_{i^{*}\rightarrow j})$ ，不允许A在 $O_{1d}(pk_{j},CT')$ 上进行查询。有人可能会想，为什么我们不为A提供第二级解密预言机呢？事实上，为对手A显式地提供这个预言机是没有用的，因为

对于挑战密文CT^∗，显然不允许A请求第二级解密预言机来解密它；
对于公钥pk_t和条件w加密的任何其他第二级密文CT_t， $(pk_{t},w,CT_{t})\ne (pk_{i^{*}},w^{∗},CT^{*})$ ，对手A可以首先发出重加密查询 $O_{re}(pk_{t},pk_{j},(w,CT_{t}))$ 来获得第一级密文CT_j，然后发出第一级解密查询 $O_{1d}(pk_{j},CT_{j})$ 来获得底层明文。下面给出了自适应选择密文攻击(IND-2CPRE-CCA)下第二级密文的语义安全的形式化定义。

定义1。对于一个C-PRE方案 $\varepsilon$ 和一个概率多项式时间对手A，分两个阶段求和猜，我们定义A对 $\varepsilon$ 的IND-2CPRE-CCA安全性的优势为：

其中st是对手A的一些内部状态信息，这里要求|m₀| = |m₁|，同时满足以下条件：

pki*是由预言机Ou生成的；
对于预言机O_c生成的公钥pk_j，A不能发出 $O_{rk}(pk_{i^{*}},w^{*},pk_j)$ 查询；
对于预言机O_c生成的公钥pk_j，A不能发出查询 $O_{re}(pk_{i^{*}},pk_{j},(w^{*},CT^{*}))$ ；
对于公钥pk_j和第一级密文 $CT'=ReEnc(CT'，rk_{i^{*}\rightarrow j})$ ， A不能发出查询 $O_{1d}(pk_{j},CT')$ 。

我们将对手A称为IND-2CPRE-CCA对手。一个C-PRE方案 $\epsilon$ 被认为是 $(t,q_u,q_c,q_{rk},q_{re},q_{1d},\epsilon)-IND-2CPRE-CCA$ 安全的，如果对于任意t-time的IND-2CPRE-CCA对手A，它分别对O_u, O_c, O_rk, O_re和O_1d进行最多的q_u, q_c, q_rk, q_re和q_d查询，我们有 $Adv^{IND-2CPRE-CCA}_{\varepsilon,A}(1^{k})\leq \epsilon$ 。

第一级密文安全。上述定义为对手提供了挑战阶段的第二级密文。接下来，通过在挑战阶段向对手提供第一级密文，我们定义了一个安全的补充定义(表示为IND-1CPRE-CCA)。注意，由于第一级密文不能在单跳C-PRE方案中被重新加密，所以允许A获得任何重新加密密钥。此外，有了这些重加密密钥，A就可以自己重新加密密文，因此不需要为他提供重加密预言机O_re。如前所述，第二级解密预言机也是不必要的。

定义2。对于一个C-PRE方案 $\varepsilon$ 和一个概率多项式时间对手A，分两个阶段求和猜，我们定义A对 $\varepsilon$ 的IND-1CPRE-CCA安全性的优势为：

其中st是对手A的一些内部状态信息，这里要求|m₀| = |m₁|， $pk_{i^{*}}$ 是由O_u生成的，并且A不能发出查询 $O_{1d}(pk_{i^{*}},CT^{*})$ 。

我们将上述对手A称为IND-1CPRE-CCA对手。我们说一个C-PRE方案E是 $(t, q_u, q_c, q_{rk}, q_{1d}, \epsilon)-IND-1CPRE-CCA$ 安全的，如果对任意t-time的IND-1CPRE-CCA对手A分别对O_rk, O_c, O_rk和O_1d进行最多的q_u, q_c, q_rk和q_d查询，我们有 $Adv^{IND-1CPRE-CCA}_{\varepsilon,A}(1^{k})\leq \epsilon$ 。

Remark。在[2]中，Ateniese等人定义了主秘密安全的概念，用于单向代理重新加密。这个安全概念抓住了这样一种直觉:即使不诚实的代理与被委托方勾结，它们仍然不可能派生出被委托方的私钥。注意，对于C-PREs，不需要定义主秘密安全性，因为这种安全性是由第一级密文安全性隐含的。这是因为，如果不诚实的代理和被委托方可以合谋获得被委托方的私钥，那么他们当然可以使用这个私钥来解密挑战密文，从而打破第一级密文安全性。

所提的CCA安全的C-PRE方案

在本节中，我们提出了一种具有cca安全性的新的C-PRE方案。在提出我们的方案之前，我们列出了三个设计cca安全C-PRE方案的重要和必要的原则：

第二级密文的有效性应该是公开可验证的；否则，将遭受类似[11,19]所示的攻击；
第二级密文应当能够抵御对手的恶意操纵；
对手也不可能恶意操纵第一级密文。我们注意到设计一个满足这三个要求的C-PRE方案是非常重要的，尤其是最后一个要求。为了帮助理解我们的方案，我们首先提出了一个不安全的尝试，然后对其进行改进，以获得我们最终的CCA安全方案。

第一次尝试

我们表示S1的第一次尝试，具体如下：

$Setup(1^{k})$ ：输入一个安全参数，设置算法首先确定 $(q,G,G_{T},e)$ ，其中q是一个k-bit素数，G和 $G_{T}$ 是素数阶为q的两个循环组，e是双线性配对 $e: G\times G \rightarrow G_{T}$ 。接下来，它选择 $g\in_{R}G$ ，以及5个哈希函数H₁、H₂、H₃、H₄和H₅使 $H_{1}:{0,1}^{*}\rightarrow Z_{q}$ ， $H2:\{0,1\}^{*}\rightarrow G$ ， $H_{3}:G\rightarrow \{0,1\}^{n}$ ， $H_{4}:\{0,1\}^{*}\rightarrow G$ 和 $H_{5}:G \rightarrow Z_{q}$ ，其中n是多项式，处于k中，消息空间为 $M=\{0,1\}^{n}$ 。全局参数是 $param=((q,G,G_{T},e),g,n,H_{1},...,H_{5})$ 。
$KeyGen(1^{k})$ ：为生成用户U_i的公钥/私钥对，取 $x_{i}\in_{R}Z_{q}$ 设公钥和私钥分别为 $pk_{i}=g^{x_{i}}$ 和 $sk_{i}=x_{i}$ 。
$ReKeyGen(sk_{i},w,pk_{j})$ ：输入私钥 $sk_{i}$ ，条件w，公钥 $pk_{j}$ ，该算法随机选取 $s\in_{R}Z_{q}$ ，输出重加密密钥为 $rk_{i\rightarrow j}=(rk_{1}, rk_{2})=\left( (H_{2}(pk_{i},w)pk_{j}^{s})^{-sk_{i}},pk_{i}^{s} \right)$ 。
$Enc_{2}(pk,m,w)$ ：在输入公钥pk、条件w和消息 $m\in M$ 时，发送方首先选取 $R\in_{R}G_{T}$ 。然后他计算出 $r=H_{1}(m,R)$ ，输出第二级密文 $CT=(C_{1},C_{2},C_{3},C_{4})$ 为 $(g^{r},R\cdot e(pk,H_{2}(pk,w))^{r},m\oplus H_{3}(R),H_{4}(C_{1},C_{2},C_{3})^{r})$ 。请注意，最后一个密文组件C₄用于确保密文的公共可验证性，而前三个组件 $(C_1,C_2,C_3)$ 实际上是应用Fujisaki-Okamoto转换[21]的CCA安全ElGamal加密方案[20]的密文。
$Enc_{1}(pk, m)$ ：输入公钥pk和消息 $m\in M$ 时，发送方首先选取 $R\in_RG_T$ 和 $s\in_RZ^{*}_{q}$ ，然后计算出 $r=H_1(m,R)$ ，输出第一级密文CT为 $CT=(\bar{C_{1}},\bar{C_{2}},\bar{C_{3}},\bar{C_{4}})=(g^{r},R\cdot e(g,pk)^{-r\cdot \bar{s}},m\oplus H_{3}(R), g^{\bar{s}})$ 。
$ReEnc(CT_{i},rk_{i\rightarrow j})$ ：在公钥pk_i下输入与条件w相关联的第二级密文 $CT_{i}=(C_1, C_2, C_3, C_4)$ ，再输入重加密密钥 $rk_{i\rightarrow j}=(rk_1,rk_2)$ ，生成公钥pk_j下的第一级密文，如下所示，检查以下等式是否成立： $e(C_1, H_4(C_1, C_2, C_3))=e(g,C_4)$ 。如果不是，则输出 $\bot$ ；其他输出 $CT_{j}=(C_1,C_2,C_3,C_4)$ ，其中 $\bar{C_1}=C_1,\bar{C_2}=C_{2}\cdot e(C_1,rk_1),\bar{C_3}=C_{3},\bar{C_4}=rk_{2}$ 。观察 $CT_{j}=(C_1,C_2, C_3, C_4)$ 确实是以下形式： $\bar{C_1}=g^{r}$ ， $\bar{C_3}=m\oplus H_3(R)$ ， $\bar{C_{4}}=pk_i^s =g^{s\cdot sk_i}$ ， $\bar{C_{2}}=R\cdot e(pk_i,H_{2}(pk_{i},w))^{r}\cdot e(g^{r},(H_2(pk_i, w)pk_{j}^{s})^{-sk_i})=R\cdot e (g, pk_{j})^{-r\cdot s\cdot sk_{i}}$ 。

令 $\bar{s}=s\cdot sk_i$ ，可以看出上述第一级密文与Eq具有相同的形式。

$Dec_{2}(CT, sk)$ ：当输入私钥sk和第二级密文 $CT=(C_1, C_2, C_3, C_4)$ 时，首先检查Eq.(4)是否成立。如果不是，它是⊥。否则，它计算R，检查 $g^{H_{1}(m,R)}=C_{1}$ 是否保持。如果是，返回m；否则是⊥。
$Dec_{1}(CT, sk)$ ：在公钥pk下输入私钥sk和第一级密文 $CT=(\bar{C_1}, \bar{C_2}, \bar{C_3}, \bar{C_4})$ ，计算出 $R=\bar{C_2}\cdot e(\bar{C_{1}}, \bar{C_{4}})^{sk}$ 和 $m=\bar{C_3}\oplus H_{3}(R)$ 。如果 $g^{H_{1}(m,R)}=\bar{C_{1}}$ 成立则返回m，否则返回⊥。

分析。乍一看，方案S1似乎是CCA安全的。不幸的是，这是不正确的，因为对手可以恶意操作第一级密文，以获得一个新的有效的密文。具体来说，给定第一级密文如式(3)，对手可以选取 $l\in_RZ_q$ ，产生另一个第一级密文 $CT'=(\bar{C_{1}}', \bar{C_{2}}', \bar{C_{3}}', \bar{C_{4}}')$ ，使：

$\bar{C_{1}}'=\bar{C_{1}}=g^{r}$ ， $\bar{C_2}'=\bar{C_2} \cdot e(\bar{C_1}, pk)^{-l}=R \cdot e(g,pk)^{−r·(\bar{s}+l)}$ ，

$\bar{C_{3}}'=\bar{C_{3}}=m_{\delta} \oplus H_{3}(R)$ ， $\bar{C_{4}}'=\bar{C_{4}} \cdot g^{l} = g^{\bar{s}+l}$ 。

令 $\bar{s}='\bar{s}+l$ ，我们可以很容易地看到，CT'是另一个新的有效密文，如Eq.(3)。因此，可以很容易地打破CCA安全性。

抗选择密文攻击的C-PRE方案

实际上，S1的不安全性在于重新加密密钥的构造，即rk₂与rk₁是松散集成的。这使对手能够恶意地操纵产生的第一级密文，并获得另一个有效的第一级密文。因此，为了设计一个CCA安全的C-PRE方案，我们应该仔细设计重新加密的密钥，这样得到的第一级密文就不会被对手恶意操纵。基于此，我们提出了CCA安全的C-PRE方案（用S2表示），如下所示：

$Setup(1^{k}),KeyGen(1^{k})$ ：和S1的相同。
$ReKeyGen(sk_i, w, pk_j)$ ：输入一个私钥 $sk_{i}$ ，条件w，公钥 $pk_{j}$ ，该算法取 $s\in_R Z_{q}$ ，输出 $rk_{i\rightarrow j}=(rk_{1}, rk_{2})$ 为 $rk_{2}=pk_{i}^{s}$ ， $rk_{1}=\left( H_{2}(pk_{i},w)pk_{j}^{s\cdot H_{5}(pk_{j}^{s\cdot sk_{i}})} \right)^{-sk_{i}}$ 。可以看到，在重新加密密钥rk_i→j中，rk₂现在与rk₁无缝集成。也就是说，我们通过在rk₁中嵌入 $H_{5}(pk_{j}^{s.sk_{i}})=H_{5}(rk_{2}^{sk_{j}})$ 来对rk₂和rk₁进行积分。这是方案S2实现CCA安全性的一个重要技巧。
$Enc_{2}(pk,m,w)$ ：和S1的一致。
$Enc_{1}(pk,w)$ ：输入公钥pk和消息 $m\in M$ 时，发送方首先选取 $R\in_{R}G_{T}$ 和 $\bar{s}\in_{R}Z^{*}_{q}$ ，然后计算出 $r=H_{1}(m,R)$ ，输出第一级密文 $CT=(\bar{C_1},\bar{C_2},\bar{C_3},\bar{C_4})$ 为 $(g^{r},R\cdot e(g,pk)^{-r\cdot \bar{s} \cdot H_{5}(pk^{\bar{s}})},m \oplus H_{3}(R), g^{\bar{s}})$ 。
$ReEnc(CT_{i},rk_{i\rightarrow j})$ ：和S1一样。注意，由于重加密密钥与S1中的重加密密钥不同，因此得到的第一级密文 $CT_{j}=(\bar{C_{1}},\bar{C_{2}},\bar{C_{3}},\bar{C_{4}})$ 的形式如下： $(g^{r},R\cdot e(g,pk_{j})^{-r\cdot s \cdot sk_{i} \cdot H_{5}(pk_{j}^{s\cdot sk_{i}})}, m\oplus H_{3}(R), g^{s\cdot sk_{i}})$ ，式中 $r=H_{1}(m, R)$ ， $R\in_{R} G_T$ 。令 $\bar{s}=s·sk_i$ ，可以看出上述第一级密文的形式与式(6)相同。

还需要注意的是，现在 $\bar{C_4}$ 通过将 $\bar{C_4}$ 嵌入 $H_5(\bar{C}^{sk_{j}}_{4})=H_{5}(pk_{j}^{s\cdot sk_{i}})$ 而与 $\bar{C_2}$ 紧密结合，因此对手无法修改第一级密文以获得新的有效密文。因此，对方案S1的攻击不适用于方案S2。

$Dec_{2}(CT, sk)$ ：和S1中的相同。
$Dec_{1}(CT, sk)$ ：该算法在公钥pk下输入私钥sk和第一级密文 $CT=(\bar{C_1}, \bar{C_2}, \bar{C_3}, \bar{C_4})$ 时，首先计算出 $R=\bar{C_2}\cdot e(\bar{C_1}, \bar{C_4})^{sk \cdot H_{5}(\bar{C}^{sk}_{4})}$ 和 $m=\bar{C_3}\oplus H_{3}(R)$ 。接下来，如果 $g^{H_{1}(m,R)}=\bar{C_{1}}$ 是可信的，则返回m；否则，返回 $\bot$ 。

安全分析

我们的方案S2的CCA安全性是基于一个称为决策双线性Diffie-Hellman（DBDH）的复杂度假设。组(G, G_T)中的DBDH问题是，给定一个元组 $(g, g^a, g^b, g^c, Z)\in G^{4} \times G_T$ ， $a,b,c\in_{R}Z_{q}$ 未知，决定是否满足 $Z=e(g, g)^{abc}$ 。多项式时间算法B在求解组(G, G_T)的DBDH问题上具有优势 $\epsilon$ ，如果 $Pr|B(g, g^a, g^b, g^c, Z=e(g, g)^{abc}=1]-Pr[B(g, g^a, g^b, g^c, Z=e(g, g)^d)=1]| \geq \epsilon$

概率由Z_q中的a, b, c, d的随机选择，G中的g的随机选择，以及B所消耗的随机比特组成。

定义3。我们说 $(t,\epsilon)-DBDH$ 假设在组(G, G_T)中成立，如果不存在在(G, GT)中求解DBDH问题具有优势 $\epsilon$ 的t-time算法B。

对于我们方案的第二级CCA安全性，我们有如下定理，其详细证明可以在附录B中找到。

定理1。我们的方案S2在随机预言模型中是IND-2CPRE-CCA安全的，假设DBDH假设在组(G, G_T)中保持。更具体地说，如果存在一个IND-2CPRE-CCA对手A，它最多向 $i\in \{1,···,5\}$ 的H_i请求q_Hi随机预言查询，并打破方案S2的 $(t, q_u, q_c, q_{rk}, q_{re}, q_d, \epsilon )-IND-2CPRE-CCA$ 安全性，则存在一个算法B，可以打破组(G, G_T)中的 $(t',\epsilon')-DBDH$ 假设。

其中 $\tau$ 是计算G、G_T的指数所需时间和计算配对所需时间的最大值；e表示自然对数的底。

S2的第一级密文安全性由以下定理保证。

定理2。我们的方案S2在随机预言模型中是IND-1CPRE-CCA安全的，假设DBDH假设在组(G, G_T)中成立。更具体地说，如果存在一个IND-1CPRE-CCA对手A，它最多向H_i请求 $i\in \{1,...,5\}$ 的 $q_{H_{i}}$ 随机预言查询，并且能够打破S2方案的 $(t, q_u, q_c, q_{rk}, q_d, \epsilon)-IND-1CPRE-CCA$ 安全性，那么就存在一个算法B，可以用，打破组(G, G_T)中的 $(t',\epsilon')-DBDH$ 假设。

其中 $\tau$ 和 $e$ 与定理1中的含义相同

定理2的证明与定理1相似，只是做了一些修改。例如，对随机预言H₂的模拟不再需要投掷有偏差的硬币，而对预言O_rk的模拟必须成功地回答所有重加密密钥查询而不中止。由于篇幅的限制，我们在全文中给出了详细的证明。

比较

在表1中，我们将我们的方案与Tang的方案[5]、Weng等人的方案[6]和Livert-Vergnaud的方案[10]进行了比较。我们首先解释表1中使用的一些符号。其中|M|、|G|、|G_T|、|svk|、|σ|分别表示明文的比特长、组G和组G_T中的一个元素、一次性签名的验证密钥和签名。我们用t_p、t_e、t_s、t_v分别表示双线性配对、求幂、签名和验证一次性签名的计算代价。l1为Weng等人方案中使用的安全参数。

Tang的方案需要一个额外的公钥加密方案PKE，假设该方案是确定性的、单向的4。在这里，我们使用 $t_{Enc_{PKE}}$ 和 $t_{Dec_{PKE}}$ 表示Tang方案中使用的公钥加密(PKE)方案中一次加密和一次解密的计算成本。对于|C_PKE|，表示Tang方案中使用的方案PKE的密文长度。
比较结果表明，我们的方案S2在计算开销和通信开销方面都优于Tang方案。我们的方案比Weng等人的方案具有更好的综合性能：Weng等人的方案在第一级加解密的密文长度和计算量上领先我们的方案，而我们的方案在其他指标上优于他们的方案；最重要的是，我们的方案是CCA安全的，而他们的失败了。我们的方案也比Libert-Vergnaud的方案有更好的整体性能。此外，我们的方案在充分研究的DBDH假设下是CCA-安全的，而Libert-Vergnaud方案在研究较少的3-弱决策双线性Diffie-Hellman反演(3-wDBDH)假设下只满足RCCA-安全（这是CCA-安全的一个较弱变体，假设可以容忍挑战密文被无害地破坏）。但是，与Tang和Weng等人的方案一样，我们的方案存在安全性依赖于已知秘钥模型中的随机预言的局限性，而Libert-Vergnaud的方案在选择秘钥模型中可以不使用随机预言进行证明。

结论

我们重新形式化了条件代理重加密(C-PRE)的定义和安全概念，并在我们的模型下提出了一个有效的CCA-安全的C-PRE方案。另外，我们对Weng等人的C-PRE方案进行了攻击，表明其无法实现CCA-security。
这项工作激发了一些有趣的开放性问题。一个是如何在没有随机的预言机的情况下构建一个CCA-secure（而不是RCCA-secure）的C-PRE方案。另一个是如何构建CCA安全的C-PRE方案，在条件上支持“或”和“与”门。