基于SkipList的ORE算法的改進(jìn)與實(shí)現(xiàn)

姚李昊升，楊立新，張于潔，蔣 欣

（1.長(zhǎng)江大學(xué) 電子信息學(xué)院，湖北 荊州 434020；2.湖北省科技信息研究院，武漢 430071；3.武漢理工大學(xué) 計(jì)算機(jī)與人工智能學(xué)院，武漢 430070）

引言

現(xiàn)有的云存儲(chǔ)服務(wù)為用戶提供了方便的數(shù)據(jù)存儲(chǔ)、管理和共享服務(wù)，云計(jì)算技術(shù)開(kāi)放式存儲(chǔ)及應(yīng)用為用戶帶來(lái)便捷[1]。同時(shí)，云存儲(chǔ)服務(wù)也逐漸面臨著越來(lái)越多的安全問(wèn)題。云上層出不窮的數(shù)據(jù)泄露問(wèn)題，各種各樣的黑客攻擊事件，給云存儲(chǔ)服務(wù)帶來(lái)了前所未有的挑戰(zhàn)。用戶認(rèn)為云服務(wù)器通常是不完全可信的，因此存儲(chǔ)在云上的數(shù)據(jù)有必要通過(guò)加密進(jìn)行保護(hù)，然而在對(duì)數(shù)據(jù)進(jìn)行加密的同時(shí)，使得一些在明文空間上的函數(shù)計(jì)算不再適用于密文空間，例如區(qū)間查詢。

區(qū)間查詢[2]-[3]是對(duì)數(shù)據(jù)進(jìn)行查詢的主要方式之一。在明文區(qū)間查詢中，用戶向服務(wù)器提供查詢區(qū)間，然后服務(wù)器將關(guān)鍵字在查詢區(qū)間內(nèi)的所有數(shù)據(jù)反饋給用戶。但是在密文區(qū)間查詢中，為保證敏感數(shù)據(jù)的機(jī)密性，用戶需要將加密后的查詢區(qū)間陷門發(fā)送給服務(wù)器，服務(wù)器運(yùn)行查詢算法后將符合條件的密文反饋給用戶，由私鑰解密后得到相應(yīng)的明文數(shù)據(jù)。由于查詢需要在密文狀態(tài)下進(jìn)行，因此如何在保證安全性的同時(shí)實(shí)現(xiàn)高效查詢是目前主要難點(diǎn)。

早期國(guó)內(nèi)外相關(guān)學(xué)者在密文區(qū)間查詢上研究保序加密方案（Order Preserving Encryption，OPE）對(duì)關(guān)鍵字查詢的可行性。由于該方案的明文和密文具有相同的一致性順序關(guān)系，因此容易遭受統(tǒng)計(jì)性攻擊，導(dǎo)致方案的安全性較低。已有文獻(xiàn)[4]構(gòu)造了一種非線性的OPE方案，該方案不需要已知原始明文的分布規(guī)律、數(shù)據(jù)量的大小等信息，在安全性上面得到了很大的加強(qiáng)。但是此方案基于的假設(shè)是數(shù)據(jù)特征會(huì)隨著時(shí)間的變化而變化，因此不具有實(shí)用性。在OPE 方案的基礎(chǔ)上，也有文獻(xiàn)[5]提出了順序揭示加密方案（Order Revealing Encryption，ORE）。ORE方案的構(gòu)造依賴于多重線性映射函數(shù)，所支持的區(qū)間查詢數(shù)據(jù)類型不僅僅只包括數(shù)值型數(shù)據(jù)，還包括其他類型的數(shù)據(jù)。Lewi等人在傳統(tǒng)ORE方案的基礎(chǔ)上提出了一種能夠抵抗推斷攻擊的改進(jìn)的ORE方案（Left-Right Order Revealing Encryption，LRORE）[6]，該方案可以保證泄露更少的順序信息，由此更好地保護(hù)數(shù)據(jù)的安全，但此方案的數(shù)據(jù)組織結(jié)構(gòu)采用順序存儲(chǔ)，對(duì)于數(shù)據(jù)的插入和刪除操作，會(huì)造成大量的數(shù)據(jù)移動(dòng)，產(chǎn)生很大的時(shí)間開(kāi)銷。

針對(duì)LRORE方案數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的不足，提出一種基于跳躍表（SkipList）的存儲(chǔ)結(jié)構(gòu)的順序揭示加密方案（SL-ORE），在保證安全性的前提下，提升了數(shù)據(jù)插入和刪除的效率，使其能夠保持和密文查詢時(shí)相同的時(shí)間復(fù)雜度。

1 相關(guān)研究

常見(jiàn)的密文區(qū)間查詢主要有以下幾種方案：

1.1 OPE方案

云服務(wù)器可以根據(jù)密文的順序信息來(lái)得到明文順序信息，因此，OPE方案可以保證涉及順序信息的查詢操作可以在密文空間高效進(jìn)行。當(dāng)進(jìn)行區(qū)間查詢時(shí)，用戶只需要提供查詢區(qū)間兩個(gè)端點(diǎn)的密文給云服務(wù)器。隨后，云服務(wù)器根據(jù)用戶提供區(qū)間端點(diǎn)的加密密文與原有數(shù)據(jù)庫(kù)的密文進(jìn)行比較。最后，云服務(wù)器返回給用戶符合查詢要求的密文數(shù)據(jù)，用戶解密即可。

OPE 方案的最佳理想安全性（Indistinguish Ability Under Ordered Chosen Plaintext Attack，IND-OCPA），最早是由Boldyreva等人[3]提出的，該安全性是保序加密方案的最高理想安全性。

隨后Boldyreva等人提出了一種利用隨機(jī)保序函數(shù)和超幾何分布設(shè)計(jì)的可證安全的OPE方案。該方案保證了安全性，即使攻擊者得到全部密文，除了密文的順序以外，就再也得不到其它任何有用的信息。

1.2 ORE方案

有文獻(xiàn)指出Boldyreva的OPE方案會(huì)泄露明文至少一半的比特信息[7]-[8]，為此Boneh[9]等人在原有OPE方案的基礎(chǔ)上提出了順序揭示加密ORE方案，該方案與保序加密不同，ORE方案是依據(jù)一個(gè)公開(kāi)的比較函數(shù)來(lái)決定兩個(gè)相應(yīng)明文的大小，而不是直接比較密文之間的數(shù)值大小。ORE方案與OPE方案相比較，Boneh等人提出的ORE方案能達(dá)到最佳理想安全性IND-OCPA。隨后，Chenette等人[10]使用偽隨機(jī)函數(shù)構(gòu)造出了一種新的ORE方案。

上述方法具有很高的檢索效率，因?yàn)榉桨钢杏玫搅藗坞S機(jī)函數(shù)。但是，該方案仍然不能達(dá)到理想安全性，因?yàn)樗惴ㄐ孤读瞬煌瑪?shù)據(jù)的第一個(gè)不相同比特位。

為了減少Chenette等人方案中信息的泄露問(wèn)題，Cash等人[11]構(gòu)造出了一個(gè)性質(zhì)保留哈希函數(shù)，并且依據(jù)雙線性對(duì)的理論，構(gòu)造出了一個(gè)新的ORE方案，該方案雖然很好地避免信息泄露問(wèn)題。但是，相對(duì)于只使用對(duì)稱簡(jiǎn)單原語(yǔ)的加密方案而言，Cash等人的方案在實(shí)際場(chǎng)景中查詢效率并不高。Furukawa等人[12]構(gòu)造第一個(gè)有陷門的ORE方案，該方案基本思想是使用兩個(gè)加密密文比較明文大小時(shí)，必須知道一方標(biāo)簽，這一標(biāo)簽是ORE方案中的陷門。在該方案中將密文分成密文c 和標(biāo)簽token 兩部分。其中token 為比較標(biāo)簽保存在客戶端中。當(dāng)用戶進(jìn)行區(qū)間查詢時(shí)，只需上傳查詢區(qū)間端點(diǎn)的密文以及對(duì)應(yīng)的比較標(biāo)簽。例如，當(dāng)查詢區(qū)間[a ,b] 時(shí)，用戶需向服務(wù)器提交( ca,tokena)和( cb,tokenb)，服務(wù)器可以進(jìn)行比較查詢，返回相應(yīng)密文，用戶解密得到所需的查詢結(jié)果。

1.3 LRORE方案

在Furukawa等人所提出的ORE方案中，當(dāng)查詢區(qū)間較多時(shí)，會(huì)造成數(shù)據(jù)順序信息的大規(guī)模泄露。對(duì)此，Lewi等人構(gòu)造新的順序揭示加密LRORE方案，該方案的加密過(guò)程中包含兩種加密算法，其中左加密算法加密明文之后得到左密文，右加密算法加密明文之后得到右密文，云服務(wù)器中存儲(chǔ)的只是右密文，其中右密文是語(yǔ)義安全的。當(dāng)數(shù)據(jù)使用者進(jìn)行區(qū)間查詢時(shí)，只需要將左加密算法生成的左密文區(qū)間端點(diǎn)對(duì)應(yīng)的密文值發(fā)送給云服務(wù)器，通過(guò)比較函數(shù)進(jìn)行左明文和右明文的大小比較之后，將查詢結(jié)果返回給用戶。這樣可以保證泄露更少的順序信息，由此更好地保護(hù)數(shù)據(jù)的安全性。

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

常見(jiàn)的索引分為線性表索引，順序表索引，鏈表索引、散列索引和樹(shù)形索引五類。由于線性搜索的方法如今無(wú)法滿足現(xiàn)有的用戶對(duì)于數(shù)據(jù)搜索的要求，雖然樹(shù)形索引具有擴(kuò)展性好，查詢和更新效率高等優(yōu)點(diǎn)，但是由于在進(jìn)行數(shù)據(jù)的插入和刪除操作時(shí)，需要不斷進(jìn)行調(diào)整樹(shù)的結(jié)構(gòu)，增加了性能開(kāi)銷。而鏈表索引的代表SkipList結(jié)構(gòu)在區(qū)間查找效率更高，不僅能保持對(duì)數(shù)級(jí)別的數(shù)據(jù)查詢效率，當(dāng)進(jìn)行數(shù)據(jù)插入和刪除時(shí)，同樣也能保持高效的性能，而且適用于大規(guī)模數(shù)據(jù)的并發(fā)訪問(wèn)，多個(gè)線程可以安全地并發(fā)執(zhí)行插入、刪除、更新和查詢操作。與其他有鎖機(jī)制的數(shù)據(jù)結(jié)構(gòu)在巨大的壓力下相比有優(yōu)勢(shì)。[13]

SkipList結(jié)構(gòu)如圖1所示，是Willipam Pugh等人[14]提出的一種替代平衡樹(shù)的概率性數(shù)據(jù)結(jié)構(gòu)，但是與平衡樹(shù)（如紅黑樹(shù)）不相同的是，跳表實(shí)現(xiàn)是基于一種隨機(jī)化的算法。其形式表現(xiàn)為有序的鏈表，其與普通鏈表最大的區(qū)別在于：各節(jié)點(diǎn)之間有一些附加的并行指針相連。每一個(gè)插入到SkipList的key 首先會(huì)被插入到最底層的鏈表中，接著存儲(chǔ)這個(gè)key 的節(jié)點(diǎn)，會(huì)以50%的概率將自己發(fā)布到上層中。SkipList的查詢、插入、刪除操作都能達(dá)到很好的性能。SkipList滿足的基本特征如下：

（1）一個(gè)跳表由兩層或者兩層以上組成。

（2）跳表的第一層包含所有的元素。

（3）每一層都是一個(gè)有序的鏈表。

（4）如果元素x 出現(xiàn)在第i 層，則所有比i 小的層都包含x。

（5）第i 層的元素通過(guò)一個(gè)down 指針指向下一層擁有相同值的元素。

（6）top 指針指向最高層的第一個(gè)元素。

2.1 SkipList查詢

例如在圖1中要查詢key 為19的結(jié)點(diǎn)，從head出發(fā)，從高到低的level進(jìn)行查找，先索引到9這個(gè)結(jié)點(diǎn)，發(fā)現(xiàn)9＜19，繼續(xù)查找（然后在level==2這層），查找到21這個(gè)節(jié)點(diǎn)，由于21＞19，所以結(jié)點(diǎn)不往前走，而是level由2降低到1然后索引到17這個(gè)節(jié)點(diǎn)，由于17＜19，所以繼續(xù)往后，索引到21這個(gè)結(jié)點(diǎn)，發(fā)現(xiàn)21＞19，所以level由1降低到0在結(jié)點(diǎn)17上，level==0索引到19，查找完畢。如果在level==0這層沒(méi)有查找到，那么說(shuō)明不存在key為19的節(jié)點(diǎn)，則查找失敗。

圖1 SkipList結(jié)構(gòu)

2.2 SkipList插入

插入節(jié)點(diǎn)的關(guān)鍵就是找到合適的插入位置，即從所有小于待插入節(jié)點(diǎn)key 值的節(jié)點(diǎn)中，找出最大的那個(gè)節(jié)點(diǎn)即可。例如在圖1 中要插入key 為17 的結(jié)點(diǎn)，先需要查找到12，由于12＜17，而12 的下一個(gè)結(jié)點(diǎn)19＞17，因而滿足條件，創(chuàng)建新結(jié)點(diǎn)，并且產(chǎn)生一個(gè)在1～MAX_LEVEL 之間的隨機(jī)level 值作為該結(jié)點(diǎn)的level，再調(diào)整指針指向。

2.3 SkipList刪除

首先查找到指定的結(jié)點(diǎn)，若沒(méi)找到則返回，反之調(diào)整指針指向，釋放結(jié)點(diǎn)空間。本文將優(yōu)化原有方案的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，將SkipList 應(yīng)用到LRORE 方案中，并提出SL-ORE 方案，通過(guò)分析得出該方案相比原有方案的具有較大的性能提升，同時(shí)它又保持了原有LRORE 方案抵抗統(tǒng)計(jì)攻擊的安全優(yōu)勢(shì)。

3 SL-ORE方案的設(shè)計(jì)與實(shí)現(xiàn)

3.1 SL-ORE方案概述

SL-ORE方案主要包括如下兩個(gè)過(guò)程：

3.1.1 初始化過(guò)程：數(shù)據(jù)擁有者將明文數(shù)據(jù)D=( x1,x2,…,xm)組織成SkipList結(jié)構(gòu)，再利用生成的密鑰對(duì)明文SkipList中的數(shù)據(jù)進(jìn)行加密，這樣就可以獲得密文SkipList。服務(wù)器對(duì)該密文SkipList進(jìn)行存儲(chǔ)（服務(wù)器僅存儲(chǔ)右密文），同時(shí)記錄初始密文結(jié)構(gòu)狀態(tài)st。

3.1.2 區(qū)間查詢和更新過(guò)程：數(shù)據(jù)使用者將待查詢明文通過(guò)密鑰sk 加密后得到的左密文發(fā)送給服務(wù)器，比較函數(shù)Compare 對(duì)當(dāng)前狀態(tài)的密文SkipList進(jìn)行跳躍查找（形如二分查找），比較對(duì)象是接收到的左密文和Skip-List中存儲(chǔ)的右密文，然后返回查詢結(jié)果給客戶端，最后更新服務(wù)器狀態(tài)st。

3.2 SL-ORE方案實(shí)現(xiàn)

本文提出的改進(jìn)方案可以描述成一個(gè)多元組算法如下所示：

(SLRQ.Setup,SLR Q.Range,SLRQ.Insert,SLRQ.Del ete)

3.2.1 SLRQ.Setup( λ,D )初始化算法：

（1）Client( λ,D )→( sk,ct )，數(shù)據(jù)擁有者以安全參數(shù)λ 作為輸入，輸出一個(gè)密鑰LRORE.Set( λ) →sk，然后把明文數(shù)據(jù)D 組織成SkipList后，對(duì)于每個(gè)元素x ∈D 通過(guò)sk 加密生成右密文ct1。

ct1←LRORE.EncryptR( sk,x )，最后將密文SkipList 發(fā)送給服務(wù)器，如圖2 初始化過(guò)程所示，其中原始明文為x，加密后的右密文為。

（2）Server( st )→st，服務(wù)器在接收客戶端發(fā)送給它的密文SkipList后，輸出一個(gè)初始化狀態(tài)st。

3.2.2 SLRQ.Range( sk,q,st )區(qū)間查詢算法：

（1）Client( sk,q=( x,y ))→t，數(shù)據(jù)使用者輸入一個(gè)查詢q=( x,y )，通過(guò)密鑰sk 加密后生成令牌t。

t=( Encr yptL( sk,x ),EncryptR( sk,y ))。之后發(fā)送給服務(wù)器。

（2）Server ( st,t )→R，服務(wù)器根據(jù)收到的令牌t=( ctx,cty)，通過(guò)比較函數(shù)Compare 對(duì)狀態(tài)為st 密文SkipList進(jìn)行搜索，找到最小值和最大值，依次讀取最小值和最大值之間的密文值，并將這些值作為結(jié)果返回給數(shù)據(jù)使用者R。

（3）Cli ent( sk,R )→S，數(shù)據(jù)使用者將收到的返回結(jié)果R 通過(guò)sk 進(jìn)行解密得到對(duì)應(yīng)的明文。

3.2.3 SL RQ.Insert( sk,q,st )插入算法：

（1）Clie nt( sk,q=x )→t，數(shù)據(jù)使用者將待插入的值x 通過(guò)密鑰sk 加密后生成令牌t。

t=( EncryptL( sk,x ),EncryptR( sk,x ))，發(fā)送給服務(wù)器。

（2）Server( st,t )→st，服務(wù)器收到令牌t=( ct1,ct2)（其中ct1,ct2分別表示左密文和右密文）之后，通過(guò)比較函數(shù)Compare( ct3,·) 對(duì)當(dāng)前狀態(tài)為st 的密文SkipList進(jìn)行搜索得到正確的插入位置，插入完成之后更新服務(wù)器中當(dāng)前的密文狀態(tài)st 。

3.2.4 SLRQ.Delete( sk,q,st )刪除算法：

（1）Client( sk,q=x )→t，數(shù)據(jù)使用者利用密鑰對(duì)要?jiǎng)h除的值進(jìn)行加密，得到令牌t，

t=( EncryptL( sk,x ))，后發(fā)送給服務(wù)器。

（2）Server( st,t )→st'，接收到令牌之后，服務(wù)器利用比較函數(shù)Compare( ct1,·) 對(duì)當(dāng)前狀態(tài)為st 的SkipList進(jìn)行搜索，找到ct2t 的位置，刪除之后更新服務(wù)器的狀態(tài)st'。

3.3 SL-ORE查詢過(guò)程

比較函數(shù)Compare 通過(guò)接收到客戶端發(fā)送的左密文與服務(wù)器存儲(chǔ)的右密文進(jìn)行比較，在密文SkipList中確定檢索區(qū)間對(duì)應(yīng)的最小和最大密文值，然后得到其中連續(xù)的密文結(jié)果R={1 2} ，服務(wù)器將查詢結(jié)果返回客戶端進(jìn)行解密得到原始明文S，如圖3所示。

3.4 0SL-ORE插入過(guò)程

圖4 插入過(guò)程圖

3.5 SL-ORE刪除過(guò)程

設(shè)定服務(wù)器中存儲(chǔ)的密文SkipList的初始狀態(tài)為st。如圖2所示，客戶端待刪除的值q=51，服務(wù)器接收客戶端發(fā)送過(guò)來(lái)的密文值，其中代表左密文，比較函數(shù)Compare 將與當(dāng)前狀態(tài)為st 的密文SkipList進(jìn)行比較，找到對(duì)應(yīng)的正確右密文進(jìn)行刪除并更新此時(shí)的密文狀態(tài)為st' ，如圖5所示。

圖5 刪除過(guò)程圖

4 安全與性能分析

4.1 性能分析

本文提出的基于SkipList結(jié)構(gòu)的SL-ORE改進(jìn)方案同Lewi等人的LRORE方案進(jìn)行了性能的分析比較，在查找過(guò)程中，Lewi等人順序表結(jié)構(gòu)和本文提出的SkipList 結(jié)構(gòu)擁有相同的時(shí)間復(fù)雜度；但在插入和刪除過(guò)程中，基于SkipList結(jié)構(gòu)的時(shí)間復(fù)雜度是對(duì)數(shù)級(jí)別的，具有更好的性能優(yōu)勢(shì)，同時(shí)還與傳統(tǒng)的OPE方法進(jìn)行對(duì)比分析，雖然傳統(tǒng)的OPE方案在查詢和插入刪除的時(shí)間復(fù)雜度上面和我們所提的SL-ORE方案相同，但是在那種插入、刪除頻繁的場(chǎng)景中，平衡樹(shù)需要進(jìn)行再平衡操作，這會(huì)使平衡樹(shù)的性能急劇下降，此外由于OPE方案的明文和密文具有相同的一致性順序關(guān)系，因此容易遭受統(tǒng)計(jì)性攻擊，導(dǎo)致它的安全性較低?，F(xiàn)將三種方案的查詢和插入、刪除的時(shí)間復(fù)雜度進(jìn)行對(duì)比，如表1所示：

表1 時(shí)間復(fù)雜度對(duì)比

SL-ORE方案在提高數(shù)據(jù)插入和刪除的效率方面均優(yōu)于對(duì)比方案。

4.2 安全分析

SL-ORE方案是建立在Lewi等人的LRORE方案基礎(chǔ)之上，加密算法分為左加密算法和右加密算法，對(duì)應(yīng)生成左密文和右密文，服務(wù)器存儲(chǔ)的僅僅是語(yǔ)義安全的右密文，不會(huì)受到統(tǒng)計(jì)攻擊，保留了Lewi原始方案的安全性。

5 結(jié)語(yǔ)

本文提出一種新的基于SkipList 的SL-ORE 方案，并闡述了該方案的具體實(shí)現(xiàn)過(guò)程。通過(guò)分析對(duì)比所提方案在數(shù)據(jù)的插入和刪除操作上比原有方案耗時(shí)更短，并在保留原有安全優(yōu)勢(shì)的前提下具有更好的性能優(yōu)勢(shì)。