云環境下基于編碼樹的新型保序加密算法

紀 鵬,呂旭明,蘇善婷,陳 碩,李東民,劉 賽

(1.國網遼寧省電力有限公司,沈陽110000; 2.南京航空航天大學 計算機科學與技術學院,南京 211106;3.南瑞集團(國網電力科學研究院)有限公司,南京 210000)

0 概述

隨著互聯網普及率不斷提升,網絡用戶信息量呈爆炸式增長,計算機領域進入大數據時代[1]。為適應計算量指數級增長,計算模式從單機處理模式發展為分布式任務處理模式,再到目前的云計算模式。用戶無需關心云平臺內部如何工作,通過管理服務器將計算或存儲任務分派給集群計算機進行處理,最大限度地利用資源[2]。

云計算帶來諸多便利和優勢的同時在安全方面也帶來新的挑戰。數據上傳到云服務器后便脫離用戶的物理控制,云存儲服務器被不法分子攻破會導致大規模用戶隱私數據泄露,這樣的惡性事件帶來的后果十分嚴重。盡管云服務提供商承諾保證用戶數據安全,但當下復雜網絡環境中存在的各種木馬、蠕蟲、惡意軟件、病毒以及各種先進的竊密手段讓人防不勝防。因此,云環境下的數據安全以及隱私保護問題成為制約其推廣的主要瓶頸,通過技術手段提升數據安全勢在必行。

數據加密是一種保護用戶數據的常用方法,用戶在本地對數據進行加密,將密文存儲在云平臺進行托管。即便云存儲服務器發生數據泄露,被竊取的僅僅是密文數據,在沒有密鑰的情況下無法獲取真實數據[3]。同時,數據加密技術可防止第三方不可信云服務器管理員利用技術手段對用戶數據進行竊取,為用戶數據的安全提供有力保障。

采用加密手段保護數據的限制在于,解密過程必須通過被信任的第三方應用[4]。傳統加密算法多數不支持對密文的運算操作:1)加密數據難以通過傳統的信息檢索方式實現有效檢索,必須將云端大量文件傳輸回本地,逐一解密后再檢索;2)云平臺應用擴展的會受到限制,例如,用戶需要對云端的數據排序或范圍查詢,云平臺很難提供相應功能,極大削弱了云計算的應用范圍和優勢。

文獻[5]提出保序加密的基本概念,對于任意明文,若滿足x>y,則必有[x1,x2]?；诖颂攸c,對于[x1,x2]范圍內明文的查詢,可轉化為對[x1,x2]范圍內密文查詢。該加密算法可應用于不可信的云環境下,對隱私數據保護的同時對密文進行相應計算,實現密文數據范圍查詢、排序等操作,突破在云環境下的檢索瓶頸。

本文提出一種基于編碼樹的保序加密算法。該算法對明文數據進行分割并通過對稱加密算法得到明文對應的DET密文,在服務端構建滿足B樹結構的編碼樹。以明文大小作為關鍵字排列順序的依據,將關鍵字查找路徑作為最終保序密文,同時利用密文更新策略保證加密算法的高效性和可靠性。

1 相關工作

保序加密是一個廣義概念,本質是通過構造函數將明文數據轉化為密文數據。研究者基于此概念通過不同角度設計構造函數,主要包括基于超幾何分布、基于隨機均勻采樣以及基于查找樹的編碼方式3種類型。

文獻[6]提出基于超幾何分布取樣的加密構造算法,對于定義域[x1,x2]內的明文,其加密后密文分布在[y1,y2],對于密文y3=(y1+y2)/2,根據超逆幾何概率從定義域選擇明文x3與之對應。文獻[7]設計的算法與此思路類似,在密文與明文空間劃分方法及映射函數不同。文獻[8]提出一種基于非退化矩陣的保序加密方案,通過矩陣實現明文與密文間的映射,具有較高安全性。由于矩陣構造過程復雜性較高,該方法不適用云環境下海量數據加密。文獻[9]提出基于噪聲的保序加密算法,在線性加密函數基礎上添加隨機噪聲,以此提高加密安全性。文獻[10]采用基于網格對角線劃分實現保序密文生成,將每個明文數據作為坐標系中一點,通過二分搜索找出位于對角線上的點并將這些點作為密鑰,通過線型函數計算密文。文獻[11]基于近似公約數提出一種隨機數保序加密算法,該算法可保證常數加密復雜度并且能夠隱藏明文分布信息。

以上方法基于數學方法定義構造函數,缺點是可能泄露明文分布情況。攻擊者獲取密文后,采用碰撞攻擊的方式能夠實現解密。文獻[6]提出等序明文不可區分(INDistinguishability under Ordered Chosen Plaintext Attacks,IND-OCPA)的定義,這一定義規定經過保序加密后,攻擊者即使獲得2個密文也無法根據密文序關系確定明文序關系。文獻[12]提出基于二叉樹的保序編碼構造方式,將密文作為關鍵字存儲在查找樹中,存儲位置根據明文大小確定,由根節點出發到達每一個關鍵字的路徑確定數據的保序密文,這種方法生成的密文不依賴于密鑰,與傳統的加密方法有所區別,嚴格來說屬于一種編碼方法。文獻[13]采用編碼方式保序加密,不同的是在加密過程中通過惰性計算提高加密速度,插入數據時使用普通加密算法處理,對數據查詢時通過編碼方式得到保序密文。在頻繁插入操作應用場景下可顯著提高加密效率,并對明文頻率信息隱藏。文獻[14]改進了文獻[12]方法中的編碼方式,提高了加密效率同時保證IND-OCPA安全性,在此基礎上提出一種改進算法[15],基于明文頻率實現將一對一編碼規則改進為一對多編碼方式,一對多編碼指相同的明文經過加密后可被映射為不同密文,這種編碼方式優點是加密后明文頻率分布發生變化。文獻[16]在基于編碼的保序加密算法基礎上進行擴展,利用消息空間擴展以及非線性空間分割來隱藏數據的分布和頻率。文獻[17]使用同態加密對保序加密中密文生成過程進行改進,提出一種支持多種關系運算的保序加密算法。文獻[18]提出基于空間的保序加密方案,利用數據庫常用索引結構生成數據保序密文,實現對高維數據加密并支持多種不同查詢類型。

2 基于編碼樹的保序加密算法

定義1(確定性加密DET) DET是一種偽隨機轉換方式,相同明文經過轉換后所得密文內容相同,密文在恢復時根據密鑰進行逆向變換可實現還原,支持對明文數據等值匹配[19-20]。DET加密采用對稱加密實現,比如固定IV的AES-CBC模式。

定義2(保序加密OPE) OPE通過一個保持數據有序性的映射機制實現明文與密文編碼的轉化,對于保序加密算法Enc定義域內任意明文,若滿足x>y,必有OPE={KeyGen,InitState,Enc,Dec,Order}。因此對于OPE={KeyGen,InitState,Enc,Dec,Order}范圍內明文的查詢,可轉化為對OPE={KeyGen,InitState,Enc,Dec,Order}范圍內密文的查詢[21]。

定義3(保序編碼OPC) OPC能夠反映密文間大小關系,對不可信服務器是可見的,明文大小的比較可轉換為對保序編碼大小的比較。在設計保序編碼時應盡量降低與明文之間的相關性,保證不可信服務器無法通過保序編碼獲取明文數據。

2.1 保序加密算法整體框架

保序加密算法可形式化表示為一個五元組OPE={KeyGen,InitState,Enc,Dec,Order}。算法功能拆分為2部分,運行在客戶端負責保序密文的生成和運行在服務器,在用戶更新數據時對密文進行同步更新。其中,KeyGen具有隨機性,而其他元素具有確定性,Enc具有交互性,各元素具體含義如下:

1)密鑰生成:KeyGen(1k)→sk,在服務器上輸入安全參數Dec(sk,c)→v,通過密鑰生成函數生成用戶加密私鑰sk。

2)服務器初始化:Dec(sk,c)→v,在服務器通過輸入安全參數Dec(sk,c)→v,生成初始編碼樹st。

3)加密:Dec(sk,c)→v,該過程是客戶端與服務器交互過程,在客戶端輸入私鑰sk與明文v,服務器輸入原始編碼樹st,最終客戶端獲得對應密文c,客戶端將密文傳輸到服務器存儲,服務器生成新的編碼樹Dec(sk,c)→v。

4)解密:Dec(sk,c)→v,客戶端運行解密函數,輸入私鑰sk以及密文c,得到對應明文v。

5)編碼調整:Order(st,c)→e,在服務器進行編碼調整,輸入原始編碼樹st以及密文c,生成一個新的保序編碼表e。

保序加密算法通過對稱加密算法生成DET密文,根據明文數據大小關系構建編碼樹,通過明文數據在編碼樹中查找路徑生成OPC,將DET密文與OPC存儲于數據服務器中,加密流程如圖1所示。

圖1 保序加密流程

2.2 基于編碼樹的OPC生成策略

定義4(編碼樹OPEm) OPEm結構類似于m階B樹,節點的關鍵字為用戶數據DET密文,圖2給出一個OPE4實例。

圖2 編碼樹結構示意圖

編碼樹具體結構如下:

1)根節點至少包含2個子節點,除非編碼樹僅包含一個關鍵字。

2)每個非根節點指向子節點的指針個數取值范圍為[m/2,m],關鍵字個數取值范圍為[m/2-1,m-1]。

3)包含n個關鍵字的節點組織形式為(P0,V1,P1,V2,…,Vn,Pn)。其中,V1、V2、V3關鍵字滿足V1對應的明文數據小于V2對應的明文數據,P1為指向該節點子樹的指針,子樹中所有節點關鍵字所對應明文數據大于V1對應的明文數據并且小于V2對應的明文數據。

在圖2中,每個節點中關鍵字為DET密文(受限于圖片大小僅展示密文部分內容),方框內數字為明文數據,實際明文并不出現在編碼樹中,此處僅為形象說明。

對于一個OPEm定義如下編碼規則:

1)每個非葉子節點指針依次編碼(0,1,…,m)。

2)節點內部關鍵字依次編碼(0,1,…,m-1)。

3)編碼二進制表示,每個編碼長度len=lbm。

每個關鍵字編碼過程可轉化為在編碼樹中查找一個關鍵字的過程。從根節點出發向下查找關鍵字,如果關鍵字位于節點內,則將關鍵字編碼按位串聯,否則將使用到的指針編碼按位串聯,直到查找到關鍵字所在節點[22]。

對于高度為H的編碼樹,設定其編碼長度為L=H×len。編碼樹第h層節點(根節點為第1層節點,葉子節點為第H層節點)中關鍵字實際編碼code長度為可通過式(1)計算:

|code|=h×len,1≤h≤H

(1)

在實際編碼尾部用1將編碼長度填充至L,關鍵字OPE編碼格式為OPC=(code[11…1])。對于圖2所示編碼樹,樹的高度為3,對應編碼長度為6。按照上文定義的編碼標準對明文進行編碼結果如表1所示。

表1 編碼結果

最終保序密文為OPC對應的十進制形式,從表1可看出,基于編碼樹生成的OPC與明文數據之間沒有任何相關性,因此不會泄露任何明文信息,同時OPC的大小能夠準確反映明文數值間大小關系。

2.3 保序密文更新規則

在節點中插入關鍵字后,若該節點內關鍵字數量超過m-1會引起節點分裂。因此,在討論插入數據時編碼更新方案分2種情況:未發生節點分裂和發生節點分裂。

1)未發生節點分裂

對于未發生節點分裂情況編碼更新較為簡單,新增關鍵字編碼通過位于之前的關鍵字編碼加1,在之后的關鍵字通過在原編碼基礎上加1得到。假設關鍵字節點位于編碼樹第h層,并在實際編碼后補充len×h個1,對應編碼更新規則如式(2)所示。

code′=code+1

(2)

2)發生節點分裂

對于分裂過程中新生成的節點中所有關鍵字,由于分裂位置發生在一個節點的m/2處,編碼路徑對應增加m/2,并在編碼后填充(L-len×h)個1,編碼更新規則如式(3)所示。

(3)

對于分裂過程中插入父節點的關鍵字,將原關鍵字編碼最后len位置為1,其他編碼保持不變,更新后該關鍵字將位于h-1層節點,在編碼后填充(L-len×h+len)個1,編碼更新規則如式(4)所示。

code′=code<

(4)

分裂后如果生成新的根節點,則樹中所有關鍵字右移一個編碼長度len,編碼更新規則如式(5)所示。

code″=code′>>len

(5)

新生成的根節點只包含左右2個子樹,根節點左子樹所有關鍵字在編碼頭部串聯00,根節點右子樹所有關鍵字在編碼頭部串聯01,以彌補右移后空缺的編碼位。

圖3給出在編碼樹中插入關鍵字后造成節點分裂并生成新根節點的實例,為簡潔表示圖中編碼樹中關鍵字直接用明文代替。在構建保序編碼時選取m=4,L=6,對應的編碼更新情況如表2所示。

圖3 編碼樹更新實例

關鍵字更新前更新后編碼層數編碼層數2400[1111]=1510000[11]=324601[1111]=3110001[11]=725310[1111]=4710100[11]=192150000[11]=32000000=03180001[11]=72000001=13450100[11]=192000100=43471000[11]=352001000=83481001[11]=392001001=93491011[11]=47200[1111]=151901100[11]=482010100=20350——010000=163

3 實驗結果與分析

3.1 安全性分析

等序明文不可區分是保序加密理想的安全狀態,規定對于2個序關系相同的明文,攻擊者無法區分加密后密文的序關系。

定義5(IND-OCPA博弈) 對于一個客戶端C以及攻擊者Adv有如下的博弈過程:

1)C通過密鑰生成函數KeyGen(1k)→sk生成一個密鑰sk,并選擇一個隨機位b。

2)C與Adv進行多輪博弈,每輪博弈過程中攻擊者進行自適應調整,第i輪博弈過程如下:

(1)Adv向客戶端C發送2個明文m/2-1。

(2)C將明文m/2-1與密鑰sk作為輸入,在服務器Sev中進行保序加密,在此過程中Adv通過監視Sev可獲得加密結果。

3)攻擊者輸出一個m/2-1,作為b的猜測。

在多輪博弈過程中輸入的明文序列m/2-1與m/2-1具有相同的序關系(對于所有的m/2-1,滿足m/2-1)。如果攻擊者猜測的結果m/2-1,則認為攻擊者取得勝利。

攻擊者向客戶端輸入明文序列m/2-1以及m/2-1,通過服務器獲取信息。保序加密使用對稱加密算法生成DET密文,對于相同明文生成密文信息相同。接下來論證在客戶端加密V明文序列和W明文序列時攻擊者所能夠獲得的信息相同[23]。

初始階段服務器不存儲任何信息,之后的每次數據加密,由于明文序列V與W具有相同序關系,密文會被插入到編碼樹中相同位置,所得保序密文也相同,這種情況下攻擊者仍然無法根據密文區分出對應的明文。因此,本文算法滿足IND-OCPA安全定義。

3.2 實驗測試

本文實驗硬件平臺包括1臺客戶端、1臺管理服務器、2臺數據服務器,具體配置為:

客戶端向用戶提供登錄界面,實現與管理服務器建立連接并請求服務,機器配置為:Intel Core 4核處理器,3.0 GHz、4 GB RAM、Window 7操作系統、JDK1.7。

管理服務器通過開源云計算框架OpenStack管理后端數據服務器,通過webservice為用戶提供服務,機器配置為:Intel Core4核處理器,3.2 GHz、16 GB RAM、Ubuntu 14操作系統。

數據服務器配置為:8個AMD Opteron8431 6核處理器,2.4 GHz、64 GB RAM、Ubuntu 14操作系統、MySql 5.6。

編碼樹的階m是影響性質的一個重要參數,影響每個節點中關鍵字以及子節點指針的數量[24]。一般選取m為2的冪,保證每個編碼長度len能取到整數?？紤]一次讀取到內存數據量不宜過大,m分別取16、32,對應的len分別為4和5。

根據上文介紹保序加密流程可知,加密過程包括根據明文大小判斷數據位于編碼樹中位置以及編碼調整步數。對于n個關鍵字,生成平衡二叉樹的高度h=lbn,對應計算編碼時間復雜度為m/2-1。對于m階B樹,其高度h取值范圍為[logmn,logm/2((n+1)/2)+1],對于最壞的情況樹高h=logm/2((n+1)/2)+1(樹中每個節點包含m/2-1個關鍵字)。此時計算編碼時間復雜度為O(logm/2(n))。采用m階編碼樹理論上可將時間縮短為原來的1/logm/22。

數據插入后需進行編碼調整。對于二叉平衡樹進行保序編碼時,檢查過程是從插入數據節點位置開始向上回溯,檢查過程時間復雜度為O(lbn)。對于B樹進行編碼,檢查判斷插入數據后節點關鍵字是否超過m-1,檢查時間復雜度為O(logm/2(n))。使用2種結構進行編碼更新的時間復雜度均為O(1)。

測試數據集包含5 000條數值型數據,其集合R={r1,r2,…,r5 000},每條數據均通過隨機函數生成,無統一序關系,分別使用mOPE[12]、OPEBCT16(m設置為16)與OPEBCT32(m設置為32)對數據進行加密。上述3種方法運行時間進行統計,包括加密總時間、編碼生成時間以及編碼更新時間,如圖4～圖6所示。

圖4 加密總時間隨插入記錄數量變化趨勢

圖5 保序編碼生成時間隨插入記錄數量變化趨勢

圖6 編碼更新時間隨插入記錄數量變化趨勢

從圖4可以看出,使用mOPE、OPEBCT16與OPEBCT32加密5 000條數據所花費總時間分別為11 948 ms、3 859 ms、3 214 ms,加密時間分別為原來的32.3%(約等于1/lb 8)與 26.9%(約等于1/lb 16)。

從圖5和圖6可以看出,在編碼生成過程與編碼更新過程中,使用OPEBCT方法可縮短加密時間,但時間縮短原因是不同的。前者由于B樹高度降低使得客戶端與服務端通信次數減少,后者由于編碼更新規則的設置減少服務器內部計算開銷。

表3給出3種方法各步驟平均運行時間,其中查找路徑長度根據客戶端與服務端通信次數確定。從表3數據可看出,本文方法減少加密過程中客戶端與服務端通信次數,提高插入數據時保序密文生成時間,與上文分析結果一致。

表3 3種方法平均耗時對比

綜上所述,使用編碼樹替代二叉平衡樹進行保序編碼的生成工作,能夠有效減少加密過程所耗費時間,同時隨著編碼樹階m的增大,加密時間呈縮小趨勢。考慮計算機內存一次可計算數據量將m設置為32。

4 結束語

本文提出一種基于編碼樹的保序加密算法,該算法對明文數據分割并通過對稱加密算法得到明文對應的DET密文,在服務端構建滿足B樹結構的編碼樹,以明文大小為關鍵字排列順序提供依據,將關鍵字查找路徑作為最終保序密文。針對保序密文的可變性,提出了保序密文更新策略,當用戶插入新數據時根據更新規則實現密文同步變換。測試結果表明,本文算法具有較高的加密效率。下一步將圍繞保序加密算法應用場景,根據密文保持明文序關系的特性,以支持多種密文運算。