可搜索数据库加密系统的设计与实现

汪海伟,杨 庚，刘国秀，曾橙焜

(南京邮电大学 计算机学院,江苏 南京 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