2018, Vol. 39
近年来, 数据库外包作为云计算一种新兴的应用模式, 因其成本低、效果好、操作易、灵活性高等特点, 已成为用户或企业数据库外包的趋势.然而, 取消数据中心, 将数据库外包至第三方数据库服务提供商进行管理和维护, 用户将面临着服务提供商恶意篡改数据库内容、伪造查询结果和遭受外部攻击等风险, 难以保证查询结果的完整性[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和GT为p阶循环群, g为G的生成元, e:G×G→GT为双线性映射, 随机选取s∈Zp*, 并给定(q+1)个元素g, gs, gs2, …, gsq, 如果不存在一个概率多项式时间算法能以不可忽略的概率计算出(a, e(g, g)1/(a+s)), 其中a∈Zp*/{-s}, 则称双线性q-SDH假设是困难的.
2 PVODB-FO模型PVODB-FO主要包含三方实体:数据拥有者、客户和云服务器.系统架构如图 1所示:数据拥有者首先生成公私钥对, 并为外包数据库计算认证数据结构和摘要, 然后将数据库和认证数据结构外包至云服务器, 最后将公钥和摘要发送给客户.客户向云服务器发送SQL查询请求, 当云服务器接收到客户请求后, 返回对应的查询结果及证据.最后客户验证查询结果的完整性.
|
图 1 系统总体架构 Fig.1 System architecture |
PVODB-FO由6个概率多项式时间算法组成, PVODB-FO={KeyGen, Setup, Query, Verify, UpdateO, UpdateS}具体描述如下:
1) (pk, sk)←KeyGen(1λ):数据拥有者输入安全参数λ, 算法输出公私钥对(pk, sk).
2) (DADS, δ)←Setup(D, sk):数据拥有者输入外包数据库D和私钥sk, 算法输出认证数据结构DADS和对应的摘要δ.
3) (R, π)←Query(Q, D, DADS):云服务器输入查询语句Q、外包数据库D和认证数据结构DADS, 算法输出查询结果R和证据π.
4) b←Verify(pk, δ, R, π):客户输入查询公钥pk、结果R、摘要δ和证据π, 算法输出比特b, 如果b=1表示验证成功, 否则表示验证失败.
5) (δ′)←UpdateO(u, δ, sk):数据拥有者输入更新语句u、摘要δ和私钥sk, 算法输出更新后的摘要δ′.
6) (D′, DADS′)←UpdateS(u, D, DADS):云服务器输入更新语句u、外包数据库D和认证数据结构DADS, 算法输出更新后的数据库D′和认证数据结构D′ADS.
2.2 安全性定义给定安全参数λ和外包数据库D, 敌手A伪造的查询结果及证据始终不能通过验证.下面通过安全性实验给出该方案安全性的形式化定义, 安全性实验步骤如下.
初始化阶段:
1) 挑战者C执行算法KeyGen, 生成公私钥对, 将公钥pk发送给敌手A, 私钥sk保留.
2) 挑战者C执行算法Setup, 输出认证数据结构DADS和摘要δ, 并将DADS和δ发送给A.
3) 敌手A向C进行多项式poly (λ)次查询或更新操作:①查询——A向C发送查询请求Q, C执行算法Query并将(R, π)返回至A; ②更新——A向C发送更新请求u, C执行算法UpdateO和UpdateS, 最后将更新后的δ′, D′和DADS′发送至A.
挑战阶段:当敌手A决定结束步骤3), 选择一个目标查询请求q*, A伪造对应的查询结果R*和证据, 且算法Verify(pk, δ, R*, π*)输出1.
如果对于任意具有概率多项式时间计算能力的敌手A, 都不能以不可忽略的概率negl (λ)赢得上述安全性实验, 则称PVODB-FO是安全的.
3 PVODB-FO方案 3.1 密钥生成算法KeyGen首先输入安全参数λ, 调用双线性映射算法生成(p, g, G, GT, e), 其中p是λ位的素数, g为G的生成元, G和GT为两个p阶循环群, 双线性映射e:G×G→GT.随机选择s∈Zp*, 计算(gs, gs2, …, gsq), 其中q=poly(λ).选取对称加密方案ε的密钥skε.
最终输出公钥pk=(gs, gs2, …, gsq), 私钥sk=(s, skε).
3.2 系统初始化对外包数据库D中每个表T, 按如下方式构建认证数据结构DADS和摘要δ:不失一般性, 假定T有n+1行, 对表中任意2列i, j进行组合得到键值对集合Si×jT={x0, …, xn}, 其中xk=(xki, xkj), xki为key, xkj为value.构建认证跳表(authenticated skip list, ASL)ASLi×jT如图 2所示, 其存储了集合Si×jT的元素, S0按xki递增的方式存储集合Si×jT中所有元素, 以及-∞和+∞两个哨兵节点.最高层Sl中的-∞节点为跳表搜索的起始节点.Si中的每个节点v存储v.elem, v.down和v.right.v.elem表示该节点内存储的元素, v.down表示下层Si-1中对应的节点, v.right表示v右侧直接相连的节点.内部节点u的子树Tu对应的叶子节点集合N, 满足∪Tu=N.内部节点u的key为子树Tu中叶子节点中最小的key, 节点u的value为
|
图 2 认证跳表结构图 Fig.2 Structure of authenticated skip list |
最后输出认证数据结构DADS包含全部ASLi×jT, 摘要δ包含全部δi×jT和哈希值H(xk1, …, xkm).
ε选择AES加密方案实现, 连接符右侧部分为叶子节点中value的累加值, 用于查询时生成证据, 左侧部分是对右侧指数部分的加密结果, 用于更新数据库, 因此只有拥有私钥skε的数据拥有者才能更新.
3.3 查询与验证(R, π)←Query(q, D, DADS)以查询语句q∈Q、数据集D和认证数据结构DADS为输入, 输出查询结果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):给定xL, xR(xL≤xR), 查询xL~xR范围内的所有元素x.将xL, xR视为待查找元素, 分别调用Search查询, 找到两元素，进而得到xL, xR所在范围的查询结果N.
上述两种查询操作, 通过比对摘要值就可验证查询结果的正确性.
3.3.2 连接查询与验证查询:连接查询q涉及表T的第i列和表T′的第j列, 令Ci和Cj表示每一列中元素的集合.使用kL=-∞和kR=∞, 在Si×iT上执行范围查询, 返回Si×iT对应的ASLi×iT的根节点值, 根节点值中包含acc(Ci).然后, 在Sj×jT′上执行相同操作得到acc(Cj).利用可验证集合交集运算得到Ci和Cj的交集C*.最后云服务器返回交集C*中元素所在的行的数据作为查询结果, 将该行的哈希值和交集计算的证据作为查询的证据.
验证:客户利用集合交集的证据来验证集合交集计算的正确性.若验证失败, 终止并拒绝查询结果; 否则验证元素哈希值的正确性, 若验证失败, 终止并拒绝查询结果, 否则接受查询结果.
3.3.3 多维范围查询与验证查询:多维范围查询结果可通过2维范围查询交集得到.不失一般性, 以2维范围查询为例, 假定所查询范围分别是[w-, w+]和[z-, z+], 在Sw×1T对应的ASLw×1T上使用边界值w-和w+作为输入, 调用RangeCover查询, 输出查询结果Rw.同样, 将边界值z-和z+作为输入, 在ASLz×1T上执行RangeCover查询, 输出查询结果Rz.利用可验证集合交集运算对集合Rw和Rz做交集, 进而得到2维范围查询的结果R*.最后云服务器返回R*中元素作为查询结果, 哈希值和交集计算的证据作为查询的证据.
验证:用集合交集的证据来验证集合交集计算的正确性, 若验证失败, 终止并拒绝查询结果; 否则验证元素哈希值的正确性, 若验证失败, 终止并拒绝查询结果, 否则接受查询结果.
3.3.4 函数型查询与验证为满足统计需求, 巧妙地设计双线性映射累加器, 实现了集合求和运算查询结果的完整性验证, 并在此基础上实现了计数和平局值查询.
假定求和查询所在列对应的集合Sj={xj1, …, xjn}, 集合中元素的累加值acc(Sj)=
求和查询过程如下.
查询:对表T的第j列进行求和查询, 云服务器利用多项式快速傅里叶变换算法求得a0和a1, 计算a1a0-1 mod p即为求和结果sum.返回证据w1和w2.
验证:判断e(gs, w1)与e(acc(S)/ga0, g)是否相等, 若不相等, 则a0系伪造, 终止并拒绝查询结果, 否则判断e(gs, w1)与e(acc(S)/ga0, g)是否相等, 若不相等, a1系伪造, 终止并拒绝查询结果, 否则判断sum与a1a0-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查询得到; 构建证据时, 返回在认证跳表ASLj×jT(key和value均由第j列元素构成)上对最大值和最小值做Search查询的证据.
验证:验证与Search查询的验证相同.
3.3.5 嵌套查询与验证查询:假定执行嵌套查询Q1ºQ2, 云服务器相当于分别执行查询Q1和Q2, 然后对Q1和Q2查询结果进行可验证的集合交集或并集操作.云服务器返回的证据为中间结果的摘要和验证最终结果的证据; 因不需要返回中间结果的全部证据, 从而极大地减小了存储与验证的开销.
验证:首先验证中间结果的摘要值与对应结果的摘要值是否相等, 若不相等, 终止并拒绝查询结果, 否则验证结果的正确性.根据查询类型在上文中找到相应的验证方法, 若验证失败, 终止并拒绝查询结果, 否则接受查询结果.
3.4 更新更新过程由数据拥有者和云服务器交互实现, 更新操作包括插入、删除、修改数据库中的一行(或多行)数据.云服务器更新外包数据库对应的数据和认证跳表, 数据拥有者更新摘要值.插入时, 首先通过Search查询找到低于插入元素x=(keyx, valuex)且最接近keyx的位置, 记录下搜索路径.找到最底层的位置后, 新建节点, 连入底层跳表.随机生成元素的最高层, 由低到高在每一层新建节点, 通过搜索路径进行相应的连接操作.删除时, 从起始节点开始搜索删除节点x, 找到x前一个位置的节点v, 则v.right即为x所在位置, 记录搜索路径.沿路径向上依次删除含有元素valuex的节点.修改时, 可先通过删除、再插入来实现.更新数据后, 数据拥有者输出更新后的摘要δ′, 并从底层节点一直更新至根节点.每个节点的更新过程:使用私钥解密
由于认证跳表弥补了双线性映射累加器不能实现范围查询、最大值和最小值查询的不足, 并且认证跳表的安全性在已有方案[8]中已得证明, 这里不在赘述.其他类型的查询都是基于求和查询的, 因此只要证明求和查询的安全性即可保证该方案的安全性.安全性证明如下:
如果存在一敌手A攻破了求和查询的安全性, 即伪造了一个结果及证据并通过了算法Verify的验证, 那么敌手A可构造一算法B, 以不可忽略的概率解决双线性q-SDH难题.证明过程如下.
算法B执行算法KeyGen生成公私钥对(pk, sk), 将pk发送给A, sk私密保存.A选定一个集合S, 算法B计算累加值acc(S)并公开, 敌手伪造求和的结果sum*, 并且证据a0*, a1*, w0*, w1*通过验证, 那么一定满足a0*≠a0或a1*≠a1.
情形1:当a0*≠a0时, 因为e(gs, w1*)=e(acc(S)/ga0*, g)且e(gs, w1)=e(acc(S)/ga0, g), 敌手A可计算出g1/s=(w1*/(gsn-1+…+ a2s+a1))(a0-a0*)-1, 这与双线性q-SDH难题相矛盾.
情形2:当a0*≠a0且a1*≠a1时, 因为e(gs, w1*)=e(acc(S)/ga0*, g), 可得w1*=gsn-1+…+a2s+a1.又因为e(gs, w2)=e(w1/ga1*, g), 敌手A可计算出g1/s=(w2*/(gsn-2+…+a2))(a1-a1*)-1, 这与双线性q-SDH难题相矛盾.
4.2 性能分析从查询类型的丰富性和算法效率两方面, 将本文方案与其他方案进行了对比.
在查询类型丰富性方面, 将本文方案与基于RAM、基于电路和基于树或签名的方案进行对比.由表 1可以看出, 本方案和基于电路的方案支持的查询类型更加丰富.
|
表 1 方案对比 Table 1 Comparison with prior works |
在算法效率方面, 从初始化、查询与验证、更新及认证跳表这4个方面对方案的性能进行了分析, 如表 2所示.其中, mi表示表i的列数, ni表示表i的行数, d为多维范围查询的维数, R为查询结果, n为认证跳表叶子节点数量, u表示更新的行数, O表示时间复杂度的上界.
|
|
表 2 性能分析 Table 2 Performance analysis |
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%2F978-3-642-40084-1_6 |