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

1、第二章 预备知识第二章 预备知识数学理论是现代密码学建立和发展的基础，包括复杂性理论、可证明安全理论等，这些理论中的许多概念在设计密码算法时是必不可少的。本章主要介绍本本文中可能会用到的一些基本概念和结论，并介绍公钥密码体制以及代理重加密体制的相关定义。最后，本章讨论了密码系统中存在的密钥泄露问题。2.1 复杂性理论在计算机中，某一个算法执行的时间是以比特运算的形式来测量的。为完成某一个算法而需要的必要的比特运算数量，称为这个算法的计算复杂性或简称复杂性。它确切定义了求解一个问题是计算“容易”还是“困难”的，并由此对问题和算法的复杂性加以分类。由于算法的计算复杂性是正整数的函数，因此要比较两个

2、算法的计算复杂性主要是比较当 x 充分大时，它们随 x 增大而增大的数量级。定义定义 2.1 令函数以及，如果是正整数，且 c 是常数，有时，则将记作，或简写为。是对算法复杂性的一个数量级分类，它表示算法所需的比特运算次数的上界，与计算机的操作时间，运行速度等固有的性质无关。在复杂性的分析过程中，我们需要知道执行某个算法的确切的比特运算次数。计算机执行某个算法所需的时间，是和比特元素的数量成正比的。这个比例常数和计算机的性能有关。在执行一个算法的过程中，基本的时间估计是多项式时间的，或简称多项式的。一般来说，由于这些算法是最快的算法，因此它们都是可取的，即多项式时间算法是有效的算法。多项式时间

3、算法是对基本的加、减、乘、除运算而言的算法。然而，有些算法的复杂性是，其中，c 为常数且f 是一个关于的多项式，即为指数时间算法，或简称为指数的。一个亚指数时间算法是，其中，c 为常数表示满足的函数。假设输入算法的最大比特长度为，则，这是指数时间算法。超多项式时间算法的概念为若一个算法的复杂性为，其中 c 为常数，是介于常数和线性函数之间的函数。对现在已知的密码体制有效的攻击算法都是超多项式时间算法，但是并没有证明不存在有效的多项式时间攻击算法。下面给出关于 的一些性质：假定 f 和 g 是正多项式，则有(1) 若，则有；(2) ；(3) 。证明：（1）若，则有常数和正整数，若，。因此，可得，

4、即。（2）令，则存在和正整数，使得当时，。因此， ，故可得。（3）令，则存在和正整数，使得当时，。因此，即。上述性质中的（1）是（3）在下的特殊情况。同样，如果，则对任意的，成立。计算复杂性是计算机科学的重要组成部分，同时也是密码学的理论基础之一。Shannon 曾指出，设计一个密码的本质上要寻找一个难解的问题。这一推断揭示了密码的安全性与计算复杂性之间的相互依赖关系。公钥密码的出现，开拓了直接利用 NPC 问题设计密码的技术路线。在当今的计算机网络时代，密码的编制和分析都利用计算机网络来进行。在这种情况下，计算复杂性理论的发展将直接影响到密码的安全，计算复杂性理论作为密码的一种理论基础将发挥

5、越来越大的作用。2.2 可证明安全理论本小节将列出本文可能涉及的各类困难问题，如无特殊说明，均假设这些问题是难解的，并称为对应的困难问题假设。然后，介绍形式化证明方法。2.2.1 困难问题假设群：S 是一个非空集合， 表示异或操作，表示一个群，如果(1) 闭包：；(2) 结合性：；(3) 恒等性：；(4) 反身性：。阶：一个群中元素的个数称为阶。第二章 预备知识循环群：令 为阶为 q 的群，各不相同，则 称为循环群，g为群 的生成元。定义定义 2.2 对任意已知元素，有，求整数，即为DL(Discrete Logarithm)难解问题。离散对数假设意味着在群上的离散对数困难问题不能够被敌手以不

6、可忽略的概率解决。定义定义 2.3 令为一个阶为 q 循环乘法群，群上的 CDH（Computational Diffie-Hellman）问题是已知二元组（未知） ，求解。设在时间 t 内敌手成功输出的概率为：，其中是可忽略的。如果 可忽略不计，则 CDH 问题是是难解的。定义定义 2.4 令为一个阶为 q 循环群，已知，其中不可知，判断输出与是否一致，即为 DDH（Decisional Diffie-Hellman）难解问题。定义定义 2.5 令为一个阶为 q 循环群，已知，求解，即 s-CDH（s-Computational Diffie-Hellman）难解问题，其中 是在 中随机选择

7、的。特别地，当 s=2 时，称 s-CDH 问题称为平方-CDH 问题。定义定义 2.6 令 为一个阶为 q 循环群，已知，其中是不可知的，P-CDH 问题意味着计算是困难的。定义定义 2.7 令为一个阶为 q 循环群，已知，其中是不可知的，P-DDH 问题意味着判断是否成立是困难的。定义定义 2.8 如果映射满足如下性质，则认为该映射是一个双线性映射（Bilinear Map）：(1)都代表群，且具有相同的素数阶 q；(2) 对所有的，等式成立；(3) 该映射是非退化的，即；(4) 映射 e 是高效可计算的。一般地，Weil 对Error! Reference source not foun

8、d.和 Tate 对Error! Reference source not found.可被用于构建双线性映射 e。定义定义 2.9 令为循环加法群，阶为 q，生成元为 P，已知，其中是不可知的，求解，即中的 CDH 问题。定义定义 2.10 令为循环加法群，阶为 q，生成元为 P，已知，其中是不可知的，然后判定等式是否满足，即中的 DDH 问题。定义定义 2.11 令为循环加法群，阶为 q，生成元为 P，在 DDH Oracle 的协助下，计算已知元组的 CDH 难题，即 GDH（gap Diffie-Hellman）问题。定义定义 2.12 令为循环加法群，阶为 q，生成元为 P，已知，求

9、解，即 q-SDH（q-strong Diffie-Hellman）问题。令、分别是阶为 q 的循环加/乘法群，双线性映射以及群生成元为 P：定义定义 2.13 已知，其中是不可知的，求解，即 BDH（Bilinear Diffie-Hellman）问题。定义定义 2.14 已知，其中是不可知的，判定等式是否成立，即 DBDH（Decisional Bilinear Diffie-Hellman）问题。定义定义 2.15 在 DBDH 预言机的协助下，求解给定的 BDH问题，即 GBDH 问题。2.2.2 形式化证明方法在可证明安全理论中，形式化安全模型被用来评估一个密码系统的安全性。一个形式

10、化的安全模型包含两个定义Error! Reference source not found.Error! Reference source not found.：一方面，它必须指出任意概率的敌手如何与密码系统中的合法用户进行多项式时间的应答/响应；另一方面，它必须说明该攻击者要达到哪些目的，才能认定该密码系统被攻破。一般来说，有两种方式来描述形式化的安全模型。一种是基于游戏（game-based）的方式。在这种形式化安全模型中，攻击者需要与一个假定的概率算法（挑战者）进行交互。挑战者初始化密码系统中使用的全部密钥，可能响应来自攻击者的询问。当攻击者终止时，游戏结束，然后，评估此时的攻击者是否具

11、备破坏该密码系统的能力。如果一个密码系统是安全的，那么我们必须给出说明任意一个攻击者能够弱化该密码系统的可能性都非常小。基于游戏的安全模型已经被广泛接受，且已被应用于多种类型的密码系统的安全性证明，包括数字签名、非对称加密和对称加密。本文所描述的形式化安全模型都是基于游戏的安全模型。基于游戏的安全模型的优点是容易理解和实现。然而，Canetti 等Error! Reference source not found.发现基于游戏安全模型下的安全性证明只能独立的证明密码系统的安全性，无法说明当该密码系统部署于复杂环境下时也是可证明安全的。大部分密第二章 预备知识码方案都不是独立存在的，而是作为大型

12、计算机系统的子程序。在这种情况下，为了确保所使用的密码算法的安全性，必须要在给定的复杂环境下进行安全性证明。因此，对于基于游戏的安全模型而言，它往往难以更好的表述大型复杂环境的安全需求。另一种是基于仿真(simulation-based)的方式。假设一个密码系统中一个任意概率的攻击者能够与该密码系统中的每个算法进行多项式时间的交互，并且其它各方也可能多项式时间的访问密码系统的算法。我们假设存在一个理想化的密码系统，该密码系统永远都不会被攻破。它不是一个实际的系统，通常会涉及到使用一个抽象的可信第三方来确保数据被安全的传输，并且该可信第三方所进行的操作对攻击者和其它各方而言是透明的。为了判断一个

13、密码方案是否安全，攻击者和其它各方需要分别与真实的密码系统和理想化的密码系统进行多项式时间的交互，然后，检查攻击者和其它各方的输出。由于理想化的密码系统不可能被攻破，如果在真实密码系统下攻击者和其它各方的输出与在理想化密码系统下的输出结果大致相同，那么这一真实的密码系统是可证明安全的。因此，我们认为一个密码系统是安全的，当且仅当上面两种输出是不可区分的或者可区分的概率极小。应该明确，基于仿真的安全模型比基于游戏的安全模型更强。特别地，基于仿真的安全模型提供的安全性证明考虑到了部署于复杂环境下密码系统，为该密码系统提供了更可靠的安全保障。目前，一些基于仿真的安全模型被广泛使用Error! Ref

14、erence source not found.。然而，已被证明，某些密码函数无法在基于仿真的安全模型下可证明安全Error! Reference source not found.Error! Reference source not found.。显示一个密码体制安全的现代方法是可证明安全性。可证明安全性的目的在于证明：如果一个敌手能够攻破一个密码体制的某个安全概念，那么就可以利用该敌手解决某个工人的数学困难问题。例如，如果一个敌手能够在选择密文攻击下攻破 RSA 的语义安全性，那么就可以利用该敌手分解大整数；可证明安全的思想就是给定一个算法 A，提出一个新算法 C，C 把 A 作为子程序

15、。输入给 C 的是希望解决的困难问题，输入给 A 的是某个密码算法。然而，如果 A 是一个积极攻击敌手（选择密文攻击敌手或者适应性选择密文攻击敌手） ，即 A 可以对输入公钥进行解密预言机询问或签名预言机询问。算法 C 要想使用A 作为子程序，就得对 A 的询问提供回答。算法 C 需要应对以下四个问题：为了回避这个问题，可以使用随机预言机模型。随机预言是一个理想的 Hash函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如果问相同的询问两次，那么回答仍然相同。在随机预言机模型中，假设敌手并不使用密码算法中定义的那个 Hash 函数。也就是所，即使将随机预言换成真实的 Hash 函数。

16、敌手 A 也是成功的。对于 A 的解密预言询问或者签名预言询问，算法 C 是通过欺骗随机预言的回答来适合自己的需要的。随机预言模型为证明密码体制的安全性提供了一个很好的方法，但是随机预言模型并不反映真实世界的计算。在随机预言模型下安全的密码体制只能说是可能在真实的世界是安全的，不能确保一定在真实的世界是安全的。文献给出了在随机预言模型下安全的密码体制在真实的世界中不安全的例子。许多密码学研究者开始设计在标准模型（不依赖于随机预言模型）下安全的密码体制。移除随机预言模型是需要代价的，通常需要更强的困难问题假设，而且在标准模型下的密码体制通常效率较低。 2.3 公钥密码体制在对称密码体制中，或者与

17、相同，或者可以容易地从中导出。从而，或者的泄露会导致系统的不安全。公钥密码体制Error! Reference source not found.（Public Key Cryptography，PKC）的提出在整个密码学发展历史中具有里程碑式的意义。在公钥密码体制中，可以扎到一个密码体制，使得由给定的来求是计算不可行的。PKC 的优势为通信发送发能够用通信接收方的公钥加密明文消息并发送给接收方，然后，接收方用其私钥解密。2.3.1 PKE 定义定义定义 2.16 公钥加密方案（Public Key Encryption，PKE）. 一个 PKE 方案由概率算法、组成:(1) 密钥生成算法：输

18、入，输出，记为；(2) 加密算法：输入及，输出密文 ，记为；(3) 解密算法：输入 c 以及 sk，输出 m 或符号 ，表示解密失败，记为。 对于每一个 n，输出的每一组密钥对，以及每一个明文m，等式总是成立。2.3.2 PKE 安全性对于任一公钥加密方案（KeyGen，Enc，Dec） ，其安全性依赖于攻击者的能力。针对一个 PKE 方案的主动攻击有以下三种方式，这些方式被用于分析密码系第二章 预备知识统的安全性。定义定义 2.17 选择明文攻击（）已知一个加密预言机，敌手任意选取消息，并询问加密预言机，从而产生对应密文。当结束询问预言机后，敌手的目标是基于已经掌握的明-密文对破坏密码系统的

19、安全性。定义定义 2.18 选择密文攻击（）选择密文攻击也称为午餐时间攻击，是一种比选择明文攻击稍强的攻击模型。在选择密文攻击中，敌手可以访问一个黑盒，这个黑盒能进行解密。在午餐时间，敌手可以选择多项式个密文来询问解密盒，解密盒把解密后的明文发送给敌手。在下午时间，敌手被告知一个目标密文，要求敌手在没有解密盒的情况下解密目标密文，或者找到关于明文的有用信息。 已知一个解密预言机，敌手任意选取密文，并询问解密预言机，从而产生对应的明文。敌手的目标是利用已获得的明-密文对破坏密码系统的安全性。当敌手结束解密预言机询问后，如果敌手能够从给定的目标密文中获得相应的明文消息，则认为攻击成功。也就是说，一

20、旦敌手接收到目标密文，攻击者的解密帮助能力将不可用。定义定义 2.19 适应性选择密文攻击（）相比 CCA，CCA2 是一种更强的攻击模型，且 CCA2 中的敌手能够一直询问解密预言机，但不包括对目标密文的询问。目前普遍认为，任何新提出的公钥加密算法都应该在适应性选择密文攻击下达到多项式安全性。2.4 代理重加密体制1998 年，Blaze 等人Error! Reference source not found.在欧密会上率先提出了代理重加密（Proxy Re-Encryption，PRE）的概念。在代理重加密体制中，一个半可信代理者（Proxy）扮演着密文转换的角色，它可以将由委托者（Del

21、egator）公钥加密的密文转换为被委托者（Delegatee）对同一明文加密的密文，然后被委托者可利用其自身私钥解密该转换后的密文。在转换过程中，代理者必须拥有一个由委托者授权的针对被委托者的密文转换密钥（即代理重加密密钥） ，同时，该代理者无法获知关于密文中对应明文的任何信息。然而，在文献Error! Reference source not found.中，Blaze 等人并没能给出规范的形式化定义，从而导致 PRE 在 19982004 年间发展缓慢Error! Reference source not found.Error! Reference source not found.E

22、rror! Reference source not found.。直到2005 年，Ateniese 等人Error! Reference source not found.在 NDSS05 上第一次对代理重加密进行了形式化定义。此后，代理重加密成为密码学和信息安全领域的一个研究热点，积累了大量研究成果。本节将对 PRE 的形式化定义、安全模型以及特性进行简要描述。2.4.1 形式化定义定义定义 2.20 代理重加密（Proxy Re-Encryption，PRE）. 一个 PRE 方案可由算法、构成： (1)：输入安全参数，密钥生成算法为用户 i 输出一对公/私钥；(2)：输入 Alice

23、 的公/私钥对和Bob 的公/私钥对（其中，是可选的） ，代理重加密密钥生成算法输出一个代理重加密密钥。注：此时，Alice 为委托者，Bob 为被委托者；(3)：输入用户 i 公钥和消息，加密算法输出消息 m 的密文；(4)：输入一个代理重加密密钥和 Alice 的密文，代理重加密算法输出针对 Bob 的重加密密文；(5)：输入用户 i 的私钥和密文 ，解密算法输出消息 m 或错误符号 表明密文 不合法。注：、和与公钥加密算法Error! Reference source not found.Error! Reference source not found.Error! Reference

24、 source not found.一致。正确性：对任意明文空间中的消息和任意两对公/私钥，上述的正确性必须满足如下两个条件：，。如图 2.1 所示，在上述代理重加密定义中，一个拥有代理重加密密钥的半可信代理者能够将 Alice 公钥下的密文重加密为 Bob 公钥下针对同一明文的密文。然后，Bob 能够解密并获得消息，同时，该代理者无法获得任何信息（如：，和 m） 。图 2.1 代理重加密系统模型 在上述 PRE 定义的算法中，被委托者 Bob 的私钥是可选的。一般地，Apk当 Bob 的私钥不参与代理重加密密钥生成时，该代理重加密方案具有单向性和非交互性；相反地，算法输出一个双向代理重加密密

25、钥，且该 PRE 方案具有交互性。此外，算法和算法输出的密文空间分别为和，当Error! Reference source not 第二章 预备知识found.Error! Reference source not found.时，算法和算法的输出具有相同的密文空间，只需一个解密算法就可以同时解密上述两种算法输出的密文；而当Error! Reference source not found.时，针对和算法，则需要两个不同的算法。2.4.2 特性在文献 Error! Reference source not found.Error! Reference source not found.中，At

26、eniese 等人描述了一些一个 PRE 方案应该具备的特性，下面将依据上述代理重加密的定义对 PRE 的 9 个重要特性进行介绍：(1) 单向性（Unidirectional）：在一个单向 PRE 方案中，代理重加密密钥是单向的，即代理者可以利用一个单向代理重加密密钥将 Alice 的密文转换为 Bob 的密文，而不能将 Bob 的密文转换为 Alice 的密文；相反地，双向（Bidirectional）PRE 不仅允许代理者将 Alice 的密文转换为Bob 的密文，而且反之亦然；(2) 复用性（Multi-use）：在一个复用 PRE 方案中，算法和算法的输出结果都可以再次作为算法的输入

27、；反之，单用（Single-use）PRE 只允许加密算法的输出作为算法的输入；(3) 秘密代理（Private-proxy）：在一个秘密代理重加密中，代理者是诚实的且能够确保代理重加密密钥的隐私性，即攻击者无法从密文转换过程中获取代理重加密密钥；反之，在公开代理（Public-proxy）PRE 中，攻击者可以通过观察代理者的输入与输出计算出代理重加密密钥；(4) 透明性（Transparent）：在一个具有透明性的 PRE 方案中，代理者是透明的，即由算法输出的密文与由算法输出的密文在计算上是不可区分的；(5) 密钥优化（Key-optimal）：在密钥优化的 PRE 方案中，不论存在多少

28、委托者或被委托者，用户只需保护和存储的少量的秘密数据；(6) 非交互性（Non-interactive）：在非交互性的 PRE 方案中，代理重加密密钥由委托者的公/私钥对和被委托者的公钥产生，即被委托者不参与代理重加密密钥的授权过程；(7) 非传递性（Non-transitive）：在非传递性 PRE 方案中，代理重加密密钥具有非传递性，即给定的代理重加密密钥和的代理重加密密钥，代理者无法通过计算得到的代理重加密密钥；(8) 暂时性（Temporary）：在暂时性的 PRE 方案中，代理重加密密钥是可撤销的，即委托者有权收回委托出去的解密授权；(9) 抗合谋攻击（Collusion-resis

29、tant）：在抗合谋攻击的 PRE 方案中，代理重加密密钥能够抵抗合谋攻击，即当被委托者与代理者合谋时，二者无法揭露委托者的私钥和明文信息。2.4.3 安全模型Canetti 和 HohenbergerError! Reference source not found.给出了针对双向、多用代理重加密的适应性选择密文攻击安全模型（CCA2） 。在该安全模型中，他们提出了挑战后继（Derivatives of the Challenge）的概念，即所有与挑战相关联的都是的后继，这一概念影响着安全模型中随机预言机的限制条件的定义。由于代理重加密存在和两种加密算法，所以挑战密文后继在代理重加密的安全模

30、型中意义重大。定义定义 2.21 挑战密文后继（Derivatives of the Challenge Ciphertext）. (1)是其自身的一个后继；(2) 如果存在是的一个后继，而又是的一个后继，那么是的一个后继；(3) 如果敌手已经发送一个询问请求到重加密预言机，并且得到了询问结果 ，那么是的一个后继；(4) 如果敌手已经发送一个询问请求到重加密密钥生成预言机，并且，那么是所有的一个后继。下面通过一个敌手和挑战者 之间的安全游戏 Unidirectional-PRE-CCA2 来定义单向代理重加密方案语义安全于适应性选择密文攻击（IND-CCA2） 。安全游戏分为如下几个阶段：阶段

31、阶段 1 1：敌手可以适应性地向挑战者 提出一系列询问请求，其中，某个 的询问过程如下： 公钥生成预言机：敌手输入索引 i，挑战者 执行 KeyGen 算法，输入安全参数，输出一对公/私钥。然后， 发送到，并将记录到表中。 私钥生成预言机：敌手输入一个公钥，挑战者 在表中查找并将其对应的私钥返回给。这里通过公钥查询预言机得到。 代理重加密密钥生成预言机：敌手以作为输入，挑战者第二章 预备知识首先查找表中对应的私钥，然后执行 ReKey 算法，并将一个代理重加密密钥返回给。这里和都是的输出。 代理重加密预言机：敌手以作为输入，挑战者 执行ReKey 和 ReEncrypt 算法，并返回一个重加密

32、密文到。这里和都是的输出，是对应的私钥。 解密查询预言机：敌手以作为输入，挑战者 首先查找表中对应的私钥，然后执行 Decrypt 算法，并返回到。这里是的输出。敌手的上述询问是适应性的，即对第 i 次询问的回答可以依赖于前 i-1 次iq的询问。挑战阶段挑战阶段：一旦敌手决定结束阶段阶段 1，将从明文空间中选择两个等长的明文消息，和一个公钥为的挑战用户。挑战者 选择一个随机比特C C并计算，然后 返回 到。此外，对于的选择将有如下限制：(1) 在阶段阶段 1 中，敌手不曾将挑战用户的公钥作为私钥查询预言机的输入；(2) 敌手不允许选择可以导致间接平凡解密下密文的挑战用户（例如，敌手可能通过多

33、次和查询将下的密文转换成查询过的某个公钥下的密文，从而使解密操作很容易实现，此类是不被允许的） 。阶段阶段 2：敌手适应性地向挑战者 提出更多的询问，其中，某个 询问过程如下：挑战者 的回答与阶段阶段 1 一致；：敌手输入一个公钥，如果且和分别不曾作为和的输入，那么，挑战者 的回答与阶段阶段 1 一致。这里是的后继；：敌手以作为输入，如果，则挑战者 拒绝回答；否则， 的回答与阶段阶段 1 一致；：敌手以作为输入，若是的一个后继，则挑战者 拒绝回答；否则， 的回答与阶段阶段 1 一致；：敌手以作为输入，若不是的一个后继，挑战者 的回答与阶段阶段 1 一致。猜测阶段猜测阶段：敌手返回一个猜测结果，

34、若，则敌手在Unidirectional-PRE-CCA2 游戏中获胜。将上述安全游戏中的敌手定义为一个 Unidirectional-PRE-CCA2 敌手，则敌手攻破安全参数为的单向代理重加密的优势为定义定义 2.22 （Unidirectional-PRE-CCA2 安全）.一个单向代理重加密方案是语义安全于适应性选择密文攻击的（Unidirectional-PRE-CCA2 安全） ，当且仅当不存在任意一个多项式时间的 Unidirectional-PRE-CCA2 敌手能够以不可忽略的优势攻破一个单向 PRE 方案。定义定义 2.23 （Unidirectional-PRE-CA 安

35、全）. 若对于任意一个多项式时间的敌手，如下概率都是可以忽略的，则声明一个单向代理重加密方案是抗合谋攻击安全的（Unidirectional-PRE-CA 安全） 。.定义定义 2.24 （Unidirectional-PRE-Full 安全）. 若一个代理重加密方案同时具备 Unidirectional-PRE-CCA 安全和 Unidirectional-PRE-CA 安全，则声明该单向代理重加密方案是完全安全的（Unidirectional-PRE-Full 安全） 。2.4.4 PRE 方案对比(1) 特性对比本文在本章 2.4.2 节中描述了代理重加密的 9 个特性，本节将据此对现有

36、的代理重加密方案进行对比分析。表 2-1 中列举了当前具有代表性的代理重加密方案。表 2-1 代理重加密方案的特性对比方案123456789Error! Reference source not found.NoYesYesYesYesNoNoNoNoError! YesNoYesYesYesYesYesNoYes第二章 预备知识Reference source not found.-1Error! Reference source not found.-2YesNoYesYesYesYesYesNoYesError! Reference source not found. YesNoYesY

37、esYesYesYesYesYesError! Reference source not found.-1NoYesNoYesYesNoNoNoNoError! Reference source not found.-2NoYesNoYesYesNoNoNoNoError! Reference source not found.-1YesNoYesNoYesYesNoNoYesError! Reference source not found.-2YesNoYesNoYesYesNoYesYesError! Reference source not found.NoNoYesNoYesNoNo

38、NoNoError! Reference source not found.-1YesNoYesYesNoYesYesNoYesError! Reference source not found.-YesNoYesYesNoYesYesYesYes第二章 预备知识2Error! Reference source not found.YesNoYesYesYesYesYesNoYesError! Reference source not found.YesNoYesYesYesYesYesNoYesError! Reference source not found.YesYesYesNoYesY

39、esYesNoYesError! Reference source not found.YesNoYesYesYesYesYesNoYesError! Reference source not found.YesNoYesNoYesYesYesNoYes从表 2-1 中，我们可以直观地发现，目前还没有一个代理重加密方案能够同时满足这 9 个特性。但随着研究的深入，方案能够满足的特性也越来越多。其中，复用性可以提高方案执行效率，暂时性可以增强方案的灵活性和实用性。然而，表 1 中仅有 4 个方案满足复用性，3 个方案满足暂时性。因此，对于这两个特性还需要进一步关注。(2) 性能对比 本节从计算开

40、销、存储开销和安全性质三个方面比较、分析了表 2-1 中各个PRE 方案的性能，如表 2-2 与表 2-3 所示。在本节性能对比中，我们忽略了 hash运算、异或操作以及循环群上的乘法、加法运算，因为它们的计算开销远比指数运算和对运算要小。表中涉及的符号解释如下，p、e 和 ep：分别表示一个双线性对运算、一个指数运算以及一个上的指数运算的运行时间；s和 v：分别表示一次签名和一次签名验证所需的时间；S.enc 和 S.dec：分别表示执行一次对称加密和解密所需的时间；k、和：分别表示一个安全参数以及和的比特长度；、和：分别表示、以及中元素的长度； |s|和|：分别表示一次签名密钥和一次签名的

41、长度； |T|：时间戳的长度；：消息 m 的长度；|S.enc|：一次对称加密密文的长度；、和：分别表示安全素数模量的长度；ROM 和 STM：分别表示随机预言机模型和标准模型。通过观察表 2-2 和表 2-3，相比基于双线性对的代理重加密方案，那些不依靠这一计算昂贵的数学工具构造的代理重加密方案无论在计算开销还是存储开销方面都要高效很多。另外，在随机预言机模型下，文献Error! Reference source not found.Error! Reference source not found.中的代理重加密方案性能要优于其它方案，其满足 CCA 安全性，加解密效率较高，且密钥与密文长

42、度适中。在标准模型下，所有方案都是利用双线性对构造的，其中 Canetti 等人 Error! Reference source not found.构造的代理重加密方案性能较好，与其它几个方案相比，它的密钥和密文更短，计算效率更高。表 2-2 代理重加密方案的计算开销对比计算开销方案加密解密重加密重加密密文解密无双线性对Error! Reference source not 2e1e1e1e第二章 预备知识found.Error! Reference source not found.-11p+1e+2ep1p+1ep1p1epError! Reference source not foun

43、d.-21p+1e+2ep1p+1ep1p1epError! Reference source not found. 1p+1e+2ep1p+1ep1p1epError! Reference source not found.-11p+3e+1ep+1s5p+1e +1v4p+1e +1v5p+1e +1vError! Reference source not 1p+3e+1ep+1s5p+1e +1v4p+1e +1v5p+1e +1vfound.-2Error! Reference source not found.-11p+5e+1ep+1s3p+1e+1ep+1v2p+4e +1v5p

44、+1e+1ep+1vError! Reference source not found.-21p+5e+1ep+1s3p+1e+1ep+1v2p+4e +1v5p+1e+1ep+1vError! Reference source not found.3e4e3e2eError! Reference source not found.-15e5e4e4eError! Reference source 5e5e4e4e第二章 预备知识not found.-2Error! Reference source not found.3e4e3e4eError! Reference source not f

45、ound.7e+1s7e4e+1v7eError! Reference source not found.1p+2e+2ep+1s3p+3e+1ep+1v6p+6e+3ep+1s+1v9p+7e+3ep+3vError! Reference source not found.kp+2e+2ep+1s3p+4e+1ep7p+5e3p+2e+2epError! Reference source not found.1p+7e+1S.enc5p+1e+1ep4p+5e+1S.enc8p+3e+1ep+1S.dec表 2-3 代理重加密方案的计算开销对比密钥长度密文长度方案公钥私钥重加密密钥原密文重加

46、密密文安全性Error! Reference source not found.2CPA, ROM, CDHError! Reference source not found.-12CPA, ROM, q-DBDHIError! Reference source not found.-222CPA, ROM, e-DBDHError! Reference source not found. 222CPA, ROM, DBDHError! Refere33CCA, ROM, m-DBDH第二章 预备知识nce source not found.-1Error! Reference source

47、not found.-233CCA, STM, DBDHError! Reference source not found.-144RCCA, STM, 3-QDBDHError! Reference source not found.-244RCCA, STM, 4-QDBDHError! Reference source not found.2CCA, ROM, CDHError! 32CCA, ROM, Reference source not found.-1+2kDDHError! Reference source not found.-232+2kCCA, ROM, DDHErro

48、r! Reference source not found.2222CCA, ROM, CDHError! Reference source not found.222CCA, ROM, CDHError! Reference source not found.CCA, STM, 2-ABDHEError! RefereCCA, STM, 3-wDBDHI第二章 预备知识nce source not found.Error! Reference source not found.322CCA, STM, 6-AmDBDH2.5 密钥泄露2.5.1 问题描述对于密码系统而言，密钥泄露攻击被认为是

49、危害性最大的一类攻击，因为密码算法（如：加密、解密和签名生成等）通常被放到一个相对不安全的设备（如：移动设备或者联网设备）上来执行，而由此类设备维护的密钥将不可避免的发生泄露。因此，密钥泄露问题可能是密码学在实际应用中存在的最大威胁：相对于解决密码系统中的困难性问题，攻击者很容易从单纯、不设防的用户那里获得密钥。当今社会，随着越来越多的用户使用移动互联设备，密钥泄露问题的威胁也随之增加。2.5.2 解决方法针对公钥密码体制存在的密钥泄露问题，通常存在三种解决方法：1、 在线密钥生成中心：在线密钥生成中心是一个协助用户实现密钥更新的可信机构。然而，当系统中的用户量不断增加时，密钥生成中心将承受巨大的计算、通信开销负荷，严重将导致系统瘫痪。此外，用户与 PKG交互时也会牺牲大量的通信开销。2、 分布式密钥存储技术：下面介绍了基于分布式存储技术的三种抗密钥泄露方法，(1) 秘密共享（Secret Sharing）技术Error! Reference