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
读书笔记：Differential Privacy From Theory to Prictice（二）
理想与现实世界 (hypothetical world & real world) 在现实世界中，一个人的隐私不可能完完全全被保护好，因为一个人的数据不是孤立的，它总是会和其他的数据联系起来，而从这些联系我们就可以推测出其中的部分信息。差分隐私使用了理想-现实世界模型来对安全性进行评估和建模。 我们将敌手建模为一个决策函数，其输入为 $ \mathcal{A}(D) $，输出一个对所有可能的决策的选择 在现实世界中，我们有一条个人数据 $ \nu $，有一数据集 $ D $ 包括 $ \nu $，敌手做出决策 $ c $ 在理想世界中，$ \nu $ 的数据被彻底删除，没有这条数据，这条数据也就不可能泄露，这条数据也就得到了完美的保护。理想世界中的数据集记为 $ D_{-\nu} $ $ \epsilon - DP $ 保证对任意敌手，在理想和现实世界的决策差别不超过 $ e_\epsilon $（$ e^\epsilon-close $），其中 $ \lambda-close $ 的定义如下： 当两概率值 $ p $ 和 $ p^\prime $ 为 $ \lambda-close $ 时： $$ p \leq \lambda p^\prime \bigwedge p^\prime \leq \lambda p \bigwedge (1 - p) \leq \lambda (1 - p^\prime) \bigwedge (1 - p^\prime) \leq \lambda (1 - p) $$ 个人数据原则 (PDP) 数据隐私是指赋予个人对其数据的控制权。如果个人数据没有被使用，那么就不会违反个人隐私。隐私并不意味着不了解个人的任何信息，也不代表着对个人无害，强制执行后者是不可行和不合理的。 作为对 PDP 的另一种支持，一种常见的保护隐私的方式是“选择退出”，一旦个体“选择退出”，个体的数据被删除，个体的隐私就得到了保护。 当相邻数据集的定义不正确时 edge - DP 当两个图仅有一条边不同时，他们为相邻图 node - DP 当一个图删除一个点和所有与其相连的边得到另一个图时，他们为相邻图 当每个节点代表一个个体时，使用 edge - DP 是不正确的，因为去除一条边并不等于对个人数据的控制，并且去掉一条边的图并不能被认为是一个理想世界（并没有完全删除一个人的数据）。对匿名化图数据的攻击就是以重新识别节点的形式出现的，而这正证明了点才是应该关注的重点所在。 群体隐私 群体隐私是个人隐私的延伸，群体隐私所保护的利益是人们为了实现自己的目标而聚集在一起、交流信息、分享感情、制定计划、一致行动的愿望和需要。
计算平均数 我们假设有一个数据集，里面是1000个人的身高数据，我们想得到这个数据集的平均身高 我们使用 numpy 库来获取随机的拉普拉斯噪声，函数如下： import numpy as np def laplace(scale): """ 随机拉普拉斯噪声 """ return np.random.laplace(loc=0, scale=scale) 简单应用拉普拉斯机制（顺序组成） 由顺序组成性质我们可以有如下方法： def laplace_mechanism_composition(d: List[float], epsilon: float, a_max: float, a_min: float) -> float: """ s, c 符合 epsilon / 2 - DP, (s / c) 符合 epsilon - DP """ s = sum(d) + laplace(2 * (a_max - a_min) / epsilon) c = len(d) + laplace(2 / epsilon) if c <= 1: return (a_max + a_min) / 2 return round(s / c, 2) 一种使用真实计数的非隐私方法 这种方法使用了真实的数据集计数，但是因为其在重采样过程中对其他值的输出概率有着放大的作用，最终导致其不满足 $ \epsilon - DP $，同时，这种方法也引入了一种名为 clamping down 的方法来将输出限制在一个范围内 def non_private_with_true_count(d: List[float], epsilon: float, a_max: float, a_min: float) -> float: """ 只在数据和上添加拉普拉斯噪声，对不在 [a_min, a_max] 范围内的值进行重采样以保证输出固定在此范围内 但是重采样的过程对其他值有着放大输出概率的作用，所以不满足 epsilon - DP """ s = sum(d) c = len(d) if c == 0: return random.uniform(a_min, a_max) a = (s + laplace((a_max - a_min) / epsilon)) / c while a < a_min or a > a_max: a = (s + laplace((a_max - a_min) / epsilon)) / c return round(a, 2) 一种使用了真实计数和 clamping down 的隐私方法 不同于上一个方法，本方法采用了不同的 clamping down 策略，即 $$ \begin{equation} \label{eq6} \prod_\nolimits{[a_{min},a_{max}]}(y)=\left\{ \begin{aligned} & a_{min}, & y < a_{min}\\ & y, & a_{min} \leq y \leq a_{max} \\ & a_{max}, & y > a_{max} \end{aligned} \right. \end{equation} $$ 并且在数据集为空时应用指数机制，输出概率如下： $$ \begin{equation} \label{eq7} output=\left\{ \begin{aligned} & Pr[a_{min}] & = & \frac{1}{2}exp(-\frac{\epsilon}{2}) \\ & Pr[uniform(a_{min}, a_{max})] & = & 1 - exp(-\frac{\epsilon}{2}) \\ & Pr[a_{max}] & = & \frac{1}{2}exp(-\frac{\epsilon}{2}) \end{aligned} \right. \end{equation} $$ 代码如下 def clamping_down_with_true_count(d: List[float], epsilon: float, a_max: float, a_min: float) -> float: """ 不同于 non_private_with_true_count，采用了不同的 clamping down 策略， 即 when a < a_min, return a_min; when a > a_max, return a_max; else, return a 可以保证 epsilon - DP """ s = sum(d) c = len(d) if c == 0: return round( np.random.choice( [a_min, random.uniform(a_min, a_max), a_max], 1, p=[1 / 2 * (np.e ** (- epsilon / 2)), 1 - np.e ** (- epsilon / 2), 1 / 2 * (np.e ** (- epsilon / 2))] )[0], 2 ) a = (s + laplace((a_max - a_min) / epsilon)) / c if a < a_min: return a_min elif a > a_max: return a_max return round(a, 2) 使用归一化处理 对数据总和进行归一化处理，可以将全局敏感度从 $ a_max - a_min $ 降低到 $ \delta_a / 2 $ def noisy_average_with_normalization(d: List[float], epsilon: float, a_max: float, a_min: float) -> float: """ 对s进行归一化处理，可以将全局敏感度从 a_max - a_min 降低到 delta_a / 2 """ s = sum(d) - len(d) * ((a_max + a_min) / 2) + laplace(2 * (a_max - a_min) / epsilon) c = len(d) + laplace(2 / epsilon) if c <= 1: return (a_max + a_min) / 2 return round(s / c + (a_min + a_max) / 2, 2) 总结 经实际证明，[一种使用了真实计数和 clamping down 的隐私方法]()比[使用归一化处理]()表现更好，当 $ \epsilon $ 较大时它们表现相近，当 $ \epsilon $ 较小时前者的优势更为突出
读书笔记：Differential Privacy From Theory to Prictice（一）
差分隐私定义 当一个算法 $ \mathcal{A} $ 满足 $ \epsilon-DP(\epsilon > 0) $，当且仅当对任意两个仅相差一条数据的数据集 $ D $ 和 $ D \prime $，有 $$ \forall T \subseteq Range(\mathcal{A}): Pr[\mathcal{A}(D) \in T] = e^\epsilon Pr[\mathcal{A}(D \prime) \in T] $$ 其中 $ Range(\mathcal{A}) $ 表示算法 $ \mathcal{A} $ 所有可能的输出。上式也可等价写为如下形式： $$ \forall t \in Range(\mathcal{A}): \frac{Pr[\mathcal{A}(D) = t]}{Pr[\mathcal{A}(D \prime) = t]} \leq e^\epsilon $$ 相邻数据集 Neighboring Dataset 两个相差一条数据的数据集互为相互数据集。 对于相邻数据集： 如果它们包含的数据数量相同，其中一个数据集可以由另一个数据集替换一条数据得到，则它适用于 Bounded DP 如果它们包含的数据数量相差1，其中一个数据集可以由另一个数据集增加/减少一条数据得到，则它适用于 Unbounded DP 注意：所有满足 $ \epsilon-unbounded DP $ 的算法都满足 $ (2\epsilon)-bounded DP $，因为用一个元素替换另一个元素可以通过删除一个元素然后添加另一个元素来实现。 差分隐私的性质 后处理 Post Processing 对一符合 $ \epsilon-DP $ 的算法 $ \mathcal{A} $，对任意算法 $ \mathcal{B} $，$ \mathcal{B}(\mathcal{A}) $ 满足 $ \epsilon-DP $，即对数据进行后处理不会影响 DP 提供的隐私性。 顺序组成 Sequential Composition 有一符合 $ \epsilon_1-DP $ 的算法 $ \mathcal{A}_1 $ 和一符合 $ \epsilon_2-DP $ 的算法 $ \mathcal{A}_2 $，则 $ \mathcal{A} = \mathcal{A}_2(\mathcal{A_1(D)}, D) $ 符合 $ (\epsilon_1 + \epsilon_2)-DP $ 一般化表示形式如下：对满足 $ \epsilon_i-DP $ 的算法 $ \mathcal{A}_i $，有算法 $ t = \langle t_1, t_2, \dots, t_k \rangle $ 满足 $ (\sum_{i=1}^k \epsilon_i)-DP $，其中 $ t_1 = \mathcal{A}_1(D), t_1 = \mathcal{A}_2(t_1, D), \dots, t_k = \mathcal{A}_k(\langle t_1, t_2, \dots, t_{k - 1} \rangle, D) $ 平行组合 Parallel Composition 将数据集 $ D $ 分为 $ k $ 部分 $ D_1, D_2, \dots, D_k $，有算法 $ \mathcal{A}_i $ 符合 $ \epsilon_i-DP $，则 $ \mathcal{A}_1(D_k), \mathcal{A}_2(D_k), \dots, \mathcal{A}_k(D_k) $ 符合 $ max_{i \in [1, \dots, k]}(\epsilon_i)-DP $ 注意：在 bounded DP 下，平行组合不成立 凸度 Convexity 有 $ k $ 个符合 $ \epsilon-DP $ 的机制，取 $ p_1, p_2, \dots, p_k \in [0, 1] $，且 $ \sum_{i=1}^k p_i = 1 $，则有机制 $ \mathcal{A} = p_1 \mathcal{A_1} + p_2 \mathcal{A_2} + \dots + p_k \mathcal{A_k} $ 符合 $ \epsilon-DP $ 拉普拉斯机制 Laplace Mechanism 全局敏感度 Global sensitivity 我们使用 $ D \simeq D^\prime $ 来表示 $ D $ 和 $ D^\prime $ 为相似数据集，$ \Delta_f $ 表示函数 $ f $ 的全局敏感度，则标量的全局敏感度 $ \Delta_f=\max _{D \simeq D^{\prime}}\left|f(D)-f\left(D^{\prime}\right)\right| $，向量的全局敏感度为 $ \Delta_f=\max _{D \simeq D^{\prime}}\left\|f(D)-f\left(D^{\prime}\right)\right\|_1 $ 标量形式 要让一个输出标量的函数 $ f $ 符合 $ \epsilon-DP $，我们可以设一个函数 $ \tilde{f}(D) = f(D) + X $，其中 $ X $ 为一个从某分布随机取到的值，对于 $ X $ 所属分布，我们需要他的均值为 0，这样 $ \tilde{f}(D) $ 就是 $ f(D) $ 的无偏估计了，同时我们还需要满足： $$ \forall t, \frac{\operatorname{Pr}[\tilde{f}(D)=t]}{\operatorname{Pr}\left[\tilde{f}\left(D^{\prime}\right)=t\right]}=\frac{\operatorname{Pr}[f(D)+X=t]}{\operatorname{Pr}\left[f\left(D^{\prime}\right)+X^{\prime}=t\right]}=\frac{\operatorname{Pr}[X=t-f(D)]}{\operatorname{Pr}\left[X^{\prime}=t-f\left(D^{\prime}\right)\right]} \leq e^\epsilon $$ 其中 $ X $ 和 $ X \prime $ 都来自同一分布。 我们设 $ d = f(D) - \tilde{f}(D \prime) $，我们需要保证 $ \forall x, \frac{\operatorname{Pr}[X=x]}{\operatorname{Pr}\left[X^{\prime}=x+d\right]} \leq e^\epsilon $，并确保 $ \forall d \leq \Delta_f $，也就是说噪声所属的分布应当满足如下性质：如果在 x 轴上移动不超过 $ \Delta_f $ 个单位，概率的变化应该不超过 $ e_\epsilon $，即如果在 x 轴上移动不超过一个单位，则概率的变化不应超过 $ e^\frac{\epsilon}{\Delta_f} $ 满足上述要求的分布为拉普拉斯分布 $ Lap(\frac{\Delta_f}{\epsilon}) $，$ Pr[Lap(\beta) = x] = \frac{1}{2\beta}e^{-\frac{|x|}{\beta}} $，$ \frac{\operatorname{Pr}[\operatorname{Lap}(\beta)=x]}{\operatorname{Pr}[\operatorname{Lap}(\beta)=x+d]} \leq e^{d / \beta} \leq e^{\Delta_f / \beta}=e^\epsilon $ 对所有函数 $ f $，有拉普拉斯机制 $ \mathcal{A}_f(D) = f(D) + Lap(\frac{\Delta_f}{\epsilon}) $ 符合 $ \epsilon-DP $ 向量形式 对所有函数 $ f $，有拉普拉斯机制 $ \mathcal{A}_f(D) = f(D) + \langle X_1, X_2, \dots, X_k \rangle) $ 符合 $ \epsilon-DP $，其中 $ X_1, X_2, \dots, X_k $ 取自 $ Lap(\frac{\Delta_f}{\epsilon}) $ 指数机制 Exponential Mechanism 拉普拉斯机制只适用于数值输出，并不适用于非数值输出（如分类等），而指数机制都适用 设 $ O $ 为包含所有可能输出的集合，在 $ O $ 中的一些值会比其他值更可取（如想输出出现次数最多的项则它比其他的输出更可取），我们使用效用函数（quality function） $ q: (\mathbb(D) \times O) \rightarrow \mathbb{R} $ 来衡量一个值的重要性，其中 $ \mathbb{D} $ 表示所有数据集的集合，$ \mathbb{R} $ 为实数集。 对任何效用函数 $ q: (\mathbb(D) \times O) \rightarrow \mathbb{R} $，指数机制 $ \mathcal{M}^\epsilon_q(D) $ 的输出 $ o \in O $ 与 $ exp(\frac{\epsilon q(D, o)}{2\Delta_q}) $ 成正比，其中 $ \Delta q=\max _{\forall o, D \simeq D^{\prime}}\left|q(D, o)-q\left(D^{\prime}, o\right)\right| $ 为函数 $ q $ 的敏感性。即 $$ \operatorname{Pr}\left[\mathcal{M}_q^\epsilon(D)=o\right]=\frac{\exp \left(\frac{\epsilon q(D, o)}{2 \Delta q}\right)}{\sum_{o^{\prime} \in O} \exp \left(\frac{\epsilon q\left(D, o^{\prime}\right)}{2 \Delta q}\right)} $$ （效用函数）单调情形 一般当效用函数是基于满足某种条件的记录数进行计数时，就会出现效用函数是单调函数的情况。在这种情况下，指数机制的输出不再与 $ exp(\frac{\epsilon q(D, o)}{2\Delta_q}) $ 成正比，而是和 $ exp(\frac{\epsilon q(D, o)}{\Delta_q}) $ 成正比。
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)) $
隐私保护算法：K-Anonymity、L-Diversity 和 T-Closeness
背景 未经脱敏的数据在公布后可能会被一些攻击者逆向得到用户的隐私信息，所以在发布前进行数据脱敏是很有必要的，而简单的脱敏并不能阻止攻击者获取隐私信息 如上表，医院发布的数据（Hospital Patient Data）中已经抹去了姓名、身份证号等信息，但是攻击者如果知道上面的投票表（Voter Registration Data）就可以通过生日（Birthdate）、性别（Sex）和邮编（ZIPcode）来推测出 Andre 患有流感（Flu），这被称作连接攻击，通过某些属性与外部表进行连接获取隐私数据 K-Anonymity（K-匿名） 为了解决上述连接攻击的情况，K-匿名应运而生。K-匿名的基本思想是对同一个准标识符（可以和外部表链接来识别个体的最小属性集，如上述例子中的 { 生日，性别，邮编 } ）至少要有 $ k $ 条记录，这样攻击者就不能通过连接来获取隐私信息了。 Table 1. Original Patients Table Table 2. A 3-Anonymous Version of Table 1 我们可以看到，在经过K-匿名处理后（例子中为3-匿名）已经不能通过连接攻击来获得用户隐私了，因为连接后有多个结果，攻击者不能确定唯一的一条结果。 但是K-匿名也有缺点，如 Table 2 所示，脱敏处理后的数据出现了相同项，也就是说，只要攻击者知道表中某一用户的邮编以 476** 开头，并且年龄在20多岁，就可以确定他患有心脏病（Heart Disease），这被称为同质化攻击。同时，如果攻击者知道一些关于用户的背景也有可能能获取到隐私，加入攻击者知道 A 的邮编为 476**，年龄为30多岁，并且患心脏病的概率很低，那么从 Table 2 的 789 列就可以推测出 A 患了癌症（Cancer），而这被称为背景攻击 L-Diversity（L-多样性） 为了解决K-匿名无法防范同质化攻击和背景攻击的情况，L-多样性出现了。-多样性在K-匿名的基础上对每个等价类都保证敏感属性至少有 $ l $ 个取值，使得攻击者最多以 $ \frac{1}{L} $ 的概率确认某个体的敏感信息，如下图就满足 3-diversity l-diversity 有多种表示方法： 可区分良表示（Distinct l-diversity）：同一等价类中敏感属性至少有 $ l $ 个可区分的取值， 但是如果某一个值的频率明显高于其他取值则可能让观察者以较高的置信度认为此等价类中的敏感属性都是这个值 熵良表示（Entropy l-diversity）：记 $ S $ 为敏感属性的取值集合，$ p(E, s) $ 为等价类 $ E $ 中敏感属性取值 $ s $ 的概率，Entropy l-diversity 要求 $ Entropy(E) = -\sum_{s \in S}logp(E, s) \geq log l $ 递归良表示（Recursive(c, l)-Diversity）：如果等价类的敏感属性有 $ m $ 中取值，记 $ r_i $ 为出现次数第 $ i $ 多的取值的频次，如果等价类满足 $ r_1 < c(r_l + r_{l+1} + \dots + r_m) $，责成等价类具有 Recursive(c, l)-diversity L-Diversity 也有一些缺点，一方面，L-Diversity 可能难以实现且没有必要实现，另一方面，我们考虑疾病检验报告的例子，我们假设整体阳性率为1%，一种情况是一个等价类里恰好有一半阳性，一半阴性，此时相比整体1%阳性的概率，该等价类中每个个体都有 $ \frac{1}{2} $ 的概率被认为是阳性。再考虑另一种情况，49个阳性和1个阴性，在该等价类中每个个体都有98%的概率被认为是阳性，远高于整体的1%，而这两种情况都代表了一种很严重的隐私风险，这种攻击被称为偏斜攻击（Skewness Attack）。另外一种对 l-diversity 有影响的攻击是相似度攻击（Similarity Attack），如果敏感属性是工资，在某一等价类中的取值都在 3k-5k 之间，那么观察者只要知道用户在这一等价类中就可以知道其工资处于较低水平，而具体数值观察者并不关心。 T-Closeness（T-相近） T-相近是L-多样性的进一步细化。T-相近要求每个K-匿名组中敏感属性值的统计分布与该属性在整个数据集中的总体分布“接近”。 我们假设观察者对个体的敏感看法有一先验看法 $ B_0 $，给观察者一个抹去准标识符信息的数据表，其中敏感属性的分布为 $ Q $，根据 $ Q $，观察者的先验概率变成 $ B_1 $。最后，发布含有准标识符信息的数据表，个体所在等价类的敏感属性的分布为 $ P $，则根据 $ P $，观察者的看法变为 $ B_2 $。 L-Diversity 的思想是限制 $ B_0 $ 和 $ B_2 $ 之间的差异，而 T-Closeness 的思想是限制 $ B_1 $ 和 $ B_2 $ 之间的差异。T-Closeness 通过限制 $ P $ 和 $ Q $ 之间的距离来限制从 $B_1$ 到 $ B_2 $ 的增益。直觉上来说，如果$ P = Q $，那么 $ B_1 $ 和 $ B_2 $ 应该是相同的。如果 $ P $ 和 $ Q $ 很接近，那么 $ B_1 $ 和 $ B_2 $ 也应该很接近，即使可能与 $ B_0 $ 有很大不同。若一个等价类的敏感属性取值分布与整张表中该敏感属性的取值分布的距离不超过阈值t，则称该等价类具有t-相近性。若一个表中所有等价类都有t-相近性，则该表也有t-相近性。 对于 $ P $ 和 $ Q $ 之间的距离，$ P $、$ Q $ 为两个概率分布 $ P = (p_1, p_2, \dots, p_m) $ 和 $ Q = (q_1, q_2, \dots, q_m) $，众所周知的变量距离公式是 $ D[P,Q] = \sum_{i=1}^{m}\frac{1}{2}|p_i - q_i| $，然而这个公式并不能反映值之间的语义距离。所以我们使用 EMD（Earth Mover's Distance，陆地移动距离）来衡量他们之间的距离。我们设 $ r_i = p_i - q_i $，EMD 可以如下计算：$ D[P, Q] = \frac{1}{m - 1}(|r_1| + |r_1 + r_2| + \dots + |r_1 + r_2 + \dots + r_{m - 1}|) = \frac{1}{m-1}\sum_{i=1}^{m}|\sum_{j=1}^{i}r_j| $ T-相近性可以防止属性泄露，但是不能防止身份泄露，所以有时候可能同时需要K-匿名与T-相近性。此外，T-相近性对于针对K-匿名算法的同质化攻击和背景攻击并不能保证永远不会发生，而是保证了如果这类攻击发生在了此类表中，那么即使使用完全广义的表也能发生相似的攻击。所以如果要发布数据，使用T-相近性进行脱敏是最好的。 参考文献 Li, N.; Li, T.; Venkatasubramanian, S. t-closeness: Privacy beyond k-anonymity and l-diversity. In Proceedings of the IEEE International Conference on Data Engineering, Istanbul, Turkey, 15–20 April 2007;
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 进行了对比