第44卷第4期2021年4月
Vol.44Ao.4
Apr.2021计算机学报
CHINESE JOURNAL OF COMPUTERS
基于可搜索加密机制的数据库加密方案
孙僖泽周福才李宇溪张宗烨
（东北大学软件学院沈阳第0年）
摘要近年来，数据外包的日益普及引发了数据泄露的问题，云服务器要确保存储的数据具有足够的安全性•为
了解决这一问题，亟需设计一套高效可行的数据库加密方案•可搜索加密技术可较好地解决面向非结构文件的查
询加密问题，但是仍未较好地应用在数据库中.因此，针对上述问题，提出基于可搜索加密机制的数据库
加密方案.
本文贡献如下：第一，构造完整的密态数据库查询框架，保证了数据的安全性且支持在加密的数据库上进行高效的
查询；第二，提出了满足ND-CHA1安全的数据库加密方案，在支持多种查询语句的前提下，保证数据不会被泄
露，同时在查询期间不会降低数据库中的密文的安全性；第三，本方案具有可移植性，可以适配目前主流的数据库，
如MySQL.PostgreSQL等.本文基于可搜索加密方案中安全索引的构建思想，利用非确定性加密方案和保序加密
方案构建密态数据库安全索引结构，利用同态加密以及ARS-CBO密码技术对数据库中的数据进行加密，实现丰富
的SQL查询，包括等值查询、布尔查询、聚合查询、范围查询以及排序查询等.本方案较BlindSeee在功能性方面增
月朗天门
加了聚合查询的支持，本方案改善了CryptDB方案执行完成SQL查询后产生相等性泄露和顺序泄露的安全性问
题，既保证了数据库中密文的安全性，又保证了系统的可用性可后数们使用一个有年000条记录的StudenD表进
行实验，验证了方案框架以及算法的有效加同时，将本方案与同类方案进行功能和安全性比较，结果表明本方案
在安全性和功能性之间取得了很好的平衡为
关键词密态数据库；可搜索加密；同态加密第ES加密;SQL查询
中图法分类号TP309DOI号年2年97/SP.J.年16.2021.00806
A Database Encryption Scheme Based on Searchable Encryption
SUE Xi-Ze ZHOU Fu-CO Li Yu-Xi ZHANG Zong-Ye
(Software College,NorLheasLern UniuersiLy,Shenyang110169)
Abstract N recegg gears,the increasin-popularitp ol outsourcin-data D cloud servee hat leS表
data leakape groblems,we neeS D ensure thah the dats storeS Y cloud server Y sufficientlp secure.N Y necessarp to desigc efficient anS feasible database encryption schemes to solve this problem.Searchable encryption can make^ncrypteS daD searchable while solve daD leakape problem for non-structural film,but it is still not well eplied Y the database.Therefore,Y Die paper,aiminp a_t the problem that the da_ta_Y the database servee is leaked,we designed a dah-base encryption framework based on searchable encryption.The noveltp of this work comee with three contributions.First,we construd a well-defined encrypten database query eramewory, which not only ensure the securitp of data,bui to made the encrypted query efficieS.Second,
Oue scheme is secure undee INA-CHAI(semantir security againsi adaptive choses keyword p Z-tacb),it ensuree that the date is not compromised and that the securitp of the ciphertext Y the
收稿日期第年-Y1在线发布日期:2020-06-30.本课题得到国家自然科学基金(62072090,61872069).中央高校基本科研业务费项目重点科学研究引导项目东201)资助.孙僖泽，硕士，主主研究领域为可搜索加密、密态数据库.T-mail：周福才东信作者)，博士，教授，中国计算机学会东CF)会员，主主研究领域为密码学、网络安全、可信计算.T-mail：thou@miL s edu.周.李宇溪，博士，主要研究领域为可搜索加密、云安全.张宗烨，博士，主主研究领域为可搜索加密.
祝福老师的贺卡4期孙僖泽等：基于可搜索加密机制的数据库加密方案807
database is not compromised during the query.Third,our framework achieves high portability and is suitablr for many mainstream databases such me MySQL,PostgreSQL and se oo.Tased on the ides of constructing securs index in searchabls encryptioo scheme,Ws uss cryptographic techniques such be homomorphio oncryptioo and AES-CBC to encrypt database.Ous scheme implemente rich SQL queriee,including equivaleoa query,Boolean query,aggregated querp, rants411X0,sort querp and so oo.O us scheme adb support for aggregateS queriee compared ta BlindSees in functionalitp.Compared to CryptDC,ous scheme doee not reveat the equalitp and the ordee of the ciphertext,which not onlp ensuree the securitp of the ciphertext in the database, bua also ensuree the availabilitp of the systern.Finally,we use s student table which hae10007 records to evaluate oue schenm,and the results show that the proposed framewory and algorithe are eSectivc.A c the same tirnw we compare the functionalitp and securitp of oue scherne with similae schemee,and oue scherne achievee o gooO balance between securitp and functionalitp.
Keywords encrypted database；searchable symmetrio encryptiod；homomorphio encryptiod；
AES encryptiod；SQL querp
1引言
随着数据量的增加，人们越来越倾向于选择将自有数据依托于第三方数据库服务提供商进行存储.目前将数据存储在外包数据库服务器上已成为一种常见的方案，常见的如华为、京东、阿里巴巴、亚
马逊以及一些医院等机构将一些主要的信息存储在外包数据库服务器上.随着外包数据库服务器中存储信息量的增多，外包数据库服务器上的信息泄露（需要受保护的信息或隐私被泄露）引发了广泛关注.外包数据库服务器方面常常出现泄露或篡改等安全问题，因为潜在的恶意外包数据库服务器可能会尝试从他们存储的数据及其处理的查询中学习信息，甚至将其泄露给某些未经授权方O-种行之有效的方法是在将数据存储到外包数据库服务器中之前对数据进行加密.但是，这种需求是以功能为代价，一旦数据被加密，在查询时需要先解密数据，这样导致搜索变得困难.因此，安全研究人员已转向研究既保护数据库内容又支持高效操作（如搜索引勺方案，而不是仅仅加密数据.为了解决云服务器中的文档信息泄露的问题,2007年Song等人提出了可搜索加密方案，该方案通过输入单个关键字在云服务器上对加密文件集进行搜索⑵；CurtmoO等人在2006年提出了更高效更安全的方案，且该方案实现了多用户的SSS；；Kamara等人在2012年提出的方案中扩展了倒排索引方法，在保证安全性的前提下满足了次线性搜索效率并可以有效添加和删除文件42014年这ash等人提出了大数据集下的动态可搜索加密方案曰.上述这些方案都只局限于文件集的搜索，目前更多的企业、政府会把信息存储在数据库中，因此如何实现密态数据库的密文查询问题，具有重要现实意义和实用价值.
为了解决数据库中数据的安全问题,2004年, Hore等人提出了一种基于数据库关系表构建的安全索引实现模糊范围查询—美国乔治亚理工学院的Amanatidie等人于2007年针对外包数据库的安全性研究提出了基于分组密码，对称加密方案和消息认证码等标准密码原语的加密模型，该方案能进行简单的密文搜索◎2010年Popa等人提出了CryptDC，为了支持更多的查询，设计了洋葱加密模型因卩一个数据通过多种加密方案进行嵌套加密. CryptDC针对字符类型列将其扩展为四列密态属性列，分别是初始向量列、通过EQ洋葱模型加密的列、ORD洋葱模型加密的列政earch洋葱模型加密的列，针对数值类型的就不会生成由Search洋葱模型加密的列，但是为了进行SUM操作生成了通过H0R洋葱模型加密的列然而CryptDC存在两个问题，其一是将明文数据库转换为密文数据库时有些密文列占用了更多存储的空间，这样无疑在查询时增加了磁盘读写开销，从而影响了系统的性能；其二是是通过洋葱模型对每个列进行加密，导致每剥掉一层洋葱加密层，它的安全性都会降低，尤其做等值查询时，会将加密方案降低到DQT方案，该
808计算机学报2021年
方案是确定性加密方案，极易泄露明文之间的信息，因此CryptDB的安全性一直饱受争议.2014年，Pappas等人提出了BlindSeey数据库加密方案，该方案通过Bloom filter、Yao混淆电路、BF搜索树技术实现了支持等值查询、布尔查询、范围查询的密态数据库系统，该方案的安全性较高，但是在查询过程中存在一定的误报并且支持的查询类型不够丰富年.2016年该oddar等人提出了Arx系统，该方案柳云龙简介
是通过Yao混淆电路和Arx-RANGE索引结构、Arx-EQ索引结构实现的，但是该方案适用于非关系型数据库年.2017年Momr等人提出一种通过索引搜索的数据库加密方案，该方案仅支持等值查询、布尔查询和范围查询，不能支持其他SQL （Structur等Querp Language）语句查询，同时其范围查询的效率非常低年.
针对外包数据库中的数据泄露问题，以及现有的数据库加密方案不能将方案的安全性与功能性兼顾的问题，本文提出基于可搜索加密机制的数据库力□密方案（DataBase encryptiog schemr based on Searchablr Encryption,DB_SE），相比于其他方案，本方案既实现了数据的安全性，又能满足现实场景中功能性的需求，主要贡献如下：
⑴提出基于可搜索加密机制的密态数据库查询框架，该框架有效地保证了在外包数据库服务器中存储的数据的安全性，并可以在加密的数据库上进行高效地查询.
⑴基于提出的框架，设计了一个满足ING-CKA年年（选择关键词攻击下的索引不可区分性）安全的数据库加密方案，通过语义安全的加密方案对数据进行加密，不会造成信息泄露问题.
选）方案支持丰富的SQL查询，包括等值查询、布尔查询、比较查询、聚合查询、范围查询、排序查询等多种复杂查询.其中，本方案通过构建保序安全索引进行范围查询，其范围查询的效率优于同类主流方案2
选）本方案的框架具有可移植性，可适配于MySQLYos等reSQL等主流数据库，支持透明的SQL查询但卩在不需要更改SQL语义的情况下进行正常地查询，保证了本方案的可移植性.
本文第0节介绍关于可搜索加密技术、哈希函数以及OPES加密算法；在第3节介绍本方案的框架、形式化定义、关键算法等内容；第4节对本方案进行安全性分析；第5节从功能性和安全性方面与两种主流的数据库加密方案进行对比，并通过实验进行性能测试；第6节总结本文所述的工作，并对未来研究作出展望.
2预备知识
2.1可搜索加密技术
可搜索加密最早是由S。混等人⑵提出的，该技术是一种加密搜索模式，使得在对加密数据进行搜索的过程中，不会对恶意服务器泄露敏感信息.可搜索的对称加密（SSE）允许用户以私密方式将其数据存储在外包云⑴务器）上，同时保持有搜索它的能力.可搜索加密技术包含用户和云服务器两个实体：用户对文件进行加密处理生成密文，同时生成文件索引，再对文件索引处理生成安全索引.将密文与安全索引上传到云服务器存储.在进行更新时，用户使用私钥与更新内容生成更新索引，并发送至服务器，服务器根据更新索引进行计算，完成更新操作.在在行搜索时，用户使用私钥与搜索关键字生成搜索令牌，将其发送至云服务器，云服务器根据构建的搜索令牌在加密的文件中进行搜索，将查询出的
密文结果进行解密，最后将明文结果返回给客户端.
对称可搜索加密方案由Curtmolo等人于2006年提出，该方案基于索引构建，方案包括了五个函数-.GenYnc Yrapdoor^Search-Yec.
sk-Gen⑴）为概率性算法，用于生成密钥，由用户执行.输入安全参数犽，输出私钥sk.
选,DG”c（D,D）为概率性算法，用于构建安全索引和加密文档集合，由用户执行.输入私钥K 和文档集合Doc=（D（h，…，Doc…C，输出安全索引［和加密文档集合EncDhc=D DncDoh，…, EncDoc c）.
t^Trapdoor^sk,d）为确定性算法，用于生成关键字的陷门，由用户执行.输入私钥sk和关键字2，输出陷门狋.
XGearchD,D为确定性算法，用于搜索包含关键字疋的文档，运行于服务端.输入安全索引和和陷门t，输出加密文档集合X.
Doc犻-Dec⑴包ncDoD为确定性算法，用于解密密文文档，由用户执行.输入私钥sk和加密文档EncDhc,，输出文档Doc,-
2.2哈希函数
哈希函数也被称为散列函数，可以将任意长度
4期孙僖泽等：基于可搜索加密机制的数据库加密方案800
的数据输出为固定长度哈希值.理想的哈希函数具有单向性、抗碰撞性和映射分布均匀性等特性.可应用于消息认证、数字签名、文件校验等方面.
华裔是什么哈希函数族可表示为多项式时间计算映射H：!X"-#，犎犓东）表示哈希函数关于K的运算.对于一个好的哈希函数来说，攻击者很难在"中到两个不同元素，使它们能够计算出#中的相同元素，这一属性被称为抵抗碰撞攻击.
使用犎第X"f#表示哈希函数族，敌手犃到两个不同元素使计算出相同结果的优势表示为
$
Adores）[K—!,（东，犕'）资A（东资
M犕犕A犎（东会犎犓（东资.
如果对于任何多项式时间的敌手A来说,
怎么改qq密码犃犎东是可忽略的验犎是能够抵抗碰撞攻击的哈希函数族理
随机预言机东0）-般由哈希函数来实例化.但是许多哈希函数具有的属性使其不适合直接用作随机预言机，比如：当消息和密钥长度已知时，采取H（密钥||消息）方式构造的哈希函数易被进行长度扩展攻击.密钥散列消息认证码（HMAC）未采用该构造方式，故可以抵抗该攻击.因此，本文使用带有公钥的HAAC构造来实例化RO，对于哈希函数来说，比MAC的定义为HMAC（H保）= H（（密㊉o pad'）会H（H㊉i pad）.re），其中，opad和i狆是两个常数，保是异或操作.
2.3OPES加密
OPES（Hrdee Preservinp Encryption Scheme）加密算法是一种保序加密算法，该算法可以使密文仍然保留对应的明文的顺序信息.传统的加密方案为了保护数据的机密性需要精确匹配才能查询，在实际需求中针对数值类型的数据经常会使用比较查询操作，但使用传统的加密算法不能容易地执行比较查询操作，OPES加密算法是为了解决这一问题被设计的，OPES算法在保证数据机密性的同时具有较好的查询功能年.
OPES加密算法允许在不对密文进行解密的情况下直接对加密数据进行比较操作，因此对于密文的比较查询布序操作以及求最大最小值操作使用OPES加密算法非常适合.同时OPES还具有以下特性：
密）对使用OPES加密的数据进行查询处理的结果是准确的.既不存在任何误报，也不遗漏任何答案元组.不会产生的查询结果的超集，因此省去了复杂的过滤步骤.
H）OPES可以很好地处理更新操作.在修改列中的值或添加列中的值的时候不需要更改其他已存在的密文值.
H）OPES可以很容易地与现有的数据库系统集成，因为它已经被设计为与现有的索引结构密B 树）一起工作.数据库被加密的事实可以对应用程序透明.
密）OPES的时间和空间开销对于在实际系统中部署OPES是合理的.
入侵者可以访问通过OPES算法加密的数据库，但没有数据库中值的分布之类的先验信息，并且不能对他选择的任意值进行加密或解密.在这样的环境中，OPES对于能够获得加密值的严格估计的对手是稳健的.最终在DB0上的实现的测量结果表明，OPES在查询处理上的性能开销很小，对于在生产环境中部署OPES是合理的.
3DB_SE方案
3.3方案框架
本文采用满足INE-CPA（自适应选择明文攻击）安全的加密方案加密密据表，结合可搜索加密思想构建安全索引，在保证数据表机密性的同时，实现功能性查询.本文将加密的数据表和基于数据表构造的安全索引结构独立存放在数据库服务器中第I 入一个代理服务器，负责构建加密索引、SQL解析与重写、加解密操作在据库服务器主要负责将代理服务器生成的加密的SQL语句在安全索引中查询、更新操作.本方案框架如图1所示.
本方案的系统框架由三种实体组成，分别是客户端、代理服务器端、托管敏感数据的不受信任的数据库服务器端.本框架分为两个区域，分别是可信区域（Trusted Zone）和不可信区域（UntrustW Zone）.
可信区域包括用户的客户端和代理服务器端Proxy两个实体.客户端负责进行正常的SQL查询；代理服务器端在密态数据库生成阶段负责生成密钥、根据策略表对原始数据表进行表结构重构、按照策略表的加密方案对原数据表进行加密并生成每张表对应的安全索引结构第roxy在查询阶段负责截取由客户端发送的SQL请求，结合可搜索加密思想提取SQL中的关键词并生成搜索陷门，将SQL
817计算机学报2020年
转换为SEQ(Search Encrypt Query)，发送给数据库服务器，当数据库服务器返回查询结果时，将返回的密文数据解密并返回给客户端.
不可信区域为不可信的数据库服务器DS,DS 中存储着加密的数据库和用于搜索的安全索引表，索引表中每条记录对应着由数据表构建的安全索引.由于在数据库服务器中，数据库存储的信息是加密的，用户和数据库管理员即使获得了内部数据也无法进行解密获得明文数据•在查询阶段，DS主要负责执行由代理服务器生成的SEQ以及更新安全索引操作.
3.2用例
本方案解决了基于可搜索加密机制在密态数据库中进行透明的SQL查询该卩在不改变SQL语义的情况下进行SQL查询.本方案主要包括密钥生成、索引的构建、索引的更新、结构化数据加密以及透明的SQL查询五个部分.为了更好地解释这些算法，通过一个实例来说明.假设数据库系统中有一个记录学校信息的数据库，里面包含多张数据表，其中一张是表Student其tudent表的部分信息如表0所示.
表1Student表信息
等snarne sage sgendes Math EnglisE portrait
0Petes03male145年2http：/Dschool/stu/peter,jpo 0Alics20female78114school/stu/alice.jpo 3B(O03male10698school/stu/bob.jpo
4Susad07female106177http：//school/stu/Susan,jpg
3・3形式化定义
本方案包含5个算法，分别是：密钥生成算法、安全索引生成算法索数据表加密算法索安全索引更新算法以及安全索引搜索算法.具体如下：
需)密钥生成算法
KeyG等需犽—GK：客户端运行该算法，给定一个安全参数k作为输入，系统输出密钥组GK.密钥组GK由三个伪随机生成的密钥：且和：组成，分别用于两个伪随机排列函数如和£)和一个散列函数Y
需)安全索引生成算法
Index狓一Buildindex t Table,GK):Proxp运行该算法，将数据表ai和密钥组G K作为输入，输出安全索弓I，其中GK为由KeyGen算法输出的密钥组密
需)数据表加密算法
EncTa l oBncryptTame(如犫e,Gey):Proxp 运行该算法，将明文数据表Table和密钥Key作为输入，输出密文数据表EncTable.
需)安全索引更新算法
Index-UpdatelndepC TrapdoorXet,U,Index): DS运行该算法，将从Proxy发送的更新关键词令牌集合TrapdoorXet和更新的犐值以及D S中的原安全索引Indey作为输入，输出新的安全索引Index.
需个：安全索引搜索法法qq飞车音乐
IdSet(uu')Search(f w,Index'):DS运行该算法，将关键词生成的搜索令牌和安全索引作为算法的输入，算法输出符合该查询条件的记录Id值集合密
3.4方案的详细描述
3.40安全索引生成算法
Indey狓Buildlnd等t Table犲GK):Proxp运行