一个高效的基于身份的分层加密方案

2012，48（24）1984年，Shamir[1]提出了基于身份的加密思想IBE，在这种体制中，用户加密时使用的公钥不是从公钥证书中获得，而是直接用标志自己身份信息的任意长度字符串作为公钥，比如姓名、邮箱地址、IP地址等。与传统的公钥密码体制相比，基于身份的加密体制不需要专门的认证机构，减少了证书分发与管理的复杂性。但是传统的基于身份密码体制只有一个私钥产生器PKG（PublicKeyGenerator），它不仅花费时间产生用户私钥，还需负责建立传输私钥的安全通道，负担较重，尤其在多用户情况下，极有可能遇到瓶颈问题。在这种情况下，基于身份的分层加密体系HIBE应运而生。在该体制中，用户分为多个层次，每一层用户都有一个相对应的PKG，并且只为它下一层的用户产生私钥，这样通过分层密钥服务器解决了PKG负荷过重的问题。目前，有关基于身份的分层加密方案屈指可数。2002年，Horwritz和Lynn[2]介绍了基于身份的分层加密的概念，同年，Gentry[3]基于BDH难题提出了一个在随机预言机模型中安全的HIBE方案。随后，Boneh[4]在标准模型中建立了一个HIBE方案，方案的密钥和密文长度都随着用户所在层次的加深而增加。针对这个问题，Boneh、Boyen和Goh[5]在2005年提出了一个HIBE方案，使得密钥的长度随着用户所在层次的加深而缩短。HIBE的核心问题是如何使方案具有更高的安全性，如何缩短密文长度，如何减少密钥的存储空间，如何减少加密解密所需的时间，提高系统运行的效率。本文基于Gentry方案，利用双线性配对构造了一个高效的基于身份的分层加密方案，并在随机预言机模型下证明该方案满足IND-ID-CCA2安全，通过分析，该方案较Gentry方案缩短了密文长度，同时，解密仅需要进行一次双线性配对，大大提高了加密和解密的效率。1预备知识1.1双线性映射定义1（双线性映射[6]）称映射e:G1´G1®G2是一个高效的基于身份的分层加密方案张席，杨玲ZHANGXi,YANGLing深圳大学计算机与软件学院，广东深圳518060CollegeofComputerScienceandSoftwareEngineering,ShenzhenUniversity,Shenzhen,Guangdong518060,ChinaZHANGXi,YANGLing.EfficienthierarchicalID-basedencryptionscheme.ComputerEngineeringandAp-plications,2012,48（24）：101-105.Abstract：Thispaperproposesanefficienthierarchicalid-basedencryptionschemewithbilinearpairing,whichisbasedonGentryscheme.ThisschememeetsIND-ID-CCA2securityintherandomoraclemodel.Thisschemere-ducestheciphertextlength,andonlycomputesbilinearpairingonceinthedecryption,whichincreasestheefficien-cyofencryptionanddecryption,comparedwithGentryscheme.Keywords：identity-based;hierarchicalencryption;randomoracle;securitymodel摘要：基于Gentry方案，利用双线性配对，提出了一个高效的基于身份的分层加密方案，在随机预言机模型下证明满足IND-ID-CCA2安全，通过分析，该方案较Gentry方案缩短了密文长度，解密仅需要进行一次双线性配对，大大提高了加密和解密的效率。关键词：基于身份；分层加密；随机预言机；安全模型文章编号：1002-8331（2012）24-0101-05文献标识码：A中图分类号：TP309.7;TN918作者简介：张席（1966—），男，副教授，研究领域为网络安全与密码。E-mail：[e-mail]收稿日期：2012-06-06修回日期：2012-07-30DOI：10.3778/j.issn.1002-8331.2012.24.023ComputerEngineeringandApplications计算机工程与应用101ComputerEngineeringandApplications计算机工程与应用2012，48（24）双线性映射，如果对于阶为素数q的有限加法循环群G1和阶为素数q的有限乘法循环群G2，映射G1´G1®G2具有如下属性：（1）双线性：对于任意的PQÎG1，abÎZ*q，有e(aPbQ)=e(PQ)ab，其中Z*q是指小于q且与q互素的正整数，aP表示P进行群运算a次。（2）非退化性：如果对于所有的QÎG1都满足e()PQ=1P=O这里O是无穷远点。（3）可计算性：存在一个有效的算法对于任何PQÎG1，均可以计算e(PQ)。1.2困难问题定义2（BDH问题[7]）设G1和G2是两个具有素数阶q的有限循环群，e:G1´G1®G2是一个可采纳的双线性映射，P是G1的生成元，对于给定的输入(P,aP,bP,cP)，其中abcÎZ*q，要求输出e(P,P)abc。若存在算法A，满足：Pr[A(PaPbPcP)=e(PP)abc]³ε则称该算法解决BDH问题的优势为ε。这个概率取决于abc的随机选择和A的输出。定义3（BDH假设）当且仅当没有一个算法能在概率多项式时间内以Î的优势解决BDH问题时，则称BDH假设成立。2基于身份的分层加密体制2.1HIBE的形式化定义基于身份的分层加密方案通常由五个部分[8]组成：系统参数生成算法（Setup）、子结点初始化算法Lower-levelSetup、密钥生成算法（Keygeneration）、加密算法（Encryption）、解密算法（Decryption）。（1）Setup：一个概率多项式时间算法。输入一个安全参数k，输出主密钥s和系统参数params。其中，系统参数params是公开使用的参数，包含明文空间描述M和密文空间描述C，初始根结点的私钥s（即主密钥）是秘密信息。（2）Lower-levelSetup：一个概率多项式时间算法。每个用户设置自己的低层密钥，为下一层用户的私钥生成做准备。（3）Keygeneration：一个概率多项式时间算法。输入系统参数params、主密钥s、用户的身份信息ID，用户的父结点计算并输出用户的私钥sk。（4）Encryption：一个概率多项式时间算法。输入系统参数params、接收方用户的身份信息ID，明文m，输出相应的密文c。（5）Decryption：一个确定性算法。输入系统参数params、接收方用户的私钥sk、密文c，输出相应的明文m。2.2HIBE的安全模型一个基于身份的分层加密方案是IND-ID-CCA2安全的，当且仅当不存在多项式时间内的敌手能以不可忽略的优势赢得下面的挑战者-敌手交互游戏。（1）参数设置：挑战者输入安全参数k，运行系统参数生成算法Setup，产生主密钥s和系统参数params。挑战者把系统参数params发给敌手A，保留主密钥s。（2）查询：敌手A发动多次询问q1q2qm，其中qi是下列情形之一：①私钥查询：敌手输入用户的身份信息ID，挑战者运行密钥生成算法Keygeneration，将对应的sk返回给敌手A。②解密查询：敌手输入用户的身份信息ID和密文c，挑战者运行密钥生成算法Keygeneration，得出用户对应的私钥sk，再运行解密算法Decryption，将结果m返回给敌手A。敌手进行这些查询是自适应的，即每个询问qi均可依赖之前q1q2qi-1的查询结果。（3）挑战：敌手决定结束查询后，就输出两个等长的明文消息m0m1ÎM和挑战用户身份ID，但ID不能在第一阶段中的私钥查询中出现过。挑战者任意挑选bÎ{01}，计算cb，并返回给敌手。（4）查询：敌手进行更多的查询：①私钥查询：敌手不能对挑战用户ID或其祖先结点进行查询，其他同之前的私钥查询。②解密查询：敌手不能对挑战密文c进行和挑战用户ID或其祖先结点的解密查询，其他同之前的解密查询。这些查询也是自适应的。（5）猜测：敌手输出猜测b′，如果b′=b，则敌手A赢得了游戏。称上述敌手A为IND-ID-CCA2敌手，并称A在给定安全参数k的情况下赢得游戏的优势为：AdvIND-ID-CCA2Aε(k)=|Pr[b′=b]-0.5|3方案描述3.1算法步骤本方案是由五个算法组成：（1）系统参数生成算法：①输入安全参数k，输出两个阶为素数q的群1022012，48（24）G1G2和双线性映射e:G1´G1®G2。②随机选择群G1的生成元P。③随机选择系统的主密钥sÎZ*q，计算Q=sP。④选择一个正整数n，定义四个密码学哈希函数H1:{}0,1*®G1，H2:G2®{}01n,H3:{01}n´{0,1}nÎZ*q，H4:{01}n®{01}n。定义明文空间M为{01}n，密文空间C为G1´{01}n´{01}n。⑤最后公开Q和系统参数params={qG1G2enPQH1H2H3H4}，保留主密钥s。（2）子结点初始化算法：①每个用户随机选择秘密参数stÎZ*q，t为用户所在的层次数。②公开Yt=stQ。（3）密钥生成算法：①输入用户的身份信息ID，计算Pt=H1{ID1ID2IDt}。②用户的父结点计算用户的私钥skt=st-1Pt。（4）加密算法：①假设接收者的身份信息为(ID1ID2IDt)，则发送方计算Pt=H1{ID1ID2IDt}ÎG1。②发送方随机选择σÎ{01}n。③发送方计算r=H3(σm)。④发送方计算密文：c=[rQ,σH2(e(rYt-1,Pt)),mH4(σ)]（5）解密算法：①令密文c=[UVW]。②接收方计算VH2(e(U,skt))=σ。③接收方计算WH4(σ)=m。3.2算法的完整性证明VH2(e(Uskt))=σH2(e(rYt-1Pt))H2(e(rQst-1Pt))=σH2(e(rst-1QPt))H2(e(rQst-1Pt))=σH2(e(rQst-1Pt))H2(e(rQst-1Pt))=σWH4(σ)=mH4(σ)σ=m3.3方案的安全性证明定理1设哈希函数H1H2H3H4是随机预言机[9-10]，如果存在敌手A能以ε的优势攻破新方案，进行私钥查询qE次，解密查询qD次，H2随机预言机查询qH2次，那么就能构造一个算法B以不可忽略的概率AdvIND-CCA2Bε()k³2ε/(e(1+qE+qD)qH2)在多项式时间内解决BDH难题，其中e»2.71。为了证明这个定理，需要先定义一个称为Basic的方案，它是由keyencryptdecrypt三个算法组成。Key:（1）输入安全参数k，输出两个阶为素数q的群G1G2和e:G1´G1®G2；（2）随机选择群G1的生成元P；（3）随机选择sÎZ*q，计算Q=sP；（4）随机选择PIDÎG*1，计算skID=sPID；（5）选择一个正整数n，定义三个密码学哈希函数H2:G2→{0,1}n,H3:{0,1}n×{0,1}n→Z*q，H4:{0,1}n→{0,1}n；公开参数params{q,G1,G2,e,n,P,PID,Q,H1,H2,H3,H4}，保留私钥skID。Encrypt:（1）发送方随机选择σÎ{01}n；（2）发送方计算r=H3()σm；（3）计算c=[rP,mH2(gr),mH4(σ)]，其中gr=e(PIDQ)。Decrypt:（1）令密文c=[UV