在密钥可委托的层次加密系统中[1,2],所有用户组成一个深度是L的树型结构,树根对应系统主密钥持有方(如密钥生成中心PKG),任何中间节点可为其子节点(或叶子节点)生成密钥.虽然层次加密方案可以机密发送一个消息给多个用户(对应一个子树路径的用户群),但在解密过程中,父节点必须通过密钥委托机制生成与接收用户身份串对应的密钥才能解密.同时,由于树型用户群结构是预先已设计好的,这种层次用户群结构非常不灵活,无 法在实际应用中实现弹性的接收者控制.基于通配身份的加密(wildcard identity-based encryption,简称WIBE)最早由Abdalla等人[3]提出,用于控制不同接收群的消息保密方案,允许身份串中部分元素由通配符*代替,只要任何匹配模板的用户使用其密钥就可以解密.WIBE可以扩展到通配内积加密[4].通配模板加密扩展WIBE,使得收发双方都采用含通配符的向量模板,其典型应用是安全群邮件收发和生物特征模板身份加密.例如,我们想将一封邮件发送到计算机系的所有人员,则可以通过*@cs.edu.cn来实现,这里的*就是通配符.利用通配模板,我们可以有效地管理不同类型的用户群. 层次加密系统密钥委托过程假定委托者与受委托者之间存在传送密钥的可信秘密信道[1,5,6],同时假定密钥对可能的攻击者来说是完全隐藏的(密码算法是公开的),敌手无法获得有关密钥的任何信息[7,8,9].在安全性方面,传统方案中允许敌手询问非匹配挑战身份密钥,无法获得匹配挑战密文身份的解密密钥的任何信息.即使匹配挑战身份的密钥被部分地泄漏(即使是一个比特),可证明安全也将失效. 在实际应用系统中,攻击者可在噪声信道或由侧信道攻击获得有关密钥的部分信息[10,11,12].例如,在层次密钥委托系统中,每个用户都可为其子树节点用户生成委托密钥,但要保证用户与其所有子节点间存在可传输密钥的秘密且可信的信道,这在大规模开放式网络系统,如云计算、物联网及Mesh网等,是非常困难的.进一步来讲,即使密钥被安全地分发,系统密码算法在执行过程中,密钥都必须调入内存被相关算法调用,这极易被攻击以通过冷启动的方法获得密钥的部分信息.密钥弹性泄漏安全的加密方案通过改进密码算法达到在密钥存在可能部分泄漏情况下的语义安全性[10,13,14,15].在密钥委托系统中,每个用户都可生成其子树的密钥,因此更容易受到这类攻击[16,17,18]. Akavia等人[19]于2009年首次引入密钥泄漏下可证明安全的概念,并设计由侧信道攻击产生的抗对称密钥的内存泄漏,引起信息安全领域的高度重视.为了模拟泄漏,设定攻击者能够访问泄漏寓言机(leakage oracle),从而获得关于密钥的任何多项式时间可计算函数的输出.Alwen等人[10]改进了文献[19]的工作,首次构建了基于边界检索模型的抗泄漏公钥加密方案,采用在硬件上不同的存储区来组织密钥,并要求多个密钥存储模块不能同时被泄漏.Dodis等人[20]& lt; /sup>和Chow等人[13]采用哈希证明系统(Hash proof system,简称HPS),分别扩展到了基于公钥和基于身份的抗弹性泄漏的加密方案,但建立在哈希证明系统上的方案不支持主(根)密钥泄漏安全性.虽然HPS提供一般的公钥加密到抗泄漏的转化技术,但在密钥可委托的方案中,无法提供密钥委托的构建[13,15];同时,HPS需要理论模型的随机提取器,在现实中不容易构造[21].Liu等人[15]改进了HPS的构建方法,使其达到更好的抗泄漏性.Lewko等人[16]提出了利用双系统加密技术达到容忍密钥有界泄漏.文献[18]设计了仿射空间作为密钥角色的容忍主密钥和用户密钥连续泄漏的加密方案. 本文了设计一个基于通配模板抗密钥弹性泄漏的加密方案.在该方案中,用户身份关联到含有通配符的身份模板,并可以实现再次密钥委托.加密过程中,接收者定义为含有通配符的身份模板,用以灵活地控制多个不同接收者.本方案可以看作是密钥弹性泄漏安全的层次身份加密HIBE(hierarchical identity-based encryption)[13,16]、模糊身份基加密FIBE(fuzzy identity-based encryption)[22]、隐藏向量加密HVE(hidden vector encryption)[23]等方案的一般扩展. 由于本方案要支持在弹性泄漏条件下的模板密钥委托功能,因此不能直接采用哈希证明系统来构建.要解决的关键问题是:如何保证密钥在部分被泄漏情况下,密钥熵损是可忽略的.为此,借助于代数空间正交向量弹性泄漏容忍映射性质(引理1),我们扩展合数阶双线性群到多维,以实现有界弹性泄漏安全;同时,借助于多维子群向量空间组织双系统空间[16],以实现对方案的自适应性安全性证明.文献[24,25]提出了入侵容忍的加密和签名方案.该系统中 密钥可以在整个生命周期被分割成离散的时间阶段,并可行演化解密密钥. 为了证明本文方案的安全性,利用子群正交性特性隐藏部分向量空间实现抗泄漏性.在实际的构造方案中,密钥和密文都处于正常形态(normal),在证明安全时,我们定义半功能化(semi-functional)的密钥和密文.事实上,半功能化密钥和密文类似HPS中的无效密钥生成器,仅用于安全性证明.根据双系统加密的性质,一个半功能密钥解密一个半功能密文是计算上不可行的.为了达到方案构造中正常形态挑战密文不能被正常形态密钥解密,我们首先将正常形态密文转换为半功能化形式,然后将敌手所询问的正常形态密钥(非匹配密钥)逐步地转换为半功能形式,并将泄漏条件下的密钥转换为支配型半功能形式,最后得到半功能化的挑战密文和密钥.我们证明这一系列转换在计算上是不可区分的.最后,我们证明在敌手获得匹配密文模板的部分密钥后,仍不能构建有效可解密挑战密文的支配型密钥. 1 预备知识 1.1 基本知识 Fp={1,2,…,p-1}.r¬Fp定义为从Fp上随机选取一元素赋值给r.设P=(a1,a2,…,aL)是L个元素的有序集合. 对0≤l≤L, ${P_{ \le \ell }}$是P中前l个元素集合,即${P_{ \le \ell }}$.为方便表述,本文以P来定义模板.本文中,u(l)定义为对安全参数l在计算上是可忽略的函数.设S表示一有限集合,|S|表示S的元素个数;设XÎc,YÎg是两个分别在概率总体X和Y上选取的随机变量,随机变量X的最小熵定义为H¥(X)=-logmaxxÎc[X=x].在已知Y下的X条件 最小熵定义为 ${H_\infty }(X|Y) = \,- \log ({E_{y \leftarrow \gamma }}[{2^{ - {H_\infty }(X|Y = y)}}])$.若X1,X2ÎX,则X1与X2的统计距离为 $SD({X_1},{X_2}) = \frac{1}{2}\sum\limits_{x \in X} {|\Pr [{X_1} = x] - \Pr [{X_2} = x]|} = \mathop {\max }\limits_A \Pr [{X_1} \in A] - \Pr [{X_2} \in A]$ (1) 定义1(计算性不可区分). 对任一概率多项式时间算法A,两个概率总体c,g满足: |Pr[A(l,c)=1]-Pr[A(l,g)=1]|≤u(l), 则称c和g对算法A在安全参数l上是计算不可区分的. 引理1[12]. 设p是素数,m,l,dÎN满足2≤2d≤l≤m,是在Fp随机选取秩是d的矩阵.设是矩阵上输出长度2J≤4pl-2d(p-1)×u(×)2的任意映射,则 SD((X1,f(X1T)),(X1,f(X2)))≤u(×) (2) 特别地,若d=1,m≈l,则f(X2)可以近似泄漏全部的X2. 显然,定理中|X2|=mlogp,允许泄漏大小J=(l-1)logp-2log(1/u(×)),此时,f(X2)以u(×)的统计距离隐藏子空间X1.假定p 是超多项式时间的安全参数,u(p)=1/p是p上的可忽略函数,此时,在f(X2)泄漏允许最大值是(l-3)logp比特时,随机变量X2的函数泄漏f(X2)可以隐藏子空间X1. 推论1. 设m是大于2的整数,p是一大素数.设 $\vec \Delta ,\vec \pi \leftarrow F_p^m,\vec \pi ' \leftarrow V_p^ \bot (\vec \Delta )$( ${V^ \bot }(\vec \pi )$是由基 $\vec \pi $生成向量空间的正交空间).对任一输出长度2J≤4pm-3(p-1)×u(×)2的映射则 $SD((\vec \Delta ,f(\vec \pi ')),\;(\vec \Delta ,f(\vec \pi ))) \le \upsilon ( \cdot )$ (3) 证明:在引理1中,置d=1,l=m-1,则X1对应于向量 $\vec \Delta $的正交空间 ${V^ \bot }(\vec \Delta )$的基,X2对应于 $\vec \pi .T \in R{k_1}(F_p^{(m - 1) \times 1}),\vec \pi '$与X1T同分布.由于\vec \Delta $是从 $F_p^m$上随机选取,X1由$\vec \Delta $所决定,则X1是 $F_p^{m \times (m - 1)}$上的均匀分布,有: $[SD((\vec \Delta ,f(\vec \pi ')),\;(\vec \Delta ,f(\vec \pi ))) = SD(({X_1},f({X_1}T)),({X_1},f({X_2})) \le \upsilon ( \cdot ).$ □ 本文采用正交子群G1和G2作为这里的正交空间.后文我们将分析本文方案的泄漏界J=(Q-1-2c)logp2.这里,Q是方案中的泄漏参数,p2是子群G2的阶,c是一常数,满足 $\upsilon ( \cdot ) = p_2^{ - 2c}$是可以忽略的,其中,2l≤p2≤2l+1. 1.2 合数阶双线性群 一个合数阶双线性群描述包括(N,G,Gt,e),阶N是多个不相等素数之积.设N=p1p2p3,这里,pi(i=1,2,3)满足对i¹j,有gcd(pi,pj)=1.除了满足传统的素数阶群双线性以外,G包含阶分别是p1,p2和p3的子群G1,G2和G3,设其生成元分别是g1,g2和g3,则G中的任一元素都可以唯一表示成的形式.这里,n1,n2,n3ÎFN.合数阶双线性 群除了满足一般双线性群的性质以外,还具有如下特殊性质: 性质1(子群生成元). 设g是G的生成元,则 ${g^{{p_2}{p_3}}}$ 是G1的生成元,${g^{{p_1}{p_3}}}$是G2的生成元, ${g^{{p_1}{p_2}}}$是G3的生成元. 证明:gÎG可以唯一表示成,这里,n1¹0 mod p1,n2¹0 mod p2,n3¹0 mod p3. $g_1^{{n_1}{p_2}{p_3}\,\bmod \,{p_1}}{(g_2^{{p_2}\,\bmod \,{p_2}})^{{n_2}{p_3}}}{(g_3^{{p_3}\,\bmod \,{p_3}})^{{n_3}{p_2}}} = g_1^{{n_1}{p_2}{p_3}\,\bmod \,{p_1}} = {g_1},{g^{{p_2}{p_3}}} = {(g_1^{{n_1}}g_2^{{n_2}}g_3^{{n_3}})^{{p_2}{p_3}}} = {g'_1}$ 由于n1¹0 mod p1且p2和p3与p1互素,根据中国剩余定理,n1p2p3¹0 mod p1,${g^{{p_2}{p_3}}}$是G1的生成元.同理,${g^{{p_1}{p_3}}}$ >是G2的生成元,${g^{{p_1}{p_2}}}$是G3的生成元. □ 性质2(正交性与非退化性). 对任意hiÎGi,hjÎGj,满足: 证明: (1) 非退化性.非退化是由双线性群的基本性质决定的.合数阶的双线性子群仍满足双线性,因此在任意子群(i=j)中,对任意u,vÎGi,满足e(u,v)¹1. (2) 正交性.当i¹j时,hi,hj属于阶分别是pi和pj的子群.设g是G的生成元,根据子群生成元的性质,hi和 hj可以分别表示成 ${({g^{N/{p_i}}})^{{n_i}}}$和 ${({g^{N/{p_j}}})^{{n_j}}}$的形式: $e({h_i},{h_j}) = e({({g^{N/{p_i}}})^{{n_i}}},{({g^{N/{p_j}}})^{{n_j}}}) = e{(g,g)^{{\textstyle{{{n_i}{n_j}{N^2}} \over {{p_i}{p_j}}}}}} = {(e{(g,g)^N})^{{n_i}{n_j}\prod\nolimits_{k = 1,...,3\backslash \{ i,j\} } {{p_k}} }} = 1.$ □ 推论2. 设Gij表示GixGj子群(i¹j).h1ÎGij,h2ÎGjk,则e(h1,h2)=Gt,j.这里,Gt,j表示由e(gj,gj)生成的子群. 文中用Gij记由(gi,gj)生成的阶是p1xp2的子群,用G表示阶是N=p1p2p3的群,即 Gij=GixGj(i,j=1,2,3),G=G1xG2xG3. 2 方案模型 2.1 通配模板及委托 定义2(HIBE). 层次身份的加密(HIBE)采用树型结构组织用户身份串,即.HIBE由5 种算法组成:HIBE=(Setup,KeyExt,KeyDer,Enc,Dec),其中,Setup算法由PKG执行,用于生成整个系统的公开参数及主密钥;KeyExt算法由PKG为任意用户(特别是1级根用户)生成密钥;KeyDer算法由用户密钥持有者为其委托身份串生成密钥;Enc和Dec算法分别由加密者和解密者执行消息的加密和解密操作. 说明:事实上,KeyExt算法利用主密钥为任意身份串生成密钥(任意身份串都是树根的子串),而KeyDer算法利用用户密钥为其委托身份生成密钥,如果把主密钥看成层次为0的身份串(空串)的密钥,则KeyExt和KeyDer算法功能相同.我们可以把PKG看成0级身份串的特殊用户,后面的方案中,我们省掉KeyExt算法. 定义3(身份模板). 设*是特殊的通配符,身份模板是定义在集合元素 ${(\{ 0,1\} \cup \{ *\} )^\ell }$上的一组有序序列.设身份模板 $P = ({a_1},{a_2},...,{a_\ell }) \in {\{ 0,1,*\} ^\ell },P' = ({a_1},{a_2},...,{a_{\ell '}})$,满足:l¢≤l,且 $\left\{ {\begin{array}{*{20}{l}} {{a_i} = {a_i}{\rm{ or }}{a_i} = *,{\rm{ }}1 \le i \le \ell '}\\ {{a_i} = *,{\rm{ }}\ell ' + 1 \le i \le \ell } \end{array}} \right.$ (5) 则称身份模板P¢匹配模板P,记作Match(P¢,P)=1;若模板不匹配,则记为Match(P¢,P)=0. 说明: (1) 若 $P = {(*,*,...,*)^\ell }$,则该模板为长度为l的任意通配模板,若加密给该模板同任何模板长度不大于l的密钥持有者均可解密其对应密文. (2) 若身份模板集定义为{0,1}上的有序串,则本方案等同于HIBE.HIBE是一类特殊的通配模板加密方案. 定义4(模板委托). 设 $P = ({a_1},{a_2},...,{a_\ell }) \in {\{ 0,1,*\} ^\ell }$是长度为l的模板,我们称满足Match(P¢,P)=1的P¢是P的委托模板. 例如,P1=*@*.edu.cn,P2=hbut.edu.cn,则Match(P2,P1)=1.这里,P1=(cn,edu,*,*),P2=(cn,edu,hbut). 设系统最大模板长度为L.在密钥模板方面,功能最强的模板是P=(*,*,…,*)L(记为L),与之对应的密钥SKL相当于系统级主密钥,它可以生成任意其他委托模板密钥,在本方案中称为根密钥.功能最弱的模板是P=f,任意其他模板都可以为之生成密钥. 与密钥模板相反,在密文模板方面,功能最强的身份模板是P=f,意味着没有用户可以解密该密文(只有根密钥才能解密).功能最弱的密文身份模板是P=(*,*,…,*)L,意味着任何人都可以解密该模板对应的密文.显然,通过对密文模板的设计和控制,可以达到加密消息给不同种类和群用户的接收者. 2.2 弹性泄漏通配模板委托加密模型 定义5. 弹性泄漏通配模板委托加密方案由4种概率多项式时间算法组成:P=(Setup,KeyDer,Enc,Dec). · Setup(l,J):以系统安全参数l和密钥泄漏界J为输入,本算法生成系统公开参数和根密钥.系统参数PK公开给所有用户并应用于其他所有算法. · KeyDer():密钥委托算法以通配模板P1及密钥 $S{K_{{P_1}}}$以及委托模板P2为输入,生成委托钥 $S{K_{{P_2}}}.$ · Enc(P¢,M):加密算法以接收者模板P¢以及消息M为输入,输出密文CTP¢. · Dec(SKP,CTP¢):解密算法以系解密密钥SKP和密文CTP¢为输入,输出消息M. 方案一致性. 设fi(×)ÎH是满足 $\sum\nolimits_i {{f_i}(\mathop {SK}\nolimits_P )} \le J$的函数族.若Match(P¢,P)=1,则使用SKP解密CTP¢得到 $\hat M = M$的概率为1,即 $\Pr \left[{\hat M \ne M\left| {\begin{array}{*{20}{l}} {(PK,S{K_\Lambda }) \leftarrow Setup(\lambda ,J)}\\ {Match(P',P) = 1}\\ {\mathop {SK}\nolimits_P \leftarrow KeyDer(\Lambda ,S{K_\Lambda },P)}\\ {\sum\limits_i \,{f_i}(\mathop {SK}\nolimits_P ) \le J}\\ {\mathop {CT}\nolimits_{P'} \leftarrow Enc(P',M)}\\ {\hat M \leftarrow Dec(\mathop {SK}\nolimits_P ,\mathop {CT}\nolimits_{P'} )} \end{array}} \right.} \right] \le \upsilon (\lambda )$ (6) 2.3 弹性泄漏语义安全性 定义6(泄漏寓言机). 泄漏寓言机OLeak以密钥SKP和泄漏界J为输入,对该寓言机的询问由任一多项式时间可计算的函数f:SKP®{0,1}≤J发起,该寓言机计算f(SKP),返回关于SKP的最多J比特的信息.若累计的f(SKP)输出超过J比特,寓言机返回f. 我们允许敌手对同一密钥进行多次泄漏寓言机询问,只要其所获得的泄漏总量不超过系统设定的泄漏界J即可.为了实现同一密钥的多次泄漏询问,可设计一个队列来记录所询问过的密钥及其泄漏总量. 在实际中应用,攻击者可以对用户的密钥在不同时间周期对同一密钥进行泄漏询问,从而避免泄漏寓言机泄漏界的控制.有效的解决措施是,在密钥的泄漏超出泄漏界之前对密钥进行更新.更新后的密钥与更新前的密钥同分布,在旧密钥被删除或不再使用的情况下,敌手对新密钥的泄漏询无法与旧密钥关联,无法生成一个合法的解密钥. 定义7(密钥连续泄漏). 在密码方案中,一个公钥对应多个密钥且具有自身密钥更新的能力,产生一个同分布的随机化密钥,称该方案是抗连续泄漏安全的. 事实上,密钥更新只是对内部的随机数进行更新,由于密钥中隐藏的随机数在解密过程中被约掉,其值不影响密钥的解密能力.特别地,若密钥每使用一次就被更新,则称该密钥是完全连续弹性泄漏安全.密钥的完全弹性泄漏在文献[14,18]中有具体描述. 我们给出达到加密方案语义安全性(semantic security)的密文不可区分性的定义,其安全性高于单向安全性.定义9中的弹性泄漏语义安全性是在允许敌手进行密钥委托OKeyDer和密钥泄漏OLeak条件下的密文不可区分性. 定义8(密文不可区分性). 敌手选择一接收者模板P和两消息(M0,M1),(M0¹M1)且|M0|=|M1|,挑战者随机抛 币mÎ{0,1}并创建密文 $C{T_{{P^*}}} = Enc({P^*},{M_\mu }).$攻击者试图猜测密文 $C{T_{{P^*}}}$中的消息Mm. 定义9(弹性泄漏语义安全性). 对任意多项式时间算法A=(A1,A2,A3),一个层次身份通配模板加密方案P=(Setup,KeyDer,Enc,Dec)在泄漏函数族H(fÎH)上算法A在图 1中的交互模型中获得的优势AdvP,A(l,J)是可忽略的,则该方案是弹性泄漏语义安全的. Fig. 1 Model of leakage-resilient semantic security图 1 弹性泄漏语义安全模型 在本安全模型中,敌手可以利用密钥委托寓言机OKeyDer对非匹配身份模板获得其完整的密钥,而且可以利用泄漏寓言机OLeak对匹配模板获得部分密钥信息. 3 方案设计 设通配模板(l≤L),则l=|P|表示模板的长度.把模板中所有通配符对应的元素索引集合记作S(P)={i|1≤i≤l,ai=*}.同样,把模板中所有不含通配符的元素索引集合记作 $\bar S(P) = \{ i|1 \le i \le \ell ,{a_i} \ne *\} .$显然, $S(P) \cup \bar S(P) = \{ 1,2,...,\ell \} .$ 3.1 设计思路 在该方案中,G1用于编码通配模板;G3用于隐藏密钥;G2子群在具体构造中没有使用,仅用于安全性证明.证明中,通过引入G2元素来构建双系统空间,实现适应性安全性证明.为达到密钥泄漏的容忍,方案中扩展G1空间到 $Q = 1 + 2c + \frac{J}{{\log {p_2}}}$维,Q是正交空间的维度.根据引理1,利用G1和G2之间子空间的正交性,用G2空间提供隐 藏G1空间上的任意映射,从而容忍J比特的密钥泄漏. 设计中,一个通配模板 $P = ({a_1},{a_2},...,{a_\ell }) \in {\{ 0,1,*\} ^\ell }$的密钥形式下: $S{K_P} = ({d_x},{d_y},{d_z}) = \left( {{{(g_1^{{\alpha _i}}{X_i})}_{i \in [Q]}},g_1^{\rho + \langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\limits_{i \in \bar S(P)} {{{({u_{i,0}} \cdot u_{i,1}^{{a_i}})}^{{r_i}}}} \cdot Y,{{(g_1^{{r_i}}{Z_i})}_{i \in \bar S(P)}}} \right) \in G_{13}^{Q + 1 + |\bar S(P)|}$ (7) 其中,dx扩展G1空间到Q维,用于隐藏含有r的dy关联模板P中所有非通配符的元素,并通过dz与模板中每一个非通配元素关联. 设计中的一个发送给身份模板 $P' = ({a_1},{a_2},...,{a_{\ell '}})$的消息密文结构是: $C{T_{P'}} = ({c_0},{c_1},{c_2},{c_3},{c_4}) = (M \cdot {\Omega ^s},{(g_1^{s{\beta _i}})_{i \in [Q]}},g_1^s,{({({u_{i,0}}u_{i,1}^{{a_i}})^s})_{i \in \bar S(P')}},{(u_{i,j}^s)_{i \in S(P'),j \in \{ 0,1\} }}) \in G_1^{Q + 1 + |P'|} \times {G_t}$ 其中,c0用于保密消息M,c1隐藏随机数,c3和c4分别对应接收者模板P¢中的非通配元素和通配元素.在解密过程中,非通配部分(对应模板索引是$\bar S({P_1}) \cap \bar S({P_2})$)采用类似HIBE的方法,实现密钥组件与密文组件的双线性配对运算,而密文模板中对应位是通配符(Pi=*).此时,模板索引是 $S(P) \cap \bar S(P')$ .解密过程中,需要先把通配符委托为与Pi相等的非通配符,以实现对应组件配对运算. 3.2 方案构造 · Setup(l,J) 给定安全参数l和系统允许的弹性泄漏界J,算法首先调用双线性群生成算法G生成F=(N=p1p2p3,G,Gt,e)¬ j(l),然后执行下列步骤: 1. 根据双线性群安全参数l满足2l≤p2≤2l+1,找出一个常数c,使得 $p_2^{ - 2c}$对安全参数λ来说在计算上是可忽略的.置 $Q = 1 + 2c + \frac{J}{{\log {p_2}}};$ 2. 随机选取子群生成元g1ÎG1,g3ÎG3; 3. 随机选择rÎFN,计算W=e(g1,g1)r;对iÎ[Q],随机选取,ai,biÎFN; 4. 对i=1,…,L(L是系统允许的身份模板最大长度,即L=|L|),j=0,1,随机选取ui,jIcirc;G1; 5. 对iÎ[Q],随机选取XiÎG3.同时选取YÎG3; 6. 设置根模板密钥: $S{K_\Lambda } = ({d_x},{d_y}) = ({(g_1^{{\alpha _i}}{X_i})_{i \in [Q]}},g_1^{\rho + \langle \vec \alpha ,\vec \beta \rangle }Y)$ (9) 7. 公开系统参数: $PK = (\Phi ,{g_1},{g_3},{(g_1^{{\beta _i}})_{i \in [Q]}},{({u_{i,j}})_{i \in [L],j \in \{ 0,1\} }},\Omega )$ (10) 说明:系统根密钥对应于模板L=(*,*,…,*)L的密钥,此时,S(L)={1,2,…,L},而.SKL写成一般密钥结构形式如下: 其中,dz组件关联模板P中的非通配符,在根密钥中,dz=f. · KeyDer( ${P_1},S{K_{{P_1}}},{P_2}$) 设身份模板 ${P_1} = ({a_1},{a_2},...,{a_\ell })$对应的密钥是: 一个P1的委托模板 ${P_2} = ({a_1},{a_2},...,{a_{\ell '}})$满足Match(P2,P1)=1.利用 $S{K_{{P_2}}}$生成P2的委托密钥过程如下: 1. 对 $i \in \bar S({P_2})$,随机选取riÎFN,ZiÎG3**; 2. 对iÎ[Q],随机选取XiÎG3以及YÎG3,然后随机选取向量 $\vec \alpha \in F_N^Q;$ 3. 计算: $\begin{array}{l} S{K_{{P_2}}} = ({d_x},{d_y},{d_z})\\ {\rm{ }} = \left( {{{(\mathop {\hat d}\nolimits_{x,i} g_1^{{\alpha _i}}{X_i})}_{i \in [Q]}},\;\mathop {\hat d}\nolimits_y \cdot g_1^{\langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\limits_{i \in \bar S({P_2})} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}Y} ,{{(\mathop {\hat d}\nolimits_{{z_i}} g_1^{{r_i}}{Z_i})}_{i \in \bar S({P_1}) \cap \bar S({P_2})}}} \right)\\ {\rm{ }} = \left( {{{(g_1^{{\alpha _i}}{X_i})}_{i \in [Q]}},\;g_1^{\rho + \langle \vec \alpha ',\;\vec \beta \rangle } \cdot \prod\limits_{i \in \bar S({P_2})} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}Y'} ,{{(g_1^{{r_i}}{Z_i})}_{i \in \bar S({P_2})}}} \right) \end{array}$ (12) 这里, .由于这些随机数是均匀分布的,因此,委托密钥 $S{K_{{P_2}}}$与其父密钥 $S{K_{{P_1}}}$具有相同分布特性. · Enc(P¢,M) 为加密消息M给身份模板,加密算法执行:随机选取sÎFN,计算密文CTP¢=(c0,c1,c2,c3,c4).即 $[C{T_{P'}} = ({c_0},{c_1},{c_2},{c_3},{c_4}) = (M \cdot {\Omega ^s},{(g_1^{s{\beta _i}})_{i \in [Q]}},g_1^s,{({({u_{i,0}}u_{i,1}^{{a_i}})^s})_{i \in \bar S(P')}},{(u_{i,j}^s)_{i \in S(P'),j \in \{ 0,1\} }})$ (13) · Dec(SKP,CTP¢) 若Match(P¢,P)=0,返回^.密钥模板P中非通配符部分与密文模板P¢中非通配符部分相等,根据模板定义,模板索引为 $\bar S(P) \cap \bar S(P')$对应位要相等,类似HIBE的解密思路,利用对应组件作配对运算.密钥模板Pi位是非通配符(Pi¹*),而密文模板对应位是通配符(Pi=*),此时,模板索引是 $S(P) \cap \bar S(P')$.要把通配符委托为与Pi相等的 非通配符,以实现对应组件配对运算.解密过程计算如下: $ A = \prod\limits_{i \in \bar S(P) \cap \bar S(P')} {e({d_{{z_i}}},{c_{3,i}})} \,\times \prod\limits_{i \in S(P) \cap \bar S(P')} {e({d_{{z_i}}},{c_{4,i,0}} \cdot c_{4,i,1}^{{a_i}})} $ (14) $ B = \frac{{e({d_y},{c_2})}}{{\prod\nolimits_{i \in [Q]} {e({d_{x,i}},{c_{1,i}})} }}$ (15) M¬c0A/B (16) 3.3 解密一致性 $\begin{array}{l} A = \prod\limits_{i \in \bar S(P) \cap \bar S(P')} {e({d_{{z_i}}},{c_{3,i}})} \times \prod\limits_{i \in S(P) \cap \bar S(P')} {e({d_{{z_i}}},{c_{4,i,0}} \cdot c_{4,i,1}^{{a_i}})} \\ {\rm{ }} = \prod\limits_{i \in \bar S(P) \cap \bar S(P')} {e(g_1^{{r_i}}{Z_i},{{({u_{i,0}} \cdot u_{i,1}^{{a_i}})}^s})} \times \prod\limits_{i \in S(P) \cap \bar S(P')} {e(g_1^{{r_i}}{Z_i},u_{i,0}^s \cdot u_{i,1}^{{a_i}s})} \\ {\rm{ }} = \prod\limits_{i \in \bar S(P) \cap \bar S(P')} {e(g_1^{{r_i}},{{({u_{i,0}} \cdot u_{i,1}^{{a_i}})}^s})} \times \prod\limits_{i \in S(P) \cap \bar S(P')} {e(g_1^{{r_i}},u_{i,0}^s \cdot u_{i,1}^{{a_i}s})} \\ {\rm{ }} = \prod\limits_{i \in \bar S(P')} {e{{(g_1^{{r_i}},{u_{i,0}}u_{i,1}^{{a_i}})}^s}} \end{array}$ (17) $\begin{array}{l} B = \frac{{e({d_y},{c_2})}}{{\prod\nolimits_{i \in [Q]} {e({d_{x,i}},{c_{1,i}})} }}\\ {\rm{ }} = \frac{{e(g_1^{\rho + \langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\nolimits_{i \in \bar S(P')} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}Y} ,g_1^s)}}{{\prod\nolimits_{i \in [Q]} {e(g_1^{{\alpha _i}}{X_i},g_1^{s{\beta _i}})} }}\\ {\rm{ }} = \frac{{e(g_1^{\rho + \langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\nolimits_{i \in \bar S(P')} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}} ,g_1^s)}}{{\prod\nolimits_{i \in [Q]} \,e(g_1^{{\alpha _i}},g_1^{s{\beta _i}})}}\\ {\rm{ }} = \frac{{e(g_1^\rho ,g_1^s)e(g_1^{\langle \vec \alpha ,\vec \beta \rangle },g_1^s)e(\prod\nolimits_{i \in \bar S(P')} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}} ,g_1^s)}}{{e{{({g_1},{g_1})}^{s\sum\nolimits_{i \in [Q]} {{\alpha _i}{\beta _i}} }}}}\\ {\rm{ }} = \frac{{e{{({g_1},{g_1})}^{\rho s}}e(g_1^{\sum\nolimits_{i \in [Q]} {{\alpha _i}{\beta _i}} },g_1^s)\prod\nolimits_{i \in \bar S(P')} {e({{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}},g_1^s)} }}{{e{{({g_1},{g_1})}^{s\sum\nolimits_{i \in [Q]} {{\alpha _i}{\beta _i}} }}}}\\ {\rm{ }} = A \cdot e{({g_1},{g_1})^{\rho s}} \end{array}$ (18) 4 安全性证明 4.1 数学难题假设 为了证明所设计方案的安全性,本文使用如下基于合数阶(子)群判定问题,该假设在文献[8]中已作分析. 设Φ=(N=p1p2p3,G=G1xG2xG3,Gt,e)是阶为N的双线性群,其中,p1,p2和p3是互素的大素数,满足2l≤p2≤2l+1.下列假设在给定部分已知信息的情况下,猜出m的概率优势对于安全参数l是可忽略的,即u(l)≈0. 数学假设1. 给定双线性群Φ以及g1,g3,区分子群G1和G12中的元素是困难的,即 $\Pr \left[{\mu = 0\left| {\begin{array}{*{20}{l}} {{g_1} \in {G_1},{g_3} \in {G_3}}\\ {\mu \leftarrow \{ 0,1\} }\\ {{T_0} \leftarrow {G_1},{T_1} \leftarrow {G_{12}}}\\ {{T_\mu } = \mu ({T_0} - {T_1}) + {T_1}} \end{array}} \right.} \right] = \frac{1}{2} + \upsilon ( \cdot ).$ 数学假设2. 给定双线性群Φ,g1,g3,X1X2和Y2Y3,区分子群G12中随机元素和G中的元素是困难的,即 $\Pr \left[{\mu = 0\left| {\begin{array}{*{20}{l}} {{g_1} \in {G_1},{g_3} \in {G_3}}\\ {{X_1}{X_2} \in {G_{12}},{Y_2}{Y_3} \in {G_{13}}}\\ {\mu \leftarrow \{ 0,1\} }\\ {{T_0} \leftarrow {G_{13}},{T_1} \leftarrow G}\\ {{T_\mu } = \mu ({T_0} - {T_1}) + {T_1}} \end{array}} \right.} \right] = \frac{1}{2} + \upsilon ( \cdot ).$ 数学假设3. 给定双线性群Φ,g1,g2,g3以及% $g_1^\rho {X_2}$和 $g_1^s{Y_2}$,区分判断e(g1,g1)rs与Gt中的随机元素是困难的,即 $\Pr \left[{\mu = 0\left| {\begin{array}{*{20}{l}} {{g_1} \in {G_1},{g_2} \in {G_2}}\\ {{g_3} \in {G_3},\;g_1^\rho {X_2},g_1^s{Y_2} \in {G_{12}}}\\ {\mu \leftarrow \{ 0,1\} }\\ {{T_0} = e{{({g_1},{g_1})}^{\rho s}},{T_1} \leftarrow {G_t}}\\ {{T_\mu } = \mu ({T_0} - {T_1}) + {T_1}} \end{array}} \right.} \right] = \frac{1}{2} + \upsilon ( \cdot ).$ 4.2 抗泄漏安全性证明 4.2.1 半功能密钥与密文 采用双系统技术,我们设计半功能化的密钥和密文形式.基本方法是,对原来密钥和密文组件乘以G2中的随机元素(G2在实际方案中没有涉及,仅用于安全性证明中设计半功能化密文或密钥). · 半功能密钥 设SKP=(dx,dy,dz)是KeyDer算法生成的正常形态密钥.随机选取kÎFN.对iÎ[Q],随机选择diÎFN;对 $i \in \bar S(P),$随机选择ziÎFN,计算: $[S{K_P} = (\mathop {\hat d}\nolimits_x ,\mathop {\hat d}\nolimits_y ,\mathop {\hat d}\nolimits_z ) = ({({d_{{x_i}}} \cdot g_2^{{\delta _i}})_{i \in [Q]}},{d_y}g_2^k,{({d_{{z_i}}} \cdot g_2^{{z_i}})_{i \in \bar S(P)}}).$ · 半功能密文 设CTP=(c0,c1,c2,c3,c4)是调用Enc算法生成的正常形态密文.随机选取xÎFN.对iÎ[Q],随机选择qiÎFN;对 $i \in \bar S(P)$,选取tiÎFN;对iÎS(P),jÎ{0,1},随机选择 $\mathop {\hat z}\nolimits_{i,j} \in {F_N}:$ $C{T_P} = (\mathop {\hat c}\nolimits_0 ,\mathop {\hat c}\nolimits_1 ,\mathop {\hat c}\nolimits_2 ,\mathop {\hat c}\nolimits_3 ,\mathop {\hat c}\nolimits_4 ) = ({c_0},{({c_{1,i}} \cdot g_2^{{\theta _i}})_{i \in [Q]}},{c_2} \cdot g_2^x,{({c_{3,i}} \cdot g_2^{{t_i}})_{i \in \bar S(P)}},{({c_{4,i,j}} \cdot g_2^{\mathop {\hat z}\nolimits_{i,j} })_{i \in S(P),j \in \{ 0,1\} }}).$ 一个半功能密钥要成功地解密一个半功能密文,除了密文模板P¢与密钥模板P满足Match(P¢,P)=1外,还要求G2部分可以约去,即,利用半功能密钥SKP和半功能密文CTP¢代入公式(14)~公式(16)时,使得: $e{({g_2},{g_2})^{\langle \vec \delta ,\vec \theta \rangle }}e{({g_2},{g_2})^{x - k}}e{({g_2},{g_2})^{\prod\nolimits_{i \in S(P) \cap \bar S(P')} {{z_i} - {t_i}} }}e{({g_2},{g_2})^{\prod\nolimits_{i \in \bar S(P) \cap \bar S(P')} {{z_i} - \mathop {\hat z}\nolimits_{i,0} \mathop {\hat z}\nolimits_{i,1}^{{a_i}} } }} = 1$ (19) 即 $\langle \vec \delta ,\vec \theta \rangle + x - k + \prod\limits_{i \in S(P) \cap \bar S(P')} {({z_i} - {t_i})} + \prod\limits_{i \in \bar S(P) \cap \bar S(P')} {({z_i} - \mathop {\hat z}\nolimits_{i,0} \mathop {\hat z}\nolimits_{i,1}^{{a_i}} )} = 0{\rm{ }}\bmod {\rm{ }}{p_2}$ (20) 根据双系统加密的性质,攻击者在未知解密密钥的情况下,敌手能够成功地解密挑战密文的优势等价于一个半功能密钥成功解密一个半功能密文的概率优势.在等式(20)中,除ai外,其他变量都是从FN中均匀选取的,使得该等式成立的概率是1/p2. 接下来我们考虑更特殊的情况,即,在敌手获得部分解密密钥(密钥弹性泄漏)的情况下,是否敌手存在解密挑战密文的优势.若一个半功能密钥可以成功地解密一个半功能密文,则称该密钥是支配型半功能的;否则,称该密钥是真半功能的.为此,我们要证明的是:在敌手获得部分泄漏的情况下,构造一个支配型半功能密钥的概率优势是可忽略的. 4.2.2 不可区分性游戏 为了给出形式化的安全性证明,我们使用一系列游戏,用于实现把正常形式的询问密钥和挑战密文转换为半功能形式的密钥和密文: 1. ΓReal:本游戏中密文和密钥均为正常形式,即,密文和密钥由P算法生成,敌手执行安全性的弹性泄漏语义安全模型. 2. ΓCSF:本游戏与ΓReal游戏的区别在于,在挑战阶段的输出用半功能密文CTP. 3. ${\Gamma _{KS{F_j}}}:$设q是敌手在安全游戏中对密钥的最大询问次数.在本游戏中,密文仍是半功能化的;同时,对 ≤j的密钥是半功能密钥,而>j的密钥是正常形式的密钥,对第j个密钥是加入安全假设的实例.显然,当j=0时, ${\Gamma _{KS{F_0}}} = {\Gamma _{CSF}}$;j=q时,中生成的密文和密钥都是半功能的.当1≤j≤q时,本游戏中密钥中前j-1个是半功能的,后面的都是正常密钥.我们证明,对所有j, ${\Gamma _{KS{F_j}}}$与 ${\Gamma _{KS{F_{j + 1}}}}$在计算上是不 区分的. 4. 本游戏与的区别在于,允许敌手对满足匹配密文的模板作泄漏询问OLeak,其泄漏量最大是J比特.我们证明:敌手在该游戏中,在已获得部分匹配密钥泄漏的条件下,不能成功构造成支配型密钥. 5. ΓCM:本游戏在 ${\Gamma _{L{R_q}}}$的基础上,将密文中的c0组件用Gt的随机元素替换. 在第1个游戏中,密钥和密文均是正常形式(由第3节的算法生成);而最后,游戏ΓCM中,密钥和密文均是半功能化的,且消息组件c0是Gt中的随机元素.对于最后一个游戏,密钥和密文全是半功能化,利用双系统性质,半功能密钥不能解密一半功能密文.而对于半功能化生成算法中未变化的组件c0,与一个随机元素不可区分.如果我们所设计的一系列游戏在计算上是不可区分的,这样反推第1个游戏中的密文获得对询问密钥情况来说则无法解密. 4.2.3 形式化证明 为了形式化证明本文方案的安全性,本节证明游戏之间在安全参数上是概率不可区分的.而根据双系统加密系统的定理,对于半功能密钥解密,真半功能挑战密文是不可行的.我们得出如下定理: 定理1(抗泄漏语义安全性). 一个层次通配模板加密方案P=(Setup,KeyDer,Enc,Dec),敌手可以询问对任意密钥(匹配和非匹配密钥)上的关于泄漏函数fÎH上的最多J比特泄漏,以及非匹配挑战密钥的密钥提取询问, 在安全数学假设1~假设3下,若敌手在游戏ΓReal,ΓCSF,和ΓCM之间是安全参数l上计算不可区分的,则该方案是(l,J)-弹性泄漏安全语义的. 证明:我们采用不可区分证明的引理(2)~引理(5)来证明方案的安全性.ΓReal是本文提出构造方案(密文在G1 子群,而密钥在G13子群).ΓCSF表明,敌手无法区分半功能挑战密文和正常形态密文.用于描述半功能密钥不能解密半功能密文.用于描述敌手在获得匹配模板泄漏询问OLeak的基础上,不能将一半功能化密钥转换 成支配型半功能密钥.ΓCM描述消息隐藏组件与随机元素不可区分.从敌手的角度来看,ΓCM中的元素是随机化的,因此无法解密挑战密文. □ 接下来给出引理(2)~引理(5)的详细证明. 引理2. 若安全假设1存在,则任何多项式时间内的算法A=(A1,A2,A3)对ΓReal和ΓCSF是计算上不可区分的. 证明:假设一种多项式时间算法A以不可忽略的优势区分ΓReal和ΓCSF,我们可以构建一种算法B作为模拟器,以相同的优势解决假设1难题.当B收到假设1的实例后,其目标是猜测元素TÎG1还是TÎG12.为此,B扮演模拟器并回答A的询问及挑战. 在系统初始化阶段,B选择使得 $p_2^{ - 2c}$可忽略的c,计算 $Q = 1 + 2c + \frac{J}{{\log {p_2}}}.$然后随机选取生成元g1ÎG1,g3ÎG3.对iÎ[J],jÎ{0,1},随机选取ui,jÎG1.随机选取X1,…,XQ,YÎG3.在有限域FN上随机选取r,a1,b1,…,aQ,bQÎFN.置系统参数 $PK = (\Phi ,{g_1},{g_3},{(g_1^{{\beta _i}})_{i \in [Q]}},{({u_{i,j}})_{i \in [L],j \in \{ 0,1\} }},\Omega = e{({g_1},{g_1})^\rho }),$并发送给A.由于B知道 $\vec \alpha $和r,可以生成系统根密钥 SKL,并为任何子模板生成委托密钥;同时,可以回答敌手A的密钥委托和密钥泄漏询问. 当A请求挑战,并提交给B两个挑战消息(M0,M1)及一个挑战通配模板P时,B随机选择m¬{0,1},计算并返回挑战密文 $C{T_{{P^*}}} = ({M_\mu }e(T,{g^\rho }),{({T^{{\beta _i}}})_{i \in [Q]}},T,{(u_{i,j}^{a_i^*})_{i \in \bar S({P^*})}},{({u_{i,j}})_{i \in S({P^*}),jin\{ 0,1\} }}).$ B知道根密钥,在询问2阶段仍然可以回答A的密钥提取询问.在输出阶段,A输出对密文中消息挑战消息 Mm的猜测m¢.B以相同的输出m¢作为对假设1的猜测:若m¢=0,则TÎG1;若m¢=1,则TÎΓ12.显然,若TÎG1,则密文 $C{T_{{P^*}}}$是正常形态的(密文中没有G2部分),此时,B可以正确模拟ΓReal.若 $T = g_1^{{n_1}}g_2^{{n_2}} \in {G_{12}}$,则$C{T_{{P^*}}}$是半功能化的. 对敌手来说,密文组件中G2部分不为1,此时可以正确模拟ΓCSF.若算法A可以成功输出m¢=m,则B以m¢作为安全假设的应答.因此,当安全假设1存在时,ΓReal和ΓCSF在计算上是不可区分的. □ 引理3. 若假设2存在,则在任意多项式时间内,算法A=(A1,A2,A3)对1≤j≤q-1, ${\Gamma _{KS{F_j}}}$和 ${\Gamma _{KS{F_{j + 1}}}}$是计算上不 可区分的. 证明:显然,当j=0时, ${\Gamma _{KS{F_0}}} = {\Gamma _{CSF}}$.若存在一种多项式时间的算法A以不可忽略的优势区分 ${\Gamma _{KS{F_j}}}$和 ${\Gamma _{KS{F_{j + 1}}}},$ 则可以构建一种算法B,以相同的优势解决安全假设2.B的目标是:收到假设2的实例(Φ,g1,g3,X1X2,Y2Y3,T)后,推断TÎG13还是TÎG.B所要做的工作是:当TÎG13时,成功模拟 ${\Gamma _{KS{F_j}}};$当TÎG时,成功模拟 初始化阶段,B选择使得 $p_2^{ - 2c}$可忽略的c,计算 $Q = 1 + 2c + \frac{J}{{\log {p_2}}}.$随机选取g1,u1,0,u1,1,…,uL,0,uL,1ÎG1,g3ÎG3.在有限域FN上随机选取r,a1,b1,…,aQ,bQÎFN.置系统参数 $PK = (\Phi ,{g_1},{g_3},{(g_1^{{\beta _i}})_{i \in [Q]}},{({u_{i,j}})_{i \in [L],j \in \{ 0,1\} }},\Omega = e{({g_1},{g_1})^\rho }).$ 对于A的密钥询问,B的回答分为以下3种情况: 1. 对前面j-1个密钥,B以半功能化密钥形式作应答: $S{K_P} = \left( {{{(g_1^{{\alpha _i}}{X_i}{X_i})}_{i \in [Q]}},g_1^{\rho + \langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\limits_{i \in \bar S(P)} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}YY'} ,{{(g_1^{{r_i}}{Z_i}{Z_i})}_{i \in \bar S(P)}}} \right),$ 其中,$ ${X_i},Y,{Z_i} \in {G_3},{X'_i},Y',{Z'_i} \in {G_2};$ 2. 对第j个密钥,B以挑战T来生成密钥: $S{K_P} = \left( {{{({T^{{\alpha _i}}})}_{i \in [Q]}},{T^{\rho + \langle \vec \alpha ,\vec \beta \rangle }} \cdot \prod\limits_{i \in \bar S(P)} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}} ,{{({T^{{r_i}}})}_{i \in \bar S(P)}}} \right);$ 3. 从j+1密钥开始,B输出正常形态密钥: $S{K_P} = \left( {{{(g_1^{{\alpha _i}}{X_i})}_{i \in [Q]}},g_1^{\rho + \langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\limits_{i \in \bar S(P)} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}Y} ,{{(g_1^{{r_i}}{Z_i})}_{i \in \bar S(P)}}} \right).$ 在挑战阶段,对挑战的通配模板 ${P^*} = (a_1^*,a_2^*,...,a_\ell ^*),$输出半功能挑战密文: $C{T_{{P^*}}} = ({M_\mu } \cdot e({X_1}{X_2},g_1^\rho ),{({({X_1}{X_2})^{{\beta _i}}})_{i \in [Q]}},({X_1}{X_2}),{({u_{i,0}}u_{i,1}^{a_i^*})_{i \in \bar S({P^*})}},{({u_{i,j}})_{i \in S({P^*}),j \in \{ 0,1\} }}).$ 使用一个正常密钥解密半功能挑战密文,若Match(P,P)=1且TÎG13,则能正常解密,此时成功模拟 ${\Gamma _{KS{F_j}}}.$使用一个半功能密钥来解密半功能挑战密文,当Match(P,P)=1且 $T = g_1^{{n_1}}g_2^{{n_2}}g_3^{{n_3}} \in G( = {G_{123}})$时,采用Dec算法进行配对运算时,由于密文和密钥都有g2部分,配对计算产生额外的g2相关的部分.设,则解密配对运算后G2部分是 $e{({g_2},{g_2})^{{m_2} - {n_2} + {m_2}{n_2}\sum\nolimits_{i \in [Q]} {{\alpha _i}{\beta _i}} }}.$若敌手成功解密 $C{T_{{P^*}}},$则 ${m_2} - {n_2} + {m_2}{n_2}\sum\nolimits_{i \in [Q]} {{\alpha _i}{\beta _i}} = 0{\rm{ m}}od{\rm{ }}{p_2},$而m2和n2是${F_{{p_2}}}$均匀分布的,此时成功模拟 ${\Gamma _{KS{F_{j + 1}}}}.$若算法A可以成功地区分 ${\Gamma _{KS{F_j}}}$和 ${\Gamma _{KS{F_{j + 1}}}},$则B可以以A的区分输出优势解决安全假设2的判定. □ 引理3证明了算法A在非匹配密钥泄漏条件下无法区分 ${\Gamma _{KS{F_j}}}$和 ${\Gamma _{KS{F_{j + 1}}}}.$接下来我们证明:对于匹配密钥SKP满足Match(P,P)=1,算法A获得部分密钥泄漏的条件下,仍不能将一个半功能密钥SKP转换为可以解密挑战密文 $C{T_{{P^*}}}$的支配型半功能密钥.该引理如下: 引理4. 设系统泄漏界J=(Q-1-2c)logp2,c是一个正整数，使得 $p_2^{ - 2c} \le \upsilon (\lambda ).$对任意一种多项式时间算法A,在 ${\Gamma _{KS{F_j}}}$游戏中把第j个密钥SKP关联到匹配挑战密文通配模板 $C{T_{{P^*}}},$即Match&l t;/ span>(P,P)=1,此时,A将这个半功能 密钥转换成支配型半功能化密钥的概率优势是可忽略的. 证明:假设一种多项式时间算法A以不可忽略的概率优势实现支配型半功能密钥转换,我们可以构造一种算法B,以相同的优势区分两个分布 $(\vec \Delta ,f(\vec \pi ))$和 $(\vec \Delta ,f(\vec \pi ')),$而这两个分布在引理1中已证明是不可区分的,并在推论1中给予进一步的细化.在推论1中,B首先置m=Q+1,d=1,p=p2(其中,p2是N的一个素数因子).算法B的目标是,借助A的不可忽略的转换能力来区分$(\vec \Delta ,f(\vec \pi ))$和$(\vec \Delta ,f(\vec \pi ')) B模拟游戏 ${\Gamma _{KS{F_j}}}$过程如下:首先运行Setup算法生成根密钥MSKL和公开参数PK.显然,由于知道系统根密钥,B可以回答敌手的任何询问,包括密钥提取和泄漏询问,但不能获得对挑战模板P相匹配的模板密钥提取询问,即,所询问的委托密钥SKP=KeyDer(L,SKL,P)满足Match(P,P)¹1(否则,A获得了完整的解密钥).我们允许A对任何满足Match(P,P)=1的模板P请求泄漏询问. 对于匹配挑战模板P(即Match(P,P)=1)的密钥泄漏询问,B应答如下:设fÎH是个概率多项式时间的泄漏函数,输入域是$F_{{p_2}}^{Q + 1},$输出域大小是{0,1}J.B收到推论1的输出 $(\vec \Delta ,f(\vec \pi )),$这里,是或B使用分布回答A的第j个密钥泄漏询问: 首先根据KeyDer算法生成一个正常形态的密钥SKP,然后随机选取$ $r \in {F_{{p_2}}},\vec \theta \in F_{{p_2}}^{|\bar S(P)|},$置半功能化密钥中的G2子群部分是: $(\underbrace {{b_1},...,{b_Q}}_{{d_x}},\underbrace {{b_{Q + 1}} + r}_{{d_y}},\underbrace {{\theta _1},...,{\theta _{|\bar S(P)|}}}_{{d_z}}).$ A请求询问挑战模板P,若第j模板不匹配P,即Match(P,P)¹1,B模拟失败,并随机输出 $\vec \pi $作为对 $\vec \Delta $是否正交的猜测;否则,第j模板满足Match(P,P)=1.设 $k = |\bar S({P^*})|$,B选择 ${t_1},...,{t_k},{z_{1,0}},{z_{1,1}},...,{z_{k,0}},{z_{k,1}} \in {F_{{p_2}}},$满足: $r{\Delta _{Q + 1}} - \prod\limits_{i \in S(P) \cap \bar S({P^*})} {({\theta _i} - {t_i})} - \prod\limits_{i \in \bar S(P) \cap \bar S({P^*})} {({\theta _i} - {z_{i,0}}z_{i,1}^{a_i^*})} = 0{\rm{ }}\bmod {\rm{ }}{p_2}$ (21) 接着调用Enc算法创建模板P的密文,然后以 $({(\Delta )_{i \in [Q]}},{\Delta _{Q + 1}},\vec t,\vec z)$作为挑战密文的半功能因子,即, $C{T_{{P^*}}}$的G2部分是: $(0,\underbrace {{\Delta _1},...,{\Delta _Q}}_{{c_1}},\underbrace {{\Delta _{Q + 1}}}_{{c_2}},\underbrace {{t_1},...,{t_k}}_{{c_3}},\underbrace {{z_{1,0}},{z_{1,1}},...,{z_{k,0}},{z_{k,1}}}_{{c_4}}).$ 若向量 $\vec \Delta $与 $\vec b$正交,即 $\langle \vec \Delta ,\vec b\rangle = 0$,则第j个密钥是支配型半功能的;若$\vec \Delta $与$\vec b$不正交,则挑战密钥是真半功能 的.半功能密钥和半功能密文配对运算后,并根据公式(21)结果,e(g2,g2)部分的指数是: 显然,若公式(22)为0,即向量$\vec \Delta $与 $\vec b$正交,则解密配对运算后e(g2,g2)0=1,该密钥是支配型半功能的;否则, $\langle \vec \Delta ,\vec b\rangle \ne 0$,该密钥是真半功能的.若A可以将一半功能密钥转换为支配型半功能的,则B以算法&l t;/ span>A的输出区分两个分布 $(\vec \Delta ,f(\vec \pi ))$和 $(\vec \Delta ,f(\vec \pi )).$这与引理1及其推论1矛盾.因此,不存在多项式时间算法构建支配型半功能 密钥. □ 引理5. 若安全假设3存在,任何多项式时间内的算法A=(A1,A2,A3)区分 ${\Gamma _{L{R_q}}}$和ΓCM是计算上不可区分的. 证明:设一种多项式时间的算法A以不可忽略的优势区分${\Gamma _{L{R_q}}}$和ΓCM,我们构建算法B,以相同的优势解决安全假设3的判定.当收到假设3的实例 $(\Phi ,{g_1},{g_2},{g_3},g_1^\rho {X_2},g_1^2{Y_2},T)$时,B的目标是输出T=e(ga,gs)还是T只能为Gt中的随机元素的猜测. 初始化阶段,B选择使得 $p_2^{ - 2c}$可忽略的c,计算 $Q = 1 + 2c + \frac{J}{{\log {p_2}}}$.然后随机选取g1,u1,0,u1,1,…,uL,0,uL,1ÎG1,g2ÎG2,g3ÎG3.在有限域FN上,随机选取a1,b1,…,aQ,bQÎFN.置 $PK = (\Phi ,{g_1},{g_3},{(g_1^{{\beta _i}})_{i \in [Q]}},{({u_{i,j}})_{i \in [L],j \in \{ 0,1\} }},\Omega = e{({g_1},{g_1})^\rho }).$ 值得注意的是,虽然B不知道r,但可以利用$g_1^\rho {X_2}$来计算,即 $\Omega = ({g_1},g_1^\rho {X_2}) = e{({g_1},{g_1})^\rho }.$ 在密钥询问阶段,B生成并回答半功能密钥: $[S{K_P} = \left( {{{(g_1^{{\alpha _i}}{X_i})}_{i \in [Q]}},(g_1^\rho {X_2})g_1^{\langle \vec \alpha ,\vec \beta \rangle } \cdot \prod\limits_{i \in \bar S(P)} {{{({u_{i,0}}u_{i,1}^{{a_i}})}^{{r_i}}}Y} ,\;{{(g_1^{{r_i}})}_{i \in \bar S(P)}}} \right).$ 在挑战阶段,算法A提交两个挑战的消息(M0,M1)及一挑战模板 ${P^*} = (a_1^*,a_2^*,...,a_\ell ^*),$B随机选择m¬{0,1},生成 半功能挑战密文: $C{T_{{P^*}}} = ({M_\mu }T,{(g_1^{{\beta _i}})_{i \in [Q]}},(g_1^s{Y_2}),{({u_{i,0}}u_{i,1}^{a_i^*})_{i \in \bar S({P^*})}},{({u_{i,j}})_{i \in S({P^*}),j \in \{ 0,1\} }})$ 若T=e(gr,gs), $C{T_{{P^*}}}$是半功能化的,而SKP是支配型半功能密钥,可以成功解密$C{T_{{P^*}}}$B成功地模拟游戏 ${\Gamma _{L{R_q}}}.$ 当T是Gt中的随机元素时,c0=MmT是Gt中完全随机的元素,此时,密文是随机消息的半功能密文,B成功模拟游 戏ΓCM.若算法A以不可忽略的优势猜测 $T = e(g_1^\rho ,g_1^s)$还是T为随机的Gt元素,则B以算法A的输出解决安全假设3的判定. □ 5 泄漏容忍性能与应用实例 5.1 应用实例 在生物特征数据(如指纹、眼膜、声音等)作为用户身份时,可为产生具有高熵的秘密信息提供一个广泛的来源,但由于其存在一定的不可精确再生性[26],因此采用通配身份模板可有效解决.例如,对于一个指纹信息,我们重点关注关键点的数据,其他部分可以以通配符代替.只要包括关键点的信息的模板匹配,我们可以认为两个指纹数据是匹配的.在多次验证用户生物特征数据时,只需测试是否与生物特征模板匹配即可. 实际应用中,在不同安全需求中有不同的模板处理.例如,在出入境管理中,指纹模板需要双手的指纹数据;而应用于一般的公务处理时,如门禁认证和计算机登录认证等,只需要一只手的指纹数据.为了实现密钥的可重用性和管理的方便性,我们可以生成双手(左手L和右手R)的指纹模板,并以关键点数据作为模板中非通配项,而其他点数据作为通配项.一个数据M加密时,指定需要双手的指纹密钥才能解密时,CTP¢中加密模板P¢=L