可搜索數據庫加密系統的設計與實現

汪海偉,楊 庚，劉國秀，曾橙焜

(南京郵電大學 計算機學院,江蘇 南京 210003)

可搜索數據庫加密系統的設計與實現

汪海偉,楊 庚，劉國秀，曾橙焜

(南京郵電大學 計算機學院,江蘇 南京 210003)

數據隱私保護已成為網絡應用中急需解決的問題,其簡單的解決方案是將隱私數據進行加密后存儲在數據庫中，但該方式存在一些缺陷，包括經加密后的明文數據會失去明文的一些屬性，如數據之間的順序關系，原有對明文的運算也無法在密文上執行，需將所有密文解密為明文才能完成操作，因而在面對大規模的數據庫存儲需求時，其執行效率遠低于明文數據庫。為在保證安全性的同時解決密文上不可直接執行SQL操作的問題，設計高效、安全的加密模型已成為當務之急。為此，設計并實現了一種包括SQL語句改寫、明文數據加密和查詢處理等功能在內的可搜索數據庫加密系統。該系統在語句執行過程中通過動態調整加密層，實現了在密文上直接執行復雜的SQL語句，避免了不可信數據庫服務器暴露明文數據，保護了數據隱私。實驗結果表明，所構建的系統具有較好的有效性和安全性。

SQL查詢；密文查詢；可搜索數據庫加密；隱私保護

0 引 言

隱私保護是數據庫安全的重要內容，其安全威脅來自于兩方面[1]:一是數據庫系統外部，攻擊者利用系統漏洞或者非法獲取訪問權限，竊取隱私數據；二是數據庫系統內部，具有合法訪問權限的數據庫管理員，存在探查、泄露隱私數據的可能性。

一種簡單的解決方案是對隱私數據進行加密后存儲在數據庫中，在查詢時，對密文數據進行解密。這種方法的缺陷是，明文數據經過加密后，失去了明文的一些屬性，如數據之間的順序關系，原有對明文的運算也無法在密文上執行，需要將所有密文解密為明文才能完成操作。該方案在面對大規模數據庫存儲需求時，在執行效率上遠低于明文數據庫[2]。

為了能在不解密的情況下對數據進行操作，研究者提出了同態算法[3]，其中全同態算法[4]允許在密文數據上進行任意操作，并得到與在明文上操作相同的結果。其缺陷在于，算法的執行效率低，時間開銷大，不具有實際應用價值。

在考慮到數據加密、密文可操作性以及實用性上，麻省理工學院的研究員設計并實現了數據庫加密系統—CryptDB[5-6]。該系統是以中間代理的形式為數據庫提供加解密功能。與直接在明文數據庫中進行操作的時間相比，只增加了15%～20%。

可搜索數據庫加密系統在CryptDB的基礎上，設計并實現了一種包括SQL語句改寫、明文數據加密和查詢處理等功能的加密系統，其特點在于語句執行過程中通過動態調整加密層，實現了在密文上直接執行復雜的SQL語句，支持字符類型數據的等值匹配，整數類型和浮點類型的密文排序和同態運算。

1 相關工作

當今數據的隱私問題越來越受到重視，數據以明文形式存儲在服務器中已不能滿足人們對隱私保護的需求，因此，數據加密技術越來越受到關注。然而，數據加密后的存儲帶來了數據查詢的難題，簡單的做法是將要查詢的數據全部解密，在明文上查詢，再將數據重新加密，這種方式易于實現，但效率低，尤其在數據量巨大的時候，解密的明文中存在大量不相關的數據，對這些數據的加解密工作是不必要的。可搜索加密機制(Searchable Encryption)[7]正是為了解決這類問題而提出的，用戶使用該機制對數據進行加密后，將密文數據交由服務器端存儲；當用戶需要根據關鍵字檢索文件時，將該關鍵字的搜索憑證(search capability)發給服務器，服務器根據這個憑證在密文數據上直接檢索，將包含有該關鍵字的文件返回給用戶，用戶只需對返回的文件進行解密即可。近些年，可搜索加密機制已得到廣泛的研究[8-14]，其中文獻[8,13-14]提出了多關鍵字搜索的解決方案，Li J等[10]解決了關鍵字的模糊查詢問題。

以上可搜索加密機制的研究側重于文本文件檢索，利用關鍵字信息在加密后的文本數據中進行匹配查詢。然而在應對數據庫中密文數據存儲及查詢問題時，以往的可搜索加密機制則無法滿足需求，如不支持一些基本的SQL查詢。在數據庫查詢中，不僅涉及到等值關系，還包括順序關系，如數值之間的大小比較；此外，對于數值型數據的計算，如sum()和avg()，如果在密文上的操作結果與明文相同，這需要密文能夠保持明文的部分或者全部屬性，這是以往可搜索加密機制無法完成的。

可搜索數據庫加密系統的目標是利用可搜索加密機制，對用戶提交的數據進行加密后存儲在數據庫中，當用戶需要查詢數據時，將要查詢的條件轉換為密文上的查詢條件，可以直接在密文上完成查詢，最終由用戶將這些結果解密。其優點在于[15]：在不可信的服務器端，數據始終以密文的形式存放，并且減少甚至消除服務器端接觸密鑰的可能性。用戶查詢時，只需要返回與查詢條件匹配的記錄即可，減少了通信開銷和用戶解密數據的計算開銷，提高了查詢效率。

CryptDB是首個在密文上進行所有SQL查詢操作的系統。該系統是以中間代理的形式為數據庫提供加解密功能。其核心包含三個部分[16]：加密策略(SQL-aware encryption strategy)、洋蔥加密模型(adjustable query-based encryption)和密鑰鏈管理方案(chain encryption keys to user passwords)。然而，該系統存在一些不足之處：

(1)對于洋蔥模型外層的加密和解密需要調用自定義的函數，因此還不能做到對原生數據庫不進行任何修改。

(2)當前的同態加密策略僅支持整數型的明文數據，不支持浮點型數據。

(3)在CryptDB設計中，在洋蔥模型“剝去”外層洋蔥層后，系統會在一段時間內保持該狀態，如果該列在此時間段內沒有被頻繁訪問，系統才會重新加密到最高級別。這樣的做法雖然提高了密文上的執行效率，但是不利于系統的安全性。

Tu等在CryptDB的基礎上，設計并實現了任務分割的數據庫加密系統-MONIMI[17]。該系統采用客戶端/服務器的架構，將任務分成客戶端和服務器端兩部分，通過分析查詢語句，決定任務的分配，如“A+B

SDB[18]在CryptDB和MONOMI的基礎上，解決了數據互操作性問題(data interoperability)。在數據庫查詢時，會出現查詢操作中需要涉及多列數據的情況，如“salary*year>10 000”，需要使用salary和year的數據。該方案支持多種運算，包括加減乘除、關系比較(>=)笛卡爾積、連接、sum、count、avg和groupby操作，然而SDB只能應用于整型數據。

2 可搜索數據庫加密系統體系結構設計

傳統的數據庫加密方案無法兼顧數據安全性和可操作性，而已有解決方案無法做到對用戶和數據庫完全透明，當前的全同態加解密算法尚不具有實際應用價值。在此基礎上，設計并實現了可搜索數據庫加密系統，不僅對用戶和數據庫完全透明，而且使用三種加密模型對數據進行加密，每種加密模型支持不同的查詢語句，能夠支持浮點類型數據的同態加法運算。

SSDB的體系結構如圖1所示。SSDB為可信端，數據庫服務器為不可信端。用戶輸入SQL語句，由SSDB對語句進行改寫，隱藏列名并對其中的明文進行加密，同時對數據庫中的加密層進行調整，使改寫后的語句能夠直接在密文上執行。數據庫服務器返回密文結果，由SSDB對結果集解密。

圖1 SSDB體系結構

2.1 加解密模塊

該模塊中包含了所有加解密算法的具體實現，提供對數據的加密和解密功能。使用三種加密模型對數據進行加密和解密，并能在加密的數據上進行SQL查詢。

SSDB包括三種加密模型，如圖2所示，分別為:

圖2 SSDB中的加密模型

(1)等值加密模型。

該模型采用兩層結構，在對明文數據進行加密時，使用確定加密算法(Deterministic Encryption Algorithm，DEA)進行加密，生成內層密文，其特征是相同的明文經過加密后的密文也相同，因此內層密文可以直接進行等值比較；使用隨機加密算法(Random Encryption Algorithm，REA)對內層的密文再次進行加密，形成兩層加密的結構，外層密文的特征是明文經過加密后的密文是隨機的，不泄露明文的任何信息，因此安全性最高。而在進行兩個密文等值比較時，需要先將外層密文解密，暴露出內層密文，完成操作后再重新加密，保持兩層加密的結構，使用該結構的目的是支持密文的等值比較，并且彌補明文信息暴露的缺陷。

(2)保序加密模型。

該模型采用單層加密，將明文使用保序加密算法[18-19](Order Preserving Encryption Algorithm，OPEA)進行加密，其特征是在不暴露明文的前提下，密文保持了明文的順序關系，能夠在密文上直接進行順序比較。

(3)同態加密模型。

該模型采用單層加密，使用同態加密算法[20](Homomorphic Encryption Algorithm,HEA)進行加密，其特征是將密文的加乘運算結果解密后即為明文的加乘結果，能夠在密文上直接完成數據庫操作中的sum和avg。

2.2 密鑰管理模塊

密鑰管理模塊的功能包括：一是為等值加密模型動態生成工作密鑰，根據需要加密的目標列的列名和主密鑰生成密鑰；二是對于保序和同態加密模型，在表創建時，數值型的列產生相應的列密鑰。SSDB中采用兩種密鑰管理方案：

(1)等值加密模型，其密鑰產生方案為：

Kmk,c=KeyGen(MasterKey mk, ColumnName c)

其中，MasterKey是用戶的主密鑰;c是列名。

密鑰管理器通過主密鑰和列名動態生成一個工作密鑰，提供給確定加密算法。

(2)對于保序加密模型和同態加密模型，密鑰均存儲在數據庫服務器中的元數據表中。為了保護密鑰不被竊取，元數據表會將這些密鑰加密后存儲。在加密和解密之前，SSDB會從元數據表中獲取這些密鑰。

2.3 元數據管理模塊

在創建表時，同樣需要改寫語句，將明文的字段類型改為密文字段類型，例如，用戶創建明文是int類型的id字段，而id列中的數據經過加密后的密文類型變為text。這有利于隱藏明文的屬性信息，但是需要明文屬性信息的時候，密文數據表就無法提供，需要創建一個元數據表，預先將明文的屬性信息作為數據存放在元數據表中。此外，對于保序和同態加密模型的密鑰，需要存放在元數據表中。元數據管理器的作用是對這些數據提供存儲與獲取的功能。表1是元數據表的結構示例圖。

表1 元數據表的結構

T1表由三列組成，分別為C1、C2、C3，存儲的明文類型分別為int、double、char。對于數值型數據，元數據表存儲了保序加密模型和同態加密模型的密鑰，而對于字符型數據，這兩列設置為null。

2.4 SQL語句重寫模塊

SQL語句重寫模塊對用戶提交的SQL語句進行解析，分析查詢類型，包括create、select、insert、update、delete，并對語句中包含的明文數據進行加密，對列名進行修改，下面通過一個例子說明：

用戶輸入語句：

select name from student where id=1;

SSDB輸出語句：

select c1_DEA from student where c2_DEA=‘Edafdfgk==’;

“id=1”屬于等值匹配的操作謂詞，解析函數調用加解密模塊對明文數字1使用等值加密模型進行加密，得到密文‘Edafdfgk==’，并且將列名id改寫為c2_DEA，代表在密文上將使用等值加密模型的列，select…from部分的列名也將被改寫為c1_DEA，表示從等值加密模型中獲取密文。

2.5 數據庫連接模塊

數據庫連接模塊負責連接數據庫，該模塊存儲了遠程數據庫的連接信息，并且能夠改變遠程的數據庫服務器，該模塊負責啟用新的連接方式。

3 系統實現及性能分析

3.1 系統實現

該系統編程語言采用Java，數據庫為MySQL，使用JSQLParser開源項目實現了SQL語句的解析功能。由于明文數據經過等值模型的加密后形成的二進制密文數據不利于存儲，所以在實現過程中，使用BASE64編碼對二進制數據進行轉換，最終以字符類型的密文數據存儲在數據庫中。

開發環境如下：

(1)硬件：處理器為Intel Core i5-2410M，內存為6 GB。

(2)軟件：操作系統為Windows 7，Java開發環境為JDK1.8，MySQL版本為5.7。

實驗使用兩臺計算機分別為SSDB可信端和不可信的服務器端，服務器端安裝MySQL作為DBMS，其硬件配置均為4核Intel Xeon E3-1226 CPU@3.3 GHz，內存為16 G，運行CentOS系統。CryptDB使用三臺服務器，分別為客戶端、中間代理和數據庫服務器。

3.2 性能測試與分析

對SSDB的性能進行測試分析，分別對插入、查詢、更新、刪除操作設計相應的測試語句，并在相同的條件下與CryptDB系統進行對比。實驗結果表明，該系統能夠在密文上直接完成增刪改查的功能，具有可用價值，通過對insert、select、update、delete語句的對比實驗，SSDB在執行效率上優于CryptDB。

3.2.1 測試方案

創建名為college的測試數據庫，其中包含兩張表：student表存儲了學生信息，包括姓名、學號、年齡、性別字段；grade表存儲了學生的成績信息，包括學號、成績字段。其中grade中的學號字段是student中學號字段的外鍵,rowid字段作為隨機加密的參數，不進行加密。

實驗針對常用SQL操作設計用于測試的執行語句：

(1)Insert(插入數據)：

insert into student(id,name,age,sex) values(1001,“alice”,22,“female”);

insert into grade(id,grade) values(1001,“alice”,22,”“female”);

(2)Select(等值查詢)：

Select*from student where age=18;

(3)Range(與順序相關的查詢操作):

Select name from student where age>18;

(4)Sum(與加法相關的查詢操作):

Select sum(grade) from grade;

(5)Join(與表連接相關的查詢操作):

Select student.name from student join grade on student.id=grade.id wheregrade.grade>60;

(6)Update(更新數據):

Updategrade set grade=grade+10;

(7)Delete(刪除數據):

Delete from student where age<18;

3.2.2 測試結果及分析

對SSDB中所使用的部分加密模型的時間花費進行測試，結果如表2所示。

表2 加密模型的時間開銷

保序加密模型中使用的算法具有不可逆的特點，因此無法計算解密時間，從實驗結果可以看出，保序加密模型和加法同態模型支持浮點類型的數據，加解密的效率高，提高了系統復雜查詢的性能。

CryptDB是首個利用部分同態加密算法并且支持在密文上直接執行SQL語句的加密系統。SSDB在CryptDB的基礎上，改進了加密模型和系統結構，因此有必要將兩者進行對比。實驗對8種SQL語句進行了測試，圖3是SSDB與CryptDB的對比結果。

從圖3(a)可以看出，SSDB的增刪改查的執行效率高于CryptDB，說明了該系統的有效性。

在空間開銷上，由于SSDB采用最多兩層結構的加密模型，因此減少了密文的存儲空間，如圖3(b)所示。向數據庫中插入103、104和105條記錄，通過統計CryptDB和SSDB產生的數據庫文件大小來進行對比分析。

測試結果顯示，SSDB與CryptDB相比，降低了空間開銷，與明文相比，在小數據量的情況下，能夠保持較少的額外空間開銷。

圖3 與CryptDB的對比實驗

4 結束語

可搜索數據庫加密系統—SSDB，針對傳統數據庫加密方式無法兼顧數據安全性和密文上復雜查詢的缺陷，通過可動態調整的兩層加密模型和重寫查詢語句，在密文上直接執行復雜的SQL語句，包括創建表、插入操作、有條件的選擇查詢、更新操作和刪除操作，支持字符類型數據的等值匹配，整數類型和浮點類型的密文排序和同態運算，在保護數據機密性的同時，提高了查詢效率。通過與CryptDB的對比，表明該系統是有效、可行的。

[1] 孟小峰,慈 祥.大數據管理:概念,技術與挑戰[J].計算機研究與發展,2013,50(1):146-169.

[2] 黃劉生,田苗苗,黃 河.大數據隱私保護密碼技術研究綜述[J].軟件學報,2015,26(4):945-959.

[3] Rivest R L,Adleman L,Dertouzos M L.On data banks and privacy homomorphisms[M]//Foundations of secure computation.New York:Academic Press,1978:169-179.

[4] 劉明潔,王 安.全同態加密研究動態及其應用概述[J].計算機研究與發展,2014,51(12):2593-2603.

[5] Popa R A,Redfield C M S,Zeldovich N,et al.CryptDB:protecting confidentiality with encrypted query processing[C]//ACM special interest group on operating systems.New York:ACM,2011:85-100.

[6] Raluca A,Popa N,Zeldovich H,et al.CryptDB:a practical encrypted relational DBMS[R].Cambridge,USA:MIT Computer Science and Artificial Intelligence Laboratory,Tech,2011.

[7] 沈志榮,薛 巍,舒繼武.可搜索加密機制研究與進展[J].軟件學報,2014,25(4):880-895.

[8] Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted data[M]//Applied cryptography and network security.Berlin:Springer-Verlag,2004:31-45.

[9] Wang C,Cao N,Li J,et al.Secure ranked keyword search over encrypted cloud data[C]//International conference on distributed computing systems.New York:IEEE,2010:253-262.

[10] Li J,Wang Q,Wang C,et al.Fuzzy keyword search over encrypted data in cloud computing[C]//International conference on computer communications.New Jersey:IEEE,2010:441-445.

[11] Boneh D,Crescenzo G D,Ostrovsky R,et al.Public key encryption with keyword search[C]//Advances in cryptology.Berlin:Springer-Verlag,2004:506-522.

[12] Shi E,Bethencourt J,Chan T H H,et al.Multi-dimensional range query over encrypted data[C]//IEEE symposium on security and privacy.New York:IEEE,2007:350-364.

[13] Cao N,Wang C,Li M,et al.Privacy-preserving multi-keyword ranked search over encrypted cloud data[C]//Proceedings of INFOCOM.Shanghai:IEEE,2011:829-837.

[14] Dan B,Waters B.Conjunctive,subset,and range queries on encrypted data[C]//Theory of cryptography.Berlin:Springer-Verlag,2006:535-554.

[15] 楊 寧,金 逸,劉 丹,等.云環境下可搜索加密技術安全機制及應用陷阱[J].計算機應用研究,2015,32(8):2254-2260.

[16] 陳 萍,張 濤,趙 敏,等.面向托管的數據庫即服務系統及其隱私保護技術[J].計算機科學,2013,40(11):140-142.

[17] Ferretti L,Colajanni M,Marchetti M.Distributed,concurrent,and independent access to encrypted cloud databases[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(2):437-446.

[18] 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,2015,59:198-207.

[19] 周 雄,李陶深,黃汝維.云環境下基于隨機間隔的保序加密算法[J].太原理工大學學報,2015(6):741-748.

[20] Liu D.Homomorphic encryption for database querying:U.S.,14/410,548[P].2013-06-21.

Design and Implementation of Searchable Database Encryption System

WANG Hai-wei，YANG Geng，LIU Guo-xiu,ZENG Cheng-kun

(College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Data privacy protection has become an urgent problem in network applications.The alternative solution is to store the private data in the database after encryption.However,there are some defects in this approach,including the loss of some attributes of plaintext after encrypted data,such as the order of the data.The original operation on the plaintext cannot be implemented in the ciphertext,and all the ciphertext need to be decrypted.Therefore,the efficiency is less than the plaintext database in the face of large-scale database storage.In order to solve the problem that the SQL operation cannot be executed on the ciphertext directly while ensuring the security,it is urgent to design an efficient and secure encryption model.A searchable database encryption system including functions of SQL statement rewriting,plaintext data encryption and query processing is proposed.The system implements dynamic encryption in the process of statement execution,complex SQL statements to be executed on ciphertext,to avoid exposing plaintext by the untrusted database server which can protect the data privacy.The experimental results show that the system has better effectiveness and safety.

SQL query;ciphertext query;searchable database encryption;data privacy-preserving

2016-08-17

2016-11-29 網絡出版時間：2017-06-05

國家自然科學基金資助項目(61272084，61572263)

汪海偉(1989-)，男，碩士研究生，研究方向為云計算安全、大數據隱私保護；楊 庚,博士,教授，CCF高級會員,研究方向為云計算與安全、分布與并行計算、大數據隱私保護。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170605.1508.060.html

TP302

A

1673-629X(2017)08-0130-05

10.3969/j.issn.1673-629X.2017.08.027