用戶可自定義的低調整率保序加密算法

孫彥珺，楊 庚，史經啟，劉國秀

SUN Yanjun,YANG Geng,SHI Jingqi,LIU Guoxiu

南京郵電大學 計算機學院、軟件學院，南京 210003

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

1 引言

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

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

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

2 相關研究

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

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

上述的保序加密方案主要都針對特定的數據類型加密，Popa等[3]提出的mOPE是一種密文可變的保序加密方案，可以支持任意數據類型的保序加密，且不會泄露除明文順序以外的任何信息。該方案在插入明文前按順序對應編碼，之后用任意的確定加密算法加密明文，再把密文與對應編碼存儲在數據庫中。因此mOPE是一種保序編碼方案，而非保序加密方案。該方案利用二叉搜索樹的性質對數據進行編碼，再把加密后的數據與其對應編碼同時存儲在數據庫中。當對密文進行比較操作時，在不解密的情況下，通過比較對應的保序編碼獲取密文順序信息。然而因為需要保證二叉搜索樹的平衡性，在數據庫進行大量插入或刪除操作時，會導致編碼的頻繁變更，給服務器帶來很大的開銷。

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

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

3.1 mOPE簡介

mOPE核心思想是利用平衡二叉搜索樹的結構對密文數據進行編碼。從根節點開始，記錄每個節點的路徑，并對二叉搜索樹的每個節點進行二進制編碼。密文數據存儲在不可信的數據庫中，當可信的客戶端向其中插入新的數據時，通過一個交互方案，獲得新數據的插入位置。如果新數據的插入破壞原平衡二叉樹的平衡性，則需要重新調整新二叉搜索樹，以保證平衡二叉搜索樹的平衡性。

3.2 mOPE編碼原理闡述

可變保序編碼根據平衡二叉搜索樹的節點路徑進行編碼，根據平衡二叉樹的重平衡特性實現可變性。

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

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

輸入：明文v

輸出：路徑path

（1）Cl? Ser：獲取OPE_Tree根節點的密文 c′，此時path為空字符串。

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

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

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

（5）Cl&Ser：當找到v，或者服務器到達樹的一個空節點時，算法終止，返回路徑path。

如圖1所示，數據庫中存儲了69、32、20、10、25加密后的密文、對應的編碼信息。當插入新數據55時，按算法1的步驟操作，依次與32、69比較后得到插入位置的路徑path為10。根據路徑path進行二進制編碼，先在 path后補“1”，然后補“0”直到達到規定長度OPE_LENGTH，即為該節點的二進制編碼。例如，55的編碼為[10]1。

通用編碼公式定義如下：

圖1 mOPE數據結構概覽

3.3 mOPE平衡調整策略

重平衡算法由Server端定義UDFs實現。用戶在需要的時候向服務器發送UDFs請求，結合前文的交互實現重平衡。該算法具體描述如下：

算法2 mOPE重平衡算法

輸入：節點的路徑path

輸出：無

（1）根據路徑path，在OPE_Tree中從插入節點的父節點開始向根節點回溯。設當前回溯節點為p。

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

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

（4）判斷節點 p的左、右子樹高度差值是否超過平衡因子，若超過則進行（5），執行“AVL旋轉”操作；否則更新節點 p高度，繼續往上回溯：節點 p指向當前節點父節點，轉（2）。

（5）對以節點 p為根節點的子樹進行“AVL旋轉”，更新相關節點的OPE編碼和高度Height，退出算法。

3.4 優缺點分析

mOPE可達IND-OCPA安全等級，是一種安全、高效的交互性保序加密方案。平衡二叉樹是實現mOPE方案的關鍵數據結構，但是嚴格維護其平衡性會引發高頻次的重平衡操作，嚴重降低算法效率，增加服務器計算開銷，當數據庫中存儲大量數據時尤為明顯。如果適當地放寬平衡二叉樹約束條件，降低重平衡執行次數，可以在不對密文操作造成較大影響的情況下，顯著降低服務器端的開銷。

4 gmOPE編碼方法

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

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

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

文獻[17]提出了一種新的重平衡方法來替換“AVL旋轉”操作，當平衡二叉樹出現失衡，只需要從失衡節點開始，向深度較深的子樹方向進行搜索，就可以得到失衡節點、一個較深子節點和較深子節點的較深子節點。把這三個主干節點和四個從屬節點按照完全二叉樹的結構進行重新排列，就可以恢復平衡。

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

當N=1時，AVL-N樹的約束條件與普通的平衡二叉搜索樹相同。如圖2所示，圖中數字為節點編號，四幅圖中每幅圖的左側為失衡二叉樹，右側為重排后的結果。下面以第一類（對應左旋）為例詳細講解重排過程。

圖2 四類重平衡情況示例

算法3 gmOPE重平衡算法-Rebalance

輸入：失衡節點的路徑path

輸出：無

（1）查找并保存失衡二叉樹的2N+5個節點信息。

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

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

③將主干節點作為新根節點，并根據主干節點相對父節點的左右方向在path后補“0”或“1”，轉②；

④node[N+3]=新根節點的左孩子，node[2N+5]=新根節點的右孩子。

（2）構建重排序完全二叉樹：根據失衡二叉樹和對應的有序完全二叉樹構建重排序完全二叉樹，得到廣度優先遍歷重排序完全二叉樹節點數組index[]。

index[]=（算法 4）

（3）將失衡二叉樹按照重排序完全二叉樹重構，更新節點編碼，詳見3.3節。

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

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

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

4.2 構建重排序二叉樹及改進

當N=1時重排后的完全二叉樹有4種類型，每種類型對應的數組中包含7個編號元素；當N=2時有8種類型，包含9個編號元素。以此類推，N越大對應的分類情況越多，計算量也越大，人工難以勝任。因此結合算法4，采用自動計算分類的形式，可以直接計算出失衡樹對應的重排數組，簡化計算過程。算法4的主要功能是根據采集到的失衡樹節點，求出重排后的節點編號，構建完全平衡二叉樹。具體算法內容如下：

算法4

輸入：平衡約束N，收集的節點數組node[]

輸出：重排序完全二叉樹節點數組index[]

（1）中序遍歷（LDR）失衡樹，得到對應的編號數組UBTArray[]。

（2）構建包含2N+5個節點的有序的完全平衡二叉樹，中序遍歷完全二叉樹，得到完全二叉樹數組CBTArray[]。

（3）根據上面的兩個數組，構建重排序完全二叉樹，得到對應的廣度優先遍歷數組index[]。

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

圖3 算法4講解圖例

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

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

圖4 數據庫臨時表實現重排算法

4.3 更新從屬節點及子節點編碼

當在執行算法3的步驟（2）生成了重排序完全二叉樹之后，需要更新2N+5個失衡節點對應的編碼和高度信息。對于重平衡后樹中節點的高度，根據調整后的二叉樹結構，自底向上依次對各個節點進行更新即可；而對于節點編碼，則要設計一種高效、正確的編碼更新規范。

由于節點路徑path發生變化，節點編碼OPE_encoding也隨之改變，并且改變前后的節點編碼均只與路徑path有關。將所有節點編碼拆分為前綴prefix和后綴suffix，前綴prefix由路徑path決定，后綴suffix由各節點在子樹內部的具體路徑決定。定義編碼調整公式為：

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

對整張表進行編碼更新會明顯降低執行效率，尤其是在數據庫中已經存在大量數據記錄時。因此可以結合葉子節點對應的編碼范圍[min，max]限定受影響的節點，從而在正確更新編碼的同時，保證編碼更新效率。

5 理論分析

5.1 gmOPE時間復雜度分析

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

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

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

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

在實際生產環境中，數據庫的記錄數n?N，因此N可以忽略不計，O(N)即為O(1)，見表1。

表1 mOPE與gmOPE時間復雜度比較

5.2 gmOPE實用性對比

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

6 實驗數據與分析

本文分別實現了mOPE和gmOPE，并且在相同的實驗環境中對兩種方案分別進行了測試。mOPE和gmOPE程序均為C/S結構，分為客戶端和服務器端兩部分?？蛻舳耸褂肑ava實現，通過JDBC與服務器通信；Server端主要為MySQL數據庫。Server端數據庫為未經修改的普通MySQL數據庫，包含用戶事先實現的自定義UDFs，用來實現邏輯二叉樹調整及編碼調整策略。客戶端程序主要功能為定位插入位置、數據加解密等計算操作，Server端主要負責編碼的調整和邏輯二叉樹的維護。其中加解密算法為電子密碼本模式的分組AES加密算法，分組長度為128位。

6.1 實驗平臺

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

實驗中將客戶端放置在服務器節點一同運行程序，忽略客戶端和Server端的通信時延，主要對數據插入操作的性能進行分析對比。

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

6.2 實驗結果分析

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

6.2.1 調整時間

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

表2 OPE/ORE方案對比分析

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

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

6.2.2 調整頻次

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

圖5 插入數據量與總的時間消耗

圖6 插入數據量與階段1的耗時

圖7 插入數據量與階段2的耗時

圖8 插入數據量和觸發重平衡操作的次數

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

圖9 平衡因子N與插入數據時觸發重平衡操作的次數

7 小結

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

參考文獻：

[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]江順亮，胡世鴻，唐祎玲，等.低調整率的廣義AVL樹及其統一重平衡方法[J].計算機應用，2015，35（3）：654-658.