- \(\Delta\) 差分隐私
数据加入随机噪声，可以上传时加噪（本地保护），可以聚合时加噪（中心可信，暴露给第三方时保护）。
- \(\Delta\) SMC 算法 [[Practical Secure Aggregation for privacy-Preserving Machine Learning.pdf]]
- 客户端之间通过安全信道沟通，利用相同随机种子，生成若干掩码对，满足 \(s_{ij} + s_{ji} = 0\)。
- 上传 \(\hat \Delta_i = \Delta_i + \sum_{j \in S_i} s_{ij}\)
- 服务器聚合，此时掩码两两抵消，得到精确聚合
- 如果掉线，那么通过秘密共享，还原掉线的设备的 \(s\)。
两种安全攻击等级：
- 诚实但好奇服务器：严格遵循协议流程仅尝试从合法接收的消息中推断隐私
- 主动攻击服务器：故意偏离协议（如选择性丢包、伪造掉线、篡改路由或广播不一致视图）以超额获取信息或破坏计算正确性。
如何确定链接图？可以有三类机制： - 按概率均匀抽取
- 基于系统资源或者数据质量启发式选择（类似 [[Hat-DFed]]）
- 基于系统状态的过滤
- \(\Delta\) 原论文中是根据设备的在线状况确定链接的子集，并且采用的是完全图。可以优化为仅与部分邻居协商（感觉只要有一颗生成树联通就够了）
- \(\oplus\) 掉线是指上传轮开始时的查询在线，但是没有上传 \(\tilde\Delta_i\) 导致无法抵消掩码，或者没法提交秘密共享的份额。
- \(\oplus\) 假设：服务器作为唯一消息路由，cli 间不沟通
- \(\oplus\) 双重掩码：有两种掩码，自掩码和互掩码。自掩码通过上传后收集自掩码种子的份额还原获取。
- \(\oplus\) 份额互斥规则：对于设备 u，从 v 获取到 u 的份额要门是 u 自掩码的（u 在线），要么是 u 和 v 互掩码的（u 不在线），避免了同时获取一个设备自掩码和互掩码的可能。
- \(\oplus\) 一致性检验：客户端必须对同一份存活列表进行数字签名。cli 收集存活列表中每一个加密，验证是否一致。恶意服务器若发送不同的离线报告，将中止。这样就不存在伪造设备离线的情况了。
- \(\oplus\) 门限阈值约束：如果说视图中有效设备个数小于 \(t\)，那么可以直接拒绝给出份，这样就会因为份额不够无法还原。
- \(\oplus\) 在线阈值检验：如果在线设备过少，那么不进行通讯。
- 综上方法，在完全图的基础上，就可以保证安全。
- 反之，如果是一棵树，那么我们可以构造这样一种攻击方案：
- 在生成掩码阶段，主动阻断部分通讯链路，使得 \(u\) 只能与少量 \(\{v_i\}\)，例如只有其父节点 \(p_u\) 通讯。
- 通过声明 \(p_u\) 离线，可以直接还原 \(s_{u, p_u}\)，由于 \(u\) 在线，可以还原 \(b_u\)，于是可以还原 \(\Delta_u\)
什么是秘密共享？
- 利用多项式插值，设需要保护的数据为 \(f(0)\)，那么可以构建一个 \(t\) 次多项式，利用 \(n\) 个点值来保护。
- 具体来说，随机在大素数数域 \({\mathbb F}_p\) 中取系数，构造多项式 \(f(x) = \sum a_k x^k\)，其中 \(a_0 = {\rm data}\)，然后分发 \(s_i = f(i)\)。
当设备非常多时，由于通讯复杂度是 \(O(n^2)\) 的，怎么办？ - 一个可行的树状结构如下文的 Turbo-Aggregate 算法
- \(\Delta\) Turbo-Aggregate
首先是分组，一共 \(L\) 组，组间树形结构传递消息。
和 SMC 类似，还是有自掩码和互掩码 \(\sum_{i, j} r^l_{i, j} = 0\) 两部分：
\[\tilde x^{l}_{i, j} = x^{l}_i + u^l_i + r^l_{i, j}
\]
传递的信息是 \(\tilde s^l_i = {\rm mean}\{ \tilde s^{l - 1}_j \} + \sum \tilde x^{l}_{i, j}\)
则 \(s^{l} = \frac 1 {N_l} \sum \tilde s^l_i = s^{l - 1} + \sum x^l_i + \sum u_i^l, s^0 = 0\)
于是传递后就可以得到 \(s^{final} = \sum_l \sum (x^l_i + u_i^l)\)
如果一个设备掉线了，考虑其影响是 \(u_l^i\) 和所有的 \(r^l_{i, j}\) 需要还原，于是继续利用秘密共享，将 \(u_l^i, r^l_{i, j}\) 的插值凭证生成 \(N_l\) 份分发给组内的其他设备，于是可以还原 \(u, r\)，消除其影响。但是论文采用的是另一个方法。
将 \(\tilde x^l_{i, j}\) 视为多项式 \(f_i^l(x)\) 在组随机的点集 \(\{\alpha_i\}\) 上的点值，于是可以类似的生成份额 \(\bar x_{i, j}^l = f_i^l(\beta_j)\)，发送给下一组；同理，用相同的方法可以生成 \(\bar s_i^l\)，用于还原 \(\tilde s_i^l\)