基于身份的具有否認認證的關(guān)鍵字可搜索加密方案

曹素珍 丁賓賓* 丁曉暉 竇鳳鴿 王彩芬

①(西北師范大學(xué) 蘭州 730000)

②(深圳技術(shù)大學(xué) 深圳 518118)

1 引言

云存儲技術(shù)[1]的發(fā)展實現(xiàn)了資源共享，幫助用戶降低了存儲成本?？紤]到云端數(shù)據(jù)的敏感性，數(shù)據(jù)需要被加密后存放在云端，傳統(tǒng)數(shù)據(jù)加密技術(shù)[2]雖有效地保護了數(shù)據(jù)的隱私，但同時又帶來了對云端密文數(shù)據(jù)檢索的難題?？伤阉骷用芗夹g(shù)[3]在保護用戶的隱私的同時又支持密文檢索，在云存儲中得到了廣泛的應(yīng)用。

2004年，Boneh 等人[4]提出了第1個公鑰可搜索加密方案(Public key Encryption with Keyword Search, PEKS)，該方案既支持密文檢索又實現(xiàn)了數(shù)據(jù)共享，但搜索效率低，安全性較差。2006年，Byun等人[5]指出PEKS方案存在離線關(guān)鍵字猜測攻擊(Keyword Guessing Attack, KGA)[6]的風(fēng)險。傳統(tǒng)的公鑰可搜索加密方案需要證書頒發(fā)機構(gòu)發(fā)布和管理用戶的證書，基于身份密碼體制[7]下的公鑰可搜索加密方案解決了復(fù)雜的證書管理問題。2014年，Wu等人[8]在身份密碼體制下提出了指定測試者的可搜索加密方案，該方案具有密文和陷門不可區(qū)分性，由于該方案并未完全定義在身份密碼系統(tǒng)架構(gòu)上，不能完全滿足密文不可區(qū)分性。王少輝等人[9]在Wu等人方案基礎(chǔ)上設(shè)計了一個具有更高效率可搜索加密方案，證明了密文不可區(qū)分性是抵御離線關(guān)鍵字猜測攻擊的充分條件，故Wu等人方案也存在離線關(guān)鍵字猜測攻擊的風(fēng)險。2017年，Huang等人[10]提出了具有公鑰認證的可搜索加密方案，通過對關(guān)鍵字認證和加密，以抵御內(nèi)部離線關(guān)鍵字猜測攻擊。但該方案存在一個缺點，若云服務(wù)器被外部攻擊者攻破，用戶的搜索隱私將被泄露。

為了保護用戶的搜索隱私，Baek等人[11]提出在擁有陷門而沒有接收者私鑰的情況下，一個指定測試者無法完成云端密文數(shù)據(jù)的檢索，但該方案無法抵御離線關(guān)鍵字猜測攻擊。為了提高離線關(guān)鍵字猜測攻擊下的安全性。2019年， Li等人[12]提出了指定服務(wù)器的基于身份認證的關(guān)鍵字可搜索加密方案，Lu等人[13]借鑒簽密思想，實現(xiàn)了在關(guān)鍵字加密過程中，敵手不能試圖通過產(chǎn)生合法關(guān)鍵字密文以達到匹配陷門的目的。普遍存在的缺陷是上述方案均沒有考慮到對發(fā)送者身份隱私保護的問題。

如今，個人信息和隱私趨于透明化。在電子投票、醫(yī)療信息、電子郵件、行政和司法報告等應(yīng)用環(huán)境中，如何保護發(fā)送者的身份隱私，使其能夠否認發(fā)送消息的行為已成為研究熱點。否認認證協(xié)議由Dwork等人[14]首次提出，該協(xié)議基于零知識證明來定義，接收者可以確認消息發(fā)送者的身份，但無法向第三方證明這一事實。 Li等人[15]在身份密碼體制下提出了具有更高效率的否認認證加密方案，并在電子郵件系統(tǒng)中得到了很好的應(yīng)用。 Wu等人[16]在身份密碼體制下提出了同時具有認證性和否認性的否認認證加密方案。

在基于身份的密碼體制下，本文提出了具有否認屬性的關(guān)鍵字可搜索加密方案，將否認認證與關(guān)鍵字可搜索加密技術(shù)相結(jié)合，在隨機預(yù)言模型下，基于雙線性Diffie-Hellman(Bilinear Diffie-Hellman,BDH)和決策雙線性Diffie-Hellman(Decisional Bilinear Diffie-Hellman, DBDH)數(shù)學(xué)困難問題，證明了方案滿足不可偽造性、密文和陷門不可區(qū)分性，同時具有否認性，即第三方無法確認消息的真實發(fā)送者，從而保護了發(fā)送者的身份隱私。

2 IDAPKSE安全模型

2.1 IDAPKSE系統(tǒng)模型

基于身份的具有否認認證的關(guān)鍵字可搜索加密方案(Identity-based Public Key keyword Searchable Encryption scheme with Denial Authentication, IDAPKSE)中有密鑰分發(fā)中心、發(fā)送者、接收者和云服務(wù)器4類實體，系統(tǒng)模型圖如圖1所示。

圖1 系統(tǒng)模型圖

(1) 密鑰分發(fā)中心(Key Generation Center,KGC)：KGC生成系統(tǒng)參數(shù)params和主密鑰s，并為發(fā)送者、接收者和云服務(wù)器提供私鑰SKi。

(2) 發(fā)送者(Data Sender, DS)：D S對明文和所選關(guān)鍵字加密，將密文上傳到云服務(wù)器。

(3) 接收者(Data Receiver, DR)：D R運行陷門生成算法，將生成的陷門上傳到云服務(wù)器。

(4) 云服務(wù)器(Cloud Server, CS)：存儲發(fā)送者上傳的密文數(shù)據(jù)，并通過接收者上傳的陷門，進行密文檢索。

2.2 IDAPKSE形式化定義

IDAPKSE包括以下算法：

(1) Setup(k)：KGC 輸入安全參數(shù)k，返回系統(tǒng)參數(shù)params和主密鑰s。

(2) 密鑰提取算法：(a)發(fā)送者和接收者密鑰提取：KGC 輸入主密鑰s和身份標(biāo)識I Di，返回公私鑰對(PKi,SKi)；(b)云服務(wù)器密鑰提?。篕GC 輸入系統(tǒng)參數(shù)params，返回云服務(wù)器的公私鑰對(PKC,SKC)。

(3) 關(guān)鍵字否認認證加密算法：發(fā)送者輸入?yún)?shù)params、關(guān)鍵字w、發(fā)送者身份I DS和私鑰SKS、云服務(wù)器的公鑰PKC、接收者的身份IDR和公鑰PKR，返回密文C并上傳到云服務(wù)器。

(4) 陷門生成算法：接收者輸入系統(tǒng)參數(shù)params、關(guān)鍵字w、發(fā)送者身份I DS和接收者身份IDR，輸出陷門Tw。

(5) 測試算法：云服務(wù)器輸入系統(tǒng)參數(shù)params、服務(wù)器私鑰SKC和陷門Tw，輸出φ。若接收者上傳的陷門與發(fā)送者上傳的關(guān)鍵字密文中包含相同的關(guān)鍵字，則φ=1，否則φ=0。

2.3 IDAPKSE安全模型

IDAPKSE方案的安全性主要考慮為不可偽造性、密文和陷門的不可區(qū)分性、否認性。下面通過挑戰(zhàn)者β和敵手αi(i=1,2,3,4)之間的游戲給出方案的安全模型。

游戲 1 不可偽造性。

(1) Setup(k)：β輸入安全參數(shù)k，返回系統(tǒng)參數(shù)params給α1，自身保留主密鑰s，運行密鑰提取算法，返回云服務(wù)器公私鑰對(PKC,SKC)。

(2) 私鑰詢問階段：α1對目標(biāo)身份外的用戶進行私鑰詢問，β運行密鑰提取算法返回私鑰給α1。

(3) 關(guān)鍵字否認認證加密詢問階段：α1向β提交發(fā)送者身份IDS、接收者身份IDR和關(guān)鍵字w。β運行密鑰提取算法得到發(fā)送者的私鑰SKS，運行關(guān)鍵字否認認證加密算法，返回密文C給α1。

(4) 陷門詢問階段：α1可以對挑戰(zhàn)關(guān)鍵字外的任意關(guān)鍵字進行陷門詢問。β通過α1選取的關(guān)鍵字w，運行陷門生成算法生成陷門Tw，返回給α1。

游戲 3 陷門不可區(qū)分性。

(1) Setup(k)：私鑰詢問階段、關(guān)鍵字否認認證加密詢問階段和陷門詢問階段同游戲1。

(2) 挑戰(zhàn)階段：α3向β提交發(fā)送者的身份I DS和接收者的身份IDR、挑戰(zhàn)關(guān)鍵字(w0?, w1?)。β隨機選擇b ∈{0,1}，生成wb的陷門Tw?返回給α3。

游戲 4 否認性。

(1) Setup(k)：假設(shè)β能夠為系統(tǒng)中的任何誠實用戶生成IDAPKSE方案下的合法密文，選擇兩個誠實的用戶D0和D1。

(2) 挑戰(zhàn)階段：α4向β提交明文消息M，β隨機選擇b ∈{0,1}，并與Db交互，使Db能夠?qū)生成IDAPKSE方案下的合法密文C?返回給α4。

(3) 區(qū)分階段：α4輸出b′∈{0,1}，若b′=b，則α4在游戲4中獲勝。

因游戲中D0和D1生成的密文的概率分布是相同的，所以對于區(qū)分者是不可區(qū)分的。

α4贏得游戲4的優(yōu)勢為

3 IDAPKSE方案

3.1 具體方案

(1) Setup(k)：輸入安全參數(shù)k，KGC執(zhí)行以下操作：(a)選擇q階循環(huán)群G1和G2，g為G1的生成元，再選擇雙線性映射e:G1×G1→G2；(b)在G1群中選擇生成元U和h，KGC隨機選擇s ∈Zq?作為主密鑰，并計算公鑰Ppub=sU；(c)定義3個抗碰撞的哈希函數(shù)：H1:{0,1}?→G1；H2:G2×{0,1}?→G1；H3:{0,1}?→Zq?。KGC保留主密鑰s，公開系統(tǒng)參數(shù)params={k, q, G1, G2, U, h, g ,Ppub, H1, H2, H3}。

(2) 密鑰提取算法：(a)發(fā)送者和接收者密鑰提取：發(fā)送者和接收者將身份 IDi發(fā)送給KGC，KGC計算對應(yīng)公鑰Qi=H1(IDi)和私鑰SKi=sQi，并通過安全信道將私鑰返回給發(fā)送者和接收者；(b)云服務(wù)器密鑰提取：KGC隨機選擇t ∈Zq?作為云服務(wù)器私鑰；輸入t和系統(tǒng)參數(shù)params，計算云服務(wù)器公鑰PKC=tg。

(3) 關(guān)鍵字否認認證加密算法：發(fā)送者輸入系統(tǒng)參數(shù)params、關(guān)鍵字w、發(fā)送者身份I DS和公私鑰對(PKS,SKS)、接收者身份IDR和公鑰PKR、云服務(wù)器公鑰PKC，按以下步驟加密關(guān)鍵字：

(a)計算：QS=H1(IDs),QR=H1(IDR),T=rQS，其中r ∈Zq?；

3.2 IDAPKSE方案正確性分析

IDAPKSE方案的正確性當(dāng)且僅當(dāng)驗證等式C1·e(SKCT1, C3)=e(SKCT2, C2)是否成立

4 安全性分析

4.1 不可偽造性

引理1 在隨機預(yù)言模型下，若敵手α1在時間t內(nèi)贏得游戲1，則存在算法C 可以解決BDH問題。

證明 挑戰(zhàn)者β輸入1個隨機的BDH問題實例(P , aP , bP , cP)，目標(biāo)計算e(P , P)abc。

(1) Setup(k)：β輸入安全參數(shù)k，返回系統(tǒng)參數(shù)params給α1。設(shè)置公鑰Ppub=cP，c為主密鑰。

(2) 攻擊階段：β維護L1,L2,L3列表，將其初始化為空，分別作為α1對隨機預(yù)言機H1,H2,H3的查詢追蹤，α1執(zhí)行多項式有界次查詢：

(a)公鑰詢問：α1向β提交任意用戶身份IDi，β檢查L1。

若未對IDi進行任何詢問，IDi為⊥，β得到(IDi,ni)，隨機選擇xi ∈Zq?作為私鑰SKi，計算公鑰PKi=xiP，返回PKi給α1并向列表L1中添加一個新的元組(IDi,PKi,SKi, ni)。

若IDi不為⊥，L1列表中存在相應(yīng)的元組，則返回存在的結(jié)果。

(b)私鑰詢問：α1提交用戶身份I Di，獲取相應(yīng)的用戶私鑰，若IDi=IDS或IDi=IDR，結(jié)束模擬。否則，β檢查列表L1。

若未對IDi進行任何詢問，IDi為⊥，β得到(IDi, ni)，隨機選擇xi ∈Zq?作為私鑰SKi，計算公鑰PKi=xi P，返回SKi給α1，并向列表L1中添加一個新的元組(IDi,PKi,SKi, ni)。

若IDi不為⊥，L1列表中存在相應(yīng)的元組，則返回存在的結(jié)果。

(c)關(guān)鍵字否認認證加密詢問：α1向β提交選定的發(fā)送者身份 IDS和接收者身份IDR及關(guān)鍵字w,β執(zhí)行以下操作：

若α1提交的IDi與β選擇的兩個身份不同，即IDi ?=IDS和IDi ?=IDR。β運行密鑰提取算法得到發(fā)送者私鑰SKS，運行關(guān)鍵字否認認證加密算法生成密文C返回給α1。

若α1提交發(fā)送者身份I Di是β選擇的兩個身份之一，即IDi=IDS或IDi=IDR，但接收者身份IDj ?=IDS且IDj ?= IDR。β不能計算發(fā)送者的私鑰，但能計算接收者的私鑰SKj=njPpub。β隨機選擇r ∈Zq?，進行以下計算：

(a)計算：T=rQi,C1=e(H2(e(T,SKj), w),PKC)r；

(b)計算：C2=rg,C3=rh；

(c)計算：Y=H3(w||IDi||IDj, T)；

(d)計算：V=e(T+Y Qi),SKj)；

(e)C=(T, C1, C2, C3, V)，返回密文C給α1。

若α1提交發(fā)送者身份與β選中身份相同，即IDi=IDS且IDj= IDR或IDj=IDS且IDi=IDR。這時，β不能夠計算發(fā)送者和接收者的私鑰，β隨機選擇r,h ∈Zq?，進行以下計算：

(a)計算：T=rP-hQi,Y=H3(w||IDR||IDS,T)，向列表L3中添加元組(w||IDR||IDS, T, h)；

(b)計算：C1=e(H2(e(SKS,QR),w),PKC)r，向列表L2中添加元組(PKS,PKR,C1,V)，其中V=e((r+Y)SKS, QR)；

目前沒有公認的解決BDH困難問題的有效算法，因此α1不存在，方案滿足密文的不可偽造性。證畢

4.2 密文不可區(qū)分性

引理2 在隨機預(yù)言模型下，若敵手α2在時間t內(nèi)贏得游戲2，則有算法C 可以解決DBDH問題。

證明 挑戰(zhàn)者β輸入一個隨機的DBDH問題實例(G1, G2, e, q,g, xg, yg, zg, Z)，目標(biāo)是解決DBDH問題。

(1) Setup(k)：β輸入安全參數(shù)k，返回params={k, q, G1, G2, e, P, h, g ,Ppub}， 其中Ppub=ZP，Z為主密鑰。計算云服務(wù)器公私鑰對PKC=tg和SKC=t，將params和云服務(wù)器公私鑰對(PKC,SKC)返回給α2。

(2) 攻擊階段：β維護L1,L2,L3列表，將其初始化為空，分別作為α2對隨機預(yù)言機H1,H2,H3的查詢追蹤，α2執(zhí)行多項式有界次查詢：

(a)公鑰詢問，私鑰詢問和關(guān)鍵字否認認證加密詢問同上文不可偽造性證明。

(b)陷門詢問階段：α2向β提交選擇的發(fā)送者身份IDS、接收者身份IDR和關(guān)鍵字w，β執(zhí)行以下操作：

若α2提交的發(fā)送者的身份與β選取的身份相同，即IDi=IDS且IDj= IDR或IDi=IDR且IDj=IDS，計算T1=ag,T2=H2(Z, w)+ah，返回陷門Tw=(T1, T2)給α2。

(4)α2繼續(xù)執(zhí)行上詢問。

(5) 猜測階段：α2輸出b′∈{0,1}，若b′=b，輸出1，否則輸出0。

F表示對挑戰(zhàn)身份的猜測是不正確的，挑戰(zhàn)者β將中止。

若β中止，則β隨機輸出b的概率為1 /2。當(dāng)β隨機猜測時，F(xiàn)不發(fā)生的概率是1/(qH(qH-1))，即Pr(F) =1/(qH(qH-1))，qH為α2最多詢問次數(shù)。

若β不被中止，α2最多贏得游戲2的概率1 /2，故β解決DBDH困難問題的優(yōu)勢為

4.3 陷門不可區(qū)分性

引理3 若DBDH假設(shè)為真，則本文方案滿足陷門不可區(qū)分性。

4.4 否認性

5 分析和比較

5.1 安全功能分析

公開發(fā)表的文獻顯示，目前還沒有基于身份的具有否認認證的關(guān)鍵字可搜索的加密方案。因此，本文的方案不能與同類方案進行比較。本文方案將在關(guān)鍵字加密、陷門生成和關(guān)鍵字密文檢索3個方面與文獻[8,10,12]的方案進行比較，表1為各方案功能對比。

表1 各方案功能對比

從表1可以看出本文方案和文獻[8,12]的方案都是在基于身份密碼體制下構(gòu)建且指定測試者，文獻[10,12]的方案和本文方案能夠抵御內(nèi)部和外部關(guān)鍵字猜測攻擊，文獻[8]的方案能夠抵御外部關(guān)鍵字猜測攻擊，但不能抵御內(nèi)部關(guān)鍵字猜測攻擊。

5.2 計算量分析

表2為各方案計算量對比， P為雙線性對運算，E 為指數(shù)運算， M 為點乘運算， H為哈希運算。表3為基本運算所消耗的時間，在關(guān)鍵字加密階段，本文方案有3個雙線性對運算，文獻[8,12]分別存在1, 2個雙線性對運算，文獻[10]沒有對運算，計算量由大到小依次為：文獻[12]、本文方案、文獻[10]、文獻[8]；在陷門生成階段，本文方案與文獻[10,12]都存在1個對運算，文獻[8]沒有對運算，計算量由大到小依次為：文獻[12]、文獻[10]、本文方案、文獻[8]；在關(guān)鍵字密文檢索階段，各個方案都存在2個對運算，文獻[8]多出1個哈希運算，文獻[12]多出2個指數(shù)運算，計算量由大到小依次為：文獻[12]、文獻[8]、本文方案、文獻[10]。綜合以上分析，本文方案在關(guān)鍵字加密和生成陷門階段，計算效率偏低，計算性能上并未占據(jù)優(yōu)勢。在關(guān)鍵字密文檢索階段，本文方案與文獻[10]的計算效率相似，與文獻[8,12]相比，具有更佳的計算性能表現(xiàn)。

表2 計算量對比

5.3 時間性能分析

本節(jié)通過仿真實驗將本文方案與文獻[8,10,12]的方案在關(guān)鍵字加密、陷門生成和關(guān)鍵字密文檢索3個方面進行了對比，加密函數(shù)由PBC[18]提供，實驗選取關(guān)鍵字Lenovo筆記本(AMD Ryzen 5 4600U with Radeon Graphics @2.10 Hz，16 GB內(nèi)存和Linux實驗選取關(guān)鍵字分別為：1, 50, 100, 300,500, 700, 900, 1000，實驗結(jié)果如圖2所示。從圖2可以看出在關(guān)鍵字加密階段，隨著關(guān)鍵字數(shù)量的增加，關(guān)鍵字加密的時間也在增加，在關(guān)鍵字數(shù)量相同的情況下，本文方案在加密階段加密時間小于文獻 [12]，本文方案比文獻[8]多出2個對運算，加密時間比文獻[8]要長。在陷門生成階段，本文方案與文獻[10,12]均有1個對運算，但文獻[12]存在2個指數(shù)運算，文獻[10]存在1個指數(shù)運算，本文方案相較于文獻[10,12]，優(yōu)勢在于在該階段沒有指數(shù)運算，生成陷門的時間相對較短，文獻[8]在該階段不存在對運算和指數(shù)運算，生成陷門時間比本文方案要短。在關(guān)鍵字密文檢索階段，各方案均有2個對運算，文獻[12]多出了2個指數(shù)運算，運算時間相對于其他方案較長，本文方案在關(guān)鍵字密文檢索階段比文獻[8,10]多出了2個點乘運算時間，文獻[8]比本文方案和文獻[10]多出1個哈希運算。由表3可以看出，點乘耗費時間最短，檢索關(guān)鍵字密文所耗費的時間本文方案接近于文獻[10]。本文方案在各個階段的計算所消耗的時間相較于其他3種方案有長有短，但本文最大的優(yōu)勢在于實現(xiàn)了否認屬性，對發(fā)送者的隱私有了很好的保護，在電子郵件、醫(yī)療信息等方面有著較好的應(yīng)用前景。

表3 不同操作的基本運算耗費時間(ms)

圖2 算法運行時間比較

6 結(jié)束語

本文方案將關(guān)鍵字可搜索加密與否認認證加密相結(jié)合，基于BDH和DBDH困難問題證明了方案滿足不可偽造性、密文和陷門的不可區(qū)分性。本文方案中的否認屬性，在保護發(fā)送者身份隱私上具有較高的實用性。不足的是本文方案基于身份密碼體制構(gòu)建，基于身份的密碼體制雖解決了PKI中的證書管理問題，但也存在密鑰托管和密鑰撤銷的缺陷，未來我們將否認認證加密遷移到無證書密碼體制下，利用無證書優(yōu)勢解決密鑰托管問題。