摘要
我们引入了一种新的密码原语,称为带关键字搜索的代理重加密,这是受电子邮件系统中的以下场景的启发:
Charlie在Alice的公钥下向Alice发送一封加密的电子邮件,其中包含一些关键字,如“urgent”,Alice通过她的邮件服务器将她的解密权限委托给Bob。期望的情况是:
(1)Bob可以仅通过使用他的私钥来解密Alice委托的邮件;
(2)Bob的邮件网关,带有来自Bob的活板门,可以测试从Alice委托的电子邮件是否包含一些关键字,例如“紧急”;
(1)Bob可以仅通过使用他的私钥来解密Alice委托的邮件;
(2)Bob的邮件网关,带有来自Bob的活板门,可以测试从Alice委托的电子邮件是否包含一些关键字,例如“紧急”;
(3)Alice和Bob不希望给予邮件服务器或邮件网关对电子邮件内容的访问权。
带关键字搜索的代理重加密(PRES)的功能是代理重加密(PRE)和带关键字搜索的公钥加密(PEKS)的结合。然而,PRES方案不能通过直接组合这两个方案来获得,因为所得到的方案在我们的安全模型中不再被证明是安全的。本文基于改进的判定双线性Diffie-Hellman假设,提出了一个具体的构造,该构造在随机预言模型下是安全的。
带关键字搜索的代理重加密(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结合起来,无法同时实现邮件服务器的功能和邮件网关的功能,比如
%7C%7CPEKS(pk_%7BA%7D%2Cw))
其中
是爱丽丝的公钥,
是消息
的关键字, 表示连接操作。原因有二:
邮件服务器的功能可以通过代理再加密(PRE)实现[7,3,4,13,18,19],其中具有特定信息(也称为再加密密钥)的半可信代理可以将Alice公钥下的密文再加密为Bob公钥下的另一个密文,而代理无法获得明文。另一方面,邮件网关的功能可以通过带有关键字搜索的公钥加密(PEKS)来实现[8,2]其中具有由解密器计算的陷门的网关学习。除了密文是否包含与陷门相对应的关键字之外,什么也不知道。但是,直接将PRE和PEKS结合起来,无法同时实现邮件服务器的功能和邮件网关的功能,比如
其中
-
根据PEKS的要求,
只能通过爱丽丝的陷门测试。因此,Bob的邮件网关不能测试
即使Alice的邮件服务器重加密
。为了进行测试,Alice可以将她的陷门给Bob,Bob会将这些陷门转发到他的邮件网关。然而,在这种情况下,爱丽丝的隐私受到了伤害,因为鲍勃并且他的邮件网关将知道每个关键字在Alice的电子邮件中的位置,而无需重新加密她的电子邮件。在Alice的邮件服务器重新加密电子邮件之前,这些信息应该只被Alice和她的邮件网关知道。请注意,只有在重新加密后,Alice才允许Bob访问她的电子邮件。
-
即使基础的PRE方案和PEKS方案都被选择为密文安全的,得到的方案也不是密文安全的。这是因为对手可以修改
或
,并用它来查询测试预言或解密预言,以获得想要的结果。我们在第2节给出了细节。
单向:这与允许的转换方向有关。在单向加密方案中,邮件服务器持有的特定信息(也称为再加密密钥)只能用于在一个方向上(仅从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方案。
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)假设。
如前所述,我们的方案是基于PRE和PEKS的技术,如[13]中的PRE方案和[9,10]中的IBE方案中的技术。然而,IBE方案中的技术不能直接用于PRES方案的构建。这是因为在IBE方案中,包含消息的密文项中总是包含解密者的信息,而在PRES方案中,重新加密后解密者会发生变化。为了在IBE中使用这些技术来构建PRES,我们对IBE技术进行了修改。特别是,用户的私钥
提出了一种基于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:对手
发出查询
,其中查询
是其中之一:
如果在接下来的
阶段1:对手
-
未损坏的密钥生成预言机
:获取新的密钥对
,给定A一个
。
-
损坏的密钥生成预言机
:获取一个新的密钥对
,给定A一个
。
-
陷门生成预言机
:当对手输入
时,其中
来自
或
,
是关键字空间中的关键字,返回陷门
,其中sk是pk对应的密钥。
-
重加密密钥生成预言机
:对于对手的输入
,其中
来自
或
,返回重加密密钥
,其中
和
分别对应于
和
的密钥。这里,与[13]中一样,我们要求
和
要么都损坏,要么都没有损坏。即
和
都来自
或
。因此,不允许在损坏的密钥和未损坏的密钥之间进行重新加密密钥生成查询。
-
重加密预言机
:对于对手的输入
,其中
来自
或
,返回重加密的密文
。
-
测试预言机
:当对手输入
时,返回
,其中
是对应
的密钥。
-
解密预言机
:对手输入
,其中
来自
或
,返回
,其中
是
对应的密钥。
可以自适应地询问这些查询,也就是说,每个查询
可能依赖于对
的回答。
挑战:一旦对手A决定阶段1结束,它从关键字空间输出两个长度相等的单词
,从消息空间输出一条消息
,以及一个希望被挑战的公钥
。公钥
有一个约束,公钥
有一个约束,即
来自
,并且
从未被查询到
。
挑战者随机选择一个
和
,它发送
作为对
的挑战。
阶段2:对手
发出更多查询
,其中查询
是其中之一:
-
未损坏的密钥生成预言机
:和阶段1的相同。
-
损坏的密钥生成预言机
:和阶段1的相同。
-
陷门生成预言机
:对于对手的输入
,如果下列条件都不成立,挑战者的响应为阶段1;否则,挑战者返回不在陷门空间的
。
-
重加密密钥生成预言机
:和阶段1的相同。
-
重加密预言机
:对对手的输入
,如果
来自
或
不是
,那么挑战者的反应是在阶段1。否则,返回不在消息空间中的
。
-
是自身的导数。
-
如果
是
的导数,
是
的导数,那么
是
的导数。
-
如果
,那么
是
的导数。
-
如果
或
,那么
是
的导数。
-
测试预言机
:对于输入
,如果
不是
的导数,挑战者的响应与阶段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]之后的定义。
-
和
是素数阶q的两个(乘性)循环群;
-
g是
的生成器;
-
e是双线性映射
。对于所有
,
。
如果
中的群作用能被有效地计算,并且存在一个群
和一个有效地可计算的双线性映射,我们就说
是一个双线性群。我们将
表示为这样一种算法:在输入安全参数
时,输出双线性映射的参数为
,其中
。
改进的决策双线性Diffie-Hellman假设(mDBDH)
mDBDH问题。另
。mDBDH问题如下:对于随机的
和
,给定
,决定是否
。如果
,算法A在求解mDBDH问题上具有优越性,其中概率是在
中
的随机选择,在
中
的随机选择,
的随机选择,以及A的随机位。
定义4 (mDBDH假设)。如果PPT算法在解决mDBDH问题上没有优势,那么e-mDBDH假设成立。
证明了mDBDH假设等价于决策双线性Diffie-Hellman(DBDH)假设([13]引理3.1)。
证明了mDBDH假设等价于决策双线性Diffie-Hellman(DBDH)假设([13]引理3.1)。
我们的方案
在本节中,我们提出了第一个双向、多用途、透明的PRES方案。
构造
符号和配置。这里,我们使用与[13]中类似的表示法和配置。即
是安全参数,
,h是G中的一个随机数,
是一个强不可伪造的一次性签名方案,
是
输出的验证密钥长度,G产生的验证密钥空间具有超对数最小熵。此外,
,
,
,
。
因此,我们方案的公共参数为
。
该方案基于[13]中的
方案和[9,10]中的IBE方案。具体情况如下:
KeyGen:在输入
时,随机选择
,设定
和
。
因此,我们方案的公共参数为
该方案基于[13]中的
KeyGen:在输入
Trapdoor:输入用户的秘密密钥
和关键字
后,输出与公钥
对应的关键字
的陷门
。
ReKeyGen:输入两个用户的密钥
,输出双向重加密密钥
。注意,我们使用与[13]的评论4.1相同的假设和方法来生成重加密密钥。
-
用户A可以随机选择一个
发送
给用户B,并发送r给代理。
-
用户B发送
到代理。
-
代理计算
。
Enc:在输入用户的公钥pk,关键字w和消息
时,执行:
-
选择一次性签名密钥对为
。设置
。
-
随机选择一个
并计算:
,
,
,
,
,
。
-
运行签名算法
,其中要签名的消息是元组
,并表示签名
。
-
输出密文
。
ReEnc:输入重加密密钥
和密钥
下的密文
,重新加密密钥
下的密文如下:
-
如果
(见下面的定义),输出
并终止;否则执行下一步。该算法
的定义如下:给定一个密文元组
和一个键
,执行以下步骤。
(a)运行
对消息
验证签名
,验证密钥
。
(b)检查
和
。
(c)如果这些检查中的任何一个失败,输出0;其他输出1。
-
计算
,输出新密文
。
Test:输入一个用户的公钥
,一个陷门
和一个密文
,执行:
-
如果
,那么输出“no”且终止;否则执行下一步。
-
如果
,那么输出“yes”,否则输出“no”。
Dec:输入一个用户的密钥sk和一个密文
,如果
,那么输出消息
;否则,输出
。
方案分析
正确性:首先,我们想通过检查第2节中逐项列出的需求来显示我们提案的正确性。
单一加密:因为
正确性的第一个属性被保留。
多解密:由于重加密的密文与原始密文具有相同的形式,因此我们可以从上述属性获得此属性。
单测试:因为
,因此我们有
。
此外,一方面,
是一个抗碰撞的哈希函数,当
时,它满足
的高概率;配对的性质告诉我们
,当
时,得到
,因为
是一个抗碰撞哈希函数。因此,我们有
,概率至少为
,其中
和
碰撞发生的概率分别为
和
。
因此,第三个正确性属性被保留了下来。
多测试:由于重新加密的密文与原始密文具有相同的形式,因此我们可以从上述属性获得此属性。
隐私的关键字。
定理1:如果mDBDH假设在
中成立,那么我们的提议满足随机预言机模型中关键字隐私的属性。
证明:我们证明,如果存在一个对手A,以
的概率破坏我们提议关键字的隐私,那么我们可以构造一个算法B,使用A以概率解决mDBDH问题:
在mDBDH输入
上,B的目的是确定
是否成立。B设置A的全局参数如下:组的描述
,它们的素数
,和映射
,
,
。系统参数为
,其中
,
为来自
的随机数。
安全参数为
。
在
游戏中,B与A进行如下交互(B模拟A的挑战者)。在接下来的游戏中,我们使用带星号的字母
,表示未损坏的
对应的挑战密文。
哈希预言机:B构建以下预言机。
阶段1。B构建了以下的预言机。
-
如果
,B用
回应A。
-
如果
,B终止。
-
如果
,B查询
得到对应的重加密密钥
,B用
回应A。
-
如果
和
,B计算
,并返回
到A。注意,当
时
。因此,重新加密的密文是有效的。
-
如果
和
,B检查是否满足
。如果是,B输出“failure”并中止。否则,B在
表中找到
,计算
。最后,B返回
给A。注意当
时
。因此,重加密的密文是有效的。
-
来自
;
-
。
-
如果
,则
,B用
回应A。
-
如果
,B解析
。如果
,B输出
并终止;否则,B检查是否满足
。如果满足,B在表
中查找
,并且计算
;否则,B在表
中查找
,并且计算
。
挑战:在某些时候,A输出一个挑战元组
。如果
不在表
中,或者
,B终止。如果
和
,B报告“失败”并终止。否则,B选择一个随机数
,使
,然后用以下数据对A进行响应:
其中
为表
中
对应的值,
为表
中
对应的值,
为表
中
对应的值。
阶段2。B构建了以下的预言机。
-
;
-
;
-
或
,
来自
。
猜想:最后,对手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在挑战阶段没有报告“失败”。
我们假设最坏的情况是B总是需要元组
来回答对
和
的查询。B在回答这些查询时报告“失败”的唯一情况是
。在给出挑战密文之前,A的概率最多为
。
用
密文查询这三个预言机。给出挑战密文后,它有Pr[a break Sig]的机会对
的密文查询这三个预言机,并且该密文不是挑战密文的衍生。因此,我们有
。
挑战阶段B报告“失败”的唯一情况是
。由于A没有查询过
,所以
和
的值与A当前的观点无关。此外,这两个值是相互独立的。因此我们有
。
因此,我们有按要求的
。
隐私信息。
定理2。如果mDBDH假设在
中成立,那么我们的提议满足了随机预言模型中消息隐私的特性。
隐私信息。
定理2。如果mDBDH假设在
证明。我们证明,如果存在一个对手A,它以
的概率破坏了我们提议的消息的隐私,那么我们可以构造一个算法B,该算法使用A以下面的概率来解决mDBDH问题:
其中
是对哈希
预言机、哈希
预言机、重加密预言机和解密预言机的查询的总和,
是
输出任何给定验证密钥的最大概率(通过假设可以忽略不计)。此外,Pr[A break Sig]也可以忽略不计的假设。
在mDBDH输入
上,B的目标是确定是否满足
。B设置A的全局参数如下:组的描述
,它们的素数
,以及映射:
,
,
。系统参数为
,其中
,
为来自
的随机数。
安全参数为
。在一个Bi-PRES-CCA-M游戏中,B与A的交互如下(B模拟A的挑战者)。在接下来的游戏中,我们使用带星号的字母
表示一个未损坏的
对应的挑战密文。
哈希预言机:B构建以下预言机。
阶段1:B构建了以下的预言机。
如果
,那么
,B用
回应A。
如果
,B解析
。如果
,B输出
并终止;否则,B检查是否满足
。如果是这样,B报告“失败”并终止。否则,B在表
中找到
,并且计算:%7D%7D%2CH_%7B2%7D(A))%7D%0A%3D%5Cfrac%7Be(g%2CH_%7B2%7D(A))%5E%7Br%7D%5Ccdot%20m%7D%7Be((H_%7B3%7D(A)%5E%7Br%7D)%5E%7B1%2Fr%5E%7B(3)%7D%7D%2CH_%7B2%7D(A))%7D%0A%3D%5Cfrac%7Be(g%2CH_%7B2%7D(A))%5E%7Br%7D%5Ccdot%20m%7D%7Be((g%5E%7Br%5E%7B(3)%5Ccdot%20r%7D%7D)%5E%7B1%2Fr%5E%7B(3)%7D%7D%2CH_%7B2%7D(A))%7D%3Dm)
挑战:在某个时候,A输出一个挑战元组
,如果
不在表
中,或
;B终止。否则,B选择一个随机数
,然后用如下数据回应A:
如果
挑战:在某个时候,A输出一个挑战元组
其中
为表
中w对应的值,
为表
中
对应的值,
为表
中
对应的值。
阶段2。B构建了以下的预言机。
猜测:最后,对手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不需要参与该过程。
在某些情况下,用户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方案的安全性来保证。
在某些情况下,汇聚节点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方案比我们的方案更复杂,效率更低。