4.2 秘密共享与安全聚合
4.2 秘密共享与安全聚合
本节摘要：联邦学习底层靠什么保护？秘密共享和安全聚合。本节讲清楚 Shamir/Additive 秘密共享、安全聚合协议、PSI（隐私集合求交）、以及它们在 FL/MPC 中的作用。读完你能理解 PETs 的分布式基础设施。
一、秘密共享
秘密共享（Secret Sharing）：把秘密 s 拆成 n 份 s₁,...,sₙ，分给 n 方。门限 t：任意 t 份合不出 s（t < 门限），t 份合出 s（t = 门限）。
直觉：秘密"分散"存储，单方或少数方合谋看不到，要足够多方合作才能重构。
Shamir 秘密共享（1979）：
- t-of-n 门限。
- 用 t-1 次多项式 f(x)，f(0)=s 是秘密，份额是 f(1),...,f(n)。
- 任意 t 份用拉格朗日插值重构 f(0)=s，t-1 份合不出（信息论安全）。
- 适合 MPC（BGW 协议）、密钥托管、分布式存储。
Additive 秘密共享：
- 把 s 拆成 n 份，份额和 = s（mod q）。
- 如 s = s₁ + s₂ + ... + sₙ（mod q）。
- 任意 n-1 份合不出 s（信息论安全，若 q 足够大）。
- 适合算术运算（加法直接，乘法用 Beaver 三元组）。
- MPC 的 SPDZ 等用 Additive 共享。
区别：Shamir 用多项式（任意 t 份重构），Additive 用求和（所有份重构）。Shamir 灵活（任意门限），Additive 简单（加法直接）。
二、安全聚合
安全聚合（Secure Aggregation）：多方各持值 vᵢ，联合算 Σvᵢ，但任何方学不到其他方的 vᵢ（只学到总和）。
应用：联邦学习的梯度聚合——服务器学到 ΣΔwᵢ，学不到单个 Δwᵢ。
实现方式：
1. 秘密共享聚合
- 每客户端把 vᵢ Additive 共享给其他客户端。
- 每客户端加自己持有的份额，得部分和。
- 服务器收集部分和，加得总和。
- 服务器只看到部分和，看不到个体 vᵢ。
2. 掩码聚合（Google Secure Aggregation）
- 每对客户端 (i, j) 协商随机掩码 mᵢⱼ = -mⱼᵢ。
- 客户端 i 上传 vᵢ + Σⱼ mᵢⱼ（加所有 pairwise 掩码）。
- 服务器加所有上传值，掩码抵消（mᵢⱼ + mⱼᵢ = 0），得 Σvᵢ。
- 服务器只看到加了掩码的值，掩码抵消后得总和，看不到个体。
3. MPC 聚合
- 用 MPC 协议（如 SPDZ）聚合，更强安全（恶意安全）。
- 性能开销大。
4. TEE 聚合
- 客户端发加密值到 TEE，TEE 内解密聚合。
- 服务器看不到个体（TEE 隔离）。
- 性能好，信任硬件。
三、安全聚合的隐私保证
1. 输入隐私：聚合方学不到个体 vᵢ，只学到总和。
2. 容错：即使部分客户端掉线，仍能聚合（要协议支持）。
3. 通信效率：相比 MPC，安全聚合通信轻（一轮或少数轮）。
4. 局限：只保护"聚合方看不到个体"，不保护"从总和推断"——如总和+已知其他方值能推断某方值。要配 DP 防"总和推断个体"。
四、隐私集合求交（PSI）
隐私集合求交（Private Set Intersection, PSI）：两方各持集合 A、B，联合算 A∩B，但不泄露 A、B 中非交集部分。
应用：
- 纵向联邦：要对齐样本（哪些客户在两方都有），用 PSI 算交集，不暴露各自独有客户。
- 密码泄露检测：用户检查密码是否在泄露库，不暴露密码给服务器。
- 广告归因：跨平台算共同用户，不暴露各自用户。
- 联系人发现：Signal/WhatsApp 用 PSI 找通讯录中已注册用户，不暴露全部通讯录。
实现：
- 基于哈希：简单但弱——双方哈希后比较，但彩虹表攻击。
- 基于 OT：强但慢——用不经意传输，一方不知道另一方集合。
- 基于 HE：一方加密集合，另一方在密文上算交集，返回加密结果。
- 基于 ECC：现代主流——用椭圆曲线 DDH，高效且安全。
五、PSI 的变体
1. PSI-CA（Cardinality）：只返回交集大小，不返回具体交集。更隐私，适合统计。
2. PSI-Sum/Average：算交集上的求和/均值。如广告归因算共同用户的转化率。
3. PSI with Payload：交集元素带关联值，算交集时带值运算。
4. 多方 PSI：n 方算共同交集，复杂度随 n 增长。
六、秘密共享和安全聚合的关系
秘密共享是底层工具，安全聚合是应用：
- 秘密共享：拆数据成份额的通用技术，用于 MPC、密钥管理、安全聚合。
- 安全聚合：用秘密共享（或掩码/MPC/TEE）实现"算总和不见个体"，是 FL 的核心组件。
- PSI：用 HE/OT/ECC 实现"算交集不见全集"，是纵向联邦的核心组件。
它们都是"分布式隐私计算"的基础设施，让多方协作而不交换原始数据。
七、工程落地
1. 库：
- Google Secure Aggregation：FL 中用，TensorFlow Federated 集成。
- OpenMined PySyft：支持安全聚合和 PSI。
- Microsoft SEAL：HE 库，支持 PSI 实现。
- ECDH-PSI：开源 PSI 实现（如 Facebook PSI）。
- Private Join and Compute（Google）：PSI+聚合开源。
2. 应用案例：
- Google Gboard：Secure Aggregation 聚合键盘模型梯度。
- Signal/WhatsApp：PSI 找已注册联系人。
- Facebook Ads：PSI 跨平台广告归因。
- 密码检测：Google/Microsoft PSI 检查密码泄露。
3. 部署要点：
- 选聚合方式：信任聚合方用简单聚合，不信任用安全聚合（掩码/MPC），性能敏感用 TEE。
- PSI 选方案：小集合用 OT，大集合用 ECC-PSI，统计用 PSI-CA。
- 容错：安全聚合要处理掉线客户端（如用秘密共享恢复）。
- 通信：多方时通信按 O(n²) 增长，要优化。
八、在 PETs 中的定位
1. 分布式 PETs 基础设施：秘密共享、安全聚合、PSI 是"数据不出域联合计算"的底层。
2. 联邦学习核心：FL 用安全聚合保护梯度，用 PSI 对齐样本（纵向）。
3. 和 HE/MPC 互补：安全聚合是 MPC 的特例（只算和），PSI 可用 HE 实现——技术栈互补。
4. 不是银弹：安全聚合只保护聚合方不见个体，不防"总和推断"（要配 DP）；PSI 保护非交集，不保护交集本身（交集双方都看到）。
⚠️ 常见误读：以为"安全聚合就完全隐私"。安全聚合只防聚合方看到个体，不防"从总和推断"——如总和+已知其他方值能推断某方。要配 DP 防推断。
💡 关键直觉：秘密共享拆数据成份额（Shamir t-of-n 多项式，Additive 求和），是 MPC/密钥管理基础。安全聚合用秘密共享/掩码/MPC/TEE 让聚合方算总和不见个体，是联邦学习核心。PSI 用 HE/OT/ECC 算交集不见全集，是纵向联邦/密码检测/广告归因核心。是分布式 PETs 基础设施，和 HE/MPC 互补，不是银弹（安全聚合不防总和推断，PSI 不保护交集本身）。
要点串联
- 秘密共享：拆秘密成份额，门限 t 份重构，Shamir（多项式，任意 t 份）、Additive（求和，所有份）。
- Shamir：t-1 次多项式，拉格朗日插值重构，信息论安全，用于 MPC BGW/密钥托管。
- Additive：份额和=s，加法直接，乘法用 Beaver 三元组，用于 MPC SPDZ。
- 安全聚合：多方算总和不见个体，方式有秘密共享聚合、掩码聚合（Google，pairwise 掩码抵消）、MPC 聚合、TEE 聚合。
- 隐私保证：输入隐私（聚合方不见个体）、容错、通信轻，但不防"总和推断"（要配 DP）。
- PSI：双方算交集不见全集，用于纵向联邦对齐/密码检测/广告归因/联系人发现。实现基于哈希（弱）/OT（慢）/HE/ECC（现代主流）。
- PSI 变体：PSI-CA（只大小）、PSI-Sum（求和）、PSI-Payload（带值）、多方 PSI。
- 库：Google Secure Aggregation、PySyft、SEAL、ECDH-PSI、Private Join and Compute。
- 案例：Gboard 聚合、Signal/WhatsApp 联系人、Facebook 广告、密码检测。
- 定位：分布式 PETs 基础设施、联邦学习核心、和 HE/MPC 互补、不是银弹。
应用对比
秘密共享与安全聚合的典型应用对比：密钥管理场景用 Shamir 分享实现门限签名与密钥恢复；联邦学习场景用安全聚合保护梯度隐私，防止参与方从梯度反推他人数据；分布式系统中的秘密分享用于容错（拜占庭容错）。选择方案时需权衡：分享的阈值参数（t-n）决定容错与安全边界、聚合协议的通信轮次影响性能、恶意安全模型（带零知识证明的验证）增加计算开销。