本文由“大数据治理的理论与技术”专题特约编辑杜小勇教授、杨晓春教授和童咏昕教授推荐.
近年来, 多个国家地区出台了一系列数据安全相关的法律, 例如欧盟的《通用数据保护条例》等. 这些相关法律法规的出台, 加剧了各企业机构等多方之间数据共享难的数据孤岛问题. 数据联邦(data federation)正是解决该问题的可能出路. 数据联邦是指多个数据拥有方在不泄露各自原始数据的前提下, 结合安全多方计算等隐私计算技术, 联合完成查询任务的计算. 这一概念已成为近年来的研究热点, 并涌现出一系列相关的代表性系统工作, 如SMCQL、Conclave. 然而, 针对关系数据库系统中核心的连接查询, 现有数据联邦系统还存在如下问题: 首先, 连接种类单一, 难以满足复杂连接条件下的查询需求; 其次, 算法性能低下, 由于现有系统往往直接调用安全工具库, 其运行时间与通信开销高昂. 因此, 针对以上问题进行研究, 提出了数据联邦下连接算法. 主要贡献如下: 首先, 设计实现了面向多方的联邦安全算子, 能够支持多种运算; 其次, 提出了支持
Recently, many countries and regions have enacted data security policies, such as General Data Protection Regulation proposed by the EU. The release of related laws and regulations has aggravated the problem of data silos, which makes it difficult to share data among various data owners. The data federation is a possible solution to this problem. Data federation refers to the calculation of query tasks jointly performed by multiple data owners without disclosing their original data and combining privacy computing technologies such as secure multi-party computation. This concept has become a research trend in recent years, and a series of representative systems have been proposed such as SMCQL and Conclave. However, for the fundamental join query in the relational database system, the existing data federation system still has the following problems. First of all, the join query type is single. It is difficult to meet the query requirements under complex join conditions. Secondly, the algorithm performance has huge improvement space, because the existing systems often call the security tool library directly, which has high running time and communication overhead. Therefore, a data federation join algorithm is proposed to address the above issues. The main contributions of this study are as follows. Firstly, multiparty-oriented federation security operators are designed and implemented, which can support a variety of operations. Secondly, a federated
近年来, 我国数字经济得到蓬勃发展. 数据作为重要资源, 已成为各类数字化转型应用的核心要素. 然而, 随着大众对数据隐私安全的日益关注, 国内外相继颁布如欧盟《通用数据保护条例》等一系列隐私安全法规, 极大地限制了各机构之间的数据共享与流通. 为了探索如何破除新型“数据孤岛”困境, 数据联邦技术以其“原始数据不出域、数据可用不可见”的隐私安全理念, 正在成为一种近来流行的数据共享新范式[
数据联邦面向多个数据拥有方的自治数据库, 通过结合安全多方计算等隐私安全技术, 实现在原始数据不出本地前提下的多方联合查询. 在数据联邦系统中, 连接查询是核心的查询操作之一, 有着广泛的应用[
• 联邦连接语义单一. 现有的数据联邦连接查询算法可支持的语义较为单一, 大多数算法仅可支持等值连接查询. 而在真实的数据联邦场景中, 两表之间的连接条件往往更为复杂, 通常为包含大于、小于等比较关系的
• 联邦算法开销高昂. 现有的数据联邦系统通常基于通用型安全多方计算工具库实现, 计算时间和通信开销十分巨大. 例如, 在数据规模为2 000行的表格间做安全连接时, 其运行效率比明文连接低4−5个数量级[
针对上述挑战, 本文聚焦数据库中支持多种连接条件的𝜃-连接, 研究数据联邦中的
• 针对已有数据联邦算法所支持连接语义单一的挑战, 首先, 本文提出了数据联邦中的
• 针对现有数据联邦系统中连接算法性能表现的挑战, 本文提出了基于本地明文预处理的算法优化策略. 针对算法执行过程中频繁出现的安全多方基础算子, 提出通过本地预排序方法, 利用本地的有序性减少安全多方基础算子的执行次数, 从而优化联邦
• 在基准数据集TPC-H上, 以时间、通信量为指标, 将本文所提算法与现有数据联邦系统进行对比, 验证了所提算法框架和优化策略的有效性. 实验结果表明, 相比于已有的数据联邦系统, 所提算法可将运行时间与通信开销分别降低61.33%和95.26%.
本文第1节介绍本文的相关工作. 第2节给出联邦
安全多方计算是数据联邦中保护数据隐私安全常用的技术之一, 本节将分别从安全多方计算技术和数据联邦连接查询两个方向回顾与本文相关的研究工作. 具体总结如下.
安全多方计算(secure multi-party computation)的概念起源于姚期智院士在1982年提出的百万富翁问题[
姚期智院士提出了姚氏混淆电路[
从2012年起, 国内外陆续发布了多个基于混淆电路和秘密共享协议的安全多方计算工具库, 例如基于混淆电路协议的ABY[
数据联邦这一概念的原型是20世纪80年代出现的联邦数据库[
上述工作可支持数据联邦中一般形式的连接查询, 但普遍存在查询效率低的问题. 因此, 有研究者尝试针对某些特殊的连接查询进行优化. 如:
• Bater等人提出的Shrinkwrap系统运用差分隐私技术降低了在两方的安全连接查询中需补充的虚拟元组数量[
• 2021年发表的Secure Yannakakis算法则主要聚焦于数据分析领域常见的连接-聚合查询操作[
• 北京航空航天大学研发的虎符系统则针对数据联邦中的空间连接查询操作进行优化[
本节首先介绍数据联邦中的基础概念, 随后给出联邦连接查询的形式化定义.
数据拥有方
遵循现有研究中对数据联邦的定义[
本文安全模型中假设数据联邦中的各数据拥有方均遵循半诚实模型的设定, 即联邦中各个数据拥有方均严格遵守协议步骤执行, 而不会恶意篡改执行中间结果发送虚假信息等. 此外, 本文安全模型将充分考虑到各方串谋的情况, 即某几个参与方间互通信息后, 根据串谋所得信息从而推断出其他参与方的原始数据. 本文将通过协议防范在串谋情况下的原始数据泄露风险, 以提供更高的安全保障. 而用户仅接收查询结果, 不影响安全模型.
本文涉及的主要符号见
主要符号表
符号 | 描述 | 符号 | 描述 | |
第 |
数据联邦全局数据库 | |||
数据拥有方 |
全局数据库中的第 |
|||
数据联邦 | 数据联邦中的参与方数量 |
其中,
联邦
数据联邦算法框架图
本文采用安全多方计算技术实现数据联邦中的连接查询, 其算法框架如
本节将分别介绍安全多方基础算子以及基于该算子设计的联邦
为了保证数据联邦
• 安全多方加法算子
对于数据联邦中的
Input: 数据拥有方
Output: 各方求和结果
1: 随机生成
2:
3: 随机生成多项
4: 计算子秘密
5:
6: 计算秘密
7: 汇总所有
8:
具体而言, 该算子将首先随机生成
• 安全多方乘法算子
对于数据联邦中的两个以秘密形式分布在各方的值[[
Input: 分布在数据拥有方
Output: 两秘密的乘积
1:
2: 计算秘密
3: 汇总所有
4:
在安全多方加法算子中, 数据拥有方
• 安全多方比较算子
对于数据联邦中两个数据拥有方
该算子需要另外两个数据拥有方
Input: 数据联邦
Output:
1: 随机生成
2: 数据拥有方
3:
4: 计算秘密
5: 计算秘密
6: 调用安全多方乘法算子计算
7:
具体而言,
• 安全多方基础算子复杂度分析
3个安全多方计算基础算子均基于多项式进行秘密分发与重建, 这两个步骤的时间复杂度均为O(
• 拓展分析
依据本文所设定的攻击模型中可能存在串谋的情况, 因此在算子设计实现中, 本文算子要求必须全部
由于联邦数据分散在多方, 因此联邦
• 比较连接列. 收到基于全局视图的连接查询后, 需要根据各拥有方数据获取其映射关系, 从而将全局查询分解为子查询. 在此, 对解析过程不进行过多介绍, 本文假设已完成查询解析. 两联邦数据拥有方分别持有左表与右表, 并在
• 确定结果行. 根据上一步比较连接列的结果, 符合连接条件的
• 拼接结果. 联邦代理节点收到符合连接条件的两表元组后, 根据
以上算法框架的伪代码见算法4.
Input: 数据拥有方
Output: 联邦连接结果
1:
2:
3: 本地计算连接结果并发送至中心
4:
5:
6:
7: 汇总所有方的元组集合, 拼接得到最终结果
8:
算法4描述了联邦连接的算法框架. 第1−3行对应本地连接场景, 每个数据拥有方先判定自己是否同时持有左表与右表的一部分: 若持有, 则先在本地对两表进行连接操作, 并将该结果发送给中心. 第4−7行对应跨成员连接场景. 第4行意为枚举任意两个数据拥有方之间进行子查询. 第5行表明两表按照连接条件进行比较, 此时出于安全需要, 应通过安全多方算子对其进行比较, 以保护各方参与比较的原始数据安全. 并得到符合连接条件的列值集合. 第6行是指根据得到的列值集合, 取出列值在数据表中对应的行值, 得到符合连接条件的元组集合. 第7行中心汇总所有元组值, 并按连接条件拼接出连接结果. 至此得到最终的联邦
联邦
• 算法安全性分析
算法4的第1−3行均在各数据拥有方本地执行, 不涉及数据拥有方之间的交互, 不会暴露其他信息.第5行涉及数据拥有方
• 算法复杂度分析
在算法4中, 第1−3行均为明文计算, 可忽略不计. 第4−6行首先枚举了任意两个数据拥有方
基于上一节提出的联邦连接泛框架, 其中的核心操作在于如何确定符合连接条件的列值集合. 该操作设计安全保护需求, 需要较高的安全操作开销. 因此, 本节主要针对比较连接列这一环节进行算法设计, 并充分利用比较结果包含的信息, 提出基于排序合并思想的优化策略.
为了实现对两个表的列值比较, 最简单直接的方法是基于双重循环的思想. 然而该方法需要进行O(
基于以上减少安全操作的优化思想, 本文提出了联邦
• 列值比较. 左指针指向左表连接列中的某一列值, 右指针指向右表连接列中的某一列值. 调用安全比较算子, 计算两个列值是否符合
• 右指针移动. 若比较结果为不符合比较条件, 则指向右表的右指针应当继续向下移动, 以便于继续比较. 此外, 由于列值为有序列表, 因此为找到首个符合要求的列值, 也可以采用二分搜索的方法进行定位.
• 左指针移动. 若比较结果符合条件, 则首先应当将对应列值加入集合中, 然后将左指针下移一位. 根据传递性可知, 左指针所指元素值对右指针前的元素值必然不符合连接条件. 因此, 直接从右指针此时指向的列值继续进行比较即可.
算法5为该优化后联邦连接的算法伪代码.
Input: 左表
Output: 符合连接条件的列值集合
1: 初始化指针
2:
3:
4:
5:
6:
7:
8:
以上伪代码描述了针对列值比较步骤的优化策略. 算法5第1行表示对指针与集合进行初始化, 将指针先指向左右表列值的首项, 将结果集合初始化为空集. 第2−7行描述优化后列值比较的过程: 第3行表示首先通过调用所设计实现的安全多方比较算子
同样沿用前面使用的实例, 通过其中的运行步骤来解释该优化策略. 如
联邦
• 算法安全性分析
在算法5中, 第3行的安全性由安全多方比较算子保证. 对数据拥有方
• 算法复杂度分析
算法5是对算法4中第5行的一个优化. 在算法5中, 第2−7行循环次数总共仅为
利用算法5实现的数据联邦
本文通过基准数据集上的实验来衡量本文所提算法相较于已有数据联邦系统的性能提升, 验证本文所提优化策略的有效性. 本节首先介绍实验环境设置, 然后从安全多方算子与联邦
本实验使用多台机器模拟联邦场景下多个数据拥有方的计算模式, 其中每台机器CPU型号为: Intel® Xeon® Platinum 8269CY CPU T 3.10 GHz), 内存32 GB, 操作系统为Ubuntu 18.04.5 LTS (Bionic Beaver), 机器间通信带宽约为6 GB/s. 采用一台机器模拟中心的联邦代理节点, 在其他机器为每个数据拥有方配置对应数据库. 在联邦连接查询执行过程中, 多台机器联合完成计算. 本实验环境设置更好地模拟了各个数据拥有方自治数据的联邦场景.
本实验选择TPC Benchmark™H (TPC-H)作为测试数据集. 该基准数据集是数据库领域测试系统查询分析性能的常用数据集, 因此本文选择该数据集测试所提连接查询算法的性能表现. TPC-H数据集来自供应商应用场景, 包含多种商品信息、订单信息等数据表, 支持生成不同数据规模的数据集.
本实验选择数据联邦系统SMCQL[
首先, 对本文设计实现的3种多方安全算子进行实验验证. 该实验内容为对两个整数进行求和、求积与比较运算. 其中, 比较对象OblivC仅支持两个参与方; SPDZ与本文所提多方安全算子Poly可支持多个参与方的运算, 实验具体设定为4个参与方(如
多方安全算子性能比较
从实验结果上可以看出, 本文所提多方安全算子Poly在运行时间上远优于其他方法, 在通信开销上处于中间水准. 在运算时间上, 本文所提方法Poly均耗时最短: 在求和运算上, Poly比SPDZ提升了87.56%; 在求积运算上, Poly比SPDZ提升了85.80%; 在比较运算上, 所提方法比SPDZ提升了75.92%. 这是由于本文方法主要基于秘密共享实现, 比混淆电路耗时更低. 在通信开销上, 本文所提方法均低于SPDZ, 但略高于OblivC: 在求和运算上, 本文所提方法比SPDZ降低了90.82%; 在求积运算上, 本文所提的方法比SPDZ降低了78.46%; 在比较运算上, 本文所提的方法比OblivC降低了78.39%. 由于秘密共享需要参与方间共享秘密值, 因此本文方法在通信开销上略高.
综上实验结果, 本文实现的多方安全算子在运行时间与通信开销上的性能表现良好, 尤其在执行时间效率上优于其他方法, 因此能够有效地支撑在
本文基于多方安全算子构建了包含3阶段的数据联邦连接算法框架, 本节将针对所提算法进行实验验证.本文选择支持
本节实验验证本文所提出的
数据规模变化时, 各系统性能对比
从实验比较结果可以看出, 随着查询数据规模的增加, 各算法的运行时间与通信开销均有所增加, 而本文所提的算法均保持性能最佳. 在运行时间上, SMCQL系统运行耗时随数据规模增长出现了明显的增加; Conclave与本文所提Sort-Merge算法的增幅均较为缓慢, 其中, 本文所提Sort-Merge算法耗时在各数据规模下均保持最低, 比SMCQL降低了98.18%, 比Conclave降低了61.33%. 在通信开销上, SMCQL系统与Conclave系统开销相近, 且SMCQL略低于Conclave, 二者开销均随数据规模增加明显增长; 本文所提Sort-Merge算法比二者低一个数量级, 其通信开销比SMCQL降低了93.36%, 比Conclave降低了95.26%. 综合以上实验结果可以看出, 本文所提Sort-Merge算法在数据规模增长时性能表现均优于比较对象SMCQL与Conclave.
接下来验证本文所提
数据拥有方数量变化时各系统性能对比
从实验比较结果可以看出, 随着数据拥有方数量的增加, 各算法的运行时间与通信开销均有所增加, 而本文所提的算法均保持性能最佳. SMCQL系统的运行耗时随数据拥有方数量的增长出现了明显的增加, 在数据拥有方数量为7方时, 已无法在规定时间内得出结果. 而Conclave与本文所提Sort-Merge算法的增幅均较为缓慢, 其中, 本文所提Sort-Merge算法耗时最低, 比SMCQL降低了95.55%, 比Conclave降低了37.50%. 在通信开销上, 本文所提Sort-Merge算法比SMCQL和Conclave系统低一个数量级, 其通信开销比SMCQL降低了93.23%, 比Conclave降低了95.59%. 综上实验结果可以看出, 本文所提Sort-Merge算法在数据拥有方数量增长时性能表现均优于比较对象SMCQL与Conclave.
本节实验验证本文所提优化策略Sort-Merge相较于基础算法Nested-Loop的性能提升表现, 其中, 数据拥有方数量设定为4方. 算法随数据规模增加的运行时间、通信开销变化如
数据规模变化时各算法性能对比
从实验结果可以看出, 本文所提的优化策略Sort-Merge相较于基础算法Nested-Loop有着较大的性能提升, 其运行时间与通信开销均接近于明文查询. 随着运行数据规模的增加, Nested-Loop方法的连接查询耗时明显增加, 在数据规模为2 600时, 已无法在规定时间内得出结果. Sort-Merge算法在运行数据规模增加时的连接查询耗时增速较慢. 与Nested-Loop算法相比, Sort-Merge算法的运行时间降低两个数量级, 不超过明文查询耗时的5倍. 就通信开销而言, Sort-Merge算法相较于Nested-Loop算法可减少96.10%, 且随着数据规模的增加, Sort-Merge算法的通信开销逐渐逼近明文查询.
接下来验证本文所提出的算法优化策略在数据拥有方数量变化时的性能提升情况, 其中, 数据规模设定为1 500行. 其运行时间和通信开销如
数据拥有方数量变化时各算法性能对比
可以发现, 随着数据拥有方数量的增长, 所有算法的运行时间和通信开销均逐渐增加. 在数据拥有方数量为5时, 基础算法Nested-Loop已无法在规定时间内得出结果. 与其相比, Sort-Merge算法的运行时间与通信开销均下降了一个数量级. Sort-Merge算法的通信开销相较于明文查询而言仅增加了170 M, 这进一步证明了所提优化策略Sort-Merge的有效性.
本文研究了数据联邦场景下的数据库连接查询问题. 首先, 针对现有研究对连接查询语义支持有限的问题, 本文提出了联邦
本系统的未来工作如下.
• 支持数据联邦中多表的连接查询算法. 本文所提算法仅可支持数据联邦中分散在多方的两张数据表之间的连接查询, 直接将该方法扩展到多张表的查询则会泄露在连接过程中的中间结果, 存在隐私泄露风险. 如何针对这一场景设计相应算法支持多张表的联邦
• 面向恶意攻击者模型的连接查询算法. 本文基于半诚实模型假设, 即每个数据拥有方会如实地按照多方协议执行相应的查询, 仅会在协议的执行过程中尝试推断其他数据拥有方的信息, 不会恶意发送错误数据. 而恶意攻击者模型则是指数据拥有方可能不按照协议执行查询, 并发送错误数据, 从而骗取其他数据拥有方的信息. 如何在此模型下设计联邦连接查询算法, 同样是值得研究的问题之一.
Bater J, Elliott G, Eggen C,
et
Li SY, Ji YD, Shi DY, Liao WD, Zhang LP, Tong YX, Xu K. Data federation system for multi-party security. Ruan Jian Xue Bao/ Journal of Software, 2022, 33(3): 1111−1127 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6458.htm [doi: 10.13328/j.cnki.jos.006458]
李书缘, 季与点, 史鼎元, 廖旺冬, 张利鹏, 童咏昕, 许可. 面向多方安全的数据联邦系统. 软件学报, 2022, 33(3): 1111−1127. http://www.jos.org.cn/1000-9825/6458.htm [doi: 10.13328/j.cnki.jos.006458].
et
Shi YX, Tong YX, Zeng YX,
et
Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation. Foundations and Trends® in Privacy and Security, 2018, 2(2−3): 70−246.
Zhu Y, Yang YT, Sun ZW, Feng DG. Ownership proofs of digital works based on secure multiparty computation. Ruan Jian Xue Bao/Journal of Software, 2006, 17(1): 157−166 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/157.htm [doi: 10.1360/jos170157]
朱岩, 杨永田, 孙中伟, 冯登国. 基于安全多方计算的数字作品所有权证明. 软件学报, 2006, 17(1): 157−166. http://www.jos.org.cn/1000-9825/17/157.htm [doi: 10.1360/jos170157].
Liu YX, Chen H, Liu YH, Li CP. Privacy-preserving techniques in federated learning. Ruan Jian Xue Bao/Journal of Software, 2022, 33(3): 1057−1092 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6446.htm [doi: 10.13328/j.cnki.jos. 006446]
刘艺璇, 陈红, 刘宇涵, 李翠平. 联邦学习中的隐私保护技术. 软件学报, 2022, 33(3): 1057−1092. http://www.jos.org.cn/1000-9825/6446.htm [doi: 10.13328/j.cnki.jos.006446].
Tan ZH, Yang GM, Wang XW, Cheng W, Ning JY. Threshold secret sharing scheme based on multidimensional sphere for cloud storage. Ruan Jian Xue Bao/Journal of Software, 2016, 27(11): 2912−2928 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4943.htm [doi: 10.13328/j.cnki.jos.004943]
谭振华, 杨广明, 王兴伟, 程维, 宁婧宇. 面向云存储的多维球面门限秘密共享方案. 软件学报, 2016, 27(11): 2912−2928. http://www.jos.org.cn/1000-9825/4943.htm [doi: 10.13328/j.cnki.jos.004943].
Shamir A. How to share a secret. Communications of the ACM, 1979, 22(11): 612−613.
et
Sheth AP, Larson JA. Federated database systems for managing distributed, heterogeneous, and autonomous databases. ACM Computing Surveys, 1990, 22(3): 183−236.
et
Bater J, Park Y, He X,
et
Bater J, He X, Ehrich W,
Tong YX, Pan XC, Zeng YX,