密码学报 ISSN 2095-7025 CN 0-95/TN E-mal: jcr@cacrnet.org.cn Journal of Cryptologc Research,204,(6):537 550 http://www.jcr.cacrnet.org.cn 密码学报 编辑部版权所有. Tel/Fax: +86-0-80330 公钥加密系统的可证明安全 新挑战新方法 刘胜利 上海交通大学计算机科学与工程系, 上海 200240 通讯作者 : 刘胜利, E-mal: sllu@sjtu.edu.cn 摘要 : 密码界对公钥加密所广泛接受的安全标准是 IND-CCA2 安全. 但是近年来各种新的攻击手段层出不穷, IND-CCA2 安全已不能应付这些攻击. 本文将对近年来出现的 选择打开攻击, 密钥泄漏攻击 密钥相关信息安全 密钥相关攻击 及 随机数相关攻击 进行阐述, 并介绍如何对这些攻击进行形式化, 如何定义能够抵御这些攻击的更高的安全标准, 包括 : 针对 选择打开攻击 的 基于仿真的选择打开 CCA2 安全 (SIM-SO-CCA2) 及 基于不可区分的选择打开 CCA2 安全 (IND-SO-CCA2); 针对 密钥泄漏攻击 的 容忍密钥泄漏 CCA2 安全 (LR-CCA2); 依赖密钥的消息的 CCA2 安全 (KDM-CCA2); 针对 密钥相关攻击 的 密钥相关 CCA2 安全 (KR-CCA2); 针对 随机数相关攻击 的 随机数相关 CCA2 安全 (RR-CCA2). 此外, 我们还简要介绍了目前达到新标准所使用的技术和方法, 包括交叉认证码技术 Hash Proof System 技术, One-Tme Lossy Flter 技术等, 同时指出了目前公钥加密可证明安全所面临的挑战. 关键词 : 公钥加密 ; 可证明安全 ; CCA2 安全中图法分类号 : TP309.7 文献标识码 : A DOI: 0.3868/j.cn.jcr.000050 中文引用格式 : 刘胜利. 公钥加密系统的可证明安全 新挑战新方法 [J]. 密码学报, 204, (6): 537 550. 英文引用格式 : Lu S L. Provable securty for publc ey encrypton challenges and approaches[j]. Journal of Cryptologc Research, 204, (6): 537 550. Provable Securty for Publc Key Encrypton Challenges and Approaches LIU Sheng-L Department of Computer Scence and Engneerng, Shangha Jao Tong Unversty, Shangha 200240, Chna Correspondng author: LIU Sheng-L, E-mal: sllu@sjtu.edu.cn Abstract: The wdely acceptable standard securty noton for publc ey encrypton s IND-CCA2 securty. Many new attacng technques are proposed n recent years, whch mpose new securty requrements beyond IND-CCA2. In ths survey, we descrbe some recent appeared attacs,.e., the Selectve-Openng Attacs, Key-Leaage Attacs, Key-Dependent Securty, Key-Related Attacs and Randomness-Related Attacs. We show how to formalze those attacs to get new securty models and set up new securty notons resstng those attacs. The formalzaton of Selectve-Openng Attacs gves the noton of Smulaton-based Selectve Openng 基金项目 : 国家自然科学基金 (670229, 637353, 63304); 高等学校博士学科点专项科研基金 (200073006); 上海市教委科研创新项目 (2ZZ02) 收稿日期 : 204-09-8 定稿日期 : 204--26
538 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 CCA2 (SIM-SO-CCA2) Securty and Indstngushable-based Selectve Openng CCA2 (IND-SO-CCA2); The formalzaton of Key-Leaage Attacs gves the noton of leaage-reslent CCA2 (LR-CCA2) Securty; The encrypton of Key-dependent messages arouses the noton of Key-Dependent Message CCA2 (KDM-CCA2) securty; The formalzaton of Key-Related Attacs gves the noton of Key-Related CCA2 (KR-CCA2) securty; The Randomness-Related Attacs gves the noton of Randomness-Related CCA2 (RR-CCA2) securty. In addton, we ntroduce the cryptographc prmtves to acheve those securty notons, and the prmtves nclude Cross-Authentcaton Codes, Hash Proof System, One-Tme Lossy Flter, etc. We also pont out the challenges for the provable securty of publc-ey encrypton. Key words: publc ey encrypton; provable securty; CCA2 securty 引言 公钥加密 (publc ey encrypton, PKE) 是密码领域中最重要的一个分支, 在信息安全中有着举足轻重的地位. 抗自适应选择密文攻击的语义安全 (semantc securty aganst adaptve chosen-cphertext attacs), 又称为 不可区分意义下的选择密文安全 (IND-CCA2) 已经成为公钥加密的标准. 标准模型下的 IND-CCA2 安全考虑的是通信两方之间的保密通信 : 发送方利用接收方的公钥对明文进行加密, 接收方利用自己的私钥对密文进行解密. 对敌手的能力的假设是 : 敌手可以自由选择两个长度相同的明文 M 0 和 M 提交给一个加密预言机. 同时敌手还拥有解密预言机 (decrypton oracle). 加密预言机随机选择一个比特 b, 对 M 进行加密得到挑战密文 C. 敌手可使用解密预言机对除 C 外的任意合法密文进行解密服务. 敌 b 手在这样一个解密预言机的帮助下来猜测 C 是对 M 0 还是 M 的加密. 如果任意概率多项式时间 (ppt) 的敌手猜测 b 成功的概率以可忽略的概率接近 2, 那么我们就称这个公钥加密方案在标准模型下是 IND-CCA2 安全. 实现 IND-CCA2 安全有多种通用方法 : Noar-Yung [] 利用非交互零知识证明 (NIZK) 的两把密钥的方法 ; Cramer 和 Shoup [2] 的 Unversal Hash Proof System(HPS) 方法 ; Boneh, Cannett, Halev, Katz [3 5] 使用基于身份的加密 (dentty based encrypton, IBE) 构造公钥加密 (PKE) 的 (B)CHK 方法 ; Peet 和 Waters [6] 的有损陷门函数 (Lossy Trapdoor Functon, LTDF) 构造法等等. 如果敌手没有解密预言机, 则上述 IND-CCA2 安全退化为 IND-CPA 安全 ; 如果敌手可以查询解密预言机, 但仅限于看到挑战密文之前, 则上述安全退化为 IND-CCA 安全. 对安全定义的形式化方法还包括语义安全 (Semantc Securty), 以及非延展安全 (Non-Malleablty Securty). 结合 CPA, CCA, CCA2 三种攻 [7] 击, 共有九种安全性定义. 这九种安全的关系由 Watanabe 等在 PKC 2003 上总结给出. 见图. 图 九种安全定义之间的关系 [7] Fgure Relaton among the nne securty notons [7]
刘胜利 : 公钥加密系统的可证明安全 新挑战新方法 539 从上图可以看出, 语义安全和不可区分安全是等价的. 而在敌手的 CCA2 攻击情况下, 三种不同的形式化定义又是等价的. 因此, 在证明 CCA2 安全时, 人们总会选择简洁易证的 IND-CCA2 安全. 在本文中, 为简单起见, 我们将 CCA2 写为 CCA. 2 公钥加密的 IND-CCA 安全以及新攻击和新要求 2. 公钥加密与 IND-CCA 安全 私钥 一个公钥加密方案包括三个算法 : 密钥生成算法 p,s ; 加密算法 M R 算法 C KeyGen p,s, 输入安全参数, 输出一对公 Enc p, ; C, 输入公钥 p 和明文 M 以及随机数 R, 输出相应的密文 C ; 解密 Dec s, M, 输入私钥 s 和密文 C, 输出所恢复的明文 M 或者一个解密失败的符号. 表 公钥加密方案算法 Table Algorthms of a Publc Key Encrypton Scheme 密钥生成算法加密算法解密算法 KeyGen p,s Encp, M ; R C Decs,C M 由于在 CCA2 攻击下, 语义安全 不可区分安全和不可延展安全是等价的. 所以我们介绍最简明的 IND-CCA2( 简记为 IND-CCA) 安全. IND-CCA 安全模型由下述实验 ( 或者称为 Game) 来刻画. 实验中有一个挑战者和一个敌手. 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 敌手. 解密阶段 : 敌手查询密文, C 挑战者调用解密算法 Decs,C 得到公私钥对, 并将公钥 p 发给 M 回复. 挑战阶段 : 敌手向挑战者提交两个长度相同的明文 M 0, M, 挑战者随机选择一个比特 b, 调用 加密算法加密, b M 得到挑战密文 C M R 解密阶段 2: 敌手查询密文 C, 但要限定 C. 猜测阶段 : 敌手猜测 b 的值 b. 如果敌手猜对 b b, 则敌人赢得了这个实验. =Enc p, ;. 挑战者将挑战密文 C 发给敌手. b C 挑战者调用解密算法 Decs,C M 回复. Fgure 2 图 2 PKE 的 IND-CCA 实验及安全模型 The IND-CCA experment of PKE and the securty model 定义 给定一个公钥加密方案 得上述实验的概率都以可以忽略的量接近 2, 即 PKE KeyGen, Enc, Dec. 如果任意的概率多项式时间 (ppt) 的敌手赢 Prob 2 bb neg 那么这个 PKE 方案就是 IND-CCA 的. 如果上述实验中没有解密阶段 和解密阶段 2, 那么 IND-CCA 安全就退化为 IND-CPA 安全 ; 如果上
540 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 述实验中只有解密阶段, 则 IND-CCA 安全退化为 IND-CCA. 2.2 IND-CCA 安全的研究现状 984 年, Goldwasser 和 Mcal [8] 提出了概率加密的公钥加密算法, 并给出了语义安全的形式化定义, 从此开启了公钥密码的可证明安全的新篇章. 两位学者也因此获得了 202 年的图灵奖. 990 年, Naor 和 Yung [] 提出了 CCA 攻击以及如何实现 IND-CCA 安全. 其思想是使用两把 密钥 对同一个明文进行加密, 也就是说, 用两个 IND-CPA 安全的公钥加密算法对同一个明文进行加密得两个密文, 同时使用非交互零知识证明 (NIZK) 来说明两个密文是对同一个明文的加密. 99 年 Racoff 和 Smon [9] 提出了 CCA2 攻击, 并指出 Noar-Yung 的方法可以扩展实现 IND-CCA2 安全, 只需要 NIZK 具有 Smulaton-Soundness 性质即可. 但是, 由于非交互零知识证明没有高效的实现方法, 所以 Noar-Yung 的方法具有理论价值但缺乏实际意义. 998 年, Cramer 和 Shoup 提出来第一个实用的 IND-CCA 安全的公钥加密方案, 它属于类 ElGamal 体制, 其安全性可以归约为 Decsonal Dffe-Hellman(DDH) 问题. 之后, Cramer 和 Shoup [2] 又将其设计思想扩展为 Hash Proof System(HPS). 其构造 PKE 的方法是使用两种类型的 HPS, 一个是 smooth HPS, 另一个是 2-unversal HPS. Smooth HPS 用于产生一个一次性密钥来掩盖明文, 而 2-unversal HPS 则用于检查密文的合法性. 基于这种方法, 可以构造出多种实用的 IND-CCA2 安全 PKE: 基于 Quadratc Resdue 假设的, 基于 Decsonal Composte Resdue 假设的等. 2006 年, Boneh, Cannett, Halev, Katz [3] 提出如何使用基于身份的加密 (IBE) 构造公钥加密 (PKE) 的 IBE IBE.Gen, IBE.Der, IBE.Enc, IBE.Dec 是具有弱的 selectve-id 的 CPA(IND-sID- BCHK 方法. 假设 CPA) 安全的基于身份的加密方案. 其中 IBE.Gen mp, ms IBE.Der ms, ID SK 算法都隐含了将 mp 作为公共输入 ; ID SK ; IBE 的加密算法 IBE.EncID,M ID ID 产生公开参数 mp 和主密钥 ms, 其它 对任意一个身份 ID, 利用主密钥产生私钥 输入身份信息和明文, 输出相应的密文 ; IBE 的解密算法 IBE.Dec SK, M 输入私钥和密文输出所恢复的明文 M 或者. 使用强的一次性签名方案 OTS OTS.Gen,OTS.Sgn,OTS.Ver 中的密钥产生算法 OTS.Gen 生成签名私钥和验证密钥对 s sg 时使得 v 作为 ID 对明文进行加密得到 =IBE.Encv, M, 再对 进行签名得到 =OTS.Sgn s sg,. 加密得到的密文为 v,,. 解密时, 先用 v 验证签名的正确性, 再使用 ms 得到密钥 s v IBE.DecSK v 的强不可伪造特性. 2.3 IND-CCA 安全的局限,v. 同 最终, 最后使用, 恢复明文. 所构造的公钥加密方案的安全性归约为 IBE 的 IND-sID-CPA 安全和一次签名 但是, IND-CCA 安全有如下的限定 : () 安全模型仅限于两方 : 发送方和接收方. 不适用于多用户的网络环境, 因此不会考虑敌人对多用户进行的主动渗透 (corrupton) 攻击 ; (2) 安全模型默认敌人所得到的私钥相关信息仅限于公钥 p 和解密预言机, 除了公钥信息以及解密服务 ( 解密预言机提供 ) 之外, 敌人没有关于私钥 s 的其它任何信息 ; (3) 挑战密文 C 所加密的信息不能是私钥直接参与计算所得到的函数值 f s. (4) 敌人不会影响解密算法中私钥 s 的使用方法. (5) 公钥加密中采用的随机数 R 是真正随机的.
刘胜利 : 公钥加密系统的可证明安全 新挑战新方法 54 网络化环境使得信息系统日趋复杂, 不同的环境对安全性能的要求也不尽相同, 采取的安全策略也具有多样性. 比如, 在多方安全计算环境中, 多个发方会使用公钥加密向同一个收方发送密文信息. 而这些密文所对应的明文很可能是相互关联的. 敌人可能会进行渗透攻击, 得到某些发送方所有的信息, 包括密文所对应的明文以及加密所使用的随机数. 此外, 边信道攻击方法的日新月异, 内存攻击 的出现颠覆了 只有计算才会泄漏信息 这一论断. 即使不做任何计算, 敌人也可能会通过 Cold-Boots Attac 来得到存储在内存的密钥的一部分信息. 这些攻击方法都导致了新的安全要求. 2.4 新攻击新要求复杂环境对保障信息安全的算法提出了更高的安全要求, 对信息安全保障理论与技术提出了更高的挑战. 具体表现在如下几个方面. () 网络化环境下的协同计算中可能会有多个实体, 他们之间相互通信的信息极有可能是相互关联的. 而敌手则可能会窃听到网络上传输的任何信息. 同时, 敌手也可能会渗透 (corrupt) 甚至完全掌控某个或多个通信实体. 那么如何保障那些没有受到敌人渗透的通信实体所加密的数据的保密性? 这样的一个复杂环境下的多方密码系统的安全性, 已经不能够由简单的只涉及两方通信的 IND-CCA 安全性来保证了. 如何建立新的安全模型, 定义新的安全指标, 设计加密算法实现并达到这些安全指标? (2) 实施密码算法的电子设备在运行的过程中会有功率消耗或电磁辐射. 而密码算法中的密钥参与算法运行时, 密钥的 0 或 比特信息会引起不同的功率消耗或者不同强度的电磁辐射. 边信道攻击 (sde channel attac) 正是通过算法运行过程中的时间消耗 功率消耗或电磁辐射之类的信息泄露对密钥进行恢复, 进而攻破密码系统. 近几年来, 边信道已经由简单功耗分析攻击 (smple power analyss attacs, SPA) 和差分功耗分析攻击 (dfferental power analyss attacs, DPA) 发展为零值点攻击 (zero-value attac), 内存攻击 (memory attac) 等. 这些攻击都是以恢复 ( 部分密钥 ) 为目的. 而传统的密码算法的可证明安全总是假设密钥服从均匀分布, 敌人 ( 计算意义下 ) 不知道密钥的任何信息. 边信道攻击无疑给敌手带来了绝对的密钥泄漏. 为了抵御这种攻击, 通常会对密钥进行盲化处理, 但是本质上并没有改变算法本身, 以牺牲效率来换取安全性. 这种解决方法具有很强的针对性, 只针对特定的算法和特定的攻击, 不具有一般性, 对新的算法和新的边信道攻击可能无能为力. 如何设计一个密码算法, 使其从理论上就能抵抗边信道攻击? (3) 在网络化的分布式存储中, 为了保证数据的安全性, 数据一般都需要加密后存储. 而在实际应用中, 加密存储中的数据中往往还包括了加密数据所使用的密钥. 如 Wndows 操作系统所提供的 BtLocer 磁盘加密系统, 数据和磁盘密钥一起加密后存储在磁盘中. 这样做的好处是方便密钥存储和管理. 而在信证系统 (credental system) 中, 为了防止用户将自己的某个私钥交给他人代理, 系统将每个用户的多个私钥利用循环加密 (crcular encrypton) 的方法进行加密存储. 泄漏一个私钥意味着泄漏了用户的所有的私钥. 无论是既成事实上的加密应用, 还是为了实现某个功能的主观设计, 都产生了 私钥加密私钥 这样一个不争的事实. 而 IND-CPA/CCA 安全模型却不能涵盖这种情况, 也就是说即使算法是 IND-CPA/CCA 安全的, 也不能保证利用私钥加密私钥所产生的密文对敌人而言是安全的. 在这种情况下, 同样也需要一个更强的安全模型, 设计具有更高安全性的密码算法. (4) 密钥相关攻击 (related-ey attac, RKA) 最早是一种常见的分组密码攻击方法. 它同样可能实施在公钥加密系统中. 敌人可以篡改解密设备中的私钥, 知道篡改的方式但不知道篡改前后的密钥值, 然后观察篡改后的私钥在解密算法的输出表现提取出有用信息, 进而破译整个密码算法. (5) 随机数相关攻击 (randomness-related attac, RRA) 则是敌人通过对公钥加密所用的随机数进行篡
542 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 改, 知道篡改的方式但不知道篡改前后的随机数的值, 对篡改后的加密算法的输出进行分析, 以期获得额外的信息. 灵活多样的网络化环境对安全性提出了不同的要求. IND-CCA 安全性对于一些环境 ( 如多方通信环境, 密钥加密存储系统, 边信道信息泄漏环境等 ) 的安全要求是远远不够的. 因此, 必须重新建立复杂环境下的安全模型, 定义新环境下的安全定义, 并在新模型下对公钥密码体制进行设计, 从理论上证明其安全性. 3 新模型新方法我们对上节所介绍的几种新攻击的进行形式化描述, 给出相应的安全定义, 并指出现有的解决方法. 3. 选择打开攻击和 SO-CCA 安全与传统的 IND-CCA 安全模型相比, 这里考虑的是多用户环境, 同时敌人有更强的能力, 表现为渗透 (corrupton) 攻击, 即 : 敌手可以自由选择打开哪些密文, 并得到相关的明文和随机数. 见图 3 和图 4. 敌人得到的信息包括 : 公钥 多个密文组成的挑战密文向量 ( 相应明文向量的概率分布可以由敌手指定 ) 敌人选择密文向量的一部分并得到相应的密文分量所对应的明文和随机数 敌人可以自适应地访问解密预言机 ( 但是不能查询挑战密文向量中的密文 ). SO-CCA 安全与传统的 CCA 安全相比, 敌人多了选择打开的能力, 目前 CCA 安全的公钥加密不一定就是 SO-CCA 安全的. 传统的 CCA 安全有两种主流的形式化定义 : 基于不可区分意义下的 IND-CCA 安全和基于仿真意义下的 SIM-CCA 语义安全. 而且两种安全是等价的, 即 IND-CCA=SIM-CCA. 同样, SO-CCA 也有两种形式化的定义 : 基于不可区分意义下的 IND-SO-CCA 安全 ( 图 3) 和基于仿真意义下的 SIM-SO-CCA 语义安全 ( 图 4). IND-SO-CCA 安全要求是 : 任意 ppt 的敌人无法区分挑战密文向量所对应的真正明文向量和一个与所打开的明文一致的重新采样的假明文向量. 这里要求明文的概率分布一定是能够条件概率重采样的 ; SIM-SO-CCA 语义安全则要求 : ppt 的敌人可以计算的都可以通过一个只知道打开的明文分量的 ppt 的仿真器所仿真. 由于 SIM-SO-CCA 不需要明文概率分布的条件概率重采样, 故更难实现. 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 解密阶段 : 敌手查询密文, C 挑战者调用解密算法 Decs,C 得到公私钥对. 将公钥 p 发给敌手. M 回复. 挑战阶段 : 敌手向挑战者提交一个可以条件重采样的概率分布 M, 挑战者根据这个概率分布选择出 n 个明文构成明文向量 M,, M, n 并将其加密得到相应的密文向量 C, C2,, C n, 其中 C Encp, M; R. 挑战者将挑战密文向量 C, C2,, Cn 发给敌手. 打开阶段 : 敌手选择一个集合 I, 2, n 发送给挑战者. 挑战者打开相应的密文分量得到 挑战者随机选择一个比特 b. 如果, 如果 0, b 则将原明文向量 M M 和打开的随机数,, n I M, R. I R 发送给敌手. b 则在固定 M 的值的情况下根据 M 概率分布重新采样得到新明文向量 I 新的明文向量发给敌手. 对于所有的 I 显然有 M M. 解密阶段 2: 敌手查询密文, 猜测阶段 : 敌手猜测 b 的值 b. 如果敌手猜对 b b, 则敌人赢得了这个实验. C 但要限定,,,. 挑战者调用解密算法 Decs,C C C C2 C n M,,, M n 并将 M 回复. Fgure 3 图 3 PKE 的 IND-SO-CCA 实验及相关安全模型 The IND-SO-CCA experment of PKE and the securty model
刘胜利 : 公钥加密系统的可证明安全 新挑战新方法 543 定义 2 给定一个公钥加密方案 Dec 得图 3 中实验的概率都以可以忽略的量接近 2, 即 那么这个 PKE 方案就是 IND-SO-CCA 的. PKE KeyGen, Enc,. 如果任意的概率多项式时间 (ppt) 的敌手赢 Prob 2 bb neg PKE 的 SIM-SO-CCA 安全要求是 : 真实实验中 ppt 敌手的输出 Out A 与理想实验中和 ppt 仿真器的输 出 Out 计算不可区分. 也就是说找不到一个 ppt 的算法以不可忽略的概率区分出这两个输出的概率分布. S SIM-SO-CCA 安全要表达的内容是 : 一个敌手从它所看到密文向量 选择打开的明文和随机数 以及解密查询所得到信息中可以 ppt 计算出来的任何内容, 都可以通过一个只看到选择打开的明文的 ppt 仿真器计算出来. 因此, 密文向量, 选择打开的随机数以及解密查询不会给敌手带来任何的收益. 见图 4. 真实实验 : 挑战者与敌手 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 得到公私钥对. 将公钥 p 发给敌手. 解密阶段 : 敌手查询密文 C, 挑战者调用解密算法 Dec s,c M 回复. 挑战阶段 : 敌手向挑战者提交一个可以有效采样的概率分布 M, 挑战者根据这个概率分布选择出 n 个明文构成明文向量 M,,, M n 并将其加密得到相应的密文向量 C 其中 C M R C, C2,, n, Enc p, ;. 挑战者将挑战密文 向量发给敌手. 解密阶段 2: 敌手查询密文, C C, C, C. 挑战者调用解密算法 Decs,C C 但要限定 M 回复. 打开阶段 : 敌手选择一个集合 I, 2, n 2, n 发送给挑战者. 挑战者打开相应的密文分量得到 M, R. 挑战者将打开 I 的信息 M, R 发给敌手. I 解密阶段 3: 敌手查询密文, 挑战者调用解密算法 Decs,C C 但要限定 CC C C M 回复.,,. 2, n 理想实验 : 挑战者与仿真器 初始阶段 : 挑战者将安全参数 发给仿真器. 挑战阶段 : 敌手向挑战者提交一个可以有效采样的概率分布 M. 挑战者根据这个概率分布选择出 n 个明文构成明文向量 M,, M. n 打开阶段 : 仿真器选择一个集合 I, 2, n 发送 给挑战者. 挑战者打开相应的明文分量得到, M 并将其发给仿真器. I 输出阶段 : 仿真器输出 Out S. 输出阶段 : 敌手输出 Out A. (a) 真实实验及安全模型 (b) 理想实验及安全模型 Fgure 4 图 4 PKE 的 SIM-SO-CCA 实验及安全模型 The SIM-SO-CCA experments of PKE and the securty model 定义 3 给定一个公钥加密方案 Dec D 都不能区分图 4 中两个实验的输出, 即 则 PKE 就是 SIM-SO-CCA 安全的. PKE KeyGen, Enc,. 如果任意的概率多项式时间 (ppt) 的区分器 Out Out Prob D A Prob D S neg
544 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 在 204 年, Hofhenz 和 Rupp 证明了 IND-SO-CCA 安全性严格高于 IND-CCA 安全 [0]. 实现 IND-SO-CCA 安全的方法 : 可以借用 Waters 用 Lossy Trapdoor Functons(LTDF) [6,] +ABO-TDF+One Tme Sgnature 来构造 CCA 安全 PKE 思想. 由于考虑的挑战密文向量有多个分量, 故需要可以 All-but-N [2], All-but-many lossy trapdoor functon [3] 等技术, 其目的是在安全证明中将挑战密文变为 lossy encrypton, 而敌人向解密 oracle 查询的密文不是 lossy encrypton, 进而识别出不合法的密文以拒绝解密. 需要指出的是, 在选择打开环境下, 我们不能使用一次签名来验证密文的合法性, 原因在于, 敌人可以通过选择打开攻击得到挑战密文中签名所用的随机数 ( 即签名密钥 ), 进而伪造合法密文, 从解密预言机中得到有关挑战明文的所有信息. 解决这个问题的一个很好的方法是使用变色龙 Hash 函数与 All-but-N(All-but-many)TDF 的结合使用. Bellare 等在文献 [4] 中提出了如何实现 SIM-SO-CPA 安全的基于身份的公钥加密. 实现 SIM-SO-CCA 安全的挑战性则更高. 在公钥加密 (PKE) 方面, Fehr [5] 等人在 EuroCrypt 200 提出使用 2-unversal Hash Proof System (HPS) 和交叉认证码 (Cross Authentcaton Codes) 相结合实现 SIM-SO-CCA [6] 安全. 在 PKC 203, Huang 等指出单纯的交叉认证码不足以证明所构造的 PKE 的 SIM-SO-CCA 安全性, [7] 而实现一比特的 SIM-SO-CCA 安全的 PKE 则无需交叉认证码. 在 INCoS203 会议上, Huang 等提出了一个加强版的交叉认证码, 成功地修复了 Fehr 等人在 EuroCrypt 200 论文中的 SIM-SO-CCA 安全证明. 在基于身份的加密 (IBE) 方面, 现在可行的方法是使用特殊的一比特的 IBE 加密和交叉认证码来实现 [8]. 一比特的公钥加密的特点是 : 加密比特 是一个合法的密文, 而加密比特 0 是随机密文 ( 随机选择出的几乎都不是合法密文 ). 此外, 加密这一比特的密文同时还封装一个密钥. 封闭密钥则是交叉认证码的输入. 多个比特的加密对应的密文通过交叉认证码粘合在一起, 生成共同的认证符. 这样就有效的防止的 Quotng Attac. 这种实现方法的缺点是效率比较低, 但却是一种可以达到 SIM-SO-CCA 安全的通用构造. 3.2 密钥泄漏攻击和 IND-LR-CCA 安全 与传统的 IND-CCA 安全模型相比, 敌手有更强的能力, 因为敌手可以额外得到密钥泄漏的一些信息. 敌手得到的信息包括 : 公钥 挑战密文 解密预言机 以及一个密钥泄漏预言机. 其中, 挑战密文是从敌人提供的长度相同的两个明文中随机选出并加密得到的. 密钥泄漏的安全模型又可分为两种 : 有界泄漏模型 (bounded model) 和辅助输入模型 (auxlary nput model). 在有界泄漏模型中, 敌人可以自适应地询问密钥泄漏预言机某个函数 f, 预言机则回复 f s. 但 s f s 的仅要 是, 要求所泄漏的所有 f 关于私钥 s 的信息不超过 s 的长度. 在辅助输入模型中, 对 求函数值求逆的是计算困难的. 因此, 这种模型更为通用. IND-LR-CCA 安全要求敌人不能区分挑战密文是他所选择的两个明文中哪个明文的加密. 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 解密及密钥泄漏阶段 : 若敌手查询密文, 手查询函数, 得到公私钥对. 将公钥 p 发给敌手. C 挑战者调用解密算法 Decs,C f 则挑战者回复 f s. 但如果历次泄漏的 s M 回复. 若敌 f 累积信息达到上界, 则回复. 挑战阶段 : 敌手向挑战者提交两个长度相同的明文 M 0, M, 挑战者随机选择一个比特 b, 调用加密 算法加密, b M 得到挑战密文 C M R Enc p, ;. 解密阶段 2: 敌手查询密文 C, 但要限定 C. 猜测阶段 : 敌手猜测 b 的值 b. 如果敌手猜对 b b, 则敌人赢得了这个实验. b 挑战者将挑战密文 C 发给敌手. C 挑战者调用解密算法 Decs,C M 回复. Fgure 5 图 5 PKE 的 IND-LR-CCA 实验及安全模型 The IND-LR-CCA experment of PKE and the securty model
刘胜利 : 公钥加密系统的可证明安全 新挑战新方法 545 定义 4 给定一个公钥加密方案 Dec 得图 5 中实验的概率都以可以忽略的量接近 2, 即 PKE KeyGen, Enc,. 如果任意的概率多项式时间 (ppt) 的敌手赢 Prob 那么这个 PKE 方案就是 -IND-LR-CCA 安全的. 2 bb neg 实现 IND-LR-CCA 安全的有效技术是提取器. 提取器可以将一个不是均匀分布但熵很大的字符串变为一个接近均匀分布的短字符串. 例如使用提取器可以将 Cramer-Shoup 方案转变为容忍密钥泄漏的版本 [9 2] ; 结合 Hash Proof System 和 Naor-Yung 两把密钥的方法即可得到容忍密钥泄漏的 LR-CCA 安全的 PKE [2] [22,23]. 但是, 目前的方法中, 要么私钥所容忍泄漏比例较小, 要么所实现效率太低. 最新的方法是将 Hash Proof System(HPS) 与 One-Tme Lossy Flter 相结合, 同时达到了高效和密钥泄漏比例接近 的两个要求. 其思想是 : HPS 封装一个密钥, 该密钥既用于掩盖明文, 又用于有效密文的验证. 而 One-Tme Lossy Flter 在挑战密文中表现为 Lossy, 即泄漏关于封装密钥很少的信息, 而敌人生成的密文中 One-Tme Lossy Flter 则表现为单射函数, 进而使敌人提交的不合法密文被解密预言机有效地拒绝. 以上方案均只适用于有界泄漏模型. 辅助输入 (Auxlary-Input) 密钥泄漏模型是对有界泄漏模型的推广. 回忆有界指的是所有的泄漏信息量不得超过私钥的长度. 但是在辅助输入模型下, 对于敌人查询的私钥泄漏函数 f 只有如下要求 : 已知函 数值 f s, 在计算意义下求 s 具有困难性. 这实际是要求函数 f 的单向性. 例如 : 如果 f 是一个单向置 换, 那么在信息论意义下, f s已经泄漏了关于 s 的信息, 但是任何的 ppt 的敌手却只能以约 2 的概率 猜中它的 hard-core 比特. 实现辅助输入密钥泄漏模型下的 PKE, 一个重要的技术是广义的 Goldreh-Levn(GL) 定理 [24], 指 的是在素数域 GFp 上如何产生单向函数的 Hard-Core. 由于广义的 GL 定理所使用的 Hard Core 函数是 [] [0] 线性函数, 故仅有 BHHO 方案和基于 LWE 的 PKE 方案可以实现 IND-LR-CPA 安全. 目前还没有实现 IND-LR-CCA 安全的 PKE 高效的实例. 3.3 密钥相关信息的加密和 KDM-CCA 安全 与传统的 IND-CCA 安全模型相比, 敌人拿到的挑战密文可能是与私钥 s 紧密联系的消息的加密. 这些消息可能是只有知道私钥 s 才可以有效计算出来的关于 s 的函数值. 敌人得到的信息包括 : 公钥 加密预言机 挑战密文 解密预言机. 其中, 敌人可以多次询问加密预言机, 而挑战密文是加密预言机的输出 : 要么每次都对一个固定明文的加密, 如对 的加密, 要么每次都是对 f s 的加密. 而 f 可以由敌人从某个固定的函数集合 中自由挑选, 函数值的长度应该和固定明文的长度相同. 定义 5 给定一个公钥加密方案 Dec 得图 6 中实验的概率都以可以忽略的量接近 2, 即 那么这个 PKE 方案就是 KDM-CCA 安全的. PKE KeyGen, Enc,. 如果任意的概率多项式时间 (ppt) 的敌手赢 bb Prob 2 neg KDM-CCA 安全要求 : ppt 的敌人不能区分挑战密文向量是对 f s 的加密还是对固定明文的加密. 如
546 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 果 f s 是一个常函数, 那么 KDM-CCA 安全就退化成了 IND-CCA 安全. 可见 KDM-CCA 安全比传统的 IND-CCA 安全要求更高 [25]. 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 解密阶段 : 敌手查询密文, C 挑战者调用解密算法 Decs,C 得到公私钥对. 将公钥 p 发给敌手. M 回复. 挑战阶段 ( 加密询问 ): 挑战者随机生成一个比特 b. 敌手向挑战者提交一个函数 进行加密查询, 为 密钥相关函数集合. (a) 如果, (b) 如果 0, 要求 s b 挑战者对 s 加密得挑战密文 C Enc p, s ; b 挑战者对一个固定明文 ( 如全 明文 ) 进行加密得到 C 的长度与固定明文长度相同. 挑战者将 是比特 b 一旦选定就不会再改变. 解密阶段 2: 敌手查询密文, 猜测阶段 : 敌手猜测 b 的值 b. C 但要限定 C C C2 C n 如果敌手猜对 b b, 则敌人赢得了这个实验. Enc p,. C 发送给敌手. 敌手的加密查询可以有多项式次, 但,,,. 挑战者调用解密算法 Decs,C M 回复. 图 6 PKE 的 KDM-CCA 实验及安全模型 Fgure 6 The KDM-CCA experment of PKE and the securty model [26] 实现 KDM-CCA 的安全更具有挑战性, 现有的方法主要有 : 利用 BHHO 方案实现 KDM-CPA 安全, 再用 Noar-Yung 的两把密钥的方法将 KDM-CPA 安全的 PKE 转化为 KDM-CCA 安全的 PKE [27] ; 使用 lossy algebrac flters [28] 实现 KDM-CCA 安全. 另一种简单的方法则是直接使用 Cramer-Shoup 方案来实现 KDM-CCA, 但是不能使用私钥加密自身 [29]. 敌手可以选择的密钥函数集合 越大, 则密钥相关安全性就越好. 目前, 敌手所可以选择的密钥函数集合仅限于 仿射函数集合, 如何扩大该集合是一个新的挑战. 3.4 密钥相关攻击 (Related-Key Attac, 简称 RKA) 及密钥相关安全 (RK-CCA) 与传统的 IND-CCA 安全模型相比, 敌人得到的解密服务更为强大. 敌人可以选择函数, 迫使解密算 法用 s 进行解密. 也就是解密预言机必须使用 函数为常函数 s s, Dec s,c 则密钥相关的 RK-CCA 安全退化为传统的 IND-CCA 安全. 使用对所提交的密文 C 进行解密. 如果 敌人得到的信息包括 : 公钥 挑战密文 特殊的解密预言机. 其中, 特殊的解密预言机的功能更加强大. 敌人在询问特殊解密预言机时, 提交的是一个密文 / 函数对 C, f, 解密预言机使用 f s 对密文 C 进 行解密. 而函数 f 是敌人在某个函数集合中自由挑选. 挑战密文则是从敌人自己选择的长度相同的两个明文中随机选出并加密得到的. 定义 6 给定一个公钥加密方案 Dec 得图 7 中实验的概率都以可以忽略的量接近 2, 即 PKE KeyGen, Enc,. 如果任意的概率多项式时间 (ppt) 的敌手赢
刘胜利 : 公钥加密系统的可证明安全 新挑战新方法 547 Prob 2 bb neg 那么这个 PKE 方案就是 -IND-RK-CCA 安全的. IND-RK-CCA 安全要求 : 敌人不能区分挑战密文是他所选择的两个明文中哪个明文的加密. 如果敌人 f s s 这样的特殊函数, 那么 IND-RK-CCA 安全就退化成为了传统的 解密查询时提交的函数总是 IND-CCA 安全. Wee [30] 通过 fnger-prnt 和 ey homomorphsm 的技术得到了基于各种标准困难性假设的 RKA-CCA 安全的 PKE, 但是密钥相关的函数集合仅限于线性函数. 其思路是 : 如果一个具有 IND-CCA 安全的 PKE 还有 fnger-prnt 和 ey homomorphsm 两种性质, 那么 RKA-CCA 安全就可以归约为 IND-CCA 安全. 原因是, 进行 RKA-CCA 攻击的敌手的所有密文查询 C, f 都可以通过 ey homomorphsm 技术转换为一个新的密 文 C, 而 fnger-prnt 性质又保证了 C 与挑战密文 C 不同. 因此, 原 IND-CCA 安全的敌手就可以对 C 进行解密查询, 进而完美回答了 C, f 的解密查询. Bellare, Paterson, Thomson [3] 在 AsaCrypt202 中提出如何 实现 RKA-CPA 安全的 IBE, 使用 (B)CHK 转换即可得到 RKA-CCA 安全的 PKE, 其函数集合扩展到了私钥的多项式. 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 得到公私钥对. 将公钥 p 发给敌手. 解密阶段 : 敌手从密钥相关函数集合 选择函数, 提交,C 以查询用 s 结果, 挑战者调用解密算法 Dec s,c M 回复. 这里. 对密文 C 进行解密的 挑战阶段 : 敌手向挑战者提交两个长度相同的明文 M 0, M, 挑战者随机选择一个比特 b, 调用加密算法 加密 b, Enc p, b;. 解密阶段 2: 与解密阶段 类似, 敌人提交 要求敌人不能查询 IC,, M 得到挑战密文 C M R 挑战者将挑战密文 C 发给敌手., C, 挑战者调用解密算法 猜测阶段 : 敌手猜测 b 的值 b. 这时的 I 是恒等函数 s 如果敌手猜对 b b, 则敌人赢得了这个实验. I s. Dec s,c M 回复. 但 图 7 PKE 的 -IND-RK-CCA 实验及安全模型 Fgure 7 The -IND-RK -CCA experment of PKE and the securty model 新的挑战是如何继续扩大密钥相关的函数集合. 3.5 随机数相关攻击 (Randomness-Related Attac, RRA) 和随机数相关安全 (RR-CCA) 在密码算法和协议中会用到大量的随机数, 而在安全分析中, 我们总是认为随机数永远是均匀独立选择的. 但是现实中的随机数并非如此完美, 甚至还会受到敌手的影响, 详见文献 [32 38] 等论文. 那么使用不完善的随机数进行公钥加密的话, 如何保证加密消息的安全性呢? 这就是随机数相关安全所要研究的. 在 随机数相关攻击 中, 敌手可以在某种程度上影响加密算法中使用的随机数的取值. 其影响的程度可以用一个函数集合 来表示. 如果 是恒等函数, 则 随机数相关攻击 下的 RR-CCA 就弱化为了 IND-CCA 安全.
548 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 定义 7 给定一个公钥加密方案 Dec 得图 8 中实验的概率都以可以忽略的量接近 2, 即 那么这个 PKE 方案就是 -IND-RR-CCA 安全的. PKE KeyGen, Enc,. 如果任意的概率多项式时间 (ppt) 的敌手赢 bb Prob 2 neg 敌人得到的信息包括 : 公钥 挑战密文 特殊的加密预言机 解密预言机. 挑战密文则是从敌人自己选择的长度相同的两个明文中随机选出并加密得到的. IND-RR-CCA 安全要求 : 敌人不能区分挑战密文是他所选择的两个明文中哪个明文的加密. 对于随机数相关攻击, 最早由 Yle 在 200 年研究 [39]. 目前最新的结果是 204 年 Paterson, Schuldt, [40] Sbborn 等使用 Correlated-Input Secure Hash 以及可以抵抗 Related-ey Attac 的伪随机函数构造的 [23]. 然而目前可抵抗 Related-ey Attac 的伪随机函数新的构造仅限于基于 DDH 类假设的构造. 其挑战是如何得到更多的构造以及如何扩大随机数相关函数集合. 初始阶段 : 挑战者调用密钥生成算法 KeyGen p,s 得到公私钥对. 将公钥 p 发给敌手. 加 / 解密阶段 : 如果敌手提交密文 C 要求解密, 挑战者调用解密算法 Decs,C 果敌人提交明文和随机数对 M, 要求加密, 则挑战者调用加密算法 Encp, ; 应的密文 C 并将 C 反馈给敌手. 这里, 为随机数相关函数集合. M 回复. 如 M R C 得到相 挑战阶段 : 敌手向挑战者提交两个长度相同的明文 M 0 和 M, 以及一个函数. 挑战者随机选 择一个比特 b, 调用加密算法加密, 发给敌手. M 得到挑战密文 C M R b 加 / 解密阶段 2: 与加解密阶段 类似, 但是在解密查询中, 敌人不能查询 猜测阶段 : 敌手猜测 b 的值 b. 如果敌手猜对 b b, 则敌人赢得了这个实验. Enc p, ;. 挑战者将挑战密文 C b, C. 图 8 PKE 的 -IND-RR-CCA 实验及安全模型 Fgure 8 The -IND-RR-CCA experment of PKE and the securty model 4 结论本文综合讨论了现在公钥加密系统面临的新的挑战, 包括 : 选择打开攻击 密钥泄漏攻击 密钥相关消息加密 密钥相关攻击及随机数相关攻击. 并介绍了现有的各种新安全模型和新安全模型下的公钥加密系统实现可证明安全所需要的理论技术. 这些新的安全概念都比传统的 IND-CCA 安全要强. 如何设计出一个公钥加密方案使其同时满足上述各种新的安全属性则是一个更大的挑战. References [] Naor M, Yung M. Publc-ey cryptosystems provably secure aganst chosen cphertext attacs[c]. In: Proceedngs of the 22nd Annual ACM Symposum on Theory of Computng STOC '90. ACM, 990: 427 437. [2] Cramer R, Shoup V. Unversal hash proofs and a paradgm for adaptve chosen cphertext secure publc-ey encrypton[c]. In: Advances n Cryptology EUROCRYPT 2002. Sprnger Berln Hedelberg, 2002: 45 64.
刘胜利 : 公钥加密系统的可证明安全 新挑战新方法 549 [3] Boneh D, Canett R, Halev S, et al. Chosen-cphertext securty from dentty-based encrypton[j]. SIAM Journal on Computng, 2006, 36(5): 30 328. [4] Canett R, Halev S, Katz J. Adaptvely-secure, non-nteractve publc-ey encrypton[c]. In: Theory of Cryptography Conference TCC 2005. Sprnger Berln Hedelberg, 2005: 50 68. [5] Canett R, Halev S, Katz J. Chosen-cphertext securty from dentty-based encrypton[c]. In: Advances n Cryptology EUROCRPT 2004. Sprnger Berln Hedelberg, 2004: 207 222. [6] Peert C, Waters B. Lossy trapdoor functons and ther applcatons[c]. In: Proceedngs of the 40th Annual ACM Symposum on Theory of Computng STOC 2008. ACM Press, 2008: 87 96. [7] Watanabe Y, Shata J, Ima H. Equvalence between semantc securty and ndstngushablty aganst chosen cphertext attacs[c]. In: Publc Key Cryptography PKC 2003. Sprnger Berln Hedelberg, 2002: 7 84. [8] Goldwasser S, Mcal S. Probablstc encrypton[j]. Journal of Computer and System Scences, 984, 28(2): 270 299. [9] Racoff C, Smon D R. Non-nteractve zero-nowledge proof of nowledge and chosen cphertext attac[c]. In: Advances n Cryptology CRYPTO '9. Sprnger Berln Hedelberg, 992: 433 444. [0] Hofhenz D, Rupp A. Standard versus selectve openng securty: separaton and equvalence results[c]. In: Theory of Cryptography Conference TCC 204. Sprnger Berln Hedelberg, 204: 59 65. [] Hemenway B, Ostrovsy R. Lossy trapdoor functons from smooth homomorphc hash proof systems[c]. In: Electronc Colloquum on Computatonal Complexty ECCC. 2009: 27 27. [2] Hemenway B, Lbert B, Ostrovsy R, et al. Lossy encrypton: constructons from general assumptons and effcent selectve openng chosen cphertext securty[c]. In: Advances n Cryptology ASIACRYPT 20. Sprnger Berln Hedelberg, 20: 70 88. [3] Hofhenz D. All-but-many lossy trapdoor functons[c]. In: Advances n Cryptology EUROCRYPT 202. Sprnger Berln Hedelberg, 202: 209 227. [4] Bellare M, Waters B, Yle S. Identty-based encrypton secure aganst selectve openng attac[c]. In: Theory of Cryptography Conference TCC 20. Sprnger Berln Hedelberg, 20: 235 252. [5] Fehr S, Hofhenz D, Kltz E, et al. Encrypton schemes secure aganst chosen-cphertext selectve openng attacs[c]. In: Advances n Cryptology EUROCRYPT 200. Sprnger Berln Hedelberg, 200: 38 402. [6] Huang Z, Lu S, Qn B. Sender-equvocable encrypton schemes secure aganst chosen-cphertext attacs revsted[c]. In: Publc-Key Cryptography PKC 203. Sprnger Berln Hedelberg, 203: 369 385. [7] Huang Z, Lu S, Qn B, et al. Fxng the sender-equvocable encrypton scheme n Eurocrypt 200[C]. In: 5th Internatonal Conference on Intellgent Networng and Collaboratve Systems INCoS 203. IEEE, 203: 366 372. [8] La J, Deng R H, Lu S, et al. Identty-Based Encrypton Secure aganst Selectve Openng Chosen-Cphertext Attac[C]. In: Advances n Cryptology EUROCRYPT 204. Sprnger Berln Hedelberg, 204: 77 92. [9] Kltz E, Mohassel P, O Nell A. Adaptve trapdoor functons and chosen-cphertext securty[c]. In: Advances n Cryptology EUROCRYPT 200. Sprnger Berln Hedelberg, 200: 673 692. [20] Lu S, Weng J, Zhao Y. Effcent publc ey cryptosystem reslent to ey leaage chosen cphertext attacs[c]. In: Topcs n Cryptology CT-RSA 203. Sprnger Berln Hedelberg, 203: 84 00. [2] Naor M, Segev G. Publc-ey cryptosystems reslent to ey leaage[c]. In: Advances n Cryptology CRYPTO 2009. Sprnger Berln Hedelberg, 2009: 8 35. [22] Qn B, Lu S. Leaage-reslent chosen-cphertext secure publc-ey encrypton from hash proof system and one-tme lossy flter[c]. In: Advances n Cryptology ASIACRYPT 203. Sprnger Berln Hedelberg, 203: 38 400. [23] Qn B, Lu S. Leaage-flexble CCA-secure publc-ey encrypton: smple constructon and free of parng[c]. In: Publc-Key Cryptography PKC 204. Sprnger Berln Hedelberg, 204: 9 36. [24] Dods Y, Goldwasser S, Kala Y T, et al. Publc-ey encrypton schemes wth auxlary nputs[c]. In: Theory of Cryptography Conference TCC 200. Sprnger Berln Hedelberg, 200: 36 38. [25] Cash D, Green M, Hohenberger S. New defntons and separatons for crcular securty[c]. In: Publc Key Cryptography PKC 202. Sprnger Berln Hedelberg, 202: 540 557. [26] Boneh D, Halev S, Hamburg M, et al. Crcular-secure encrypton from decson dffe-hellman[c]. In: Advances n Cryptology CRYPTO 2008. Sprnger Berln Hedelberg, 2008: 08 25. [27] Camensch J, Chandran N, Shoup V. A publc ey encrypton scheme secure aganst ey dependent chosen plantext and adaptve chosen cphertext attacs[c]. In: Advances n Cryptology EUROCRYPT 2009. Sprnger Berln Hedelberg, 2009: 35 368. [28] Hofhenz D. Crcular chosen-cphertext securty wth compact cphertexts[c]. In: Advances n Cryptology EUROCRYPT. 203: 520 536.
550 Journal of Cryptologc Research 密码学报 Vol., No.6, Dec. 204 [29] Qn B, Lu S, Huang Z. Key-dependent message chosen-cphertext securty of the Cramer-Shoup Cryptosystem[C]. In: Australasan Conference on Informaton Securty and Prvacy ACISP 203. Sprnger Berln Hedelberg, 203: 36 5. [30] Wee H. Publc ey encrypton aganst related ey attacs[c]. In: Publc Key Cryptography PKC 202. Sprnger Berln Hedelberg, 202: 262 279. [3] Bellare M, Paterson K G, Thomson S. RKA securty beyond the lnear barrer: IBE, encrypton and sgnatures[c]. In: Advances n Cryptology ASIACRYPT 202. Sprnger Berln Hedelberg, 202: 33 348. [32] Fujsa E, Oamoto T. Secure ntegraton of asymmetrc and symmetrc encrypton schemes[c]. In: Advances n Cryptology CRYPTO '99. Sprnger Berln Hedelberg, 999: 537 554. [33] Goyal V, O Nell A, Rao V. Correlated-nput secure hash functons[c]. In: Theory of Cryptography Conference TCC 20. Sprnger Berln Hedelberg, 20: 82 200. [34] Gutterman Z, Pnas B, Renman T. Analyss of the lnux random number generator[c]. In: IEEE Symposum on Securty and Prvacy, 2006. IEEE, 2006: 37 385. [35] Hennger N, Durumerc Z, Wustrow E, et al. Mnng your Ps and Qs: detecton of wdespread wea eys n networ devces[c]. In: 2st USENIX Securty Symposum. 202: 205 220. [36] Deban: Deban Securty Advsory DSA-57-: OpenSSL Predctable Random Number Generator[OL]. http://www.deban.org/ securty/ 2008/dsa-57. [37] Stamos A, Becherer A, Wlcox N. Cloud computng securty ranng on the trendy new parade[c]. In: Blac Hat USA, 2009. [38] Dorrendorf L, Gutterman Z, Pnas B. Cryptanalyss of the random number generator of the wndows operatng system[j]. ACM Transactons on Informaton and System Securty, 2009, 3(): 0. [39] Yle S. Resettable publc-ey encrypton: how to encrypt on a vrtual machne[c]. In: Topcs n Cryptology CT-RSA 200. Sprnger Berln Hedelberg, 200: 4 56. [40] Paterson K G, Schuldt J C N, Sbborn D L. Related randomness attacs for publc ey encrypton[c]. In: Publc-Key Cryptography PKC 204. Sprnger Berln Hedelberg, 204: 465 482. 作者信息 刘胜利 (974 ), 河北石家庄人, 博士, 上海交通大学教授. 在西安电子科技大学获学士 硕士和博士学位, 在荷兰爱因霍芬技术大学获密码学博士学位. 主要研究领域为公钥密码学 信息理论安全. E-mal: sllu@sjtu.edu.cn