支持全操作的公共可验证外包数据库方案

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-03-23

王强, 玄鹏开, 王红伟, 周福才
东北大学软件学院, 辽宁沈阳 110169
收稿日期：2017-04-24
基金项目：中央高校基本科研业务费专项资金资助项目(N151704002)；国家自然科学基金资助项目(61772127, 61472184)。
作者简介：王强(1991-), 男, 辽宁桓仁人, 东北大学博士研究生;
周福才(1964-), 男, 辽宁沈阳人, 东北大学教授, 博士生导师。

摘要：针对当前外包数据库完整性研究方案存在的时空开销大、查询和更新效率低、无法同时支持多种SQL查询结果的完整性验证等问题, 提出一个支持全操作的公共可验证外包数据库模型, 并给出该模型的形式化定义和安全性定义.在模型的基础上利用双线性映射累加器和认证跳表实现了包含三方实体且支持全操作的公共可验证外包数据库方案, 给出了方案中各算法的具体描述及实体间的交互过程.最后分别对方案的安全性和效率进行分析, 结果表明, 该方案具有不可伪造性, 并具有较高的效率.
关键词：完整性验证公共可验证外包数据库全操作双线性映射累加器
A Publicly Verifiable Outsourced Database Scheme with Full Operations
WANG Qiang, XUAN Peng-kai, WANG Hong-wei, ZHOU Fu-cai
School of Software, Northeastern University, Shenyang 110169, China
Corresponding author: ZHOU Fu-cai, E-mail: fczhou@mail.neu.edu.cn
Abstract: Aiming at the existing shortcomings of outsourced database schemes including heavy temporal and spatial cost, low efficiency for query and update, and lack of the support for the complete verification of multiple SQL query results, this paper proposes a publicly verifiable outsourced database model supporting full operations. The formal definition and security definition are presented. On the basis of the model, a publicly verifiable outsourced database scheme, composed of three entities, is constructed using bilinear mapping accumulator and authenticated skip list. Also, the implement and the communication are described in detail. Finally, the security and efficiency are analyzed, respectively, which shows that the proposed scheme is with unforgeability and high efficiency.
Key words: integrity verificationpublic verificationoutsourced databasefull operationbilinear-map accumulator
近年来, 数据库外包作为云计算一种新兴的应用模式, 因其成本低、效果好、操作易、灵活性高等特点, 已成为用户或企业数据库外包的趋势.然而, 取消数据中心, 将数据库外包至第三方数据库服务提供商进行管理和维护, 用户将面临着服务提供商恶意篡改数据库内容、伪造查询结果和遭受外部攻击等风险, 难以保证查询结果的完整性^[1], 因此实现支持查询结果完整性验证的数据库外包方案对云计算的发展具有重大意义.
目前, 针对外包数据库查询结果完整性验证问题已展开大量研究, 主要分为三类:基于数字签名、基于认证数据结构和基于可验证计算.基于数字签名的方法^[2-3]存在验证代价较高和更新代价高的问题.基于认证数据结构的方法是对基于数字签名方法的改进, 通常包含两类:基于Merkle哈希树^[4-5]和基于累加器^[6].基于Merkle哈希树虽不需要对每一元组进行签名, 但由于叶子节点是排序好的元组的哈希值, 任何一次更新都可能破坏已有的认证数据结构, 更新代价较高.验证查询结果正确性的证据随元组的数量呈对数级增长, 只支持单维范围和元素隶属关系的查询.另一种基于累加器的方法, 只支持集合交集、并集、差集及元素隶属关系的查询, 不支持求和、计数、平均值、范围、最大值、最小值、连接和嵌套查询.基于可验证计算的方法分为两类:基于电路^[7-8]和基于RAM^[8-9].两者均是将外包数据库编译到程序中, 在编译好的程序中输入查询语句, 返回与之对应的结果.这两种方法的计算代价较高, 难以应用于实际.基于电路的方法效率比基于RAM的更低, 程序中电路的规模至少与数据库本身一样大, 且不支持更新.而基于RAM模型的系统虽然支持全部查询操作, 但是编码的难度较高.
综上所述, 已有的外包数据库完整性验证方案存在时空开销大、查询和更新效率低和不支持全操作(支持多种SQL查询)等不足, 难以适于实际应用.针对此问题, 本文提出一个支持全操作的公共可验证外包数据库模型(publicly verifiable outsourced database with full operations, PVODB-FO), 并给出了该模型的形式化定义和安全性定义.在模型的基础上, 借助双线性映射累加器和认证跳表, 本文方案不仅可以同时支持连接、多维范围、函数和嵌套等查询操作而且可高效更新.
1 双线性q-SDH假设令λ为安全参数, G和G_T为p阶循环群, g为G的生成元, e:G×G→G_T为双线性映射, 随机选取s∈Z_p^*, 并给定(q+1)个元素g, g^s, g^s², …, g^{s^q}, 如果不存在一个概率多项式时间算法能以不可忽略的概率计算出(a, e(g, g)^1/(a+s)), 其中a∈Z_p^*/{-s}, 则称双线性q-SDH假设是困难的.
2 PVODB-FO模型PVODB-FO主要包含三方实体:数据拥有者、客户和云服务器.系统架构如图 1所示:数据拥有者首先生成公私钥对, 并为外包数据库计算认证数据结构和摘要, 然后将数据库和认证数据结构外包至云服务器, 最后将公钥和摘要发送给客户.客户向云服务器发送SQL查询请求, 当云服务器接收到客户请求后, 返回对应的查询结果及证据.最后客户验证查询结果的完整性.
图 1(Fig. 1)

图 1 系统总体架构Fig.1 System architecture

2.1 模型定义PVODB-FO由6个概率多项式时间算法组成, PVODB-FO={KeyGen, Setup, Query, Verify, UpdateO, UpdateS}具体描述如下:
1) (pk, sk)←KeyGen(1^λ):数据拥有者输入安全参数λ, 算法输出公私钥对(pk, sk).
2) (D_ADS, δ)←Setup(D, sk):数据拥有者输入外包数据库D和私钥sk, 算法输出认证数据结构D_ADS和对应的摘要δ.
3) (R, π)←Query(Q, D, D_ADS):云服务器输入查询语句Q、外包数据库D和认证数据结构D_ADS, 算法输出查询结果R和证据π.
4) b←Verify(pk, δ, R, π):客户输入查询公钥pk、结果R、摘要δ和证据π, 算法输出比特b, 如果b=1表示验证成功, 否则表示验证失败.
5) (δ′)←UpdateO(u, δ, sk):数据拥有者输入更新语句u、摘要δ和私钥sk, 算法输出更新后的摘要δ′.
6) (D′, D_ADS′)←UpdateS(u, D, D_ADS):云服务器输入更新语句u、外包数据库D和认证数据结构D_ADS, 算法输出更新后的数据库D′和认证数据结构D′_ADS.
2.2 安全性定义给定安全参数λ和外包数据库D, 敌手A伪造的查询结果及证据始终不能通过验证.下面通过安全性实验给出该方案安全性的形式化定义, 安全性实验步骤如下.
初始化阶段:
1) 挑战者C执行算法KeyGen, 生成公私钥对, 将公钥pk发送给敌手A, 私钥sk保留.
2) 挑战者C执行算法Setup, 输出认证数据结构D_ADS和摘要δ, 并将D_ADS和δ发送给A.
3) 敌手A向C进行多项式poly (λ)次查询或更新操作:①查询——A向C发送查询请求Q, C执行算法Query并将(R, π)返回至A; ②更新——A向C发送更新请求u, C执行算法UpdateO和UpdateS, 最后将更新后的δ′, D′和D_ADS′发送至A.
挑战阶段:当敌手A决定结束步骤3), 选择一个目标查询请求q^*, A伪造对应的查询结果R^*和证据, 且算法Verify(pk, δ, R^*, π^*)输出1.
如果对于任意具有概率多项式时间计算能力的敌手A, 都不能以不可忽略的概率negl (λ)赢得上述安全性实验, 则称PVODB-FO是安全的.
3 PVODB-FO方案3.1 密钥生成算法KeyGen首先输入安全参数λ, 调用双线性映射算法生成(p, g, G, G_T, e), 其中p是λ位的素数, g为G的生成元, G和G_T为两个p阶循环群, 双线性映射e:G×G→G_T.随机选择s∈Z_p^*, 计算(g^s, g^s², …, g^{s^q}), 其中q=poly(λ).选取对称加密方案ε的密钥sk_ε.
最终输出公钥pk=(g^s, g^s², …, g^{s^q}), 私钥sk=(s, sk_ε).
3.2 系统初始化对外包数据库D中每个表T, 按如下方式构建认证数据结构D_ADS和摘要δ:不失一般性, 假定T有n+1行, 对表中任意2列i, j进行组合得到键值对集合S_i×j^T={x₀, …, x_n}, 其中x_k=(x_ki, x_kj), x_ki为key, x_kj为value.构建认证跳表(authenticated skip list, ASL)ASL_i×j^T如图 2所示, 其存储了集合S_i×j^T的元素, S₀按x_ki递增的方式存储集合S_i×j^T中所有元素, 以及-∞和+∞两个哨兵节点.最高层S_l中的-∞节点为跳表搜索的起始节点.S_i中的每个节点v存储v.elem, v.down和v.right.v.elem表示该节点内存储的元素, v.down表示下层S_i-1中对应的节点, v.right表示v右侧直接相连的节点.内部节点u的子树T_u对应的叶子节点集合N, 满足∪T_u=N.内部节点u的key为子树T_u中叶子节点中最小的key, 节点u的value为

.ASL构建完毕, 输出其摘要δ_i×j^T.最后使用可交换哈希函数H对表T每行计算哈希值H(x_k1, …, x_km), 其中m表示表T列的数量.
图 2(Fig. 2)

图 2 认证跳表结构图Fig.2 Structure of authenticated skip list

最后输出认证数据结构D_ADS包含全部ASL_i×j^T, 摘要δ包含全部δ_i×j^T和哈希值H(x_k1, …, x_km).
ε选择AES加密方案实现, 连接符右侧部分为叶子节点中value的累加值, 用于查询时生成证据, 左侧部分是对右侧指数部分的加密结果, 用于更新数据库, 因此只有拥有私钥sk_ε的数据拥有者才能更新.
3.3 查询与验证(R, π)←Query(q, D, D_ADS)以查询语句q∈Q、数据集D和认证数据结构D_ADS为输入, 输出查询结果R和证据π.b←Verify(pk, δ, R, π)输入查询公钥pk、结果R、摘要δ和证据π, 输出一个比特b：b=1表示验证通过, b=0表示验证未通过.不同的SQL查询, 生成的证据也不同.
3.3.1 常规查询与验证查找查询(Search):x为待查找元素, 从ASL根节点搜索, 令v表示当前节点, 比较x与v.elem大小.若x＞v.elem, 向右搜索, 若v为右侧哨兵节点, 搜索结束, 查找失败; 否则令v=v.right.若x≤v.elem, 向下搜索, 若v.down=null且x=v.elem, 则找到元素x; 若v.down≠null且x≤v.elem, 令x=v.down; 若v.down=null且x≠v.elem, 查找失败.
范围查询(RangeCover):给定x_L, x_R(x_L≤x_R), 查询x_L~x_R范围内的所有元素x.将x_L, x_R视为待查找元素, 分别调用Search查询, 找到两元素，进而得到x_L, x_R所在范围的查询结果N.
上述两种查询操作, 通过比对摘要值就可验证查询结果的正确性.
3.3.2 连接查询与验证查询:连接查询q涉及表T的第i列和表T′的第j列, 令C_i和C_j表示每一列中元素的集合.使用k_L=-∞和k_R=∞, 在S_i×i^T上执行范围查询, 返回S_i×i^T对应的ASL_i×i^T的根节点值, 根节点值中包含acc(C_i).然后, 在S_j×j^T′上执行相同操作得到acc(C_j).利用可验证集合交集运算得到C_i和C_j的交集C^*.最后云服务器返回交集C^*中元素所在的行的数据作为查询结果, 将该行的哈希值和交集计算的证据作为查询的证据.
验证:客户利用集合交集的证据来验证集合交集计算的正确性.若验证失败, 终止并拒绝查询结果; 否则验证元素哈希值的正确性, 若验证失败, 终止并拒绝查询结果, 否则接受查询结果.
3.3.3 多维范围查询与验证查询:多维范围查询结果可通过2维范围查询交集得到.不失一般性, 以2维范围查询为例, 假定所查询范围分别是[w^-, w⁺]和[z^-, z⁺], 在S_w×1^T对应的ASL_w×1^T上使用边界值w^-和w⁺作为输入, 调用RangeCover查询, 输出查询结果R_w.同样, 将边界值z^-和z⁺作为输入, 在ASL_z×1^T上执行RangeCover查询, 输出查询结果R_z.利用可验证集合交集运算对集合R_w和R_z做交集, 进而得到2维范围查询的结果R^*.最后云服务器返回R^*中元素作为查询结果, 哈希值和交集计算的证据作为查询的证据.
验证:用集合交集的证据来验证集合交集计算的正确性, 若验证失败, 终止并拒绝查询结果; 否则验证元素哈希值的正确性, 若验证失败, 终止并拒绝查询结果, 否则接受查询结果.
3.3.4 函数型查询与验证为满足统计需求, 巧妙地设计双线性映射累加器, 实现了集合求和运算查询结果的完整性验证, 并在此基础上实现了计数和平局值查询.
假定求和查询所在列对应的集合S_j={x_j1, …, x_jn}, 集合中元素的累加值acc(S_j)=

.累加值指数部分对应的多项式为

, 其中

.集合S_j中元素的和

.求和运算的证据为w₁, w₂, 其中w₁=g^{s^n-1+…+a₂s+a₁}, w₂=g^{s^n-2+…+a₃s+a₂}.若e(g^s, w₁)=e(acc(S)/g^a₀, g), sum=a₁a₀^-1 mod p和e(g^s, w₂)=e(w₁/g^a₁, g)同时成立, 则接受求和计算结果.
求和查询过程如下.
查询:对表T的第j列进行求和查询, 云服务器利用多项式快速傅里叶变换算法求得a₀和a₁, 计算a₁a₀^-1 mod p即为求和结果sum.返回证据w₁和w₂.
验证:判断e(g^s, w₁)与e(acc(S)/g^a₀, g)是否相等, 若不相等, 则a₀系伪造, 终止并拒绝查询结果, 否则判断e(g^s, w₁)与e(acc(S)/g^a₀, g)是否相等, 若不相等, a₁系伪造, 终止并拒绝查询结果, 否则判断sum与a₁a₀^-1 mod p是否相等, 若不相等则拒绝查询结果, 否则接受查询结果sum.
计数查询过程如下.
查询:云服务器通过SQL计数查询可直接获得计数值R.构造证据时, 云服务器在表T中需要计数的第j列后增加1列j′, j′列中每行元素等于j列对应行元素加1, 返回第j列和j′列求和查询的证据作为计数查询的证据.
验证:首先验证求和查询sum(j)和sum(j′)的正确性, 再验证计数值count(j)是否等于sum(j′)-sum(j); 若相等则接受计数结果, 否则拒绝计数结果.
平均值查询过程如下.
查询:第j列平均值查询的结果可通过求和查询结果除以计数查询结果得到.返回的证据为求和查询的证据和计数查询的证据.
验证:首先验证求和查询与计数查询的正确性, 再验证平均值查询结果avg(j)是否等于sum(j)/count(j); 若相等则接受平均值结果, 否则拒绝平均值结果.
最大值与最小值查询过程如下.
查询:对第j列作最大值和最小值查询, 可直接通过SQL查询得到; 构建证据时, 返回在认证跳表ASL_j×j^T(key和value均由第j列元素构成)上对最大值和最小值做Search查询的证据.
验证:验证与Search查询的验证相同.
3.3.5 嵌套查询与验证查询:假定执行嵌套查询Q₁oQ₂, 云服务器相当于分别执行查询Q₁和Q₂, 然后对Q₁和Q₂查询结果进行可验证的集合交集或并集操作.云服务器返回的证据为中间结果的摘要和验证最终结果的证据; 因不需要返回中间结果的全部证据, 从而极大地减小了存储与验证的开销.
验证:首先验证中间结果的摘要值与对应结果的摘要值是否相等, 若不相等, 终止并拒绝查询结果, 否则验证结果的正确性.根据查询类型在上文中找到相应的验证方法, 若验证失败, 终止并拒绝查询结果, 否则接受查询结果.
3.4 更新更新过程由数据拥有者和云服务器交互实现, 更新操作包括插入、删除、修改数据库中的一行(或多行)数据.云服务器更新外包数据库对应的数据和认证跳表, 数据拥有者更新摘要值.插入时, 首先通过Search查询找到低于插入元素x=(key_x, value_x)且最接近key_x的位置, 记录下搜索路径.找到最底层的位置后, 新建节点, 连入底层跳表.随机生成元素的最高层, 由低到高在每一层新建节点, 通过搜索路径进行相应的连接操作.删除时, 从起始节点开始搜索删除节点x, 找到x前一个位置的节点v, 则v.right即为x所在位置, 记录搜索路径.沿路径向上依次删除含有元素value_x的节点.修改时, 可先通过删除、再插入来实现.更新数据后, 数据拥有者输出更新后的摘要δ′, 并从底层节点一直更新至根节点.每个节点的更新过程:使用私钥解密

得到

, 更新得到新的

, 计算更新后的累加器值

, 然后将

发送给云服务器.最终云服务器输出更新数据D′和ASL.
4 安全性分析和性能分析4.1 安全性分析由于认证跳表弥补了双线性映射累加器不能实现范围查询、最大值和最小值查询的不足, 并且认证跳表的安全性在已有方案^[8]中已得证明, 这里不在赘述.其他类型的查询都是基于求和查询的, 因此只要证明求和查询的安全性即可保证该方案的安全性.安全性证明如下:
如果存在一敌手A攻破了求和查询的安全性, 即伪造了一个结果及证据并通过了算法Verify的验证, 那么敌手A可构造一算法B, 以不可忽略的概率解决双线性q-SDH难题.证明过程如下.
算法B执行算法KeyGen生成公私钥对(pk, sk), 将pk发送给A, sk私密保存.A选定一个集合S, 算法B计算累加值acc(S)并公开, 敌手伪造求和的结果sum^*, 并且证据a₀^*, a₁^*, w₀^*, w₁^*通过验证, 那么一定满足a₀^*≠a₀或a₁^*≠a₁.
情形1:当a₀^*≠a₀时, 因为e(g^s, w₁^*)=e(acc(S)/g^{a₀^*}, g)且e(g^s, w₁)=e(acc(S)/g^a₀, g), 敌手A可计算出g^1/s=(w₁^*/(g^{s^n-1+…+ a₂s+a₁}))^{(a₀-a₀^*)^-1}, 这与双线性q-SDH难题相矛盾.
情形2:当a₀^*≠a₀且a₁^*≠a₁时, 因为e(g^s, w₁^*)=e(acc(S)/g^{a₀^*}, g), 可得w₁^*=g^{s^n-1}+…+a₂s+a₁.又因为e(g^s, w₂)=e(w₁/g^{a₁^*}, g), 敌手A可计算出g^1/s=(w₂^*/(g^{s^n-2+…+a₂}))^{(a₁-a₁^*)^-1}, 这与双线性q-SDH难题相矛盾.
4.2 性能分析从查询类型的丰富性和算法效率两方面, 将本文方案与其他方案进行了对比.
在查询类型丰富性方面, 将本文方案与基于RAM、基于电路和基于树或签名的方案进行对比.由表 1可以看出, 本方案和基于电路的方案支持的查询类型更加丰富.
表 1(Table 1)

表 1 方案对比Table 1 Comparison with prior works

方案	连接查询	多维查询	多维连接查询	函数查询	更新
基于树	×	×	×	×	×
基于签名	×	×	×	×	×
基于电路	√	√	√	√	×
基于RAM	√	√	√	√	√
本文方案	√	√	√	√	√
??注：×不支持，√支持.

表 1 方案对比 Table 1 Comparison with prior works

在算法效率方面, 从初始化、查询与验证、更新及认证跳表这4个方面对方案的性能进行了分析, 如表 2所示.其中, m_i表示表i的列数, n_i表示表i的行数, d为多维范围查询的维数, R为查询结果, n为认证跳表叶子节点数量, u表示更新的行数, O表示时间复杂度的上界.
表 2(Table 2)

表 2 性能分析Table 2 Performance analysis

认证跳表	查找	O(lbn)
	范围查询	O(lbn)
	插入	O(lbn)
	删除	O(lbn)
初始化	私钥大小	O(1)
	算法复杂性	O(∑_im_i²n_i)
	摘要大小	O(∑m_i²+∑n_i)
查询与验证	多维范围查询	证据大小	O(d·lbn)
	多维范围查询	验证时间	O(d·lbn+\|R\|)
	连接查询	证据大小	O(\|R\|)
	连接查询	验证时间	O(\|R\|)
	求和查询	证据大小	O(1)
	求和查询	验证时间	O(1)
	嵌套查询 (多维范维+求和)	证据大小	O(d)
	嵌套查询 (多维范维+求和)	验证时间	O(d+\|R\|)
更新操作		O(m_i²lbn)

表 2 性能分析 Table 2 Performance analysis

5 结论1) 提出一个支持全操作的公共可验证外包数据库模型, 并给出了模型的安全性定义.
2) 在模型基础上, 利用双线性映射累加器和认证跳表实现了一个不仅能同时支持多种SQL查询, 还支持数据动态更新的公共可验证外包数据库方案, 给出了方案中各算法的具体实现.
3) 证明了方案的安全性, 其安全性归约至双线性q-SDH问题, 并分析了方案中各算法的性能.
参考文献

[1]	Kellaris G, Kollios G, Nissim K, et al.Generic attacks on secure outsourced databases[C]// Proceedings of the Computer and Communications Security.[S.l.]: ACM, 2016: 1329-1340.http://dl.acm.org/ft_gateway.cfm?id=2978386&ftid=1805840&dwn=1&CFID=870554800&CFTOKEN=86292093
[2]	Song W, Wang B, Wang Q, et al. Tell me the truth:practically public authentication for outsourced databases with multi-user modification[J].Information Sciences, 2017, 387: 221–237.DOI:10.1016/j.ins.2016.07.031
[3]	Cheng W, Pang H H, Tan K L.Authenticating multi-dimensional query results in data publishing[C]// IFIP Annual Conference on Data and Applications Security and Privacy.Berlin: Springer-Verlag, 2006: 60-73.http://dl.acm.org/citation.cfm?id=2090490
[4]	Niaz M S, Saake G.Merkle Hash Tree based techniques for data integrity of outsourced data[C/OL].[2017-01-23].https://pdfs.semanticscholar.org/5f8a/e87238e505aa03ea6130cdf74454d7347de9.pdf.
[5]	Miao M, Ma J, Huang X, et al. Efficient verifiable databases with insertion/deletion operations from delegating polynomial functions[J].IEEE Transactions on Information Forensics and Security, 2018, 13(2): 511–520.DOI:10.1109/TIFS.2017.2758746
[6]	Camenisch J, Kohlweiss M, Soriente C.An accumulator based on bilinear maps and efficient revocation for anonymous credentials[C]// Proceedings of the Public Key Cryptography.Irvine, 2009: 481-500.http://dl.acm.org/citation.cfm?id=1531989
[7]	Parno B, Howell J, Gentry C, et al.Pinocchio: nearly practical verifiable computation[C]// IEEE Symposium on Security & Privacy.New York: IEEE, 2013: 238-252.http://dl.acm.org/citation.cfm?id=2497621.2498115
[8]	Bensasson E, Chiesa A, Tromer E, et al.Succinct non-interactive zero knowledge for a von Neumann architecture[C]// Proceedings of the 23rd USENIX Security Symposium.San Diego, 2014: 781-796.http://dl.acm.org/citation.cfm?id=2671275
[9]	Bensasson E, Chiesa A, Genkin D, et al.SNARKs for C: verifying program executions succinctly and in zero knowledge[C]// Proceedings of the International Cryptology Conference.Washington DC, 2013: 90-108.https://link.springer.com/chapter/10.1007/978-3-642-40084-1_6