郁 鵬, 潘森杉, 張建明

(江蘇大學(xué) 計算機科學(xué)與通信工程學(xué)院, 江蘇 鎮(zhèn)江 212013)

在已實現(xiàn)的云計算[1]服務(wù)中,隱私安全一直令人擔(dān)憂,這已成為阻礙云計算發(fā)展和推廣的主要因素之一.用戶的數(shù)據(jù)隱私包括可用來識別或定位個人的信息(如電話號碼等)、敏感的信息(如個人財務(wù)信息等).云計算的隱私安全問題[2]源于云計算數(shù)據(jù)外包和服務(wù)租賃的特點.用戶數(shù)據(jù)存儲到云環(huán)境中,人們失去了對數(shù)據(jù)的直接控制力,可能會導(dǎo)致個人隱私數(shù)據(jù)的泄露和濫用.而近年來發(fā)生的Google,MediaMax等云服務(wù)商泄露或丟失用戶數(shù)據(jù)的事實證實了人們的擔(dān)心.加密是一種常用的保護用戶隱私數(shù)據(jù)的方法,但目前大多數(shù)的加密方案都不支持直接對密文的運算[3],如區(qū)間搜索、范圍查詢,因而嚴(yán)重妨礙了云服務(wù)商為用戶提供更進一步的數(shù)據(jù)管理和運算服務(wù),從而削弱了云計算的優(yōu)勢.

保序加密是一個保護加密值順序的加密方案,可以使系統(tǒng)以與明文相同的方式在密文上執(zhí)行順序操作:一個數(shù)據(jù)庫服務(wù)器能建立一個索引,所有加密數(shù)據(jù)都可以使用與明文數(shù)據(jù)相同方式來執(zhí)行范圍查詢和排序,導(dǎo)致系統(tǒng)性能良好.這個優(yōu)點使得可對已有軟件進行最小的改變,使保序加密更容易被應(yīng)用.但是順序會給敵手更多的背景知識.假設(shè)敵手從其他數(shù)據(jù)提供者獲取一些統(tǒng)計信息包括數(shù)據(jù)頻率和數(shù)據(jù)分布.這樣的敵手在保序數(shù)據(jù)隱私挖掘中總是被提到,但是在保序加密方案中還鮮有提及.敵手可以得到有用的統(tǒng)計信息來進行統(tǒng)計攻擊.

在敵手的攻擊中,假設(shè)敵手具有關(guān)于明文值或明文域上的統(tǒng)計信息的先驗知識.以前的保序加密忽略這些類型的攻擊或者假設(shè)攻擊者沒有關(guān)于明文域的任何信息.實際上,敵手在許多情況下可能具有關(guān)于明文域的基礎(chǔ)信息或者更多的信息[4].

文中擬提出一個在外包數(shù)據(jù)庫中可以抵抗統(tǒng)計攻擊、實用、安全有效的保序加密方案.該方案中劃分明文值區(qū)域成許多區(qū)間,允許一個整數(shù)在使用相同的密鑰時能被加密成多個值從而抵抗統(tǒng)計攻擊.

1 相關(guān)工作

1.1 云環(huán)境下加密

云環(huán)境下的加密有3個參與方: 數(shù)據(jù)擁有者、云服務(wù)器提供者和用戶.而加密涉及的具體算法概括說包括4種: ① 系統(tǒng)建立算法，由數(shù)據(jù)擁有者運行,主要用來生成系統(tǒng)參數(shù)和數(shù)據(jù)擁有者的密鑰.輸入安全參數(shù)、數(shù)據(jù)擁有者生成系統(tǒng)的公開參數(shù)和自己的私鑰.當(dāng)涉及可搜索的公鑰加密算法時,公開參數(shù)也包括數(shù)據(jù)擁有者的公鑰. ② 數(shù)據(jù)加密算法，用來加密可搜索的數(shù)據(jù).算法輸入公開參數(shù)和數(shù)據(jù)明文,輸出相應(yīng)的密文(有時還會輸出加密的數(shù)據(jù)關(guān)鍵詞的索引表).如果是可搜索的對稱加密算法,則算法還需輸入數(shù)據(jù)擁有者的私鑰. ③ 令牌生成算法，當(dāng)用戶需要搜索數(shù)據(jù)時,向數(shù)據(jù)擁有者提交搜索請求,然后數(shù)據(jù)擁有者運行該算法對請求進行響應(yīng).算法輸入搜索條件和數(shù)據(jù)擁有者的私鑰,輸出一個令牌(token)或稱為陷門. ④ 數(shù)據(jù)檢索算法，用戶利用該令牌逐一測試密文或索引是否滿足指定的檢索條件,僅當(dāng)滿足條件時,算法才輸出相應(yīng)的密文或者索引[5].

如果大數(shù)據(jù)加密之后存儲,那么大數(shù)據(jù)以密文的形式存在,所以在密文搜索階段不太可能會泄漏大數(shù)據(jù)的隱私[6-7].然而在這種情況下,為了保證大數(shù)據(jù)的可用性,必須要求對密文能夠進行有效的檢索和查詢,所以本階段的主要問題是如何設(shè)計能夠滿足大數(shù)據(jù)特點的可搜索的加密算法,即如何設(shè)計安全、運行效率高且允許對一般數(shù)據(jù)進行復(fù)雜搜索請求的密文搜索算法.

1.2 保序加密

保序加密最早由R. AGRAWAL等[8]在2004年提出,其核心思想為擴域映射,即將原數(shù)據(jù)映射到另一個大域空間中.保序加密的優(yōu)點是可以對加密數(shù)據(jù)在無需解密的狀態(tài)下直接進行比較操作,等值或者范圍查詢以及涉及MIN,MAX和COUNT的聚合查詢.另一個加密方案有著可證安全保證(Boldy-reva′09)[9]:加密等價于保留順序的隨機映射.但是它的加密執(zhí)行時間是176 ms,所以這個方案效率低.對于一個保序加密方案,可以達到的理想安全是IND-OCPA(Boldyreva′09):關(guān)于明文值除了它們的順序外,不會再泄露更多的信息.達到理想安全的保序加密方案是可變保序加密(Popa′13[10],Kerschbaum′14[11]),這些方案通過建立包含所有加密明文值的二叉平衡樹來工作,要求加密協(xié)議是交互的,并且對于已經(jīng)加密的少量密文會隨著新的明文值被加密而改變,用戶可以自己定義函數(shù)來實現(xiàn)在數(shù)據(jù)庫中的操作.這些功能嚴(yán)重地影響著方案的效率.除了以上的幾種保序加密方案,一些其他的保序加密方案(Teranishi′14[12], Mavroforakis′15[13])也被提出,但是它們都除了值的數(shù)據(jù)還泄露了更多的信息[14].通過上面總結(jié)可以發(fā)現(xiàn):為了達到高安全性,保序加密需要隱藏密文的順序并且使用額外的功能來完成順序比較,但是這種方法會導(dǎo)致低的效率,額外的存儲空間并且不能直接密文比較.

1.3 線性加密技術(shù)和非線性加密技術(shù)

2013年,LIU D. X.等[15]首次提出線性加密的基本模型ax+b+noise,其中x是明文,a和b是密鑰,noise是一個隨機選擇的值.但是這種線性加密模型沒有安全保證,敵手可以利用重復(fù)型的數(shù)據(jù)來獲取密鑰.在極端情況下,選取重復(fù)數(shù)據(jù)的最大值和最小值來估計a的大小,當(dāng)重復(fù)型數(shù)據(jù)越多,推測a的準(zhǔn)確性越高.

針對這種情況,LIU D. X.等進一步提出了非線性加密模型af(x)x+b+noise,其中a>0;在x不等于0時,f(x)>0;在x1>x2>0或者x1f(x2).由于方程是非線性的,noise的取值范圍會根據(jù)不同的輸入值而不同,能很好地彌補線性加密的缺點,不會因為重復(fù)型數(shù)據(jù)而讓敵手估計a的大小.

2 系統(tǒng)模型

2.1 問題模型

圖1給出了保序加密基礎(chǔ)模型.

圖1 保序加密基礎(chǔ)模型

如圖1所示,保序加密模型反映了數(shù)據(jù)擁有者、云服務(wù)器提供者和用戶之間的交互,具體過程如下: ① 用戶用加密算法E對數(shù)據(jù)d進行加密,然后存儲到云服務(wù)器上; ② 用戶得到數(shù)據(jù)擁有者授權(quán)后,對搜索條件參數(shù)(para)進行加密,并且和計算要求(type)一起發(fā)送給云服務(wù)器; ③ 云服務(wù)器驗證用戶的權(quán)限,然后根據(jù)搜索條件得到搜索結(jié)果E(result)并返回給用戶; ④ 用戶對E(result)解密,得到相應(yīng)的明文.

在這個過程中,因為保序加密的特點,云服務(wù)器可以對加密數(shù)據(jù)直接進行操作,那么產(chǎn)生了一個問題:用戶和數(shù)據(jù)提供者對于敏感數(shù)據(jù)和參數(shù)進行怎樣的加密處理,才能使數(shù)據(jù)隱私得到保護.如果這個問題不能得到有效解決,用戶就不能利用云計算中的計算資源對敏感數(shù)據(jù)進行處理,從而削弱了云計算的優(yōu)勢.圖2給出了問題模型示意圖.

圖2 問題模型

2.2 敵手模型

保序加密操作在客戶端上執(zhí)行,文中采取有效的方法來確?？蛻舳松喜粫孤度魏侮P(guān)鍵信息.

假設(shè)有如下2種攻擊者：

1) 消極的攻擊者.它們有外包數(shù)據(jù)庫的訪問權(quán)限,能看到加密數(shù)據(jù),除了順序還想知道更多的信息,但是只能進行統(tǒng)計攻擊.

定義1抗統(tǒng)計攻擊.ε為一個加密算法,令Δ為明文值統(tǒng)計量∑p和對應(yīng)密文值的統(tǒng)計量∑c的相似度統(tǒng)計;當(dāng)Δ相當(dāng)小時,可認為加密算法ε抗統(tǒng)計攻擊.

2) 積極的攻擊者.它們既有數(shù)據(jù)庫訪問權(quán)限又有客戶端訪問權(quán)限,有更多的信息來猜測加密的數(shù)據(jù),能進行已知明文攻擊或者選擇明文攻擊來猜測加密密鑰.文中對選擇明文攻擊進行限制—IND-DNCPA(indistinguishabilityunderdistinctandneighboringchosenplaintextattack)[16].

定義2IND-DNCPA的安全性.敵手A發(fā)起以下攻擊: ① 敵手A選擇一組連續(xù)明文M={x1,x2,…,xk},xi∈D,xi≠xj且i,j∈[1,k],用加密算法進行計算得到相應(yīng)的加密結(jié)果C={c1,c2,…,ck},A試圖通過解方程的方式解出其他密文c(c?C)對應(yīng)的明文; ② 敵手A選擇2個數(shù)據(jù)m0,m1,其中m1=m0+1,且m0?M,m1?M; ③ 加密算法隨機加密其中一個數(shù)據(jù)mb，b∈{0,1},并將產(chǎn)生的密文cb返回給A; ④ 敵手A輸出b′作為對b的猜測,則敵手A的優(yōu)勢概率定義為Adv(A)=|Pr[b′=b]-0.5|=ε.如果ε足夠小可忽略不計,則算法是IND-DNCPA安全的.

實際上,現(xiàn)實中主要的威脅是第1種攻擊者.它們能得到存儲在外包數(shù)據(jù)庫上的數(shù)據(jù),但卻不能得到加密密鑰.所以抗統(tǒng)計分析攻擊是文中基本和實際的安全目標(biāo).

3 新的保序加密模型

以下將介紹具體擴展密文的方法并且提出一個基于非線性映射的保序加密方案(nOPE).

3.1 概念

本節(jié)介紹文中將使用到的一些變量.

Di: 原始明文信息空間的一個區(qū)間,可以表示為Di=[li,ri].在2個相鄰區(qū)間Di和Di+1,總是存在ri=li+1.

Ci: 擴展后的信息空間即密文空間中的一個區(qū)間,可以表示為Ci=[li′,ri′].在2個相鄰區(qū)間Ci和Ci+1,總是存在ri′=li+1′.

Enc(): 從原始明文空間到密文空間的映射函數(shù),是一個單調(diào)遞增函數(shù),由不同區(qū)間Di的Enci(x)組成.

Range(i): 用以獲得原始明文區(qū)間Di的最大值和最小值的函數(shù).

Range′(i): 用以獲得密文區(qū)間Ci的最大值和最小值的函數(shù).

Index(i): 用以獲得值x在區(qū)間Di中的索引數(shù)i的函數(shù).

3.2 保序加密構(gòu)造

加密系統(tǒng){M,C,k,Enc,Dec}含有明文空間M,密文空間C,密鑰k,加密算法Enc和解密系統(tǒng)Dec.

保序加密方案通過以下幾步執(zhí)行: ① 隨機劃分原始明文信息空間成一系列不同長度的區(qū)間; ② 選擇一個擴展的密文空間并且把密文空間劃分成數(shù)量相同的區(qū)間; ③ 使用非線性加密功能來把原始數(shù)據(jù)映射到擴展的密文空間中去.

該保序加密方案具體如圖3所示.

圖3 保序加密方案

3.2.1 劃分原始明文空間

與Liu′16[17]中的思想相同,將原始明文空間M劃分成一系列的區(qū)間Di=[li,ri]，i=1,2,…,m,由于原始明文空間M通常是離散的空間,需要li,ri∈Z滿足以下條件:

(1)

[li,ri]∩[lj,rj]=?，i≠j.

(2)

這個步驟很有意義,有助于有效地破壞數(shù)據(jù)的分布規(guī)律:對于一個數(shù)據(jù)集,存在數(shù)據(jù)越多,劃分成的區(qū)間數(shù)也就越多.

3.2.2 劃分密文空間

將密文空間C劃分成一系列的區(qū)間Ci=[li′,ri′]，i=1,2,…,m,需要li′,ri′∈Z滿足以下條件:

(3)

[li′,ri′]∩[lj′,rj′]=?，i′≠j′.

(4)

對于每一個原始信息區(qū)間Di,對應(yīng)的密文區(qū)間為Ci,即通過加密功能使Enc(li)=li′,Enc(ri)=ri′.文中通過劃分?jǐn)?shù)據(jù)空間來破壞數(shù)據(jù)分布規(guī)律,在Di中包含的數(shù)據(jù)越多,Ci的范圍也就越大.

3.2.3 映射步驟

經(jīng)過上面2步劃分,需要把各個數(shù)據(jù)映射到密文空間C上,使用加密功能Enc(x)來實現(xiàn)這一目標(biāo).對于明文空間中的每個數(shù)據(jù)x,得到包含x的區(qū)間Di=[li,ri],對于不同的區(qū)間Di,使用不同的加密功能Enci(x)來把不同的值映射到目標(biāo)空間Ci=[li′,ri′],總體的過程如下:

(5)

3.2.4 劃分方法

劃分空間的目標(biāo)是破壞統(tǒng)計特征,以下將討論怎么劃分明文空間M和密文空間C來實現(xiàn)這個目標(biāo).

劃分空間的規(guī)則如下: ① 若一個原始數(shù)據(jù)集合存在越多的數(shù)據(jù),則應(yīng)該劃分越多的區(qū)間,稱這些區(qū)間作為密集區(qū)間; ② 對于一個包含高頻數(shù)據(jù)的原始密集區(qū)間Di,其對應(yīng)的密文空間Ci應(yīng)該有一個大范圍,即對于2個相鄰值x1,x2∈Ci,有d(x1,x2)?1或者|ri′-li′|?|ri-li|.

上面2個規(guī)則能夠破壞數(shù)據(jù)分布,密集區(qū)間擴展到密文空間有大的范圍,但是稀疏區(qū)間擴展到密文空間是小的范圍,并且通過這個方法密文會接近均勻分布.

為了實現(xiàn)劃分,給出如下參數(shù):

P=(xmin,xmax,{Ti},dmin),

(6)

式中:xmin和xmax為明文的起始點;{Ti}代表密集區(qū)間的集合；dmin是文中能設(shè)的最小長度的區(qū)間.

具體的劃分方法如下:令明文空間為

M=R1+T1+R2+T2+…+Rn+Tn+Rn+1，

(7)

式中Rn為稀疏區(qū)間,隨機選擇整數(shù)si使區(qū)間Ri分成相同的區(qū)間,對于密集區(qū)間Ti=[li,ri]來說,將其劃分為

Ti=dmin+n∩…∩dmin.

(8)

密文空間采用與明文空間相同的劃分方法.

數(shù)據(jù)的更新如下:當(dāng)在原始數(shù)據(jù)集合中插入少量新的數(shù)據(jù)時,密集區(qū)間不變;在原始數(shù)據(jù)集合中插入大量新的數(shù)據(jù)后,重新對新數(shù)據(jù)集進行劃分密集區(qū)間,更改密鑰,重新進行加密.

通過上面的劃分方法能確定索引數(shù)Index(x),表達式為

(9)

3.2.5 加密功能

加密函數(shù)Enc()應(yīng)該滿足以下條件:Enc()是可解的,對于?x∈Di,擴展空間值Enci(x)是很容易通過編程計算的.而且如果yi=Enci(x),那么對應(yīng)的xi=Enci-1(yi)也應(yīng)該是可計算的.

可計算的過程:為了實現(xiàn)可編程化,對于第i個區(qū)間邊界值和x∈Di作為輸入,輸出結(jié)果為y∈Ci.事實上,加密功能函數(shù)可以由任何單調(diào)遞增函數(shù)生成.最簡單的可計算過程是采用線性方程方法,但是對于重復(fù)性數(shù)據(jù),采用線性方程方法易于被攻擊.所以使用非線性映射來作用在保序加密模型上,且使用的加密函數(shù)如下:

Enci(x)=aix3+bi+δi,

(10)

所以加密功能Enc()可以定義為

(11)

式中:δ(x,Di)=0，x?Di;δ(x,Di)=1，x∈Di.

干擾系數(shù)δ:這里干擾系數(shù)δ可以破壞數(shù)據(jù)的統(tǒng)計特性.例如,對于高頻數(shù)據(jù)xi,可以構(gòu)成一對多的映射:

(12)

這是一個點對集的映射,假如使干擾系數(shù)δ服從均勻分布,則密文的分布概率是

(13)

因此數(shù)據(jù)的統(tǒng)計特征可以被干擾系數(shù)破壞.

3.2.6 保序加密系統(tǒng)

基于上述劃分功能和加密功能,可采用如下的方法來描述文中的保序加密系統(tǒng):

OPE=(Init,Enc,Dec).

Init()算法在保序加密客戶端上執(zhí)行,需要輸入以下參數(shù): ① 明文信息空間M輸入空間最小值xmin和最大值xmax; ② 密文空間C輸入空間最小值ymin和最大值ymax; ③ 劃分明文空間輸入密集區(qū)間{Ti}和可設(shè)置區(qū)間最小值dmin; ④ 劃分對應(yīng)密文空間的參數(shù).

最終的密鑰k由{li,ri,li′,ri′,dmin}組成.

Enc(x,k)算法在保序加密客戶端上執(zhí)行,來加密數(shù)據(jù)x輸出它的對應(yīng)密文.為了加密x,首先通過計算Index(x)來得到索引i,然后執(zhí)行Enci(x)來得到對應(yīng)的密文.

Dec(y,k)算法在保序加密客戶端上執(zhí)行,來解密數(shù)據(jù)y輸出它的對應(yīng)明文.可用如下公式表示解密過程:

(14)

在解密之前需要求出包含數(shù)據(jù)y的密文區(qū)間Ci的索引值i.

4 正確性和安全性分析

在上述保序加密系統(tǒng)的前提下,將分析它的正確性和安全性,即抗統(tǒng)計分析和IND-DNCPA.事實上,文中僅存儲密文在不信任的數(shù)據(jù)庫上,所以敵手只能得到一些密文而不能得到其他信息.

4.1 算法正確性分析

定理1稱保序加密方案nOPE是正確的,如果滿足以下條件:

1) ?m∈D,?Dec(k,Enc(k,m))=m;

2)x1>x2(x1,x2∈D),有Enc(x1)>Enc(x2).

證明1) 根據(jù)該保序加密的結(jié)構(gòu),每個明文所在的區(qū)間是非線性劃分的且沒有交集,因此保證了任何密文值只能屬于一個對應(yīng)的明文區(qū)間.加密時,明文x通過Index函數(shù)求出明文所在區(qū)間,得到ai和bi,通過aix3+bi+noise來求出密文;解密時,密文y通過Index函數(shù)求出密文所在區(qū)間,得到ai和bi,來求解出對應(yīng)的明文.因此,只要加密和解密的過程中使用相同的密鑰k,就能使加密的明文解密后得到相同的明文.

2) 該保序加密方案a恒大于0,每個明文加密后的密文沒有交集,假設(shè)2個相鄰的數(shù)x1和x2,x1

綜上所述,該保序方案是正確的.

4.2 統(tǒng)計攻擊

事實上,需要證明文中的基礎(chǔ)模型Enc(x)=ax3+b+δ在統(tǒng)計攻擊下安全.與統(tǒng)計攻擊有關(guān)的是相似度的統(tǒng)計,在這種攻擊中,攻擊者試圖基于明文上的一些統(tǒng)計信息找到密文值和明文值之間的匹配,并利用它們來獲得密鑰.

定理2保序加密方案nOPE是抗統(tǒng)計攻擊的.

證明之前的單一映射保序加密,如MIN,MAX和COUNT的統(tǒng)計函數(shù)對相同的明文值和密文值是相同的.另外,這種單一映射加密明文值為另一個固定值,所以加密前后數(shù)據(jù)值的頻率是一樣的.這種單一映射的保序加密有著高相似度統(tǒng)計Δ,所以這種方案在統(tǒng)計攻擊下是不安全的.

文中基本模型中引入了干擾系數(shù)δi來阻止統(tǒng)計攻擊，映射形式如下:

(15)

式中: |δi|

(16)

本文方案中,因為明文值被加密成許多不同的值,所以明顯地明文值和加密后的密文值的頻率不同,即

(17)

此外,MIN,MAX和COUNT的統(tǒng)計函數(shù)在密文和明文值上完全不同,因此關(guān)于明文值的統(tǒng)計量∑p和對于密文值的統(tǒng)計量∑c是不同的.可以明顯地看出該算法相似度百分比Δ遠小于單值映射的相似度百分比.基于定理2,該方案對于統(tǒng)計攻擊是安全的,因為統(tǒng)計的相似度百分比Δ相當(dāng)小.對于統(tǒng)計函數(shù),這個方案仍是在加密數(shù)據(jù)上直接使用元函數(shù).例如,MIN值是第1個區(qū)間的最小加密值,MAX值是最后一個區(qū)間的最大加密值.

4.3 IND-DNCPA安全

引理1假設(shè)明文空間|M|=m并且Enc具有保序功能,在選擇明文攻擊下經(jīng)過logm次詢問可以得到關(guān)于任何密文的范圍.

所有的保序加密算法在選擇明文攻擊下面都是不安全的,所以對于選擇明文攻擊作出限制,稱之為IND-DNCPA攻擊.

定理3保序加密方案nOPE是IND-DNCPA安全的.

證明由于方案具有保序性,敵手A可能通過分析M中密文的差距以及與m0或m1最近點的密文來推斷b.

1) 當(dāng)A通過求出平均距離

(18)

來猜測x的值時,由于方案是非線性映射y=ax3+b,使得密文與參照函數(shù)

f(x)=Enc(x1)+(x-x1)d

(19)

相差很大,因此,A無法從密文直接猜測出相對應(yīng)的明文.

2) 當(dāng)A通過分析密文之間的距離d′來推測密文的值域時,當(dāng)相鄰的2個點在同一個區(qū)間中時,有

d′=ai(xi+1)3-ai(xi)3;

(20)

當(dāng)相鄰的2個點在不同區(qū)間時,有

d′=ai(xi+1)3+bi-aj(xi)3-bj+noisei-noisej

(21)

使得A要判斷值域的大小變得很困難.

因此,A的優(yōu)勢概率為

Adv(A)=|pr[b′=b]-0.5|=ε,

(22)

式中ε是一個足夠小可忽略不計的數(shù).

綜上所述,該算法是具有IND-DNCPA安全的.

5 仿真和實現(xiàn)

5.1 實施細節(jié)

對于文中算法,需要保護數(shù)據(jù)格式并且形成數(shù)值型保序加密密文.在實際應(yīng)用中,數(shù)字范圍通常不大,而數(shù)據(jù)庫為數(shù)值數(shù)據(jù)提供了一些具有大范圍的數(shù)據(jù)類型,例如,SQL server的“real”型范圍是從-3.40×1038到3.40×1038,足夠用于一些保序加密的應(yīng)用程序.通過這種方式,保序加密密文將是實數(shù),并且可以存儲在原始字段中,從而導(dǎo)致對現(xiàn)有軟件的最小更改.文中方案的所有保序加密操作包括加密和解密操作都是只在客戶端上執(zhí)行.因此,這個可以用任何可編程語言部署和實現(xiàn),包括java,c++等.本次方案在Win10的試驗環(huán)境下實現(xiàn),使用工具為MyEclipse 10和Matlab 7.1.

5.2 試驗結(jié)果

用一組學(xué)生成績來測試該算法的實際表現(xiàn),測試其執(zhí)行時間,顯示加密后的數(shù)據(jù)分布,試驗結(jié)果如圖4-6所示.圖4給出了保序加密的平均執(zhí)行時間.

由圖4可見,每10萬個加密數(shù)平均加密執(zhí)行時間大約30 ms,而Boldyreva′09算法加密一個數(shù)據(jù)需要花費176 ms,所以文中保序加密方案執(zhí)行時間短、效率高.圖5給出了試驗數(shù)據(jù).

圖4 加密平均執(zhí)行時間

圖5 試驗數(shù)據(jù)

圖5a給出了學(xué)生成績的原始數(shù)據(jù)分布,可見學(xué)生的成績主要集中在70到90之間.圖5b給出了加密后學(xué)生成績的數(shù)據(jù)分布,對于相同的數(shù)據(jù)則是加密成為不同的數(shù)據(jù),即在區(qū)間[ax3+b,ax3+b+noise],具體數(shù)據(jù)72加密值范圍為[17 507 936,17 835 985].圖6給出了數(shù)據(jù)分布.

圖6 數(shù)據(jù)分布

由圖6可見,加密后數(shù)據(jù)分布明顯被破壞了.

5.3 方案比較

在效率、安全性和可編程3個方面,把文中方案和其他經(jīng)典的保序加密方案(Popa′13和Liu′16)進行比較,表1給出了比較結(jié)果.

表1 文中方案和其他經(jīng)典的保序加密方案的比較

由表1可見:

1) 關(guān)于效率,Popa′13的方案有最低效率.在Popa′13方案中當(dāng)加密一個值的時候,客戶端需要和服務(wù)器相互作用,而且服務(wù)器需要在添加和刪除節(jié)點的時候平衡二叉樹,這大大地降低了方案的效率.而文中方案和Liu′16方案使用一些沒有交互的非線性數(shù)學(xué)函數(shù),有著相同的效率,方案的執(zhí)行時間短、效率高.

2) 關(guān)于安全性,Popa′13方案達到了理想安全.相比較Liu′16線性映射方案,文中方案使用非線性映射來隱藏數(shù)據(jù)分布和數(shù)據(jù)頻率,克服了對于重復(fù)型數(shù)據(jù)線性映射的缺點,它能抗統(tǒng)計攻擊和IND-DNCPA,達到更高安全性.文中方法不準(zhǔn)備和Popa′13方案一樣達到理想安全,因為會失去保序加密對于密文數(shù)據(jù)直接比較的特點,會限制保序加密的應(yīng)用,方案中通過隱藏數(shù)據(jù)分布和數(shù)據(jù)頻率來提高保序加密方案的安全性.

3) 關(guān)于可編程性,文中方案有著更好的應(yīng)用.該方案通過可編程語言易于實現(xiàn)非線性保序加密功能.但是在Popa′13方案中,除了樹平衡操作,用戶定義功能需要在不同數(shù)據(jù)庫上實現(xiàn),這增加了可編程難度.

6 結(jié) 論

1) 指出在密文數(shù)據(jù)直接比較時,隱藏數(shù)據(jù)的分布和數(shù)據(jù)頻率是十分重要的也是保序加密的目標(biāo).

2) 在方法中引入干擾系數(shù)和擴展消息空間的方法,克服了對于重復(fù)型數(shù)據(jù)破解密鑰的問題,使得明文的統(tǒng)計特性被破壞了從而達到了抗統(tǒng)計攻擊,并且達到了IND-DNCPA.

3) 通過沒有交互的非線性數(shù)學(xué)函數(shù),方法的效率大大提高.

4) 該保序加密方案不僅有著以前保序加密的優(yōu)點(即能在不解密密文的前提下在服務(wù)器上直接進行范圍查詢),而且安全性分析和性能評價展示了該算法既安全又高效.

)

[1] BEHERA A, RATHA B K, SETHI S. Green cloud computing: a survey[J]. IJSEAT, 2017, 4(12): 763-767.

[2] RASTOGI N, GLORIA M J K, HENDLER J. Security and privacy of performing data analytics in the cloud: a three-way handshake of technology, policy and management[J]. Journal of Information Policy, 2015, 5:129-154.

[3] 季一木, 朱曈暉, 柴博周,等. 云環(huán)境下用戶隱私混合加密方案及其性能分析[J]. 重慶郵電大學(xué)學(xué)報(自然科學(xué)版), 2015, 27(5):631-638.

JI Y M, ZHU T H, CHAI B Z, et al. Hybrid encryption scheme and performance analysis for user′s privacy in cloud[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2015,27(5):631-638.(in Chinese)

[4] 喬帥庭, 韓文報, 李益發(fā),等. 一種改進的中間域多變量公鑰簽名方案[J]. 四川大學(xué)學(xué)報(自然科學(xué)版), 2014, 51(3):512-516.

QIAO S T, HAN W B, LI Y F, et al. An improved medium-filed multivariate public key signature scheme[J]. Journal of Sichuan University(Natural Science Edition), 2014, 51(3):512-516.(in Chinese)

[5] 鄔海琴,王良民.基于連通支配集的無線傳感網(wǎng)top-k查詢最優(yōu)支撐樹研究[J].電子學(xué)報,2017, 45(1):119-127.

WU H Q, WANG L M. Connected dominating set based support-tree for top-kquery in wireless sensor networks[J]. Acta Electronica Sinica, 2017, 45(1):119-127. (in Chinese)

[6] 劉湘雯, 王良民. 數(shù)據(jù)發(fā)布匿名技術(shù)進展[J]. 江蘇大學(xué)學(xué)報(自然科學(xué)版), 2016, 37(5):562-571.

LIU X W, WANG L M. Advancement of anonymity technique for data publishing[J]. Journal of Jiangsu University (Natural Science Edition), 2016, 37(5):562-571. (in Chinese)

[7] 寧子嵐. 面向云存儲基于屬性的隱私保護算法[J]. 吉林大學(xué)學(xué)報(理學(xué)版), 2017, 55(4):921-926.

NING Z L. Attribute based privacy preserving algorithm for cloud storage[J]. Journal of Jilin University (Science Edition), 2017, 55(4):921-926.(in Chinese)

[8] AGRAWAL R, KIERNAN J, SRIKANT R, et al. Order preserving encryption for numeric data[C]∥Procee-dings of the 2004 ACM SIGMOD International Confe-rence on Management of Data. New York: ACM, 2004:563-574.

[9] BOLDYREVA A, CHENETTE N, LEE Y, et al. Order-preserving symmetric encryption[C]∥Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer Verlag, 2009: 224-241.

[10] POPA R A, LI F H, ZELDOVICH N. An ideal-security protocol for order-preserving encoding[C]∥Proceedings of the 2013 IEEE Symposium on Security and Privacy. New York: IEEE, 2013:463-477.

[11] KERSCHBAUM F, SCHR?PFER A. Optimal average-complexity ideal-security order-preserving encryption[C]∥Proceedings of the 21st ACM Conference on Computer and Communications Security. New York: ACM, 2014: 275-286.

[12] MALKIN T, TERANISHI I, YUNG M. Order-preserving encryption secure beyond one-wayness[C]∥Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer Verlag, 2014: 42-61.

[13] MAVROFORAKIS C, CHENETTE N, O′NEILL A, et al. Modular order-preserving encryption, revisited[C]∥Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2015: 763-777.

[14] LI K, ZHANG W M, YANG C, et al. Security analysis on one-to-many order preserving encryption based cloud data search[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(9): 1918-1926.

[15] LIU D X, WANG S L. Nonlinear order preserving index for encrypted database query in service cloud environments[J]. Concurrency and Computation: Practice and Experience, 2013, 25(13): 1967-1984.

[16] 黃汝維,桂小林,陳寧江,等.云計算環(huán)境中支持關(guān)系運算的加密算法[J].軟件學(xué)報,2015,26(5):1181-1195.

HUANG R W,GUI X L,CHEN N J, et al. Encryption algorithm supporting relational calculations in cloud computing[J]. Journal of Software, 2015, 26(5):1181-1195. (in Chinese)

[17] LIU Z L, CHEN X F, YANG J, et al. New order preserving encryption model for outsourced databases in cloud environments[J]. Journal of Network & Computer Applications, 2016, 59:198-207.