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

1.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院 數(shù)據(jù)科學(xué)與工程研究院，上海 200062

2.上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 200090

3.南京農(nóng)業(yè)大學(xué) 信息科技學(xué)院，南京 210095

Crypt-JDBC模型：洋蔥加密算法的優(yōu)化改進(jìn)*

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

1.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院 數(shù)據(jù)科學(xué)與工程研究院，上海 200062

2.上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 200090

3.南京農(nóng)業(yè)大學(xué) 信息科技學(xué)院，南京 210095

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

CryptDB；加密數(shù)據(jù)庫；Crypt-JDBC模型；洋蔥加密算法；密文數(shù)據(jù)庫

1 引言

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展和因特網(wǎng)的普及，數(shù)據(jù)管理技術(shù)得到迅速發(fā)展，各種互聯(lián)網(wǎng)應(yīng)用和云端應(yīng)用蓬勃發(fā)展，這增加了數(shù)據(jù)被盜的風(fēng)險(xiǎn)。

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

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

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

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

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

本文的主要貢獻(xiàn)如下：

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

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

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

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

2 相關(guān)工作

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

2.1 CryptDB

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

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

2.2 L-EncDB

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

L-EncDB結(jié)構(gòu)如圖2所示。不難看出，L-EncDB的結(jié)構(gòu)與CryptDB相似，也使用多密碼學(xué)算法承載了明文的不同運(yùn)算屬性。

2.3 MrCrypt

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

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

Fig.2 L-EncDB architecture圖2 L-EncDB結(jié)構(gòu)

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

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

3 洋蔥加密算法

由圖1～圖3可以看出，通過使用多密碼學(xué)函數(shù)來承載功能不同的運(yùn)算屬性，可以近似達(dá)到在密文上執(zhí)行SQL指令的結(jié)果，因而是一種集合式的全同態(tài)加密算法。本文將進(jìn)一步分析各個(gè)加密層，并給出主列與輔助列的改進(jìn)密碼集合方法。

第3.1節(jié)討論了洋蔥加密算法中洋蔥層與各密碼學(xué)算法的對應(yīng)關(guān)系和特性。第3.2節(jié)總結(jié)了洋蔥加密算法的不足，并提出了簡化洋蔥加密算法的思路：（1）壓縮洋蔥層，擴(kuò)展洋蔥列；（2）雙向性密碼學(xué)算法保證數(shù)據(jù)準(zhǔn)確性（Eq列），多個(gè)單項(xiàng)性密碼學(xué)算法確保僅暴露部分?jǐn)?shù)據(jù)屬性（如Ord列），從而保證安全性；（3）設(shè)計(jì)列名的明文密文對應(yīng)規(guī)則，減少對上下文信息的依賴。

3.1 加密層特性

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

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

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

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

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

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

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

3.2 洋蔥加密算法的不足與改進(jìn)思路

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

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

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

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

針對上述不足，提出了改進(jìn)思路。

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

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

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

下面將根據(jù)這些思想對洋蔥加密算法進(jìn)行改進(jìn)。

4 基于改進(jìn)洋蔥加密算法的Crypt-JDBC模型

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

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

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

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

定義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(‘a(chǎn)bc’,200,‘xyz’)”等，其中insert語句中value括號內(nèi)的值為對應(yīng)密文列的密碼值。

4.1 密文列加密算法

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

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

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

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

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

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

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

Fig.5 Improved field encryption algorithm圖5 改進(jìn)后的密文列加密算法

4.2 多列等值連接的改進(jìn)執(zhí)行方法

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

原算法中的等值連接操作使用了橢圓加密算法，并存在一個(gè)公共點(diǎn)P，并通過公式計(jì)算每個(gè)列的對應(yīng)值[2]：

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

如此可在不同密文列上實(shí)現(xiàn)連接操作。這種方式實(shí)現(xiàn)比較復(fù)雜，效率較為低下，需要設(shè)計(jì)復(fù)雜的比較方式，以及大量UDF代碼的支持。

該方法可分成兩部分：第一部分實(shí)現(xiàn)了明文到中間密文值的轉(zhuǎn)換，是一一對應(yīng)的；第二部分實(shí)現(xiàn)了參數(shù)差異性轉(zhuǎn)換，不同的參數(shù)對應(yīng)不同的轉(zhuǎn)換結(jié)果，當(dāng)參數(shù)相同時(shí)密文值相同。這種等值比較方式，在靜態(tài)環(huán)境下能保證完全的無關(guān)性，但在動(dòng)態(tài)環(huán)境下會(huì)揭露出不同列中相同值的對應(yīng)關(guān)系。

分析可得，因?yàn)閳?zhí)行等值比較的主體是數(shù)據(jù)庫本身，所以它在執(zhí)行過程中總是會(huì)了解這種對應(yīng)關(guān)系。因此，無論多么復(fù)雜的算法，最終只能夠保證靜態(tài)環(huán)境下的安全性。

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

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

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

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

4.3 列名對應(yīng)關(guān)系改進(jìn)與密鑰管理

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

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

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);//根據(jù)c是字符型還是數(shù)值型，改寫明文列column到多密文列fields

7. nst.add(lfs);

8.Return nst;

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

5.2 Insert語句改寫過程

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

算法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;

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

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

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

改寫時(shí)，首先需要判斷運(yùn)算符的格式，依此修改明文列名到不同的密文屬性列，以及修改明文值到不同的密文值。例如“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. 依據(jù)c的運(yùn)算屬性改寫condition，更新nst;

5.Foreacht∈st.select.sellist do

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

7. Return nst；

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

算法4SELECT SQL rewrite returnset function

輸入：密文數(shù)據(jù)集合

輸出：明文數(shù)據(jù)集合

1.解析密文數(shù)據(jù)集合;

2.定義臨時(shí)密鑰列表tmplist;

3.獲取列名res_fields、行數(shù)據(jù)res_rows;

4.Foreachf∈res_fields do

5. 獲取f對應(yīng)的解密密鑰key;

6. tmplist.add(key);

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

8.構(gòu)建明文數(shù)據(jù)集合并返回;

綜上，容易發(fā)現(xiàn)，密鑰管理模塊貫穿了整個(gè)改寫算法的始終，且明文列與密文列的對應(yīng)使得多條查詢語句間的耦合性大大降低，減少了各語句間的關(guān)聯(lián)性，具有極好的設(shè)計(jì)結(jié)構(gòu)。

6 實(shí)驗(yàn)

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

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

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

Fig.6 Efficiency for executing multiple create statements圖6 連續(xù)執(zhí)行多條create語句的效率對比

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

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

Fig.8 Efficiency for executing multiple insert statements圖8 連續(xù)執(zhí)行多條insert語句的效率對比

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

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

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

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

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

Fig.12 Part of cipher text stored in DB圖12 存儲(chǔ)的部分密文數(shù)據(jù)

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

7 總結(jié)

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

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

當(dāng)然，本文模型在實(shí)際應(yīng)用中還有若干問題需要解決，如用到的UDF功能算法的設(shè)計(jì)，更多SQL語句的改寫方式，擴(kuò)充到其他數(shù)據(jù)庫或大數(shù)據(jù)庫的可行性等。

[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—），女，河南安陽人，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院博士，上海電力學(xué)院教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)樾畔踩?，?shù)據(jù)庫安全等。

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—），男，安徽淮北人，華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫，信息安全，基于位置的服務(wù)等。

YUAN Peisen was born in 1980.He is a lecture at NanjingAgricultural University.His research interests include dataintensive computing and data mining,etc.袁培森（1980—），男，河南淮陽人，南京農(nóng)業(yè)大學(xué)講師，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)處理，數(shù)據(jù)挖掘等。

A

：TP392

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

Received 2016-07,Accepted 2016-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版: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