基于隨機(jī)函數(shù)的非線性映射保序加密方案

徐衍勝，張游杰

（1.山西軍躍邁科信息安全技術(shù)有限公司，太原 030006；2.太原鵬躍電子科技有限公司，太原 030032）

（*通信作者電子郵箱zyoujie@163.com）

0 引言

近年來(lái)，云計(jì)算以其動(dòng)態(tài)擴(kuò)展、按需服務(wù)、按量計(jì)費(fèi)等優(yōu)勢(shì)，吸引了眾多的企業(yè)關(guān)注［1］。在軟件即服務(wù)（Software as a Service，SaaS）成為應(yīng)用趨勢(shì)的大背景下，部署和虛擬化在云計(jì)算環(huán)境中的數(shù)據(jù)庫(kù)應(yīng)用也越來(lái)越廣泛［2］。與此同時(shí)，由于數(shù)據(jù)存儲(chǔ)在云端，用戶失去了對(duì)數(shù)據(jù)的直接控制，全部交由第三方云服務(wù)提供商進(jìn)行管理，敏感數(shù)據(jù)的安全性將難以得到保證，云環(huán)境下的數(shù)據(jù)安全以及隱私保護(hù)也成為一個(gè)重要問(wèn)題［3］。為保證數(shù)據(jù)安全性，一般采用加密的方法，將敏感數(shù)據(jù)加密后存入云服務(wù)器。但是，傳統(tǒng)的加密方法多數(shù)都不支持直接對(duì)密文的運(yùn)算［4］，如排序、范圍查詢等。在檢索時(shí)，必須將云端的大量數(shù)據(jù)傳輸?shù)奖镜?，極大削弱了云計(jì)算的優(yōu)勢(shì)和應(yīng)用范圍。

因此，研究既能保證數(shù)據(jù)安全性，又能為數(shù)據(jù)庫(kù)提供高性能檢索的數(shù)據(jù)加密方法，具有重要的意義。

1 相關(guān)工作

1.1 保序加密

保序加密方案（Order Preserving Encryption Scheme，OPES）最早由Agrawal 等在2004 年提出［5］，核心思想為擴(kuò)域映射，即將明文空間映射到一個(gè)更大域的密文空間。由于其密文值順序與明文值順序是一致的，因此可以支持對(duì)密文數(shù)據(jù)的最大值、最小值、范圍查詢，同時(shí)可以對(duì)密文數(shù)據(jù)執(zhí)行g(shù)roup by、order by 等操作。但是，由于數(shù)據(jù)的有序性，可以給攻擊者更多的背景知識(shí)。攻擊者可以通過(guò)獲取一些統(tǒng)計(jì)信息包括數(shù)據(jù)頻率和數(shù)據(jù)分布來(lái)進(jìn)行統(tǒng)計(jì)攻擊［6-7］。同時(shí)，該方法需要預(yù)先知道數(shù)據(jù)庫(kù)中所有被保護(hù)數(shù)據(jù)的值域。當(dāng)需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行插入操作時(shí)，該方法僅在理論上具備可行性［5，8］。

在OPES 基礎(chǔ)之上，為了從根本上提高保序加密（Order Preserving Encryption，OPE）的效率和安全性，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究［8-14］。如Boldyreva等［9］將OPES與超幾何和負(fù)超幾何分布相結(jié)合，提出了基于折半查找和超幾何概率分布的保序?qū)ΨQ加密方法。Krendelev 等［10］基于非退化矩陣概念，提出一種改進(jìn)的OPES。Martinez等［11］基于網(wǎng)格對(duì)角線劃分原理實(shí)現(xiàn)了保序密文生成。沈楠等［12］綜合運(yùn)用坐標(biāo)自動(dòng)網(wǎng)格化處理、保序加密機(jī)制、基于身份加密和完整性驗(yàn)證等多種密碼學(xué)手段，提出了基于保序加密的網(wǎng)格化位置隱私保護(hù)方案。

從現(xiàn)有研究成果來(lái)看，目前大部分保序加密方案不能隱藏原始數(shù)據(jù)分布的概率，容易遭受統(tǒng)計(jì)攻擊，存在安全隱患［13］。為了達(dá)到高安全性，許多保序加密方案需要通過(guò)使用額外的功能來(lái)隱藏密文的順序并且完成順序比較，但是這些額外的功能會(huì)導(dǎo)致效率的降低。

1.2 保序加密安全性

針對(duì)OPES 的安全性能，Boldyreva 等［14］提出一種新的安全性標(biāo)準(zhǔn)：等序明文不可區(qū)分IND-OCPA（INDistinguishability under Ordered Chosen Plaintext Attack）。該標(biāo)準(zhǔn)規(guī)定，保序加密理想的安全狀態(tài)等是等序明文不可區(qū)分，即：對(duì)于2 個(gè)序關(guān)系相同的明文，攻擊者無(wú)法區(qū)分加密后密文的序關(guān)系。根據(jù)該標(biāo)準(zhǔn)，經(jīng)過(guò)保序加密后，除了明文順序信息以外，不應(yīng)該暴露明文的其他信息。

1.3 線性加密與非線性加密

Liu 等［15］在2013 年首次提出線性加密的基本模型：ax+b+noise。但是該方案安全性很低，攻擊者只需要知道2 對(duì)明文和密文即可破解線性參數(shù)a和b。針對(duì)這種情況，Liu 等［15］進(jìn)一步提出了非線性加密模型af（x）+b+noise。該方法很好地彌補(bǔ)了線性加密的缺點(diǎn)，不會(huì)因?yàn)橹貜?fù)型數(shù)據(jù)而讓攻擊者估計(jì)a的大小。

在此基礎(chǔ)上，郁鵬等［6］提出了一種基于非線性映射的保序加密方案（nOPE）。該方案根據(jù)數(shù)據(jù)分布的疏密程度來(lái)將其劃分為多個(gè)不同的區(qū)間，通過(guò)分段函數(shù)來(lái)確定明文x所在的區(qū)間索引i，利用Enc(x)=aix3+bi+δi來(lái)實(shí)現(xiàn)加密。該方案在高效率的基礎(chǔ)上進(jìn)一步提高了安全性。但是，由于在實(shí)際使用中比較復(fù)雜，使其應(yīng)用范圍受到了限制。表現(xiàn)在：1）該方案需要預(yù)先知道數(shù)據(jù)集的分布情況，并據(jù)此劃分區(qū)間和設(shè)置參數(shù)；2）在原始數(shù)據(jù)集合中插入大量新的數(shù)據(jù)后，需要再次對(duì)數(shù)據(jù)集進(jìn)行區(qū)間劃分，并更改密鑰，重新進(jìn)行加密。

為解決這些問(wèn)題，兼顧安全性、高效性與易用性，本文提出一個(gè)基于隨機(jī)函數(shù)的非線性映射保序加密方案，命名為rnOPE。

2 算法模型

2.1 原理及系統(tǒng)構(gòu)成

本文方案的基本原理是將明文空間看作一個(gè)等差遞增數(shù)列，數(shù)列中每一個(gè)元素都映射到一個(gè)單獨(dú)的密文空間。在密文空間的順序與明文空間一致的情況下，利用隨機(jī)函數(shù)來(lái)保證密文空間與明文空間具有不同的分布特征。在加密時(shí)，只需從對(duì)應(yīng)的密文空間中隨機(jī)選取一個(gè)值即可作為其密文。

加密系統(tǒng){D，C，K，E}由明文空間D、密文空間C、密鑰K和加密算法E構(gòu)成。

明文空間D由長(zhǎng)度為L(zhǎng)的等差遞增數(shù)列{d1，d2，…，dL}構(gòu)成，公差為d，滿足以下條件：

密文空間C由L個(gè)長(zhǎng)度不同的空間Ci(i=1，2，…，L)構(gòu)成，每個(gè)空間Ci與D中的di一一對(duì)應(yīng)。C滿足以下條件：

其中：vj和vj+1是空間Cj對(duì)應(yīng)區(qū)間的最小值與最大值，{v1，v2，…，vL+1}是一個(gè)非等差的遞增數(shù)列，記為V。

密鑰K用于構(gòu)建密文空間C。

加密算法E用于實(shí)現(xiàn)di與Ci的對(duì)應(yīng)關(guān)系，并從對(duì)Ci中隨機(jī)選取一個(gè)值作為加密后的數(shù)據(jù)，滿足以下條件。

2.2 密文空間的計(jì)算

由式（2）可知，密文空間的計(jì)算過(guò)程實(shí)際上是一個(gè)確定遞增數(shù)列V的過(guò)程。為使加密前后的數(shù)據(jù)具有不同的統(tǒng)計(jì)特征，V中相鄰元素的差值（即Ci的長(zhǎng)度）應(yīng)具有非均勻分布的特征。計(jì)算過(guò)程如下。

1）初始化密鑰K。

①確定一個(gè)數(shù)值N，N≤L，并符合條件1的限制。條件1的定義見(jiàn)下文。

②確定一個(gè)用于構(gòu)造密鑰K的隨機(jī)數(shù)發(fā)生函數(shù)F（）。每次調(diào)用該函數(shù)都將產(chǎn)生一個(gè)隨機(jī)數(shù)字，這些隨機(jī)數(shù)字在N次內(nèi)應(yīng)具有非均勻分布的特征。為達(dá)此目的，可對(duì)一個(gè)均勻分布的隨機(jī)函數(shù)做非線性運(yùn)算，以破壞其分布特征。同時(shí)，明文空間D的各項(xiàng)參數(shù)及數(shù)值N也可以參與運(yùn)算，以便每個(gè)參數(shù)都可以對(duì)密鑰K產(chǎn)生作用。比如，本文中采用了以下公式：

其中：dL和d1分別是D的最大值和最小值，d是構(gòu)成D的等差數(shù)列的公差；rand（1，N）可隨機(jī)生成整數(shù)，0 ≤rand(1，N) ＜N；rand()可隨機(jī)生成實(shí)數(shù)，0 ≤rand() ＜1.0。

③連續(xù)調(diào)用N+1 次F（），生成數(shù)列R={r1，r2，…，rN+1}。數(shù)列R是一個(gè)非等差的遞增數(shù)列，該數(shù)列中每?jī)蓚€(gè)相鄰的元素構(gòu)成一個(gè)區(qū)間Ki(i=1，2，…，N)，進(jìn)而構(gòu)成密鑰K。K滿足以下條件。

2）利用密鑰K生成密文空間。

密文空間C的長(zhǎng)度L往往是一個(gè)非常大的數(shù)字。為了方便編程實(shí)現(xiàn)，設(shè)計(jì)一個(gè)函數(shù)G，在需要時(shí)臨時(shí)生成所需部分的區(qū)間。即

已知某數(shù)值x∈D，函數(shù)G(K，x)的實(shí)現(xiàn)方法如下：

①將明文空間D等分成N個(gè)長(zhǎng)度相同的明文區(qū)間Di(i=1，2，…，N)，作為明文區(qū)間初始值，并找出x所在的明文區(qū)間；將密鑰K作為密文區(qū)間初始值，Di與Ki(i=1，2，…，N)一一對(duì)應(yīng)。其中等分是指Di符合以下條件：a）D=；b）所有Di都由一個(gè)長(zhǎng)度為L(zhǎng)/N的等差數(shù)列構(gòu)成，公差均為d；c）Dj的最大值小于Dj+1的最小值，j=1，2，…，N-1。

②判斷x所在的明文區(qū)間中是否只有1個(gè)元素，如果是則此時(shí)對(duì)應(yīng)的密文區(qū)間即為輸出，否則執(zhí)行以下操作。

③將x所在的明文區(qū)間再次等分為N份，并在等分后的區(qū)間中找出x所在的區(qū)間；將對(duì)應(yīng)的密文區(qū)間也分為N份，保證與明文區(qū)間的對(duì)應(yīng)關(guān)系。其中，密文區(qū)間按密鑰K中每個(gè)元素的長(zhǎng)度比例來(lái)劃分。

④轉(zhuǎn)到步驟②。

根據(jù)此方法，規(guī)定條件1 為：N必須保證明文空間D中的任意元素在生成對(duì)應(yīng)的密文區(qū)間時(shí)，上述步驟執(zhí)行的順序和次數(shù)都相同。

該方法在計(jì)算機(jī)上的實(shí)現(xiàn)過(guò)程如下。

①定義參數(shù)及變量：（a）定義長(zhǎng)度為L(zhǎng)的明文空間D，確定其構(gòu)成參數(shù)dL、d1和d的值，并保證x∈D。其中dL和d1分別是D的最大值與最小值，d是構(gòu)成D的等差數(shù)列的公差。（b）定義常量N。（c）定義數(shù)組變量M，整數(shù)型變量index，實(shí)數(shù)型變量Mmax、Mmin、Vlen、Vmax和Vmin，用于計(jì)算過(guò)程中各個(gè)中間數(shù)據(jù)的存儲(chǔ)。在計(jì)算完成后，Vmax和Vmin用于記錄x對(duì)應(yīng)的密文區(qū)間，可記為［Vmin，Vmax）。

②將明文空D間平均分為N等份，使用變量M來(lái)表示。計(jì)算x在M中的索引，存入變量index，計(jì)算公式為index=。x所在的區(qū)間記為M［index］，最大值與最小值分別存入變量Mmax和Mmin，計(jì)算公式為Mmax=d1+(index+1)×(dL+d-d1)/N，Mmin=d1+index×(dL+d-d1)/N。對(duì)應(yīng)的密文區(qū)間V［index］的最大值與最小值分別存入變量Vmax和Vmin，計(jì)算公式為Vmax=rindex+2，Vmin=rindex+1。其中：rn(n=1，2，…，N+1)是數(shù)列R中的元素，函數(shù)Int()的作用為取整。以上表述中下標(biāo)全部從1開(kāi)始，index從0開(kāi)始，下同。

③如果Mmax-Mmin≤d，則認(rèn)為V[index]=[Vmin，Vmax)即是x所對(duì)應(yīng)的密文區(qū)間，可以結(jié)束運(yùn)算。

④如果Mmax-Mmin＞d，則執(zhí)行以下運(yùn)算。令M=M[index]，然后將區(qū)間M平均分為N等份，并繼續(xù)使用變量M來(lái)表示。計(jì)算x在M中的索引，存入變量index，計(jì)算公式為。x所在的區(qū)間記為M［index］，最大值與最小值分別存入變量Mmax和Mmin；對(duì)應(yīng)的密文區(qū)間變量V［index］的最大值與最小值分別存入變量Vmax和Vmin，計(jì)算公式為Vmax=Vmin+rindex+2×Vlen/(rN+1-r1)，Vmin=Vmin+rindex+1×Vlen/(rN+1-r1)。其中，Vlen=Vmax-Vmin，且Vlen必須在Vmax和Vmin之前進(jìn)行計(jì)算。

⑤轉(zhuǎn)到步驟③。

2.3 加密算法E的實(shí)現(xiàn)

加密算法E需要實(shí)現(xiàn)從明文空間D到密文空間C的映射，并從對(duì)應(yīng)的密文區(qū)間中隨機(jī)抽取一個(gè)值作為密文。公式為：

其中：Vmax、Vmin是由函數(shù)G(K，x)生成的密文區(qū)間的最大值與最小值，滿足[Vmin，Vmax)=G(K，x)；rand()可隨機(jī)生成實(shí)數(shù)，0 ≤rand() ＜1.0。

3 正確性與安全性分析

從正確性、IND-OCPA 安全和抗統(tǒng)計(jì)攻擊三方面對(duì)rnOPE進(jìn)行分析。

3.1 正確性分析

在明文空間D中任選兩個(gè)元素x1、x2，x1＜x2。如果有E(x1)＜E(x2)，則認(rèn)為方案是正確的。

下面對(duì)函數(shù)G(K，x)在計(jì)算機(jī)上的實(shí)現(xiàn)過(guò)程進(jìn)行分析。

假定：1）計(jì)算一個(gè)明文元素的密文空間需要n(n≥0)輪循環(huán)；第0輪循環(huán)對(duì)應(yīng)過(guò)程中的步驟2）。2）每輪循環(huán)中，x1對(duì)應(yīng)明文區(qū)間的索引記為index1，對(duì)應(yīng)密文區(qū)間的最大值記為Vmax1；x2對(duì)應(yīng)明文區(qū)間的索引記為index2，對(duì)應(yīng)密文區(qū)間的最小值記為Vmin2。

如果x1與x2在第0 輪循環(huán)處于不同的區(qū)間，則由步驟2）可知，index1 ＜index2，Vmax1=rindex1+2，Vmin2=rindex2+1。由于rindex1+2≤rindex2+1，所以：Vmax1≤Vmin2。

如果x1與x2在第m(m＞0)輪循環(huán)時(shí)處于不同的區(qū)間，則由步驟4）可知，index1 ＜index2，Vmax1=Vmin+rindex1+2×Vlen/(rN+1-r1)，Vmin2=Vmin+rindex2+1×Vlen/(rN+1-r1)，其中Vlen和Vmin分別是上一輪循環(huán)中x1與x2所對(duì)應(yīng)密文區(qū)間的長(zhǎng)度和最小值。由于rindex1+2≤rindex2+1，所以Vmax1≤Vmin2。

綜上所述，如果x1＜x2，則對(duì)應(yīng)的密文區(qū)間滿足條件Vmax1≤Vmin2。根據(jù)約定，區(qū)間包含最小值，不包含最大值。因此，由式（8）可知，E(x1)＜E(x2)。所以，rnOPE是正確的。

3.2 IND-OCPA安全

假設(shè)攻擊者能夠操縱客戶端，并且有順序關(guān)系完全相同的兩組數(shù)據(jù)集D1 和D2。攻擊者將這兩組數(shù)據(jù)發(fā)送至客戶端，操縱客戶端對(duì)其中一組進(jìn)行rnOPE 加密。如果攻擊者能夠通過(guò)分析加密結(jié)果來(lái)判斷客戶端加密了哪一組數(shù)據(jù)，則認(rèn)為rnOPE不滿足IND-OCPA；反之則認(rèn)為滿足IND-OCPA［8］。

攻擊者用于分辨客戶端加密了哪一組數(shù)據(jù)的條件有三種：根據(jù)密文順序判斷、根據(jù)單個(gè)密文值大小判斷和根據(jù)明文與密文值變化規(guī)律判斷。

對(duì)于根據(jù)密文順序判斷的情況：在rnOPE 方案中，對(duì)明文數(shù)據(jù)集中值不相等元素，對(duì)應(yīng)密文的順序與明文完全相同；對(duì)明文數(shù)據(jù)集中值相等元素，由于每個(gè)元素對(duì)應(yīng)的密文值是一個(gè)隨機(jī)數(shù)據(jù)，故其對(duì)應(yīng)密文的順序是隨機(jī)的。由于數(shù)據(jù)集D1和D2具有相同的順序關(guān)系，在這兩種情況下都無(wú)法由密文的順序判分辨出明文數(shù)據(jù)集。因此，根據(jù)密文順序進(jìn)行判斷的條件是不成立的。

對(duì)于根據(jù)單個(gè)密文值大小判斷的情況：由密鑰K的計(jì)算公式可知，大小與明文空間D的各項(xiàng)參數(shù)及數(shù)值N有關(guān)。在攻擊者不知道這些參數(shù)的情況下，無(wú)法由密文大小推斷出明文值的范圍。因此，根據(jù)密文值大小進(jìn)行判斷的條件也是不成立的。

對(duì)于根據(jù)明文與密文值變化規(guī)律判斷的情況：在本文方案中，無(wú)論是密文空間C的劃分，還是加密算法E的實(shí)現(xiàn)，全部通過(guò)隨機(jī)算法來(lái)隨機(jī)生成。按特定規(guī)律分布的明文在經(jīng)過(guò)加密后，除順序不變以外，將變得沒(méi)有規(guī)律。因此，根據(jù)明文與密文值變化規(guī)律判斷的條件也是不成立的。

由以上分析可知，兩組數(shù)據(jù)加密后，攻擊者無(wú)法判斷對(duì)哪一組數(shù)據(jù)進(jìn)行了加密。

同時(shí)，由密文空間的計(jì)算過(guò)程可知，對(duì)于?x∈D，對(duì)應(yīng)的密文空間構(gòu)造函數(shù)G(K，x)只與x在D中的位置有關(guān)，而與x本身的值無(wú)關(guān)。因此，通過(guò)rnOPE 加密后的結(jié)果，除順序信息外，不會(huì)暴露明文的其他信息，所以rnOPE 滿足IND-OCPA安全。

3.3 抗統(tǒng)計(jì)攻擊

假設(shè)攻擊者能夠操縱客戶端，并且已知某數(shù)據(jù)集中明文的數(shù)值以及各個(gè)明文的數(shù)量，攻擊者操縱客戶端將該數(shù)據(jù)集進(jìn)行加密后，存入數(shù)據(jù)庫(kù)。如攻擊者可以基于明文上的一些統(tǒng)計(jì)信息找到密文值和明文值之間的匹配，則認(rèn)為不能有效地抵抗統(tǒng)計(jì)攻擊。

統(tǒng)計(jì)攻擊發(fā)生在明文與密文一一對(duì)應(yīng)，且不會(huì)改變的情況下［8］。在rnOPE 方案中，由式（8）可知，同樣值的明文在每次加密時(shí)其結(jié)果是不同的。假設(shè)某數(shù)據(jù)集D1的長(zhǎng)度為L(zhǎng)1，某個(gè)值x在數(shù)據(jù)集D1 中出現(xiàn)的次數(shù)為Z（Z＞1），則其頻率為Pr(x)=，而對(duì)應(yīng)的密文值頻率為Pr(E(x))=。由此可看出，明文值和密文值的頻率明顯不同。因此，rnOPE 能夠有效地抵抗統(tǒng)計(jì)攻擊。

4 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證rnOPE 的性能，分別做了運(yùn)算性能實(shí)驗(yàn)和正確性與安全性實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為：Windows 10 操作系統(tǒng)，8 GB 運(yùn)行內(nèi)存，Intel Core i5-4660 CPU @3.20 GHz，開(kāi)發(fā)環(huán)境Visual.Net 2010，C#語(yǔ)言。

4.1 運(yùn)算性能實(shí)驗(yàn)

由密文空間的計(jì)算過(guò)程可知，運(yùn)算性能與明文空間D的范圍、公差d及密鑰K的長(zhǎng)度N有關(guān)。在實(shí)際應(yīng)用中，D的范圍與公差d的取值只要能保證要加密的數(shù)據(jù)集是D的子集即可?；诖?，實(shí)驗(yàn)方法如下。

明文空間D取值［0，109），公差d=1，長(zhǎng)度L=109。設(shè)計(jì)8組數(shù)據(jù)集X1、X2、…、X8，各組數(shù)據(jù)集的長(zhǎng)度依次為1×105，2×105，…，8×105，取值方式均為從1開(kāi)始依次遞增1的整數(shù)。對(duì)每組數(shù)據(jù)集，分別做三組實(shí)驗(yàn)，每組實(shí)驗(yàn)所用密鑰K的長(zhǎng)度N分別取102、104、106。每組數(shù)據(jù)集的實(shí)驗(yàn)過(guò)程為：首先隨機(jī)生成密鑰K；然后開(kāi)始計(jì)時(shí)，并開(kāi)始對(duì)數(shù)據(jù)集中的數(shù)據(jù)依次加密；數(shù)據(jù)全部加密完成后，記錄所用時(shí)間。結(jié)果見(jiàn)圖1。

由實(shí)驗(yàn)結(jié)果可知，在明文空間D不變的情況下，密鑰K的長(zhǎng)度越大，加密速度越快。當(dāng)密鑰K的長(zhǎng)度N固定時(shí)，所需時(shí)長(zhǎng)與加密數(shù)量呈線性關(guān)系。密鑰長(zhǎng)度為100 時(shí)，每加密10 萬(wàn)個(gè)數(shù)據(jù)耗時(shí)約47 ms；密鑰長(zhǎng)度為106時(shí)，每加密10 萬(wàn)個(gè)數(shù)據(jù)耗時(shí)約38 ms。

4.2 正確性與安全性實(shí)驗(yàn)

取某一個(gè)班級(jí)的學(xué)生總分成績(jī)作為數(shù)據(jù)集，長(zhǎng)度為37，數(shù)據(jù)的取值范圍在100～800。明文空間D取值［0，1 000）?？紤]到成績(jī)可能保留1 位小數(shù)，公差d設(shè)為0.1，以保證成績(jī)數(shù)據(jù)集包含在明文空間之內(nèi)。密鑰K的長(zhǎng)度N設(shè)定為20。對(duì)這組數(shù)據(jù)集采用rnOPE 進(jìn)行加密，對(duì)加密前后的數(shù)據(jù)進(jìn)行比較分析，結(jié)果見(jiàn)圖2～3。

圖2（a）給出了學(xué)生成績(jī)分布，圖2（b）給出了加密后的數(shù)據(jù)分布。通過(guò)對(duì)加密前后的數(shù)據(jù)進(jìn)行分析，可得出：

1）對(duì)于不同的成績(jī)，加密后的順序與加密前保持了一致。對(duì)于相同的成績(jī)，在加密后成為不同的數(shù)據(jù)。如圖2（b）中，有成績(jī)排名靠后的數(shù)據(jù)大于排名靠前數(shù)據(jù)的現(xiàn)象。這是因?yàn)檫@兩條數(shù)據(jù)在加密前相等，成績(jī)?nèi)珵?10，加密后的值分別為1.677E+09 和1.692E+09，后者大于前者。由此可知，該方案是正確的。

2）數(shù)據(jù)加密前后其分布差異很大。如圖2（b）與圖2（a）相比，在不考慮相同成績(jī)的情況下，兩者僅在趨勢(shì)上相同，都是呈下降趨勢(shì)。而從下降幅度來(lái)看，相鄰數(shù)據(jù)間的降幅差異巨大且無(wú)規(guī)律。因此，僅通過(guò)對(duì)密文數(shù)據(jù)的分析，很難推斷出除排名順序以外的其他信息。由此可知，該方案符合INDOCPA安全。

圖2 數(shù)據(jù)分布Fig.2 Data distribution map

圖3（a）給出了學(xué)生成績(jī)范圍統(tǒng)計(jì)分布，圖3（b）給出了加密后的范圍統(tǒng)計(jì)分布。通過(guò)對(duì)加密前后的統(tǒng)計(jì)分布進(jìn)行分析，可知：

加密前后的數(shù)據(jù)統(tǒng)計(jì)分布特征明顯不同：學(xué)生成績(jī)?cè)?00～400 分人數(shù)最多，為11 人；但加密后，在2.5E+09～3.0E+09 次數(shù)最多，為16。加密結(jié)果明顯地破壞了數(shù)據(jù)的統(tǒng)計(jì)分布特征。由此可知，該方案可以有效抵抗統(tǒng)計(jì)攻擊。

圖3 范圍統(tǒng)計(jì)分布圖Fig.3 Range statistical distribution map

4.3 方案比較

在效率、安全性、易用性方面，將本文所提的rnOPE 方案與文獻(xiàn)［6］所提的nOPE方案進(jìn)行對(duì)比：

1）在效率方面。rnOPE在密鑰長(zhǎng)度為106時(shí)，每加密10萬(wàn)個(gè)數(shù)據(jù)耗時(shí)約38 ms。nOPE 每加密十萬(wàn)個(gè)數(shù)據(jù)耗時(shí)約30 ms［6］?？紤]到文獻(xiàn)［6］未指明實(shí)驗(yàn)所需具體硬件環(huán)境，可以認(rèn)為，rnOPE 與nOPE 的加密運(yùn)算性能處于同一量級(jí)，執(zhí)行時(shí)間短、效率高［6］。

2）在安全性方面。rnOPE 達(dá)到了理想安全I(xiàn)ND-OCPA，并能有效抵抗統(tǒng)計(jì)攻擊；nOPE 只達(dá)到了IND-DNCPA（INDistinguishability under Distinct and Neighboring Chosen Plaintext Attack）［6］，同樣能有效抵抗統(tǒng)計(jì)攻擊。

3）在易用性方面。rnOPE 可采用任何計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)，可編程性強(qiáng)，同時(shí)參數(shù)設(shè)置簡(jiǎn)單，適應(yīng)性強(qiáng)；nOPE同樣可編程性強(qiáng)，但參數(shù)設(shè)置較為復(fù)雜，應(yīng)用范圍受到限制。

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

本文方案采用了一種不可逆的加密方法，不能提供解密功能。在實(shí)際應(yīng)用中，需要與已知的普通高安全加密算法如3DES（Triple Data Encryption Standard）、高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）等配合使用，以達(dá)到解密的目的。

針對(duì)本文方案的應(yīng)用場(chǎng)景，圖4 反映了數(shù)據(jù)提供者、云服務(wù)器、用戶之間的數(shù)據(jù)交互過(guò)程。過(guò)程如下：1）數(shù)據(jù)提供者分別使用保序加密算法E和普通加密算法E1 對(duì)數(shù)據(jù)集{d1，d2，…，dn}進(jìn)行加密，得到密文si和ev，并提交給云服務(wù)器存儲(chǔ)；2）用戶在得到數(shù)據(jù)提供者授權(quán)后，使用算法E對(duì)搜索條件參數(shù)param進(jìn)行加密，并且同計(jì)算要求type一起發(fā)送給云服務(wù)器；3）云服務(wù)器根據(jù)搜索條件，對(duì)si進(jìn)行檢索，并將對(duì)應(yīng)的ev返回給用戶；4）用戶對(duì)ev進(jìn)行解密，得到相應(yīng)的明文。

圖4 應(yīng)用場(chǎng)景Fig.4 Application scenario

在此過(guò)程中，使用了兩種加密算法，加密結(jié)果分別在數(shù)據(jù)表中占用2 個(gè)字段。其中保序加密算法E生成的密文si所在字段SafeIndex 主要用于檢索，可建立索引，可執(zhí)行范圍查詢、最大值、最小值、排序等檢索操作；普通加密算法E1生成的密文ev所在字段EncodedValue 不參與檢索操作，只將結(jié)果返回用戶，由用戶解密后得到明文。

6 結(jié)語(yǔ)

本文方案基于隨機(jī)函數(shù)，通過(guò)從明文空間到密文空間的非線性映射實(shí)現(xiàn)了保序加密。該方案具有三個(gè)特點(diǎn)：1）在保證密文空間與明文空間順序一致的同時(shí)，可有效破壞數(shù)據(jù)的分布特征，抵抗統(tǒng)計(jì)攻擊，并且達(dá)到了IND-OCPA 安全；2）每10 萬(wàn)個(gè)數(shù)據(jù)的平均加密時(shí)間在30 ms～50 ms，加密效率較高；3）方案不需要復(fù)雜的參數(shù)預(yù)設(shè)，且可以采用任何計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)，具有良好的易用性。綜上所述，本文方案較好地兼顧了安全、效率和易用性，配合常用的高安全加密算法，可適用于云環(huán)境下關(guān)系型數(shù)據(jù)庫(kù)中數(shù)值型數(shù)據(jù)的加密存儲(chǔ)。