基于隨機函數的非線性映射保序加密方案

徐衍勝，張游杰

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

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

0 引言

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

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

1 相關工作

1.1 保序加密

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

在OPES 基礎之上，為了從根本上提高保序加密（Order Preserving Encryption，OPE）的效率和安全性，國內外學者進行了大量的研究［8-14］。如Boldyreva等［9］將OPES與超幾何和負超幾何分布相結合，提出了基于折半查找和超幾何概率分布的保序對稱加密方法。Krendelev 等［10］基于非退化矩陣概念，提出一種改進的OPES。Martinez等［11］基于網格對角線劃分原理實現了保序密文生成。沈楠等［12］綜合運用坐標自動網格化處理、保序加密機制、基于身份加密和完整性驗證等多種密碼學手段，提出了基于保序加密的網格化位置隱私保護方案。

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

1.2 保序加密安全性

針對OPES 的安全性能，Boldyreva 等［14］提出一種新的安全性標準：等序明文不可區分IND-OCPA（INDistinguishability under Ordered Chosen Plaintext Attack）。該標準規定，保序加密理想的安全狀態等是等序明文不可區分，即：對于2 個序關系相同的明文，攻擊者無法區分加密后密文的序關系。根據該標準，經過保序加密后，除了明文順序信息以外，不應該暴露明文的其他信息。

1.3 線性加密與非線性加密

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

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

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

2 算法模型

2.1 原理及系統構成

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

加密系統{D，C，K，E}由明文空間D、密文空間C、密鑰K和加密算法E構成。

明文空間D由長度為L的等差遞增數列{d1，d2，…，dL}構成，公差為d，滿足以下條件：

密文空間C由L個長度不同的空間Ci(i=1，2，…，L)構成，每個空間Ci與D中的di一一對應。C滿足以下條件：

其中：vj和vj+1是空間Cj對應區間的最小值與最大值，{v1，v2，…，vL+1}是一個非等差的遞增數列，記為V。

密鑰K用于構建密文空間C。

加密算法E用于實現di與Ci的對應關系，并從對Ci中隨機選取一個值作為加密后的數據，滿足以下條件。

2.2 密文空間的計算

由式（2）可知，密文空間的計算過程實際上是一個確定遞增數列V的過程。為使加密前后的數據具有不同的統計特征，V中相鄰元素的差值（即Ci的長度）應具有非均勻分布的特征。計算過程如下。

1）初始化密鑰K。

①確定一個數值N，N≤L，并符合條件1的限制。條件1的定義見下文。

②確定一個用于構造密鑰K的隨機數發生函數F（）。每次調用該函數都將產生一個隨機數字，這些隨機數字在N次內應具有非均勻分布的特征。為達此目的，可對一個均勻分布的隨機函數做非線性運算，以破壞其分布特征。同時，明文空間D的各項參數及數值N也可以參與運算，以便每個參數都可以對密鑰K產生作用。比如，本文中采用了以下公式：

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

③連續調用N+1 次F（），生成數列R={r1，r2，…，rN+1}。數列R是一個非等差的遞增數列，該數列中每兩個相鄰的元素構成一個區間Ki(i=1，2，…，N)，進而構成密鑰K。K滿足以下條件。

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

密文空間C的長度L往往是一個非常大的數字。為了方便編程實現，設計一個函數G，在需要時臨時生成所需部分的區間。即

已知某數值x∈D，函數G(K，x)的實現方法如下：

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

②判斷x所在的明文區間中是否只有1個元素，如果是則此時對應的密文區間即為輸出，否則執行以下操作。

③將x所在的明文區間再次等分為N份，并在等分后的區間中找出x所在的區間；將對應的密文區間也分為N份，保證與明文區間的對應關系。其中，密文區間按密鑰K中每個元素的長度比例來劃分。

④轉到步驟②。

根據此方法，規定條件1 為：N必須保證明文空間D中的任意元素在生成對應的密文區間時，上述步驟執行的順序和次數都相同。

該方法在計算機上的實現過程如下。

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

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

③如果Mmax-Mmin≤d，則認為V[index]=[Vmin，Vmax)即是x所對應的密文區間，可以結束運算。

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

⑤轉到步驟③。

2.3 加密算法E的實現

加密算法E需要實現從明文空間D到密文空間C的映射，并從對應的密文區間中隨機抽取一個值作為密文。公式為：

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

3 正確性與安全性分析

從正確性、IND-OCPA 安全和抗統計攻擊三方面對rnOPE進行分析。

3.1 正確性分析

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

下面對函數G(K，x)在計算機上的實現過程進行分析。

假定：1）計算一個明文元素的密文空間需要n(n≥0)輪循環；第0輪循環對應過程中的步驟2）。2）每輪循環中，x1對應明文區間的索引記為index1，對應密文區間的最大值記為Vmax1；x2對應明文區間的索引記為index2，對應密文區間的最小值記為Vmin2。

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

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

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

3.2 IND-OCPA安全

假設攻擊者能夠操縱客戶端，并且有順序關系完全相同的兩組數據集D1 和D2。攻擊者將這兩組數據發送至客戶端，操縱客戶端對其中一組進行rnOPE 加密。如果攻擊者能夠通過分析加密結果來判斷客戶端加密了哪一組數據，則認為rnOPE不滿足IND-OCPA；反之則認為滿足IND-OCPA［8］。

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

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

對于根據單個密文值大小判斷的情況：由密鑰K的計算公式可知，大小與明文空間D的各項參數及數值N有關。在攻擊者不知道這些參數的情況下，無法由密文大小推斷出明文值的范圍。因此，根據密文值大小進行判斷的條件也是不成立的。

對于根據明文與密文值變化規律判斷的情況：在本文方案中，無論是密文空間C的劃分，還是加密算法E的實現，全部通過隨機算法來隨機生成。按特定規律分布的明文在經過加密后，除順序不變以外，將變得沒有規律。因此，根據明文與密文值變化規律判斷的條件也是不成立的。

由以上分析可知，兩組數據加密后，攻擊者無法判斷對哪一組數據進行了加密。

同時，由密文空間的計算過程可知，對于?x∈D，對應的密文空間構造函數G(K，x)只與x在D中的位置有關，而與x本身的值無關。因此，通過rnOPE 加密后的結果，除順序信息外，不會暴露明文的其他信息，所以rnOPE 滿足IND-OCPA安全。

3.3 抗統計攻擊

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

統計攻擊發生在明文與密文一一對應，且不會改變的情況下［8］。在rnOPE 方案中，由式（8）可知，同樣值的明文在每次加密時其結果是不同的。假設某數據集D1的長度為L1，某個值x在數據集D1 中出現的次數為Z（Z＞1），則其頻率為Pr(x)=，而對應的密文值頻率為Pr(E(x))=。由此可看出，明文值和密文值的頻率明顯不同。因此，rnOPE 能夠有效地抵抗統計攻擊。

4 實驗與結果分析

為驗證rnOPE 的性能，分別做了運算性能實驗和正確性與安全性實驗。實驗環境為：Windows 10 操作系統，8 GB 運行內存，Intel Core i5-4660 CPU @3.20 GHz，開發環境Visual.Net 2010，C#語言。

4.1 運算性能實驗

由密文空間的計算過程可知，運算性能與明文空間D的范圍、公差d及密鑰K的長度N有關。在實際應用中，D的范圍與公差d的取值只要能保證要加密的數據集是D的子集即可。基于此，實驗方法如下。

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

由實驗結果可知，在明文空間D不變的情況下，密鑰K的長度越大，加密速度越快。當密鑰K的長度N固定時，所需時長與加密數量呈線性關系。密鑰長度為100 時，每加密10 萬個數據耗時約47 ms；密鑰長度為106時，每加密10 萬個數據耗時約38 ms。

4.2 正確性與安全性實驗

取某一個班級的學生總分成績作為數據集，長度為37，數據的取值范圍在100～800。明文空間D取值［0，1 000）。考慮到成績可能保留1 位小數，公差d設為0.1，以保證成績數據集包含在明文空間之內。密鑰K的長度N設定為20。對這組數據集采用rnOPE 進行加密，對加密前后的數據進行比較分析，結果見圖2～3。

圖2（a）給出了學生成績分布，圖2（b）給出了加密后的數據分布。通過對加密前后的數據進行分析，可得出：

1）對于不同的成績，加密后的順序與加密前保持了一致。對于相同的成績，在加密后成為不同的數據。如圖2（b）中，有成績排名靠后的數據大于排名靠前數據的現象。這是因為這兩條數據在加密前相等，成績全為210，加密后的值分別為1.677E+09 和1.692E+09，后者大于前者。由此可知，該方案是正確的。

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

圖2 數據分布Fig.2 Data distribution map

圖3（a）給出了學生成績范圍統計分布，圖3（b）給出了加密后的范圍統計分布。通過對加密前后的統計分布進行分析，可知：

加密前后的數據統計分布特征明顯不同：學生成績在300～400 分人數最多，為11 人；但加密后，在2.5E+09～3.0E+09 次數最多，為16。加密結果明顯地破壞了數據的統計分布特征。由此可知，該方案可以有效抵抗統計攻擊。

圖3 范圍統計分布圖Fig.3 Range statistical distribution map

4.3 方案比較

在效率、安全性、易用性方面，將本文所提的rnOPE 方案與文獻［6］所提的nOPE方案進行對比：

1）在效率方面。rnOPE在密鑰長度為106時，每加密10萬個數據耗時約38 ms。nOPE 每加密十萬個數據耗時約30 ms［6］。考慮到文獻［6］未指明實驗所需具體硬件環境，可以認為，rnOPE 與nOPE 的加密運算性能處于同一量級，執行時間短、效率高［6］。

2）在安全性方面。rnOPE 達到了理想安全IND-OCPA，并能有效抵抗統計攻擊；nOPE 只達到了IND-DNCPA（INDistinguishability under Distinct and Neighboring Chosen Plaintext Attack）［6］，同樣能有效抵抗統計攻擊。

3）在易用性方面。rnOPE 可采用任何計算機語言實現，可編程性強，同時參數設置簡單，適應性強；nOPE同樣可編程性強，但參數設置較為復雜，應用范圍受到限制。

5 應用場景

本文方案采用了一種不可逆的加密方法，不能提供解密功能。在實際應用中，需要與已知的普通高安全加密算法如3DES（Triple Data Encryption Standard）、高級加密標準（Advanced Encryption Standard，AES）等配合使用，以達到解密的目的。

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

圖4 應用場景Fig.4 Application scenario

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

6 結語

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