一種抗商業(yè)秘密的雙態(tài)仿射加密方案

一種抗商業(yè)秘密的雙態(tài)仿射加密方案

1抗密鑰泄露模型的建立現(xiàn)代密碼學(xué)假設(shè)用戶密鑰對(duì)可能攻擊是完全隱藏的，但事實(shí)上，它可以通過(guò)邊緣信道攻擊，如時(shí)間攻擊、電源消耗、冷啟動(dòng)攻擊和光譜分析等。攻擊和加密系統(tǒng)。根據(jù)aiv等人提出的密鑰泄漏概念。即使攻擊者從密鑰中獲取信息，加密方案也是意義安全的。因此，加密方案被定義為一種抗密反射攻擊。為了模擬泄露，攻擊者必須訪問(wèn)泄露諺語(yǔ)機(jī)，并獲取不同于預(yù)期邊界值的密鑰函數(shù)的輸出，即f：f（sk）{0.1}。除了原有的意義安全功能外，攻擊者還可以自適應(yīng)泄漏語(yǔ)句機(jī)。唯一限制是攻擊者獲得的泄露輸出的長(zhǎng)度，不能超過(guò)預(yù)定義的邊界值。該模型也被稱為布局泄漏模型（blm）。al燕等人首次提出了基于邊界搜索模型的加密方案，以防止主要密鑰的泄漏。此外，還有一個(gè)基于事務(wù)閾值的災(zāi)難模型。這是一個(gè)沒(méi)有解決的問(wèn)題。該模型只支持每個(gè)身份的單一密鑰披露。布什提出了一個(gè)基于邊界搜索模型的加密方案，但不支持主要密鑰的披露。此外，還有一個(gè)基于可靠系統(tǒng)的加密方案（sde）可以同時(shí)支持主要密鑰的披露。lewko等人提出了一個(gè)加密方案，以支持身份泄露，但不支持主要密鑰的披露。lewko等人提出了一個(gè)加密方案，建議使用二進(jìn)制加密（sde）技術(shù)，同時(shí)支持主要密鑰的披露?？臻g加密(SpatialEncryption,SE)采用仿射空間作為解密角色,而仿射空間中的點(diǎn)向量作為加密策略.根據(jù)仿射空間的包含性可實(shí)現(xiàn)密鑰的再次委托能力.在標(biāo)準(zhǔn)的SE方案的基礎(chǔ)上,Vie和Abdalla采用DSE技術(shù)設(shè)計(jì)抗密鑰泄露的空間加密方案,該方案中可泄露界與空間的維度相關(guān)聯(lián).在SE方案中,由于加密策略定義為κ維的點(diǎn)向量,因此無(wú)法實(shí)現(xiàn)策略的再次委托能力.雙態(tài)仿射函數(shù)加密是一般空間加密的一般性擴(kuò)展.在雙態(tài)仿射函數(shù)加密方案中,加密策略和解密角色都定義為仿射子空間.角色委托實(shí)現(xiàn)解密能力的再次委托,可以實(shí)現(xiàn)類(lèi)似基于代理的密碼系統(tǒng),而加密策略定義于可委托的仿射空間,擴(kuò)展的加密策略委托能力可以支持重加密的能力.因此,雙態(tài)仿射空間加密具有廣泛的模型,它擴(kuò)展了PKE、HIBE、ABE、HVE、FE等方案.本文設(shè)計(jì)了一個(gè)抗密鑰泄露安全的雙態(tài)仿射函數(shù)加密方案,在雙系統(tǒng)加密模型下,實(shí)現(xiàn)自適應(yīng)安全抗用戶密鑰多次泄露和主密鑰泄露.本方案中,加密策略和解密角色都定義為代數(shù)仿射向量子空間,并且可以有再次委托的能力.當(dāng)解密角色空間與加密策略空間存在一不動(dòng)點(diǎn)(交集不為空)時(shí),可實(shí)現(xiàn)函數(shù)的匹配并解密.本方案中通過(guò)引入抗泄露組件,提高密鑰的抗泄露能力.同時(shí)通過(guò)密鑰生成和委托算法的特殊功能,實(shí)現(xiàn)主密鑰和用戶密鑰的更新功能,從而提高系統(tǒng)的抗連續(xù)泄露性.本文方案是抗泄露的IBE、HIBE、SE和FE的一般性擴(kuò)展:特別地,當(dāng)加密策略和解密角色縮小為仿射空間中兩個(gè)點(diǎn)向量時(shí),本方案簡(jiǎn)化為抗泄露IBE方案;當(dāng)仿射空間定義為樹(shù)形結(jié)構(gòu)空間而解密角色定義為一個(gè)點(diǎn)向量時(shí),本方案為抗泄露HIBE方案;當(dāng)解密角色變成一個(gè)點(diǎn)時(shí),本方案為抗泄露SE方案.1.1抗泄漏能力的實(shí)現(xiàn)方案采用多維雙系統(tǒng)加密技術(shù)實(shí)現(xiàn),可以容忍主密鑰的泄露和用戶密鑰的連續(xù)泄露,同時(shí)達(dá)到自適應(yīng)安全.為實(shí)現(xiàn)抗主密鑰泄露和連續(xù)用戶密鑰泄露,把一維半功能空間擴(kuò)展為n維.在雙系統(tǒng)加密DSE技術(shù)中,密文和密鑰都可以定義兩種形態(tài):正常(Normal)和半功能(Semi-Functional,SF).正常形態(tài)密鑰可以解密任何一種形式的密文,但SF的密鑰只能解密正常形態(tài)密文,不能解密SF密文.目前實(shí)現(xiàn)DSE的方法主要有3種:基于標(biāo)簽tag的構(gòu)建、基于正交雙線性子群的構(gòu)建和基于雙對(duì)向量空間(DualPairingVectorSpaces,DPVS).本文采用正交雙線性群來(lái)設(shè)計(jì)抗泄露能力.構(gòu)建方案的密文和密鑰都定義為正常形式,在證明過(guò)程中采用混合證明方法,首先密文改變成SF形態(tài)的,密鑰由正常形式逐步改變成SF形態(tài),我們要證明敵手不能感知到這些改變,主要基于合數(shù)階群的子群判定假設(shè).最后模擬器生成SF形式的密鑰和密文,并作為挑戰(zhàn)密文提供給敵手,若敵手能正確解密密文,則可利用它來(lái)解決SF密鑰對(duì)SF密文的判定性問(wèn)題.設(shè)計(jì)的困難問(wèn)題是,在密鑰由正常形態(tài)改變成SF形態(tài)的過(guò)程中,模擬器要為任何仿射向量空間準(zhǔn)備密鑰并生成相應(yīng)的SF密文.本文采用有支配能力的SF功能密鑰來(lái)實(shí)現(xiàn):從敵手來(lái)看,這些密鑰與一般SF密鑰是同分布的,但從模擬器來(lái)看,若解密一SF密文,用支配密鑰可以解密成功,因此在敵手詢問(wèn)過(guò)程中不會(huì)暴露密鑰是正常還是SF形態(tài)的信息.本文擴(kuò)展SF空間到n維(n≥2).由于一個(gè)密鑰的泄露量是有界的,當(dāng)敵手所獲得的泄露量不超過(guò)這個(gè)量時(shí)不能區(qū)分正交向量與隨機(jī)向量.n越大,抗泄露的容忍性越好.1.2方案證明和驗(yàn)證本文第2節(jié)介紹所用的一些基礎(chǔ)知識(shí);第3節(jié)給出抗泄露的雙態(tài)仿射函數(shù)加密框架和安全性模型;第4節(jié)給出詳細(xì)的構(gòu)造方案;方案的正確性、一致性和安全性的分析和證明在第5節(jié)給出;第6節(jié)討論本方案的泄露界;第7節(jié)對(duì)本文作出小結(jié).2預(yù)備知識(shí)2.1設(shè)u=(u1,…,un),v=(v1,…,vn)∈ZnN是一組向量,〈u,v〉是向量的內(nèi)積.設(shè)g是群G的生成元,記gv為向量gv??=(gv1,…,gvn)∈Gn.類(lèi)似,grv??=(grv1,…,grvn),g〈u,v〉??=gu■WΡΜathAyApv=g∑iui?vi.設(shè)(Ν,G,Gt,?e)為雙線性群描述,滿足對(duì)任意a,b∈ZN,存在有效可計(jì)算的雙線性映射?e:?e(ga,gb)=?e(g,g)ab.?en(gu,gv)??=n∏i=1?en(gui,gvi)=?e(g,g)?u,v?.設(shè)?g[n+d]是長(zhǎng)度為n+d的一組Gr元素的隨機(jī)向量,(gu1?g1,gu2?g2,?,gun?gn,gv1?gn+1,?,gvd?gn+d)簡(jiǎn)記為(gu,gv)*?g[n+d].記r←S為從集合S中隨機(jī)選取一元素r.negl(λ)是對(duì)λ可忽略的函數(shù),即對(duì)任意z>0,一函數(shù)f(λ):N→R滿足f(λ)≤λ-z.定義1.計(jì)算不可區(qū)分性.對(duì)任一PPT算法A,兩個(gè)概率總體{X1},{Y2}滿足|Pr[A(1λ,X1)=1]-Pr[A(1λ,X2)=1]|≤negl(λ),則稱X1和X2對(duì)算法是計(jì)算不可區(qū)分的.引理1.設(shè)q是一素?cái)?shù),m,l,d∈ZN滿足m≥l≥2d,X1,X2分別是Zq上選取的m×l和m×d的隨機(jī)矩陣.T←Rankd(Zl×dq)是秩是d的矩陣集.f:Zm×dq→Ω是矩陣Zm×dq上的任意函數(shù),滿足Dist((X1,f(X1T)),(X1,f(X2)))≤negl(·),|Ω|≤4ql-2d(q-1)·negl(·)2(1)這里Dist(X1,X2)表示兩個(gè)隨機(jī)變量X1和X2的統(tǒng)計(jì)距離.推論1.設(shè)m是大于2的整數(shù),q是一大素?cái)?shù).設(shè)δ,τ←Zmq,τ′←V⊥q(δ)(V⊥(τ)是由基τ生成向量空間的正交空間),對(duì)任一函數(shù)f:Zmq→Ω,Dist((δ,f(τ′)),(δ,f(τ)))≤negl(·),|Ω|≤4qm-3(q-1)·negl(·)2(2)應(yīng)用引理1,置d=1,l=m-1,則X1對(duì)應(yīng)于向量的正交空間V⊥(ˉδ)的基,X2對(duì)應(yīng)于ˉτ.本文采用正交子群Gq作為這里的正交空間.我們?cè)诤竺娣治龊陀懻摫疚姆桨傅男孤督鏻MSK=lSK=2+(n-1-2c)log(q),此時(shí)negl(·)=q-c是可以忽略的.定義2.仿射空間.設(shè)d∈ZN,x∈ZκΝ,M∈Zd×κΝ,我們定義一仿射空間S=Aff(M,x)?ZκΝ為S=Aff(M,x)??={x+Mue84cWPMathAyApz|z∈ZdΝ},稱d(d≤κ)為仿射空間S的維度,記為d2Dim(S)=d.T∈Zd1×d2N引理2.若兩仿射空間S1=Aff(M1,x1)維ˉδ度為d1,S2=Aff(M2,x2)維度為d2,滿足S2?S1,則存在一有效可求解的矩陣和向量z∈Zd1N,滿足x2=x1+Mue84cWPMathAyAp1z.引理3.若兩仿射空間S1=Aff(M1,x1)維度為d1,S2=Aff(M2,x2)維度為d2,滿足S1∩S2≠?,則存在一有效可求解的矩陣T1,T2和向量z1,z2,滿足M1T1=M2T2,x1-x2=Mue84cWPMathAyAp2z2-Mue84cWPMathAyAp1z1.證明.設(shè)S1∩S2=S′,S′?S1,S′?S2,根據(jù)引理2,M′=M1T1,x′=x1+Mue84cWPMathAyAp1z1,M′=M2T2,x′=x2+Mue84cWPMathAyAp2z2,得證.證畢.2.2合數(shù)階雙線性群的特性一個(gè)合數(shù)階的雙線性群描述包括(Ν,G,Gt,?e),階N是多個(gè)不等的素?cái)?shù)之積.設(shè)N=pqr,這里p、q、r是不相等的素?cái)?shù).除滿足雙線性群的一般性質(zhì)外,群G包含階分別是p、q和r的子群Gp、Gq和Gr,設(shè)其子群生成元分別是g、ˉg和?g,則G中的任一元素都可以表示成ga1ˉga2?ga3的形式,這里a1,a2,a3∈ZN.合數(shù)階雙線性群具有如下特殊性質(zhì).性質(zhì)1(子群生成元).設(shè)h是G的生成元,則hqr是Gp的生成元,hpr是Gq的生成元,hpq是GrM2=M1T的生成元.性質(zhì)2(子群正交性).設(shè)hp∈Gp,hq∈Gq,hr∈Gr,對(duì)所有a1,a2,a3∈ΖΝ,?e(ha1p,ha2q)=1,?e(ha1p,ha3r)=1,?e(ha2q,ha3r)=1.2.3階大法求解困難問(wèn)題為證明所設(shè)計(jì)方案的安全性,本文使用如下基于合數(shù)階群的(子)群判定問(wèn)題,該假設(shè)在文獻(xiàn)中已作分析.假設(shè)1.設(shè)(Ν,G=Gp×Gq×Gr,Gt,?e)是階N=pqr的雙線性群,σ,τ←ΖΝ,g∈Gp,ˉg∈Gq,?g∈Gr.給定元組Θ=(Ν,G,Gt,?e;g,?g,Τ1=gσ∈Gp,Τ2=gσˉgτ∈Gpq),區(qū)分T1和T2是個(gè)困難問(wèn)題.假設(shè)2.設(shè)(Ν,G,Gt,?e)是階N=pqr的雙線性群,σ,V,τ←ΖΝ,g∈Gp,ˉg∈Gq,?g∈Gr.給定元組Θ=(Ν,G,Gt,?e;g,?g,X1∈Gpq,X2∈Gqr,Τ1=gσ?gV∈Gpr,Τ2=gσˉgτ?gV∈G),區(qū)分T1和T2是個(gè)困難問(wèn)題.假設(shè)3.設(shè)(Ν,G,Gt,?e)是階N=pqr的雙線性群,α,s,t,t′←ΖΝ,g∈Gp,ˉg∈Gq,?g∈Gr.給定元組Θ=(Ν,G,Gt,?e;g,ˉg,?g,X1∈gαˉgt,X2∈gsˉgt′,Τ1=?e(gα,gs),Τ2←Gt),區(qū)分T1和T2是個(gè)困難問(wèn)題.3模型模型3.1密鑰生成算法一個(gè)雙態(tài)仿射函數(shù)加密(DASE)由5個(gè)PPT算法組成:∏=(Init,KeyGen,Dele,Encr,Decr).Init和KeyGen算法由可信第三方PKG執(zhí)行,Init算法生成系統(tǒng)公鑰和主密鑰,KeyGen算法為用戶持有的仿射空間生成密鑰,同時(shí)也可以更新主密鑰;Dele算法由一仿射空間鑰的持有者為其子空間生成委托密鑰,同時(shí)也可以更新自己的密鑰;Encr和Decr分別由加密者和解密者執(zhí)行消息的加密和解密操作.為標(biāo)記用戶密鑰和主密鑰的泄露和更新,我們定義兩個(gè)特殊的空間:空仿射空間?和超仿射空間Λ.(1)Init(1λ,lMSK,lSK,κ,n).輸入系統(tǒng)安全參數(shù)1λ、主密鑰泄露界lMSK、用戶密鑰泄露界lSK、抗泄露容忍度n和仿射空間的維度κ,初始化算法生成系統(tǒng)公鑰和主密鑰.(2)KeyGen(MPK,MSK,S).密鑰生成算法輸入系統(tǒng)公鑰和主密鑰,以及一仿射空間S,若S=Λ則更新主密鑰,否則輸出S的密鑰SKS.(3)Dele(MPK,S1,SK1,S2).密鑰委托算法輸入系統(tǒng)公鑰、仿射空間S1及其密鑰SKS1,以及S1的仿射子空間S2,若S2=?則更新S1的密鑰,否則輸出S2的密鑰SKS2.(4)Encr(MPK,S′,m).加密算法輸入系統(tǒng)公鑰、接收者仿射空間S′以及消息m,輸出加密的密文CTS′.(5)Decr(MPK,S,SKS,S′,CTS′).解密算法輸入系統(tǒng)公鑰、加密策略空間S′及密文CTS′、解密角色空間S及密鑰SKS,輸出消息m.正確性與一致性.Q、M和C分別是仿射向量空間、明文空間和密文空間.對(duì)所有正確生成的(MPK,MSK)、S仿射空間密鑰SKS、S′接收者角色的消息m密文CTS′∈C.f(·)和f′(·)是任意的用戶密鑰和主密鑰的泄露函數(shù),滿足∑ifi(SKS)≤lSK,∑ifi(MSK)≤lMSK.若S∩S′≠?,使用SKS解密CTS′得到m′=m.即Ρr[(ΜΡΚ,ΜSΚ)←Ιnit(1λ,?ΜSΚ,?SΚ,κ,n)S1,S2,S′∈Q,S2∩S′≠?,m∈Μ∑ifi(SΚS2)≤?SΚ,∑ifi(ΜSΚ)≤?ΜSΚCΤS′←Encr(ΜΡΚ,S′,m)m′←Decr(ΜΡΚ,S2,Dele(ΜΡΚ,S1,ΚeyGen(ΜΡΚ,ΜSΚ,S1),S2),S′,CΤS′)m′=m]≤negl(λ).3.2抗泄漏方案lmsk,lsk抗泄露安全的雙態(tài)仿射加密的安全模型定義為如下的游戲框架ExpLR∏,A(λ).1.系統(tǒng)參數(shù).挑戰(zhàn)者C運(yùn)行Init算法生成系統(tǒng)參數(shù)MPK和主密鑰MSK,并把MPK發(fā)送給敵手A.2.詢問(wèn)1.本階段A自適應(yīng)地向挑戰(zhàn)者進(jìn)行下列詢問(wèn):(1)創(chuàng)建密鑰詢問(wèn)(OCrea).敵手提供一系列子空間Sj,挑戰(zhàn)者生成并存儲(chǔ)Sj的密鑰SKSj.(2)泄露詢問(wèn)(OLeak).敵手提供一仿射空間Sj及概率多項(xiàng)式函數(shù)fi:SK→{0,1}*,挑戰(zhàn)者用fi(SKSj)作回答(泄露總長(zhǎng)度∑ifi(SKSj)不能超過(guò)lSK).詢問(wèn)中,敵手也可以直接請(qǐng)求一個(gè)主密鑰泄露的多項(xiàng)式時(shí)間函數(shù)fi(MSK)詢問(wèn).(3)密鑰詢問(wèn)(ORevl).敵手提供子空間Sj,挑戰(zhàn)者以完整的密鑰SKSj作為回答.(4)委托鑰詢問(wèn)(ODele).敵手提供兩空間S1,S2,挑戰(zhàn)者首先查詢OCrea的隊(duì)列是否有SKS1,如果不存在則調(diào)用OCrea為SKS1生成密鑰,然后調(diào)用Dele算法生成并回答委托鑰SKS2,同時(shí)把SKS2存儲(chǔ)于OCrea密鑰隊(duì)列中.(5)解密詢問(wèn)(ODecr).輸入一密文CT和一仿射空間S,挑戰(zhàn)者生成仿射空間密鑰SKS,輸出消息m.3.挑戰(zhàn).敵手隨機(jī)選擇兩消息m0,m1∈M以及挑戰(zhàn)子空間S*,要求S*不在密鑰詢問(wèn)ORevl的隊(duì)列中,也不是已詢問(wèn)過(guò)的空間的仿射子空間,且在泄露詢問(wèn)OLeak獲得的比特量小于lSK.接下來(lái)挑戰(zhàn)者隨機(jī)選擇β∈{0,1},計(jì)算CTS*←Encr(MPK,S*,mβ),將密文CTS*發(fā)送給敵手A.4.詢問(wèn)2.類(lèi)似詢問(wèn)1,但要滿足:不能對(duì)主密鑰MSK或挑戰(zhàn)S*的密鑰作OCrea和OLeak詢問(wèn)5.輸出.敵手輸出β′,若β′=β,敵手贏得該游戲.對(duì)雙態(tài)仿射加密方案DASE的安全游戲中,OCrea、OLeak、ORevl、ODele和ODecr分別是創(chuàng)建密鑰諭言機(jī)、泄露諭言機(jī)、密鑰詢問(wèn)諭言機(jī)、委托諭言機(jī)和解密諭言機(jī),泄露函數(shù)f:SK→{0,1}*,敵手在ExpLR∏,A(λ)中的優(yōu)勢(shì)定義為AdvLR∏,A(λ)??=2|Pr[β′=β]-1|(3)定義3.抗泄露語(yǔ)義安全性.對(duì)任一個(gè)多項(xiàng)式時(shí)間內(nèi)的敵手A在ExpLR∏,A(λ)游戲中,同一仿射空間多次用戶密鑰泄露最多獲得lSKbit的密鑰信息(∑lj≤lSK),最多獲得lMSK的主密鑰信息,敵手所獲得的優(yōu)勢(shì)AdvLR∏,A(λ)是可忽略的,稱該抗泄露雙態(tài)仿射函數(shù)加密是(lMSK,lSK)-LR-CCA安全的.若在ExpLR∏,A(λ)游戲中敵手不能詢問(wèn)解密諭言機(jī)ODecr,則稱該方案是(lMSK,lSK)-LR-CPA安全的.本文重點(diǎn)考慮方案的密鑰抗泄露性,對(duì)消息的保密性方面所設(shè)計(jì)的方案達(dá)到CPA安全.可以利用轉(zhuǎn)換工具使CPA安全的方案達(dá)到CCA安全.一般的抗泄露安全只針對(duì)用戶密鑰泄露,本方案在此基礎(chǔ)上實(shí)現(xiàn)抗主密鑰泄露和連續(xù)泄露.定義4.抗主密鑰泄露.當(dāng)系統(tǒng)主密鑰在泄露量不超過(guò)lMSK時(shí),系統(tǒng)仍是安全的,稱該方案抗主密鑰泄露安全的.lMSK稱為主密鑰泄露界.定義5.抗連續(xù)泄露.若一個(gè)密碼方案具有自身密鑰更新的能力,產(chǎn)生一個(gè)相同分布的重新隨機(jī)化的密鑰,稱該方案是抗連續(xù)泄露的.實(shí)際中,攻擊者可以對(duì)同一用戶的密鑰進(jìn)行多次的密鑰泄露詢問(wèn),因此通過(guò)多次的泄露詢問(wèn)獲得超出泄露界的密鑰信息量.但若密鑰可以被更新,則攻擊者以前的泄露詢問(wèn)不起作用,需要重新開(kāi)始對(duì)新的密鑰進(jìn)行泄露詢問(wèn).特別地,每當(dāng)密鑰被使用(或一定周期)就進(jìn)行一次密鑰更新,這樣攻擊者無(wú)法多次獲得同一仿射空間的相同密鑰上的泄露信息,此加密方案是完全抗連續(xù)泄露的.4新密鑰的生成本方案中,一個(gè)仿射空間S??=Aff(M,x)的密鑰形式為SΚS=(ku,ka,kr,kw)=(gu,gα+r(a+?x,w?)-?u,v?,gr,grΜ■WΡΜathAyApw)*?g[n+d+2],其中ku∈Gn,ka,kr∈G,kw∈Gd,?g[n+d+2]∈Gn+d+2r.這里d=Dim(S)是仿射空間的維度,κ是最大仿射空間的維度.系統(tǒng)中n是大于等于2的整數(shù),它控制密鑰泄露的容忍度.n越大,系統(tǒng)的抗泄露容忍性越好,n越小,系統(tǒng)的密文和密鑰越短.系統(tǒng)初始化參數(shù)中,預(yù)先設(shè)置主密鑰的泄露界lMSK和用戶密鑰的泄露界lSK,并且要求用戶在自定義泄露函數(shù)f(·)的獲得密鑰的總輸出長(zhǎng)度不能超過(guò)這個(gè)界.(1)Init(1λ,lMSK,lSK,κ,n).PKG首先調(diào)用雙線性群生成器生成(Ν=pqr,G=Gp×Gq×Gr,Gt,?e),然后隨機(jī)選取α∈ΖΝ,u,v∈ΖnΝ,w∈ΖκΝ,g,ga∈Gp,ˉg∈Gq,?g∈Gr.設(shè)置并公開(kāi)系統(tǒng)公鑰MPK=(N,G,Gt,e;?ΜSΚ,?SΚ,g,?g,ga,gv,gw,e(g,g)α),同時(shí)保存主密鑰ΜSΚ=(ˉku,ˉka,ˉkr,ˉkw)=(gu,gα+ra-?u,v?,gr,grw)*?g[n+κ+2].這里?g[n+κ+2]是Gr上的一組隨機(jī)n+κ+2維向量,可以先隨機(jī)選擇η∈ZnΝ×ZN×ZN×ZκΝ,然后計(jì)算?gη得到.(2)KeyGen(MPK,MSK,S).第1步,PKG為仿射空間S??=Aff(M,x)生成導(dǎo)入密鑰//SΚS:設(shè)d=Dim(S),//SΚS=(?ku,?ka,?kr,?kw)=(ˉku,ˉka·d∏i=1(ˉkwi)xi,ˉkr,ψ(gΜ■WΡΜathAyAp,ˉkw))=(gu,gα+r(a+?x,w?)-?u,v?,gr,grΜ■WΡΜathAyApw)*?g[n+d+2](4)這里,設(shè)仿射矩陣M=(X1,…,Xd)ue84cWPMathAyAp∈Zd×κΝ,定義ψ(gΜ■WΡΜathAyAp,ˉkw)??=(g〈X1,rw〉,…,g〈Xd,rw〉).第2步,對(duì)//SΚS進(jìn)行隨機(jī)化處理:隨機(jī)選擇r′∈ΖΝ,u′∈ΖnΝ,?gη∈Gn+d+2r,計(jì)算SΚS=//SΚS*?gu′,gr′(a+?x,w?)?g?-u′,v?,gr′,gr′Μ■WΡΜathAyApw?*?gη=?gu+u′,gα+(r+r′)(a+?x,w?)-?u+u′,v?,gr+r′,g(r+r′)Μ■WΡΜathAyApw?*?gη+[n+d+2](5)由于r,r′,u,u′是ZN上隨機(jī)選取的,因此隨機(jī)化前后的密鑰是同分布的.值得注意的是,當(dāng)為一個(gè)特殊的κ維的仿射空間Λ:SΛ=Aff(E,0)生成密鑰時(shí)(E是單位陣,0是零向量),本質(zhì)上是在更新主密鑰MSK.此時(shí),〈0,w〉=0,grEue84cWPMathAyApw=grw,即經(jīng)過(guò)密鑰導(dǎo)入和隨機(jī)化之后,密鑰結(jié)構(gòu)沒(méi)有變化,只是用新隨機(jī)數(shù)代替原來(lái)的r和u.(3)Dele(MPK,S1,SK1,S2).S2=Aff(M2,x2)是S1=Aff(M1,x1)的仿射子空間,即S2?S1,設(shè)d1=Dim(S1),d2=Dim(S2),根據(jù)引理2,存在一有效的計(jì)算求出T和z滿足M2=M1T,x2=x1+Mue84cWPMathAyAp1z.①若S2=S1,則系統(tǒng)更新委托者自身密鑰SKS1:采用KeyGen中的更新算法(5),可以獲得與原有密鑰同分布的新密鑰.②若S2?S1,S1為S2生成委托密鑰(設(shè)S1的密鑰是SKS1=(ku,ka,kr,kw)):首先生成導(dǎo)入密鑰-//SΚS2=(?ku,?ka,?kr,?kw)-=(ku,kagrΜ■WΡΜathAyAp1zw,kr,ψ(gΜ■WΡΜathAyAp1,ˉkw))=(gu,gα+r(a+?x2,w?)-?u,v?,gr,grΜ■WΡΜathAyAp2w?*?g[n+d2+2].第2步,對(duì)//SΚS2再隨機(jī)化,獲得與//SΚS2同分布的密鑰SKS2:隨機(jī)選擇r′∈ΖΝ,u′∈ΖnΝ,?gη∈Gn+d2+2r,計(jì)算SΚS2=//SΚS2*?gu′,gr′(a+?x2,w?)?g?-u′,v?,gr′,gr′Μ■WΡΜathAyAp2w?*?gη=?gu+u′,gα+(r+r′)(a+?x2,w?)-?u+u′,v?,gr+r′,g(r+r′)Μ■WΡΜathAyAp2w?*?gη+[n+d2+2](6)(4)Encr(MPK,S′,m)給定一消息m∈Gt和一接收者仿射空間角色S′=Aff(M′,x′),本算法隨機(jī)選取s∈ZN,生成密文CTS′.CΤS′=(cm,cv,cs,ca,cw)=(m?e^(g,g)sα,gsv,gs,g-s(a+?x′,w?),gsΜ′■WΡΜathAyApw)(7)特別地,當(dāng)接收角色空間S′縮小為仿射空間的一個(gè)點(diǎn)向量x′時(shí),M′=?,cw=1G.此時(shí)加密方案簡(jiǎn)化為一般的空間加密方案.(5)Decr(MPK,S,SKS,S′,CTS′).若解密者的角色空間S=Aff(M,x)與加密策略空間S′=Aff(M′,x′)的交不為空(S∩S′≠?),則存在一仿射空間點(diǎn)向量x*∈S∩S′.根據(jù)線性代數(shù)性質(zhì)及引理3,可以有效地找出向量z,z′滿足:x*=x+Mue84cWPMathAyApz=x′+(M′)ue84cWPMathAyApz′.解析SKS=(ku,ka,kr,kw),CTS′=(cm,cv,cs,ca,cw),計(jì)算kδ=ka·∏i=1d(kwi)zi,-cδ=ca·∏i=1d(cwi)zi(8)這里d=Dim(S∩S′).輸出消息m.m=cme^(ku,cv)e^(kδ,cr)e^(ks,cδ)(9)5均質(zhì)和安全性5.1準(zhǔn)確性5.1.1盲化因子提取密文CTS′中,cm∈Gt,cv,ca,cs,cw∈Gp,而密鑰SKS∈Gpr,根據(jù)子群的正交性、密鑰與密文的雙線性運(yùn)算(cm除外),密鑰的Gr子群元素g^[n+d+2]將被約除.因此解密一致性只需考慮子群Gp中元素的計(jì)算.根據(jù)引理3,x*=x+Mue84cWPMathAyApz=x′+(M′)ue84cWPMathAyApz′.kδ=ka·∏i=1d(kwi)zi=gα+r(a+〈x,w〉)-〈u,v〉grMue84cWPMathAyApzw=gα+r(a+〈x,w〉)-〈u,v〉gr〈x*-x〉w=gα+r(a+〈x*,w〉)-〈u,v〉,同理,cδ=g-s(a+?x*,w?),e^(ku,cv)=e^(gu,gsv)=e^(g,g)s?u,v?(10)e^(kδ,cr)=e^(gα+r(a+?x*,w?)-?u,v?,gs)-=e^(g,g)sαe^(g,g)rs(a+?x*,w?)e^(g,g)-s?u,v?(11)e^(ks,cδ)=e^(gr,g-s(a+?x*,w?))=e^(g,g)-rs(a+?x*,w?)(12)e^(ku,cv)e^(kδ,cr)e^(ks,cδ)=e^(g,g)sα(13)使用上述盲化因子e^(g,g)sα可以從cm中正確提取消息m.5.1.2共享參數(shù)u和r在KeyGen中,PKG利用主密鑰MSK對(duì)任一仿射空間S=Aff(M,x)生成密鑰SKS=(ku,ka,kr,kw)∈Gprn+d+2.這里ku,kr用于隱藏隨機(jī)數(shù)u和r,我們主要驗(yàn)證ka和kw的正確性.k^a=kˉa·∏i=1d(kˉwi)xi=gα+ra-?u,v??gr?x,w?*g^′=gα+r(a+?x,w?)-?u,v?*g^′∈Gpr(14)k^w=ψ(gΜ■WΡΜathAyAp,kˉw)=(g?X1,rw?,?,g?Xd,rw?)*g^[d]=grΜ■WΡΜathAyApw*g^[d]∈Gprd(15)在隨機(jī)化過(guò)程中,密鑰的結(jié)構(gòu)和長(zhǎng)度沒(méi)有發(fā)生變化,只是用新的隨機(jī)數(shù)u+u′和r+r′代替原密鑰中的u和r,因此不影響密鑰的一致性.5.1.3委托密鑰生成s1的方法S2是S1的仿射子空間,根據(jù)引理2,存在一有效可求解的矩陣M和向量z,滿足x2=x1+Mue84cWPMathAyApz,故Mue84cWPMathAyApz=-x1+x2.對(duì)生成的S2的委托密鑰中,k^w的求解過(guò)程與式(6)相同.a=rMue84cWPMathAyAp1zw=gα+r(a+〈x1,w〉)-〈u,v〉gr〈-x1+x2,w〉=gα+r(a+〈x2,w〉)-〈u,v〉(16)5.2密鑰更新5.2.1不同性質(zhì)的主密鑰更新PKG可以通過(guò)對(duì)特殊仿射空間SΛ=(E,0)的密鑰提取來(lái)更新主密鑰MSK:Dim(SΛ)=κ,E是單位陣,0是零向量.主密鑰更新是對(duì)密鑰中的隨機(jī)數(shù)進(jìn)行再隨機(jī)化處理,由于主密鑰中每個(gè)組件都與隨機(jī)數(shù)關(guān)聯(lián),因此進(jìn)行主密鑰更新可以容忍系統(tǒng)的泄露,我們很容易得到下面的定理.定理1.在DASE方案中,主密鑰更新不影響系統(tǒng)以前和以后產(chǎn)生的密鑰,但可以提高系統(tǒng)的抗主密鑰泄露安全性.通過(guò)周期性更新主密鑰,可以抗主密鑰的連續(xù)泄露.5.2.2密鑰基于再隨機(jī)數(shù)的開(kāi)發(fā)在Dele算法中,任何密鑰持有者除了可以為仿射子空間生成子密鑰外,還可以更新自身密鑰.在密鑰結(jié)構(gòu)和長(zhǎng)度不變的情況下,通過(guò)再隨機(jī)化隨機(jī)數(shù)的功能實(shí)現(xiàn)密鑰更新.定理2.在DASE方案中,密鑰更新不影響該密鑰生成的子密鑰,但可以提高系統(tǒng)的抗主密鑰泄露安全性.關(guān)于密鑰可泄露的大小與安全強(qiáng)度,我們?cè)诤竺嬗懻?5.3s1與s13本方案具有委托路徑獨(dú)立性:一個(gè)委托的密鑰與路徑無(wú)關(guān).設(shè)有3個(gè)仿射空間S1,S2,S3滿足S3?S2?S1,則為S3生成的兩個(gè)密鑰Dele(MPK,S1,SKS1,S3)與Dele(MPK,S2,Dele(MPK,S1,SKS1,S2),S3)是計(jì)算不可區(qū)分的.5.4半功能化密鑰的生成與一般加密方案的證明不同之處在于,一般的語(yǔ)義安全性只需要回答敵手的密鑰詢問(wèn),而本方案允許敵手進(jìn)行額外的主密鑰MSK和仿射空間角色密鑰SKS的泄露詢問(wèn).特別地,敵手可以對(duì)挑戰(zhàn)的仿射子空間作有界長(zhǎng)度的密鑰泄露詢問(wèn).可泄露的界lMSK,lSK是安全參數(shù)的多項(xiàng)式表達(dá)式,即lMSK=?MSK(λ),lSK=lSK(λ).首先,挑戰(zhàn)者C運(yùn)行Init算法生成系統(tǒng)參數(shù)和主密鑰,并把系統(tǒng)公鑰發(fā)送給敵手A.同時(shí),C提供給敵手一個(gè)記錄主密鑰MSK及關(guān)聯(lián)的用戶密鑰SK及泄露量的句柄H??=(Handle,Space,(MSK∪SK),Leaked-bit)),以利敵手進(jìn)行詢問(wèn)并保持相應(yīng)的狀態(tài).在詢問(wèn)階段,由于OKeyGen,ODele都可以由OCrea生成,在詢問(wèn)階段敵手可以自適應(yīng)地進(jìn)行三種詢問(wèn):OCrea,OLeak和ORevl.在OCrea中,敵手提供一個(gè)主密鑰的句柄給挑戰(zhàn)者,并請(qǐng)求挑戰(zhàn)者生成一個(gè)密鑰,并存儲(chǔ)在相應(yīng)隊(duì)列中.每次詢問(wèn)后,挑戰(zhàn)者要返回一個(gè)與相應(yīng)句柄相應(yīng)的用戶密鑰給A,使得A在后面的OLeak和ORevl詢問(wèn)中能夠?qū)?yīng)它所使用的句柄.在OLeak詢問(wèn)中,A使用句柄可以有選擇性地進(jìn)行泄露詢問(wèn),所有的泄露函數(shù)fi和泄露量由敵手自適應(yīng)地選擇(只要泄露總量不超過(guò)lMSK和lSK).在此詢問(wèn)過(guò)程中,挑戰(zhàn)者記錄敵手每次所泄露過(guò)的密鑰及泄露量.當(dāng)敵手請(qǐng)求一個(gè)OCrea詢問(wèn)時(shí),挑戰(zhàn)者創(chuàng)建一條上述記錄并置初值為0.ORevl詢問(wèn)允許敵手獲得某一仿射空間的S生成的密鑰SKS.為了保持一致性,敵手只需提供一個(gè)S的句柄.顯然,敵手不能獲得主密鑰的詢問(wèn),也不能對(duì)挑戰(zhàn)的仿射空間作密鑰提取詢問(wèn).為此,挑戰(zhàn)者用集合R記錄已詢問(wèn)過(guò)的仿射空間.方案中KeyGen或Dele產(chǎn)生的密鑰和Encr生成的密文都是正常形式的,為了幫助證明,我們?cè)O(shè)計(jì)半功能化的密鑰形式.基本方法是對(duì)原來(lái)密鑰和密文組件乘以Gq中的隨機(jī)元素(Gq在實(shí)際方案中沒(méi)有涉及,僅用于安全性證明中設(shè)計(jì)半功能化密文或密鑰).隨機(jī)選取gˉθ1,gˉγ1∈Gqn+2,gˉθ2,gˉγ2∈Gqd,計(jì)算半功能密鑰:SΚ?S??=((ku,ka,kr)*gˉθ1,kw*gˉθ2)∈Gpqrn+d+2.半功能密文:CΤ?S′??=(cm,(cv,cs,ca)*gˉγ1,cw*gˉγ2)∈Gt×Gpqn+d+2.顯然一個(gè)半功能密鑰要成功解密一個(gè)半功能密文,除了加密策略S′與解密角色S滿足S∩S′≠?,根據(jù)式(8)還要滿足〈θ1,γ1〉+〈Mue84cWPMathAyApzθ2,M′ue84cWPMathAyApz′γ2〉=0modq.為了證明方案的安全性,我們使用一系列不可區(qū)分的游戲,最初游戲Leak中密鑰和密文均是正常形式,而最后的LeakCK中密鑰和密文均是半功能化的,LeakCKM中的消息組件cm是隨機(jī)化的.定義如下:(1)Leak.本游戲中密文和密鑰均為正常形式,即密文和密鑰由DASE中算法生成,敵手執(zhí)行Exp∏,ALR(λ)定義的游戲模型.(2)LeakD.與Leak的區(qū)別在于,對(duì)敵手的Dele和KeyGen詢問(wèn),用OCrea代替.由于這兩個(gè)諭言機(jī)所生成的密鑰是不可區(qū)分的,因此LeakD與Leak是不可區(qū)分的.(3)LeakC.本游戲與LeakD的區(qū)別在于,在挑戰(zhàn)階段,挑戰(zhàn)者用半功能密文CΤ?S′作為挑戰(zhàn)的輸出.(4)LeakCKj.與LeakC相同的是,本游戲中密文仍是半功能化的.同時(shí),本游戲產(chǎn)生半功能化的密鑰存儲(chǔ)于H中,OCrea生成正常的密鑰而OLeak和ORevl生成半功能化的密鑰.與密鑰詢問(wèn)一樣,本游戲也生成半功能的主密鑰.顯然,j=0時(shí),LeakCK0=LeakC;j=qe(qe是詢問(wèn)的最大次數(shù))時(shí),LeakCK中生成的密文和密鑰都是半功能化的.當(dāng)1≤j≤qe時(shí),所生成的密鑰中前j-1個(gè)是半功能化的,后面的都是正常密鑰.我們證明對(duì)所有j,LeakCKj與LeakCKj+1是不可區(qū)分的.同時(shí),我們證明敵手在Leakj+1中不能構(gòu)造可解密挑戰(zhàn)密文的支配型密鑰.(5)LeakCKM.與LeakCK不同的是,本游戲中密文中的cm改變成Gt中的隨機(jī)元素.通過(guò)LeakCK與LeakCKM的不可區(qū)分性,我們可以證明cm對(duì)消息是保密的.定理3.在一個(gè)抗泄露的雙態(tài)仿射函數(shù)加密方案中,若Leak,LeakD,LeakC,LeakCK,LeakCKM之間是計(jì)算性不可區(qū)分的,則該方案是抗泄露安全的.證明.我們采用一系列不可區(qū)分的證明引理4～8來(lái)證明本抗泄露方案的安全性.Leak是本文提出方案的正常密鑰和密文,而LeakCK表明敵手無(wú)法區(qū)分的半功能化密文和密鑰,LeakCKM是對(duì)消息隱藏組件與隨機(jī)元素不可區(qū)分.引理7在引理1的分布不可區(qū)分性的基礎(chǔ)上證明在泄露界中,敵手無(wú)法構(gòu)造一個(gè)支配型的密鑰去解密挑戰(zhàn)密文.因此從敵手來(lái)看,這些游戲不可區(qū)分,而LeakCK和LeakCKM是完全隨機(jī)化的密文組件,敵手無(wú)法從這些組件中獲得密文的有用信息.因此,本方案是(lMSK,lSK)-LR-CPA安全的.引理4.任何多項(xiàng)式時(shí)間內(nèi)的敵手A無(wú)法區(qū)分Leak和LeakD.證明.OCrea執(zhí)行OKeyGen的輸出.通過(guò)KeyGen和Dele的算法可知,兩者的輸出是同一分布的,同時(shí)ODele的委托密鑰也應(yīng)當(dāng)在OCrea生成的密鑰隊(duì)列中,因此OKeyGen和ODele都可以由OCrea生成,敵手無(wú)法區(qū)別一個(gè)密鑰是哪個(gè)諭言機(jī)生成.引理5.若安全假設(shè)1存在,則任何多項(xiàng)式時(shí)間內(nèi)的敵手A無(wú)法區(qū)分LeakC和LeakD.證明.假設(shè)一多項(xiàng)式時(shí)間的敵手A可以以不可忽略的優(yōu)勢(shì)區(qū)分LeakD和LeakC,則我們可以構(gòu)建一算法D作為模擬器以相同的優(yōu)勢(shì)解決安全假設(shè)1.當(dāng)D收到假設(shè)1的實(shí)例(Ν,G,Gt,e^;g,g^),D的目標(biāo)是猜測(cè)一元素T∈Gp還是T∈Gpq.為此,D扮演模擬器并回答敵手A的詢問(wèn)及挑戰(zhàn)如下(1)初始化.D隨機(jī)選擇α,a,u,v,w∈Z2n+κ+2,置系統(tǒng)公鑰ΜΡΚ=(Ν,g,g^,ga,gv,gw)并發(fā)送給A.(2)詢問(wèn)1.由于D知道系統(tǒng)主密鑰α和v,因此可以為任何仿射空間生成密鑰,并且可以回答敵手A的OCrea、OLeak、ORevl、OKeyGen及ODele等詢問(wèn).(3)挑戰(zhàn).當(dāng)A提交給D兩個(gè)挑戰(zhàn)的消息Gm0,m1及挑戰(zhàn)子空間S*=Aff(M*,x*),模擬器D隨機(jī)選擇β∈{0,1},輸出密文CΤS*=(cm,cv,cs,ca,cw)=(mβe^(Τ,gα),Τv,Τ,Τ-(a+?x*,w?),Τ(Μ*)■WΡΜathAyApw).(4)詢問(wèn)2.與詢問(wèn)1相同,同時(shí)要求A不能對(duì)S*及其超空間作ORevl詢問(wèn).(5)輸出.A輸出對(duì)密文中消息mβ的猜測(cè)β′.D以相同的輸出β′作為對(duì)假設(shè)1的猜測(cè):β′=0則T∈Gp,β′=1則T∈Gpq.若T∈Gp,則密文CTS*是正常形態(tài)的(沒(méi)有Gq元素),此時(shí)B可以正確模擬Leak.若Τ=gσgˉτ∈Gpq,則密文是半功能化的,此時(shí)cm=mβe^(Τ,gα)=me^(g,g)α,θ=τ(v,1,-a+?-x*,w?,(Μ*)■WΡΜathAyApw).事實(shí)上,雖然a,u,v,w是從ZN中選取.但在公開(kāi)參數(shù)MPK中時(shí)都是作為g∈Gp的指數(shù),因此這些值模q是不為0的(p,q,r是互素的階).對(duì)敵手來(lái)說(shuō)密文組件中Gq部分不為1Gq.因此可以正確模擬LeakC.引理6.若安全假設(shè)2存在,則任何多項(xiàng)式時(shí)間內(nèi)的敵手A無(wú)法區(qū)分LeakCKj和LeakCKj+1.證明.若一多項(xiàng)式時(shí)間的敵手A以不可忽略的優(yōu)勢(shì)區(qū)分LeakCKj和LeakCKj+1,我們可以構(gòu)建一算法D以相同的優(yōu)勢(shì)解決安全假設(shè)2.D的目標(biāo)是判斷假設(shè)2的實(shí)例(g,g^,X1,X2,Τ)中T為Gpq還是G中的元素.我們證明當(dāng)T∈Gpq時(shí),D能成功模擬LeakCKj,當(dāng)T∈G時(shí),D能成功模擬Leakj+1.(1)初始化.D隨機(jī)選擇α,a,v,w∈Zn+κ+2N,設(shè)置系統(tǒng)公鑰ΜΡΚ=(g,g^,ga,gw,gw,e^(g,g)α).(2)詢問(wèn)1.本階段對(duì)密鑰回答分為3種情況①對(duì)前面的j-1個(gè)密鑰,D設(shè)置成半功能密鑰,即SΚS=(gu,gα+r(a+?x,w?)-?u,v?,gr,grΜ■WΡΜathAyApw)*g^[n+d+2]*X2[n+d+2]∈Gn+d+2.②對(duì)第j個(gè)密鑰,D將生成挑戰(zhàn)項(xiàng)的密鑰,SΚS=(Τu,gαΤa+?x,w?-?u,v?,Τ,ΤΜ■WΡΜathAyApw)*g^[n+d+2].顯然,當(dāng)T∈Gpr時(shí),SKS是正常形態(tài)的.當(dāng)Τ=gσgˉτg^V∈G(注:G=Gpqr)時(shí),半功能密鑰因子θ=τ(u,a+〈x,w〉-〈u,v〉,1,Mue84cWPMathAyApw).θ作為g∈Gp的指數(shù)(計(jì)算時(shí)modp)而p與q互素,因此θ≠0,從敵手來(lái)看SKS是半功能的.③從j+1密鑰開(kāi)始,D輸出正常形式的密鑰,即SΚS=(gu,gα+r(a+?x,w?)-?u,v?,gr,grΜ■WΡΜathAyApw)*g^[n+d+2]∈Gprn+d+2.(3)挑戰(zhàn).D生成一個(gè)半功能化的密文:CΤ?S*=(mβe^(X1,gα),X1v,X1,X1-a-?x*,w?,X1(Μ*)■WΡΜathAyApw).(4)設(shè)X1=gk1gˉk2∈Gpq,挑戰(zhàn)密文中半功能化因子γ=k2(v,1,-a-〈x*,w〉,(M*)ue84cWPMathAyApw).設(shè)SΚ?S=((ku,ka,kr)*gˉθ1,kw*gˉθ2),在半功能化密鑰生成或委托時(shí),根據(jù)式(8),若S使用半功能密鑰SΚ?S去生成一子空間密鑰x2=x1+Mue84cWPMathAyApz,則半功能化參數(shù)θ′=θ1+(0,…,0,〈z,θ2〉).同樣,半功能化密鑰參數(shù)γ′=γ1+(0,…,0,〈z′,γ2〉).〈θ′,γ′〉=τk2(〈u,v〉-a-〈x*,w〉-〈(M*)ue84cWPMathAyApz′,w〉+a+〈x,w〉-〈u,v〉+〈Mue84cWPMathAyApz,w〉)modq=τk2(〈x-x*,w〉+〈(M*)ue84cWPMathAyApz′-Mue84cWPMathAyApz,w〉)modq.若敵手解密CTS′,則〈θ′,γ′〉=0modq.若敵手可以區(qū)分Leakj和Leakj+1,我們可以不可忽略的優(yōu)勢(shì)找出N的因式q,并成功解決安全假設(shè)2.引理7.設(shè)泄露界lSK=(n-1-2c)logq,c是一正整數(shù).對(duì)任一PPT敵手A在Leakj+1中把第j個(gè)密鑰關(guān)聯(lián)到挑戰(zhàn)密文向量空間,把第j個(gè)半功能密鑰替換成支配型密鑰去解密挑戰(zhàn)密文的優(yōu)勢(shì)是可忽略的.證明.假設(shè)一個(gè)PPT敵手A以不可忽略的優(yōu)勢(shì)達(dá)到上述的轉(zhuǎn)換,我們可以構(gòu)造一算法B以相同的優(yōu)勢(shì)區(qū)分(δ,f(τ))和(δ,f(τ′))從而攻擊引理1和推論1的結(jié)論.在本證明中主要考慮密鑰結(jié)構(gòu),我們把主密鑰當(dāng)成超仿射空間的密鑰,這樣所有的泄露都由密鑰泄露諭言機(jī)OLeak生成.B收到推論1的實(shí)例后,置m=n+1,q是N的因子.B的目標(biāo)是借助A證明上述兩個(gè)分布有不可忽略的優(yōu)勢(shì).B模擬Leakj+1如下:首先運(yùn)行Init算法生成主密鑰MSK和系統(tǒng)公鑰MPK,把公鑰MPK發(fā)送給敵手A.由于B知道系統(tǒng)主密鑰,因此可以回答敵手的任何詢問(wèn).假定在第j個(gè)密鑰詢問(wèn)中,敵手以不可忽略的優(yōu)勢(shì)選擇與挑戰(zhàn)空間有不動(dòng)點(diǎn)的空間S*(如不能達(dá)到不可區(qū)分的優(yōu)勢(shì),則敵手無(wú)法構(gòu)造支配密鑰去解密密文,同時(shí)不能區(qū)分兩個(gè)分布).B接下來(lái)回答A的請(qǐng)求生成泄露串.f是一個(gè)PPT時(shí)間的函數(shù),輸入域是Zqn+1,值域大小是2?SK.B收到(δ,f(τ)),這里τ是x或x′,B使用f(τ)回答敵手的第i個(gè)密鑰泄露詢問(wèn)如下:選擇r1,r2,θ∈Zqd+2,置Gq子群部分密鑰gˉυ,這里υ=(υ1,…,υn,r1,υn+1+r2,θ).A詢問(wèn)挑戰(zhàn)空間S*,若第j空間鑰隊(duì)列中不包含S*,B失敗并隨機(jī)輸出τ是δ正交的猜測(cè).否則,若第j個(gè)仿射空間是S=Aff(M,x),則存在一算法求解x*=x+Mz.B隨機(jī)選擇k2∈Zq滿足υn+1+r2,(r1+〈z,θ〉)k2=0modq,然后使用(δ,k2)∈Zqn+2作為參數(shù)構(gòu)造挑戰(zhàn)密文.若δ與υ正交,則第j個(gè)密鑰是支配型半功能的,即(υ1,…,υn,r1,υn+1+r2)+(0,…,0,〈x,θ〉)*δ=〈υ,δ〉+δn+1r2+(r1+〈x,θ〉)k2=0modq.若δ與υ不正交,則挑戰(zhàn)密鑰是真半功能的,即上式恒不為0.B使用A的挑戰(zhàn)輸出以不可忽略的優(yōu)勢(shì)區(qū)分(δ,f(τ))和(δ,f(τ)).這與引理1的推論1矛盾.因此敵手在Leakj+1中把一個(gè)半功能密鑰替換成支配型半功能密鑰的優(yōu)勢(shì)是可忽略的.引理8.若安全假設(shè)3存在,則任何多項(xiàng)式時(shí)間內(nèi)的敵手A無(wú)法區(qū)分LeakCK和LeakCKM.證明.假設(shè)一多項(xiàng)式時(shí)間的敵手A以不可忽略的優(yōu)勢(shì)區(qū)分LeakCK和LeakCKM,我們可以構(gòu)建一算法D以相同的優(yōu)勢(shì)解決安全假設(shè)3.當(dāng)D收到假設(shè)3的實(shí)例,D的目標(biāo)是猜測(cè)Τ=e^(gα,gs)還是Τ(g,gˉ,g^,X1=gαgˉt,X2=gsgˉt′,Τ)只能為Gt中的隨機(jī)猜測(cè).為此,D扮演模擬器并回答敵手A的詢問(wèn)及挑戰(zhàn)如下:(1)初始化.D隨機(jī)選擇a,v,w