公钥密码体制的研究(2)

第二章 预备知识

率的攻击者能够与该密码系统中的每个算法进行多项式时间的交互，并且其它各方也可能多项式时间的访问密码系统的算法。我们假设存在一个理想化的密码系统，该密码系统永远都不会被攻破。它不是一个实际的系统，通常会涉及到使用一个抽象的可信第三方来确保数据被安全的传输，并且该可信第三方所进行的操作对攻击者和其它各方而言是透明的。为了判断一个密码方案是否安全，攻击者和其它各方需要分别与真实的密码系统和理想化的密码系统进行多项式时间的交互，然后，检查攻击者和其它各方的输出。由于理想化的密码系统不可能被攻破，如果在真实密码系统下攻击者和其它各方的输出与在理想化密码系统下的输出结果大致相同，那么这一真实的密码系统是可证明安全的。因此，我们认为一个密码系统是安全的，当且仅当上面两种输出是不可区分的或者可区分的概率极小。

应该明确，基于仿真的安全模型比基于游戏的安全模型更强。特别地，基于仿真的安全模型提供的安全性证明考虑到了部署于复杂环境下密码系统，为该密码系统提供了更可靠的安全保障。目前，一些基于仿真的安全模型被广泛使用错误！

未找到引用源。

。然而，已被证明，某些密码函数无法在基于仿真的安全模型下可证明安

全错误！未找到引用源。错误！未找到引用源。。

显示一个密码体制安全的现代方法是可证明安全性。可证明安全性的目的在于证明：如果一个敌手能够攻破一个密码体制的某个安全概念，那么就可以利用该敌手解决某个工人的数学困难问题。例如，如果一个敌手能够在选择密文攻击下攻破RSA的语义安全性，那么就可以利用该敌手分解大整数；

可证明安全的思想就是给定一个算法A，提出一个新算法C，C把A作为子程序。输入给C的是希望解决的困难问题，输入给A的是某个密码算法。然而，如果A是一个积极攻击敌手（选择密文攻击敌手或者适应性选择密文攻击敌手），即A可以对输入公钥进行解密预言机询问或签名预言机询问。算法C要想使用A作为子程序，就得对A的询问提供回答。算法C需要应对以下四个问题：

为了回避这个问题，可以使用随机预言机模型。随机预言是一个理想的Hash函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如果问相同的询问两次，那么回答仍然相同。在随机预言机模型中，假设敌手并不使用密码算法中定义的那个Hash函数。也就是所，即使将随机预言换成真实的Hash函数。敌手A也是成功的。对于A的解密预言询问或者签名预言询问，算法C是通过欺骗随机预言的回答来适合自己的需要的。

随机预言模型为证明密码体制的安全性提供了一个很好的方法，但是随机预言模型并不反映真实世界的计算。在随机预言模型下安全的密码体制只能说是可能在真实的世界是安全的，不能确保一定在真实的世界是安全的。文献给出了在

随机预言模型下安全的密码体制在真实的世界中不安全的例子。许多密码学研究者开始设计在标准模型（不依赖于随机预言模型）下安全的密码体制。移除随机预言模型是需要代价的，通常需要更强的困难问题假设，而且在标准模型下的密码体制通常效率较低。

2.3 公钥密码体制

在对称密码体制中，或者

或者与

相同，或者可以容易地从

中导出。从而，

的泄露会导致系统的不安全。公钥密码体制错误！未找到引用源。（Public Key

来求

是计算不可行的。

Cryptography，PKC）的提出在整个密码学发展历史中具有里程碑式的意义。在公钥密码体制中，可以扎到一个密码体制，使得由给定的方，然后，接收方用其私钥解密。

PKC的优势为通信发送发能够用通信接收方的公钥加密明文消息并发送给接收

2.3.1 PKE定义

定义 2.16 公钥加密方案（Public Key Encryption，PKE）. 一个PKE方案由概率算法

(2) 加密算法(3) 解密算法 对于每一个n，等式

、、：输入。

组成: ：输入，输出

及

，记为

；

；

，输出密文，记为

(1) 密钥生成算法

：输入c以及sk，输出m或符号，表示解密失败，记为

输出的每一组密钥对总是成立。

，以及每一个明文m，

2.3.2 PKE安全性

对于任一公钥加密方案（KeyGen，Enc，Dec），其安全性依赖于攻击者的能力。针对一个PKE方案的主动攻击有以下三种方式，这些方式被用于分析密码系统的安全性。

定义 2.17 选择明文攻击（

）已知一个加密预言

机，敌手任意选取消息，并询问加密预言机，从而产生对应密文。当结束询问预言机后，敌手的目标是基于已经掌握的明-密文对破坏密码系统的安全性。

定义 2.18 选择密文攻击（

）选择密文攻击也

称为午餐时间攻击，是一种比选择明文攻击稍强的攻击模型。在选择密文攻击中，敌手可以访问一个黑盒，这个黑盒能进行解密。在午餐时间，敌手可以选择多项

第二章 预备知识

式个密文来询问解密盒，解密盒把解密后的明文发送给敌手。在下午时间，敌手被告知一个目标密文，要求敌手在没有解密盒的情况下解密目标密文，或者找到关于明文的有用信息。 已知一个解密预言机，敌手任意选取密文，并询问解密预言机，从而产生对应的明文。敌手的目标是利用已获得的明-密文对破坏密码系统的安全性。当敌手结束解密预言机询问后，如果敌手能够从给定的目标密文中获得相应的明文消息，则认为攻击成功。也就是说，一旦敌手接收到目标密文，攻击者的解密帮助能力将不可用。

定义 2.19 适应性选择密文攻击（

）

相比CCA，CCA2是一种更强的攻击模型，且CCA2中的敌手能够一直询问解密预言机，但不包括对目标密文的询问。目前普遍认为，任何新提出的公钥加密算法都应该在适应性选择密文攻击下达到多项式安全性。

2.4 代理重加密体制

1998年，Blaze等人错误！未找到引用源。在欧密会上率先提出了代理重加密（Proxy Re-Encryption，PRE）的概念。在代理重加密体制中，一个半可信代理者（Proxy）扮演着密文转换的角色，它可以将由委托者（Delegator）公钥加密的密文转换为被委托者（Delegatee）对同一明文加密的密文，然后被委托者可利用其自身私钥解密该转换后的密文。在转换过程中，代理者必须拥有一个由委托者授权的针对被委托者的密文转换密钥（即代理重加密密钥），同时，该代理者无法获知关于密文中对应明文的任何信息。然而，在文献错误！未找到引用源。中，Blaze等人并没能给出规范的形式化定义，从而导致PRE在1998~2004年间发展缓慢错误！未找到引用源。错误！未找到引用

源。错误！未找到引用源。

。直到2005年，Ateniese等人错误！未找到引用源。在NDSS′05上第一次对代

理重加密进行了形式化定义。此后，代理重加密成为密码学和信息安全领域的一个研究热点，积累了大量研究成果。本节将对PRE的形式化定义、安全模型以及特性进行简要描述。

2.4.1 形式化定义

定义 2.20 代理重加密（Proxy Re-Encryption，PRE）. 一个PRE方案可由算法

(1) (2)

Bob的公/私钥对

、、、、；

构成：

，密钥生成算法

为和

：输入安全参数，

用户i输出一对公/私钥

：输入Alice的公/私钥对

（其中，

是可选的），代理重加密密钥生成

算法(3)

输出一个代理重加密密钥

：输入用户i公钥

。注：此时，Alice为委托者，和消息

，加密算法

和Alice的密

； 输

Bob为被委托者； 输出消息m的密文(4)

文，代理重加密算法(5) 注：

引用源。

；

：输入一个代理重加密密钥：输入用户i的私钥

输出针对Bob的重加密密文

和密文，解密算法

出消息m或错误符号表明密文不合法。

、

和

与公钥加密算法错误！未找到引用源。错误！未找到引用源。错误！未找到

和任意两对公/私钥

，

。

如图2.1所示，在上述代理重加密定义中，一个拥有代理重加密密钥半可信代理者能够将Alice公钥下的密文

的密文

无法获得任何信息（如：

，

和m）。

图2.1 代理重加密系统模型

pkA 在上述PRE定义的Bob的私钥相反地，

算法和

引用源。

一致。

，上述的正确性必须满足如下两个条件：

正确性：对任意明文空间中的消息

的

重加密为Bob公钥下针对同一明文

，同时，该代理者

。然后，Bob能够解密并获得消息

算法中，被委托者Bob的私钥是可选的。一般地，当

不参与代理重加密密钥生成时，该代理重加密方案具有单向性和非交互性；算法输出一个双向代理重加密密钥，且该PRE方案具有交互性。此外，

算法输出的密文空间分别为

算法和

和

，当

错误！未找到引用源。错误！未找到

时，算法的输出具有相同的密文空间，只需一个解密算法

错误！未找到引用源。

就可以同时解密上述两种算法输出的密文；而当和

算法，则需要两个不同的

算法。

时，针对

2.4.2 特性

在文献错误！未找到引用源。错误！未找到引用源。中，Ateniese等人描述了一些一个PRE方案应该具备的特性，下面将依据上述代理重加密的定义对PRE的9个重要特性进行介绍：

(1) 单向性（Unidirectional）：在一个单向PRE方案中，代理重加密密钥是单