周 雄,李陶深,2,黃汝維,2

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,南寧 530004;2.廣西高校并行與分布式計(jì)算技術(shù)重點(diǎn)實(shí)驗(yàn)室,南寧 530004)

云環(huán)境下基于隨機(jī)間隔的保序加密算法

周 雄1,李陶深1,2,黃汝維1,2

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,南寧 530004;2.廣西高校并行與分布式計(jì)算技術(shù)重點(diǎn)實(shí)驗(yàn)室,南寧 530004)

針對(duì)隱藏原始數(shù)據(jù)分布的問(wèn)題,提出一種改進(jìn)型的基于隨機(jī)間隔的保序加密算法(OPERI)。算法首先將原始數(shù)據(jù)域映射至新的數(shù)據(jù)域中以達(dá)到隱藏原始數(shù)據(jù)分布和改變數(shù)據(jù)分布概率的目的,其次通過(guò)引入隨機(jī)間隔對(duì)數(shù)據(jù)進(jìn)行加密,支持對(duì)密文數(shù)據(jù)的關(guān)系運(yùn)算。安全性分析和實(shí)驗(yàn)結(jié)果表明:OPERI算法在已有安全性基礎(chǔ)上能夠抵御統(tǒng)計(jì)型攻擊,并能高效實(shí)現(xiàn)密文關(guān)系運(yùn)算。

保序加密;隱私保護(hù);云計(jì)算;統(tǒng)計(jì)型攻擊

隨著云計(jì)算的快速發(fā)展,人們?cè)絹?lái)越關(guān)注隱私安全問(wèn)題。目前解決用戶(hù)隱私安全問(wèn)題的常用方法是采用加密技術(shù)將數(shù)據(jù)加密后再存儲(chǔ)到云端,但是現(xiàn)有的大多數(shù)加密方案都不支持對(duì)密文的運(yùn)算,如果對(duì)加密數(shù)據(jù)進(jìn)行檢索、排序,勢(shì)必會(huì)嚴(yán)重妨礙云服務(wù)提供商對(duì)數(shù)據(jù)的管理,從而削弱了云計(jì)算所帶來(lái)的優(yōu)勢(shì)。文獻(xiàn)[1]對(duì)各類(lèi)算法進(jìn)行分析研究,就現(xiàn)有保序加密算法(Order Preserving Encryption,OPE)不能同時(shí)滿(mǎn)足高效性和安全性需求的問(wèn)題,提出一種基于隨機(jī)樹(shù)的保序加密算法OPEART,通過(guò)引入隨機(jī)性實(shí)現(xiàn)了對(duì)數(shù)據(jù)的加密。雖然OPEART算法較好地解決了密文上的關(guān)系運(yùn)算問(wèn)題,但是它不能隱藏原始數(shù)據(jù)分布,加密后的密文與原始數(shù)據(jù)呈現(xiàn)相同的數(shù)據(jù)分布,因此不能很好地抵擋統(tǒng)計(jì)型攻擊。

為了解決隱藏原始數(shù)據(jù)分布的問(wèn)題,筆者對(duì)OPEART算法進(jìn)行改進(jìn),提出一種基于隨機(jī)間隔的保序加密算法(OPERI)。該算法首先會(huì)通過(guò)映射函數(shù)將原始數(shù)據(jù)分布轉(zhuǎn)化為不同類(lèi)型的分布,然后通過(guò)隨機(jī)分配大小不同的間隔域?qū)崿F(xiàn)對(duì)數(shù)據(jù)的加密。

1 相關(guān)工作

目前有關(guān)保序加密方案的研究成果大致分為2類(lèi):即密文不變的保序加密方案和密文可變的保序加密方案。

1.1 密文不變的保序加密方案

該類(lèi)方案的主要思想是:同一加密算法加密同一數(shù)據(jù)得到的密文是相同的。文獻(xiàn)[2]基于多項(xiàng)式函數(shù)提出一種OPE方案,該方案利用一系列嚴(yán)格遞增的多項(xiàng)式函數(shù)來(lái)對(duì)整數(shù)進(jìn)行加密,密鑰是多項(xiàng)式函數(shù)的系數(shù),進(jìn)行多次計(jì)算可以得到最終的密文。文獻(xiàn)[3]和[4]利用加密函數(shù)enc(v)=av+b+vnoise對(duì)明文v進(jìn)行加密,利用噪聲vnoise提高其安全性?；谡郯氩檎乙约俺瑤缀畏植己拓?fù)超幾何分布相結(jié)合文獻(xiàn)[5]、[6]和[7]提出一種保序?qū)ΨQ(chēng)加密算法(OPSE),支持對(duì)加密數(shù)據(jù)的各種關(guān)系運(yùn)算。文獻(xiàn)[8]提出一種基于非退化矩陣概念的OPE方案,該方案采用矩陣?yán)碚?具有很高的安全性,但是由于構(gòu)造矩陣的過(guò)程復(fù)雜,不適于云環(huán)境下的大型的數(shù)據(jù)庫(kù)系統(tǒng)。文獻(xiàn)[9]提出一種基于網(wǎng)格對(duì)角線(xiàn)劃分原理的OPE方案,該方案首先使用二分搜索確定點(diǎn)的位置,位于對(duì)角線(xiàn)上的點(diǎn)的坐標(biāo)為加密密鑰,然后通過(guò)線(xiàn)性函數(shù)計(jì)算得到密文值。文獻(xiàn)[10]提出一種將桶劃分和樹(shù)的遍歷相結(jié)合的OPE方案,經(jīng)過(guò)多次迭代確定每個(gè)桶中包含的數(shù)據(jù)以達(dá)到安全性標(biāo)準(zhǔn)。

1.2 密文可變的保序加密方案

云計(jì)算環(huán)境下的大型數(shù)據(jù)庫(kù)系統(tǒng)需要滿(mǎn)足數(shù)據(jù)處理效率性上的需求,如檢索時(shí)間不能過(guò)長(zhǎng)、處理過(guò)程不能過(guò)于復(fù)雜;也要滿(mǎn)足安全性上的需求,如能夠抵擋選擇明文攻擊(IND-CPA)或者統(tǒng)計(jì)型攻擊(IND-SA)等。由于保序加密支持密文上的關(guān)系運(yùn)算,能夠提高數(shù)據(jù)檢索效率,同時(shí)能夠達(dá)到特定級(jí)別的安全性。為此,設(shè)計(jì)了一個(gè)基于隨機(jī)間隔的保序加密算法,能夠滿(mǎn)足密文隱藏原始明文的分布,具有保序性,且加解密負(fù)載不會(huì)隨著數(shù)據(jù)域的變化而變化。

2 系統(tǒng)模型

2.1 系統(tǒng)體系結(jié)構(gòu)

支持隱私保護(hù)的云計(jì)算體系結(jié)構(gòu)如圖1所示,該結(jié)構(gòu)反映了數(shù)據(jù)擁有者(Data Owner,DO)、用戶(hù)(Certificate User,CU)和云服務(wù)器(Cloud Database Server,CDS)之間的交互,具體過(guò)程如下:

1) DO首先通過(guò)轉(zhuǎn)換模塊對(duì)原始數(shù)據(jù)pi(i∈[1,n],n≥1)進(jìn)行處理,隱藏其數(shù)據(jù)分布,得到新的數(shù)據(jù)分布集di(i∈[1,n],n≥1);

2) 通過(guò)加密模塊,采用加密算法E對(duì)數(shù)據(jù)di(i∈[1,n],n≥1)加密得到E(di),然后通過(guò)安全信道進(jìn)行傳輸存儲(chǔ)到CDS上;

3) 獲得DO授權(quán)的CU對(duì)請(qǐng)求參數(shù)(para)首先經(jīng)過(guò)轉(zhuǎn)換模塊得到(para1),然后采用相同的加密算法E加密后得到E(para1),并將E(para1)和計(jì)算要求(type)提交給CDS;

4) CDS驗(yàn)證CU的權(quán)限后根據(jù)CU的計(jì)算要求,對(duì)其權(quán)限范圍內(nèi)的E(di)和請(qǐng)求參數(shù)E(para1)進(jìn)行計(jì)算,得到計(jì)算結(jié)果E(result),并將E(result)返回給CU;

5) CU獲得E(result)后通過(guò)解密模塊進(jìn)行解密得到中間值tempValue,然后通過(guò)還原模塊處理,得到最終明文結(jié)果result.

圖1 支持隱私保護(hù)的云計(jì)算體系結(jié)構(gòu)

2.2 威脅模型

由于云計(jì)算數(shù)據(jù)外包和服務(wù)租賃的特點(diǎn),DO和CU將數(shù)據(jù)提交給CDS進(jìn)行存儲(chǔ)和運(yùn)算,CDS會(huì)對(duì)DO的數(shù)據(jù)和CU的計(jì)算請(qǐng)求很好奇,通過(guò)持續(xù)的統(tǒng)計(jì)分析獲取額外的信息,這種內(nèi)部攻擊是云計(jì)算所獨(dú)有的攻擊模型。因此考慮了內(nèi)部攻擊中最常見(jiàn)的統(tǒng)計(jì)型攻擊(Statistical Attack,SA),即攻擊者在獲取相關(guān)背景信息后,可以從數(shù)據(jù)擁有者那里獲取一些統(tǒng)計(jì)信息,然后發(fā)動(dòng)以下攻擊:從明文和密文的數(shù)據(jù)分布中,攻擊者可以很容易確定密文的范圍。例如給定的屬性域“薪水”,假如攻擊者知道員工的薪水分布情況，如圖2所示,可以在密文上進(jìn)行統(tǒng)計(jì),試著確認(rèn)包含5 000到6 000的區(qū)間的密文的范圍。

圖2 薪水-員工數(shù)據(jù)分布

3 保序加密算法OPERI

本節(jié)將設(shè)計(jì)一個(gè)基于隨機(jī)間隔的保序加密算法(Order-Preserving Encryption based on Random Interval,OPERI),支持對(duì)加密數(shù)據(jù)的任何關(guān)系運(yùn)算。OPERI算法主要分為3個(gè)階段:數(shù)據(jù)初始化階段;數(shù)據(jù)加密、解密階段;數(shù)據(jù)還原階段。首先,OPERI算法將原始數(shù)據(jù)D進(jìn)行劃分,然后通過(guò)映射函數(shù)映射到一個(gè)范圍更大的空間C上,來(lái)達(dá)到隱藏?cái)?shù)據(jù)分布和改變數(shù)據(jù)分布概率的目的。其次,算法根據(jù)空間C的大小和密鑰key計(jì)算獲得值域V={vmin,vmax}和初始間隔interval,然后將值域V平分為vnum份,對(duì)初始間隔隨機(jī)分為大小不同的m份,重新計(jì)算vmin,vmax的值,每次迭代都會(huì)改變值域V的大小,進(jìn)行vlevel次迭代后,可將密文值確定在一個(gè)區(qū)間{xminx,xmaxx}內(nèi)。最后,算法利用隨機(jī)數(shù)確定密文值的大小。

OPERI算法由以下4個(gè)算法過(guò)程組成。

3.1 初始化Init

初始化算法Init描述為:

Init:{tmin,tmax,v}←Init(mmin,mmax,m)

其中,mmin,mmax定義了原始數(shù)據(jù)的定義域D,通過(guò)處理后得到中間值C定義域?yàn)閧tmin,tmax},原始明文m處理后得到v.

對(duì)于明文空間D,劃分成一系列的區(qū)間Di=[li,ri] (i=1,2,…,m) .由于D通常是離散的空間,所以設(shè)定li,ri∈z,滿(mǎn)足:

(1)

劃分明文空間可以有效地破壞數(shù)據(jù)的分布規(guī)律:即對(duì)于一個(gè)數(shù)據(jù)集,數(shù)值越多,劃分的區(qū)間數(shù)就越多。

對(duì)于擴(kuò)展空間C,劃分相等個(gè)數(shù)的區(qū)間Ci=[li’,ri’](i=1,2,…,m),設(shè)定li’,ri’滿(mǎn)足:

(2)

給定一個(gè)原始明文區(qū)間Di,相對(duì)應(yīng)的擴(kuò)展空間區(qū)間為Ci,還能得知Mi(li)=li’,Mi(ri)=ri’.同樣劃分?jǐn)U展空間可以有效破壞數(shù)據(jù)的分布規(guī)律:即在Di中包含的數(shù)據(jù)越多,對(duì)應(yīng)的Ci的范圍也就越大。

映射函數(shù)M滿(mǎn)足以下條件:M是可解的,對(duì)于?x∈Di,擴(kuò)展空間值Mi(x)是很容易通過(guò)編程計(jì)算的。而且如果yi=Mi(xi),那么相對(duì)應(yīng)的xi=Mi-1(yi)也很容易求出。為了實(shí)現(xiàn)可編程化,第i個(gè)區(qū)間邊界值和x∈Di作為輸入,輸出結(jié)果yi∈Ci.最簡(jiǎn)單的過(guò)程如下所示:

計(jì)算比例因子vscale=(ri’-li’)/(ri-li);

映射x到擴(kuò)展空間,y=li’+vscale(x-li’);

通過(guò)以上計(jì)算,原始明文空間D映射到擴(kuò)展空間C中,從而能夠隱藏原始數(shù)據(jù)的分布以及改變數(shù)據(jù)分布概率

3.2 加密算法Enc

加密算法Enc描述如下:對(duì)于數(shù)據(jù)v∈C,c←Enc(vmin,vmax,vinterval,vlevel,vnum,vkey,v)且c∈V.其中,vkey表示密鑰;vmin,vmax定義了OPERI算法的最小值和最大值;vinterval為初始間隔域大小,vlevel是處理間隔域的層數(shù);vnum定義了值域分割的數(shù)量。Enc算法的過(guò)程描述如下:

算法1.加密算法Enc

輸入:值域最小值vmin,值域最大值vmax,初始間隔域vinterval,計(jì)算次數(shù)vlevel,處理間隔域?qū)訑?shù)vlevel,密鑰vkey,值域平分個(gè)數(shù)vnum,擴(kuò)展區(qū)間明文值v

輸出:密文值c

1:procedure Enc(vmin,vmax,vinterval,vlevel,vnum,vkey,v)

2:t← (vmax-vmin)/vnum;

3:tt←vinterval;

4: fori=1 tovlevel

5: splitList←v

6: ranList←random.next();

7: borderList←border;

8: end for

9: fori=0 tovlevel

10:vmin=vmin+t-splitList[i]+tt-borderList[i];

11: if split[i]==borderList[i][0]

12:vmax=vmin+t-ranList[i]+tt-(borderList[i][1]-

borderList[i-1][1]);

13: elsevmax=vmin+t-ranList[i];

14:tt=t-(1-ranList[i]);

15: end for

16:c=vmin+(vmax-vmin)-random(vkey+v);

17: end procedure

3.3 解密算法Dec

解密算法Dec描述如下:對(duì)于密文c∈V,v∪φ←Dec(vmin,vmax,vinterval,vlevel,vnum,vkey,c),φ表示無(wú)解。Dec算法的具體過(guò)程描述如下:

算法2.解密算法Dec

輸入:值域最小值vmin,值域最大值vmax,初始間隔域vinterval,處理間隔域?qū)訑?shù)vlevel,值域平分個(gè)數(shù)vnum,密鑰vkey,密文c

輸出:擴(kuò)展空間明文值v

1:procedure Dec(vmin,vmax,vinterval,vlevel,vnum,vkey,c)

2:t← (vmax-vmin)/vnum;

3:tt←vinterval;

4: fori=1tovlevel

5:

6:r=random(vkey+x);

8: ifx==xivmax=vmin+t—r+tt—random(vkey+xj);

9: elsevmax=vmin+t—r;

10:tt=t·(1-r);

11:v=v+x;

12: end for

13:end procedure

3.4 還原算法Restore

還原算法Restore描述如下:對(duì)于v∈C,m←Restore(tmin,tmax,v),經(jīng)計(jì)算后可得到最終結(jié)果m且m∈D。算法的具體過(guò)程描述如下:

算法3.還原算法Restore

輸入:擴(kuò)展區(qū)間值域最小值tmin,擴(kuò)展區(qū)間值域最大值tmax,擴(kuò)張空間明文值v

輸出:原始明文值m

1:procedure Restore(tmin,tmax,v)

2:vscale← (tmin,tmax);

3:m=(v-tmin)/vscale+tmin;

4: end procedure

4 安全性分析

定義1 一個(gè)加密算法E在統(tǒng)計(jì)型攻擊(SA)下是安全的,如果攻擊者ξ發(fā)起以下攻擊:原始數(shù)據(jù)各個(gè)區(qū)間的分布概率都不相等的情況下,假設(shè)p(x∈D1)>p(x∈D2)>…>p(x∈Dm),ξ在進(jìn)行多次查詢(xún)后,得到的密文分布概率p(x∈C1),p(x∈C2),…,p(x∈Cm),通過(guò)統(tǒng)計(jì)分析,ξ根據(jù)明文數(shù)據(jù)分布做出猜測(cè)有p(x∈C1)>p(x∈C2)>…>p(x∈Cm) .

ξ的優(yōu)勢(shì)概率定義為:Adv(ξ)=|p(x∈Ci-p(x∈Cj)|=ε,(i,j∈[1,m]且i≠j),如果 足夠小,則E在統(tǒng)計(jì)型攻擊下是安全的。

定義2 如果一個(gè)數(shù)x∈Di,Di表示一個(gè)區(qū)間,p(x∈Di)=|Di|/L(Di),其中L(Di)為Di的寬度,|Di|為Di中包含的元素個(gè)數(shù)。

定理1 OPERI算法在統(tǒng)計(jì)型攻擊(SA)下是安全的。

證明 在數(shù)據(jù)初始化過(guò)程中,OPERI算法通過(guò)劃分映射等操作,可以隱藏原始數(shù)據(jù)的分布并且改變數(shù)據(jù)分布概率。根據(jù)定義2得知,如果在未進(jìn)行空間擴(kuò)展的情況下,密文分布明文分布相同。由于有p(x∈D1)>p(x∈D2)>…>p(x∈Dm),則有p(x∈C1)>p(x∈C2)>…>p(x∈Cm) .在進(jìn)行了空間擴(kuò)展后,原始數(shù)據(jù)空間D劃分為多個(gè)大小不等的區(qū)間Di,同樣擴(kuò)展空間C也會(huì)被分為相同數(shù)量的區(qū)間Ci,通過(guò)映射函數(shù)M使得Ci=M(Di),Ci區(qū)間的大小根據(jù)Di中的元素個(gè)數(shù)來(lái)定。假設(shè)明文區(qū)間中的任意兩個(gè)子區(qū)間Di,Dj,元素個(gè)數(shù)分別為s,t,那么映射區(qū)間Ci,Cj大小為s-g,t-g(g為設(shè)定的單位距離)。最后通過(guò)計(jì)算獲得的密文值區(qū)間x∈C1,x∈C2,…,x∈Cm會(huì)呈現(xiàn)出近線(xiàn)性分布y=k·x+b那么對(duì)于任意兩個(gè)區(qū)間Di,Dj中的元素有p(x∈Di)=|Di|/L(Di)=s/(s-g)=1/g以及p(x∈Di)=|Di|/L(Di)=t/(t-g)=1/g.

同理可以推出p(x∈C1)≈p(x∈C2)≈… ≈p(x∈Cm),即有|p(x∈Ci-p(x∈Cj)|=ε,(i,j∈[1,m]且i≠j),其中任意小,因此OPERI算法在統(tǒng)計(jì)型攻擊下是安全的。證畢。

5 實(shí)驗(yàn)

通過(guò)實(shí)驗(yàn)對(duì)OPERI算法與文獻(xiàn)[1]提出的OPEART算法進(jìn)行比較。實(shí)驗(yàn)部署在云翼實(shí)驗(yàn)平臺(tái)上,該平臺(tái)是一個(gè)基于Web的面向?qū)W生的云計(jì)算環(huán)境,以KVM和Swift為基礎(chǔ),并部署在由12臺(tái)服務(wù)器構(gòu)成的集群上。

5.1 數(shù)據(jù)分布

實(shí)驗(yàn)1比較通過(guò)OPERI與OPEART加密后的數(shù)據(jù)分布。為了讓實(shí)驗(yàn)的結(jié)果更具有對(duì)比性,實(shí)驗(yàn)選取兩組原始分布具有特征性的數(shù)據(jù),第一組是成對(duì)數(shù)分布的y=log1.2(x),為使數(shù)據(jù)分布更廣泛,將x的范圍定義在[1,10 000]內(nèi),得到y(tǒng)后再乘以10 000取整;第二組是成指數(shù)分布的y=1.01x,實(shí)驗(yàn)選取的x值范圍是[1,1 000],得到y(tǒng)后再乘以10 000取整。

第一組數(shù)據(jù)的原始分布以及加密后的分布圖如圖3所示。

圖3 第一組數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

第二組數(shù)據(jù)的原始分布以及加密后的分布圖如圖4所示。

圖4 第二組數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

通過(guò)圖3和圖4的實(shí)驗(yàn)比較結(jié)果可以看出,經(jīng)過(guò)OPEART算法加密后的數(shù)據(jù)與原始數(shù)據(jù)呈現(xiàn)相同的分布,而通過(guò)OPERI算法加密后的數(shù)據(jù)呈近線(xiàn)性分布,并不與原始數(shù)據(jù)分布相同。實(shí)驗(yàn)1的結(jié)果表明,OPERI算法比OPEART算法更能隱藏原始數(shù)據(jù)的分布特征,具有更高的安全性。

5.2 數(shù)據(jù)分布概率

實(shí)驗(yàn)2是比較通過(guò)OPERI和OPEART加密后的數(shù)據(jù)分布概率,實(shí)驗(yàn)選取圖2對(duì)應(yīng)的薪水-員工數(shù)據(jù),實(shí)驗(yàn)對(duì)比結(jié)果如圖5所示。

圖5 數(shù)據(jù)分布概率的實(shí)驗(yàn)對(duì)比結(jié)果

由圖5的對(duì)比結(jié)果可以看出,通過(guò)OPEART算法加密后,數(shù)據(jù)與原始數(shù)據(jù)具有相同的數(shù)據(jù)分布概率,在5 000～6 000范圍的數(shù)據(jù)分布概率明顯大于其他區(qū)間數(shù)據(jù)的概率,而通過(guò)OPERI算法加密后,數(shù)據(jù)的整體分布概率基本相同,很好地達(dá)到了隱藏?cái)?shù)據(jù)分布概率的目的。

5.3 OPERI算法的效率

實(shí)驗(yàn)3比較了OPERI算法與OPEART算法在加解密、范圍檢索兩方面的性能。其中,OPERI算法與OPEART算法選擇相同的參數(shù)vlevel=7,vnum=99,實(shí)驗(yàn)結(jié)果如圖6、圖7所示。

圖6 加解密時(shí)間對(duì)比

圖7 檢索時(shí)間對(duì)比

由圖6可以看出,OPERI算法的加密和解密負(fù)載幾乎是一樣的,相比OPEART算法加解密時(shí)間也是呈線(xiàn)性增長(zhǎng)。由圖7可以看出,在進(jìn)行范圍檢索時(shí),OPERI算法與OPEART算法在時(shí)間上都是呈線(xiàn)性增長(zhǎng)。性能上相差不大。

綜合實(shí)驗(yàn)結(jié)果來(lái)看,OPERI算法能夠隱藏原始數(shù)據(jù)分布,具有更高的安全性,而且在加解密以及檢索性能上與OPEART算法相差不大。

6 應(yīng)用場(chǎng)景

在實(shí)際的云環(huán)境中,應(yīng)用本文的OPERI算法可以進(jìn)行以下這些操作:

1) 比較運(yùn)算。假如需要求出某個(gè)區(qū)間[xm,xn]內(nèi)的數(shù)據(jù),首先將原始數(shù)據(jù)排好序得到x1

2) 字符串精確匹配。字符串是由一個(gè)個(gè)的字符構(gòu)成,由于不同的字母對(duì)應(yīng)的ASCII碼值不同,而且大小按照字母表順序排列,比如a對(duì)應(yīng)的ASCII碼值為97,b對(duì)應(yīng)的碼值為98,有a

3) 字符串模糊匹配。假如需要查找字符串a(chǎn)bcde,經(jīng)過(guò)2)中的字符串精確匹配后發(fā)現(xiàn)沒(méi)有完全匹配的字符串,但是有相近的字符串a(chǎn)bcee、abcfe和abcge,由于OPERI算法能計(jì)算得出e與d的距離相比于f與d和g與d的距離更近,所以最終會(huì)選擇將abcee的密文返回給用戶(hù),然后用戶(hù)進(jìn)行解密得到距離abcde最近的明文值abcee.這種模糊匹配不同于用編輯距離查找模糊字符串的做法,它是返回距離指定字符串最近的明文值。

7 結(jié)論

對(duì)OPEART算法進(jìn)行改進(jìn),提出了一種OPERI算法。改進(jìn)的算法首先利用線(xiàn)性表達(dá)式將原始明文空間映射至擴(kuò)展空間,從而能夠隱藏原始數(shù)據(jù)的分布以及改變數(shù)據(jù)分布概率;其次將擴(kuò)展空間的數(shù)據(jù)作為加密算法的輸入,通過(guò)引入隨機(jī)間隔,每經(jīng)過(guò)一輪計(jì)算,密文所在的數(shù)據(jù)域的范圍會(huì)被縮小;最后通過(guò)隨機(jī)數(shù)確定密文的值。安全性分析和實(shí)驗(yàn)結(jié)果證明了OPERI算法在原有安全性的基礎(chǔ)上能夠抵擋統(tǒng)計(jì)型攻擊,并且具有很高的運(yùn)行效率,能夠抵擋統(tǒng)計(jì)型攻擊。

[1] Huang Ruwei,Gui Xiaolin,Chen Ningjiang.An encryption algorithm supporting relational calculations in cloud computing[J].Journal of Software,2015,26(5):1181-1195.

[2] Ozsoyoglu G,Singer D A,Chung S S.Anti tamper databases:querying encrypted databases[C]∥Proceeding of the 17th Annual IFIP WG 11.3 Working Conference on Database and Applications Security.GA,USA,2003:1-19

[3] Liu D,Wang S.Nonlinear order preserving index for encrypted database query in service cloud environments[J].Concurrency and Computation:Practice and Experience,2013:1967-1984.

[4] Liu D,Wang S.Programmable order-preserving secure index for encrypted database query[C]∥2012 IEEE Fifth International Conference on Cloud Computing.Hawaii,USA,2012:502-509.

[5] Boldyreva A,Chenette N,Lee Y,et al.Order-preserving symmetric encryption[J].Advances in Cryptology-EUROCRYPT,2009:224-241.

[6] Boldyreva A,Chenette N,O’Neil A.Order-Preserving encryption revisited:improved security analysis and alternative solutions[C]∥Proceedings of the 31st annual conference on Advances in Cryptology.Berlin,Heidelberg,2011:578-595.

[7] Mohammad A,Ashkan P,Marinescu D C.Security of applications involving multiple organizations-order preserving encryption in hybrid cloud environments[C]∥2014 IEEE 28th International Parallel & Distributed Processing Symposium Workshops.Phoenix (Arizona),USA,2014:894-903.

[8] Krendelev S F,Yakovlev M,Usoltseva M.Order-preserving encryption schemes based on arithmetic coding and matrices[C]∥Proceedings of the 2014 Federated Conference on Computer Science and Information Systems.Warsaw,Poland,2014:891-899.

[9] Martinez S,Miret J M,Tomas R,et al.Securing databases by using diagonal-based order preserving symmetric encryption[J].Applied Mathematics & Information Sciences,2014,8(5):2085-2094.

[10] Fang Q,Wilfred Ng,Feng J,et al.Mining bucket order-preserving submatrices in gene expression data[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(12):2218-2231.

[11] Bebek G.Anti-tamper database research:inference control techniques[R].Technical Report EECS 433 Final Report,Case Western Reserve University,2002.

[12] Popa R A,Li F H,Zeldovich N.An ideal-security protocol for order-preserving encoding[C]∥2013 IEEE symposium on Security and Privacy.San Francisco,CA,USA,2013:463-477.

[13] Reddy K S,Ramachandram S.A Novel dynamic order-preserving encryption scheme[C]∥2014 First International Conference on Networks & Soft Computing (ICNSC).Andhra Pradesh,India,2014:92-96.

[14] Liu Zheli,Chen Xiaofeng,Yang Jun,et al.New order preserving encryption model for outsourced database in cloud environments[J].Journal of Network and Computer Applications,2014,(7):1-10.

(編輯：劉笑達(dá))

Order-Preserving Encryption Algorithm based on RandomInterval in Cloud Environments

ZHOU Xiong1,LI Taoshen1,2,HUANG Ruwei1,2

(1.SchoolofComputer,ElectronicsandInformation,GuangxiUniversity,Nanning530004,China；2.GuangxiCollegesandUniversitiesKeyLaboratoryofParallelandDistributedComputing,Nanning530004,China)

With the further development of Cloud Computing,people are more concerned for data privacy.Encryption is an effective way to protect data privacy.But it makes data inoperable and most of them can not hide data distribution.To solve the problem of hiding original data distribution,modified order-preserving encryption algorithm based on random interval in cloud environment (OPERI) is proposed in this paper.Firstly,original data are be mapped to new data domain in order to hide the data distribution of original data and change the data probability.Then,random interval is introduced to encrypt the data,which can suppert relational calculations on ciphertexts.Security analysis and experiment results show that OPERI algorithm can resist the statistical attack on the original security and it is efficient to realize relational calculations on ciphertexts.

order preserving encryption;privacy protect;cloud computing;statistical attack

1007-9432(2015)06-0741-08

2015-05-10

國(guó)家自然科學(xué)基金資助項(xiàng)目:無(wú)線(xiàn)Mesh網(wǎng)絡(luò)中基于定向天線(xiàn)的關(guān)鍵技術(shù)研究(61363067),廣西自然科學(xué)基金項(xiàng)目(2012GXNSFAA053222)，廣西教育廳科研基金項(xiàng)目(2013YB007)資助

周雄(1990-),男，湖北武穴人，碩士生，主要從事網(wǎng)絡(luò)計(jì)算與信息安全研究，(Tel)13768301390

李陶深，湖北武穴人，博士，教授，主要從事分布式數(shù)據(jù)庫(kù)系統(tǒng)、無(wú)線(xiàn)mesh網(wǎng)絡(luò)、云計(jì)算研究。

TP309

A

10.16355/j.cnki.issn1007-9432tyut.2015.06.019