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

最近，一种代理重加密的变体——条件代理重加密(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。

Mambo和Okamoto[7]首先引入了授权解密权的概念，作为对密文先解密再加密这种简单方法的性能更好的替代方案。Blaze, Bleumer和Strauss[1]将代理重加密的概念形式化，并提出了第一个双向PRE方案(Alice对Bob的委托同时允许Bob对Alice的重加密)。2005年，Ateniese等人[2,3]提出了基于双线性对的单向PRE方案。

文中的方案[1,2,3]只对选择明文攻击（CPA）是安全的。然而，应用程序经常需要cca安全性。在ACM CCS ' 07中，Canetti和Hohenberger[8]提出了一个基于双线性对的CCA安全的双向PRE方案。随后，Libert和Vergnaud[4]提出了一种抗可重放选择密文攻击(RCCA)的单向预方案[9]。在他们的扩展版本中，Libert和Vergnaud[10]进一步考虑了条件代理重加密的问题，并在标准模型中提出了一个RCCA安全的C-PRE方案，而不需要假设注册的公钥。

以前的PRE方案依赖于昂贵的双线性配对。因此，Canetti和Hohenberger[8]留下了一个没有配对的cca安全PRE的开放性问题。在CANS’08中，Deng等人[11]提出了一种cca安全的双向无配对PRE方案。在PKC ' 09中，Shao和Cao[12]提出了一个没有配对的单向PRE方案，并声称他们的方案是cca安全的。然而，Weng等人[13]指出，Shao和Cao的PRE方案通过给出具体的攻击而不是CCA安全。Weng等人在[13]的基础上进一步提出了一种高效的CCA安全的无配对的单向PRE方案。

由Libert和Vergnaud[14]引入的可跟踪代理重新加密，试图通过跟踪已经公开了重新加密密钥的代理来解决这个问题。代理重加密在基于身份的场景中也有研究，如[15,16,17]。最近，Chu等[18]提出了一种C-PRE的通用版本，命名为条件代理广播重加密(CPBRE)，该代理可以一次为一组用户重新加密密文。

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

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

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

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

，，

。

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

• 未损坏的密钥生成预言机：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首先运行，然后返回到A。
• 重加密预言机O_re(pk_i, pk_j, (w, CT_i))：挑战者C先运行，其中，然后将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^∗在目标公钥和目标条件w^∗下加密的场景。A可以向以上五个预言机发出一系列查询。这些查询是允许的，只要它们不允许A轻易地解密。例如，A不应该查询来获得重新加密的密钥当pk_j来自预言机O_c时。否则，A可以轻松地解密挑战密文，首先将其重新加密为第一级密文，然后用sk_j解密。

同样，A也不能查询哪里的pk_j来自预言机O_c。同样，对于第一级密文，不允许A在上进行查询。有人可能会想，为什么我们不为A提供第二级解密预言机呢？事实上，为对手A显式地提供这个预言机是没有用的，因为

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

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

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

• pki*是由预言机Ou生成的；
• 对于预言机O_c生成的公钥pk_j，A不能发出查询；
• 对于预言机O_c生成的公钥pk_j，A不能发出查询；
• 对于公钥pk_j和第一级密文， A不能发出查询。

我们将对手A称为IND-2CPRE-CCA对手。一个C-PRE方案被认为是安全的，如果对于任意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查询，我们有。

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

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

其中st是对手A的一些内部状态信息，这里要求|m₀| = |m₁|，是由O_u生成的，并且A不能发出查询。

我们将上述对手A称为IND-1CPRE-CCA对手。我们说一个C-PRE方案E是安全的，如果对任意t-time的IND-1CPRE-CCA对手A分别对O_rk, O_c, O_rk和O_1d进行最多的q_u, q_c, q_rk和q_d查询，我们有。

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

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

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

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

• ：输入一个安全参数，设置算法首先确定，其中q是一个k-bit素数，G和是素数阶为q的两个循环组，e是双线性配对。接下来，它选择，以及5个哈希函数H₁、H₂、H₃、H₄和H₅使，，，和，其中n是多项式，处于k中，消息空间为。全局参数是。
• ：为生成用户U_i的公钥/私钥对，取设公钥和私钥分别为和。
• ：输入私钥，条件w，公钥，该算法随机选取，输出重加密密钥为。
• ：在输入公钥pk、条件w和消息时，发送方首先选取。然后他计算出，输出第二级密文为。请注意，最后一个密文组件C₄用于确保密文的公共可验证性，而前三个组件实际上是应用Fujisaki-Okamoto转换[21]的CCA安全ElGamal加密方案[20]的密文。
• ：输入公钥pk和消息时，发送方首先选取和，然后计算出，输出第一级密文CT为。
• ：在公钥pk_i下输入与条件w相关联的第二级密文，再输入重加密密钥，生成公钥pk_j下的第一级密文，如下所示，检查以下等式是否成立：。如果不是，则输出；其他输出，其中。观察确实是以下形式：，，，。

令，可以看出上述第一级密文与Eq具有相同的形式。

• ：当输入私钥sk和第二级密文时，首先检查Eq.(4)是否成立。如果不是，它是⊥。否则，它计算R，检查是否保持。如果是，返回m；否则是⊥。
• ：在公钥pk下输入私钥sk和第一级密文，计算出和。如果成立则返回m，否则返回⊥。
  

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

，，

，。

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

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

• ：和S1的相同。
• ：输入一个私钥，条件w，公钥，该算法取，输出为，。可以看到，在重新加密密钥rk_i→j中，rk₂现在与rk₁无缝集成。也就是说，我们通过在rk₁中嵌入来对rk₂和rk₁进行积分。这是方案S2实现CCA安全性的一个重要技巧。
• ：和S1的一致。
• ：输入公钥pk和消息时，发送方首先选取和，然后计算出，输出第一级密文为。
• ：和S1一样。注意，由于重加密密钥与S1中的重加密密钥不同，因此得到的第一级密文的形式如下：，式中，。令，可以看出上述第一级密文的形式与式(6)相同。
  

还需要注意的是，现在通过将嵌入而与紧密结合，因此对手无法修改第一级密文以获得新的有效密文。因此，对方案S1的攻击不适用于方案S2。

• ：和S1中的相同。
• ：该算法在公钥pk下输入私钥sk和第一级密文时，首先计算出和。接下来，如果是可信的，则返回m；否则，返回。

我们的方案S2的CCA安全性是基于一个称为决策双线性Diffie-Hellman（DBDH）的复杂度假设。组(G, G_T)中的DBDH问题是，给定一个元组，未知，决定是否满足。多项式时间算法B在求解组(G, G_T)的DBDH问题上具有优势，如果

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

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

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

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

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

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

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

其中和与定理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。在这里，我们使用和表示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方案，在条件上支持“或”和“与”门。