Crypt-JDBC模型：洋蔥加密算法的優化改進*

陳 鶴，田秀霞,2，袁培森，金澈清+

1.華東師范大學 計算機科學與軟件工程學院 數據科學與工程研究院，上海 200062

2.上海電力學院 計算機科學與技術學院，上海 200090

3.南京農業大學 信息科技學院，南京 210095

Crypt-JDBC模型：洋蔥加密算法的優化改進*

陳 鶴1，田秀霞1,2，袁培森3，金澈清1+

1.華東師范大學 計算機科學與軟件工程學院 數據科學與工程研究院，上海 200062

2.上海電力學院 計算機科學與技術學院，上海 200090

3.南京農業大學 信息科技學院，南京 210095

CryptDB是一種典型的密文存儲技術，它根據運算操作語義使用洋蔥加密算法將SQL語句改寫到不同的洋蔥密文列，從而僅暴露數據的部分屬性即可執行查詢任務。針對洋蔥加密算法的不足之處提出了一種名為Crypt-JDBC的改進模型：（1）鑒于洋蔥層數多，且相鄰層功能差異大，新模型把洋蔥列分為主列與輔助列，并壓縮洋蔥層的改進方法（主列使用雙向算法可還原明文，輔助列使用單向算法提供屬性，保證安全性）；（2）鑒于等值連接算法復雜低效，新模型通過簡化一個關鍵模塊（差異性轉換）來降低復雜度；（3）鑒于列名的明文、密文名稱對應性弱，新模型重新設計了明密文列名稱的對應關系，減少了上下文信息，加強了密鑰整體性。實現了Crypt-JDBC模型，用JDBC替換中間件軟件MySQL-Proxy。實驗結果表明，該模型具有較高的執行效率。

CryptDB；加密數據庫；Crypt-JDBC模型；洋蔥加密算法；密文數據庫

1 引言

隨著計算機技術的快速發展和因特網的普及，數據管理技術得到迅速發展，各種互聯網應用和云端應用蓬勃發展，這增加了數據被盜的風險。

在相當長一段時間內，數據以明文形式存儲在數據庫中，并通過防火墻、安全口令等方式來確保數據安全。然而，黑客可以通過竊取數據庫用戶的賬號與密碼來訪問數據，因而無法絕對保證數據安全。

更新型的數據保護方法則利用現代密碼學成果，以全密文方式存儲關鍵數據。當數據擁有者查詢數據時，需完全解密密文數據，才能夠得到明文信息。在這種情況下，即使黑客破譯了數據庫用戶的賬號與密碼，也只能夠獲取密文數據，而無法還原出真實信息，從而有效地保證了數據安全。

然而，上述數據管理方式需要不斷解密密文，從而顯著地降低了執行效率。因此，一些學者也在探索能否直接基于密文數據來執行典型的數據庫查詢。

2011年，美國麻省理工學院的Popa等人提出了CryptDB，允許用戶在前端以明文方式定義查詢和接收結果，后端所有的運算操作均直接由密文承載。這種新型的類全同態加密方式使用了洋蔥加密算法，把明文列分拆為多密文列，且各列承載不同的多密文層結構。CryptDB通過這種改寫SQL語句的方式來完成密文的查詢操作，包括Eq密文列對應等值比較（對稱加密算法）操作，Ord密文列對應大小比較（OPE算法）操作，HOM密文列對應求和、求平均（paillier同態加密算法）操作，Search密文列對應模糊查找操作。Popa把這種SQL語句的改寫方法稱作洋蔥加密算法。

然而，CryptDB所涉及的洋蔥加密算法仍然存在以下幾點不足：（1）多層密碼層的設計并不能起到安全性的疊加，且上下層間屬性差異性較大，存在密碼層間繼承性的沖突；（2）有些洋蔥密碼層（如等值連接層EqJoin、大小連接層OrdJoin）的實現方式復雜且低效；（3）明文列與密文列沒有對應關系和轉化方式，增加了SQL語句改寫時對上下文信息的依賴。

本文的主要貢獻如下：

（1）提出了壓縮洋蔥層、擴展洋蔥列的設計，把洋蔥層分為主列和輔助列（前者使用雙向密碼算法可還原明文，后者使用單向密碼算法保證運算功能和安全性），解決了洋蔥層冗余與上下密碼層差異性較大的不足。

（2）提出了新的等值連接Eq_Join算法，簡化原算法的兩部分操作（確定性轉化與差異性轉化），并提高RND層參數IV的利用率，從而提高性能。

（3）提出了新的明密文列轉換設計，減小了執行SQL語句時對上下文信息的依賴性，規范了密鑰管理接口，使中間件僅存儲密鑰信息，解決了原算法SQL執行時前后查詢語句耦合度高的問題。

本文組織結構如下：第2章介紹相關工作；第3章詳細說明洋蔥密碼算法存在的問題和改進想法；第4章提出了Crypt-JDBC的設計思路，給出了一些改進方法；第5章針對CryptDB與Crypt-JDBC進行了實驗對比；最后總結全文并展望未來工作。

2 相關工作

密文數據庫已經被研究了相當長一段時間。早期工作主要通過對數據進行加密來存儲，并且在進行每次查詢時，再對數據進行解密來獲取查詢結果。這種方式簡單明了，但是效率低下。另一類代表性工作是同態加密算法，其目標是設計出能夠在密文上執行的全同態操作方法。但是這種方式仍處于研究之中，沒有較好的解決辦法。CryptDB提供了一種均衡的解決辦法，它沒有使用太過復雜的理論化加密方法，也沒有執行效率低下的全解密過程，是一種使用多個現代密碼學算法的動態調整查詢語句指令的算法。

2.1 CryptDB

Pola等人在2011年提出了CryptDB的概念，并開源了其代碼[1-3]。其使用開源軟件MySQL-Proxy充當上下層交互的媒介，來操控和改寫從前端接收到的SQL指令與后端返回的結果集合。MySQL-Proxy提供了lua腳本接口，可通過C鏈接庫對lua腳本的邏輯進行擴充。CryptDB使用了腳本中預設的4個函數接口，包括read_auth()、disconnect_client()、read_query(packet)、read_query_result(inj)。其腳本函數的觸發調用時機分別是：讀取客戶端的認證信息時調用，失去客戶端連接時調用，代理收到客戶端的查詢請求時調用，收到MySQL的返回結果集合時調用。

在文獻[4]中，Popa等人提出了洋蔥加密算法，其主要思想是：把一個明文列（column）分拆成多個密文列（field），并在每個列上以洋蔥加密的方式層層加密value值，當執行SQL語句時，改寫該查詢語句并在密文數據上執行（為了簡單起見，本文稱明文列為column，密文列為field）。如圖1所示，洋蔥加密算法本質上是一種改寫SQL語句的方法，根據運算屬性的不同，動態地選擇改寫方式。

2.2 L-EncDB

Li等人在2015年提出了L-EncDB[5]，使用保存格式加密算法（format-preserving encryption）、模糊查詢加密算法（fuzzy query encryption）、保序加密算法（order-preservingencryption）來解析不同的SQL語句。

L-EncDB結構如圖2所示。不難看出，L-EncDB的結構與CryptDB相似，也使用多密碼學算法承載了明文的不同運算屬性。

2.3 MrCrypt

Tetali等人在2013年提出了MrCrypt，定義了特定的同態加密模式，以在密文上執行特定的運算，如加法同態pallier、乘法同態ElGamal、相等判斷DET、大小判斷OPE[6-7]，如圖3所示。

Fig.1 Onion encryption layers圖1 洋蔥層示例

Fig.2 L-EncDB architecture圖2 L-EncDB結構

Fig.3 Encryption schemes of MrCrypt圖3 MrCrypt的加密模式

該文側重于MapReduce的密文改寫執行方法，并給出了改寫示例。其利用了多個同態算法來承載不同的屬性運算，與CryptDB中洋蔥加密算法的思路相類似，也給出類似的壓縮洋蔥層的設計。由于Map-Reduce框架簡單高效，故十分適合該方法。

3 洋蔥加密算法

由圖1～圖3可以看出，通過使用多密碼學函數來承載功能不同的運算屬性，可以近似達到在密文上執行SQL指令的結果，因而是一種集合式的全同態加密算法。本文將進一步分析各個加密層，并給出主列與輔助列的改進密碼集合方法。

第3.1節討論了洋蔥加密算法中洋蔥層與各密碼學算法的對應關系和特性。第3.2節總結了洋蔥加密算法的不足，并提出了簡化洋蔥加密算法的思路：（1）壓縮洋蔥層，擴展洋蔥列；（2）雙向性密碼學算法保證數據準確性（Eq列），多個單項性密碼學算法確保僅暴露部分數據屬性（如Ord列），從而保證安全性；（3）設計列名的明文密文對應規則，減少對上下文信息的依賴。

3.1 加密層特性

洋蔥加密算法分拆了明文列屬性到多個密文列，且不同密文列的洋蔥結構不同，加密算法也不同。有些密碼學算法僅需要密鑰作為唯一參數，而有些密碼學方法則需要更多參數，這些參數需要在密鑰管理模塊中設計與組織。本節將介紹各加密層的設計思想。

RND（random）：該密碼層要求較大程度的隨機化，以提升安全性，即使以相同密鑰值構建的相同加密算法來加密相同的明文值，其密文值也不相同。原因在于，其通過密碼分組鏈接（cipher block chaining，CBC）模式下的組對稱加密算法（如AES、Blowfish）實現，在該模式下，密鑰并不是全部的輸入參數，還包括輸入參數IV。而即使服務器端知曉了IV值，但不知密鑰的話，也無法解密密文數據，故具有較高的安全性。

DET（deterministic）：該密碼層要求同一列中明文與密文的確定性，在同一加密算法下，如果兩項密文的明文值相同，則其對應的密文值也相同。與RND相比，DET體現了雙向特性，即能夠在明文和密文之間相互轉換。這要求算法本身是一種偽隨機序列算法（pseudo-random permutation，PRP），從而能夠通過算法本身的隨機性，來保證整個DET密碼層的隨機性。因為IV沒有參與，故與RND方法相比較，其安全性較大程度上依賴于算法本身的安全性。

OPE（order-preserving encryption）：該密碼層要求同一列中數值的大小比較。換言之，如果x〈y，那么OPE_k(x)〈OPE_k(y)。這種算法針對數值比較，這是由OPE算法的特性決定的。OPE算法最初是在文獻[7]中提出的，是一種全新的密碼學設想，即在一次加密過程后，除了數值大小的信息被暴露之外，其余信息都保持安全性。這種算法的初衷，是把原始數值用另外的數值替換，從而可通過比較新數之間的大小來確定原數之間的大小。文獻[8-9]在此基礎上進行了擴展，提出了新的安全性概念IND-OPCA。但Boldyreva指出無法實現真正意義上的IND-OPCA，于是基于偽隨機函數的安全性定義POPF-CCA，并提出了利用超幾何分布在各數值區間產生隨機數值的方法。這種方法最先在文獻[3]中采用，也應用在開源代碼中。但是Popa等人在文獻[10]中重新梳理了OPE方法，認為OPE算法均存在一個弊端，即密文一旦確定就無法改變，于是提出了動態保序的思想mOPE。該算法通過平衡樹存儲數值，根據葉子節點到根節點之間的走勢得到01序列，而平衡樹的自平衡功能則可以動態改變序列編碼，從而更新密文數值的大小。這種方式具有較強的安全性，但實現起來較為復雜，使用了大量的UDF（user defined function）功能函數，且需要客戶端程序的配合。

HOM（homomorphic encryption）：該密碼層要求可以在密文上直接計算得到和與平均。可使用paillier算法[11]，當需要計算某一數值列的SUM或者AVG值時，調用MySQL中的UDF功能把該列上所有的值相乘取模，得到的密文值返回解密，即可得到最終的明文結果值。

Search（word search）：該密碼層要求可以在密文上進行模糊搜索。此時模糊搜索的粒度是詞，其實驗思想并不復雜。通過對明文句中的單詞進行分隔，對每一個單詞實現單獨加密，得到的密文結果保存在數據庫中。當需要查找指定詞時（如name like‘Alice％’），直接加密該詞獲得密文，并使用like關鍵字重構SQL語句且執行（如name like‘XXX％’），將查找到的結果返回解密。故該設計思想僅支持全單詞匹配。

Join（JOIN和OPE-JOIN）：該密碼層在文獻[3]中提出，是兩表連接時所需的密碼層級，分別對應了等值連接操作（如s.id=t.id）和大小比較連接操作（如s.id〉t.id）。Join密碼層在文獻[12]中使用了很大篇幅，在后續論文中也有對其運行方式的思索。在兩列密文以不同密鑰加密的前提下，算法仍然能夠通過不同列的Join層執行連接操作。這種特性能夠很好地支持密文上的連接操作，具有很好的應用性。

3.2 洋蔥加密算法的不足與改進思路

洋蔥加密算法存在一些不足。

（1）洋蔥層冗余與上下密碼層差異性較大。不同洋蔥密碼層承載了不同的運算操作，這體現了算法的功能性與安全性。但是執行上下密文層轉換的主體是數據庫本身，最終該列的安全性將由最內層密碼算法保證。因此，多密碼層沒有使安全性得到疊加，卻增加了上下層轉換時的運算開銷。且上下層間的功能性差異較大，沒有完全的繼承性，功能性略顯沖突（如DET與Eq_Join）。

（2）原等值連接算法的低效性。原算法先用偽隨機函數轉換明文，后通過橢圓加密算法與不同指數上標計算得到不同密文。改變指數上標即可改變密文值，從而實現對應。本質上，這種方法由兩部分組成，確定性轉化與參數差異性轉化（前者保護了明文安全，后者產生差異）。上述特性的實現，存在更加簡化的方法，因此原算法的步驟略顯復雜和低效。

（3）明文列與密文列名稱沒有對應性。明文列與密文列名稱間相互轉換，洋蔥加密算法存儲映射列表以對應明文與密文列名，這種方式對上下文信息的要求較高，尤其算法主體運行在中間層，這必然導致多次SQL之間的信息共享，無疑會增加操作之間的耦合性。

針對上述不足，提出了改進思路。

（1）壓縮洋蔥層，擴展洋蔥列，并把洋蔥列分為主列與輔助列（前者使用雙向算法可還原明文，后者使用單向算法提供各種運算屬性支持卻不能還原明文）。

（2）簡化等值連接算法的兩步轉換方式，其中差異性轉換可利用RND層存儲在數據庫上的參數IV，以減少中間件需要保存的數據。

（3）設計明文列與密文列名稱的對應關系，減少執行SQL語句時對上下文信息的依賴（如密文列“XXX_Eq”可直接解密得到“sid”，無需記錄對應關系），中間件僅保存密鑰信息，從而確保各執行操作之間的低耦合性。

下面將根據這些思想對洋蔥加密算法進行改進。

4 基于改進洋蔥加密算法的Crypt-JDBC模型

首先描述Crypt-JDBC模型的基本架構。如圖4所示，該模型是一個輕量型的基于JDBC的SQL語義改寫方法。

Fig.4 Crypt-JDBC model圖4 Crypt-JDBC模型

Crypt-JDBC模型做了以下改進：（1）采用JDBC替換了原中間件程序MySQL-Proxy，簡化了結構；（2）壓縮洋蔥層，擴展洋蔥列，把洋蔥列分為主密文列（如Eq列）與輔助密文列（如Ord列、Search列等），主列使用雙向的加密算法，可解密得到原始值，輔助列則使用單向加密算法支持各種運算操作，不可解密還原；（3）改進密文上的等值連接算法，簡化步驟，減少中間件存儲信息；（4）修改密鑰管理模塊以匹配新的洋蔥列模型，增加列名稱的明密文轉換以減少改寫步驟對上下文的依賴，最終使中間件僅維護各密文列的密鑰，實現低耦合高內聚。

Crypt-JDBC將明文SQL語句改寫成密文SQL語句并執行，且解密返回的密文結果集。此時，數據庫中存放的所有數據均以密文形式存儲，從而保證數據安全。

定義1（明文SQL語句）改寫前的SQL語句，如“create table student(sid int not null)”、“insert into student(sid)values(1)”等。

定義2（密文SQL語句）通過洋蔥加密算法分拆明文列后組織起來的語句，如“create table S(XXX_Eq varchar(64),XXX_Ord BigInt,XXX_Add varchar(256))”、“insert into S(XXX_Eq,XXX_Ord,XXX_Add)values(‘abc’,200,‘xyz’)”等，其中insert語句中value括號內的值為對應密文列的密碼值。

4.1 密文列加密算法

多洋蔥層設計的初衷，原本是為了更強的安全性與功能性，但是上下層間的屬性差異性較大，如DET與EQ_JOIN層，這影響了功能性；并且執行加層去層的主體是數據庫本身，這影響了安全性。因此原方法在功能與安全上均不能達到預期，卻增加了上下層轉換的計算開銷。

改進措施包括：壓縮洋蔥層，擴展洋蔥列，把層疊的密碼層分拆為更多的洋蔥列，如表1所示。由于不再有多層次，這種改進的洋蔥列被稱為密文列。

Table1 Onion fields contrast表1 洋蔥列對照表

如表1中所示，對比圖1，首先考慮將等值連接層（Eq_Join）與比較連接層（Ord_Join）分離，作為單獨的列。其次，將所有的RND層去除。因為執行密文上下層轉換的主體是第三方服務器，在這種情況下，處在最外層的RND層則無法起作用。

更進一步，可以把洋蔥列分為主密文列（如Eq列）與輔助密文列（如Ord列、Search列等）。主列使用雙向加密算法，可解密得到明文；而輔助列使用單向加密算法，支持各種運算操作，卻不能解密。

圖5描述了洋蔥加密算法的改進，由于大大減少了洋蔥層的使用，稱之為密文列加密算法。它同樣將明文列（如sid）分拆為多列（如Eq、Ord等），多密文列各自承擔不同的運算。

舉一個簡單例子說明不同加密列承載了不同的運算操作，例如，“select sid from student where sid〉1 and sname=‘Alice’”會被改寫為“select sid.eq from student where sid.ord〉OPE(1)and sname.eq=DET(‘Alice’)”。值得注意的是，此示例忽略了一些細節操作，如密鑰選擇，密文列名稱修改等。詳細的算法會在4.3節中詳細介紹。

Fig.5 Improved field encryption algorithm圖5 改進后的密文列加密算法

4.2 多列等值連接的改進執行方法

等值層所要解決的問題如下：即使兩列密文以不同密鑰進行加密，算法仍然能夠對其執行連接操作。那么如何在這種情形下做等值連接呢？例如“select*fromA,BwhereA.a=B.b;”。

原算法中的等值連接操作使用了橢圓加密算法，并存在一個公共點P，并通過公式計算每個列的對應值[2]：

其中，K代表此列所存密鑰，而K0為公共值。當請求連接c和c′兩列時，中間層將計算ΔK=K/K′，并通過如下式子將兩列轉換為相同密鑰加密的密文值：

如此可在不同密文列上實現連接操作。這種方式實現比較復雜，效率較為低下，需要設計復雜的比較方式，以及大量UDF代碼的支持。

該方法可分成兩部分：第一部分實現了明文到中間密文值的轉換，是一一對應的；第二部分實現了參數差異性轉換，不同的參數對應不同的轉換結果，當參數相同時密文值相同。這種等值比較方式，在靜態環境下能保證完全的無關性，但在動態環境下會揭露出不同列中相同值的對應關系。

分析可得，因為執行等值比較的主體是數據庫本身，所以它在執行過程中總是會了解這種對應關系。因此，無論多么復雜的算法，最終只能夠保證靜態環境下的安全性。

故本文提出了簡化方法：第一步，替換更簡便的哈希算法（如MD5算法，長度128位）。第二步，把中間密文值與參數IV（RND層的參數，長度128位）進行按位異或運算，得到最終的密文值。

當插入數值v時，首先計算v的消息摘要，再與該行的IV值進行按位異或運算，得到最終值，并將該值插入到密文列中。當查詢時，則需要UDF功能的配合，如下所示。

考慮一個等值連接語句“select*froms,t wheres.sid=t.tid”。分析where子句表達式，可確定其執行了等值連接操作。故將該語句改寫為“select*froms,t where udf_eqjoin(sid,IV)=udf_eqjoin(tid,IV)”。其中，udf_eqjoin()是用戶自定義函數UDF，是擴充的功能代碼，能夠被MySQL所識別。

用戶自定義接口是數據庫自帶的可擴展接口，可以在不修改DB源碼的情形下擴充功能。其擴充后的函數可以像abs()函數一樣方便使用。由于UDF不會對數據庫的其他部分產生影響，是一種非常實用也非常流行的數據庫擴展技術。

4.3 列名對應關系改進與密鑰管理

原作中采用了如下方式來管理密鑰：Kt,c,o,l=PRPMK(table,column,onion,layer)，通過傳入表名、列名、洋蔥列、加密層來確定加密層的密鑰值。但這種方式僅考慮了加密層的密鑰獲取，而沒有考慮列名稱的對應。

本文設計了列名的明文密文對應方式。該方式管理著兩組密鑰索引，分別對應轉換數據的密鑰和轉換列名的密鑰。為了敘述方便，本文以column表示明文列（如“sid”），field表示密文列（如“XXX_Eq”或“XXX_Ord”）。前者是上式的變形，存儲了鍵值對〈k,v〉：表名table、明文列column、密文列field和該密文列對應的密鑰，如((student，sid，XXXoEq)，Gen(XXXoEq))，其中Gen()函數的功能是生成密鑰，它根據密文列field的屬性，選擇不同的方法生成密鑰，例如Eq選擇AES或Blowfish，Ord選擇OPE算法等。后者則是存有明文列名column與密文列名field相互轉換的密值，如((student，sid)，key)和((student，XXXoEq)，key)。當通過密鑰把明文列名column轉換成密文列field后，需要同時將這2個鍵值對加入到索引中，以同時支持明文列與密文列間的相互轉換。

5 查詢語句的改寫過程

以下將描述Crypt-JDBC模型中的密文列加密算法，并簡述其改寫查詢語句的過程，包括密鑰的管理使用和改寫SQL語句的方法。

5.1 Create語句改寫過程

Create語句改寫方法首先解析SQL語句，分析并生成各密文列密鑰。其算法偽代碼如下。

算法1CREATE SQL rewrite function

輸入：明文SQL語句

輸出：密文SQL語句

1.Statement st=Jsqlparser();//解析明文SQL語句

2.Statement nst=new Statement();

3.Foreachc∈st.create.columns do

4. FieldKey k1=KeyFieldGen(c);//生成列名稱密鑰

5. Key k2=KeyGen(c);//生成密文列密鑰

6. List lfs=Rewrite(c);//根據c是字符型還是數值型，改寫明文列column到多密文列fields

7. nst.add(lfs);

8.Return nst;

為了使得明文列column的名稱和密文列field的名稱能夠相互對應，使得列名變得有意義，并簡化SQL改寫過程中的操作，前端保存兩者列名之間轉換的密鑰值，可減少中間件需要記錄的數據。

5.2 Insert語句改寫過程

Insert語句改寫過程需要知道明文列與密文列間的對應關系，及各列的加密密鑰。這種對應關系可以通過前端保存的密鑰索引來快速尋找。類似的，密鑰也可通過前端索引快速獲得。其算法偽代碼如下。

算法2INSERT SQL rewrite function

輸入：明文SQL語句

輸出：密文SQL語句

1.Statement st=Jsqlparser();//解析明文SQL語句

2.Statement nst=new Statement();

3.Foreachc∈st.insert.columns do

4. FieldKey k1=KeyFieldGet(c);//獲取列名稱密鑰

5. List lk=KeysGet(c);//獲取所有的密文列密鑰

6. Ifc.value instance of int then

7. List lfs=Rewrite_int(c,lk);//改寫明文列column到多密文列fields

8. Else

9. Listlfs=Rewrite_string(c,lk);//改寫明文列column到多密文列fields

10. EndIf

11. nst.add(lfs);

12.Return nst;

此時，改寫過程所需要的全部信息均為密鑰值，這統一了前端后端通信的接口，使得密鑰管理模塊更加高效。

5.3 Select語句改寫過程與解密返回集合

Select語句和前面兩種語句稍有區別，它含有更多的表達式，如where子句和and子句。在這些子句中，包含有各種運算操作。這些運算操作由運算符和運算值所組成，如“sid=1”，“sid〉2”，“sname like‘Alice％’”等。

改寫時，首先需要判斷運算符的格式，依此修改明文列名到不同的密文屬性列，以及修改明文值到不同的密文值。例如“sid=1”可修改為“XXX_Eq=Enc(1,key)”，其中XXX由“sid”加密得到。

算法3SELECT SQL rewrite function

輸入：明文SQL語句

輸出：密文SQL語句

1.Statement st=Jsqlparser();//解析明文SQL語句

2.Statement nst=new Statement();

3.Foreachc∈st.select.whereand.condition do

4. 依據c的運算屬性改寫condition，更新nst;

5.Foreacht∈st.select.sellist do

6. 改寫返回列名，更新nst;

7. Return nst；

使用JDBC執行該密文SQL語句，并得到返回結果集合。該集合由列名與行元素組成，對該數據集合解密后可得到明文數據。

算法4SELECT SQL rewrite returnset function

輸入：密文數據集合

輸出：明文數據集合

1.解析密文數據集合;

2.定義臨時密鑰列表tmplist;

3.獲取列名res_fields、行數據res_rows;

4.Foreachf∈res_fields do

5. 獲取f對應的解密密鑰key;

6. tmplist.add(key);

7.Dec(res_rows,tmplist);//解密密文數據

8.構建明文數據集合并返回;

綜上，容易發現，密鑰管理模塊貫穿了整個改寫算法的始終，且明文列與密文列的對應使得多條查詢語句間的耦合性大大降低，減少了各語句間的關聯性，具有極好的設計結構。

6 實驗

本文實現了Crypt-JDBC模型，使用JDBC作為連接MySQL的中間件，以取代MySQL-Proxy軟件[13]。實驗運行在Ubuntu12.04環境下，MySQL版本為5.5.47。中間件MySQL-Proxy的版本是0.8.5[14]（Crypt-DB開源代碼中的Proxy版本為0.8.4，本實驗修改了開源代碼的安裝指令[15-16]，替換了較新的版本）。Crypt-JDBC運行在Eclipse中，Java版本為1.8.0_77。

本實驗對比了CryptDB與Crypt-JDBC的執行效率。由于僅支持少量的SQL語句，本實驗主要以增刪查改SQL語句為例，測試它們在連續執行5、15、30、50條語句后的時間消耗。

圖6描述了連續執行多條create語句的效率對比，可以看出隨著執行語句條數的增加，CryptDB的上升幅度遠遠超過Crypt-JDBC模型的上升幅度。而隨著n的增加，兩條曲線在15到30階段所增加的幅度要大于30到50階段。這說明隨著create語句的增多，其上升幅度放緩。圖7描述了每條create語句所需的平均時間，可以發現它呈現階段上升的趨勢。

Fig.6 Efficiency for executing multiple create statements圖6 連續執行多條create語句的效率對比

Fig.7 Average time of each create statement圖7 單條create語句的平均執行時間

圖8描述的是連續執行多條insert語句的時間對比，可以看出執行insert語句的時間與條數存在一種大致的線性關系，和create語句中階梯上升的情形相區別。同時，從圖9中可以發現一個有趣的現象，隨著insert語句執行次數的增加，每條insert語句所需要的平均單位時間有所降低。

Fig.8 Efficiency for executing multiple insert statements圖8 連續執行多條insert語句的效率對比

Fig.9 Average time of each insert statement圖9 單條insert語句的平均執行時間

圖10中的縱坐標代表數據量，橫坐標代表執行多次select語句所需時間，n為執行語句數。該圖描述了在不同數據量的表上執行多次select語句所需總時間。如圖所示，相同數據量下，執行多條select語句所需的總時間，隨著執行次數的增大而增大；同理，執行次數相同時，總時間也與數據量正相關。

圖11描述了不同數據量下Crypt-JDBC與Crypt-DB的select語句執行效率對比。連續執行40次select指令可消除單次執行的誤差，并與圖10中數據相對應。圖12展示了存放在MySQL中的部分數據，從左到右分別是Eq、Ord、Add列。

Fig.10 Average time of each select statement in Crypt-JDBC model圖10 Crypt-JDBC模型中select語句的平均執行時間

Fig.11 Efficiency for executing 40 select statements圖11 執行40次select語句的效率對比

Fig.12 Part of cipher text stored in DB圖12 存儲的部分密文數據

通過實驗可以看出，Crypt-JDBC模型的執行效率要高于CryptDB，原因有兩點：（1）CryptDB使用MySQL-Proxy軟件作為程序的中間件，而Proxy需要向前端與后端發送數據，因而其運行時間比直接使用JDBC大了很多；（2）Crypt-JDBC在設計上比Crypt-DB少了一些洋蔥密碼層卻多了一些洋蔥密文列，這是一種用空間換取時間的策略。Crypt-JDBC模型使用單向密碼算法來確保安全性，使用UDF代碼來確保功能性，達到了安全性與功能性的統一。

7 總結

本文探討了CryptDB的發展歷程和設計理念，深入分析了洋蔥加密算法，并發現了三點不足之處：洋蔥層冗余與上下密碼層差異性較大，等值連接算法的低效性，明文列與密文列名稱沒有對應性。針對以上不足，提出了新模型Crypt-JDBC，替換了中間件MySQL-Proxy，具有較好的執行效率。

本文還依據“壓縮洋蔥層，擴展洋蔥列，并把洋蔥列分為主列與輔助列”的思想，改進了洋蔥加密算法。由于改進后的洋蔥列上僅有一層或兩層洋蔥密文層，故這種改進后的算法也可以稱作密文列加密算法。本文還分析了等值連接方法的特性，簡化了兩步轉換的方式，提出了新的等值連接方法。本文也擴充和修改了密鑰的管理，使明文列與密文列名稱建立對應關系，減少了SQL執行過程中對上下文信息的依賴。

當然，本文模型在實際應用中還有若干問題需要解決，如用到的UDF功能算法的設計，更多SQL語句的改寫方式，擴充到其他數據庫或大數據庫的可行性等。

[1]Popa RA,Redfield C M S,Zeldovich N,et al.CryptDB:protecting confidentiality with encrypted query processing[C]//Proceedings of the 23rd ACM Symposium on Operating Systems Principles,Cascais,Portugal,Oct 23-26,2011.New York:ACM,2011:85-100.

[2]Popa RA,Zeldovich N,Balakrishnan H.CryptDB:a practical encrypted relational DBMS,MIT-CSAIL-TR-2011-005[R].CSAIL,MIT,2011.

[3]Tu S,Kaashoek M F,Madden S,et al.Processing analytical queries over encrypted data[C]//Proceedings of the 39th International Conference on Very Large Data Bases,Trento,Italy,Aug 26-30,2013.Red Hook,USA:Curran Associates,2013:289-300.

[4]Popa RA.Building practical systems that compute on encrypted data[D].Cambridge,USA:Massachusetts Institute of Technology,2014.

[5]Li Jin,Liu Zheli,Chen Xiaofeng,et al.L-EncDB:a lightweight framework for privacy-preserving data queries in cloud computing[J].Knowledge-Based Systems,2015,79:18-26.

[6]Tetali S D,Lesani M,MajumdarR,et al.MrCrypt:static analysis for secure cloud computations[J].ACM SIGPLAN Notices,2013,48(10):271-286.

[7]AgrawalR,Kiernan J,SrikantR,et al.Order preserving encryption for numeric data[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data,Paris,Jun 13-18,2004.New York:ACM,2004:563-574.

[8]Amanatidis G,BoldyrevaA,O’NeillA.Provably-secure schemes for basic query support in outsourced databases[C]//LNCS 4602:Proceedings of the 21st Annual IFIP WG 11.3 Working Conference on Data and Applications Security,Redondo Beach,USA,Jul 8-11,2007.Berlin,Heidelberg:Springer,2007:14-30.

[9]BoldyrevaA,Chenette N,O’NeillA.Order-preserving encryption revisited:improved security analysis and alternative solutions[C]//LNCS 6841:Proceedings of the 31st Annual Conference on Advances in Cryptology,Santa Barbara,USA,Aug 14-18,2011.Berlin,Heidelberg:Springer,2011:578-595.

[10]Popa RA,Li F H,Zeldovich N.An ideal-security protocol for order-preserving encoding[C]//Proceedings of the 2013 Symposium on Security and Privacy,San Francisco,USA,May 19-22,2013.Piscataway,USA:IEEE,2013:463-477.

[11]Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//LNCS 1592:Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques,Prague,May 2-6,1999.Berlin,Heidelberg:Springer,1999:223-238.

[12]Popa RA,Zeldovich N.Cryptographic treatment of CryptDB's adjustable join,MIT-CSAIL-TR-2012-006[R].CSAIL,MIT,2012.

[13]Curino C,Jones E P C,Popa RA,et al.Relational cloud:a database service for the cloud[C]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research,Pacific Grove,USA,Jan 9-12,2011:235-240.

[14]Taylor M.MySQL proxy web site[EB/OL].(2016-04)[2016-07-04].https://launchpad.net/mysql-proxy.

[15]Shoup V.Alibrary for doing number theory[EB/OL].(2013-05)[2016-07-04].http://www.shoup.net/ntl/.

[16]Popa RA,Redfield C M S,Zeldovich N,et al.CryptDB web site[EB/OL].(2015-11)[2016-07-04].http://css.csail.mit.edu/cryptdb.

Crypt-JDBC Model:Optimization of Onion EncryptionAlgorithm*

CHEN He1,TIAN Xiuxia1,2,YUAN Peisen3,JIN Cheqing1+
1.Institute for Data Science and Engineering,School of Computer Science and Software Engineering,East China Normal University,Shanghai 200062,China
2.College of Computer Science and Technology,Shanghai University of Electric Power,Shanghai 200090,China
3.College of Information Science and Technology,NanjingAgricultural University,Nanjing 210095,China
+Corresponding author:E-mail:cqjin@sei.ecnu.edu.cn

CHEN He,TIAN Xiuxia,YUAN Peisen,et al.Crypt-JDBC model:optimization of onion encryption algorithm.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1246-1257.

CryptDB is a typical encrypted data storage technology that uses onion encryption algorithm to rewrite the SQL statement to the different columns of the onion,so that only partial attributes of data are exposed for conducing different operations.To overcome the multiple weaknesses of onion encryption algorithm,this paper proposes a new Crypt-JDBC model:(1)As the existence of too many layers of onion,and poor inheritance of neighbor layers,the new model compresses layers of onion,and divides onion-fields into the main field and auxiliary fields(the main field uses a two-way algorithm for restoring the plain text,and the auxiliary fields use one-way algorithm for operations and security);(2)As the existence of inefficient join function,the new model simplifies one important part(difference transformation)to reduce complexity;(3)As the existence of low corresponding between the namesof columns and fields,the new model redesigns the corresponding relationship between columns(plain text)and fields(cipher text),reduces the context information,and enhances the integrity of keys.This paper implements the Crypt-JDBC model,and uses JDBC to replace the middleware MySQL-Proxy.The experimental results show that the model is efficient.

CryptDB;crypto database;Crypt-JDBC model;onion encryption algorithm;cipher text database

ia was born in 1976.She

the Ph.D.degree from Fudan University.Now she is a professor and M.S.supervisor at Shanghai University of Electric Power.Her research interests include information security and database security,etc. 田秀霞（1976—），女，河南安陽人，復旦大學計算機科學技術學院博士，上海電力學院教授、碩士生導師，主要研究領域為信息安全，數據庫安全等。

CHEN He was born in 1992.He is an M.S.candidate at School of Computer Science and Software Engineering,East China Normal University.His research interests include databases,information security and location-based service,etc.陳鶴（1992—），男，安徽淮北人，華東師范大學計算機科學與軟件工程學院碩士研究生，主要研究領域為數據庫，信息安全，基于位置的服務等。

YUAN Peisen was born in 1980.He is a lecture at NanjingAgricultural University.His research interests include dataintensive computing and data mining,etc.袁培森（1980—），男，河南淮陽人，南京農業大學講師，主要研究領域為海量數據處理，數據挖掘等。

A

：TP392

*The National Natural Science Foundation of China under Grant Nos.61370101,U1501252,61532021,61502236,61202020(國家自然科學基金);the National Basic Research Program of China under Grant No.2012CB316203(國家重點基礎研究發展計劃(973計劃));the Innovation Program of Shanghai Municipal Education Commission under Grant No.14ZZ045(上海市教委科研創新重點項目).

Received 2016-07,Accepted 2016-09.

CNKI網絡優先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1458.032.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1246-12

10.3778/j.issn.1673-9418.1608037

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056