SAGIRI'S BLOG
type: channel
link: http://blog.sagiri.tech/
description: Your description here.
items: MDM 2021 A Differentially Private Task Planning Framework for Spatial Crowdsourcing
items: VLDB 22 Adore: Differentially Oblivious Relational Database Operators
items: VLDB 23 OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization
items: VLDB 22 Privacy-preserving Cooperative Online Matching over Spatial Crowdsourcing Platforms
items: 读书笔记：Differential Privacy From Theory to Prictice（二）
items: 一些差分隐私的代码练习
items: 读书笔记：Differential Privacy From Theory to Prictice（一）
items: VLDB22 Federated Matrix Factorization with Privacy Guarantee
items: 隐私保护算法：K-Anonymity、L-Diversity 和 T-Closeness
items: VLDB 22 Hu-Fu: Efficient and Secure Spatial Queries over Data Federation

MDM 2021 A Differentially Private Task Planning Framework for Spatial Crowdsourcing
type: item
date: 2023-05-15T14:58:00+08:00
description: 摘要 本篇文章定义了隐私保护任务规划（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} $ 和 $…

VLDB 22 Adore: Differentially Oblivious Relational Database Operators
type: item
date: 2023-05-07T20:13:00+08:00
description: 摘要 本篇论文提出了 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,…

VLDB 23 OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization
type: item
date: 2023-03-26T21:38:00+08:00
description: 摘要 本文引入了 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}=…

VLDB 22 Privacy-preserving Cooperative Online Matching over Spatial Crowdsourcing Platforms
type: item
date: 2023-02-24T21:38:08+08:00
description: 摘要 本文提出了一种名为隐私保护的协作在线匹配（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(…

读书笔记：Differential Privacy From Theory to Prictice（二）
type: item
date: 2023-02-20T14:17:50+08:00
description: 理想与现实世界 (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 是不正确的，因为去除一条边并不等于对个人数据的控制，并且去掉一条边的图并不能被认为是一个理想世界（并没有完全删除一个人的数据）。对匿名化图数据的攻击就是以重新识别节点的形式出现的，而这正证明了点才是应该关注的重点所在。 群体隐私 群体隐私是个人隐私的延伸，群体隐私所保护的利益是人们为了实现自己的目标而聚集在一起、交流信息、分享感情、制定计划、一致行动的愿望和需要。

一些差分隐私的代码练习
type: item
date: 2023-02-07T16:36:00+08:00
description: 计算平均数 我们假设有一个数据集，里面是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 rou…

读书笔记：Differential Privacy From Theory to Prictice（一）
type: item
date: 2023-01-10T00:16:00+08:00
description: 差分隐私定义 当一个算法 $ \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^{\prim…

VLDB22 Federated Matrix Factorization with Privacy Guarantee
type: item
date: 2023-01-03T23:43:00+08:00
description: 摘要 本文主要研究了不同联邦学习环境下的矩阵分解（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 $ 联邦矩阵分解 本章介绍了在三…

隐私保护算法：K-Anonymity、L-Diversity 和 T-Closeness
type: item
date: 2022-11-27T21:50:00+08:00
description: 背景 未经脱敏的数据在公布后可能会被一些攻击者逆向得到用户的隐私信息，所以在发布前进行数据脱敏是很有必要的，而简单的脱敏并不能阻止攻击者获取隐私信息 如上表，医院发布的数据（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 …

VLDB 22 Hu-Fu: Efficient and Secure Spatial Queries over Data Federation
type: item
date: 2022-11-21T15:31:53+08:00
description: 摘要 本篇文章提出了 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}^…