标准模型下一种实用的和可证明安全的IBE方案

《计算机学报》2010年第2期，2010，33（2）标准模型下一种实用的和可证明安全的IBE方案徐鹏，崔国华*，雷凤宇华中科技大学计算机科学与技术学院信息安全实验室湖北武汉430074摘要：组合公钥方案是一种用于基于身份密码体制中生成用户加密密钥和私钥的知名方案。针对组合公钥方案存在合谋攻击的问题，通过仅扩展该方案的私钥生成过程，实现了扩展方案的抗合谋攻击性。在此基础上构建标准模型下基于DecisionalBilinearDiffie-Hellman假设可证明安全的一种新的基于身份加密方案。最后，为了说明所构新方案的实用性，分析了扩展组合公钥方案的用户加密密钥抗碰撞性；对比了新方案和同类的3个知名方案在安全性证明的归约程度方面、加解密的时间复杂度方面和密文的长度方面的性能，并得出新方案在以上三点上具有目前最优的指标，因此新方案是相对较实用的。关键字：组合公钥，合谋攻击，标准模型，DecisionalBilinearDiffie-Hellman假设，基于身份加密1.引言1984年，Shamir创造性的提出了基于身份的加密体制（Identity-BasedEncryption,IBE）的概念[1]。和传统的公钥加密体制不同，它可以使用任意字符串作为用户的公钥，这样取消了传统公钥加密体制对在线密钥管理中心的需要，从而大大的提高了效率。虽然IBE的概念提出的很早，但直到2001年才由Boneh提出了第一个实用的IBE方案[2]，并且该方案成功的在随机预言机模型（RandomOracleModel,ROModel）下将双线性计算难题BilinearDiffie-Hellman问题（BDH问题）的求解归约到其IBE方案的破解，因此是RO模型下可证明安全的。与此同时，Boneh也提出了新的问题，即能否构建标准模型下可证明安全的IBE方案。在标准模型下构建可证明安全的加密方案具有十分重要的实用意义。众所周知，RO模型下的安全性证明中使用了随机预言机提供询问应答服务，而真实环境中并不存在随机预言机，因此一个RO模型下可证明安全的加密方案在实用中必须选取合适的哈希函数或伪随机函数等等算法来代替方案中的随机预言机（即实例化随机预言机过程），这样对实例化后的方案是否安全和实用需要做进一步的评估[3]。而在标准模型下可证明安全的加密方案通常只需要抗碰撞的哈希函数、或伪随机函数、或单向函数，甚至有的方案根本不需要此类函数，因此其可证明安全性更实用。当然，这些并不能说明标准模型绝对优于RO模型，因为成功实例化随机预言机后的加密方案并不一定比标准模型下可证明安全的方案的安全性和执行效率低，而且有的标准模型下可证明安全的加密方案很显然就是不实用的，例如，文献[4]中的IBE方案。由于在标准模型下构建可证明安全的加密方案比RO模型要难，而且其安全性证明更实用，因此近几年得到了广泛的重视，特别是构建标准模型下可证明安全的IBE方案。在证明安全性的过程中，必须选取一个公认的难题（或称之为假设），并完成该难题的求解到加密方案破解的归约。这些难题可分为：计算难题和判定难题。而要在标准模型下建立可证明安全的加密方案必须选取判定难题，因为在RO模型下安全性证明的归约过程中计算难题的求解是依赖随机预言机的，而标准模型下由于不存在随机预言机，并且在安全性定义的攻击游戏中[2]，仿真器不可能根据其与相应攻击者的交互信息求解计算难题，例如，IND-ID-CPA安全性定义的攻击游戏中，攻击者告诉仿真器的只有身份信息、两个等长的明文信息和攻击结束时的一位猜测信息，而这些信息或者是仿真器已知的、或者和计算难题的国家自然科学基金项目，编号：60703048；湖北省自然科学基金项目，编号：2007ABA313。联系地址：华中科技大学计算机学院信息安全实验室徐鹏（收）邮编430074电话：[phone]E-mail:[e-mail]《计算机学报》2010年第2期，2010，33（2）求解无关，因此无法正确的归约并求解计算难题。由此可见，判定难题在标准模型中构建可证明安全的IBE方案是至关重要的。2004年，Boneh等人[5]提出了第一个标准模型下可证明安全的IBE方案，即在相对较弱的安全性定义下（即非适应性选择挑战ID和选择明文攻击下的语义不可区分性，简称为IND-sID-CPA安全性）成功的实现了DecisionalBilinearDiffie-Hellman问题（DecisionalBDH问题）的求解到该方案破解的归约。但是在相对较强的安全性定义下（即适应性选择挑战ID和选择明文攻击下的语义不可区分性，简称为IND-ID-CPA安全性），该IBE方案的归约十分“松散”，具体的说该归约是指数级的归约，因而在实用中为了保证IND-ID-CPA安全性会选取一个很大的安全参数，但这使得该IBE方案不具有实用性。同年，Boneh等人[4]提出了另一个标准模型下可证明安全的IBE方案，虽然该方案实现了IND-ID-CPA安全性下DecisionalBDH问题的求解到IBE方案破解相对有效的归约，但其方案中密文的长度与用户ID的长度有关，因而密文较长，同时也增加了加解密的时间复杂度，从而降低了实用性。2005年，Waters[6]提出了第一个标准模型下可证明安全的且综合来说较实用的IBE方案，即该方案不仅具有固定长度的密文（安全参数的3倍），同时实现了IND-ID-CPA安全性下DecisionalBDH问题的求解到IBE方案破解相对有效的归约。2006年，Gentry[7]提出了另一个标准模型下可证明安全的IBE方案，该方案不仅减少了公开参数的个数，提高了性能，并且实现了更紧的归约，但是该归约是基于一个更强的问题，即判定的双线性Diffie-Hellman指数的扩展问题（DecisionalAugmentedBilinearDiffie-HellmanExponentProblem,简称为DecisionalABDHEProblem），因而该方案的性能和安全性并不一定比前述方案优秀[7]，因此其实用性是否真的提高，还有待研究。通过研究发现，采用组合公钥方案[8]（CombinedPublic-KeyScheme,简称为CPK）可以构建更高效的IBE方案，并且若不考虑CPK本身的安全性问题，该方案是标准模型下可证明安全的，而且具有目前同类方案[4,5,6]中最优的DecisionalBDH问题的求解到IBE方案破解的归约，和相对最优的加解密时间复杂度和密文长度。但是众所周知，CPK存在合谋攻击问题[9]，即令CPK中私钥种子矩阵为mh阶，则若有mh个合法用户参与合谋即可计算出私钥种子矩阵。目前，现有的防范该攻击的方法[9]都是不合理的，例如，要求合法用户的总数小于mh，很明显这和CPK的设计宗旨是相违背；通过加强管理使得合谋用户数量小于mh，这种方法是不具有说服力的。因而，本文提出的新IBE方案首先继承CPK的优点及加密密钥和私钥的生成方法，通过扩展私钥的生成过程实现根本上的抗合谋攻击性；再由该扩展CPK方案构建标准模型下可证明安全的IBE方案；最后通过与前述的同类方案对比归约程度、加解密执行效率、密文长度来说明该方案具有相对较好的实用性。另外，在标准模型下可证明安全的IBE方案中，要求不同用户的加密密钥具有抗碰撞性（通常由输入为用户ID的某个抗碰撞的哈希函数实现），因此为了说明扩展CPK方案生成的用户加密密钥具有抗碰撞性，本文将详细分析新方案中加密密钥种子矩阵的规模（即mh的大小）对抗碰撞性的影响，得出具有某种程度的抗碰撞性所需要的矩阵规模，而且由于扩展CPK方案和原CPK方案的加密密钥的生成方法相同，因此该结论也适用于原CPK方案。为了方便理解，本文将一些重要的预备知识集中在下一章中描述，并进行简要的分析。2.预备知识本章将简要介绍与可证明安全的IBE方案有关的重要基础知识，分别是：IBE方案的核心构件——单向函数“双线性映射”；安全性归约中基于的难题；安全性证明所要达到的安全目标，即安全性定义。2.1双线性映射双线性映射是对修正后的Weil对和Tate对的总结和抽象，是第一个实用的IBE方案[2]之所以成功的关键，因而在2001年后的大部分IBE方案中都得到了应用。定义1.令1G和2G分别是两个大素数q阶加法循环群和乘法循环群。称满足以下条件的映射ˆe：112GGG为双线性映射，条件如下：《计算机学报》2010年第2期，2010，33（2）⒈双线性性：对1,PQG和,abZ，有ˆˆ(,)(,)abeaPbQePQ成立。⒉非退化性：若P为群1G的生成元，则ˆ(,)ePP是2G的生成元。⒊可计算性：对1,PQG，映射ˆ(,)ePQ在有效时间内可计算。一个具体的双线性映射可以参考文献[2]。2.2ComputationalDiffie-Hellman假设定义2[10].令1G为素数q阶加法群，P为该群的一个生成元。群1G上的CDH问题(CDHP)为：给定P、aP、bP，计算abP，其中,ab在*qZ中随机选取。若有效时间内，任意概率多项式时间算法的求解优势可忽略，则称群1G上CDH假设成立。2.3DecisionalBilinearDiffie-Hellman假设DecisionalBDH问题的提出是因为在具有双线性映射的群中，判定Diffie-Hellman（DDH）问题是易解的，即DDH假设不成立，因此Boneh在双线性映射群中扩展了DDH问题，即得到DecisionalBDH问题，并提出了研究热点，即若DecisionalBDH假设成立如何在标准模型下构建基于该假设的可证明安全的IBE方案。定义3.令1G和2G是两个大素数q阶加法循环群和乘法循环群，且存在双线性映射ˆe：112GGG，P为群1G的生成元。DecisionalBDH问题定义如下：DecisionalBDH问题：给定一个具有若干形如,,,,PaPbPcPabcP的Diffie-Hellman分组的分布D和一个具有若干形如,,,,PaPbPcPrP的随机分组的分布R，区分这两个分布，其中,,,abcr在范围*qZ中随机选取。若不存在有效的统计测试算法能在概率多项式时间T内，以至少的优势解DecisionalBDH问题，则称为(,)T-DecisionalBDH假设，即DecisionalBDH假设成立。总的来说，判定难题属于不可区分性问题，而不可区分性问题又分为：计算不可区分性问题和统计不可区分性问题。目前为止，几乎所有基于判定问题可证明安全的公钥加密方案中，其判定问题均是统计不可区分性问题，例如：著名的Cramer-Shoup方案[11]；还有本文第一章中介绍的所有标准模型下可证明安全的IBE方案[4,6,7]。关于统计不可区分性的定义可以参考[12]。2.4IND-ID-CPA安全性IND-ID-CPA安全性指的是适应性选择挑战ID和选择明文攻击下的语义不可区分性，是目前可证明安全的IBE方案中最受重视的安全性定义，因为凡是具有该安全性的IBE方案均可由Canetti等人[13]、Boneh等人[14]和Boyen等人[15]分别提出的通用方法有效的扩展为具有IND-ID-CCA安全性（适应性选择挑战ID和选择密文攻击下的语义不可区分性）的IBE方案，因此一般只证明某IBE方案具有IND-ID-CPA安全性。但是实现IND-ID-CPA安全性并不容易，有些方案只在较弱的安全性定义IND-sID-CPA下才具有相对较实用的安全性归约，而在IND-ID-CPA安全性下的归约完全不实用[5]，因此这也是标准模型下构建可证明安全的IBE方案的难点。下面给出IND-ID-CPA攻击的通用定义，再根据该攻击给出IND-ID-CPA安全性的定义。定义4.IND-ID-CPA攻击由如下几个阶段构成：初始化阶段：挑战者生成公开参数和秘密参数，并将公开参数传递给攻击者。私钥查询阶段1：攻击者可以向挑战者多次查询任意用户的私