2025-11-23T13:58:16.869352

Multi-Message Secure Aggregation with Demand Privacy

Sun, Zhang, Wan et al.
This paper considers a multi-message secure aggregation with privacy problem, in which a server aims to compute $\sf K_c\geq 1$ linear combinations of local inputs from $\sf K$ distributed users. The problem addresses two tasks: (1) security, ensuring that the server can only obtain the desired linear combinations without any else information about the users' inputs, and (2) privacy, preventing users from learning about the server's computation task. In addition, the effect of user dropouts is considered, where at most $\sf{K-U}$ users can drop out and the identity of these users cannot be predicted in advance. We propose two schemes for $\sf K_c$ is equal to (1) and $\sf 2\leq K_c\leq U-1$, respectively. For $\sf K_c$ is equal to (1), we introduce multiplicative encryption of the server's demand using a random variable, where users share coded keys offline and transmit masked models in the first round, followed by aggregated coded keys in the second round for task recovery. For $\sf{2\leq K_c \leq U-1}$, we use robust symmetric private computation to recover linear combinations of keys in the second round. The objective is to minimize the number of symbols sent by each user during the two rounds. Our proposed schemes have achieved the optimal rate region when $ \sf K_c $ is equal to (1) and the order optimal rate (within 2) when $\sf{2\leq K_c \leq U-1}$.
academic

Multi-Message Secure Aggregation with Demand Privacy

基本信息

  • 论文ID: 2504.20639
  • 标题: Multi-Message Secure Aggregation with Demand Privacy
  • 作者: Chenyi Sun, Ziting Zhang, Kai Wan (华中科技大学), Giuseppe Caire (柏林工业大学)
  • 分类: cs.IT math.IT
  • 发表时间: 2025年10月13日 (arXiv v2)
  • 论文链接: https://arxiv.org/abs/2504.20639

摘要

本文研究了一个带有需求隐私的多消息安全聚合问题，其中服务器旨在计算来自K个分布式用户的本地输入的Kc≥1个线性组合。该问题解决两个任务：(1) 安全性，确保服务器只能获得所需的线性组合而不泄露用户输入的任何其他信息；(2) 隐私性，防止用户了解服务器的计算任务。此外，还考虑了用户掉线的影响，最多K-U个用户可能掉线且其身份无法预先预测。作者针对Kc=1和2≤Kc<U两种情况分别提出了两种方案。对于Kc=1，引入了使用随机变量对服务器需求进行乘法加密的方法；对于2≤Kc<U，使用鲁棒对称私有计算来恢复第二轮中密钥的线性组合。

研究背景与动机

问题定义

联邦学习允许分布式用户在中央服务器的协调下协作训练全局模型，但模型更新仍可能泄露用户本地数据的信息。为进一步增强安全性，安全聚合被引入以确保服务器只能获得聚合更新而不获得用户数据的任何额外信息。

研究动机

  1. 多任务学习需求：相比单任务，多任务学习可以利用多个结果来增强模型训练的整体性能，通过共享信息和资源提高学习效率。
  2. 现有方法局限性：
    • 现有信息论安全聚合问题主要关注Kc=1的情况
    • 缺乏对服务器计算任务隐私保护的考虑
    • 需要在用户掉线情况下保证安全性和隐私性
  3. 实际应用需求：在实际联邦学习场景中，服务器可能需要计算多个不同的线性组合，同时用户不应该知道服务器的具体计算需求。

核心贡献

  1. 新问题形式化：首次提出了带有需求隐私的多消息安全聚合问题，扩展了传统安全聚合的研究范围。
  2. 最优方案(Kc=1)：提出了结合乘法加密需求和加法加密模型的安全聚合方案，实现了最优通信速率区域，等于无隐私约束的安全聚合问题的容量。
  3. 近似最优方案(2≤Kc<U)：利用对称私有计算方案，显著改进了直接重复第一种方案Kc次的基线方法，第一轮速率最优，第二轮速率在因子2内最优。
  4. 理论分析：提供了完整的可达性证明和逆向界限分析，建立了问题的理论基础。

方法详解

系统模型

参与者：

  • 1个服务器和K个非共谋用户(K≥2)
  • 用户i持有输入向量Wi和密钥Pi
  • Wi包含L个独立同分布的均匀符号，定义在有限域Fq上

目标函数： 服务器计算线性映射： g(W1,⋯ ,WK)=F[W1,⋯ ,WK]Tg(W_1, \cdots, W_K) = F[W_1, \cdots, W_K]^T

其中F是Kc×K维系数矩阵：

a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}$$ **通信模型**： - **第一轮**：服务器发送查询Q1,i给用户i，用户i反馈消息Xi - **第二轮**：服务器告知存活用户集合U1，发送查询Q^{U1}_{2,i}，用户i发送Y^{U1}_i ### 约束条件 1. **可解码性**：服务器能无错误计算所需线性组合 2. **安全性**：服务器无法获得超出目标计算结果的用户输入信息 3. **隐私性**：用户无法推断服务器的需求矩阵F ### Kc=1情况的方案 #### 核心思想 结合乘法加密需求和加法加密模型，通过随机变量t对服务器需求进行加密。 #### 详细步骤 **阶段1 (查询生成)**： - 服务器随机选择t ∈ Fq\{0} - 定义查询：$Q_{1,i} = \frac{1}{ta_{1,i}}$，i ∈ [K] **阶段2 (密钥生成)**： - 为每个用户i生成Zi，均匀分布在F^L_q上 - 将Zi分成U个子密钥：[Zi]m ∈ F^{L/U}_q - 使用MDS矩阵M编码：$[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}$ **阶段3 (第一轮传输)**： - 用户i发送：$X_i = W_i + Q_{1,i}Z_i$ **阶段4 (第二轮传输)**： - 用户j ∈ U1发送聚合编码子密钥：$\sum_{i \in U_1}[\tilde{Z}_i]_j$ - 服务器通过MDS解码恢复$\sum_{i \in U_1} Z_i$ #### 解密过程 服务器计算： $$\sum_{i \in U_1} \frac{1}{Q_{1,i}}X_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i + \sum_{i \in U_1} Z_i$$ 由于$t \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i$，服务器可解码目标线性组合。 ### 2≤Kc<U情况的方案 #### 核心思想 利用鲁棒对称私有计算在第二轮传输中保证安全性和隐私性。 #### 详细步骤 **阶段1 (密钥生成)**： - 为每个i ∈ [K]，从F^L_q中随机选择Zi - 所有用户共享密钥：Pi = (Zi)i∈[K] - 共享L/(U-1)个公共随机变量作为密钥掩码 **阶段2 (第一轮传输)**： - 用户i发送：$X_i = W_i + Z_i$ **阶段3 (第二轮传输)**： - 服务器需要恢复Kc个密钥组合：$\sum_{i \in U_1} a_{n,i}Z_i$，n ∈ [Kc] - 将每个密钥Zi分成长度为L' = U-1的子密钥 - 使用对称私有计算方案Kc次，分别获取每个线性组合 - 通过拉格朗日编码构造查询多项式，保护计算任务隐私 ## 实验结果 ### 理论结果 **定理3 (Kc=1最优性)**： 对于(K,U,Kc)多消息安全聚合问题，当U≤K-1且Kc=1时，容量区域为： $$\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}$$ **定理5 (2≤Kc<U可达性)**： 当2≤Kc<U≤K-1时，速率元组$(R_1 = 1, R_2 = \frac{K_c}{U-1})$是可达的。 **定理6 (逆向界限)**： 任何可达速率必须满足：$R_1 \geq 1, R_2 \geq \frac{K_c}{U}$ ### 性能分析 1. **最优性**：Kc=1情况达到理论最优 2. **近似最优性**：2≤Kc<U情况下，第一轮速率最优，第二轮速率在因子2内最优： $$\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2$$ 3. **与基线比较**：相比直接重复方案，新方案将第一轮速率从Kc降至1，第二轮速率从Kc/U增至Kc/(U-1) ## 相关工作 ### 安全聚合 - **信息论安全聚合**：Zhao和Sun首次提出信息论形式化，实现容量区域{(R1,R2) : R1≥1, R2≥1/U} - **实用安全聚合**：LightSecAgg通过解耦密钥生成过程显著减少所需密钥数量 ### 私有信息检索与计算 - **私有信息检索(PIR)**：允许服务器从分布式数据库中私密检索消息 - **私有计算(PC)**：扩展PIR框架包含消息的线性计算 - **对称私有计算**：同时保护服务器计算任务隐私和用户数据安全 ### 多任务学习 - **协调学习**：多个任务通过共享信息和资源协作，提高整体学习效率 - **共同表示**：任务受益于共同表示、梯度或共享组件 ## 结论与讨论 ### 主要结论 1. 首次形式化了带需求隐私的多消息安全聚合问题 2. 对于Kc=1实现了最优通信速率区域 3. 对于2≤Kc<U实现了第一轮最优、第二轮近似最优的性能 4. 提供了完整的理论分析框架 ### 局限性 1. **开放区域**：当Kc≥U时的容量区域刻画仍未解决 2. **密钥大小**：未优化所需密钥大小的最小化 3. **实用性**：理论方案在实际系统中的实现复杂度较高 4. **扩展性**：对于非线性计算任务的扩展性有限 ### 未来方向 1. **容量区域完整刻画**：解决Kc≥U情况下的最优性问题 2. **密钥优化**：最小化所需密钥大小以提高实用性 3. **系统实现**：开发实际可部署的系统原型 4. **非线性扩展**：扩展到非线性计算任务 ## 深度评价 ### 优点 1. **理论贡献显著**：开创性地结合了安全聚合和需求隐私，填补了重要理论空白 2. **方法创新性强**：巧妙结合乘法加密和对称私有计算，技术路线新颖 3. **理论分析完整**：提供了严格的可达性证明和逆向界限分析 4. **实际意义重大**：解决了联邦学习中的重要隐私保护问题 ### 不足 1. **适用范围有限**：仅考虑线性计算任务，实际应用中可能需要非线性操作 2. **实现复杂度高**：特别是2≤Kc<U情况下的对称私有计算实现较为复杂 3. **参数限制**：要求Kc<U的限制在某些应用场景下可能过于严格 4. **实验验证缺失**：缺乏实际系统实现和性能测试 ### 影响力 1. **学术价值**：为安全多方计算和联邦学习领域提供了新的理论框架 2. **实用潜力**：为隐私保护的分布式机器学习提供了理论基础 3. **可复现性**：理论结果清晰，但实际实现需要大量工程工作 ### 适用场景 1. **联邦学习**：多任务联邦学习中的隐私保护聚合 2. **分布式统计**：需要计算多个统计量的分布式系统 3. **隐私保护分析**：金融、医疗等对隐私要求严格的数据分析场景 ## 参考文献 论文引用了多个重要参考文献，包括： - Zhao & Sun的信息论安全聚合工作 - Sun & Jafar的私有信息检索和私有计算容量结果 - Zhu等人的对称私有多项式计算方案 - Shannon的经典信息论安全结果 --- **总体评价**：这是一篇高质量的理论论文，在安全聚合和隐私保护计算交叉领域做出了重要贡献。虽然在实用性方面还有改进空间，但其理论创新和严格分析为后续研究奠定了坚实基础。