一种支持密文数据操作的关系型数据库安全外包数据处理方法

摘要

本发明公开了一种支持密文数据操作的关系型数据库安全外包数据处理方法。本方法为：1)数据库拥有者利用私有密钥对待外包数据库进行加密后生成外包密文数据库，并将其发送至云服务供应商；2)已获授权的终端用户以SQL语句的形式向该数据库拥有者提交明文数据操作请求；3)该数据库拥有者将该数据操作请求的明文SQL语句转换为密文SQL语句集合发送至该云服务供应商；4)该云服务供应商在该外包密文数据库上直接执行该密文SQL语句；若为查询请求，则将得到的密文查询结果返回至该数据库拥有者；5)该数据库拥有者接收并解密该密文查询结果，向该终端用户返回明文记录。本发明保障了外包关系型数据库的数据机密性和有效利用。

说明书

技术领域

本发明涉及一种支持密文数据操作的关系型数据库安全外包数据处理方法，属云计算安全和数据库安全领域。

背景技术

目前，将私有的关系型数据库外包至云服务供应商，可以为商业团体以及个人用户带来巨大的便捷和收益，然而与此同时，外包数据库的安全和隐私问题日益严峻。云计算用户的敏感信息(例如金融交易记录、个人医疗档案等)正面临着不同程度的滥用和泄露。

公有云环境通常使用云端驱动的数据库加密技术抵御外部攻击者的恶意入侵，但是依然难以阻止不可信云服务供应商的内部攻击。因此，为避免云端加密可能会带来的隐私泄露的问题，云数据库加密应完全由数据库拥有者实施，从而真正地实现“加密后外包与查询后解密”的服务模式。

客户端加密主要面临两项难题：其一，选用何种加密算法对关系型数据库进行加密；其二，如何对加密后的密文关系型数据库执行数据操作。相关的研究已经取得了一系列重要的成果，包括全同态加密技术、部分同态加密技术等。更多的工作则围绕密文域等值查询、范围查询、聚合查询以及模糊查询中的一种或者多种而展开，然而其所支持的数据操作种类十分有限。某些综合的密文数据库查询方案能够支持部分基于SQL的查询操作，但是存在以下四点不足：

(1)不同类型的SQL语句需调用不同的加密技术以完成解释，导致数据库服务性能降低；

(2)云服务供应商无法直接执行SQL语句，云服务模式难以彻底摆脱对可信代理的依赖；

(3)云服务供应商执行数据操作前需获知解密密钥，尚未完全克服云端加密的安全风险；

(4)终端用户的数据库访问模式以及云数据库的关系结构被迫发生变化。

发明内容

针对现有技术中存在的问题，本发明的目的在于提供一种支持密文数据操作的关系型数据库安全外包数据处理方法。这种方法保护了关系型数据库在外包过程中的数据机密性及有效数据利用。所采用的客户端加密技术从根本上解决了云端加密的安全问题。图1是本发明的模块设计与总体架构。

本发明解决其技术问题所用的技术方案是：一种支持密文数据操作的关系型数据库安全外包数据处理方法(包括查询请求、插入请求、更新请求和删除请求)。该方法作用于终端用户、数据库拥有者和云服务供应商三者之间。关系型数据库在外包前由数据库拥有者负责加密，然后由云服务供应商在外包密文数据库上直接执行基于SQL的全类型数据操作，返回的查询结果则由数据库拥有者代替终端用户进行解密。具体地，本发明的方法流程为：

1.数据库拥有者将关系型数据库安全外包至云服务供应商：

(1)数据库拥有者生成私有密钥；

(2)数据库拥有者经密码模块对待外包数据库进行加密后生成外包密文数据库，并发送至云服务供应商；

(3)云服务供应商接收并原地存储该外包密文数据库；

(4)数据库拥有者在云服务供应商处创建用户自定义函数。

2.终端用户请求对关系型数据库进行隐私保护的数据操作：

(1)终端用户登录数据库系统，并向数据库拥有者提交明文SQL语句；

(2)数据库拥有者依据访问控制策略，判断查询请求是否已得到授权，如若非法访问，则拒绝操作；

(3)数据库拥有者经转换模块将明文SQL语句转换为密文SQL语句集合，发送至云服务供应商；

(4)云服务供应商调用用户自定义函数，在密文数据库中执行密文SQL语句，并将密文查询结果返回至数据库拥有者；

(5)数据库拥有者接收并解密查询结果集，向终端用户返回明文记录。

本发明的安全外包数据处理方法包括以下的五大模块：

(1)密码模块(OPEA算法)，用于加密或解密外包数据库。OPEA算法的加密函数具有保序性和可加性，能够最大限度地保留数据的可操作性。将OPEA算法密文域划分为多个按照先后顺序排列的密文分区，图2是该密码模块的映射结构，第i个密文分区的上下边界被分别定义为U_i和L_i。具体来看，图中所采用的一对多的映射结构将单一的明文值映射为某个密文分区内的多个密文值，用于构造OPEA算法的加密函数，从而改善密码模块的安全性以抵御惟密文攻击、统计攻击以及弱选择明文攻击。

(2)转换模块(SQL-Translator解释器)，用于转换待请求的明文SQL语句，同时确保经转换后得到的密文SQL语句可以在密文数据库中正常执行。图3是该转换模块的处理流程。

(3)用户自定义函数，部署在云服务供应商，主要用于云端的等值比较、聚合比较、和值计算和字符串分割等操作。

(4)加密规则，整型数据直接使用OPEA算法进行加密；加密浮点型数据时，按明文空间的最小精度来划分密文空间；字符型数据按终端用户选定的最小匹配单元转为整型后依次加密、填充并拼接。具体到外包关系型数据库而言，明文空间就是数据库中全部数据组成的有限集合。

(5)访问控制，选用不同的密钥加密具有不同保密级别的数据表或数据字段；已取得合法访问授权的终端用户可以通过共享用户口令登录数据库系统；数据库拥有者依据目前已登录用户的数据访问权限获取相应的加解密密钥。

本发明的有益效果是：

(1)本发明解决了客户端加密的两项主要难题，保障了外包关系型数据库的数据机密性和有效利用。

(2)本发明的总体架构适用于Microsoft Windows Azure SQL Database等未经修改的商业化云数据库平台。

(3)本发明仅需单次加密数据库，故存储开销更低，且数据访问模式与云数据库关系结构得以保留。

(4)本发明密码模块的OPEA算法能够抵御惟密文攻击、统计攻击以及弱选择明文攻击。其简化边界生成子算法、加密子算法和解密子算法的平均时间复杂度分别达到O(T)，O(1)和O(log T)，T是明文域的最大值，基本优于主流的对称密码算法。此外，OPEA算法的比较操作用时和网络通信开销忽略不计。密文域的噪声增长问题可通过调整密钥在常量级时间内得到有效控制。

(5)本发明转换模块支持目前最多种类的SQL数据操作，涵盖等值查询、范围查询、聚合查询、模糊查询、插入、更新、删除等数据操作语句。SQL-Translator解释器的转换用时在微秒量级以内，并满足任意类型和长度的数据转换需求。

(6)本发明直接执行密文查询而无需解密外包数据，查询结果准确，无误判，无漏判。相同查询精度下，客户端后处理开销较低，总体查询效率较高。

附图说明

图1为系统总体架构图。给出了本发明的模块设计、数据流向和参与者的作用范围。

图2为密码模块映射结构图。给出了OPEA算法的分区、间隔的划分方法以及明文域至密文域的映射关系。

图3为转换模块处理流程图。给出了SQL-Translator解释器的工作流程，包含核心转换模块和子转换模块。

图4为待外包数据库示例；

图5为外包密文数据库示例；

图6为密文查询结果示例；

图7为解密后的明文查询结果示例。

具体实施方式

下面结合附图对本发明作进一步说明。

图1是系统总体架构图，主要涉及密码模块、转换模块和用户自定义函数三大核心服务模块。具体方法包括下列步骤：

1.图2是密码模块映射结构图。密码模块的实现方法包括：

(1)设计并实现具有可加性的保序加密算法OPEA，离散密文域由顺序密文分区构成，其加密函数E:X→Y满足下述两个条件(X和Y分别是OPEA的明文与密文空间；具体到外包数据库应用，明文空间是指明文数据库中全部数据组成的集合，密文空间是指密文数据库中全部数据组成的集合)：

a)b∈X，a<b当且仅当E(a)<E(b)；

b)b,c∈X，若a+b<c，则有E(a)+E(b)<E(c)。

该算法由三个子算法构成：

a)边界生成子算法BoundaryGen，输入随机的非负整数集合R＝{R_i}以及随机正整数σ>max_1≤i≤T{R_i}-R₁作为密钥，根据密钥计算并输出密文域的密文分区下边界集L＝{L_i}＝{L[i]}(1≤i≤T)和上边界集U＝{U_i}＝{U[i]}(1≤i≤T)。其中，R_i是随机数集合中第i个元素，L_i和L[i]是第i个密文分区的下边界，U_i和U[i]则是第i个密文分区的上边界。子算法首先设定首个密文分区[L₁,U₁]，有L[1]＝σ且U[1]＝L[1]+R₁，随后迭代地划定后续密文分区的上下边界值，要求满足L[t]＝max_1≤i<t{U[i]+U[t-i]}且U[t]＝L[t]+R_t(2≤t≤T)。这里T是明文域的最大值，即明文数据库中全部数据的最大可能取值。

b)加密子算法Enc，输入边界集和正整数明文m，输出集合{L[m],L[m]+1,…,U[m]}内的随机整数作为密文c＝E(m)。加密子算法在加密明文值m时，根据密文分区的边界集L和U，加密函数E(·)将会从集合{L[m],L[m]+1,…,U[m]}中选择并返回一个随机数作为密文值c。

c)解密子算法Dec，输入边界集和密文c，借助折半查找算法输出密文c所属密文分区的编号作为明文值。

(2)简化OPEA算法的边界生成子算法，令密钥R_i(1≤i≤T)以非降序排列，得到线性边界函数：

(3)扩展OPEA算法以判定密文关系E’(a)+E’(b)>E’(c)，其中E’:X→Y’是扩展算法的加密函数。

a)扩展的边界生成子算法BoundaryGen’，要求密钥σ>3·max_1≤i≤T{R_i}，根据密钥计算并输出密文分区的扩展上边界集U’＝{U’[i]}(1≤i≤T)以及扩展下边界集L’＝{L’[i]}(1≤i≤T)。扩展子算法划定首个密文分区U’[1]＝σ且L’[1]＝U’[1]-R₁，后续密文分区应满足上边界U’[t]＝min_1≤i<t{L’[i]+L’[t-i]}且下边界L’[t]＝U’[t]-R_t(R_t<U’[t]-U’[t-1],2≤t≤T)，其线性边界函数为：

b)扩展的加密子算法和扩展的解密子算法与Enc和Dec类似。

(4)数据库拥有者使用OPEA算法对全部数据项进行加密，使用抗碰撞哈希函数或者对称密码技术对数据表名、列名等进行加密。

2.用户自定义函数的实现方法包括：

(1)数据库拥有者依据密钥以及查询请求中的待比较明文选取随机整数x∈[max{R₁,R₂},σ+R₁)，并发送至云服务供应商，其中R₁＝U[value₁]-L[value₁]和R₂＝U[value₂]-L[value₂]分别是待比较明文值value₁和value₂所对应的密文分区长度。

(2)设计并实现等值比较函数EqualityCom(x,E(value₁),E(value₂))，判定步骤为：

a)若E(value₁)和E(value₂)的距离不大于x，则明文值相等，函数输出0，否则继续执行步骤b)；

b)若E(value₁)大于E(value₂)，则value₁大于value₂，函数输出1；而若E(value₁)小于E(value₂)，则value₂大于value₁，函数输出-1。

(3)设计出聚合比较函数SumEqualityComL[value],U’[value])，是某数据库字段的数据项集合，SUM是求和函数，明文value与查询条件中的某个常量数值相对应，L[value]和U’[value]分别是value对应的密文分区下边界和扩展上边界。这里要求且R以非降序排列，判定步骤为：

a)若不大于L[value]且不小于U’[value]，则与value相等，函数输出0，否则继续执行步骤b)；

b)若大于U’[value]，则大于value，函数输出1；而若小于L[value]，则value大于函数输出-1。

(4)借助用户自定义函数SumEqualityCom，在数据库拥有者与云服务供应商之间部署安全和值计算协议。假设Att是某数据库字段的数据项集合，协议步骤为：

a)云服务供应商计算SUM(E(Att))和SUM(E’(Att))，并将密文累加结果发送至数据库拥有者；

b)数据库拥有者解密得到d＝Dec(SUM(E(Att)),L)和d’＝Dec(SUM(E’(Att)),U’)；

c)若d与d’相等，则数据库拥有者获知SUM(Att)＝d，并将E(SUM(Att))＝SUM(E(Att))返回云服务供应商。协议结束。

d)否则，数据库拥有者将会继续尝试寻找能够使得SumEqualityCom(SUM(E(Att)),SUM(E’(Att)),L[d+i],U’[d+i])＝0成立的整数i(0≤i≤d’-d)，从而获知SUM(Att)＝d+i，并将E(d+i)返回云服务供应商。协议结束。

(5)设计并实现字符串分割函数Split(str,delimiter)，str是待分割的LIKE运算符的密文搜索模式串，delimiter是分隔符，分割后的结果采用Table类型存储并返回。

3.图3是转换模块处理流程图。转换模块的实现方法包括：

(1)针对经OPEA算法加密的外包数据库，设计并实现SQL-Translator解释器，采用标准Transact-SQL数据操作语句作为输入。这里假设tbl是明文库某数据表名，Att、Att₁、Att₂是明文库某字段的数据项集合，val、val₁、val₂是常量数值，*^C是密文域对应的数据库对象。

(2)转换明文数据操作语句中的数据库实体，转换规则为：

a)数据表名、列名使用抗碰撞哈希函数或对称加密技术进行匿名化转换；

b)常量值使用OPEA算法进行转换。

(3)划分转换后的数据操作语句为最小转换单元，其中包含完整谓词表达式或子句结构。

(4)依次为最小转换单元调用相应的子转换模块。其中，子转换模块i与最小转换单元i对应，设有该最小转换单元i的转换规则，将其转换为对应的密文SQL子句。针对查询、插入、更新、删除四类数据操作语句，表1详述了其最小转换单元的转换规则。

表1为最小转换单元的转换规则

表1中各转换规则具体描述如下：

■对于查询操作语句：形如SELECT<Att₁,Att₂,…>FROM<tbl>的查询操作语句直接转换为

SELECT<Att₁^C,Att₂^C,…>FROM<tbl^C>

其余子句的转换规则如下，其中规定整数x∈[max_1≤i≤T{R_i},σ+R₁)：

WHERE子句

形如Att₁＝Att₂的比较运算符表达式直接转换为EqualityCom(x,Att₁^C,Att₂^C)＝0。

形如Att₁>Att₂的比较运算符表达式直接转换为EqualityCom(x,Att₁^C,Att₂^C)>0。

形如Att₁<Att₂的比较运算符表达式直接转换为EqualityCom(x,Att₁^C,Att₂^C)<0。

同理，比较运算符<>，！＝，！>，<＝，！<，>＝的转换规则可通过组合上述规则而得到。

形如Att BETWEEN>1>2的BETWEEN运算符表达式直接转换为

EqualityCom(x,Att^C,Att₁^C)>＝0∧EqualityCom(x,Att^C,Att₂^C)<＝0

形如Att NOT BETWEEN Att ₁AND>2的NOT>

EqualityCom(x,Att^C,Att₁^C)<0∨EqualityCom(x,Att^C,Att₂^C)>0

形如Att IN(Att₁,Att₂,…)的IN运算符表达式直接转换为

EqualityCom(x,Att^C,Att₁^C)＝0∨EqualityCom(x,Att^C,Att₂^C)＝0∨…

形如Att NOT IN(Att₁,Att₂,…)的NOT>

EqualityCom(x,Att^C,Att₁^C)！＝0∧EqualityCom(x,Att^C,Att₂^C)！＝0∧…

形如Att IS NULL的IS运算符表达式直接转换为

EqualityCom(x,Att^C,NULL^C)＝0

形如Att IS NOT NULL的IS NOT运算符表达式直接转换为

EqualityCom(x,Att^C,NULL^C)！＝0

对于形如Att[NOT]LIKE pat[ESCAPE esch]的LIKE运算符，逐步采用如下的转换方式：为Att增加临时列Att_Match；根据转义符esch转义通配符并以OPEA算法加密普通字符；声明外层游标匹配数据项长度；以Split函数将搜索模式串pat分割为3部分，并分别生成起始、中间和结束部分的匹配条件，使用AND或OR拼接各个匹配条件；声明内层游标匹配当前数据项的密文字符串；更新Att_Match列以及查询条件。LIKE运算符的转换结果由上述转换步骤所需的全部SQL语句构成。

对于形如s₁WHERE>2)的子查询语句，其中s₁和s₂是SELECT语句，逐步采用如下的转换方式：转换内层查询s₂，其查询结果存入临时表#INTER_TABLE2；将外层查询转换为s₁WHERE>

对于查询条件con₁和con₂而言，有以下转换规则：

形如con₁>2的组合查询条件直接转换为con₁^C∧con₂^C。

形如con₁>2的组合查询条件直接转换为con₁^C∨con₂^C。

ORDER>

形如ORDER BY>1,Att₂,…[ASC|DESC]的ORDER>

ORDER BY>1^C,Att₂^C,…[ASC|DESC]

在密文SQL语句执行过程中，云服务供应商首先以EqualityCom函数判定出Att₁^C中属性值相同的记录，然后再按照Att₂^C进行排序。

GROUP>

对于形如GROUP BY Att的GROUP BY子句，逐步采用如下的方式转换：对Att列进行自连接查询，满足查询条件的结果存入临时表#TEM；转换为临时表内查询GROUP BY Att^C。GROUP>

HAVING子句

形如MIN(Att)的聚合函数直接转换为MIN(Att^C)。

形如MAX(Att)的聚合函数直接转换为MAX(Att^C)。

形如COUNT(Att)的聚合函数直接转换为COUNT(Att^C)。

对于形如SUM(Att)的聚合函数，则转换为云服务供应商与数据库拥有者之间的安全和值计算协议，借助该协议最终计算得到E(SUM(Att))。

形如AVG(Att)的聚合函数直接转换为E(SUM(Att))/COUNT(Att^C)。

■对于插入操作语句：形如INSERT INTO<tbl>(<Att₁,Att₂,…>)VALUES(val₁,val₂,…)的插入操作语句直接转换为

INSERT INTO<tbl^C>(<Att₁^C,Att₂^C,…>)VALUES(E(val₁),E(val₂),…)

同理，对于插入操作语句中包含的子查询语句，其转换规则与查询操作语句相同。

■对于更新操作语句：形如UPDATE<tbl>SET<Att>＝val的更新操作语句直接转换为

UPDATE<tbl^C>SET<Att^C>＝E(val)

同理，对于更新操作语句中由FROM子句和WHERE子句指定的更新条件，其转换规则与查询操作语句的查询条件相同。

■对于删除操作语句：形如DELETE FROM<tbl>的删除操作语句直接转换为

DELETE FROM<tbl^C>

同理，对于删除操作语句中由WHERE子句指定的删除条件，其转换规则与查询操作语句中的查询条件相同。

(5)对转换得到的密文SQL子句进行拼接和排列，得到完整的密文SQL语句，并使其保留相同语义。例如对于下述明文查询语句：

SELECT>1 FROM tbl WHERE>1＝Att₂ ORDER BY>1

GROUP BY>1HAVING>2)>val

经SQL-Translator转换后拼接排列得到下述密文查询语句：

SELECT>1^C>C>1^C,Att₂^C)＝0ORDER>1^CGROUP BY>1^C>2)),SUM(E’(Att₂)),L[val],U’[val])>0

(6)输出可以直接在外包密文数据库上执行的密文SQL语句。

下面给出本发明的一个具体实施例。

1.假设数据库拥有者的明文数据库由一个名为EXAMPLE的数据表组成。表中包含两个明文字段(或称明文属性列)，列名分别为C_CUSTKEY和C_NATIONKEY。表中共有5条明文记录(即5行数据)，如图4所示。

2.数据库拥有者借助密码模块对该明文数据库进行加密处理，并将加密后得到的密文数据库发送至云服务供应商。明文数据库中名为EXAMPLE的明文数据表对应密文数据库中名为[8e3b72508e05135569ace4ed9b96d137]的密文数据表，表中共5条密文记录，如图5所示；其中，d0d0a493e28066e951fa7a980e81cb05和4eed023b3ef2a4fd3b3fae34f828ba5e分别是使用抗碰撞哈希函数对明文列名C_CUSTKEY和C_NATIONKEY进行加密处理后得到的密文列名。第一行的密文数据项121和4423则分别是使用OPEA算法对明文数据库第一行的明文数据项1和15逐一加密后得到的密文值。

3.假设终端用户提出下述查询操作请求(即明文SQL语句)：

SELECT*FROM EXAMPLE WHERE C_NATIONKEY>10

终端用户请求从EXAMPLE表中查询出C_NATIONKEY值大于10的数据记录。其中C_NATIONKEY>10是查询条件，查询结果应返回两条明文记录(1,15)和(2,13)。

4.数据库拥有者借助转换模块对该明文SQL语句进行转换处理，得到密文SQL语句：

SELECT*FROM[8e3b72508e05135569ace4ed9b96d137]

WHERE EqualityCom(100,[4eed023b3ef2a4fd3b3fae34f828ba5e],2891)>0

其中EqualityCom(100,[4eed023b3ef2a4fd3b3fae34f828ba5e],2891)是用户自定义函数。EXAMPLE^C＝[8e3b72508e05135569ace4ed9b96d137]，x＝100，C_NATIONKEY^C＝[4eed023b3ef2a4fd3b3fae34f828ba5e]，E(10)＝2891。

5.数据库拥有者将密文SQL语句发送至云服务供应商。由云服务供应商负责在密文数据库中执行查询，执行过程中需要调用用户自定义函数EqualityCom。查询结束后得到符合查询条件的密文查询结果，如图6所示。

6.云服务供应商将该密文查询结果返回给数据库拥有者。数据库拥有者借助密码模块对其进行解密处理，最终得到明文查询结果，如图7所示：

7.数据库拥有者将该明文查询结果返回给终端用户。外包数据库查询过程结束。