基于格的訪問控制加密技術研究

譚高升 李 偉 馬靜靜 王偉忠 邢建華 馬明杰

1(北京京航計算通訊研究所 北京 100074)

2(軍事科學院系統(tǒng)工程研究院 北京 100101)

3(中國工業(yè)互聯(lián)網(wǎng)研究院 北京 100102)

訪問控制加密[1](access control encryption, ACE)是一種功能性公鑰加密,不僅可以控制誰有權限閱讀消息(讀權限),還可控制誰有權限發(fā)送消息(寫權限).控制讀權限是傳統(tǒng)公鑰加密,例如基于身份的加密[2-4]、基于屬性的加密[5-7]等具備的特點,即只有擁有解密私鑰的接收者可以閱讀加密消息.幾乎所有的傳統(tǒng)公鑰加密都未考慮控制消息的寫權限.在一些通信系統(tǒng)中控制寫權限是一種非常重要的需求,尤其在具有多個安全等級的通信系統(tǒng)中.

文獻[1]構造了基于DDH(decisional Diffie-Hellman)假設的訪問控加密方案,但是,文獻[8]指出此方案存在密文泄露攻擊(即無發(fā)送權限的攻擊者可以通過獲取有發(fā)送權限人員生成的密文,從而取得相應的發(fā)送權限).存在這種攻擊的根源在于文獻[1]中的安全模型存在局限性.文獻[8]提出了角色遵守安全性模型(role respecting security model),文獻[1]方案滿足此安全模型即可抵抗密文泄露攻擊.文獻[8]基于Naor-Yung構造策略[9]利用非交互零知識證明[10]和同態(tài)公鑰加密[11]構造了CCA安全的方案.但是,文獻[2]并未修補文獻[1]中的DDH方案,文獻[2]提出的構造方法很難直接應用于DDH方案,由于非交互零知識證明使得方案既復雜又低效,方案的通信策略受到限制.構造高效的滿足任意通信策略的CCA安全的訪問控制加密方案是文獻[2]中的公開問題.

本文主要貢獻如下:首先將文獻[1]中的DDH方案進行了通用化設計,并以非常高效的方式修補了方案易受密文泄露攻擊的不足.其次,提出了一種通用、高效、滿足任意通信策略的CCA安全的訪問控制加密方案,并能夠基于多種標準假設實例化,包括基于格上困難性假設,因此,本文方案還具備后量子安全性(post quantum security).最后,分別基于帶錯學習(learning with error, LWE)[12]與短整數(shù)解[13]假設(short integer solutions, SIS)和DBDH假設[14]給出了CCA安全方案的2種實例化構造.本文主要貢獻如下:

1) 抗密文泄露攻擊的高效CPA安全方案.本文將文獻[1]的DDH方案進行了通用化設計,并基于滿足同態(tài)性質(zhì)的公鑰加密與偽隨機函數(shù)構造了CPA安全的抗密文泄露攻擊的訪問控制加密方案.如果方案同樣基于DDH假設進行實例化,本文方案與初始DDH方案相比同樣高效,均有相同的密文長度,唯一的額外開銷是關于偽隨機函數(shù)的計算開銷.

2) 滿足任意通信策略的通用高效CCA安全的訪問控制加密方案.本文利用基于身份加密(identity based encryption, IBE)、強一次簽名(strong one-time signature, SOTS)和偽隨機函數(shù)構造了通用的CCA安全訪問控制加密方案.受到文獻[15]中的變換(CHK-變換)啟發(fā),本文利用CHK-變換構造的CCA方案效率更高.在本文方案中,密文的基礎形式為c=(vk,c1,c2,σ),其中vk是強一次簽名的認證密鑰,c1和c2是IBE的密文,σ是(c1,c2)作為消息生成的簽名.發(fā)送權限的控制原理是存在1個信道控制器,其對簽名進行驗證,如果簽名有效,則對(vk,c1,c2)進行處置,生成發(fā)送給接收者的密文c′.需要注意,CCA安全性只針對密文c,c′無法滿足CCA安全性.

3) 基于格假設或DBDH假設下方案實例化.本文給出2種通用CCA安全方案的實例化構造:一種基于LWE和SIS假設,滿足后量子安全性;另一種基于DBDH假設,效率更高.方案構造的關鍵在于IBE方案需滿足特殊的性質(zhì),本文稱為身份變換不可區(qū)分性(參見定義1),本文證明文獻[13-14]中的IBE方案均滿足身份變換不可區(qū)分性.

文獻[1]還提出了滿足任意通信策略條件下密文長度可以是多項式對數(shù)(polylogarithmic)復雜度(關于通信系統(tǒng)中用戶數(shù)量)的方案,但是,此方案需要基于不可區(qū)分性混淆(indistinguishability obfuscation, IO).文獻[10]基于標準的雙線性對假設,提出了密文長度同樣為多項式對數(shù)復雜度的方案,但是此方案的通信策略受限,不能滿足任意的通信策略.文獻[16]提出了基于標準化假設的訪問控制加密方案,其方案密文長度滿足多項式對數(shù)復雜度且可以滿足任意通信策略.方案構造過程使用了數(shù)字簽名、謂詞加密(predicate encryption)和單密鑰函數(shù)加密(functional encryption),為了實現(xiàn)寫權限控制,函數(shù)加密需要支持隨機化函數(shù)(randomized functionality)[17-18].文獻[19]提出了基于LWE假設的訪問控制加密方案.以上所有方案只滿足CPA安全性.表1給出了本文方案與相關方案的對比結(jié)果:

表1 本文方案與相關方案的對比結(jié)果

本文方案同時滿足抗密文泄露攻擊、后量子安全性、任意通信策略.雖然密文的長度復雜度為多項式級別,考慮實際系統(tǒng)通信帶寬的提升,本文方案因構造簡單同樣具有實用價值.

1 基礎知識

基于身份的加密:基于身份的加密方案IBE由4個算法構成,記作(KGI,ExtI,EncI,DecI),本文的IBE方案需要滿足身份可變性.記IBE.CONVERT(·,·)為概率性算法,稱為身份變換算法,輸入身份id和以id為公鑰的密文c,輸出1個“新的”身份id′和id′為公鑰的密文c′,記作(id′,c′)←IBE.CONVERT(id,c),且滿足如下要求.

定義1.身份變換不可區(qū)分性.記λ為安全參數(shù),IBE為基于身份的加密方案.記ID為IBE的身份空間.U(ID)表示ID空間上的均勻分布.稱IBE滿足身份變換不可區(qū)分性,如果存在多項式時間算法IBE.CONVERT(·,·),任取(id,c)∈ID×Cid,記解密算法解密結(jié)果m=DecI(skid,id,c),生成(id′,c′)←IBE.CONVERT(id,c),滿足:

1) 輸出身份id′的分布Did′與U(ID)計算不可區(qū)分;

2) 密文c′與c具有同等的安全強度且m=DecI(skid′,id′,c′).

滿足身份不可區(qū)分性的IBE將作為本文方案構造的基礎之一,構造CCA安全的公鑰加密方案.并且,在方案實例化中,本文將提出2種滿足身份變換不可區(qū)分性的IBE,分別基于格假設與基于DBDH假設.

訪問控制加密:ACE由5個多項式時間算法構成,記作(Setup,KG,Enc,San,Dec).初始化算法為概率性算法,記作(pp,msk)←Setup(1λ,PL),其中,λ為安全參數(shù),PL:[n]×[n]→{0,1}為通信策略,PL(i,j)=1表示用戶i可以給用戶j發(fā)送消息,否則表示不允許發(fā)送,pp表示公共參數(shù),后續(xù)算法都會默認包括公共參數(shù);密鑰生成算法為概率性算法,記作k←KG(msk,i,t),其中i∈{0,1,…,n+1}表示用戶的身份,0表示空身份,n+1表示信道控制器身份,t∈{sen,rec,san}表示身份屬性,分別為發(fā)送者、接收者和信道控制器,k∈{eki,dki,rk}分別表示加密密鑰、解密密鑰和重隨機化密鑰;加密算法為概率性算法,記作c←Enc(eki,m),eki為加密密鑰;密文重隨機化算法為概率性算法,記作c←San(rk,c),rk為重隨機化密鑰;解密算法為確定性算法,記作m′←Dec(dkj,c′),dkj為解密私鑰.

訪問控制加密正確性指對任意合法生成的密鑰eki,dkj,如果PL(i,j)=1,則解密失敗的概率Pr[m′≠m]≤negl(λ),即為關于安全參數(shù)的可忽略函數(shù).訪問控制加密的安全性定義包括選擇明文攻擊下的不可讀規(guī)則(no-read rule, NR)、不可寫規(guī)則(no-write rule, NW)與角色關聯(lián)性(role-respecting, RR),分別記作NR-CPA,NW-CPA,RR-CPA,其中,不可讀規(guī)則根據(jù)安全目標,分為密文負載機密性(payload privacy, PP)發(fā)送者匿名性(sender anonymous, SA),分別記作PP-CPA,SA-CPA;進一步,包括選擇密文攻擊下的不可讀規(guī)則、不可寫規(guī)則與角色關聯(lián)性,分別記作PP-CCA,SA-CPA,NW-CCA,RR-CCA.本文將提出分別滿足2種安全性的訪問控制加密方案.

2 通用方案構造

本節(jié)分別給出CPA安全通用方案構造與CCA安全通用方案構造.

2.1 CPA安全通用方案構造

本節(jié)主要構造針對單用戶系統(tǒng)的訪問控制加密方案,即系統(tǒng)中只有1個發(fā)送者、1個接收者和1個信道控制器,針對多用戶系統(tǒng),可以通過并行執(zhí)行多個單用戶加密方案實現(xiàn)多用戶系統(tǒng)方案構造,記單用戶訪問控制加密方案為1-ACE.1-ACE方案由同態(tài)公鑰加密方案和偽隨機函數(shù)構造而成,記同態(tài)公鑰加密方案PKE為(KGP,EncP,DecP),滿足IND-CPA安全性,密文間的同態(tài)運算記作“+”.記偽隨機函數(shù)為Fkprf(·),其中kprf為偽隨機函數(shù)密鑰.令偽隨機函數(shù)的定義域為PKE的密文空間CP,值域為PKE的明文空間MP.1-ACE方案構造如下:

1) (pp,msk)←Setup(1λ,PL).輸入安全參數(shù)λ和系統(tǒng)通信策略PL:{0,1}×{0,1}→{0,1},初始化算法調(diào)用同態(tài)公鑰加密密鑰生成算法(skP,pkP)←KGP(1λ)和偽隨機函數(shù)密鑰生成算法kprf←KGprf(1λ),輸出1-ACE方案的主私鑰msk=(skP,kprf)和公共參數(shù)pp=(pkP,PL,λ).

2)k←KG(msk,i,t).輸入主私鑰msk,編號i∈{1,2}和角色t∈{sen,rec,san},密鑰生成算法如下:

① 對于輸入(msk,1,sen),輸出發(fā)送者加密密鑰ek1=kprf;

② 對于輸入(msk,1,rec),輸出接收者解密密鑰dk1=skP;

③ 對于輸入(msk,2,san),輸出信道控制器的重隨機化密鑰rk=kprf.

3)c←Enc(ek1,m).輸入加密密鑰ek1和消息m,計算c1=EncP(pkP,m)與c2=EncP(pkP,Fkprf(c1)),輸出密文c=(c1,c2).

4)c′←San(rk,c).輸入重隨機化密鑰rk和密文c,算法選擇1個隨機整數(shù)r,計算密文c3←EncP(pkP,Fkprf(c1))與密文同態(tài)計算結(jié)果c′=r(c2-c3)+c1,輸出重隨機化密文c′.

5)m′←Dec(dk1,c′).輸入解密密鑰dk1和密文c′,調(diào)用解密算法m′←DecP(skP,c′),輸出消息m′.

規(guī)定:如果PL(i,j)=0,即發(fā)送者i不允許給接收者j發(fā)送消息,則發(fā)送給j的密文為從密文空間隨機選擇的密文.

關于方案正確性,如果對于合法生成的公鑰和私鑰,同態(tài)公鑰加密可以正確解密同態(tài)計算后的密文,則1-ACE方案同樣可以正確解密.

1-ACE方案CPA安全性:記λ為安全參數(shù)、PL為通信策略,如果同態(tài)加密方案PKE滿足選擇明文攻擊下不可區(qū)分安全(IND-CPA)且函數(shù)Fkprf(·)滿足偽隨機安全性,則構造的1-ACE方案滿足NR-CPA,NW-CPA,RR-CPA安全性.具體地,對于任意攻擊1-ACE方案的敵手A,假設其運行時間為T,則存在攻擊公鑰加密方案PKE的敵手A′,滿足

2.2 CCA安全通用方案構造

在CCA安全通用方案構造中,同樣以構造單用戶訪問控制加密方案為主.記基于身份的加密方案IBE為(KGI,ExtI,EncI,DecI),且具有同態(tài)性質(zhì),記IBE方案的身份變換算法為IBE.CONVERT(·,·),同態(tài)計算符號為“+”.記SIG=(KGS,S,V)為強一次簽名方案(strong one-time signature),Fkprf(·)為偽隨機函數(shù).滿足CCA安全的1-ACE方案構造如下:

1) (pp,msk)←Setup(1λ,PL).輸入安全參數(shù)λ和系統(tǒng)通信策略PL:{0,1}×{0,1}→{0,1},調(diào)用IBE方案的密鑰生成算法(mskI,mpkI)←KGI(1λ)和偽隨機函數(shù)密鑰生成算法kprf←KGprf(1λ),輸出1-ACE方案的主私鑰msk=(mskI,kprf)和方案公共參數(shù)pp=(mpkI,PL,λ).

2)k←KG(msk,i,t).輸入主私鑰msk,編號i∈{1,2}和角色t∈{sen,rec,san},密鑰生成算法如下:

① 對于輸入(msk,1,sen),輸出發(fā)送者加密密鑰ek1=kprf;

② 對于輸入(msk,1,rec),輸出接收者解密密鑰dk1=mskI;

③ 對于輸入(msk,2,san),輸出信道控制器的重隨機化密鑰rk=kprf.

3)c←Enc(ek1,m).輸入加密密鑰ek1和消息m,調(diào)用強一次簽名密鑰生成算法(skS,vkS)←KGS(λ),將vkS作為IBE的身份標識,計算c1=EncI(mpkI,vkI,m)與c2=EncI(mpkI,vkS,Fkprf(c1)),計算簽名σ←S(skS,(c1,c2)),輸出密文c=(vkS,c1,c2,σ).

如果同態(tài)的IBE方案可以正確解密,則上述方法構造的1-ACE方案同樣可以正確解密.

1-ACE方案CCA安全性:記λ為安全參數(shù)、PL為通信策略,假設同態(tài)IBE方案滿足自適應選擇身份選擇明文攻擊下不可區(qū)分安全(IND-aID-CPA)和身份變換不可區(qū)分性(定義1),一次性簽名方案滿足選擇消息攻擊下強存在不可偽造安全性(sEUF-CMA),函數(shù)Fkprf(·)滿足偽隨機安全性.則構造的1-ACE方案滿足NR-CCA(PP-CCA與SA-CCA)、NW-CCA與RR-CCA安全性.具體地,對于任意攻擊1-ACE方案的敵手A,假設敵手執(zhí)行qD次解密查詢,則存在攻擊IBE方案的敵手A′,滿足

敵手A′的運行時間為T+qD(TE+TD),其中,T為敵手A的運行時間,TE為IBE私鑰提取算法的運行時間,TD為執(zhí)行IBE解密算法的運行時間.

3 方案實例化

CPA安全的訪問控制加密方案可以由ElGamal加密、Paillier加密或基于格的同態(tài)加密[5,14]結(jié)合偽隨機函數(shù)進行實例化構造.本文重點實例化CCA安全的訪問控制加密方案.一種實例化基于帶錯學習假設(LWE)和最短整數(shù)解(SIS)假設,另一種基于判定性雙線性Diffie-Hellman(DBDH)假設.通過通用構造方案可知,實例化的核心是構造滿足條件的IBE方案,本節(jié)只對IBE方案的身份變換算法進行實例化.

3.1 基于LWE與SIS假設方案實例化

CCA安全的訪問控制加密方案實例化構造中IBE方案選擇文獻[13]提出的相關方案,記作GPV-IBE,強一次簽名方案同樣選擇文獻[13]的簽名方案,在文獻[13]中被稱為概率性全域哈希方案(probabilistic full hash scheme),結(jié)合文獻[20]的同態(tài)公鑰加密設計方法,可以簡單地將文獻[13]的IBE方案轉(zhuǎn)化為具有同態(tài)性質(zhì)的IBE方案.記GPV-IBE的身份變換算法為GPV-IBE.CONVERT,構造如下.

(id′,c′)←GPV-IBE.CONVERT(id,c):記身份標識映射函數(shù)為(id)={ui}i∈{1,…,l},其中ui∈為n維整系數(shù)向量,l為明文空間消息長度;GPV-IBE方案的密文拆分為c={(pi,ci)}i∈{1,…,l},其中pi=ATsi+2xi∈包含隨機數(shù)部分,A∈為主公鑰,si∈為隨機選取向量,xi←χn為取自誤差分布的誤差向量;其中ei←χ,mi∈{0,1}為消息比特;隨機選取zi←χm,計算輸出和

3.2 基于DBDH假設方案實例化

基于DBDH假設的方案實例化主要利用文獻[14]提出的IBE方案與文獻[21]的強一次簽名.記IBE方案為WATERS-IBE,方案的身份變換算法如下.