《使用关键字搜索的代理重加密》文章阅读

我们引入了一种新的密码原语，称为带关键字搜索的代理重加密，这是受电子邮件系统中的以下场景的启发：

Charlie在Alice的公钥下向Alice发送一封加密的电子邮件，其中包含一些关键字，如“urgent”，Alice通过她的邮件服务器将她的解密权限委托给Bob。期望的情况是：
（1）Bob可以仅通过使用他的私钥来解密Alice委托的邮件；
（2）Bob的邮件网关，带有来自Bob的活板门，可以测试从Alice委托的电子邮件是否包含一些关键字，例如“紧急”；

（3）Alice和Bob不希望给予邮件服务器或邮件网关对电子邮件内容的访问权。
带关键字搜索的代理重加密（PRES）的功能是代理重加密（PRE）和带关键字搜索的公钥加密（PEKS）的结合。然而，PRES方案不能通过直接组合这两个方案来获得，因为所得到的方案在我们的安全模型中不再被证明是安全的。本文基于改进的判定双线性Diffie-Hellman假设，提出了一个具体的构造，该构造在随机预言模型下是安全的。

介绍

随着互联网的快速发展，人们更喜欢用电子邮件而不是普通邮件来进行交流。在公钥加密设置中，发送方用接收方的公钥对邮件进行加密，以保护邮件的隐私。考虑下面的情况。具有来自用户的特殊信息的用户邮件网关可以将电子邮件路由到不同的设备，例如笔记本电脑、台式机和智能手机，以便用户能够在他/她想要的任何设备上阅读电子邮件。例如，带有关键字“紧急”的电子邮件会被发送到智能手机。由于某些原因，经理Alice需要将她对商务电子邮件的解密权限授予副经理Bob。这种委托可以通过Alice的邮件服务器来完成，该服务器重新加密Alice的商务电子邮件并将其发送给Bob。最后，鲍勃可以用他自己的私钥读取它们。同时，Bob的邮件网关也可以路由这些重新加密的电子邮件。我们的目标是：

（1）Alice的邮件服务器可以重新加密发送给Alice的邮件，但无法获取内容。

（2）仅具有来自Bob的陷门的Bob的邮件网关可以测试诸如“紧急”之类的关键字是否包含在委托的电子邮件中，但是不了解关于电子邮件的任何其他信息。
邮件服务器的功能可以通过代理再加密（PRE）实现[7,3,4,13,18,19]，其中具有特定信息（也称为再加密密钥）的半可信代理可以将Alice公钥下的密文再加密为Bob公钥下的另一个密文，而代理无法获得明文。另一方面，邮件网关的功能可以通过带有关键字搜索的公钥加密（PEKS）来实现[8,2]其中具有由解密器计算的陷门的网关学习。除了密文是否包含与陷门相对应的关键字之外，什么也不知道。但是，直接将PRE和PEKS结合起来，无法同时实现邮件服务器的功能和邮件网关的功能，比如

其中是爱丽丝的公钥，是消息的关键字， 表示连接操作。原因有二：

1. 根据PEKS的要求，只能通过爱丽丝的陷门测试。因此，Bob的邮件网关不能测试即使Alice的邮件服务器重加密。为了进行测试，Alice可以将她的陷门给Bob，Bob会将这些陷门转发到他的邮件网关。然而，在这种情况下，爱丽丝的隐私受到了伤害，因为鲍勃并且他的邮件网关将知道每个关键字在Alice的电子邮件中的位置，而无需重新加密她的电子邮件。在Alice的邮件服务器重新加密电子邮件之前，这些信息应该只被Alice和她的邮件网关知道。请注意，只有在重新加密后，Alice才允许Bob访问她的电子邮件。
2. 即使基础的PRE方案和PEKS方案都被选择为密文安全的，得到的方案也不是密文安全的。这是因为对手可以修改或，并用它来查询测试预言或解密预言，以获得想要的结果。我们在第2节给出了细节。
   

本文提出了一种新的密码原语，称为关键字搜索代理重加密（PRES），以同时实现邮件服务器的功能和邮件网关的功能。对PRES的要求有三个方面：允许的变换方向、允许的变换时间和变换后密文的格式。
单向：这与允许的转换方向有关。在单向加密方案中，邮件服务器持有的特定信息（也称为再加密密钥）只能用于在一个方向上（仅从Alice到Bob）对密文进行再加密；如果信息可以用于双向重新加密（从Alice到Bob，反之亦然），那么PRES方案是双向的。
多用途：这与允许的转化时间有关。如果密文可以被邮件服务器多次重新加密，比如从Alice到Bob，再从Bob到Carol等等，那么PRES方案就是多用途的；否则，它是单用途的。
透明：这与转换后的密文的格式有关。如果用重加密密钥重加密的密文和用委托者的私钥加密的密文在计算上是不可区分的，我们称PRES方案是透明的。

相关著作

将PRE和PEKS直接结合不能得到PRES，但通过PRE和PEKS技术可以得到PRES方案。因此，我们对PRE和PEKS做一个简短的介绍。
PRE的概念由Blaze等人提出;他们还提出了第一个PRE方案，这是一个具有多可用性和透明性的双向PRE方案。之后，基于密钥共享技术，Ivan和Dodis提出了一种通用构造的单次使用单向但不透明的PRE方案。在[3,4]中，Ateniese等人提出了其他基于双线性映射的单次使用、单向但不透明的PRE方案。如[13,19]所述，上述方案均不能实现[13,19]所定义的选定密文安全性。Green和Ateniese在随机oracle模型中提出了第一种选择密文安全、基于id、一次性使用、单向但不透明的PRE方案。在ACM CCS 2007上，Canetti和Hohenberger在标准模型中提出了第一种选择的密文安全、多用途、双向和透明的PRE方案。最近，Libert和Vergnaud在标准模型中提出了第一种可重玩的选择密文安全、一次性使用、单向但不透明的PRE方案。Shao和Cao在随机预言机模型中提出了一种选择密文安全、一次性使用、单向但不透明的PRE方案。注意，可重玩选择的密文安全性比选择的密文安全性弱。在可重玩的选择密文安全模型中，不允许对手使用其对应消息是挑战消息之一的密文查询解密预言机。关于PRE的完整论文列表，读者可以参考[1]。
PEKS的概念是由Boneh等人提出的。在[9,10]中基于身份的加密（IBE）方案的基础上，Boneh等人提出了第一个PEKS方案。后来，Abdalla等人重新审视了PEKS的概念，并指出PEKS与匿名IBE之间的关系。最近，Bellare、Di Crescenzo和Saraswat分别提出了基于RSA和Jacobi符号的其他PEKS方案。在[11,17]中提出了表达能力更强的关键字搜索PEKS方案。

我们的贡献

本文介绍了关键字搜索代理重加密的概念，特别是双向关键字搜索代理重加密的概念。我们还提出了一个双向PRES的安全模型，特别是选择密文安全概念：关键字保密和消息保密。
如前所述，我们的方案是基于PRE和PEKS的技术，如[13]中的PRE方案和[9,10]中的IBE方案中的技术。然而，IBE方案中的技术不能直接用于PRES方案的构建。这是因为在IBE方案中，包含消息的密文项中总是包含解密者的信息，而在PRES方案中，重新加密后解密者会发生变化。为了在IBE中使用这些技术来构建PRES，我们对IBE技术进行了修改。特别是，用户的私钥被更改为，其中sk是私钥生成器的主密钥。
提出了一种基于Canetti-Hohenberger技术和Boneh-Franklin技术的双向PRES方案，该方案在随机预言模型中被证明是安全的。该方案的安全性基于改进的决策双线性Diffie-Hellman（mDBDH）假设，该假设等价于决策双线性Diffie-Hellman（DBDH）假设。

文章组织

其余的论文组织如下。第2节提出了基于关键字搜索的（双向）代理重加密的定义和安全模型。第3节介绍了双线性映射和mDBDH假设。在第4节中，我们介绍了我们的双向PRES方案，并对其进行了分析。第5部分给出了PRES的另外两个应用，最后在第6部分对本文进行了总结。

定义

在本节中，我们将重点介绍如何定义双向方案。

定义1（双向PRES。基于关键字搜索的双向代理重加密（PRES）方案由以下多项式时间随机化算法组成：

• ：给定安全参数k，密钥生成算法输出一个公钥/私钥对。
• ：给定用户的私钥和关键字，陷门生成算法输出用户对应的关键字的陷门。这个算法由私钥的所有者执行，他将通过一个安全通道将陷门发送到她/他的邮件网关。
• ：给定Alice的私钥和Bob的私钥，重加密密钥生成算法输出重加密密钥。该算法由Alice和Bob执行，他们通过安全通道将重新加密密钥发送到她/他的邮件服务器。
• ：给定一个公钥、一个关键字和消息空间中的消息，加密算法输出一个对应的密文。我们表示为密文的关键字。该算法由邮件发送者执行。
• ：给定委托对应的重加密密钥和公钥下的密文，重加密算法输出另一个公钥对应的密文或错误符号。该算法由邮件服务器执行，对密文进行转换。我们说是一个委托，如果已经被执行。
• ：给定用户的公钥、密文和陷门，如果，测试算法输出“yes”，否则输出“no”。该算法由邮件网关执行，检查密文C中是否包含与陷门关联的关键字。
• ：给定用户的秘钥和密文，解密算法在消息空间中输出相应的消息或错误符号。该算法由Alice/Bob执行。
  

正确性。PRES的正确性属性比公钥加密更复杂，它有以下四个要求。注意，我们假设所有的对手都是多项式时间的对手。

• 单一的解密：对于所有输出，所有在关键字空间和所有在消息空间，等式必须保持概率1减去一个可以忽略的量。这个属性保证邮件接收者可以用她/他的公钥解密加密的邮件。
• 多解密：对于任意，输出的任意序列对，任意， 的所有输出，消息空间中的所有m，关键字空间中的所有w和的所有输出，等式必须以1减去一个可忽略的量的概率保持。此属性保证用户可以在邮件服务器转换后解密他人委托的加密邮件。
• 单一的测试：对于输出的所有，关键字空间中的任意两个不同的单词和消息空间中的所有，等式和必须以1减去一个可忽略的量的概率成立。此属性保证邮件网关能够正确测试加密邮件的关键字。
• 多测试：对于任意，输出的任意对序列，任意，输出的所有，消息空间中的所有m，任意两个不同的单词在关键字空间和输出的所有，公式和概率为1减去一个可忽略的量。这个属性保证邮件网关可以正确地测试从其他人（而不是它的客户端）委托的加密邮件的关键字。

双向PRES有两个安全概念：关键字隐私和消息隐私。

在这种安全概念下，对手可以获得任何密文的明文，几乎所有的活动门，除了那些与两个指定关键字相关的，但是，它不能决定哪个关键字对应一个给定的密文。这个安全概念保证只有拥有活板门的人才能进行测试。
如果在接下来的博弈中，没有多项式有界对手对挑战者具有不可忽略的优势，则双向PRES方案能够保持关键字的隐私性。注意，我们采用[13]中的假设为关键字定义了隐私：静态破坏，也就是说，在这个安全概念中，对手必须在计算开始之前确定被破坏的各方，并且它不允许在被破坏和未被破坏的各方之间自适应破坏邮件服务器。
阶段1：对手发出查询，其中查询是其中之一：

• 未损坏的密钥生成预言机：获取新的密钥对，给定A一个。
• 损坏的密钥生成预言机：获取一个新的密钥对，给定A一个。
• 陷门生成预言机：当对手输入时，其中来自或，是关键字空间中的关键字，返回陷门，其中sk是pk对应的密钥。
• 重加密密钥生成预言机：对于对手的输入，其中来自或，返回重加密密钥，其中和分别对应于和的密钥。这里，与[13]中一样，我们要求和要么都损坏，要么都没有损坏。即和都来自或。因此，不允许在损坏的密钥和未损坏的密钥之间进行重新加密密钥生成查询。
• 重加密预言机：对于对手的输入，其中来自或，返回重加密的密文。
• 测试预言机：当对手输入时，返回，其中是对应的密钥。
• 解密预言机：对手输入，其中来自或，返回，其中是对应的密钥。
  

可以自适应地询问这些查询，也就是说，每个查询可能依赖于对的回答。

挑战：一旦对手A决定阶段1结束，它从关键字空间输出两个长度相等的单词，从消息空间输出一条消息，以及一个希望被挑战的公钥。公钥有一个约束，公钥有一个约束，即来自，并且从未被查询到。

挑战者随机选择一个和，它发送作为对的挑战。

阶段2：对手发出更多查询，其中查询是其中之一：

• 未损坏的密钥生成预言机：和阶段1的相同。
• 损坏的密钥生成预言机：和阶段1的相同。
• 陷门生成预言机：对于对手的输入，如果下列条件都不成立，挑战者的响应为阶段1；否则，挑战者返回不在陷门空间的。

；

或，来自。这个约束是必需的，因为如果不是，那么对手可以使用自己测试挑战密文。

• 重加密密钥生成预言机：和阶段1的相同。
• 重加密预言机：对对手的输入，如果来自或不是，那么挑战者的反应是在阶段1。否则，返回不在消息空间中的。

的导数定义如下：

1. 是自身的导数。
2. 如果是的导数，是的导数，那么是的导数。
3. 如果，那么是的导数。
4. 如果或，那么是的导数。

• 测试预言机：对于输入，如果不是的导数，挑战者的响应与阶段1相同。否则，返回。
• 解密预言机：和阶段1的相同。

猜想：最后，对手A猜出，如果就赢了。

我们将这样的对手A称为对手。我们将对手A攻击的优势定义为安全参数k的以下函数：。

利用游戏，我们可以用关键字搜索方案为双向代理重加密的关键字定义隐私。

定义2（安全性）。如果在任何多项式时间内对手A的函数可以忽略，则双向PRES方案保持关键字的隐私性。简而言之，我们说PRES是安全的。

召回构建。对手总是可以赢得游戏。假设挑战密文为。在阶段2中，对手可以使用查询，其中。如果返回值是“yes”，则对手猜测为，否则猜测为。

在这种安全概念下，对手可以得到除指定密文之外的几乎所有密文的明文，但是所有陷门不能决定哪条消息对应于指定的明文。这个安全概念保证了只有拥有私钥的人才能解密密文。
这里，我们将消息的隐私定义为关键字的隐私。如果在下面的博弈中，没有多项式有界对手对挑战者具有不可忽略的优势，我们说双向PRES方案保持消息的保密性。

阶段1：与消息隐私安全模型中相同。

挑战：一旦对手A决定阶段1已经结束，它就从消息空间输出两个长度相等的单词，一个分别与相关联的关键字，以及一个希望被挑战的公钥。公钥只有一个约束，即来自。

挑战者随机选取一个，和集合，发送作为对的挑战。

阶段2：对手可以自适应查询与博弈阶段2相同的预言机，除了以下三个预言机：

陷门生成预言机：和阶段1的相同。

测试预言机：和阶段1的相同。

解密预言机：对于对手的输入，如果来自，或者不是的导数，挑战者的反应与阶段1相同。否则，返回不在消息空间中的。

猜想：最后，对手A输出一个猜测，如果则赢得游戏。

我们将这样的对手A称为对手。我们将对手A攻击的优势定义为安全参数k的以下函数：。

利用博弈，我们可以定义双向PRES方案的消息隐私性。

定义3（双安全性）。如果对于任何多项式时间的双向对手A，函数Adv可以忽略，我们说双向方案保持消息的保密性。简而言之，我们说是安全。

收回构造。对手总是可以赢得游戏。假设挑战密文为。在阶段2中，对手可以使用查询，其中。如果返回值是，则对手猜测为，否则猜测为。

备注1（关于生成重新加密密钥）。重新加密密钥生成算法可以通过中的方法实现[5,13]。在这种情况下，当Alice或Bob与她或他的邮件服务器勾结时，她或他可以通过组合她或他的私钥和重新加密密钥来获得对方的私钥。请注意，它不允许在安全游戏中的受损方和未受损方之间自适应破坏邮件服务器，这允许我们使用中的重新加密密钥生成算法。

在本小节中，我们简要回顾了双线性映射和双线性映射组的定义，这是继[9,10]之后的定义。

1. 和是素数阶q的两个（乘性）循环群；
2. g是的生成器；
3. e是双线性映射。对于所有，。
   

如果中的群作用能被有效地计算，并且存在一个群和一个有效地可计算的双线性映射，我们就说是一个双线性群。我们将表示为这样一种算法：在输入安全参数时，输出双线性映射的参数为，其中。

mDBDH问题。另。mDBDH问题如下：对于随机的和，给定，决定是否。如果，算法A在求解mDBDH问题上具有优越性，其中概率是在中的随机选择，在中的随机选择，的随机选择，以及A的随机位。

定义4 （mDBDH假设）。如果PPT算法在解决mDBDH问题上没有优势，那么e-mDBDH假设成立。
证明了mDBDH假设等价于决策双线性Diffie-Hellman（DBDH）假设（[13]引理3.1）。

我们的方案

在本节中，我们提出了第一个双向、多用途、透明的PRES方案。

符号和配置。这里，我们使用与[13]中类似的表示法和配置。即是安全参数，，h是G中的一个随机数，是一个强不可伪造的一次性签名方案，是输出的验证密钥长度，G产生的验证密钥空间具有超对数最小熵。此外，，，，。
因此，我们方案的公共参数为。
该方案基于[13]中的方案和[9,10]中的IBE方案。具体情况如下:
KeyGen：在输入时，随机选择，设定和。

Trapdoor：输入用户的秘密密钥和关键字后，输出与公钥对应的关键字的陷门。

ReKeyGen：输入两个用户的密钥，输出双向重加密密钥。注意，我们使用与[13]的评论4.1相同的假设和方法来生成重加密密钥。

• 用户A可以随机选择一个发送给用户B，并发送r给代理。
• 用户B发送到代理。
• 代理计算。

Enc：在输入用户的公钥pk，关键字w和消息时，执行：

1. 选择一次性签名密钥对为。设置。
2. 随机选择一个并计算：，，，，，。
3. 运行签名算法，其中要签名的消息是元组，并表示签名。
4. 输出密文。
   

ReEnc：输入重加密密钥和密钥下的密文，重新加密密钥下的密文如下：

• 如果（见下面的定义），输出并终止；否则执行下一步。该算法的定义如下：给定一个密文元组和一个键，执行以下步骤。

（a）运行对消息验证签名，验证密钥。

（b）检查和。

（c）如果这些检查中的任何一个失败，输出0；其他输出1。

• 计算，输出新密文。

Test：输入一个用户的公钥，一个陷门和一个密文，执行：

• 如果，那么输出“no”且终止；否则执行下一步。
• 如果，那么输出“yes”，否则输出“no”。

Dec：输入一个用户的密钥sk和一个密文，如果，那么输出消息；否则，输出。

正确性：首先，我们想通过检查第2节中逐项列出的需求来显示我们提案的正确性。

单一加密：因为

正确性的第一个属性被保留。

多解密：由于重加密的密文与原始密文具有相同的形式，因此我们可以从上述属性获得此属性。

单测试：因为，因此我们有。

此外，一方面，是一个抗碰撞的哈希函数，当时，它满足的高概率;配对的性质告诉我们，当时，得到，因为是一个抗碰撞哈希函数。因此，我们有，概率至少为，其中和碰撞发生的概率分别为和。

因此，第三个正确性属性被保留了下来。

多测试：由于重新加密的密文与原始密文具有相同的形式，因此我们可以从上述属性获得此属性。

隐私的关键字。

定理1：如果mDBDH假设在中成立，那么我们的提议满足随机预言机模型中关键字隐私的属性。

证明：我们证明，如果存在一个对手A，以的概率破坏我们提议关键字的隐私，那么我们可以构造一个算法B，使用A以概率解决mDBDH问题：

，其中，、、、和分别是对哈希预言机、测试预言机、重加密预言机、测试生成语言和解密预言机的查询次数，δ是G输出任何给定验证密钥的最大概率（假设是可以忽略的）。此外，Pr[A break Sig]也可以忽略不计的假设。

在mDBDH输入上，B的目的是确定是否成立。B设置A的全局参数如下：组的描述，它们的素数，和映射，，。系统参数为，其中，为来自的随机数。

安全参数为。

在游戏中，B与A进行如下交互（B模拟A的挑战者）。在接下来的游戏中，我们使用带星号的字母，表示未损坏的对应的挑战密文。

哈希预言机：B构建以下预言机。

：对哈希函数的输入, B首先检查元组是否出现在表中。如果是yes，B用回应A。否则，B以的概率使，其中，为的最大查询次数。最后，如果，B用回应A，或者如果，用回应A，并在表中记录。

：当向哈希函数输入A时，B首先检查表中是否存在元组。如果存在，B用回应A。否则，如果，B用回应A，并在表中记录；如果，B选取随机数，用回应A，并在表中记录。

：当向哈希函数输入A时，B首先检查元组是否出现在表中。如果是，B用回应A。否则，如果， B用响应A，并在表中记录；如果， B选择随机数，然后用回应A，并在表中记录。

：对哈希函数的输入，B首先检查元组是否出现在表中。如果是，B用回应A。否则，B选择随机数，然后用回应A，并在表中记录。

阶段1。B构建了以下的预言机。

：在输入索引i时，B随机选取。如果，B计算；否则，B计算。最后，B在表中记录元组，并以响应A。表用于记录和的进程，这些记录将用于其他预言机来响应查询。

：在输入时，B检查中是否发生，如果没有，B终止。否则，如果，B终止。如果，则B用响应A ，并在表中记录元组。

：在输入上，如果，B以响应A。如果，B查询获得，如果，B响应A；或报告“失败”并中止。注意，当时有；当时有。

：在输入时，B检查和是否同时出现在中，如果没有，B终止。否则，B执行如下操作。

• 如果，B用回应A。
• 如果，B终止。

：在输入， B检查和是否都出现在表中，如果没有，B终止。否则，B解析，如果，B输出是并终止；否则，B执行如下操作。

• 如果，B查询得到对应的重加密密钥，B用回应A。
• 如果和，B计算，并返回到A。注意，当时。因此，重新加密的密文是有效的。
• 如果和，B检查是否满足。如果是，B输出“failure”并中止。否则，B在表中找到，计算。最后，B返回给A。注意当时。因此，重加密的密文是有效的。

：在输入， B查询获得硬币，如果下列条件之一保持，B查询获得，并用响应A。

• 来自；
• 。
  

如果上述条件都不成立，B检查是否满足。如果是，B输出“failure”并中止。否则，B在表中找到，并检查。如果方程成立，那么B回答A“yes”；否则响应“no”。注意，。

：在输入时，B检查表中是否出现，如果没有，B终止。否则，B执行如下操作。

• 如果，则，B用回应A。
• 如果，B解析。如果，B输出并终止；否则，B检查是否满足。如果满足，B在表中查找，并且计算；否则，B在表中查找，并且计算。

挑战：在某些时候，A输出一个挑战元组。如果不在表中，或者，B终止。如果和，B报告“失败”并终止。否则，B选择一个随机数，使，然后用以下数据对A进行响应：

其中为表中对应的值，为表中对应的值，为表中对应的值。

阶段2。B构建了以下的预言机。

：与阶段1相同。

：对于对手的输入，如果下列条件都不成立，B的反应与阶段1相同。

• ；
• ；
• 或，来自。

如果上述条件之一成立，B返回不在陷门空间内的。

：在输入，B解析，如果和，B终止；否则，B的性能与阶段1相同。

：输入，B解析，如果；B终止。否则，B的性能与阶段1相同。

猜想：最后，对手A输出猜想。如果，则B输出1（即一个mDBDH实例），否则B输出0（即不是一个mDBDH实例）。

如果B没有报告“失败”，那么A的视图与真实攻击中的视图是相同的。此外，当B接收到一个mDBDH实例作为输入时，挑战密文是的正确加密，A猜测的优势与实际执行时相同。当B没有接收到mDBDH实例时，挑战密文不包含关于的信息，因为密文分量均匀分布在上，与无关，A的猜测的概率正好是1/2。

现在，我们分析B在模拟过程中没有报告“失败”的概率。我们定义了三个独立事件：

• ：B不会因为A的任何陷门查询而报告“失败”。在这种情况下，coin应该是1。
• ：B不会报告A的任何测试和重加密查询的结果“失败”。在本例中，不在对、和的查询中。
• ：B在挑战阶段没有报告“失败”。

W.l.o.g，我们假设A不会两次请求相同关键字的陷门。由于无论还是，上的分布是相同的，且coin的值与A的观点无关，因此，一个陷门导致B报告“失败”的概率为。假设A最多进行次陷门查询，则。

我们假设最坏的情况是B总是需要元组来回答对和的查询。B在回答这些查询时报告“失败”的唯一情况是。在给出挑战密文之前，A的概率最多为。用密文查询这三个预言机。给出挑战密文后，它有Pr[a break Sig]的机会对的密文查询这三个预言机，并且该密文不是挑战密文的衍生。因此，我们有。

挑战阶段B报告“失败”的唯一情况是。由于A没有查询过，所以和的值与A当前的观点无关。此外，这两个值是相互独立的。因此我们有。

因此，我们有按要求的。
隐私信息。
定理2。如果mDBDH假设在中成立，那么我们的提议满足了随机预言模型中消息隐私的特性。

证明。我们证明，如果存在一个对手A，它以的概率破坏了我们提议的消息的隐私，那么我们可以构造一个算法B，该算法使用A以下面的概率来解决mDBDH问题：

其中是对哈希预言机、哈希预言机、重加密预言机和解密预言机的查询的总和，是输出任何给定验证密钥的最大概率（通过假设可以忽略不计）。此外，Pr[A break Sig]也可以忽略不计的假设。

在mDBDH输入上，B的目标是确定是否满足。B设置A的全局参数如下：组的描述，它们的素数，以及映射：， ，。系统参数为，其中，为来自的随机数。

安全参数为。在一个Bi-PRES-CCA-M游戏中，B与A的交互如下（B模拟A的挑战者）。在接下来的游戏中，我们使用带星号的字母表示一个未损坏的对应的挑战密文。

哈希预言机：B构建以下预言机。

：对哈希函数的输入m，B首先检查元组是否出现在表中。 如果是，B用回应A。 如果不是，B选择一个随机数，然后用响应A，并在表中记录。

：对哈希函数的输入A，B首先检查元组是否出现在表中。 如果是，B用回应A。如果不是，如果，B用响应A，并在表中记录；如果，B选取随机数，然后用响应A，并在表中记录。

和：和定理1的证明一样。
和：与定理1证明中的相同。
：在输入时，B查询得到。如果，B用回应A；如果，则为。注意，当时；当时。因此，返回的陷门是有效的。
：在输入， B查询得到。用回答A。
：在输入时，B检查表中是否出现，如果没有，B终止。否则，B执行如下操作。

如果，那么，B用回应A。
如果，B解析。如果，B输出并终止；否则，B检查是否满足。如果是这样，B报告“失败”并终止。否则，B在表中找到，并且计算：
挑战：在某个时候，A输出一个挑战元组，如果不在表中，或；B终止。否则，B选择一个随机数，然后用如下数据回应A：

其中为表中w对应的值，为表中对应的值，为表中对应的值。

阶段2。B构建了以下的预言机。

：与阶段1相同。

：输入，B解析，如果，和，B终止；否则，B的性能与阶段1相同。

：输入，B解析，如果，B终止。否则，B的性能与阶段1相同。

猜测：最后，对手A输出猜测。如果，则B输出1（即一个mDBDH实例），否则B输出0（即不是一个mDBDH实例）。

B的成功概率与[13]中相同，因为B的哈希、哈希、陷门和测试响应都是根据我们的提议的一个真实实例完美分布的，其他预言机的情况与[13]中相同。

因此，我们根据需要得到。

PRES的更多应用

云计算中的一个应用

云计算越来越受到信息和通信技术界的关注，因为它可以降低与计算基础设施中硬件和软件资源管理相关的成本。在云计算中，远程数据中心负责存储用户数据，包括需要保护的数据。一方面，远程数据中心通常被认为是半可信的，因此私有数据应该被加密。另一方面，用户通常不是检索所有的加密数据，而是检索部分加密数据，这就要求可搜索的加密方案支持基于关键字的密文搜索。
在某些情况下，用户Alice希望与用户Bob共享一些数据，但不是所有数据。一种可能的解决方案如下:Alice从她的数据中心检索并解密加密的数据，然后通过安全通道发送给Bob，Bob将加密并发送结果密文到他的数据中心。虽然这种解决方案可以保证共享数据的隐私性，但是效率非常低。传输数据的总大小至少是共享数据的三倍，并且Alice和Bob都需要参与该过程。
PRES方案可以提供更有效的解决方案，该方案允许从Alice的数据中心到Bob的数据中心的直接数据传输，并且Bob可以像处理自己的数据一样处理这些数据。首先，PRES支持对原始密文和重新加密的密文进行基于关键字的搜索。第二，持有重加密密钥的实体可以进行密文的变换，但不能解密密文。特别是，Alice的数据中心有从Alice到Bob的重新加密密钥。当Alice想要与Bob共享一些数据时，她只需要告诉她的数据中心哪些数据是用于传输的。Alice的数据中心首先用陷门搜索所需数据，然后使用代理重加密密钥转换关联数据，并将结果数据发送到Bob的数据中心。根据PRES的正确性，Bob可以将Alice共享的数据解密搜索为己有。在该解决方案中，所需网络带宽的总大小与共享数据的大小相同，Alice和Bob不需要参与该过程。

传感器网络中的一个应用

无线通信和电子技术的最新进展使得传感器网络得以快速发展。传感器网络的一个常见应用是监控我们周围的环境，并提供信息供我们分析和响应。由于采集的数据量很大，为了方便分析和快速响应，需要对数据进行分类。一种自然的分类方法是使用关键字。例如，当传感器Sam在其感测范围内检测到“火警”时，它通过多跳自组织方式将带有关键字“火警”的紧急信息转发给主汇聚节点Alice。由于请求量很大，Alice有一个接收器服务器来帮助她完成分类工作。通常，由于信息的安全性和隐私性，只有预定的主sink节点可以访问收集的数据，并且sink服务器应该在不知道细节的情况下通过关键字对数据进行分类。
在某些情况下，汇聚节点Alice太忙而不能响应来自传感器的每个请求，或者由于低功率而不能继续工作，她可以通过她的汇聚
服务器将她的工作委托给其他汇聚节点，例如汇聚节点Bob。在这种情况下，Alice的sink服务器除了按关键字分类作业之外，还有另一个任务，就是将发送给Alice的数据重新加密，然后发送给Bob。最后，Bob可以对它进行与sink节点Alice相同的操作，即Bob可以允许他的sink服务器对它进行分类工作，并且Bob可以将访问权限委托给其他sink节点。
利用PRES方案，我们可以如下容易地设计实现上述示例的网络系统。传感器使用目标传感器节点的公钥，使用PRES加密算法对数据进行加密，并发送密文。目标传感器节点的汇聚服务器分别通过陷门和再加密密钥对加密数据进行分类和转换。数据的机密性可以通过底层PRES方案的安全性来保证。

结论

本文介绍了基于关键字搜索的代理重加密的概念，它是由电子邮件系统的需求所激发的。本文提出了一个具体的双向PRES方案，该方案在随机预言模型下是安全的。此外，我们还分别给出了PRES在云计算和传感器网络中的两个应用。这项工作激发了一些有趣的开放性问题。举个例子：

• 设计一个没有配对的PRES方案。如前所述，PRES可用于传感器网络。然而，传感器网络中的传感器具有有限的计算资源，这排除了基础PRES方案中耗时的操作，例如计算配对。
• 设计一个在标准模型下证明安全的PRES方案。我们试图设计这样的方案，但是失败了，因为现有的PKES方案[12,11,17] 在标准模型中被证明是安全的，不能轻易地转换成可重加密的PKES方案。
• 设计一个有效的单向PRES方案。我们使用了密钥共享技术[16,15] 然而，为了获得单向压力方案；得到的PRES方案比我们的方案更复杂，效率更低。

我们把这些问题留给以后的研究。

感谢

我们感谢《信息科学》的匿名评论者提供的有见地的评论和有益的建议。我们也感谢张钫对写作改进的帮助。