一種基于連接關鍵詞的實用化可搜索加密方案

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

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

0 概述

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

為了更好地解決海量數據的安全存儲與檢索問題,可搜索加密技術[1]應運而生,其目標是在不影響數據檢索功能的前提下,保護用戶外包數據的安全性與查詢隱私。可搜索加密技術的基本應用過程為:用戶加密自己的數據并上傳到遠程服務器,在需要檢索文件時提交其關鍵詞的陷門給服務器,隨后服務器使用陷門檢索到密文并返回給用戶,整個過程中服務器將不會獲取關于密文與其關鍵詞的任何信息。

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

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

1 基礎知識

1.1 雙線性映射

設p為素數,令G1、G2是p階循環群,若映射e:G1×G1→G2滿足以下性質,則稱e為一個雙線性映射:

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

3)可計算性(computable):對于任意的P,Q∈G1,存在多項式時間算法計算e(P,Q)。

1.2 方案的困難性假設

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

2 基于連接關鍵詞的可搜索加密方案

2.1 系統描述

圖1 可搜索加密方案應用過程

2.2 算法定義

基于連接關鍵詞的可搜索加密方案由以下6個多項式時間算法組成:

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

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

2.3 安全性模型

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

階段1適應性詢問階段:

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

猜測攻擊者輸出b′∈{0,1},當b′=b時,攻擊者獲勝。

本文定義攻擊者A在攻擊基于連接關鍵詞的可搜索加密模型時的優勢為:

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

3 算法構造

(1)

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

(2)

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

式(1)的數學證明如下:

如果WIi=Ωi,有:

式(2)的數學證明如下,有:

如果WIi=Ωi,有:

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

4 安全性分析

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

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

H1查詢敵手A向隨機預言機H1發出查詢請求,為了響應這個請求,B初始化一個空的三元組列表H1,當A向隨機預言機H1請求Wi∈{0,1}*時,B按以下規則做出回應:

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

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

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

H2查詢敵手A向隨機預言機H2發出查詢請求,為了響應這個請求,B需要初始化一個空的二元組列表H2,當A向隨機預言機H2請求gi∈{0,1}*時,B按以下規則做出回應:

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

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

H3查詢敵手A向隨機預言機H3發出查詢請求。為了響應這個請求,B初始化一個空的多元組列表H3,當A向隨機預言機H3發送請求Mi‖Bi,1‖Bi,2‖…‖Bi,m∈{0,1}*和ski∈κ時,B按以下規則做出回應:

1)如果查詢Mi‖Bi,1‖Bi,2‖…‖Bi,m和ski已經出現在H2表中,B回復H3(Mi‖Bi,1‖Bi,2‖…‖Bi,m,ski)=roi。

表1 Hash算法說明

挑戰者與攻擊者之間的攻擊游戲如下:

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

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

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

(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查詢:當A發起Qi=(Ii,1,Ii,2,…,Ii,ti,Ωi,1,Ωi,2,…,Ωi.ti)查詢解密陷門,B進行如下操作:

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

(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)。

挑戰者A輸出2個文件D0=(M0,H0)和D1=(M1,H1),并發送給B。B進行如下操作:

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

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

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

最終,A會給出判斷結果,表明B給出的挑戰C是否為D0或D1的密文。

5 應用方案

根據算法過程,本文實現了服務器與客戶端一對多的交互型可搜索加密云存儲系統[14],將可搜索加密方案劃分到服務器和客戶端2個部分,通過交互實現文件的存取和共享[15]。

5.1 控制臺算法的分析與實現

為進行算法效率測試,需實現一個控制臺算法,從而避免在真實場景下網絡與文件的讀寫影響算法的實際運行時間。本文借助Java的JPBC庫來實現控制臺算法[16],工具函數的說明如下:

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

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

參數設置:有限域的階數為512比特位,群的階數為128比特位。

控制臺算法運行結果如圖2所示。其中,H2=S說明STrapdoor匹配成功,origin_sk=get_sk表明DTrapdoor匹配成功并解密出正確密鑰。

圖2 控制臺算法運行結果

5.2 服務器-客戶端的分析與實現

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

圖3 服務器交互界面

圖4 客戶端工具界面

方案步驟說明如下:

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

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

3)本地索引:算法本身能夠實現連接查詢,但是需要用戶自行記憶關鍵詞在文件中的位置,這對用戶不夠友好,因此,通過生成本地關鍵詞索引,實現用戶本地的預查詢,這樣可以避免記憶關鍵詞位置,同時也可以實現否定查詢。

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

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

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

7)文件存取等步驟的簡化:用戶查詢到的文件和公鑰一般是多個,本文方案能夠對多個文件同時進行解密而非逐個解密,對公鑰集合進行統一上傳而無需逐個上傳。

5.3 效率分析

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

表2 各加密方案的效率對比

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

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

圖5 2種方案密文生成效率對比

圖6 2種方案陷門生成效率對比

圖7 2種方案單個文件匹配效率對比

6 結束語

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