- $\Delta$ 差分隐私
数据加入随机噪声，可以上传时加噪（本地保护），可以聚合时加噪（中心可信，暴露给第三方时保护）。
- 服务器作为唯一消息路由，cli 间交流，利用由 Diffie-Hellman 密钥协商确定性派生，生成若干掩码对，满足 $s_{ij} + s_{ji} = 0$。
- 上传 $\hat \Delta_i = \Delta_i + \sum_{j \in S_i} s_{ij}$
- 服务器聚合，此时掩码两两抵消，得到精确聚合
- 如果掉线，那么通过秘密共享，还原掉线的设备的密钥，进一步还原 $s_{ij}$。
两种安全攻击等级：
- 诚实但好奇服务器：严格遵循协议流程仅尝试从合法接收的消息中推断隐私
- 主动攻击服务器：故意偏离协议（如选择性丢包、伪造掉线、篡改路由或广播不一致视图）以超额获取信息或破坏计算正确性。
如何确定链接图？可以有三类机制： - 按概率均匀抽取
- 基于系统资源或者数据质量启发式选择（类似 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)$。
什么是 Diffie-Hellman 密钥协商？ - 利用乘法简单，但是除法困难，例如椭圆曲线。双方约定大素数 p 和生成元 g（公开）。
- 各自选定私钥 $A = g^a, B = g^b$，交换私钥
- 得到密钥 $key = g^{ab} = A^b = B^a$
- 注意，即使获取了 $A, B, p, g$，也无法快速的获得 $key$，这基于椭圆曲线离散对数计算困难。
- 原文采用了 SHA-256 将 key 转化为随机串，论文原型采用 AES 计数器模式 (AES-CTR) 作为 PRG。通过递增计数器输入 AES 块加密，生成任意长度的伪随机比特流；随后按位截取或取模运算将比特流映射到 $[0,R)$ 整数域。
- AES 算法暂时忽略
当设备非常多时，由于通讯复杂度是 $O(n^2)$ 的，怎么办？
- AES 算法暂时忽略
- 一个可行的树状结构如下文的 Turbo-Aggregate 算法
- $\Delta$ Turbo-Aggregate
首先是分组，一共 $L$ 组，组间树形结构传递消息。
和 SMC 类似，还是有自掩码和互掩码 $\sum_{i, j} r^l_{i, j} = 0$ 两部分： ^0c0944
$$\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 s$ 阶段消除影响，否则需要额外恢复 $s_i$，鲁棒性可能没有论文的方法那么好。
将 $\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$