基于加密数据库的快速查询方法研究

◆王福超 牛长春

（华北水利水电大学信息工程学院 河南 450046）

1 引言

随着无线网络以及智能手机的普及，人们在生活、工作和学习中使用着越来越多的网络应用。尤其是近几年，各种订票软件、订餐软件、租房软件成为人们日常生活的常用品。用户在使用这些产品的同时，产生了大量的数据存储在企业的数据库中。目前大多数企业为了减少维护成本，会选择将收集到的数据存储到云数据库中，让第三方代替维护和管理，这就造成了不可避免的安全隐患。因为数据库的管理人员属于可靠但好奇的角色，在对数据库进行管理时，不可避免地要访问到企业内部重要资料、收集用户的数据，并具有对数据的查看权和修改权，即使排除数据库管理人员对数据库安全的威胁因素，仍存在当数据库被黑客攻击后造成数据泄漏的风险。

为保证用户的隐私安全，排除来自企业内部的威胁因素，目前最常用也是最可靠的方法之一是将关键信息加密后再向数据库中存储。但明文信息被加密成密文后就失去了自身的属性，尤其是当数值型数据被加密后，无法直接进行比较和运算，当需要进行这些操作时，密文需要被全部解密成明文后才能完成，这将严重耗费系统资源。针对这种问题，近几年，有不少相关的新技术相继被学者们提出。如保持有序加密技术、同态加密技术、密文索引查询技术等，但能够将这些技术综合到一个系统实现的还不多。本文主要在关系型数据库中的密文数据提供高效查询，并提供添加、更新、删除数据和密钥管理的功能。根据加密数据库的缺点，将结合较新的技术达到能快速对数据执行加解密，且加密强度足够高。对密钥管理灵活高效，不能占用系统大量的资源，要保证密钥的安全性，数据在加密存储后，支持对密文的快速查询。支持多种常用的查询语句。如等值查询、范围查询等，同时应支持部分函数查询，并实现快速查询。

2 研究现状

目前，针对数据库加密的研究主要集中在加密技术的选择、加密算法的改进以及对密钥的安全管理等方面。2016 年，黄保华等人[1]分别针对字符型和数值型数据提出了一种基于索引技术的二阶段查询方案，该方案的设计思路是从时间性能和过滤性能两方面来提高查询效率。对于数值型数据，分别使用单调和非单调函数确保索引的过滤性和安全性。对于字符型数据，通过构造敏感字符信息矩阵，达到过滤不需要的密文数据以减少解密时间的效果。但对于使用该方案带来的存储索引空间消耗较大的问题，作者没有给出有效的解决方案。2017 年，王伟等人[2]使用MapReduce 编程框架并结合已有的CryptDB 加密系统的工作原理，设计了一款基于B/S 架构的并行密文数据库系统。作者的设计思路是将云计算技术与可搜索加密技术融合使用，使用任务调度算法来产生适当的任务分配策略，使加密和存储大规模数据的性能和速度得到明显提升。S.Muthurajkumar 等人[3]提出了一种将时间约束与Map reduce 算法相结合的时态安全云图约简算法，以及本文新提出的链式Hill 密码加密算法。该算法的主要优点是减少了处理时间，有效地保证了系统的安全性。Sha Ma 等人[4]提出了标准模型中第一个使用光滑投影哈希函数（SPHF）的泛型PCE，并证明了它的s-priv1-cca 安全与当前的断开安全无关。本文设计了支持快速查询的加密模型，并实现了模型中使用的三种加密算法，将输入的明文数据使用三种算法加密后分别存储到数据库中，查询时该模型可根据查询语句的类型来匹配数据库中相应的密文数据，进而支持在加密数据库中可直接对密文进行比较和运算，提高对加密数据库的查询速度。

3 模型设计

支持速查的加密模型设计参考了CryptDB 系统的洋葱加密模型[5]，洋葱模型具有集多种算法于一体，支持快速查询并能确保加密数据足够安全的优秀性能，但也显得有些臃肿。本人将其简化后设计成新的加密模型为系统使用，如图1 所示，分别为确定加密模型（DET 模型）、保序加密模型（OPE 模型）和同态加密模型（Hom 模型），这些模型的使用能显著提高系统对密文数据的查询速度。此外，为提高数据安全性，分别在确定加密层和保序加密层上各包装一层随机加密模型（RND 模型）。并将这三种模型结合起来使用，其模型的功能介绍如下。

图1 系统使用的加密模型

3.1 基础模型简介

确定加密模型（DET 模型），该模型在设计中使用到了两层加密，里层使用的是确定加密层，外层包装上随机加密层。DET模型的特点是相同的明文V 通过算法加密后的值C 也是确定的。使用此模型可加快等值查询的速度。保序加密模型（OPE 模型）该模型用到的算法是文献[6]中提出的非线性保序索引算法（OPE算法），该算法能满足加密后的索引数据仍能保持明文顺序的需求。如明文V1＜ V2，则将明文加密后的索引值I1＜ I2。利用这种特性可以直接在密文上完成明文关系的比较，提高查询效率。同态加密模型（Hom 模型），模型主要负责加密用户表中的数值型数据，其使用的算法是文献[7-8]提出的同态加密算法（Hom 算法），此算法的特点是，加密后得到的密文分组可直接参与计算。因此我们可以直接使用MySql 内置的聚集函数，从而提高函数查询的速度。

3.2 随机加密模型（RND 模型）

RND 模型的主要作用是包装DET 模型和OPE 模型。作为强加密层，它能有效隐藏密文可能会暴露出来的明文特征，提高被包装模型处理数据的安全性。该模型使用的算法简称RND 算法，具体使用的是数据库中内置的AES 算法，为方便操作，把每条记录的行号和主密钥作为算法密钥，以表名和字段名为条件执行加解密操作。该模型还有个特点是可以动态的包装和剥离，当用户通过系统向数据库中存入密文数据C 后，还需要把C 当作参数使用此模型处理成新的密文数据后再存储，查询C 时则把待查询属性列的所有数据项的RND 层全部剥离，查询完成再立即对其包装。使用该模型可保证数据一直处于安全状态。

4 速查性能测试与分析

为了对模型进行效率评估，我们分别在两种条件下进行测试。首先在数据量大小一定的情况下，使用不同种类的查询语句，分别测试语句在执行过程中各个模块的详细耗时情况。其次测试在不同数据样本下，使用相同查询语句的查询性能，最后对系统进行综合评价。

4.1 数据库中数据样本大小确定，执行不同类型的查询语句。

测试条件：表中共2000 条数据记录。

测试语句：select id， tname， tage， tsex from teacher where tname='邢567'；

表1 等值查询耗时统计表

第三次 15ms 1ms 111ms ＜1ms 141ms 268ms 平均耗时 15.3ms 3.3 122.3 ＜1ms 109.3ms 250.3ms

测试语句：select tname， tage， tsex from teacher where id ＜ 10；

表2 范围查询耗时统计表

测试语句：select salary.bsalary，teacher.tname from salary inner join teacher on teacher.id = salary.id where teacher.id = 120；

表3 连接查询耗时统计表

测试语句：select avg（bsalary） from salary where id ＜ 1000；

表4 函数查询耗时统计表

分析表1、4 看出系统在执行等值查询和函数查询操作时耗时比较短，分别为250.3ms 和260.7ms。相对从表2、3 中的对比发现，范围查询和连接查询操作的耗时比较长，分别为460ms和457ms。造成这种现象的原因是：前两种查询方式只需将部分确定加密的字段去除随机层（函数查询不需要），且需要解密的密文较少。而后两者查询方式中，范围查询操作需要对使用了确定加密和保序加密的字段全部去除随机层，并且需要解密的密文集较大。此外，连接查询还涉及多表之间的连接，因此耗时较长。

从执行过程中各模块的耗时情况来看，对语句的重构操作和执行操作花费的时间最短，几乎在2 毫秒以内。获取元信息操作耗时也比较短，因为其只需要执行一条查询元信息表的语句，将返回的元信息保存即可。最耗时的是随机加密层的处理操作，因为系统加密粒度是字段级别的，需要对字段中的所有数据执行加解密操作。

4.2 数据库中数据样本大小不确定，执行相同类型的查询语句，如表5 所示：

表5 不同样本下的查询操作耗时表

3000 条 11ms 1ms 157ms ＜1ms 110ms 279ms 1548ms 5000 条 13ms 1ms 377ms ＜1ms 108ms 499ms 3246ms 10000 条 10ms 2ms 455ms ＜1ms 109ms 576ms 6254ms 15000 条 10ms 2ms 609ms ＜1ms 110ms 731ms 12562ms

测试条件：分别有1000 条、3000 条、5000 条、10000 条、20000 条记录。

测试语句：select * from teacher where id = 656；

根据表5 可以发现，查询操作中耗时最短的依然是sql 语句重构操作和执行操作，接下来耗时较短的分别是元信息获取操作和解密并显示出结果操作。这些操作的耗时是比较稳定的，不会随着样本数量的改变而产生大幅度变化。但对于随机加密层的处理操作，其耗时是随着查询样本数据的增多而增加。

根据表5 绘制出折线图如图3 所示：该图清晰地显示出系统查询耗时与数据样本之间的关系。从图中可以看出，在所使用的查询语句相同的情况下，随着数据表中的数据样本的不断增大，查询所耗费的时间也近似呈现出线性增加的趋势，这反映出本系统具有良好的稳定性。与使用普通加密策略的查询耗时结果对比，系统具有较快的查询速度。

图3 查询耗时-样本关系折线图

5 总结

对隐私的保护催生出了数据库加密技术，而把数据加密之后又会显露出无法对密文直接进行比较和运算，导致查询速度过慢的问题。通过研究和分析，本人提出了综合使用索引技术和同态技术将数据加密的方案来实现对加密数据库的快速查询，并设计了支持速查的安全加密模型。模型中用到的每种算法加密后的数据都有各自的特性，将这些密文数据分别存储后，利用数据的特性来提高系统对等值查询、范围查询和函数查询的查询速度。