一種基于連接關(guān)鍵詞的實(shí)用化可搜索加密方案

駱云鵬,朱旎彤,毛慈偉,程晉雪,許春根

(南京理工大學(xué) 理學(xué)院,南京 210094)

0 概述

云存儲(chǔ)技術(shù)能為數(shù)據(jù)提供巨大的存儲(chǔ)空間,且其使用較為便捷,因此,得到了研究人員的廣泛關(guān)注。然而,云數(shù)據(jù)通常以明文形式存儲(chǔ),因此,其安全性難以得到保證。近年來,云數(shù)據(jù)泄露事件不斷發(fā)生,其中多數(shù)是由于黑客的非法入侵和云端服務(wù)器管理員的不當(dāng)操作而導(dǎo)致。例如,2011年Sony公司被黑客入侵導(dǎo)致上億用戶資料外泄。

為了更好地解決海量數(shù)據(jù)的安全存儲(chǔ)與檢索問題,可搜索加密技術(shù)[1]應(yīng)運(yùn)而生,其目標(biāo)是在不影響數(shù)據(jù)檢索功能的前提下,保護(hù)用戶外包數(shù)據(jù)的安全性與查詢隱私?？伤阉骷用芗夹g(shù)的基本應(yīng)用過程為:用戶加密自己的數(shù)據(jù)并上傳到遠(yuǎn)程服務(wù)器,在需要檢索文件時(shí)提交其關(guān)鍵詞的陷門給服務(wù)器,隨后服務(wù)器使用陷門檢索到密文并返回給用戶,整個(gè)過程中服務(wù)器將不會(huì)獲取關(guān)于密文與其關(guān)鍵詞的任何信息。

可搜索加密能夠很好地保護(hù)用戶外包數(shù)據(jù)的機(jī)密性,同時(shí)使得加密數(shù)據(jù)的高效搜索成為可能,即具有很好的擴(kuò)展性。文獻(xiàn)[2-3]提出對(duì)稱可搜索加密方案并進(jìn)行進(jìn)一步完善。文獻(xiàn)[4]提出基于公鑰的可搜索加密協(xié)議,其利用基于身份的加密設(shè)計(jì)了公鑰可搜索加密方案。公鑰可搜索加密方案允許多個(gè)用戶利用公鑰進(jìn)行加密,僅擁有相應(yīng)私鑰的用戶才可以搜索加密的數(shù)據(jù)。文獻(xiàn)[5-6]利用雙線性對(duì)分別構(gòu)造了基于連接關(guān)鍵詞的可搜索加密方案BLL和RT,2種方案的特點(diǎn)都是關(guān)鍵詞陷門大小固定,但是判斷每個(gè)文檔時(shí)都需要計(jì)算2次雙線性對(duì)。文獻(xiàn)[7]提出了在非結(jié)構(gòu)文本上的基于連接關(guān)鍵詞的可搜索加密方案FK,其在搜索加密文檔時(shí)無需指定關(guān)鍵詞的位置。為了更接近實(shí)際中的搜索情況,文獻(xiàn)[8]利用詞典和關(guān)鍵詞間的編輯距離,提出了一個(gè)基于模糊關(guān)鍵詞的可搜索加密方案,其在關(guān)鍵詞拼寫錯(cuò)誤或格式不一致的情況下也能搜索出正確的密文。此外,文獻(xiàn)[9-10]提出了其他具有特殊功能的基于多關(guān)鍵詞的可搜索加密方案,擴(kuò)展了多關(guān)鍵詞可搜索加密的應(yīng)用范圍。

本文提出一種基于連接關(guān)鍵詞的可搜索加密方案,并通過Java編程語言實(shí)現(xiàn)該方案,以驗(yàn)證其加密性能。

1 基礎(chǔ)知識(shí)

1.1 雙線性映射

設(shè)p為素?cái)?shù),令G1、G2是p階循環(huán)群,若映射e:G1×G1→G2滿足以下性質(zhì),則稱e為一個(gè)雙線性映射:

2)非退化性(non-degenerate):如果P是G1的生成元,則e(P,P)是G2的生成元。

3)可計(jì)算性(computable):對(duì)于任意的P,Q∈G1,存在多項(xiàng)式時(shí)間算法計(jì)算e(P,Q)。

1.2 方案的困難性假設(shè)

Pr[A(P,xP,x2P,…,xqP)=e(P,P)1/x]≥ε

2 基于連接關(guān)鍵詞的可搜索加密方案

2.1 系統(tǒng)描述

圖1 可搜索加密方案應(yīng)用過程

2.2 算法定義

基于連接關(guān)鍵詞的可搜索加密方案由以下6個(gè)多項(xiàng)式時(shí)間算法組成:

KeyGen(1k):為概率算法,輸入安全參數(shù)k,生成一個(gè)公私鑰對(duì)(Apub,Apriv)。

Encrypt(Apub,D):為用戶執(zhí)行的加密算法,輸入公鑰Apub和文件M,輸出密文C。

2.3 安全性模型

初始化利用KeyGen(1k)算法產(chǎn)生私鑰Apriv并將其發(fā)送給攻擊者。

階段1適應(yīng)性詢問階段:

挑戰(zhàn)攻擊者向挑戰(zhàn)者提交挑戰(zhàn)文件D0=(M0,H0)和D1=(M1,H1)。其限制為:在階段1中,D0和D1在搜索陷門詢問階段未被詢問,且Qi與H0和H1的匹配情況在解密陷門詢問階段未被詢問,同時(shí)和在解密詢問階段未被詢問。挑戰(zhàn)者挑出一個(gè)隨機(jī)數(shù)b∈{0,1},并將其加密后的密文C=Encrypt(Apub,Db)發(fā)送給攻擊者。

猜測攻擊者輸出b′∈{0,1},當(dāng)b′=b時(shí),攻擊者獲勝。

本文定義攻擊者A在攻擊基于連接關(guān)鍵詞的可搜索加密模型時(shí)的優(yōu)勢為:

Advε,A(1k)=|Pr[b=b′]-1/2|

3 算法構(gòu)造

(1)

如果式(1)等式成立,則輸出Yes;否則,輸出No。

(2)

如果式(2)等式成立,則輸出E,Enc(sk,PB);否則,輸出⊥。

式(1)的數(shù)學(xué)證明如下:

如果WIi=Ωi,有:

式(2)的數(shù)學(xué)證明如下,有:

如果WIi=Ωi,有:

H3(M‖B1‖B2‖…‖Bm,sk)=r0

4 安全性分析

本文通過建立一個(gè)隨機(jī)預(yù)言機(jī)模型[13]進(jìn)行選擇密文攻擊,采用規(guī)約化思想將安全性問題規(guī)約為求解q-BDH問題,以證明本文方案具有選擇密文攻擊下的密文不可區(qū)分性(IND-CCA)。挑戰(zhàn)者通過預(yù)言機(jī)得到的密文D0和D1不會(huì)泄露文件0和文件1是否包含相同關(guān)鍵詞,即敵手無法通過獲得的陷門查詢到含相同關(guān)鍵詞的其他文件。

定理1如果q-BDH問題在群G1難解,則本文可搜索加密方案具有選擇密文攻擊下的密文不可區(qū)分性(IND-CCA)。

H1查詢敵手A向隨機(jī)預(yù)言機(jī)H1發(fā)出查詢請(qǐng)求,為了響應(yīng)這個(gè)請(qǐng)求,B初始化一個(gè)空的三元組列表H1,當(dāng)A向隨機(jī)預(yù)言機(jī)H1請(qǐng)求Wi∈{0,1}*時(shí),B按以下規(guī)則做出回應(yīng):

1)如果查詢Wi出現(xiàn)在H1表中,B回復(fù)H1(Wi)=hi。

3)如果ci>m,B選擇一個(gè)隨機(jī)數(shù)hi∈{0,1}lb p,否則,hi=βci。

4)B將加入H1表,回復(fù)H1(Wi)=hi。

H2查詢敵手A向隨機(jī)預(yù)言機(jī)H2發(fā)出查詢請(qǐng)求,為了響應(yīng)這個(gè)請(qǐng)求,B需要初始化一個(gè)空的二元組列表H2,當(dāng)A向隨機(jī)預(yù)言機(jī)H2請(qǐng)求gi∈{0,1}*時(shí),B按以下規(guī)則做出回應(yīng):

1)如果查詢gi出現(xiàn)在H2表中,B回復(fù)H2(gi)=γi。

2)否則,B隨機(jī)生成一個(gè)γi∈{0,1}lb p,并將加入H2表中,回復(fù)H2(gi)=γi。

H3查詢敵手A向隨機(jī)預(yù)言機(jī)H3發(fā)出查詢請(qǐng)求。為了響應(yīng)這個(gè)請(qǐng)求,B初始化一個(gè)空的多元組列表H3,當(dāng)A向隨機(jī)預(yù)言機(jī)H3發(fā)送請(qǐng)求Mi‖Bi,1‖Bi,2‖…‖Bi,m∈{0,1}*和ski∈κ時(shí),B按以下規(guī)則做出回應(yīng):

1)如果查詢Mi‖Bi,1‖Bi,2‖…‖Bi,m和ski已經(jīng)出現(xiàn)在H2表中,B回復(fù)H3(Mi‖Bi,1‖Bi,2‖…‖Bi,m,ski)=roi。

表1 Hash算法說明

挑戰(zhàn)者與攻擊者之間的攻擊游戲如下:

階段1A提出查詢qi,且qi是以下查詢中的一種:

1)ST查詢:當(dāng)A發(fā)起Qi=(Ii,1,Ii,2,…,Ii,ti,Ωi,1,Ωi,2,…,Ωi.ti)查詢搜索陷門,B進(jìn)行如下操作:

(1)B模擬H1查詢獲得hi,j,hi,j=H1(Ωi,j),找到<Ωi,j,hi,j,ci,j>對(duì)應(yīng)表中的多元組,如果?j,ci,j=Ii,j,則B失敗,即不能找到含相同關(guān)鍵詞的組。

(2)否則,B定義Ji=sIi,1+sIi,2+…+sIi,ti+hi,1+…+hi,ti=Γix+Δi,其中,Γi=αIi,1+αIi,2+…+αIi,ti,Δi=-(βIi,1+βIi,2+…+βIi,ti)+(hi,1+hi,2+…+hi,ti)。

2)DT查詢:當(dāng)A發(fā)起Qi=(Ii,1,Ii,2,…,Ii,ti,Ωi,1,Ωi,2,…,Ωi.ti)查詢解密陷門,B進(jìn)行如下操作:

(1)B模擬H1查詢獲得hi,j,hi,j=H1(Ωi,j),找到<Ωi,j,hi,j,ci,j>對(duì)應(yīng)表中的多元組,如果?j,ci,j=Ii,j,則B失敗,即不能找到含相同關(guān)鍵詞的組。

(2)否則,B定義Ji=SIi,1+SIi,2+…+SIi,ti+hi,1+hi,2+…+hi,ti=Γix+Δi,其中,Γi=αIi,1+αIi,2+…+αIi,ti,Δi=-(βIi,1+βIi,2+…+βIi,ti)+(hi,1+hi,2+…+hi,ti)。

挑戰(zhàn)者A輸出2個(gè)文件D0=(M0,H0)和D1=(M1,H1),并發(fā)送給B。B進(jìn)行如下操作:

1)B執(zhí)行上述算法,通過回復(fù)H1查詢來獲得hi,j,hi,j=H1(Wi,j),i∈{0,1},1≤j≤m。將添加在H1表中。若?j,ci,j=j對(duì)i=0或1成立,則B成功。

2)B取i=0或1,使得?j,ci,j=j。

階段2B重復(fù)階段1的操作獲得它所輸入關(guān)鍵詞的陷門,其中有一個(gè)限制為:C未被詢問過,即未對(duì)D0和D1進(jìn)行過陷門查詢和解密查詢。

最終,A會(huì)給出判斷結(jié)果,表明B給出的挑戰(zhàn)C是否為D0或D1的密文。

5 應(yīng)用方案

根據(jù)算法過程,本文實(shí)現(xiàn)了服務(wù)器與客戶端一對(duì)多的交互型可搜索加密云存儲(chǔ)系統(tǒng)[14],將可搜索加密方案劃分到服務(wù)器和客戶端2個(gè)部分,通過交互實(shí)現(xiàn)文件的存取和共享[15]。

5.1 控制臺(tái)算法的分析與實(shí)現(xiàn)

為進(jìn)行算法效率測試,需實(shí)現(xiàn)一個(gè)控制臺(tái)算法,從而避免在真實(shí)場景下網(wǎng)絡(luò)與文件的讀寫影響算法的實(shí)際運(yùn)行時(shí)間。本文借助Java的JPBC庫來實(shí)現(xiàn)控制臺(tái)算法[16],工具函數(shù)的說明如下:

1)字符串處理函數(shù):算法在具體描述中,關(guān)鍵詞以比特串形式存在,因此,需要將關(guān)鍵詞編碼成比特串。本文編碼方案先取出字符串中每個(gè)字符的Ascii碼,將其轉(zhuǎn)化為8位比特串,將每個(gè)字符串的比特串拼接得到字符串的比特串標(biāo)識(shí),上述過程可逆。

2)哈希函數(shù)選擇:算法中需要H1、H2、H33個(gè)哈希函數(shù),程序選擇MD5消息摘要算法作為H1、H3,SHA1數(shù)字簽名算法作為H2。H3的輸入由比特串和對(duì)稱加密密鑰的比特串拼接構(gòu)成。

參數(shù)設(shè)置:有限域的階數(shù)為512比特位,群的階數(shù)為128比特位。

控制臺(tái)算法運(yùn)行結(jié)果如圖2所示。其中,H2=S說明STrapdoor匹配成功,origin_sk=get_sk表明DTrapdoor匹配成功并解密出正確密鑰。

圖2 控制臺(tái)算法運(yùn)行結(jié)果

5.2 服務(wù)器-客戶端的分析與實(shí)現(xiàn)

將可搜索加密方案分離到服務(wù)器與客戶端2個(gè)部分[17],服務(wù)器交互界面如圖3所示,客戶端工具界面如圖4所示。

圖3 服務(wù)器交互界面

圖4 客戶端工具界面

方案步驟說明如下:

1)文件的加密方式:采用AES128加密算法進(jìn)行加密。

2)代數(shù)結(jié)構(gòu)與元素的存儲(chǔ)方式:不同于控制臺(tái)程序,服務(wù)端和客戶端不再共享變量,因此,所有的群元素、群結(jié)構(gòu)需要編碼成某種形式并傳送給服務(wù)器,本文將群元素編碼成byte數(shù)組進(jìn)行傳輸,將群結(jié)構(gòu)以Java配置文件.properties形式存取。

3)本地索引:算法本身能夠?qū)崿F(xiàn)連接查詢,但是需要用戶自行記憶關(guān)鍵詞在文件中的位置,這對(duì)用戶不夠友好,因此,通過生成本地關(guān)鍵詞索引,實(shí)現(xiàn)用戶本地的預(yù)查詢,這樣可以避免記憶關(guān)鍵詞位置,同時(shí)也可以實(shí)現(xiàn)否定查詢。

4)密鑰封裝:由于用戶無需記憶AES128的密鑰,因此為了簡化程序過程,通過群元素生成AES128密鑰,這樣避免了將密鑰編碼成橢圓曲線上的點(diǎn)的繁瑣步驟,同時(shí)對(duì)安全性沒有任何影響。

5)密鑰存儲(chǔ):自存自取的文件密鑰均存儲(chǔ)在本地,本地工具默認(rèn)對(duì)不同文件使用不同的密鑰,保證某個(gè)用戶分享文件后,分享對(duì)象不會(huì)獲得解密該用戶所有文件的能力。

6)一對(duì)多分享設(shè)計(jì):在本文算法步驟中,同時(shí)分享文件給多個(gè)用戶是不沖突的,通過輸入其他用戶的公鑰集合,程序針對(duì)每個(gè)公鑰生成一個(gè)私鑰,從而方便一對(duì)多的分享過程,且相比于單一分享模式,一對(duì)多分享需要的額外存儲(chǔ)空間可以忽略不計(jì)。

7)文件存取等步驟的簡化:用戶查詢到的文件和公鑰一般是多個(gè),本文方案能夠?qū)Χ鄠€(gè)文件同時(shí)進(jìn)行解密而非逐個(gè)解密,對(duì)公鑰集合進(jìn)行統(tǒng)一上傳而無需逐個(gè)上傳。

5.3 效率分析

本節(jié)分析方案的效率,用m、P、E、H和n分別代表關(guān)鍵詞個(gè)數(shù)、一次雙線性運(yùn)算的復(fù)雜度、一次指數(shù)運(yùn)算的復(fù)雜度、哈希運(yùn)算和其他運(yùn)算,p代表Zp的階數(shù)。本文方案與其他方案進(jìn)行效率比較[18],結(jié)果如表2所示。算法運(yùn)行環(huán)境是Linux deepin15.5,Intel(R)Core(TM)i7-7700HQ,8 GB內(nèi)存,語言為Java 8。

表2 各加密方案的效率對(duì)比

由于文件及其索引均以密文形式存儲(chǔ)在云端,因此文件與文件之間、索引與索引之間都具有不可區(qū)分性,無法進(jìn)行排序,這使得在陷門匹配的過程中,陷門需要通過順序查找與所有文件索引一一匹配,算法復(fù)雜度為O(n),其中,每一步都包含了2次雙線性配對(duì)。在效率分析時(shí),本文不再考慮文件加密、密鑰生成、密鑰解密、文件解密過程中所消耗的時(shí)間,原因是它們的時(shí)間相比于陷門匹配可忽略不計(jì)。

針對(duì)不同的關(guān)鍵詞個(gè)數(shù),分別比較本文方案和基于PEKS的連接關(guān)鍵詞方案(簡稱PEKS方案)在密文生成、陷門生成和單個(gè)文件匹配上的時(shí)間,結(jié)果如圖5～圖7所示。在圖7中,worst是最長匹配時(shí)間,即全部關(guān)鍵詞匹配成功的時(shí)間,best是最短匹配時(shí)間,即在第一個(gè)關(guān)鍵詞就匹配失敗的時(shí)間,average是平均匹配時(shí)間。可以看出,本文方案與對(duì)比方案在密文生成上的效率相當(dāng),而在陷門生成和文件匹配時(shí),由于對(duì)比方案以及多數(shù)方案[4,19]中采用決策樹來實(shí)現(xiàn)連接關(guān)鍵詞搜索,需要生成多個(gè)陷門并進(jìn)行多次匹配,因此所需時(shí)間隨著關(guān)鍵詞個(gè)數(shù)的增多而顯著提高,而本文方案僅需單陷門單次匹配,因此,其陷門生成和匹配時(shí)間復(fù)雜度與關(guān)鍵詞無關(guān),由結(jié)果可見,本文方案在保證密文生成效率的同時(shí),大幅提高了連接關(guān)鍵詞的搜索效率。

圖5 2種方案密文生成效率對(duì)比

圖6 2種方案陷門生成效率對(duì)比

圖7 2種方案單個(gè)文件匹配效率對(duì)比

6 結(jié)束語

本文提出一種基于連接關(guān)鍵詞的可搜索加密方案,安全性證明結(jié)果顯示,破譯該方案的難度高于求解BDH問題。考慮到記憶關(guān)鍵詞位置時(shí)存在一定難度,本文制作一個(gè)索引作為單關(guān)鍵詞文件并加密上傳,用戶可通過解密獲得關(guān)鍵詞位置信息,方便其進(jìn)行文件查詢。此外,該方案在不泄露私鑰的前提下可以完成與他人的文件共享。但是,本文方案中多個(gè)關(guān)鍵詞使用單個(gè)陷門,下一步將針對(duì)方案中可能存在的哈希碰撞問題進(jìn)行研究并提出解決方案。