摘要
本篇文章提出了 Hu Fu（虎符） 系统，第一个基于数据联邦的安全空间查询处理系统，解决了现有解决方案空间查询效率低的问题，其思想是将空间查询的安全处理分解为尽可能多的明文操作和尽可能少的安全操作，并且支持原生SQL查询输入以及后端的异构空间数据库。
介绍
虎符系统消除了对诚实代理（Honest Broker（见SMCQL））的需求，并支持更多的数据仓库（测试了10个）。虎符的关键思想是在保证安全性的前提下将联邦空间查询分解为尽可能多的明文操作和尽可能少的安全操作，其中不涉及安全距离相关操作，且安全操作的实现速度比一般用途的 SMC 库更快。
虎符由三个组件组成：一个有着新颖组合方案的查询重写器，一组用于异构数据库的驱动程序以及一个支持 SQL 的易于使用的查询界面。查询重写器识别一组明文和安全运算符，以覆盖感兴趣的查询，并采用新颖的组合计划，在确保安全的同时尽量减少安全运算符的使用。驱动程序为安全运营商提供了专用的SMC协议和明文操作，作为不同数据仓库选择的异构空间数据库之上的接口。查询界面支持本地SQL中的空间查询，以便于使用。
本文的主要贡献如下：
- 第一个通过数据联邦执行高效、安全的空间查询的系统
- 新的关于联合空间查询的分解方案
Hu Fu（虎符），一个高效易用的支持 SQL 和异构空间数据库的系统
问题陈述
- 联邦范围查询/计数：返回所有在查询范围内的在联邦里的数据（个数）
- 联邦 KNN 查询：给定一个数据联邦 $ F = \{F_1, \dots, F_n\} $，一个查询点 $ p $ 和一个整数 $ k $，查询返回一个含有 $ k $ 个空间对象的集合 $ kNN(F, p, k) $（$ \forall o \in kNN(F, p, k), \forall o' \in F - kNN(F, p, k), d(p, o) \leq d(p, o') $）
- 联邦距离连接：给定一个空间对象的输入数据集 $ R $，一个数据联邦 $ F $ 和一个半径 $ r $，返回在 $ F $ 中的对 $ R $ 中所有对象距离小于半径的二元组（$ R \bowtie_r F = \{(o, o')|o \in R, o' \in F, d(o, o') \leq r \} $）
- 联邦 kNN 连接：给定一个空间对象的输入数据集 $ R $，一个数据联邦 $ F $ 和 $ k $，返回所有在 $ R $ 中的与 $ o' \in kNN(F, o, k) $ 成对的 $ o $（对象），整个过程不会泄露除返回集合以外的信息
当前研究的痛点主要在于过度的安全距离操作和对通用库的依赖，而虎符对大规模的安全距离操作涉及到的安全操作明显更少，每个安全操作也通过专用算法高效实现
系统概览
虎符通过两个模块解决了空间查询速度低下的问题：一个查询重写器和一个驱动程序
查询重写器江联邦空间查询分解为明文和安全操作符，驱动程序负责将这些操作符是纤维纯文本和安全原语，并使用专用算法实现和优化
虎符还包含一个透明的查询接口，他支持使用原生 SQL 编写的联邦空间查询
上图是虎符的工作流程，可以看到在每个数据孤岛上都运行着一个虎符 Drivers 实例，用于与其底层数据库进行交互。在用户机器上部署了查询接口和查询重写器，当查询时先通过查询接口进行解析，再通过查询重写器将其转换为一系列优化后的明文和安全运算符。随后这些运算符被发送到各个数据孤岛运行的 Drivers 并执行，随后各孤岛将局部结果返回给客户机的虎符接口，将结果汇总后再返回给用户。
查询重写器
运算符主要分为两大类：明文运算符和安全运算符
明文运算符
明文运算符可以涉及空间查询中强制执行的与距离相关的操作，在每个数据孤岛中本地执行，但应该是各种空间数据库广泛支持的常用操作
明文运算符分为明文范围查询和明文范围计数两种
- 明文范围查询：对于一个数据孤岛 $ F_i $，给定一个查询范围 $ \mathcal{R} $，明文范围查询 $ PRQ_{F_i}(\mathcal{R}) $ 返回 $ F_i $ 中在 $ \mathcal{R} $ 内的明文空间对象数据
- 明文范围计数：与明文范围查询相同，只不过返回的是空间对象的个数
安全运算符
安全运算符应避免有关距离的相关操作，用于孤岛间的数据操作，最好是高效实现的运算符
安全运算符分为安全求和、安全比较和安全集合合并三种
- 安全求和：对于一个联邦 $ F $，每个孤岛 $ F_i $ 持有一个数字 $ \beta_i $，安全求和在不向其他参与方泄漏 $ \beta_i $ 的同时计算并返回 $ \sum_{i=1}^{n}\beta_i $ ($ SSM_F(\beta_1, \dots, \beta_n) = \sum_{i=1}^{n}\beta_i $)
- 安全比较：对于一个联邦 $ F $，每个孤岛 $ F_i $ 持有一个数字 $ \beta_i $ 和一个值 $ k $，安全比较在不向其他参与方泄露 $ \sum_{i=1}^{n}\beta_i $ 或 $ \beta_i $ 的同时比较 $ \sum_{i=1}^{n}\beta_i $ 和 $ k $ 的大小 ($ SCP_F(\beta_1, \dots, \beta_n, k) = sign(\sum_{i=1}^{n}\beta_i - k) $)
- 安全集合合并：对于一个联邦 $ F $，每个孤岛 $ F_i $ 持有一个空间对象集合 $ S_i= {o_1^i, \dots, o_{m_i}^i} $，安全集合合并在不泄露每个集合的来源的情况下计算多个集合的并集 ($ SS\cup_F(S_1, \dots, S_n) = \bigcup^n_{i=1}S_i $)
总体分解策略
- 已知半径查询
理想情况下仅需一个安全运算符即可收集结果，因为纯文本运算符支持纯文本范围查询和计数，所以只需对结果集合使用安全求和/集合合并运算符即可 - 未知半径查询
对于未知半径查询，将该查询转为多个已知半径查询。对于夸孤岛间的通信需要额外的安全运算符。虎符使用二分搜索以尽量减少循环和安全运算符数量
已知半径查询的分解
联邦范围查询可被分解为 $ n $ 个明文半径为 $ r $ 的范围查询，联邦范围计数也可以被分解为 $ n $ 个明文范围计数。当夸孤岛收集结果时需要进行一个安全求和/集合合并，以防止数据泄露。
未知半径查询的分解
因为半径是未知的，所以首先应该获取一个合适的范围。
上图展示了如何对一个联邦 kNN 查询进行分解，其中：
- $ \nu_0 $ 为上界，他可以设置为区域直径或由用户来自定义
- $ \epsilon_0 $ 为精度下限，可以设置为位置坐标的精度
算法使用二分搜索，在每次迭代中，$ thres = \frac{l+u}{2} $，对每个孤岛的进行一次半径为 $ thres $ 的明文范围计数，并将结果的和与 $ k $ 做一次安全比较，如果当前 $ count $ 小于 $ k $ 则说明当前半径过短，将下界 $ l $ 更新为 $ thres $，并进行下一轮遍历；如果当前 $ count $ 大于 $ k $ 则说明当前半径中有足够的点，将上界 $ u $ 更新为 $ thres $。
使用差分隐私来加速未知半径查询
主要有以下两个方面：
- 缩小预定义上界：每个孤岛在本地明文执行 kNN 查询，并返回第 $ k $ 个对象到查询点的距离 $ d_i^k $。因为直接返回该值有可能会暴露实际距离，所以对其应用拉普拉斯机制，也就是对每个孤岛添加一个正噪声并获得扰动后的结果 $ d_i^{'k} $随后将所有孤岛中的上边界收紧至最小距离 $ \nu_0 = min_id_i^{'k} $，因为在这个范围内至少有 $ k $ 个点
- 减少安全比较的运行时间和通信成本：在上方的算法中对 $ \sum_1^n \beta_i $ 和 $ k $ 进行比较，而比较和通信的开销至少是 $ O(n^2) $，当 $ \sum_1^n \beta_i $ 和 $ k $ 明显不同时可以将其减少到 $ O(n) $。在这种情况下每个孤岛可以在局部计数结果上添加拉普拉斯噪声，随后汇总扰动后的结果。如果结果比 $ k $ 大/小很多，则直接对阈值进行调整
超越主流的空间查询
对于未知半径查询的分解方法也适用于其他查询范围的类型（如矩形），因为每个孤岛的底层空间数据系统都支持使用任意形状的查询范围进行明文范围查询/计数。同时查询重写器还支持聚合查询。
驱动
虎符的驱动中实现了明文和安全原语
安全求和原语
首先 $ n $ 个孤岛同意 $ n $ 个公共参数 $ = \{u_1, \dots, \u_n\} $，随后每个孤岛选择一个随机的 $ n-1 $ 次多项式 $ t_i(x) = (\sum_{k=1}^{n-1}a_{ik}x^k) + \nu_i $ 并计算得到 $ n $ 个值 $t_i(u_1), \dots, t_i(u_n)$。其中 $ a_{ik} $ 表示孤岛独立生成的随机系数，$ \nu_i $ 表示孤岛本地计算的计数结果。随后每个孤岛都想其他孤岛发送多项式 $ t_i(u_j) $ 的值。
当一个孤岛收到了所有其他孤岛发来的值后，它计算这些值的和 $ S(u_j) = \sum_{i=1}^nt_i(u_j)=(\sum_{k=1}^{n-1}(u_j^k\sum_{i=1}^na_{ik}))+\sum_{i=1}^n\nu_i $ 并将其发送给查询用户。用户可以将其看作为一个线性的等式 $ S(u_j) = \sum_{k=1}^{n-1}u_j^kz_k + z_n $，$ n $ 个未知参数为 $ z_k = \sum_{i=1}^na_{ik} (k=1, \dots, n - 1) $，$ z_n = \sum_{i=1}^n\nu_i $，用户还知道所有的公共参数和所有孤岛的计算和，所以用户可以使用高斯消元法获得 $ \sum_{i=1}^n\nu_i $
安全比较原语
安全比较的主要思想是计算 $ X(\sum_{i=1}^n\beta_i - k) $ 而不是 $ \sum_{i=1}^n\beta_i - k $。其中 $ X $ 是一个随机的正实数。虎符将安全比较简化为比较经典的安全乘法协议来确保安全。
安全乘法协议需要两个乘法器 $ x $ 和 $ y $，每个乘法器都被分为 $ n $ 个共享份额 $ X = \sum_{i=1}^nx_i $，$ Y = \sum_{i=1}^n y_i$，每个共享都被分发到各个孤岛。在虎符中的安全乘法协议中 $ Y = \sum_{i=1}^n\beta_i - k $，$ y_i = \beta_i = \frac{k}{n} $。因为每个孤岛都知道自己的结果 $ \beta_i $，用户只需要发送 $ \frac{k}{n} $ 给所有孤岛。随后每个孤岛随机生成一个正实数 $ x_i $ 并使用安全乘法协议计算 $ XY = (\sum_{i=1}^nx_i)(\sum_{i=1}^n\beta_i - \frac{k}{n}) $ 并将结果返回给用户。
安全集合合并原语
此原语基于随机共享，并分为两个阶段。第一阶段每个孤岛将其结果和一些假数据放到一个全局集合并在第二阶段中将他们移除。虎符使用差分隐私来减少虚假记录的数量，从而降低通信成本。观察到添加和删除家记录可以独立完成，所以将全局集合拆分为批处理，以允许并行执行。随后每个孤岛可以独立地添加和删除每个批次的噪声数据，从而缩短延迟。
查询接口
虎符的查询页面为用户提供了一个联邦视图，隐藏了底层各孤岛的详细信息，这使得用户发送查询时不需要担心孤岛的组织方式，还可以保护各个孤岛数据的安全性。虎符使用 Calcite 的模式管理器来实现统一联合视图。
相比于常规的 SQL 查询语句，虎符增加了两个新的关键字：DWithin 和 kNN。
DWithin(p, F.location, r) 返回所有在 $ F $ 中与 $ p $ 的距离小于 $ r $ 的对象
kNN(R.location, F.location, k) 指明 $ F $ 中的空间对象是否在 $ R $ 中的所有查询点的 kNN 集合中
性能评估
本章将虎符、Conclave 和 SMCQL 进行了对比
