孫彥珺，楊 庚，史經(jīng)啟，劉國秀

SUN Yanjun,YANG Geng,SHI Jingqi,LIU Guoxiu

南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，南京 210003

School of Computer Science&Technology,School of Software,Nanjing University of Posts and Telecommunications,Nanjing 210003,China

1 引言

隨著云計(jì)算技術(shù)的不斷發(fā)展，大量用戶數(shù)據(jù)被上傳并存儲(chǔ)在云端數(shù)據(jù)庫中。如何在有效利用這些數(shù)據(jù)的同時(shí)，保證用戶隱私信息的安全，成為加密算法的研究熱點(diǎn)之一。傳統(tǒng)數(shù)據(jù)加密方案雖然可以有效降低存儲(chǔ)在不可信服務(wù)器端機(jī)密信息的泄露，但由于無法直接對密文進(jìn)行有效操作，因而需要先在客戶端對密文解密后才能進(jìn)行相關(guān)計(jì)算，浪費(fèi)了云計(jì)算平臺(tái)的計(jì)算能力。一種可行方案是將保序加密OPE（Order-Preserving Encryption）方案與云計(jì)算平臺(tái)結(jié)合，允許用戶在云端直接對密文進(jìn)行特定計(jì)算。比較大小是數(shù)據(jù)庫中常見的操作，如對某列數(shù)據(jù)進(jìn)行比較、排序或范圍查詢等。OPE方案可以在提供較高安全保護(hù)級(jí)別的同時(shí)，為用戶提供基于云端密文的有效計(jì)算服務(wù)。

2004年Agrawal等[1]提出了一種對數(shù)值型數(shù)據(jù)進(jìn)行保序加密的方案（Order-Preserving Encryption Scheme，OPES），允許用戶直接對密文進(jìn)行比較操作，但該方案需要在已知明文的情況下預(yù)計(jì)分布，而且不能支持字符串等其他數(shù)據(jù)類型。2005年Li等[2]提出了前綴保留加密方案（PPE），能保證一定范圍內(nèi)的順序信息，但不能嚴(yán)格地保證順序大小，支持范圍查詢。2013年P(guān)opa等[3]提出的可變保序編碼（mutable Order-Preserving Encoding，mOPE），可以支持任意數(shù)據(jù)類型的保序加密，但在數(shù)據(jù)進(jìn)行插入刪除操作時(shí)效率較低。

本文基于廣義的平衡二叉搜索樹（AVL-N樹）提出了可變保序編碼方案（general mutable Order-Preserving Encoding，gmOPE），支持任意數(shù)據(jù)類型的保序加密，允許用戶自定義加密算法與調(diào)整策略，優(yōu)化了二叉樹重平衡調(diào)整與編碼更新算法，提高了數(shù)據(jù)插入刪除操作的效率。第2章對相關(guān)研究做出陳述；第3章描述mOPE方案的思路及缺陷；第4章提出改進(jìn)后的gmOPE方案，并對其進(jìn)行分析；第5章在理論上與現(xiàn)有方案對比分析gmOPE的算法性能和實(shí)用性；第6章實(shí)現(xiàn)兩種方案，并基于不同量級(jí)的數(shù)據(jù)集對兩者的性能測試對比分析；第7章對研究的內(nèi)容進(jìn)行總結(jié)。

2 相關(guān)研究

為方便衡量保序加密方案的安全性，Boldyreva等[4]介紹了一種新的OPE安全性標(biāo)準(zhǔn)IND-OCPA（indistinguishability under an Ordered Chosen Plaintext Attack），論證了如果僅假設(shè)一些具體的攻擊環(huán)境，無法達(dá)到保序加密所需要的安全性。Liu發(fā)表的文獻(xiàn)[5-6]，都利用加密函數(shù)Enc(v)=a×v+b+noise對明文v進(jìn)行加密，通過添加噪聲noise來提高其安全性。文獻(xiàn)[6]針對索引加密數(shù)據(jù)提出了一種非線性保序方案，允許用戶直接在密文數(shù)據(jù)庫中進(jìn)行范圍查詢。該方案不僅能夠保存明文的順序信息，還彌補(bǔ)了文獻(xiàn)[5]中線性保序索引方案的安全漏洞。

2013年文獻(xiàn)[7]提出可比較加密的概念，克服了保序加密的弱點(diǎn)，降低了加密數(shù)據(jù)公開的信息量，提高了CryptDB[8]和Monomi[9]的安全性。但該方案需要較大的密文長度，造成加密數(shù)據(jù)庫的性能下降，減少了實(shí)用性。第二年，F(xiàn)urukawa[10]提出一種基于記號(hào)的可比較加密方法（token-based short comparable encryption），通過比較密文對應(yīng)記號(hào)獲得密文順序信息，且密文長度較短。該方法對密文進(jìn)行不等于判斷時(shí)計(jì)算開銷較大，但結(jié)合索引技術(shù)可以縮短延遲。

上述的保序加密方案主要都針對特定的數(shù)據(jù)類型加密，Popa等[3]提出的mOPE是一種密文可變的保序加密方案，可以支持任意數(shù)據(jù)類型的保序加密，且不會(huì)泄露除明文順序以外的任何信息。該方案在插入明文前按順序?qū)?yīng)編碼，之后用任意的確定加密算法加密明文，再把密文與對應(yīng)編碼存儲(chǔ)在數(shù)據(jù)庫中。因此mOPE是一種保序編碼方案，而非保序加密方案。該方案利用二叉搜索樹的性質(zhì)對數(shù)據(jù)進(jìn)行編碼，再把加密后的數(shù)據(jù)與其對應(yīng)編碼同時(shí)存儲(chǔ)在數(shù)據(jù)庫中。當(dāng)對密文進(jìn)行比較操作時(shí)，在不解密的情況下，通過比較對應(yīng)的保序編碼獲取密文順序信息。然而因?yàn)樾枰ＷC二叉搜索樹的平衡性，在數(shù)據(jù)庫進(jìn)行大量插入或刪除操作時(shí)，會(huì)導(dǎo)致編碼的頻繁變更，給服務(wù)器帶來很大的開銷。

2015年，Boneh等[11]首次提出ORE方案（orderrevealing encryption），與OPE類似，直接通過密文獲得明文順序。該方案基于多重線性映射設(shè)計(jì)了第一個(gè)對密文進(jìn)行大小比較的ORE系統(tǒng)，可以提供“最大可能”的語義安全。并且數(shù)據(jù)不局限于數(shù)值型數(shù)據(jù)，與Pandey等[12]PPE方案思想類似，更具通用性。之后，Chenette等[13]基于偽隨機(jī)函數(shù)對優(yōu)化了ORE方案，提升了效率和安全性。2016年，Lewi等[14]提出了一種新的ORE方案，具有比現(xiàn)有OPE和ORE方案更強(qiáng)的安全性，并且加密速度更快，能夠有效抵御Naveed等[15]描述的推論攻擊。文獻(xiàn)[16]首先引入外包數(shù)據(jù)庫的系統(tǒng)模型，指出隱藏?cái)?shù)據(jù)分布和數(shù)據(jù)頻率的重要性，并基于此提出了一種新的簡單保序加密模型。

3 可變保序編碼mOPE加密方法

3.1 mOPE簡介

mOPE核心思想是利用平衡二叉搜索樹的結(jié)構(gòu)對密文數(shù)據(jù)進(jìn)行編碼。從根節(jié)點(diǎn)開始，記錄每個(gè)節(jié)點(diǎn)的路徑，并對二叉搜索樹的每個(gè)節(jié)點(diǎn)進(jìn)行二進(jìn)制編碼。密文數(shù)據(jù)存儲(chǔ)在不可信的數(shù)據(jù)庫中，當(dāng)可信的客戶端向其中插入新的數(shù)據(jù)時(shí)，通過一個(gè)交互方案，獲得新數(shù)據(jù)的插入位置。如果新數(shù)據(jù)的插入破壞原平衡二叉樹的平衡性，則需要重新調(diào)整新二叉搜索樹，以保證平衡二叉搜索樹的平衡性。

3.2 mOPE編碼原理闡述

可變保序編碼根據(jù)平衡二叉搜索樹的節(jié)點(diǎn)路徑進(jìn)行編碼，根據(jù)平衡二叉樹的重平衡特性實(shí)現(xiàn)可變性。

將明文數(shù)據(jù)v插入數(shù)據(jù)庫中邏輯平衡二叉樹的具體步驟可以歸納成算法1，具體描述如下（Cl表示客戶端Client，Ser表示服務(wù)器端Server）：

算法1遍歷平衡二叉搜索樹查找明文v的插入路徑

輸入：明文v

輸出：路徑path

（1）Cl? Ser：獲取OPE_Tree根節(jié)點(diǎn)的密文 c′，此時(shí)path為空字符串。

（2）Cl：用戶解密密文c′從而獲得加密前的明文v′。

（3）Cl?Ser：判斷待插入明文v與明文v′的大小關(guān)系。若 v＜v′，則向左進(jìn)行查找，path=path+“0”；若v=v′，則找到節(jié)點(diǎn)；若 v＞v′，則向右進(jìn)行查找，path=path+“1”。

（4）Ser：服務(wù)器基于用戶的反饋信息，返回下一個(gè)密文 c′，并執(zhí)行步驟（2）。

（5）Cl&Ser：當(dāng)找到v，或者服務(wù)器到達(dá)樹的一個(gè)空節(jié)點(diǎn)時(shí)，算法終止，返回路徑path。

如圖1所示，數(shù)據(jù)庫中存儲(chǔ)了69、32、20、10、25加密后的密文、對應(yīng)的編碼信息。當(dāng)插入新數(shù)據(jù)55時(shí)，按算法1的步驟操作，依次與32、69比較后得到插入位置的路徑path為10。根據(jù)路徑path進(jìn)行二進(jìn)制編碼，先在 path后補(bǔ)“1”，然后補(bǔ)“0”直到達(dá)到規(guī)定長度OPE_LENGTH，即為該節(jié)點(diǎn)的二進(jìn)制編碼。例如，55的編碼為[10]1。

通用編碼公式定義如下：

圖1 mOPE數(shù)據(jù)結(jié)構(gòu)概覽

3.3 mOPE平衡調(diào)整策略

重平衡算法由Server端定義UDFs實(shí)現(xiàn)。用戶在需要的時(shí)候向服務(wù)器發(fā)送UDFs請求，結(jié)合前文的交互實(shí)現(xiàn)重平衡。該算法具體描述如下：

算法2 mOPE重平衡算法

輸入：節(jié)點(diǎn)的路徑path

輸出：無

（1）根據(jù)路徑path，在OPE_Tree中從插入節(jié)點(diǎn)的父節(jié)點(diǎn)開始向根節(jié)點(diǎn)回溯。設(shè)當(dāng)前回溯節(jié)點(diǎn)為p。

（2）查詢數(shù)據(jù)庫得到節(jié)點(diǎn) p的高度h_root和左、右子樹的高度h_left、h_right。由于插入新節(jié)點(diǎn)后，節(jié)點(diǎn) p的高度可能會(huì)發(fā)生改變，記父節(jié)點(diǎn)新的高度h_root_new=max(h_left,h_right)+1。

（3）比較插入新節(jié)點(diǎn)前后節(jié)點(diǎn) p的高度h_root和h_root_new，判斷AVL樹平衡性。如果高度不變，說明AVL樹依然平衡，不需要重平衡，退出算法；否則，繼續(xù)（4）。

（4）判斷節(jié)點(diǎn) p的左、右子樹高度差值是否超過平衡因子，若超過則進(jìn)行（5），執(zhí)行“AVL旋轉(zhuǎn)”操作；否則更新節(jié)點(diǎn) p高度，繼續(xù)往上回溯：節(jié)點(diǎn) p指向當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)，轉(zhuǎn)（2）。

（5）對以節(jié)點(diǎn) p為根節(jié)點(diǎn)的子樹進(jìn)行“AVL旋轉(zhuǎn)”，更新相關(guān)節(jié)點(diǎn)的OPE編碼和高度Height，退出算法。

3.4 優(yōu)缺點(diǎn)分析

mOPE可達(dá)IND-OCPA安全等級(jí)，是一種安全、高效的交互性保序加密方案。平衡二叉樹是實(shí)現(xiàn)mOPE方案的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，但是嚴(yán)格維護(hù)其平衡性會(huì)引發(fā)高頻次的重平衡操作，嚴(yán)重降低算法效率，增加服務(wù)器計(jì)算開銷，當(dāng)數(shù)據(jù)庫中存儲(chǔ)大量數(shù)據(jù)時(shí)尤為明顯。如果適當(dāng)?shù)胤艑捚胶舛鏄浼s束條件，降低重平衡執(zhí)行次數(shù)，可以在不對密文操作造成較大影響的情況下，顯著降低服務(wù)器端的開銷。

4 gmOPE編碼方法

數(shù)據(jù)的插入操作主要分為兩部分：定位數(shù)據(jù)插入位置并計(jì)算保序編碼和保證邏輯二叉搜索樹的平衡性。階段1每次必須執(zhí)行，階段2則根據(jù)需要執(zhí)行，且階段2耗時(shí)較多，因此若能降低階段2的執(zhí)行頻次，就能顯著地提高數(shù)據(jù)插入的效率。本文通過放寬約束條件到N，將AVL擴(kuò)展為廣義平衡二叉樹AVL-N，降低重平衡頻次，提升算法效率。gmOPE基于廣義平衡二叉樹進(jìn)行編碼，使用“(N+2)+(N+3)”重構(gòu)算法替換“AVL旋轉(zhuǎn)”操作，因而比mOPE更具通用性。同時(shí)通過借助數(shù)據(jù)庫臨時(shí)表實(shí)現(xiàn)重排算法、設(shè)計(jì)正確且高效的編碼更新規(guī)范等方法對算法進(jìn)行優(yōu)化，進(jìn)一步提升算法整體效率。

4.1 平衡二叉樹的重平衡方法

保證二叉樹的平衡性，可以減少C/S交互次數(shù)，提高用戶查詢數(shù)據(jù)的效率。重平衡操作一般采用旋轉(zhuǎn)法，但旋轉(zhuǎn)調(diào)整的理論比較抽象，旋轉(zhuǎn)方向又各不相同，代碼量大且流程復(fù)雜，實(shí)際使用較為復(fù)雜。如果利用平衡二叉樹“中為根、小為左、大為右”的特性來重組失衡子樹，可以省去針對不同的失衡結(jié)構(gòu)采用不同的旋轉(zhuǎn)方法的復(fù)雜中間過程，使算法更為簡單。

文獻(xiàn)[17]提出了一種新的重平衡方法來替換“AVL旋轉(zhuǎn)”操作，當(dāng)平衡二叉樹出現(xiàn)失衡，只需要從失衡節(jié)點(diǎn)開始，向深度較深的子樹方向進(jìn)行搜索，就可以得到失衡節(jié)點(diǎn)、一個(gè)較深子節(jié)點(diǎn)和較深子節(jié)點(diǎn)的較深子節(jié)點(diǎn)。把這三個(gè)主干節(jié)點(diǎn)和四個(gè)從屬節(jié)點(diǎn)按照完全二叉樹的結(jié)構(gòu)進(jìn)行重新排列，就可以恢復(fù)平衡。

本文在此基礎(chǔ)上，擴(kuò)展為“(N+2)+(N+3)”重構(gòu)算法，并把該算法應(yīng)用于廣義的平衡二叉樹中，該樹允許用戶自定義平衡因子N，又稱為AVL-N樹，并用此優(yōu)化mOPE。擴(kuò)展后的重平衡算法主要由兩部分組成，算法3主要用于標(biāo)識(shí)、保存2N+5個(gè)失衡節(jié)點(diǎn)，并利用算法4自動(dòng)計(jì)算的失衡節(jié)點(diǎn)分類情況，把失衡樹重構(gòu)為完全二叉樹，其中N+2個(gè)節(jié)點(diǎn)稱為主干節(jié)點(diǎn)，主干節(jié)點(diǎn)對應(yīng)二叉樹OPE_Tree中單個(gè)節(jié)點(diǎn)；N+3個(gè)節(jié)點(diǎn)稱為從屬節(jié)點(diǎn)，從屬節(jié)點(diǎn)對應(yīng)OPE_Tree中的單個(gè)節(jié)點(diǎn)或某個(gè)子樹抽象而成的抽象子節(jié)點(diǎn)。之后更新各個(gè)節(jié)點(diǎn)的編碼和高度信息，以及N+3個(gè)抽象子節(jié)點(diǎn)下屬所有節(jié)點(diǎn)的編碼信息。算法4主要用于計(jì)算失衡節(jié)點(diǎn)對應(yīng)的分類情況，求出重排后完全二叉樹各節(jié)點(diǎn)相應(yīng)的編號(hào)，并存儲(chǔ)在數(shù)組index[]中。由于平衡二叉搜索樹是通過編碼OPE_encoding維護(hù)的邏輯二叉樹，因此對于節(jié)點(diǎn)左、右孩子及父節(jié)點(diǎn)的查找，可以直接通過路徑path定位到。該方法采用自動(dòng)計(jì)算分類的形式，流程簡單，易于操作。

當(dāng)N=1時(shí)，AVL-N樹的約束條件與普通的平衡二叉搜索樹相同。如圖2所示，圖中數(shù)字為節(jié)點(diǎn)編號(hào)，四幅圖中每幅圖的左側(cè)為失衡二叉樹，右側(cè)為重排后的結(jié)果。下面以第一類（對應(yīng)左旋）為例詳細(xì)講解重排過程。

圖2 四類重平衡情況示例

算法3 gmOPE重平衡算法-Rebalance

輸入：失衡節(jié)點(diǎn)的路徑path

輸出：無

（1）查找并保存失衡二叉樹的2N+5個(gè)節(jié)點(diǎn)信息。

①將失衡節(jié)點(diǎn)作為根節(jié)點(diǎn)，存入node[i](i=1)；

② 比較path+“0”節(jié)點(diǎn)和path+“1”節(jié)點(diǎn)的高度，高度較大的節(jié)點(diǎn)作為主干節(jié)點(diǎn)，較小的作為從屬節(jié)點(diǎn)。主干節(jié)點(diǎn)存入node[i+1]，從屬節(jié)點(diǎn)存入node[i+N+3]。i=i+1，若i＞N+1，轉(zhuǎn)④，否則轉(zhuǎn)③；

③將主干節(jié)點(diǎn)作為新根節(jié)點(diǎn)，并根據(jù)主干節(jié)點(diǎn)相對父節(jié)點(diǎn)的左右方向在path后補(bǔ)“0”或“1”，轉(zhuǎn)②；

④node[N+3]=新根節(jié)點(diǎn)的左孩子，node[2N+5]=新根節(jié)點(diǎn)的右孩子。

（2）構(gòu)建重排序完全二叉樹：根據(jù)失衡二叉樹和對應(yīng)的有序完全二叉樹構(gòu)建重排序完全二叉樹，得到廣度優(yōu)先遍歷重排序完全二叉樹節(jié)點(diǎn)數(shù)組index[]。

index[]=（算法 4）

（3）將失衡二叉樹按照重排序完全二叉樹重構(gòu)，更新節(jié)點(diǎn)編碼，詳見3.3節(jié)。

更新高度：由葉子節(jié)點(diǎn)開始向上，根據(jù)左右子節(jié)點(diǎn)高度計(jì)算并更新父節(jié)點(diǎn)高度h_root_new=max(h_left,h_right)+1，并向上回溯至重排序完全二叉樹根節(jié)點(diǎn)。

注：有序完全二叉樹是指按照廣度優(yōu)先遍歷方式遍歷二叉樹，得到的是有序數(shù)列。下文概念相同。

建立一個(gè)大小為8的節(jié)點(diǎn)指針數(shù)組node[8]收集并保存節(jié)點(diǎn)信息：0號(hào)節(jié)點(diǎn)為失衡節(jié)點(diǎn)的父節(jié)點(diǎn)，1號(hào)節(jié)點(diǎn)為失衡節(jié)點(diǎn)，2號(hào)節(jié)點(diǎn)為1號(hào)節(jié)點(diǎn)較深的子節(jié)點(diǎn)，5號(hào)節(jié)點(diǎn)為1號(hào)節(jié)點(diǎn)較淺的子節(jié)點(diǎn)。以此類推，直到所有失衡二叉樹節(jié)點(diǎn)都收集完成，采集到的節(jié)點(diǎn)數(shù)組為圖2中第一類對應(yīng)的編號(hào)。失衡節(jié)點(diǎn)的父節(jié)點(diǎn)可以通過路徑path去掉最后一位后往上回溯求得，與node[0]效果相同，因此文章不單獨(dú)列出node[0]，默認(rèn)為節(jié)點(diǎn)node[1]～node[2N+5]。之后根據(jù)算法4，求出重排后完全二叉樹各節(jié)點(diǎn)相應(yīng)的編號(hào)，生成重平衡后的廣度優(yōu)先遍歷數(shù)組index[]=[2，3，1，4，7，6，5]（詳細(xì)步驟見4.2節(jié)）。最終根據(jù)index[]數(shù)組即可重建平衡二叉搜索樹，并根據(jù)算法3更新AVL樹對應(yīng)數(shù)據(jù)項(xiàng)的編碼和高度，至此完成了一次重平衡操作。

4.2 構(gòu)建重排序二叉樹及改進(jìn)

當(dāng)N=1時(shí)重排后的完全二叉樹有4種類型，每種類型對應(yīng)的數(shù)組中包含7個(gè)編號(hào)元素；當(dāng)N=2時(shí)有8種類型，包含9個(gè)編號(hào)元素。以此類推，N越大對應(yīng)的分類情況越多，計(jì)算量也越大，人工難以勝任。因此結(jié)合算法4，采用自動(dòng)計(jì)算分類的形式，可以直接計(jì)算出失衡樹對應(yīng)的重排數(shù)組，簡化計(jì)算過程。算法4的主要功能是根據(jù)采集到的失衡樹節(jié)點(diǎn)，求出重排后的節(jié)點(diǎn)編號(hào)，構(gòu)建完全平衡二叉樹。具體算法內(nèi)容如下：

算法4

輸入：平衡約束N，收集的節(jié)點(diǎn)數(shù)組node[]

輸出：重排序完全二叉樹節(jié)點(diǎn)數(shù)組index[]

（1）中序遍歷（LDR）失衡樹，得到對應(yīng)的編號(hào)數(shù)組UBTArray[]。

（2）構(gòu)建包含2N+5個(gè)節(jié)點(diǎn)的有序的完全平衡二叉樹，中序遍歷完全二叉樹，得到完全二叉樹數(shù)組CBTArray[]。

（3）根據(jù)上面的兩個(gè)數(shù)組，構(gòu)建重排序完全二叉樹，得到對應(yīng)的廣度優(yōu)先遍歷數(shù)組index[]。

算法4由三部分組成，以第一類情況為例，說明重排過程。如圖3所示，中序遍歷失衡樹得到數(shù)組UBTArray[]=[4，3，7，2，6，1，5]，然后構(gòu)建包含 2N+5個(gè)節(jié)點(diǎn)的有序完全二叉樹并進(jìn)行中序遍歷，記為數(shù)組CBTArray[]=[4，2，5，1，6，3，7]。步驟（3）結(jié)合UBTArray[]和CBTArray[]，得到重排后的索引數(shù)組index[]=[2，3，1，4，7，6，5]，即為重排完全二叉樹的廣度優(yōu)先遍歷結(jié)果。結(jié)合路徑path和編碼OPE_encoding，在算法3中即可完成重平衡操作。

圖3 算法4講解圖例

算法4主要涉及數(shù)組操作和中序遍歷操作，在高級(jí)編程語言中實(shí)現(xiàn)較為簡單。由于算法4不涉及任何客戶端操作，同時(shí)為省去不必要的通信開銷，將算法4定義成數(shù)據(jù)庫UDF，借助數(shù)據(jù)庫臨時(shí)表實(shí)現(xiàn)重排算法。通過臨時(shí)表實(shí)現(xiàn)重排算法，使邏輯更加直觀簡潔，省去了構(gòu)建完全二叉樹和中序遍歷等操作，既簡化了算法步驟，又節(jié)省了計(jì)算時(shí)間，提升了算法效率。以圖2第一類情況說明UDF具體實(shí)現(xiàn)過程。

首先將節(jié)點(diǎn)node編號(hào)按采集順序依次存入臨時(shí)表（圖4（a））。OPE_LENGTH取值為4，將OPE_encoding的值與節(jié)點(diǎn)編號(hào)對應(yīng)存入表中。再將表格內(nèi)容按照OPE_encoding編碼大小排序，達(dá)到與中序遍歷相同的效果，node編號(hào)排序隨之改變。然后將中序遍歷有序完全二叉樹的結(jié)果數(shù)組CBTArray[]存入列CBT編號(hào)，如圖4（b）所示。最后將圖4（b）對列CBT編號(hào)執(zhí)行order by語句，即可得到圖4（c）中的結(jié)果，此時(shí)node編號(hào)列的內(nèi)容即為重排后的完全二叉樹廣度優(yōu)先遍歷的結(jié)果。之后按算法3的后續(xù)步驟即可完成一次重排序過程。改進(jìn)后的算法4借助數(shù)據(jù)庫臨時(shí)表，通過order by語句達(dá)到中序遍歷相同的效果，簡化了重新生成index[]數(shù)組的過程。

圖4 數(shù)據(jù)庫臨時(shí)表實(shí)現(xiàn)重排算法

4.3 更新從屬節(jié)點(diǎn)及子節(jié)點(diǎn)編碼

當(dāng)在執(zhí)行算法3的步驟（2）生成了重排序完全二叉樹之后，需要更新2N+5個(gè)失衡節(jié)點(diǎn)對應(yīng)的編碼和高度信息。對于重平衡后樹中節(jié)點(diǎn)的高度，根據(jù)調(diào)整后的二叉樹結(jié)構(gòu)，自底向上依次對各個(gè)節(jié)點(diǎn)進(jìn)行更新即可；而對于節(jié)點(diǎn)編碼，則要設(shè)計(jì)一種高效、正確的編碼更新規(guī)范。

由于節(jié)點(diǎn)路徑path發(fā)生變化，節(jié)點(diǎn)編碼OPE_encoding也隨之改變，并且改變前后的節(jié)點(diǎn)編碼均只與路徑path有關(guān)。將所有節(jié)點(diǎn)編碼拆分為前綴prefix和后綴suffix，前綴prefix由路徑path決定，后綴suffix由各節(jié)點(diǎn)在子樹內(nèi)部的具體路徑?jīng)Q定。定義編碼調(diào)整公式為：

其中new_len和old_len分別為新舊路徑的長度。

對整張表進(jìn)行編碼更新會(huì)明顯降低執(zhí)行效率，尤其是在數(shù)據(jù)庫中已經(jīng)存在大量數(shù)據(jù)記錄時(shí)。因此可以結(jié)合葉子節(jié)點(diǎn)對應(yīng)的編碼范圍[min，max]限定受影響的節(jié)點(diǎn)，從而在正確更新編碼的同時(shí)，保證編碼更新效率。

5 理論分析

5.1 gmOPE時(shí)間復(fù)雜度分析

本文介紹的mOPE方案和新提出的gmOPE方案，插入過程都主要分為兩個(gè)階段：階段1包括定位插入位置、計(jì)算OPE編碼、改寫SQL語句和向數(shù)據(jù)庫中插入密文記錄；階段2為檢查邏輯二叉樹是否失衡并觸發(fā)重平衡算法。

在第一階段，邏輯平衡二叉樹相關(guān)操作的時(shí)間復(fù)雜度最大?？蛻舳伺c服務(wù)器交互，找到待插入數(shù)據(jù)的位置。假設(shè)數(shù)據(jù)表中已經(jīng)存在n個(gè)數(shù)據(jù)項(xiàng)，由于兩種方案的實(shí)現(xiàn)方式均為平衡二叉樹，因此具有相似的時(shí)間復(fù)雜度?？蛻舳伺c服務(wù)器在最好情況下需要進(jìn)行(lbn」+1)次通信交互，以及相應(yīng)次數(shù)的加解密操作；而在最壞情況下，mOPE仍然為(lbn」+1)，gmOPE由于平衡因子由1擴(kuò)展到了N，因此需要多進(jìn)行N次交互操作，復(fù)雜度為 (lbn」+1)+N 。

在第二階段，所有操作均在服務(wù)器端進(jìn)行，因此沒有通信開銷，僅有平衡性檢測和重平衡開銷。兩種方案在每次插入數(shù)據(jù)后都調(diào)用UDF函數(shù)檢查平衡性，當(dāng)存在失衡節(jié)點(diǎn)時(shí)，可能會(huì)不斷回溯至根節(jié)點(diǎn)，即為最壞情況O(lbn)；當(dāng)二叉樹仍然平衡時(shí)，結(jié)束回溯操作，即為最好情況O(1)。gmOPE判斷失衡的方法與AVL方案一致，因此兩者時(shí)間復(fù)雜度相似。重平衡操作時(shí)，在最好情況下，gmOPE需要平衡包含空節(jié)點(diǎn)在內(nèi)的2N+5個(gè)節(jié)點(diǎn)，mOPE要平衡7個(gè)節(jié)點(diǎn)；最壞情況即為調(diào)整整個(gè)樹，兩者時(shí)間復(fù)雜度均為O(n)。

mOPE方法基于普通平衡二叉樹來編碼，大約每插入兩次數(shù)據(jù)就會(huì)觸發(fā)一次重平衡操作。而gmOPE基于廣義平衡二叉樹AVL-N來編碼，降低了插入數(shù)據(jù)時(shí)觸發(fā)重平衡操作的概率，N越大，觸發(fā)重平衡操作的概率就越低。假設(shè)插入相同的數(shù)據(jù)量為n，gmOPE重平衡操作的次數(shù)n2小于mOPE的n1，因此gmOPE的重平衡頻率 fg也小于mOPE的 fm，即 fg≤fm（ N=1時(shí)等號(hào)成立）。又因?yàn)閱未螘r(shí)間復(fù)雜度基本相同，所以gmOPE重平衡操作的平均時(shí)間復(fù)雜度更具優(yōu)勢。重平衡操作在整個(gè)插入過程中耗時(shí)最多，因而雖然單次插入操作時(shí)由于N的存在gmOPE時(shí)間復(fù)雜度略微高于mOPE，但多次插入時(shí)，由于gmOPE調(diào)整頻次比mOPE低得多，因此gmOPE整體時(shí)間復(fù)雜度更具優(yōu)勢。

在實(shí)際生產(chǎn)環(huán)境中，數(shù)據(jù)庫的記錄數(shù)n?N，因此N可以忽略不計(jì)，O(N)即為O(1)，見表1。

表1 mOPE與gmOPE時(shí)間復(fù)雜度比較

5.2 gmOPE實(shí)用性對比

2015年，Boneh等[11]首次提出了一種基于多重線性映射的保序加密概念ORE。該方案雖然為最新研究成果，為保序加密提供了新的研究思路，但在安全性方面仍有不足，且在應(yīng)用實(shí)現(xiàn)上有一定難度，而mOPE已經(jīng)在CryptDB[8]系統(tǒng)中得到實(shí)際應(yīng)用。本文在mOPE基礎(chǔ)上改進(jìn)提出的gmOPE方案，可以自定義UDFs函數(shù)配合現(xiàn)有數(shù)據(jù)庫使用，不需要對數(shù)據(jù)庫做定制，并能根據(jù)需要結(jié)合現(xiàn)有加密方案增強(qiáng)安全性，安全性達(dá)到INDOCPA等級(jí)，更好地應(yīng)用于實(shí)際生產(chǎn)環(huán)境。因此與ORE和mOPE相比，gmOPE兼顧了安全性與效率，可以在實(shí)際應(yīng)用中發(fā)揮其優(yōu)勢，見表2。

6 實(shí)驗(yàn)數(shù)據(jù)與分析

本文分別實(shí)現(xiàn)了mOPE和gmOPE，并且在相同的實(shí)驗(yàn)環(huán)境中對兩種方案分別進(jìn)行了測試。mOPE和gmOPE程序均為C/S結(jié)構(gòu)，分為客戶端和服務(wù)器端兩部分。客戶端使用Java實(shí)現(xiàn)，通過JDBC與服務(wù)器通信；Server端主要為MySQL數(shù)據(jù)庫。Server端數(shù)據(jù)庫為未經(jīng)修改的普通MySQL數(shù)據(jù)庫，包含用戶事先實(shí)現(xiàn)的自定義UDFs，用來實(shí)現(xiàn)邏輯二叉樹調(diào)整及編碼調(diào)整策略?？蛻舳顺绦蛑饕δ転槎ㄎ徊迦胛恢?、數(shù)據(jù)加解密等計(jì)算操作，Server端主要負(fù)責(zé)編碼的調(diào)整和邏輯二叉樹的維護(hù)。其中加解密算法為電子密碼本模式的分組AES加密算法，分組長度為128位。

6.1 實(shí)驗(yàn)平臺(tái)

硬件平臺(tái)主要為服務(wù)器節(jié)點(diǎn)。Server節(jié)點(diǎn)運(yùn)行數(shù)據(jù)庫及UDFs函數(shù)，配置為：CPU為Intel?Xeon E3-1225 v3，3.2 GHz/8 MB緩存；內(nèi)存為16 GB（2×8 GB）1 333 MHz Dual Ranked RDIM；硬盤為1 TB 3.5-inch 7.2 K RPM SATA II Hard Drive。軟件平臺(tái)：操作系統(tǒng)為：Centos 6.6，數(shù)據(jù)庫為mysql-5.1.73，JDK版本為64位1.7.0_45。

實(shí)驗(yàn)中將客戶端放置在服務(wù)器節(jié)點(diǎn)一同運(yùn)行程序，忽略客戶端和Server端的通信時(shí)延，主要對數(shù)據(jù)插入操作的性能進(jìn)行分析對比。

數(shù)據(jù)集：mOPE和gmOPE采用同一數(shù)據(jù)集，為使用Python隨機(jī)生成的包含5 000條不重復(fù)的整數(shù)型數(shù)據(jù)的數(shù)據(jù)集Data{r1，r2，…，r5 000}，滿足對任意 i,j，ri≠rj，ri與rj的大小關(guān)系隨機(jī)。

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

分別對mOPE和gmOPE中AVL-N 樹 N 為1、2、3、4、5五種情況下的方案進(jìn)行測試，比較它們的性能差別，分析在不同情況下插入不同數(shù)據(jù)量的明文數(shù)據(jù)所需的時(shí)間以及觸發(fā)重平衡操作的次數(shù)。

6.2.1 調(diào)整時(shí)間

圖5為兩個(gè)階段總的時(shí)間消耗隨插入數(shù)據(jù)量的變化，包括階段1中的計(jì)算時(shí)間和數(shù)據(jù)庫插入耗時(shí)，階段2中調(diào)用UDF函數(shù)檢查二叉樹平衡性并重新調(diào)整二叉樹和編碼。其中階段1的計(jì)算量主要由查找明文插入位置、加解密操作、重寫SQL語句和數(shù)據(jù)庫插入操作組成，mOPE和gmOPE的每一次插入操作均必須經(jīng)過階段1的所有步驟，因此兩種方案在階段1的耗時(shí)基本相同。且gmOPE方案中N的增大并未對階段1的耗時(shí)造成明顯影響。圖6為階段1的耗時(shí)隨插入數(shù)據(jù)量的變化。在插入5 000條數(shù)據(jù)的時(shí)候，mOPE和gmOPE在N取不同值時(shí)階段1耗時(shí)均約為139 s，其中計(jì)算時(shí)間約為15 s，插入耗時(shí)約為124 s。

表2 OPE/ORE方案對比分析

階段1的操作為mOPE和gmOPE的共同部分，時(shí)間消耗基本一致，兩者時(shí)間開銷的差別主要集中在階段2的二叉樹重平衡操作部分，因此下面重點(diǎn)分析兩者在階段2的時(shí)間差別，對比分析兩者的性能。

圖7為階段2的耗時(shí)隨插入數(shù)據(jù)量的變化，觀察可知兩個(gè)方案均具有穩(wěn)定性，調(diào)整時(shí)間隨數(shù)據(jù)量的增加穩(wěn)定增長，沒有出現(xiàn)因?yàn)閿?shù)據(jù)量的增加而導(dǎo)致操作時(shí)間急劇增長的情況。gmOPE在N=1的時(shí)候即為普通的AVL樹，與mOPE效果一樣：兩者觸發(fā)重平衡操作的頻次如圖8所示，完全一致；由于gmOPE具有通用性，在收集失衡節(jié)點(diǎn)及二叉樹調(diào)整等操作步驟的時(shí)候比AVL復(fù)雜，因此調(diào)整操作比mOPE耗時(shí)多，實(shí)驗(yàn)顯示插入5 000條數(shù)據(jù)，gmOPE（1）階段 2耗時(shí)比 mOPE多出24.6%。但隨著N的增大，gmOPE在插入數(shù)據(jù)過程中觸發(fā)重平衡操作的次數(shù)顯著下降，重平衡操作的總耗時(shí)也隨之下降。雖然單次二叉樹調(diào)整操作gmOPE耗時(shí)比mOPE多，但因?yàn)間mOPE調(diào)整頻次顯著下降，因而gmOPE在N≥2時(shí)的整體效率優(yōu)于mOPE。結(jié)果顯示，在N=2～5時(shí)，gmOPE在階段2中調(diào)整操作的耗時(shí)比mOPE節(jié)省約2.8%～34.8%。當(dāng)N取值為5時(shí)，gmOPE階段2效率比mOPE提升約53.3%，整體效率提升約40.4%。并且隨著N的繼續(xù)增大，gmOPE效率提升會(huì)更加顯著。

6.2.2 調(diào)整頻次

圖8描述的是兩種方案在插入不同數(shù)據(jù)量的數(shù)據(jù)時(shí)所觸發(fā)的重平衡操作的次數(shù)，gmOPE在N=1時(shí)AVL-N即為普通的AVL樹，調(diào)整次數(shù)與mOPE完全一致。隨著N的增大，gmOPE的重平衡次數(shù)具有越來越明顯的優(yōu)勢：當(dāng) N=2時(shí)，gmOPE的調(diào)整次數(shù)僅為mOPE的50.7%；N=3時(shí)，gmOPE的調(diào)整次數(shù)已經(jīng)下降為mOPE的22.2%。

圖5 插入數(shù)據(jù)量與總的時(shí)間消耗

圖6 插入數(shù)據(jù)量與階段1的耗時(shí)

圖7 插入數(shù)據(jù)量與階段2的耗時(shí)

圖8 插入數(shù)據(jù)量和觸發(fā)重平衡操作的次數(shù)

圖9是當(dāng)用戶向數(shù)據(jù)庫中插入5 000條數(shù)據(jù)時(shí)，觸發(fā)重平衡操作的次數(shù)隨廣義平衡二叉樹中N的大小的變化關(guān)系。從圖中可以看出，在gmOPE方案中，隨平衡因子N的增大，觸發(fā)重平衡的操作次數(shù)有顯著的降低。當(dāng)N=11時(shí)，插入同樣的數(shù)據(jù)量，gmOPE的重平衡次數(shù)只有mOPE的千分之一。

圖9 平衡因子N與插入數(shù)據(jù)時(shí)觸發(fā)重平衡操作的次數(shù)

7 小結(jié)

本文利用廣義的平衡二叉搜索樹，實(shí)現(xiàn)了可變保序編碼方案gmOPE，并取得了較為理想的實(shí)驗(yàn)結(jié)果。把該保序加密方案運(yùn)用在數(shù)據(jù)加密系統(tǒng)中，可以讓客戶端能直接對密文數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行檢索等操作，且支持任意類型數(shù)據(jù)的保序加密。gmOPE加密方案允許用戶自定義平衡約束條件，采用新型的重平衡調(diào)整方法，既保證了保序加密方案的可變性，又減少了重平衡的次數(shù)，提高了效率。實(shí)驗(yàn)結(jié)果表明，gmOPE整體效率得到大幅提升，在N=5時(shí)，整體效率提升約40.4%。

參考文獻(xiàn)：

[1]Agrawal R，Kiernan J，Srikant R，et al.Order preserving encryption for numeric data[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data，2004：563-574.

[2]Li J，Omiecinski E R.Efficiency and security trade-off in supporting range queries on encrypted databases[C]//IFIP Annual Conference on Data and Applications Security and Privacy，2005：69-83.

[3]Popa R A，Li F H，Zeldovich N.An ideal-security protocol for order-preserving encoding[C]//2013 IEEE Symposium on Security and Privacy，2013：463-477.

[4]Boldyreva A，Chenette N，Lee Y，et al.Order-preserving symmetric encryption[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques，2009：224-241.

[5]Liu D，Wang S.Programmable order-preserving secure index for encrypted database query[C]//2012 IEEE Fifth International Conference on Cloud Computing，2012：502-509.

[6]Liu D，Wang S.Nonlinear order preserving index for encrypted database query in service cloud environments[J].Concurrency and Computation：Practice and Experience，2013，25（13）：1967-1984.

[7]Furukawa J.Request-based comparable encryption[C]//European Symposium on Research in Computer Security，2013：129-146.

[8]Popa R A，Redfield C，Zeldovich N，et al.CryptDB：Protecting confidentiality with encrypted query processing[C]//Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles，2011：85-100.

[9]Tu S，Kaashoek M F，Madden S，et al.Processing analytical queries over encrypted data[J].Proceedings of VLDB Endowment，2013，6（5）：289-300.

[10]Furukawa J.Short comparable encryption[C]//International Conference on Cryptology and Network Security，2014：337-352.

[11]Boneh D，Lewi K，Raykova M，et al.Semantically secure order-revealing encryption：Multi-input functional encryption without obfuscation[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques，2015：563-594.

[12]Pandey O，Rouselakis Y.Property preserving symmetric encryption[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques，2012：375-391.

[13]Chenette N，Lewi K，Weis S A，et al.Practical orderrevealing encryption with limited leakage[C]//Proceedings of the 23rd International Conference on Fast Software Encryption（IACR-FSE），2016：474-493.

[14]Lewi K，Wu D J.Order-revealing encryption：New constructions，applications，and lower bounds[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security，2016：1167-1178.

[15]Naveed M，Kamara S，Wright C V.Inference attacks on property-preserving encrypted databases[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security，2015：644-655.

[16]Liu Z，Chen X，Yang J，et al.New order preserving encryption model for outsourced databases in cloud environments[J].Journal of Network and Computer Applications，2016，59：198-207.

[17]江順亮，胡世鴻，唐祎玲，等.低調(diào)整率的廣義AVL樹及其統(tǒng)一重平衡方法[J].計(jì)算機(jī)應(yīng)用，2015，35（3）：654-658.