MDM 2021 A Differentially Private Task Planning Framework for Spatial Crowdsourcing
摘要 本篇文章定义了隐私保护任务规划（Privacy-Preserving Task Planning, PPTP）问题，该问题致力于任务位置的差分隐私和平台总收益最大化。本篇文章首先应用了拉普拉斯机制来保护位置，随后对 PPTP 问题提出了一种有效且高效的任务规划算法，并对其进行了验证。 介绍 本篇文章有如下贡献： 定义 PPTP 问题并提出一个高效的私有任务规划（Efficient Private Task Planning, EPTP）解决方案框架，其由一个可以保证地理不可区分性（geo-indistinguishability）的隐私机制和一个最大化收益的任务规划算法组成 量化了地理不可区分的隐私机制对任意任务规划算法的可靠性 在理论分析的基础上设计了一个新的任务规划算法，以较低的时间成本达到近似最大化收益 验证了算法的有效性和高效性 前言 本章定义了 PPTP 问题并提出了用于评估在位置隐私约束下的任务规划算法有效性的分析模型，下面是本章用到的符号说明： 问题定义 任务（Task） 一个任务 $ t $ 是一个五元组 $ (loc_t, rel_t, exp_t, rev_t, \epsilon_t) $，其中 $ loc_t $ 是任务位置，$ rel_t $ 是释放时间，$ exp_t $ 是过期时间，$ rev_t $ 是任务 $ t $ 完成给平台带来的收入，$ \epsilon_t $ 是任务 $ t $ 的隐私预算。 考虑任务规划的在线设置，一个任务 $ t $ 的出现在释放时间 $ rel_t $ 之前是未知的。如果工人 $ w $ 在任务过期时间 $ exp_t $ 之前到达以 $ loc_t $ 为圆心，半径为 $ R $ 的圆内，则任务 $ t $ 完成。其中半径 $ R $ 定义在后文，取决于应用场合。 工人（Worker） 一个工人 $ w $ 是一个四元组 $ (sLoc_w, dLoc_w, rel_w, exp_w) $，其中 $ sLoc_w $ 是初始位置，$ dLoc_w $ 是目标位置，$ rel_w $ 是释放时间，$ exp_w $ 是过期时间。 一个工人 $ w $ 的出现在释放时间 $ rel_w $ 之前是未知的，工人在释放时间 $ rel_w $ 时出现在初始位置 $ sLoc_w $。使用 $ cLoc_w $ 来代替工人 $ w $ 的当前位置。如果一个工人 $ w $ 可以在有效时间间隔 $ [rel_t, exp_t] $ 内到达任务 $ t $ 的位置并处于圆心为 $ loc_t $，半径为 $ R $ 的圆内，则它可以完成这个任务 $ t $，并为平台增加 $ rev_t $ 的收入。此外，使用 $ dis(.,.) $ 来表示两个位置的距离，并假设工人以单位速度移动。 任务计划（Task Plan） 一个工人 $ w $ 的任务计划 $ p_w $ 是一个工人 $ w $ 从当前位置 $ cLoc_w $ 出发应该顺序到达的位置序列 $ \langle l_1, l_2, \dots, l_{\left|p_w\right|} \rangle $。当工人 $ w $ 可以在过期时间 $ exp_w $ 前到达目的地 $ dLoc_w $ 时这个计划 $ p_w $ 是合法的，即 $$ curT + dic(cLoc_w, l_1) + \sum_{i = 1}^{\left| p_w \right| - 1} dis(l_i, l_{i + 1}) \leq exp_w $$ 其中 $ curT $ 是当前时间。 假设 $ P $ 是一个所有工人的计划集合，即 $ \{ p_w | w \in W \} $。由工人 $ w $ 完成的计划 $ p_w $ 定义为 $ AT(p_w) $。为了简便，使用 $ AT(P) $ 表示集合 $ P $ 中所有已完成的任务集合，即 $ A T(P)=\cup_{p \in P} A T(p) $。假设计划由任务规划算法生成，并保证有效性。 隐私机制（Privacy Mechanism） 给定一个位置空间 $ \mathcal{L} $ 和一个模糊位置空间 $ \mathcal{L}^\prime $，隐私机制 $ \mathcal{M} $ 是一个概率函数，将 $ \mathcal{L} $ 中的每个精确位置 $ x $ 以某种概率映射到 $ \mathcal{L}^\prime $ 中的一个模糊位置 $ x^\prime $ 地理不可区分性（Geo-Indistinguishability） 一个隐私机制 $ \mathcal{M} $ 如果对任何 $ x_1, x_2 \in \mathcal{L} $ 和 $ x^\prime \in \mathcal{L}^\prime $ 有 $$ \frac{Pr(x_1, x^\prime)}{Pr(x_2, x^\prime)} \leq e^{\epsilon \cdot dis(x_1, x_2)} $$ 则这个机制符合 $ \epsilon-Geo-Indistinguishability $ 隐私保护任务规划问题（Privacy-Preserving Task Planning Problem, PPTP Problem） 给定一组动态工人集合 $ W $ 和一组动态任务集合 $ T $，问题是为任务设计一个隐私机制 $ \mathcal{M} $，为工人制定计划集合 $ P $，其中机制 $ \mathcal{M} $ 以任务 $ t $ 的位置 $ loc_t $ 为输入，输出一个符合地理不可区分性的模糊位置 $ loc_t^\prime $；并对任务的模糊位置进行规划，最大化已完成任务的总收益，即 $ Rev(P) = \sum_{t \in AT(P)} rev_t $，问题示例如下： 假设当前有2个工人和3个任务，他们的释放时间和过期时间如下 Table II 所示，对应的位置如下 Fig. 1 所示： 任务 $ t_1 $ 的真实位置 $ (1.5, 4) $ 被隐私机制扰动至模糊位置 $ (2, 4) $。假设半径 $ R $ 为1并且任务 $ t_1 $ 被分配给工人 $ w_1 $，因为 $ dis(t_1, t_1^\prime) = 0.5 \leq 1 $，所以工人 $ t_1 $ 可以通过到达模糊位置$ (2, 4) $ 来完成任务。 分析模型 竞争比（Competitive Ratio, CR） 假设 ALG 是基于混淆位置的兴趣算法，OPT 是基于任务精确位置的最优算法，ALG 的竞争比是在隐私机制分配的期望收益与 OPT 获得的收益之比，即 $$ C R_p(A L G)=\min _{I \in \mathcal{I}} \frac{\mathbb{E}_{\mathcal{M}}[\operatorname{Rev}(A L G(I))]}{\operatorname{Rev}(O P T(I))} $$ 其中 $ \mathcal{I} $ 是所有实例的空间，$ ALG(I) $ 和 $ OPT(I) $ 是由 $ ALG $ 和 $ OPT $ 生成的规划。 高效的私有任务规划框架（Efficient Private Task Planning Framework, EPTP Framework） 框架概览 上图展示了 EPTP 框架的概览，工作流程如下： 平台收集工人和任务的信息，其中任务的精确位置在发送至平台之前使用隐私机制进行扰动 平台使用模糊位置来执行任务规划算法为工人制定计划 工人根据计划完成被指定的任务 隐私机制及分析 本文首先针对隐私预算为 $ \epsilon_t $ 的任务 $ t $ 提出了一种 $ \epsilon_t-geo-indistinguishability $ 的隐私机制，使用平面拉普拉斯分布，该机制将 $ loc_t \in \mathcal{X} $ 以下式的概率映射到 $ loc_t^\prime \in \mathcal{X} $： $$ \operatorname{Pr}\left(l o c_t, l o c_t^{\prime}\right)=\frac{\epsilon_t^2}{2 \pi} \cdot e^{-\epsilon_t \cdot d i s\left(l o c_t, l o c_t^{\prime}\right)} $$ 任务规划算法（Task Planning Algorithm） 本算法使用动态插入方法（dynamic insertion approach），在为单个工人规划时考虑了长期效应，并应用动态规划来提高算法的效率。动态插入方法描述如下： 当一个工人 $ w $ 出现时，算法调用 TaskPlanSingleWorker 函数（在后文 Algorithm 2 中描述）来为 $ w $ 从可用任务集合 $ T_{avai} $ 中制定计划；当一个任务 $ t $ 出现时，算法调用 InsertTask 函数（在后文 Algorithm 3 中描述）以最小的额外距离将 $ t $ 插入到已经到达平台（$ w_{best} \in W_{act} $）的工人的现有计划中，同时保持其他任务的顺序不变。 单工人任务规划（TaskPlanSingleWorker, Algorithm 2） 算法描述如下： 当为新出现的工人制定计划时使用贪心策略，通过下方两个定义来考虑当前的平均收益和长期效应。 每空移动距离收益（Revenue per Empty Moving Distance, REMD） 给定一个可用任务 $ t $ 和一个新出现的工人 $ w $，$ w $ 与 $ t $ 之间的 REMD 定义如下： $$ R E(w, t)=\frac{\operatorname{rev}_t}{\operatorname{dis}\left(c \operatorname{Loc}_w, \operatorname{loc}_t^{\prime}\right)} $$ 拥有更大 REMD 的任务在为新出现的工人分配任务时拥有较高的优先级。对于长期效应： 如果任务 $ t $ 有较小的空闲时间（$ exp_t - curT $），他应该被分配一个较高的优先级，因为它会以更高的概率过期 如果任务 $ t $ 更靠近 $ w $ 的目的地 $ dLoc_w $，它应当被分配较低的优先级，因为任务在之后（工人沿途前往目的地时）可以更有效的完成 为了衡量这种长期效应，定义了每一朝向目的地距离空闲时间（Spare Time per Heading Destination Distance, STHDD） 每一朝向目的地距离空闲时间（Spare Time per Heading Destination Distance, STHDD） 给定一个工人 $ w $ 和当前时间 $ curT $，$ w $ 与 $ t $ 之间的 STHDD 定义如下： $$ S T(w, t)=\frac{\exp p_t-c u r T}{\operatorname{dis}\left(\operatorname{loc}_t^{\prime}, d L o c_w\right)} $$ 不同于 REMD，拥有更大 STHDD 的任务意味着更低的优先级，因为它可以在之后更高效的完成。 上文 Algorithm 2 描述了考虑上述两方面（REMD, STHDD）的单工人任务规划算法，算法首先将可用任务集合 $ T_{avai} $ 根据 RMED 和 STHDD 的比值（$ \frac{RE(w, t)}{ST(w, t)} $）进行排序，然后按排序顺序将任务追加到计划 $ p_w $ 中（只要任务不违反 $ t $ 和 $ w $ 的到期时间）。如果没有任务被分配给 $ w $，则 $ w $ 移动到它的目的地 $ dLoc_w $ 基于动态规划的插入（Dynamic Programming based Insertion, Algorithm 3） 算法描述如下： 给定一个工人 $ w $ 和他未完成的计划 $ p_w = \langle l_1, l_2, \dots, l_{m_w} \rangle $，$ D_w[i] $ 是 $ w $ 从当前位置 $ cLoc_w $ 到第 $ i $ 个位置 $ l_i $ 所需的时间。在 $ p_w $ 中的最后一个位置也是 $ w $ 的目的地，即 $ l_{m_w} = dLoc_w $。对 $ i = 1, \dots, m_w $，$ E_w[i] $ 代表在第 $ i $ 个位置 $ l_i $ 之前插入任务 $ t^* $ 所引起的额外通行距离，即 $$ E_w[i] = \left\{\begin{array}{l} \operatorname{dis}\left(c L o c_w, l o c_{t^*}^{\prime}\right)+\operatorname{dis}\left(l \operatorname{loc}_{t^*}^{\prime}, l_i\right)-\operatorname{dis}\left(c L o c_w, l_i\right), i=1 \\ \operatorname{dis}\left(l_{i-1}, l o c_{t^*}^{\prime}\right)+\operatorname{dis}\left(\operatorname{loc}_{t^*}^{\prime}, l_i\right)-\operatorname{dis}\left(l_{i-1}, l_i\right), 2 \leq i \leq m_w \end{array}\right. $$ 算法的基本思想是，如果我们将任务 $ t^* $ 插入到计划 $ p_w $ 中的位置 $ l_k $ 之前，则 对 $ 1 \leq i < k $，从 $ cLoc_w $ 到 $ l_i $ 的通行距离，即 $ D_w[i] $ 保持不变 对 $ k \leq i \leq m_w $，从 $ cLoc_w $ 到 $ l_i $ 的通行距离会增加 $ E_w[k] $ 这表明当在 $ p_w $ 中寻找最佳的任务 $ t^* $ 的插入位置时，只有 $ E_w[k] $ 和 $ t^* $ 有关，其他变量都可以预先计算。更具体的，可以使用一个变量列表来代替在 $ p_w $ 中每个位置插入 $ t^* $ 的最大容忍的额外通行时间，并用这些变量来确定插入位置的有效性。设 $ MD_w[k] $ 为一个任务插入到 $ l_k $ 之前并保证所有 $ p_w $ 中的任务都不会过期的最大容忍额外通行时间，则 $ MD_w[k] $ 要么是任务在 $ l_k $ 的最大容忍额外通行时间（用 $ e_k $ 表示），形式表示为 $ e_k - D_w[k] $，要么是任务在 $ \{l_{k+1}, l_{k+2}, \dots, l_{m_w}\} $ 的最大容忍额外通行时间。 因此，我们可以用如下的方法计算 $ MD_w[k] $： $$ M D_w[k]= \begin{cases}\exp _w-D_w\left[m_w\right], & k=m_w \\ \min \left(e_k-D_w[k], M D_w[k+1]\right), & 1 \leq k<m_w\end{cases} $$ 在计算出 $ 1 \leq k \leq m_w $ 的 $ MD_w[k] $ 后，我们可以通过判断是否 $ E_w[k] \leq MD_w[k] $ 来确定任务 $ t $ 在 $ t_k $ 之前的插入是否合法（不会导致过期）。最后我们可以通过从 $ m_w $ 到 1 迭代 $ k $，计算 $ MD_w[k] $ 和 $ E_w[k] $，并比较是否 $ E_w[k] \leq MD_w[k] $ 来寻找最佳插入位置。 为了找到最佳插入位置，对每个工人 $ w_a \in W_{act} $，首先基于上文提到的算式计算列表 $ E_{w_a}[.] $ 和 $ MD_w[.] $，随后对每个插入位置 $ i $，对 $ E_{w_a}[i] $ 和 $ MD_{w_a}[i] $ 的值进行对比来判断插入后的计划是否有效且有最小的额外距离，并更新当前最佳插入位置。 实验 本文在合成和真实数据集上进行了实验，实验参数如下表： 本文将 EPTP 与两种具有相同隐私机制的先进任务规划算法进行了比较： baseline-Delay：Delay Planning algorithm，为每个新到达的工人分配任务，并保持计划不变直到工人完成计划 baseline-Fast：Fast Planning algorithm，随着任务到来不断更新计划 实验结果如下： 任务数量和工人数量的影响（Effect of $ \left| T \right| $ && Effect of $ \left| W \right| $） 当工人数量不变时，EPTP 表现最好，其次是 baseline-Fast，最后是 baseline-Delay，这是因为 EPTP 考虑了当前收入和长期效应。 当任务数量不变时，随着工人数量的增加，所有三种算法（包括EPTP）的收入都会增加。其中，EPTP 在大多数情况下表现最佳，并且相对于 baseline 有39％-70％的收入提高。此外，随着工人数量的增加，baseline-Fast 和 EPTP 的时间成本也会增加，而 baseline-Delay 则保持稳定。最后，在内存成本方面，EPTP 和 baseline-Fast 消耗相似大小的内存，并且它们在内存成本方面更有效率。 任务空闲时间（$ exp_t - rel_t $）和工人空闲时间（$ exp_w - rel_w $）的影响（Effect of $ ts_t $ && Effect of $ ts_w $） 在不同任务空闲时间的情况下，EPTP 仍然是最优的。随着任务空闲时间的增加，三种算法的收入都增加，但是 baseline-Delay 的收入较小。在时间方面 baseline-Fast 和 EPTP 都会增加，baseline-Delay 保持不变。 在不同工人空闲时间的情况下，EPTP 还是最优的。随着任务空闲时间的增加，三种算法的收入都增加，EPTP 收入最高。在时间方面，在大多数情况下所有算法的时间成本保持稳定，这是因为无论如何算法都要遍历所有任务，所以时间不会有太大改变。/ 半径 $ R $ 和最大收入的影响（Effect of the radius $ R $ && Effect of $ Rev_{max} $） 在不同半径 $ R $ 的情况下，EPTP 在大多数情况下仍然表现最好。随着半径增加，三种算法收益都增加。在时间成本上，EPTP 优于 baseline-Fast，baseline-Delay 表现最优。 在不同最大收益的情况下，EPTP 仍然优于 baseline，所有算法的收益都随着 $ Rev_{max} $ 的增加而增加。baseline-Fast 和 EPTP 的增加幅度大于 baseline-Delay。时间和内存成本稳定。 在真实数据集上的表现（Performance on Real Datasets） EPTP 在大多数情况下优于 baseline，并拥有合理的时间和内存开销，与合成数据集上的实验结果一致。
VLDB 22 Adore: Differentially Oblivious Relational Database Operators
摘要 本篇论文提出了 Adore：一组差分不经意关系型数据库运算符的实现（A set of Differentially Oblivious RElational database operators），包括带投影的选择、带聚合分组和外键连接。这组运算符降低了缓存复杂度、运行时复杂度和输出大小，并且比目前最先进的完全不经意算子（ObliDB）快7.4倍。 介绍 本章介绍了一些硬件加密方法（Intel SGX、RISC-V Sanctum），介绍了差分隐私技术在增强数据隐私方面的应用，提出了differential obliviousness，并从缓存复杂度、时间复杂度和输出大小三个方面进行了评估（如下图） 本篇论文贡献如下： 将差分不经意性应用到数据库运算符中，设计了三种不经意运算符 形式化证明了这些运算符满足差分不经意性，并且降低了缓存复杂度和输出虎大小 通过实验证明了这些运算符相对于当前最先进的完全不经意运算符有性能提升（7.4×） 背景 威胁模型 以 Intel SGX 为例，数据存储在 enclave（被隔离的内存区域，不能被os等访问）中并加密，用户通过一个不可信的 I/O 组件与其沟通，用户将加密查询发送给不可信组件后，不可信组件再将加密查询发送给 enclave，相同的，enclave 也会将输出的加密数据经由不可信组件发送给用户。同时 enclave 可能会将一些加密数据写入内/外存，因为预留的内存空间（enclave）是有上限的，而攻击者通过观察 enclave 如何读写加密数据和中间结果可以推测出一些信息。 内存访问模式（Memory access patterns） 内存访问模式可以反映数据的访问模式，如顺序访问、随机访问、局部性访问等。如果某些程序的内存访问模式包含了某些敏感数据的特定访问模式，那么攻击者可能会根据这些内存访问模式来推断出这些敏感数据的存在和内容，从而造成数据隐私泄露。 其次，内存访问模式和数据隐私还存在着一定的信号侦听风险。攻击者可以通过监视内存访问模式来获取机密数据的信息。例如，在一些侧信道攻击中，攻击者可以通过监视程序或系统的内存访问模式，可以推断出正在执行的代码或访问的数据是什么，从而进一步获取敏感数据。 差分不经意性（Differential Obliviousness） 与标准的差分隐私不同，本文并不要求数据计算的输出是私有的，但是要求计算的过程、数据库系统的可观测运行时候的行为，即访问模式是差分私有的，而这一概念被称为差分不经意性。 一个算法 $ \mathcal{A} $ 满足 $ (\epsilon, \delta)-\operatorname{differentially Obliviousness} $，如果对任意两个相邻数据库 $ D_1 $，$ D_2 $ 和任意内存访问模式 $ S $ 的子集，有： $$ \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_1\right) \in S\right] \leq e^\epsilon \cdot \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_2\right) \in S\right]+\delta $$ 完全不经意性（Full Oblivious） 一个算法 $ \mathcal{A} $ 是不经意的，如果对任意两个大小相同的数据库 $ D_1 $，$ D_2 $ 和任意可能的内存访问模式 $ S $ 的子集，有 $$ \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_1\right) \in S\right] \leq \operatorname{Pr}\left[\mathcal{M}\left(\mathcal{A}, D_2\right) \in S\right]+\delta $$ 差分不经意运算符 本章用到的符号解释如下表： 带投影的选择（selection with projection）$ (\sigma, \prod) $ select column_name1, column_name2 from table_name where condition select 运算符得到一个关系，并根据给出的条件输出一个子集，在关系代数中写作 $ \sigma_{\phi}(R) $，其中 $ \phi $ 是过滤谓词，$ R $ 是输入表（table_name） projection 运算符将一个关系转换为另一个，在关系代数中写作 $ \prod_{a_1, \dots, a_n}(R) $，其中 $ a_1, \dots, a_n $ 是一系列属性的集合，在结果中保留了 $ a_1, \dots, a_n $ 这些属性而舍弃掉了其他的 简单非不经意算法（Naïve non-oblivious algorithm） 时间是线性的，但是攻击者可以通过读写指针前进的频率来判断出哪些属性被保留哪些则被舍弃，所以本文差分不经意过滤算法的主要思想就是混淆每个指针的前进速度，使其刚好足以实现差分不经意 差分私有前缀和（Differentially Private prefix-sum） 对于一个只包含0和1的长度为 $ n $ 的数据流 $ D \in \{0, 1 \}^n $，它的前缀和 $ Y_c $ 代表在前 $ c $ 个元素中有多少个1出现。假设有一个 $ (\epsilon, \delta) $ - differentially private prefix sum 算法可以回答至多 $ n $ 个答案，每个答案 $ \widetilde{Y}_c $ 有很高的可能性在 $ \left[Y_c-s, Y_c+s\right] $。为了使写入指针的轨迹差分私有，我们可以将输出指针移动到 $ Y_c - s $，并将已经扫描还未输出的元祖储存在私有缓冲区中（enclave），只需要 $ 2s $ 大小的私有缓冲区就可以保证该算法只有很小的概率才会出错。本文使用 Chan 提出的二进制机制作为 DP 前缀和预言机，该机制本质上是建立一个二进制区间树来储存局部噪声和以实现最优近似隐私权衡。对每个 $ c \in [n] $，估计的前缀和 $ \widetilde{Y}_c $ 有 $ O\left(\epsilon^{-1} \cdot(\log T) \cdot \sqrt{\log t} \cdot \log (1 / \delta)\right. $ 的误差的概率至少为$ 1 - \delta $ 差分不经意过滤（Differentially Oblivious Filtering, DoFilter） 设 $ I $ 是长为 $ N $ 的输入表，$ s $ 为 DP 前缀和预言机的近似误差（每个查询的概率至少为 $ 1 - \delta $）。在私有内存中创建一个长度为 $ 2s $ 的缓冲区 $ P $，$ I \prime $ 为在虚拟内存外的输出表，和一个用于指示目前读取元组数目的计数器 $ c $。随后重复以下操作直至 $ I $ 结束： 读取接下来 $ s $ 个元组并更新计数器 $ c $ 对每个元组 $ t $，当谓词赋值为 TRUE 时将其推入 P 中 从 P 弹出元组直至输出表 $ I\prime $ 达到长度 $ \widetilde{Y}_c - s $ 当读到 $ I $ 的末尾后，将所有 $ P $ 中的元组弹出，并在 $ I \prime $ 上添加必要的填充元组直至其长度到达 $ \widetilde{Y}_N $，其中 $ N = \left| I \right| $ 该算法描述如下： 带聚合的分组（Grouping with Aggregation）$ (\gamma, \alpha) $ select count(*) from table_name group by grouping_attribute grouping 运算符对一个关系分组和/或聚合一些列，通常记为 $ \gamma_L(R) $，其中 $ L $ 为由分组属性（将要对 $ R $ 进行分组的 $ R $ 所拥有的属性）和应用于 $ R $ 的 aggragation 运算符（如 $ \gamma_{c_1, c_2, \alpha_1(c_3)} $ 将会将 $ R $ 根据属性 $ \{c_1, c_2\} $ 进行分组，并输出 $ \alpha_1 $ 应用于 $ c_3 $ 上的聚合值） 本文提出了一种基于分组属性随机划分的非不经意哈希分组算法，可以通过在分组属性 $ L $ 上应用伪随机函数（pseudorandom function, PRF）来实现。为了让每个分区都适应私有内存的大小（$ M $），本段应用了一种预处理步骤来获取正确的随机划分算法参数 $ s $，使用随机流不同计数算法（randomized streaming distinct count algorithm）来得到一个查询产生分组数的估计值 $ \widetilde{G} $，大约需要 $ k=\lceil\widetilde{G} / M\rceil $ 次扫描来找到所有的分组。 本文提出的差分隐私不同计数流算法（Differentially Private Distinct Count）如下（Algorithm 5）： 本文提出的差分不经意分组（Differentially Oblivious Grouping）算法如下（Algorithm 2）： 其中 $ I $ 是输入表，$ L $ 是由分组属性和聚合属性组合而成的列表。 外键连接（Foreign Key Join）$ (\bowtie) $ select * from table_1 join table_2 on table_1.primary_key = table_2.foreign_key; 使用 $ R \bowtie S^2 $ 来表示关系 $ R $ 的主键和 $ S $ 的外键上的一个连接。 典型的不经意连接算法有如下几个步骤： 填充：将两个表中的元组填充到相同的大小，并为每个元组添加一个“标记”列以标记该元组来自哪个表 排序：通过执行oblivious sort将来自两个表的元组路由到同一组 顺序扫描：通过对排序后的表进行顺序扫描来生成结果表 去除填充：最后，使用另一个oblivious sort去除所有填充元素 本文提出了差分不经意外键连接算法（Differentially Oblivious Foreign Key Join Algorithm）DoJoin，在 DoJoin 中，两个相邻数据集应该包含同一主键，并且它们的外键表具有相同长度的记录，但是其中有一条数据不同。DoJoin 从以下三个方面改进了典型的不经意连接算法： 使用更高效的桶不经意排序（$ O(nlogn) $）（Bucket Oblivious Sort）代替了 ObliDB 中使用的双调排序（$ O(nlog^2n) $）（Bitonic Sort） 移除了去除填充这一步（已在Algorithm 1中进行），只对输入进行一次排序 将输出中的填充元组填充到差分不经意性要求的大小，而不是更坏的情况，在实际中填充量可能很小 DoJoin 算法描述如下： 其中 $ R $ 为主键表，$ S $ 为外键表，$ k_R $ 是 $ R $ 的主键， $ k_S $ 是 $ S $ 中连接 $ R $ 的外键。DoJoin 算法首先将双方的元组填充到相同的大小，并在每个元组中添加一个标记列来表明它来自哪个关系。随后将得到的元组进行拼接，并将其先按键列再按标记列进行排序。对于有相同键的元组，来自 $ R $ 的元组总是先被读取。随后算法顺序扫描表，当扫描到一个元组时，如果它来自于关系$ R^\prime $ （填充后的 $ R $），则将其赋值给工作元组；如果它来自于关系$ S^\prime $ （填充后的 $ S $），则将其与工作元组进行连接操作，并将结果输出到结果集中。 差分私有区分计数（Differentially Private Distinct Count） 本章描述了一个基于差分隐私的分区计数算法，介绍了随机抽样的顺序统计量性质，$ (\epsilon, \delta) \text {-Sensitivity } $，并对其的进行了证明和分析，DISTINCT COUNT算法描述如下，DPDistinctCount 如上 Algorithm 5 所示： 性能评估 本章对 DO 运算符在 Big Data Benchmark 上进行了测试，并与 ObliDB 和 Spark SQL 进行了对比。隐私参数 $ eplsilon = 1 $，$ \delta = 2^{-30} $。 在 Benchmark #1: Selection with projection 中，相比没有加密的非不经意 spark SQL，有 7.8 - 26.0 倍的开销，开销主要来自于在 SGX enclave 内存中移动数据时的加密和解密；相比 ObliDB 有 1.5-3.7 倍的速度提升，这种性能增益来自更高效的算法和差分不经意性带来的更小的填充大小。 在 Benchmark #2: Grouping with aggregation 中，在中等数据集上（300k-300M）相比没有加密的非不经意 spark SQL，有 12.4 - 105.7 倍的开销；对于300K行的UserVisits表进行分组聚合，DO 运算符与 ObliDB 具有类似的性能，但 ObliDB 无法在3000万行的 User Visits 表上运行聚合分组。 在 Benchmark #3: Foreign Key Join 中，相比没有加密的非不经意 spark SQL，有 98.1 - 182.1 倍的开销，但相比 ObliDB 有 4.8-7.4 倍的速度提升。 下面是对 DO 运算符不同阶段耗时的拆分图，各部分说明如下： Encrypt：在 enclave 中加密 Decrypt：在 enclave 中解密 Read：将数据从不受信任的内存读入 enclave Write：将数据从 enclave 写入不受信任的内存 Compute：在 enclave 中计算
VLDB 23 OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization
摘要 本文引入了 OpBoost 框架，提出了三种在垂直联邦学习下的满足基于距离的 LDP（dLDP）的保序脱敏提升树算法用于对训练数据进行脱敏，优化了 dLDP 定义，并研究了有效的采样分布进一步提高了算法的精度和效率。 介绍 本章介绍了一些基础概念，如联邦学习，HFL，VFL，提升树等 提升树算法是一种流行的监督机器学习算法，有着高效性和可解释性的特点，被广泛应用于基于异构特征的预测任务中，但是当前现有的大多数提升树算法都是在集中式设置下提升的，直接访问整个数据集，在当前人们越来越注重隐私的环境下集中式的设置限制了提升树算法的广泛部署，所以设计一个使用的隐私保护VFL提升树算法成为一个重要问题。 本文贡献如下： 提出了新的隐私保护垂直联合提升树框架 OpBoost 设计了三种保序脱敏算法 优化 dLDP 定义 引入新的保序度量用于量化保序脱敏算法的隐私性，并使用此度量对 OpBoost 进行了综合评估 一些知识 基于距离的本地差分隐私（Distance-based Local Differential Privacy, dLDP） 对任意输入 $ x, x^\prime \in \mathbb{D} $ 和 $ \left| x - x^\prime \right| \leq t $，对所有 $ y \in \operatorname{Range} (\mathcal{M}) $ 有 $$ \operatorname{Pr}[\mathcal{M}(x)=y] \leq e^{t \epsilon} \cdot \operatorname{Pr}\left[\mathcal{M}\left(x^{\prime}\right)=y\right] $$ 保序脱敏算法（Order-Preserving Desensitization Algorithm） 保序脱敏算法（Order-Preserving Desensitization Algorithm） 令 $ X = x_1, x_2, \dots, x_n (\forall i.x_i \in \mathbb{N}) $ 为敏感序列，$ Y = y_1, y_2, \dots, y_n (\forall i.y_i \in \mathbb{N}) $ 为由脱敏算法 $ \mathcal{R} $ 生成的噪声序列。脱敏算法 $ \mathcal{R} $ 为保序的当且仅当 $$ \begin{aligned} & \forall i, j . x_i>x_j \Rightarrow y_i>y_j, \quad \text { and } \\ & \forall i, j \cdot y_i>y_j \Rightarrow x_i \geq x_j . \end{aligned} $$ 概率保序脱敏算法（Probabilistic Order-Preserving Desensitization Algorithm） 令 $ X = x_1, x_2, \dots, x_n (\forall i.x_i \in \mathbb{N}) $ 为敏感序列，$ Y = y_1, y_2, \dots, y_n (\forall i.y_i \in \mathbb{N}) $ 为由脱敏算法 $ \mathcal{R} $ 生成的噪声序列。脱敏算法 $ \mathcal{R} $ 为概率保序的当且仅当 $$ \forall i, j . x_i>x_j \Rightarrow \operatorname{Pr}\left[y_i>y_j\right] \geq \gamma(t) $$ 其中 $ \gamma(t) \in [0, 1] $，$ \left| x_i - x_j \right| \leq t $。在这里 $ \gamma(t) $ 是与 $ x_i $ 到 $ x_j $ 之间的距离有关的函数，当 $ \gamma(t) = 1 $ 时则为保序脱敏算法。 梯度提升树（Gradient Tree Boosting） GBDT (Gradient Boosting Decision Tree），中文名为梯度提升决策树，是一种基于决策树的增强学习算法，它被广泛地应用于回归、分类以及排序等问题。XGBoost 是一种 GBDT 的高效实现。 在梯度提升树的过程中，只有特征值的顺序是必要的。该算法（XGBoost）持续寻找分裂点并计算其增益。我们设 $ I_L $ 和 $ I_R $ 分别为样本集分裂（split）后的左右节点，$ g_i $ 和 $ h_i $ 为梯度，$ \lambda $ 和 $ \omega $ 为正则化参数，分裂的增益如下： $$ G_{split}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_L} g_i\right)^2}{\sum_{i \in I_L} h_i+\lambda}+\frac{\left(\sum_{i \in I_R} g_i\right)^2}{\sum_{i \in I_R} h_i+\lambda}-\frac{\left(\sum_{i \in I} g_i\right)^2}{\sum_{i \in I} h_i+\lambda}\right]-\omega $$ 计算 $ G_{split} $ 所需所有的变量都只能从特征值的顺序中推导出来。因此我们可以在不知道每个特征的确切值的情况下构建提升树。 系统概览 架构 在 OpBoost 中用户被分为两类： A方为持有训练样本标签的用户，在训练过程中A方充当中心服务器，与B方交换信息，进行模型训练。训练好的模型只存储在A方，A方负责利用其对新样本进行预测。 B方为仅持有样本若干特征的用户集合。B方作为客户端，通过与A方交换必要的信息来参与训练 执行流程 训练流程（Training Process） 首先B方在与A方交流前将本地特征脱敏： 特征值预处理 提升树算法会对具有自然排序的数值和分类特征进行不同的处理，通常采用 one-hot 编码，编码后可以使用 LDP 机制脱敏 用保序脱敏算法进行脱敏 用序号代替脱敏值后发送给A方 随后A方在收集B方的所有特征信息后找到特征上的最佳分割点（将序号记录为分割点） 最后A方将所有拆分点的序号发送给B方得到其脱敏值，并以此更新树模型 预测流程（Prediction） 在上述训练流程结束后，A方会得到一个完整的决策树模型，A方可以独立预测本地的新样本（非私有），也可以与B方合作预测新样本（私有）。所有新样本在脱敏或输入模型前都需要做与训练样本相同的处理。 特征值预处理算法（Pre-Processing for Feature Values） 该算法将所有不同特征的数值映射到一个统一的离散值域 上图是一些标志的定义，算法通过应设函数 $ \mathcal{B} $ 将离散数值映射到统一离散值域 $ \mathbb{D}_\perp $。设 $ \mathcal{X}_c \in \mathbb{D} $ 为一个特征的数值集合，B方将每个值 $ \mathcal{X}_c^i $ 做如下映射： $$ X_{i n t}^i=\left\lceil L+\frac{X_c^i-\text { lower }}{\text { upper-lower }} \cdot(R-L)\right\rceil $$ 其中 $ \operatorname{lower} $ 和 $ \operatorname{upper} $ 分别是 $ \mathbb{D} $ 的上下界，$ L $ 和 $ R $ 分别为 $ \mathbb{D}_\perp $ 的上下界。映射域 $ \mathbb{D}_\perp $ 越大，原始值的顺序就可以保留更多。将不同特征的值映射到统一值域中的原因是两个属性对于数值变化的敏感程度可能不同，所以需要将其映射到统一值域以方便评估脱敏化数据集的隐私性和效用性。 保序脱敏算法（Order-preserving Desensitization Algorithms） 该算法使用了 dLDP 机制实现保序脱敏，相比于 LDP 机制，dLDP 机制使得距离近的数据更难区分，而不是任意键值对之间。这使得以此训练出来的模型具有更高的准确性和更高的性能（LDP机制使得大量顺序信息丢失）。此算法有三个部分：Global-Map，Adj-Map 和 Local-Map。 Global-Map 算法描述如下 该算法建立在指数机制的变体上，根据一个效用函数为每个值分配输出概率。效用函数可以定义为该值域敏感值之间的距离，使得某个值可以以更高的概率脱敏得到更近的值。 Adj-Map 在经过分析过后发现在对有序数值进行脱敏时基于距离来分配在值域 $ \mathbb{D}_\perp $ 中映射其他值的概率更为合适。 但是现有的 dLDP 是基于 L1 距离，并且并未考虑数据分区的问题（数值可能相差很小但却在两个分区，例如血糖大于7mmol/l可能是糖尿病，6.9和7.1仅差0.2，但是和5.0和5.2之间的0.2完全不同，因为6.9和7.1跨越了数据的分区），于是本文扩展了 dLDP 的定义，增加了一个隐私预算参数，用两个参数来调整在不同分区和相同分区内的隐私等级。扩展后的 Partition-dLDP 定义如下： 一个算法 $ \mathcal{M} $，当且仅当其对所有的输入 $ x, x^\prime \in \mathbb{D}_\perp $，$ \left| x - x^\prime \right| \leq t $，$ \mathbb{D}_\perp $ 等分为若干长度为 $ \theta $ 的划分，对任何输出 $ y \in \operatorname{Range}(\mathcal{M}) $，有 $$ \operatorname{Pr}[\mathcal{M}(x)=y] \leq e^{\left\lceil\frac{t}{\theta}\right\rceil \epsilon_{\text {prt }}+\theta \epsilon_{n e r}} \cdot \operatorname{Pr}\left[\mathcal{M}\left(x^{\prime}\right)=y\right] $$ 当满足如下条件时： $$ \left\{\begin{array}{l} \epsilon_{p r t}=\theta \epsilon_{n e r} \\ \epsilon_{n e r}=\frac{\epsilon}{1+\theta /\left|D_{\perp}\right|} \end{array}\right. $$ Partition-dLDP 将退化为现有的 dLDP 定义 但是 Partition-dLDP 有个局限性就是他只能应用于均匀的划分（像是分数这种0-60不及格，60-80及格，80-100优秀的就是不均匀划分），而这也是未来可以拓展的方向 Adj-Map 算法描述如下 Adj-Map 算法首先以满足 $ \epsilon_{prt}-dLDP $ 的 Global-Map 为输出域随机选择一个分区作为输出域，随后利用满足 $ \epsilon{ner}-dLDP $ 的 Global-Map 将敏感值随机映射到该分区中的一个值 Local-Map 当 $ \epsilon_{prt} $ 增大时，敏感值可以以更大的概率映射到它所在的分区，当 $ \epsilon_{prt} = \infty $ 时，脱敏值的输出域从 $ \mathbb{D}_\perp $ 缩小到它所在的分区，因此不同分区的敏感值在脱敏后仍然保持着顺序。具体来说每个敏感值在其所在的分区通过满足 $ \epsilon_{ner}-dLDP $ 的 Global-Map 进行脱敏。划分的粒度越细，保留的顺序信息就越多。 使用有界离散拉普拉斯提高效率 由于指数机制下采样的计算复杂度和输出域的大小成正比，如果输出域较大的话采样过程就会变得很低效。并且指数机制要求输入/输出域的边界已知，在复杂场景下可能很难脱敏，如果输入域未知的情况下还要引入新的参数，这可能会对隐私有一定影响，会增加部署需求。 本章重点研究的是输入域未知或输出域较大的情况，使用有界离散拉普拉斯机制来替换指数机制。拉普拉斯分布支持无界的输入/输出采样，使得输入/输出域可以视为无穷大，下面是离散拉普拉斯分布的定义： 具有尺度参数 $ \lambda $ 的离散拉普拉斯分布记为 $ \operatorname{Lap}_{\mathbb{Z}}(\lambda) $，其中 $ \lambda = \frac{1}{\epsilon} $。其概率分布定义如下： $$ \forall z \in \mathbb{Z}, \operatorname{Pr}[Z=z]=\frac{e^{1 / \lambda}-1}{e^{1 / \lambda}+1} \cdot e^{-|z| / \lambda} $$ 由于拉普拉斯机制的输出域无界，所以就会出现值在期望输出域外的情况，对于这种情况进行重采样，重采样得到的有界离散拉普拉斯概率分布如下： 给定一个采样范围 $ [l, u] $，有界离散拉普拉斯概率分布为 $ \forall z \in[l, u], \operatorname{Pr}[Z=z]=\tau \cdot \frac{e^{1 / \lambda}-1}{e^{1 / \lambda}+1} \cdot e^{-|z| / \lambda} $，其中 $ \lambda = \frac{1}{\epsilon} $，有 $$ \tau= \begin{cases}\frac{2}{e^{u / \lambda}\left(1-e^{-(u-l+1) / \lambda}\right)}, & l<u<0 \\ \frac{2}{1-e^{-(-l+1) / \lambda}-e^{-(u+1) / \lambda}+e^{-1 / \lambda}}, & l<0<u \\ \frac{2}{e^{-l / \lambda}\left(1-e^{-(u-l+1) / \lambda}\right)}, & 0<l<u\end{cases} $$ 重采样的概率随着域的减小而增大，这会导致采样的耗时增加，而对于某些具有很强的侧信道攻击能力的敌手来说有可能从中可以得到一些信息，所以当输入输出域较小时建议使用指数机制。 理论分析 一个特征值的脱敏值在排序后没有跨越任何划分点 $ x^{\dagger} \in [L, R] $ 的概率至少为 $ \beta $，其中 $$ \beta=\sum_{k \in I_l} \sum_{x^{\dagger} \in[L, R]}\left(\mathcal{M}\left(k, x^{\dagger}\right) \cdot \prod_{j \neq k, j \in I_l} \sum_{x_l \in\left[L, x^{\dagger}\right]} \mathcal{M}\left(j, x_l\right) \cdot \prod_{j \in I_r} \sum_{x_r \in\left[x^{\dagger}+1, R\right]} \mathcal{M}\left(j, x_r\right)\right) $$ $ \beta $ 的值会受到特征值的分布和密度以及划分点的位置所影响。下图是本文的保序脱敏算法与 LDP 机制的比较： 可以看到，数据集的分布越集中或越密集，脱敏后无序值对的数量越高，也就降低了脱敏后值的效用程度。此外，可以看到 $ \beta $ 随着划分点接近特征值的中位数而减小。尽管许多因素对 $ \beta $ 的影响都比较大，但本文提出的算法总是优于 LDP 方法。 实验 本文在 Salaries 数据集下对 OpBoost 进行了评估。数据集和实验结果如下： 讨论 保序脱敏算法可以扩展到多特征值，利用组合定理将隐私预算分配给各个特征 对不关心不同分区中值的不可取分性的用户，Local-Map 是最佳选择 对没有额外领域知识，不追求高精度模型的用户，Global-Map 是最佳选择 对有额外领域知识和更高效用/精度追求的用户可以选择 Adj-Map，并自行设置 $ \alpha $ 和 $ \theta $ 只有当 $ \epsilon $ 很大时（如 $ \epsilon > 2.56 $），$ \alpha < 1 $ 才占优 由于在实际应用中 $ epsilon $ 通常小于1甚至0.1，所以用户可以将 $ \alpha $ 一直保持在大于1的值 当 $ \alpha $ 过大时对结果并没有太大改善，所以没有必要将 $ \alpha $ 设置得过大
VLDB 22 Privacy-preserving Cooperative Online Matching over Spatial Crowdsourcing Platforms
摘要 本文提出了一种名为隐私保护的协作在线匹配（Privacy-preserving Cooperative Online Matching(PCOM)）的框架，可以保护用户和工人在各自平台上的隐，并基于两种不同的隐私保护策略提出了两种不同的 PCOM 算法。 本文主要贡献如下： 制定了 PCOM，并提出了 PCOM 框架，在考虑敏感数据隐私的情况下将各平台收益最大化 证明了 PCOM 框架满足差分隐私性质，并提出了两种求解 PCOM 的算法 基于平台历史数据对请求的收益进行定价 综合考虑收益和请求被接受的概率进行定价 在真实和合成数据集上验证了算法的有效和高效性 问题说明 问题定义 请求（Request） 一个空间众包平台上的请求 $ r $ 定义如下：$ r = \langle t_r, l_r, d_r, \nu_r \rangle $，其中 $ t_r $ 为请求发出的时间，$ l_r $ 是在二维地图上请求发出的地点，$ d_r $ 是完成请求所需要的距离，$ \nu_r $ 是完成请求可以获得的收益 工人（Worker） 一个空间众包平台上的工人 $ w $ 定义如下：$ w = \langle t_w, l_w, rad_w \rangle $，其中 $ t_w $ 为工人出现的时间，$ l_w $ 为在二维地图上工人出现的地点，$ rad_w $ 为二维空间上工人服务的半径 本地/合作平台（Local/Cooperative Platform） 一个平台的描述如下：$ p = \langle R, W \rangle $，其中 $ R $ 是平台 $ p $ 上请求的集合，$ W $ 是在平台 $ p $ 上注册的工人集合。对于一个给定的请求 $ r $，请求发出的平台称为请求 $ r $ 的本地平台（Local Platform），相反，合作平台（Cooperative Platform）是合作中除了本地平台以外的任意平台。在本地平台上的工人称为本地工人（local worker），记为 $ w_{loc} $，在合作平台上的工人称为合作工人（cooperative worker），记为 $ w_{cop} $ 对外支付（Outer Payment） 当一个合作工人需要服务一个请求 $ r $，他想获得一笔报酬 $ \nu_r^\prime \in (0, \nu_r] $，其中 $ \nu_r^\prime $ 称为对外支付 收入（Revenue） 当请求 $ r $ 由本地工人服务时，平台将收到 $ \nu_r $ 的报酬，当请求 $ r $ 由合作工人服务时，平台将收到 $ \nu_{r_i} - \nu_{r_i}^\prime $ 的报酬。假设有一个可行匹配 $ M $，$ M_{loc} $ 为满足本地工人服务的匹配，$ M_{cop} $ 为满足合作工人服务的匹配，则平台的总收入定义如下： $$ \operatorname{Rev}=\sum_{i=1}^{\left|M_{l o c}\right|} v_{r_i}+\sum_{i=1}^{\left|M_{c o p}\right|}\left(v_{r_i}-v_{r_i}^{\prime}\right) $$ 隐私保护协作在线匹配（Privacy-preserving Cooperative Online Matching）（PCOM） 给定一组愿意参与合作的空间众包平台 $ P $，每个平台 $ p \in P $ 包含请求和工人，工人和请求依次出现。 PCOM 将为每个平台找到一个受益 $ Re\nu $ 最大的匹配结果 $ M $，并且满足以下约束： 时间约束：一个请求只能由发出之前就存在的工人来完成 1对1约束：一个请求同时只能由一个工人进行服务，反之亦然 不变约束：一旦某个工人被分配到某个请求，则该分配不可被更改或取消 范围约束：一个工人只能服务位置在服务半径内的请求 隐私约束：实时数据隐私（请求精确位置不应泄露给平台）和历史数据隐私（用户请求的出现、结束位置和时间不应泄露给合作平台） 评价准则 差分隐私（Differential Privacy） 地理不可分（Geo-indistinguishability） 假设 $ \mathcal{X} $ 是一个精确位置的集合，给定一个随机算法 $ A $，$ Range(A) $ 是可能报告的输出的集合，当对所有的 $ x, x^\prime \in \mathcal{X} $，$ z \in Range(A) $，$ d(x, x^\prime) \leq r $，有 $$ \operatorname{Pr}[A(x)=z] \leq e^{\varepsilon d\left(x, x^{\prime}\right)} \operatorname{Pr}\left[A\left(x^{\prime}\right)=z\right] $$ 则称 $ A $ 是 $ (\epsilon, r) - Geo-indistinguishability $ Geo-I 使得具有相同输出的两个输入位置不可取分 PCOM 问题框架 当一个请求 $ r $ 出现在本地平台 $ p_{loc} $ 后，$ p_{loc} $ 基于 $ r $ 的位置确定是否有本地工人。如果有，则通过如 TOTA 和 FTOA 这样的分配算法为请求分配一个合适的工人；如果没有，则进入协作处理，如下图： 协作处理有如下5个步骤： 为了保证隐私，本地平台（Platform A）根据 Geo-I 机制对 $ r $ 的位置进行扰动并将扰动后的请求发送给所有协作平台（Platform B, C） 每个协作平台根据请求 $ r $ 的位置和上面提到的约束条件寻找可用工人。有可用工人的平台将通过 $ \epsilon_2 - DP $ 估计 $ r $ 的对外支付（Outer Payment）$ \nu_r^\prime $，并将其发送给本地平台 当收到所有合作平台返回的外部支付后，选择 $ \nu_r^\prime $ 最小的一个进行合作（Platform B） 被选择的合作平台根据可用的合作工人的接受概率来选择要服务 $ r $ 的工人，接受概率可通过【ICDE 2020 Real Time Cross Online Matching in Spatial Crowdsourcing】中的方法进行计算，假设合作平台会告知它的工人此请求来自外部平台，合作工人有权拒绝服务 一旦有愿意服务 $ r $ 的合作工人出现，本地平台以精准位置释放 $ r $，随后合作工作者可验证 $ r $ 是否满足范围约束，如果满足，则服务 $ r $ ，否则拒绝 $ r $。如果成功服务，合作平台将收到 $ \nu_r^\prime $，本地平台将收到 $ \nu_r - \nu_r^\prime $ 该框架被证明为符合 $ \left(\left(\epsilon_1+\epsilon_2\right) * \max _{p \in P}\left|p_W\right|\right)-DP $，其中 $ \left|p_W\right| $ 为平台 $ p $ 的工人个数 Direct PCOM（D-PCOM）算法 D-PCOM 算法使用贪婪方式来解决 PCOM 问题。为了最大化本地平台收益，D-PCOM 算法会将请求优先发送给本地工人。算法描述如下： D-PCOM 也有两个缺点： 可能会分配过多的本地工人来执行价值较小的请求 在处理外部支付的过程中，D-PCOM 考虑了平台上所有工人的历史请求，但是忽略了可用工人对请求的偏好，因此对于全局计算的 $ \nu_r^\prime $，在一些单价较高的地区，可用工人接受请求的概率较小，在一些单价较低的地区可能出现 $ \nu_r^\prime > \nu_r $ 导致请求被拒绝 Selectable PCOM（S-PCOM）算法 为了克服 D-PCOM 的第一个缺点，S-PCOM 通过一个随机阈值来过滤请求，收入大于阈值的请求将基于本地匹配进行分配，小于的将基于合作匹配进行分配 为了克服 D-PCOM 的第二个缺点，在合作匹配过程中，S-PCOM 首先根据扰动过的地理位置寻找可用合作工人，并基于计算可用合作工人的接受概率计外部支付。合作平台的外部支付越高，则被本地平台选择的概率就越小。工人 $ w $ 的外部支付期望为 $$ \mathbb{E}\left(v_i, w\right)=v_i *\left(1-\operatorname{Pr}\left(v_i, w\right)\right) $$ 其中 $ \operatorname{Pr}\left(v_i, w\right) $ 为 $ w $ 想要以外部支付 $ w $ 来服务请求的概率。 S-PCOM 算法描述如下： 实验评估 上图为实验中用到的真实数据集，其中 $ R $ 为请求数，$ W $ 为工人数，$ rad $ 为工人的服务半径 上图为实验用到的合成数据集，随即从其他日期选择 500-50k 个请求和 100-10k 个工人，组成一个包含 1000-1000k 个请求和 200-20k 个工人的数据集。 本章将 D-PCOM，S-PCOM，没有合作的匹配算法 TOTA 和最新的 RamCOM 进行了对比 总收入 两种 PCOM 算法均增加了每日平均收入 服务请求数 D-PCOM 算法服务的请求数最大，因为它将每个可能的请求都分配给本地工人，而 S-PCOM 的请求数虽然小于 D-PCOM，但是其收入却高于 D-PCOM，因为 S-PCOM 偏向于更高价值的请求 合作请求数 因为 D-PCOM 算法优先考虑本地匹配，所以合作请求数小于 S-PCOM 算法，而 S-PCOM 算法又因为位置扰动导致合作请求数小于 RamCOM 接收率 D-PCOM 的接收率比 S-PCOM 小，这代表 S-PCOM 考虑工人偏好的策略是有效果的 上图是一些关于算法可扩展性的实验结果 实验结果表明位置的隐私水平对两种 PCOM 算法匹配的准确性和完整性有直接的影响，而定价的隐私水平影响不大。当合理选择隐私预算（$ \epsilon = 0.7 $）时，S-PCOM 的表现和最优合作匹配算法相当。 相关工作 空间众包匹配 激励机制问题 空间众包中的隐私保护任务分配 参考文献 Privacy-preserving cooperative online matching over spatial crowdsourcing platforms
VLDB22 Federated Matrix Factorization with Privacy Guarantee
摘要 本文主要研究了不同联邦学习环境下的矩阵分解（MF）问题，提出了一个通用的联邦矩阵分解（FMF）算法框架，系统地表征了垂直联邦学习（VFL）、水平联邦学习（HFL）和本地联邦学习（LFL）三种不同设置的数据采集、训练和发布阶段的隐私泄露风险，并引入隐私概念和一种新的被称为嵌入裁剪的私有学习技术以提供端到端的隐私保护。 介绍 本章主要介绍了一些联邦学习的概念和三种不同设置的联邦学习（VHL、HFL、LFL）所需要的不同的隐私边界设置。 本文的贡献如下： 提出了一个应用于三种设置的抽象的计算范式 针对不同的隐私泄露风险为不同的设置设计了不同的FL算法 提出使用嵌入裁剪（Embeddings Clipping）代替梯度裁剪（Gradient Clipping）来进行更新 提出了用于矩阵分解的 SGDMF 算法（包括 VFL-SGDMF、HFL-SGDMF、LFL-SGDMF） 背景 本章主要介绍了一些背景知识，如矩阵分解、差分隐私等 矩阵分解 矩阵分解问题可以形式化为如下最小化损失函数： $$ \mathcal{L}(X,U,V): \frac{1}{|\Omega|} \sum_{(i,j) \in \Omega} \mathcal{L}_{i,j}(X,U,V)=\frac{1}{|\Omega|} \sum_{(i,j) \in \Omega}(X_{ij}-\langle u_i,\nu_j \rangle)^2 $$ 差分隐私 Sequential composition: moments accountant $ M(X, aux) $ 表示 $ X $ 的输出，$ aux $ 为辅助输入，可包含前面步骤的所有中间结果 在 $ \lambda $ 处的矩生成函数（$ M $ 中的隐私损失）的对数定义如下： $$ \alpha_M(\lambda;X,X',aux) = logE_{o~M(X,aux)}[exp(\lambda log \frac{Pr[M(X,aux)=o]}{Pr[M(X',aux)=o]})] $$ 其中上界为 $ \alpha_M(\lambda) = max_{X,X',aux}\alpha_M(\lambda;X,X',aux) $，$ M_t $ 为适应性机制，使用 $ M_1 ~ M_{t-1} $ 和数据集 $ X $ 作为输入 Moments Accountant 将总体隐私损失限制在 $ M_1 $ 到 $ M_T $ 之间（通过 $ log $ 矩母函数） Moments Accountant 设机制 $ M $ 为一系列适应性机制 $ M_1,\dots,M_T $，则有 (1) 对任何 $ \lambda $，有 $ \alpha_M(\lambda) \leq \sum^{T}_{t=1}\alpha_{M_t}(\lambda) $ (2) 对任何 $ \epsilon > 0 $，机制 $ M $ 为 $ (\epsilon, \delta) $ - 差分隐私，$ \delta = min_{\lambda}exp(\alpha_M(\lambda)-\lambda_{\epsilon}) $ Parallel Composition 若 $ M_1, \dots, M_T $ 为 $ (\epsilon^{(1)}, \delta^{(1)}), \dots, (\epsilon^{(s)}, \delta^{(s)}) $ - 差分隐私，且他们都在不相交的数据集 $ X_1, \dots, X_s $ 上计算，则整体隐私损失为 $ (max_k\{\epsilon^{(k)}\}, max_k\{\delta^{(k)}\}) $ Per-rating Privacy 当有一索引 $ (i,j) $ 使得 $ X_{i,j} = \perp $ 且 $ X'_{i,j} \neq \perp $（或相反），且对任意 $ (i',j') \neq (i,j) $，有 $ X_{i',j'} = X_{i,j} $，则 $ X,X' $ 为相邻数据集 Per-rating Privacy 保护每个单独的由每个用户给出的评分 Bounding Sensitivity Sensitivity 指的是当数据有一条发生变化（增加/删除）时所产生的影响 Gradient Clipping 梯度裁剪可以用于 Bounding Sensitivity，但是在实际应用中有限制每个评分的效果和需要额外空间存储每个评分梯度的问题 Trimming 限制参与方 $ k $ 的最大评分数为 $ \theta^{(k)} $，并将剩余评分转换为 $ \perp $ 联邦矩阵分解 本章介绍了在三种不同设置（VFL、HFL、LFL）下的矩阵分解 垂直联邦学习（VFL）下的矩阵分解 User embeddings $ U = [u_i]_{i \in [n]} \in \mathbb{R}^{n \times p} $ Item embeddings $ V_{\mathbb{F}_k} = [\nu_i]_{j \in \mathbb{F}_k} \in \mathbb{R}^{m_k \times p} $ 对参与方 $ k $ 的损失函数：$ \mathcal{L}\left(\mathrm{X}_{\mathbb{F}_k}, U, V_{\mathbb{F}_k}\right)=\frac{1}{\left|\Omega_k\right|} \sum_{(i, j) \in \Omega_k}\left(\mathrm{X}_{i j}-\left\langle u_i, v_j\right\rangle\right)^2 $ 整体损失函数：$ \mathcal{L}(\mathrm{X}, U, V)=\sum_k \frac{\left|\Omega_k\right|}{|\Omega|} \mathcal{L}\left(\mathrm{X}_{\mathrm{F}_k}, U, V_{\mathrm{F}_k}\right)=$ $\frac{1}{|\Omega|} \sum_k \sum_{(i, j) \in \Omega_k}\left(\mathrm{X}_{i j}-\left\langle u_i, v_j\right\rangle\right)^2 $ User Embeddings：$ \nabla_U \mathcal{L}(\mathrm{X}, U, V)=\sum_k \frac{\left|\Omega_k\right|}{|\Omega|} \nabla_U \mathcal{L}\left(\mathrm{X}_{\mathbb{F}_k}, U, V_{\mathbb{F}_k}\right) $ Item Embeddings：$ \nabla_{V_{\mathbb{F}_k}} \mathcal{L}(\mathrm{X}, U, V)=\frac{\left|\Omega_k\right|}{|\Omega|} \nabla_{V_{\mathbb{F}_k}} \mathcal{L}\left(\mathrm{X}_{\mathbb{F}_k}, U, V_{\mathbb{F}_k}\right) $ User Embaddings 的归一化随机梯度：$ \mathrm{g}_U^{(k)}=\frac{1}{n^{\prime} m_k^{\prime} \tau} \sum_{(i, j) \in I_k} \nabla_U \mathcal{L}_{i, j}\left(\mathrm{X}_{\mathrm{F}_k}, U^{(k)}, V_{\mathrm{F}_k}\right) \approx \nabla_U \mathcal{L}\left(\mathrm{X}_{\mathrm{F}_k}, U, V_{\mathrm{F}_k}\right) $ Item Embaddings 的归一化随机梯度：$ \mathrm{g}_{V_{\mathrm{F}_k}}^{(k)}=\frac{1}{n^{\prime} m_k^{\prime} \tau} \sum_{(i, j) \in I_k} \nabla_{V_{\mathrm{F}_k}} \mathcal{L}_{i, j}\left(\mathrm{X}_{\mathrm{FF}_k}, U^{(k)}, V_{\mathrm{F}_k}\right) \approx \nabla_{V_{\mathrm{F}_k}} \mathcal{L}\left(\mathrm{X}_{\mathrm{F}_k}, U, V_{\mathrm{F}_k}\right) $ 水平联邦学习（HFL）下的矩阵分解 局部损失函数：$ \mathcal{L}\left(\mathbf{X}_{\mathbb{U}_k}, U_{\mathbb{U}_k}, V\right)=\frac{1}{\left|\Omega_k\right|} \sum_{(i, j) \in \Omega_k}\left(\mathbf{X}_{i j}-\left\langle u_i, v_j\right\rangle\right)^2 $ 全局损失函数：$ \mathcal{L}(\mathrm{X}, U, V)=\sum_k \frac{\left|\Omega_k\right|}{|\Omega|} \mathcal{L}\left(\mathrm{X}_{\mathbb{U}_k}, U_{\mathbb{U}_k}, V\right) $ 本地联邦学习（LFL）下的矩阵分解 LFL 是一种当 $ s = n, \mathbb{U}_i = \{i\} $ 时的 HFL 特例 MF 问题常用的 FL 范式 初始化和局部预计算 联合学习（需要通信） 局部微调 在 VFL 中，share embedding 是 user embedding，而在 HFL 中，share embedding 是 item embedding 在上述三个步骤中，步骤1、3可以在本地完成，而步骤2需要通信，更新步骤如下： VFL：$ U^{(k)} \leftarrow U^{(k)}-\gamma_t \mathrm{~g}_U^{(k)}, V_{\mathbb{F}_k} \leftarrow V_{\mathbb{F}_k}-\frac{\gamma_t m_k}{m} \mathbf{g}_{V_{\mathbb{F}_k}}^{(k)} $ HFL： $ U_{\mathbb{U}_k} \leftarrow U_{\mathbb{U}_k}-\frac{\gamma_t n_k}{n} \mathbf{g}_{U_{\mathbb{U}_k}}^{(k)}, V^{(k)} \leftarrow V_{\mathbb{F}_k}-\gamma_t \mathbf{g}_{V^{(k)}}^{(k)} $ 算法描述如下 Figure 3： 隐私垂直联邦学习矩阵分解 VFL-SGDMF Embedding Clipping 因为所有评分都在 $ [0,R] $ 的范围内（$ R $ 是一个有限的数字），所以 user embeddings 和 item embeddings 都被限制为非负的，所以在本文中对 user embeddings 和 item embeddings 施加了更强的约束如下： $$ \mathcal{U}: \forall i \in[n],\left\|u_i\right\|_2^2 \leq R, u_i \geq 0, \quad \mathcal{V}: \forall j \in[m],\left\|v_j\right\|_2^2 \leq R, v_j \geq 0 $$ Random Trimming 对每个参与方 $ k $，将其局部数据集中每个用户所拥有的评分数限制在 $ \theta^{(k)} $，并将其余评分转换为 $ \perp $ 隐私放大 通过使用 mini-batch 技术可实现隐私放大，对数据进行采样 隐私局部更新 为了保护中间和最终结果，$ U $ 和 $ V $ 都需要加入一个随机的噪声进行扰动，并且投影到上文 Embedding Clipping 中所提到的约束域 局部更新 U：$ U^{(k)}=\Pi_{\mathcal{U}}\left(U^{(k)}-\gamma_t \tilde{\mathrm{g}}_U^{(k)}\right) $ 局部更新 V：$ V_{\mathbb{F}_k}=\Pi_{\mathcal{V}}\left(V_{\mathbb{F}_k}-\frac{\gamma_t m_k}{m} \tilde{\mathrm{g}}_{V_{\mathbb{F}_k}}^{(k)}\right) $ 其中 $ \tilde{\mathrm{g}}_U^{(k)}=\mathrm{g}_U^{(k)}+\xi_U^{\left(k, t, t^{\prime}\right)} $，$ \tilde{\mathrm{g}}_{V_{\mathrm{F}_k}}^{(k)}=\mathrm{g}_{V_{\mathrm{F}_k}}^{(k)}+\xi_{V_{\mathrm{F}_k}}^{\left(k, t, t^{\prime}\right)} $，噪音 $ \xi_U^{\left(k, t, t^{\prime}\right)} $ 和 $ \xi_{V_{\mathbb{F}_k}}^{\left(k, t, t^{\prime}\right)} $ 的维度和梯度的，且对于每个局部更新，它们独立于零均值高斯分布进行采样，方差取决于隐私定义和隐私参数 VFL-SGDMF 局部微调 VFL-SGDMF 算法的收敛取决于两方面：DP 噪声和问题的非凸性 对最后的 $ \kappa $ 轮迭代，user embeddings 是固定的，各参与方只更新 item embeddings，最终每个参与方在训练时访问局部评分矩阵 $ TT\prime + \kappa $ 次。由于在最后的迭代中只有 item embeddings 发生变化，所以每次局部更新的敏感度较小。将问题转化为凸问题，每次更新的噪声更小，可以在训练中获得更小更稳定的损失。 隐私水平联邦学习矩阵分解 HFL-SGDMF 初始化和局部预计算 联合学习 每个参与方使用差分隐私保护更新本地 item embeddings：$ V^{(k)}=\Pi_{\mathcal{V}}\left(V^{(k)}-\gamma_t \tilde{\mathbf{g}}_V^{(k)}\right) $，其中 $ \tilde{\mathbf{g}}_V^{(k)} $ 是采样率为 $ \eta = \frac{n_k \prime}{n_k} $ 和固定 $ U_{\mathbb{U}_k} $ 的 item embeddings 的 mini-batch 的隐私梯度。 局部微调 跨设备学习：LFL-SGDMF 不同于 HFL，LFL 可能会面临用户设备不可用或用户设备与中心方之间的通信断开的情况，所以需要保证在训练过程中即使有大量用户在一次或多次迭代中退出的情况下 LFL 仍然可以可以保证隐私性。 LFL-SGDMF 改编自 FMF 算法，主要对第二步联合学习进行了修改，基本思想是在通过 SA（Secure Aggregation）聚合 item embeddings 的更新的同时保证聚合梯度满足 DP，同时引入尽可能小的噪声。 如果将 SA 看作一个预言机，则在每轮迭代中都会有两轮通信。 第一轮通信 协调服务器发起 $ SA_\omega $，并从各参与方请求更新。对每个参与方 $ i $ 进行一次采样 $ X_{ij} $，并报告更新噪声为 $ \tilde{\mathrm{g}}_V^{(i, t)}=\nabla_V \mathcal{L}_{i, j}\left(u_i, V^{(t)}\right)+\xi^{(i, t)} $，其中噪声 $ \xi^{(i, t)} $ 取样自高斯分布 $ \left(0, \zeta_1 \sigma_v^2\right) $。随后参与方调用预言机 $ \mathrm{SA}_\omega-\operatorname{report}\left(\tilde{\mathrm{g}}_V^{(i, t)}\right) $，服务器通过调用 $ SA_\omega-agg $ 对上报的更新进行聚合。本轮的幸存者集合记为 $ \mathbb{U}^{(t, 1)} $。若剩余用户量小于 $ (1 - \omega)n $，则 $ SA_\omega $ 中止，本轮没有学习到任何东西，反之由 $ SA_\omega $ 解码的聚合梯度可以被分解为 $ \tilde{\mathrm{g}}_V^{(t)} = \sum_{i \in \mathbb{U}^{(t, 1)}} \nabla_V \mathcal{L}_{i, j}\left(u_i, V^{(t)}\right)+\sum_{i \in \mathbb{U}^{(t, 1)}} \xi^{(i, t)} $ 第二轮通信 协调服务器首先向幸存者广播 $ |\mathbb{U}^{(t, 1)}| $ 并请求替换噪声。存活的参与方向协调服务器发送 $ \bar{\xi}^{(i, t)}=-\xi^{(i, t)}+\xi^{\prime(i, t)} $，其中 $ \xi^{\prime(i, t)} $ 取样自高斯分布 $ \left(0, \zeta_2 \sigma_v^2\right) $。用户退出也可能发生在第二轮，所以记第二轮的幸存者集合为 $ \mathbb{U}^{(t, 2)} $。服务器对替换噪声进行聚合，将两轮交换后的聚合噪声梯度分解为 $ \tilde{\mathrm{g}}_V^{(t)}=\sum_{i \in \mathbb{U}_t} \nabla_V \mathcal{L}_{i, j}\left(u_i, V^{(t)}\right)+\sum_{i \in \mathbb{U}^{(t, 1)}-\mathbb{U}^{(t, 2)}} \xi^{(i, t)}+\sum_{i \in \mathbb{U}^{(t, 2)}} \xi^{\prime(i, t)} $，协调服务器利用这些信息更新 item embeddings，并将更新后的值广播给各方。 LFL-SGDMF 对每个参与方的通信成本为 $ O(T(log n+mp)) $
VLDB 22 Hu-Fu: Efficient and Secure Spatial Queries over Data Federation
摘要 本篇文章提出了 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 进行了对比
SIGMOD 21 Secure Yannakakis: Join-Aggregate Queries over Private Data
摘要 本篇文章描述了一个安全版本的 Yannakakis 算法（用于计算自由连接聚合查询）。本协议可用于有两方参与的安全计算模型（2PC），对比当前最先进的基于混淆电路的协议有显著的提升。 1. 介绍 当前的许多框架如 SMCQL 等，它们的中间结果可能会过大，而如此大规模的电路（混淆电路）计算起来是非常耗时的，为了改进这一点，本文提出了 secure Yannakakis 协议。 如果一个协议要忽略输入数据，它的成本就不能依赖于输入，这意味着每个输入都应该产生与最坏情况输入相同的成本，而这使得所有基于成本的查询优化技术都不会起作用。本文作者提出应该寻找最坏情况下的有效算法，无论输入是什么，其成本都是有界的，而 Yannakakis 算法正式这样一种算法，这也是作者选择将 Yannakakis 移植到 SMC 下的原因。 将 Yannakakis 移植到 SMC 下有几个技术难点： Yannakakis 不是基于电路的算法，而且其重度依赖于哈希连接来实现最佳的 $ O(IN + OUT) $ 的时间复杂度。为解决次问题，文章设计了一个不基于电路的用于连接和半连接的协议，其成本与输入大小加输出大小呈线性关系 必须将不同关系的运算符的协议放在一起，并且中间结果不能泄露任何隐私信息。为了解决此问题，文章在设计半连接协议时使用了一种“电路友好”的最新的 PSI（Private Set Intersection，隐私集合求交）协议 最终，作者将秘密共享和不经意拓展置换作为“胶水”，将上述几个部分“粘”在一起，组成了 secure Yannakakis 协议。 2. 相关工作 本章介绍了前人的一些工作： 基于 Sharemind 实现的用于安全计算双向连接的不经意 AES 协议，但是此协议由于揭露了中间连接的大小而无法做到与其他运算符相结合 通过提供一个可信的第三方来进行计算（当前有许多硬件芯片如 Intel SGX 等可作为一个信任方），本文的协议是基于无信任参与方的，但是也可以将一些计算移动到信任方（如果有） 外源数据库如 CryptDB 和 Cipherbase 等，数据拥有者将数据加密后上传到外源数据库，外源数据库为数据拥有者提供 SQL 服务，但是这与 SMC 模型中大多数数据拥有者希望在不共享数据的情况下进行查询的想法不同 3. 附加说明关系的连接聚合查询 本章描述了查询定义和 Yannakakis 算法 将查询属性作为点，关系作为边，可将查询转换为一个超图，再将超图转换为连接树（连接树不是唯一的）（join tree）。上图是如下SQL查询 SELECT B, D, E, F, SUM(D+F*G) FROM R1 JOIN R2 JOIN R3 JOIN R4 JOIN R5 GROUP BY B, D, E, F 的连接树，其中有下划线的代表是要输出的属性（B，D，E，F），而 free-connex 是指所有的输出属性都在不输出属性的上方（parents）。如左边 (a) 树，未输出的属性 A 在输出的属性 B 和 D 的上方，所以这棵树就不是 free-connex 的，而 (b) 树中所有输出的属性都在未输出的属性上方，所以这棵树就是 free-connex 的。对于所有 free-connex 的连接树，Yannakakis 算法都可以做到 $ O(IN + OUT) $。 Yannakakis 算法 注意：Yannakakis 应用于 free-connex 的连接树（无环查询） 修改后的 Yannakakis 算法主要有以下三个步骤： 减少，通过将孩子投影到其父亲来消除不输出的属性，如上图中 (b) 树 可以将 R2 投影到 R1 来消除不输出的属性 C 半连接，当消除不输出属性后将孩子与父亲进行半连接来消除无用的行，如将 R1 与投影后的 R2 进行半连接，并用结果取代 R1，并删除 R2 全连接，当所有前置操作都结束后，从下至上进行全连接，并输出结果 Yannakakis 有两个阶段，一个是 semijoin 半连接，另一个是 join-aggregate 连接聚合阶段，而 Secure Yannakakis 将连接聚合阶段分为了减少阶段和全连接阶段，并将减少阶段置于半连接阶段之前，这并不会影响 Yannakakis 的正确性证明。 修改后的 Yannakakis 仍然是 $ O(IN + OUT) $ 的复杂度 4. 安全查询评估 本章主要讲述了 Secure Yannakakis 的安全性。 文章引入了真实-理想世界范式，在理想世界中，Alice 和 Bob 将他们的数据发送给受信任的第三方，第三方评估查询，并将结果返回给Alice（指定的接收者），Bob没有得到任何输出。；在现实世界中，他们遵循规定的协议来评估查询。一方的视图（在理想和现实世界中）由她/他在协议期间发送和接收的所有消息，加上她/他自己的输入和输出组成。如果对于现实世界中的任何输入和任何对手 A，存在一个模拟器，使得给定 A 的理想世界视图，模拟器可以产生一个与A的现实世界视图无法区分的视图，则该协议是安全的。 当参与双方的视图之间的统计距离小于 $ 2^{- \sigma} $ 时称他们是不可区分的（其中 $ \sigma $ 为安全参数） 对于计算不可区分性，文章将是视图输入到一个概率多项式时间的区分器，由它来试图决定这是个真实世界视图还是一个模拟视图，要求成功概率不超过 $ \frac{1}{2} + 2_{- \sigma} $，计算不可区分性通常基于对某些问题的严格假设，如伪随机函数、离散对数和整数分解。计算安全参数是指密码原语中用于实现计算不可区分性的密钥长度。 最后，协议也被允许失败，即它在没有计算正确输出的情况下终止。此概率也设置为 $ 2^{- \sigma} $ ，与违反安全性的概率相同。 5. 密码原语 本章主要讲述了 Secure Yannakakis 所使用的一些密码学技术（秘密共享，混淆电路，隐私集合求交（PSI），不经意扩展置换（OEP）和在秘密共享载荷上的隐私集合求交） 上述技术中 秘密共享 和 混淆电路 已做过笔记，在此处不再赘述 Secure Yannakakis 使用算数共享，布尔混淆电路，基于布谷鸟哈希和混淆电路的PSI协议和不经意扩展置换 6. Secure Yannakakis 本章主要讲述了 Secure Yannakakis 的具体实现。 Secure Yannakakis 中的 投影-聚合、半连接和连接协议必须满足以下要求： 每个输入关系由 Alice 或 Bob 拥有 输出关系由一方拥有，输出关系中的元组只能依赖于拥有方的输入关系和查询结果 输入输出关系的注释以秘密共享的形式由 Alice 和 Bob 持有 输出关系的大小仅取决于公开信息（输入关系大小和查询结果大小），而不是输入元组 每个输入和输出元组（及其注释）的访问模式无法区分 不经意投影-聚合协议 对于 $ \pi_{F}^{\oplus}(R) (select \oplus \quad (annotation) \quad group \quad by \quad F)$，Alice 先将 R 中的元组按照 F 进行排列，以保证相关的元组是相邻的，随后 Alice 和 Bob 使用不经意扩展置换来将分享的注释重新排序，这样能够让其与排序过的元组对应上，随后将其一个一个对应上即可。为保证这个算法是不经意的，使用混淆电路来进行实现。 对于 $ \pi_{F}^{1}(R) (\{ t \in R | \upsilon(t) \neq 0 \})$，因为不能够让 Alice 知道 $ \pi_{F}^{1}(R) $（它依赖于 R 的注释），所以作为替代向 Alice 发送一个语意上与 $ \pi_{F}^{1}(R) $ 相等的关系。输出包含所有在 $ \pi_{F}(R) $ 中的元组。对于在 $ \pi_{F}^{1}(R) $ 中的元组，他的注释会是 $ [\![1]\!] $，而对于其他的元组则是 $ [\![0]\!] $（ $ [\![x]\!] $ 代表秘密共享形式的 $ x $） 不经意半连接协议 Secure Yannakakis 拥有两种类型的半连接，一种是一个带注释的链接 $ R = R_{F} \bowtie^{\otimes} R_{F^{'}} $，另一种是 $ R = R_{F} \ltimes^{\otimes} R_{F_{'}} $ TODO: 补充实现步骤 不经意连接协议 本协议分为三步： 揭露 通过对悬垂和非悬垂元组注释的假设，我们可以知道有 $ R_{F}^{*} = \pi_{F}(\mathcal{J}^{*}) $（$ R^{*} $ 代表 $ R $ 中的所有注释不为 0 的元组集合），这代表了 $ R_{F}^{*} $ 是可以从 $ \mathcal{J}^{*} $ 派生出来的（但他的注释不能），所以可以被发送给 Alice。随后使用 $ |R_{F}| $ 混淆电路来检查对每个 $ t \in R_{F} $，是否有 $ \upsilon{t} = [\![\upsilon(t)]\!]_{1} + [\![\upsilon(t)]\!]_{2} = 0 $，如果结果为是，则返回一个假元组，否则返回 $ t $。如果 $ t $ 不是假的，则 Alice 将其放入 $ R_{F}^{*} $。运行和交流耗时为 $ O(IN) $ 连接 经过上一步骤，对于任意的关系 $ R_{F} $，Alice 都知道 $ R_{F}^{*} $。她可以在本地使用无注释的 Yannakakis 算法来计算连接 $ \mathcal{J}^{*} = \bowtie_{F \in \epsilon} $，并将结果 $ OUT = |\mathcal{J}^{*}| $ 发送给 Bob。Alice 可以向 $ \mathcal{J}^{*} $ 中加入假元组并在之后向 Bob 发送 $ \mathcal{J}^{*} $ 的大小来防止 Bob 知道 $ OUT $ 的确切值。这个步骤耗时为 $ O(IN + OUT) $，但交流耗时是一个常数 计算注释 设 $ t_{i} $ 为 $ \mathcal{J}^{*} $ 中的第 $ i $ 个元组，对每个关系 $ R_{F} $，Alice 定义一个扩展置换：$ \xi_{F}: [OUT] \rightarrow [|R_{F}|] $，其中 $ \xi_{F}(i) = index(\pi_{F}(t_{i}) \quad in \quad R_{F}, i \in [OUT]) $。随后 Alice 和 Bob 使用 OEP 将 $ R_{F} $ 的注释进行重新排序，他们就可以知道 $ \{[\![\upsilon(\pi_{F}(t_{i}))]\!]\} $，最后，对每个 $ t_{i} \in \mathcal{J_{*}} $。最终，他们使用混淆电路计算注释 $ [\![\upsilon(t_{i})]\!] = [\![\otimes_{F \in \epsilon} \upsilon(\pi_{F}(t_{i})) ]\!] $。此步骤耗时为 $ O(IN + OUT) $ Secure Yannakakis 算法 Secure Yannakakis 算法的描述如下： 减少阶段 在本步骤中，算法自下向上遍历连接树 $ \mathcal{T} $，同时当 $ F^{'} \subseteq F_{p} $ 时执行更新 $ R_{F_{p}} \leftarrow R_{F_{p}} $，而这可以进一步分解为两步：计算 $ \pi_{F^{'}}^{\oplus}(R_{F}) $ 和半连接，前者通过不经意投影-聚合协议计算，后者通过不经意半连接协议计算。协议智慧更改其注释，并不会修改 $ R_{F_{p}} $ 的大小。此阶段消耗为 $ O(IN) $。 半连接阶段 原始的 Yannakakis 算法通过两次半连接来删除所有的悬垂元组，但他不是不经意的。修改后的 Yannakakis 算法通过将它们的注释设为0来代替这个操作，可以通过不经意半连接协议进行计算。此阶段的消耗也是 $ O（IN）$。 全连接阶段 在前两个阶段后，只剩下输出属性，悬空元组的注释都是0。通过使用不经意连接协议可以计算出全连接的结果 $ \mathcal{J}^{*} $。因为 $ \mathcal{J}^{*} $ 的注释世界过的一部分，所以这些可以揭露给 Alice。此阶段的消耗为 $ O(IN + OUT) $ 优化 当一方拥有一个关系和其注释时 在这种情况下，带注释的投影聚合协议可以直接在本地计算。在不经意半连接协议中，当 Bob 知道所有自己所知道的关系的注释的时候，他们只需要带有有效负载的 PSI 协议，而不需要运行带有秘密共享的 PSI 协议。这种优化通常只在 Yannakakis 协议开始时有效，因为对于每个协议，输出关系的注释都将变成共享形式。 当一方拥有一个包含根节点的子树 假设 Alice 拥有包含根节点的子树。在 Yannakakis 算法自下向上的减少阶段中，对 Bob 的所有关系，全部计算都在本地完成，然后它们执行一些不经意半连接，其中 Bob 知道所有关于他所拥有的关系的注释，所以我们只需要使用带有有效负载的 PSI 协议。之后，即使注释是共享的，所有计算都是在 Alice 的关系上进行的。因此我们只需要简化的不经意半连接协议。在这种特殊类型的查询中，我们不需要使用带有秘密共享有效负载协议的PSI，因此可以提高效率。 7. 扩展 选择条件 假设此时对每一个关系 $ R_{F} $ 有一个条件限制 $ \phi_{F} $，对于不同的隐私要求，有以下几种选项： 条件的选择性不是私有的，则直接将 $ R_{F} $ 替换为 $ \sigma_{\phi_{F}}(R_{F}) $，这样可以降低一些算法的消耗 条件的选择性是私有的，则将所有不符合 $ \phi_{F} $ 的元组都替换为假元组后运行 Secure Yannakakis 算法 如果精确的选择性是私有的，但是可以透露一些上限，则可以将 $ R_{F} $ 替换为 $ \sigma_{\phi_{F}}(R_{F}) $，随后添加一些假元组。这在成本和隐私之间取得了很好的平衡 查询组合 有些聚合查询可能不是 free-connex 的，但是他们可以分解为两个或多个这样的查询。对此我们首先运行 Secure Yannakakis 算法的两个实例来计算每个类的共享形式的计数和总和。然后，我们为每个类使用混淆电路来计算平均值，并且只向 Alice 透露平均值。 针对查询结果保护隐私 根据本文定义的 2PC 模型，Alice 可以知道查询的结果，当查询结果是敏感的时候，可以使用拉普拉斯分布向结果中加入噪声，并通过混淆电路并入结果发送给 Alice。 8. 实验 经过试验可以发现 Secure Yannakakis 在速度上有着难以置信的提升，下面是一些图表 参考文献 Secure Yannakakis: Join-Aggregate Queries over Private Data 3448016.3452808.mp4
Eurosys 19 Conclave: secure multi-party computation on big data
摘要 当前的 MPC 算法在大数据上的速度非常的缓慢，而这导致了其在大数据上的应用进展也极其缓慢。许多关系分析查询可以保证 MPC 端到端的安全性，而不需要在所有运算上都使用 MPC。本文所介绍的 Conclave 是一个查询编译器，通过将此类查询转换为数据并行、本地明文处理和小型MPC步骤的组合来加速此类查询。当各参与方都信任彼此的数据集的时候，Conclave 会应用新的混合 MPC 清晰文本协议，在 MPC 之外运行其他步骤，并进一步提高可扩展性。 Conclave 的原型使用 Python 和 Spark 来生成明文代码，使用 Obliv-C 框架编写 MPC 相关的安全代码，并且表现大大优于最相似的系统 SMCQL 1. 介绍 本章主要介绍了 MPC 和 Conclave 的原理 Conclave 是本文提出的一个支持 MPC 查询的编译器，他可以使得 MPC 在大数据上高效地运行。 Conclave 有三个关键的想法。首先，Conclave 会分析查询来应用转换，可以在不损害安全的前提下减少运行的时间；其次，Conclave 在输入关系上使用了可选的，粗粒度的注解来应用新的混合协议，这个协议可以对纯文本和 MPC 进行比较，以获得进一步的加速，尤其是类似 joins 这种众所周知的在 MPC 下非常慢的操作；第三，Conclave 生成的代码将可扩展的、不安全的数据处理系统（如Spark）与安全但缓慢的 MPC 系统相结合。 本文的关键贡献有四点 查询分析技术，可以只通过粗粒度的注解得出在关系查询中哪些部分必须在 MPC 中运行 在保证安全的前提下将一些耗时的操作移出 MPC 在已有的相互信任的参与方之间使用新的MPC-明文混合协议来提升 MPC 中的 joins 和 aggregations 的性能 Conclave 原型使用 Python，Spark，Obliv-C 和 Sharemind 来生成高效的用于执行的代码 2. 背景 本文介绍了 MPC 在大数据中的应用，MPC 的安全保障和 MPC 相关的技术和扩展 Conclave 主要使用两种 MPC 技术，一种是混淆电路，另一种是秘密共享，这两种技术在博客中都有文章，不再赘述。 文章还提到了一点就是在实践中的可扩展性。上图在基于秘密共享（Sharemind）和混淆电路（Obliv-C）的MPC框架上对三种关系运算符与不安全明文执行的性能进行了测试评估并得出了以下结论：当前的MPC系统不太可能扩展到中等大小的数据集。特别是联接和聚合的性能较差：60%以上的隐私敏感分析查询使用联接，34%以上包含聚合。由于缺乏新的加密技术，因此在大数据上运行MPC的唯一方法可能是在不需要使用 MPC 的时候避免使用其加密技术。 3. 概述 本章介绍了 Conclave 的一些相关概念和实现。 威胁模型 Conclave 同 SMCQL 一样，是适用于半诚实模型的，要求参与方诚实地执行协议 安全保障和假设 Conclave 是一个为在外部 MPC 系统（后端）中的执行生成代码的查询编译器，所以 Conclave 继承了所使用的 MPC 后端的安全保证和假设，但也必须维护它们。Conclave 还特别隐藏了所有处理过的私有数据以及值频率等元数据。Conclave 针对其 MPC 后端可以容忍的串通敌对各方的相同阈值提供了这些保证。 与 MPC 论文一致，Conclave 将所有输入规模的大小视为 public，并隐藏在 MPC 下处理的中间关系的大小。但是，在 Conclave 重写查询以将操作移出 MPC 后，剩余 MPC 的输入大小可能与原始输入大小不同。根据查询，这可能会泄露信息。如果新的MPC输入关系的大小与数据无关，Conclave 的重写是安全的。对于依赖于数据的大小，Conclave 只有在所有受影响的各方都授权的情况下才会进行重写，否则选择较慢的查询计划。 同时，Conclave 提供的混合协议还可以用一部分安全性来换取性能的提升 4. Conclave 查询规范 Conclave 假设每一方都运行了： 一个本地Conclave代理，该代理与其他各方通信并管理本地和MPC作业 一个本地MPC端点（例如，Obliv-C 或 Sharemind 节点），所有这些都运行在私有基础设施上 可选的并行数据处理系统（例如，Spark），若没有并行数据处理系统，Conclave 将在Python中顺序运行本地计算。 Conclave 还拥有可选的信任方注解，一个参与方如果乐意将隐私数据透露给另一个信任的参与方就可以使用此注解（如银行机构将数据透露给政府监管机构，但不愿意将其泄露给其他竞争对手等），这种注解有助于 Conclave 减少高消耗的 MPC 步骤，从而提高速度。 5. 查询编译 Conclave 的编译阶段分为6步： Conclave 从一个复杂的大型 MPC 查询计划开始，首先将输入关系传到中间关系来确定数据在哪里跨越了各参与方的边界 Conclave 使用在第一步的得到的信息将查询重写为更少使用 MPC 的等价查询 Conclave 通过 DAG 来传播输入关系的信任注解，并根据推理规则将他们组合起来，以确定应该在何时可以将部分运算符放在 MPC 之外执行 随后 Conclave 在信任注解同意的情况下通过使用混合协议运算符替换一些可以在 MPC 之外运行的运算符来将巨大的内部 MPC 分为多个更小的 MPC 和一些本地步骤 如果有可能，Conclave 通过将一些高消耗的运算符（如排序等）移动到本地或用消耗更低的运算符代替来进一步减少高消耗的不经意协议的使用 最后，Conclave 通过在本地和 MPC 操作之间的每个转换处拆分DAG划分查询来为生成的子 DAG 生成代码，并在各自的后端执行它们。 注解传播 第一次传播以拓扑排序的方式沿着 DAG 从上往下传播，并以反向拓扑顺序遍历的方式将输出位置备份到图中。对于每个中间运算符，传播会派生其结果关系的所有者。如果一方能从其自己的数据导出一个关系，则称此方拥有这个关系。如果有多方拥有这个关系，则此关系没有拥有者，而没有拥有者的关系需要在 MPC 下运行。 第二次传播 Conclave 将会对每个中间关系的列确定一个信任集，如果一方被委托有足够的输入数据来计算该列，则该方被该中间结果列信任。传播这种信任的概念使 Conclave 在确保信息不会泄露给各方明确授权的信任方以外的参与方的同时使用混合协议来计算中间关系成为可能。 每个输入列的信任集合由信任注解来定义。Conclave 通过拓扑排序的方式在 DAG 中传播这些注解，对于每个运算符 $ o $ 的每个结果列 $ c $，Conclave 确定 $ o $ 的哪个操作数列有助于计算 $ c $。Conclave 将 $ c $ 的信任集设置为这些操作数列的信任集的交集。 这种传播算法有助于 Conclave 维护一个重要的安全不变原则：仅当列可从一方被授权的输入列派生的时候才会向另一方揭露此列。这可以保证 Conclave 使用混合协议是安全的。 寻找 MPC 边界 Conclave 从一个在单体巨大的 MPC 里的 DAG 开始计划查询，它可以将可以在 MPC 外本地明文运行的操作符取出，并将其他运算符分为本地预处理运算符和较小的 MPC 步骤。这个转换几乎对 Conclave 后端的安全保证性没有影响。 从输入关系开始，Conclave 将 MPC 边界沿着 DAG 向下推进，在保证正确性和安全性的同时尽量往下推进。当所有关系传播完毕后，每个关系要么是一个拥有唯一所有者的单例关系，要么是一个没有所有者的分区关系。在分区关系中，多方持有关系的一个子集（即分区）。Conclave 从每个单例输入关系中遍历 DAG，并从 MPC 中提取运算符，直到它遇到一个具有分区输出的运算符，它必须在 MPC 下处理该运算符。 查询通常会通过 concat 运算符将来自多方的输入合并到一个单独的分区关系中。这会创建一个“虚拟”输入关系，其中包含来自所有各方的数据，虽然这很方便，但是这回迫使 Conclave 过早的进入 MPC 中。为了避免这种情况的出现，Conclave 将 concat 运算符移动到任何分布在输入分区上的运算符下面，如对于运算符 $ op $ 和由 $ pA $ 到 $ pN $ 拥有的关系 $ R_{pA} $ 到 $ R_{pN} $，有 $$ op(R_{pA} | \dots | R_{pN} \equiv op(R_{pA}) | \dots | op(R_{pN})) $$ 虽然二级聚合必须在 MPC 下运行，但是 Conclave 可以将本地预聚合移出 MPC，并显著地减少输入到 MPC 的数据量。 在某些情况下，Conclave可以将 MPC 的边界从输出关系往上推动。有些运算符是可逆的（可从结果推出输入），对于这类运算符，结果就会泄露输入，所以这类运算符就不需要在 MPC 下执行。相反，Conclave 揭示了可逆运算符的输入与最终接收者的关系以进行本地明文乘法，即使输入具有不同的所有者。 安全影响 Conclave 在执行任何的 push-down 操作前都需要得到参与方的确认，因为此操作会改变输入到 MPC 后端的数据长度。 混合运算符 Conclave 将工作密集型运算符（如连接和聚合）分为多个混合运算符。Conclave 通过向 STP（selectively-trusted party，选择性信任方）揭露一些输入列来将一些高消耗的部分外包给其计算，因此混合运算符会涉及到 STP 的本地计算和 MPC 的多方计算。Conclave 只有在查询的信任注解中放松了输入列的隐私限制时才会应用此转换。Conclave 目前支持 hybrid join, public join 和 hybrid aggregation 三种混合运算符。 hybrid join 当双方数据有一个相交的信任集时（即共享一个STP），Conclave 可以将 MPC join 转换为 Hybrid join 协议如下处理： 参与方在 MPC 下输入关系 各方将除连接键列之外的所有列投影出去，并向STP显示生成的仅有键列的关系 对每一个键列关系，STP 枚举所有行，并为所有输入行分配一个唯一的标识符，Conclave 之后会用这个标识符来将聚合的结果链接回在秘密共享中的行 STP对枚举的键列关系执行明文连接 STP将左右关系的行标识符列投射为两个新关系，并秘密分享给不受信任的各方 各方对每个被打乱的输入关系执行一个类似 Laud 的不经意索引协议，对给定的秘密索引的集合，索引协议不经意选择在关系对应位置的列。通过使用索引关系和打乱的输入，各方选择包含结果的左右行，产生两个关系 left_rows 和 right_rows 双方将这两种关系连接起来，并将结果重新打乱 public join 如果 MPC 连接双方的连接键列都是 public（列的信任注解包括所有参与方） 的，则 Conclave 可以使用 public join。各方将连接键列发送给随机选择的一方；该方枚举并连接行，最后将连接的索引关系发送给各方，各方计算连接结果。 hybrid aggregation 如果在 group-by 列上的信任集包含一个 STP，Conclave 可以将 MPC aggregation 转为 hybrid aggregation 协议如下处理： 参与方不经意打乱输入并向 STP 揭露打乱过的 group-by 列 STP 在本地枚举被揭露的键，产生键列与索引列的关系，并在键列上对其进行排序 STP 扫描关系并为每一行都计算出一个等价的标志来表示此行的键是否与上一行相同 STP 从已排序的关系中将键列投影，只留下索引，并将此索引发送给其他参与方 STP 秘密共享等价标志 相互不信任的各方根据明文排序信息对打乱的关系行进行重新排序，这样行就以分组列的值为顺序排序了 在 MPC 中，各方对结果进行扫描。对于每个条目，如果相应的秘密等价标志是1就将之前的值聚合到当前的值中。各方也会储存秘密等价标志以便于进行最后的比较 各方打乱结果并揭露等价标志，并移除所有设置标志的条目 减少不经意操作 对于排序这种高消耗的 MPC 操作，Conclave 通过遍历 DAG 来查看有无冗余排序并消除他们。 6. 实现 Conclave 使用 Python 和 Spark 实现明文前端，使用 Obliv-C 和 Sharemind 实现 MPC 后端。 7. 评估 本章对 Conclave 进行了测试。 8. 相关工作 本章对之前的一些相关工作作了介绍，并将 Conclave 与之前已有的一些框架进行了对比。 混合模式下的 MPC 本段将 Conclave 与 Wysteria 进行了对比，相比于 Wysteria 的细粒度注释，对数据分析师有着更高的 MPC 知识要求，Conclave 的目标人群是不太具有 MPC 知识的数据分析师，并专注于自动化。Conclave 还支持在已有的框架中（如 Spark）进行明文并行计算 查询重写和 MPC 替代方案 本段将 Conclave 与 许多其他框架如 Kerschbaum、SMCQL、Opaque 等进行了对比。Conclave 与 SMCQL 相同，使用列层级的注解，但是 Conclave 的注解表现力更强，混合协议也允许额外的性能提升。 受保护的数据库和可扩展性 与之前数据库保护社区多年所研究的对单数据库的大数据量安全查询相反，Conclave 的应用场景是分布式的 推断和隐私 MPC 提供对运算中敏感状态的保护，但是不限制从输出中推断出敏感输入的可能性。之前的许多框架都利用了查分隐私（Different privacy, DP），Conclave 并没有使用 DP，但是添加它并不需要对查询编译做根本性的更改。 9. 总结和展望 Conclave 通过重写查询来减小在 MPC 中的高消耗操作来加速了在大数据上的安全多方计算。 参考文献 Eurosys 19 Conclave: secure multi-party computation on big data
VLDB17 SMCQL: Secure Querying for Federated Databases
摘要 在数据量不断膨胀的今天，但是因为隐私问题，在科学研究等方面的数据共享工作仍然进展缓慢。 本文提出了一种名为 PDN（Private Data Network）的用于多个互不信任的参与方之间的联邦数据库形式。在PDN中，用户将查询请求发送给一个名为诚实代理（Honest Broker）的中间人，由诚实代理通过SMC（Secure Multiparty Compute）协调各方进行计算并最终将结果返回给用户。 本文还提出了一个用于实现PDN的框架——SMCQL，SMCQL可以根据SQL语义将SQL语句转换为SMC原语，并且在不向同级别数据提供者揭露隐私信息的情况下完成查询。只有诚实代理和查询者可以获得PDN的查询结果。同时为了提高速度，SMCQL还使用了启发式算法优化了PDN对SMC的使用（SMC会消耗大量的资源） 1. 介绍 本章详细介绍了联邦数据库和PDN的工作方式，以及SMCQL的一些特性 用户向诚实代理提交查询，所有参与方根据诚实代理提供的安全协议进行计算，由诚实代理将多方的结果整合并返回给用户，从用户的角度看PDN与传统的数据库是完全一样的，提交查询，得到结果。 PDN使用SMC（Secure Multiparty Compute）完成多个不信任的参与方之间的计算和查询，因为SMC需要满足安全传输 ，所以他消耗的计算资源会非常的庞大，通常是明文查询的数倍。所以SMCQL通过将SQL语句转化为SMC原语，确定需要使用SMC的部分，并通过启发式算法优化，大大降低的SMC的使用，提高了计算速度。 SQMQL是适用于半诚实模型的数据库框架，它假设各参与方都诚实地执行诚实代理提供的安全协议，并使用了差分隐私通过在查询中注入噪声等来对个人信息进行保护以防有恶意查询者想要获取到隐私信息。在系统建立时，整个PDN会对表的内容进行统一定义，并且为不同的属性设定不同的安全级别，诚实代理会和所有参与者一起在安全的前提下完成这个表的链接。同时，各参与方可以制定一个策略用于定义其所允许执行的请求类型。 不同于采用同态加密的outsourced computation，PDN是将数据保留给其持有者，利用SMC来隐藏具体的计算过程而不是隐藏具体的数据。PDN将安全计算分摊给所有参与者，并只采用一个轻量级的诚实代理来协调请求处理过程。 本篇论文的主要贡献有如下几点： 一个用于有多个彼此不信任的数据提供商参与的联邦数据库（PDN） 一个可以将SQL语句转换为安全计算原语的生成器 基于启发式的PDN查询执行优化器 对该系统基于现实中的医疗数据进行了深入测试评估 2. 背景 本章主要介绍了SMCQL是如何实现SMC的。 SMCQL主要采用混淆电路（Garbled Circuits）和ORAM（Oblivious RAM）来实现SMC运算，主要是因为这两者都比较成熟，优化比较好。SMCQL利用混淆电路来计算在多方数据上的操作，利用ORAM来保护数据在执行者间的传输（在每次读写时都打乱包含数据的tuple，从而使得数据的访问细节对于被访问者来说是未知的）。SMCQL可以为每个数据库操作单独设计一个混淆电路，利用ORAM完成操作间的数据传递，从而避免了设计一个复杂的臃肿的大型混淆电路来执行一系列的操作。 3. 系统概述 本章主要介绍了SMCQL是如何将SQL语句转换为SMC原语的。 首先，诚实代理在收到查询的SQL语句后，首先将其转换为一个有向无环图（DAG），也就是语法树，诚实代理对其进行检查，以确保其在PDN的安全策略下是可以运行的。 诚实代理生成一个安全计划，标识语法树中的需要使用安全计算的最小子树，该安全计划是由诚实代理自下往上对树进行遍历，对敏感数据的数据流进行建模生成的 SMCQL使用启发式方法将该语法树优化为多个小的SMC单元，并对SMC的数量进行优化 诚实代理通过优化后的plan生成一系列的SMC代码用于协调各个参与者完成请求 每个参与者各自按照其自身的协议执行SQL请求，并在诚实代理提供的SMC代码下进行协作 当前该系统支持多种SQL操作，包括selection、projection、aggregation、limit、some window aggregates，对于join操作目前仅支持equi-join、theta-join、cross products。 4. 安全查询执行器 本章主要介绍了SMCQL是如何将PDN计划中的物理运算符转换为可执行的安全的代码 首先将一些组合多方数据的步骤加入计划中，随后对运算符树中所有的运算符生成一个安全的代码 安全代码使用混淆电路在多个参与方上联合计算，并将结果存入ORAM（Oblivious RAM）中。引擎使用这种安全的结构在操作符两边的节点间传递数据。 SMCQL使用ObliVM——一个拥有类似C语言语法的语言来创建混淆电路和ORAM。首先它将代码转换为一组逻辑门和ORAM的集合，然后在执行阶段再生成混淆电路。这个语言与底层的混淆电路协议相互解耦，使得使用不同的协议时对于编程者可以无缝切换。 每个操作在转换成安全代码时，都需要一个对应的模板函数，这个模板函数接受过滤器谓词（filter predicates）、输入的大小作为输入，其为一种操作定义了安全代码的具体工作流程。模板和逻辑门、ORAM共同构成了PDN的低级表示，并在执行阶段编译出混淆电路。 5. 安全模型 本章主要介绍了SMCQL面向用户提供的协议，同时还介绍了SMCQL的安全类型系统 面向用户的安全协议 SMCQL提供了以下三个数据保护级别： public：该数据对所有参与方都可见 protected：该数据仅对数据源，诚实代理和用户可见，使用k匿名（k-anonymity）来描述一个protected属性的安全度，指该属性的一条记录至少和k-1个记录不可区分。在这种情况下，用户和诚实代理是可以通过协调多个参与者来获取这些数据的。 private：该数据仅对数据源可见 隐私数据流 上图为安全系统的语法树，其中 phrase 可以是一个 expression、一个 set 或是一个 operator，expression 表示属性的引用、常量、算数与比较运算符、逻辑连接符，set 表示expression的集合，operator 表示以一个运算，输入一个 set，输出一个 set 该系统还定义了high和low两个安全级别，分别对应public和private类型（之后将protected视作private），一个expression是low的，当且仅当其中引用的所有属性都不是high的；一个set是low的，当且仅当其中所有的expression都是low的。 上图描述了operator中的low和high的定义。其中R-NEST描述了一个操作的安全等级应当高于其子结点；R-NEST-BIN针对二元操作，如果一个子结点的安全等级为high，则该结点也为high。 本文基于这套形式系统来描述其operator-tree的结构，并从而通过安全等级的传递来描述敏感数据在树结构中的流动。 SMC优化 本章主要介绍了对SMC的优化。 对于树上的每一个运算符都有以下三种执行模式： Plain：运算符被标记为低，并在源数据库中进行评估 Sliced：被标记为高的运算符安全地运行在由公共表达式水平分区的元组上。 Secure：被标记为高的运算符使用一个单独的SMC程序在所有的数据提供方上执行。 每个Sliced的operator在接受明文输入后，需要利用slice key对输入进行二进制化加密。具有相同slice key的不同值被独立计算。Slice 可以显著减少 SMC 的使用。 上图为SMCQL用于确定执行模式的算法。扫描从plain模式开始对树进行扫描，当碰到了高运算符时，引擎会切换为 sliced 或 secure 模式。如果运算符为 sliced 模式，则其祖先都要运行在 sliced/secure 模式中以保证数据安全。 比如COUNT(*)在涉及private attribute时，我们可将其分为两步，第一步在各个参与者中各自计算相应的数量，第二步利用SMC方法进行求和。可见第一步是low的，而第二步是high的，我们称这样的operator是splittable operator。每个splitable operator能够被分为两个安全等级不同的phrase，将其视作两个等级不同的子句而不是一个high的整体，能够进一步减小SMC开销。 再进一步，我们可以仅在涉及多方的情况下才使用SMC方法，称为semi-join。理由和上面的一样，我们可以将请求执行分为两个部分，在仅涉及自身一个参与者的情况下，可以采用明文计算而无需SMC方法；在涉及发送和传递数据时才使用SMC方法。 测试 本章对SMCQL的性能进行了测试。 其中 Baseline 对应所有属性都被视作 private 的，从而不进行任何优化；SMC Minimization对应通过分析high和low而减少了对于SMC的使用，包括splittable operators；Fully Optimized对应继续采用slice execution的方法进行优化，可以看到优化后的执行时间大大降低。 随后本文以recurrent c. diff场景为例，进一步测试了不同条件对于每个operator的性能影响： 同时本文还在comorbidity情景下使用不同的输入大小，测试了Secure状态和明文状态下的性能差异。本文将Secure在Scale增大时的性能降低主要归结于不经意传输时需要传输和打乱的数据的规模增大。 参考文献 VLDB17 SMCQL: Secure Querying for Federated Databases 21/7/11 读书笔记 smcql: Secure Querying for Federated Databases