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

需要プライバシーを備えた多メッセージ安全集約

基本情報

  • 論文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個の線形結合を計算することを目的としている。本問題は2つのタスクに対処している：(1) セキュリティ：サーバーが所望の線形結合のみを取得し、ユーザー入力の他の情報を漏らさないことを保証する；(2) プライバシー：ユーザーがサーバーの計算タスクを知ることを防止する。さらに、ユーザーのドロップアウトの影響も考慮され、最大K-U個のユーザーがドロップアウトする可能性があり、その身元は事前に予測できない。著者はKc=1と2≤Kc<Uの2つのケースに対して、それぞれ2つのスキームを提案している。Kc=1の場合、ランダム変数を使用してサーバーの需要を乗法的に暗号化する方法を導入している；2≤Kc<Uの場合、ロバスト対称プライベート計算を使用して第2ラウンドで鍵の線形結合を復元している。

研究背景と動機

問題定義

フェデレーテッドラーニングにより、分散ユーザーは中央サーバーの調整下でグローバルモデルの協調学習が可能になるが、モデル更新はユーザーのローカルデータの情報を漏らす可能性がある。セキュリティをさらに強化するため、安全集約が導入され、サーバーが集約更新のみを取得し、ユーザーデータの追加情報を取得しないことを保証している。

研究動機

  1. マルチタスク学習の需要：単一タスクと比較して、マルチタスク学習は複数の結果を活用してモデル学習の全体的なパフォーマンスを向上させ、情報とリソースの共有を通じて学習効率を改善できる。
  2. 既存方法の限界：
    • 既存の情報論的安全集約問題は主にKc=1のケースに焦点を当てている
    • サーバーの計算タスクのプライバシー保護に対する考慮が不足している
    • ユーザーのドロップアウト状況下でセキュリティとプライバシーを保証する必要がある
  3. 実用的なアプリケーション需要：実際のフェデレーテッドラーニングシナリオでは、サーバーが複数の異なる線形結合を計算する必要があり、同時にユーザーはサーバーの具体的な計算需要を知るべきではない。

主要な貢献

  1. 新しい問題の形式化：需要プライバシーを備えた多メッセージ安全集約問題を初めて提案し、従来の安全集約研究の範囲を拡張した。
  2. 最適スキーム（Kc=1）：乗法的暗号化需要と加法的暗号化モデルを組み合わせた安全集約スキームを提案し、最適通信速率領域を実現した。これはプライバシー制約のない安全集約問題の容量に等しい。
  3. 準最適スキーム（2≤Kc<U）：対称プライベート計算スキームを利用し、第1スキームをKc回直接繰り返すベースライン方法を大幅に改善した。第1ラウンドの速率は最適であり、第2ラウンドの速率は係数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次元係数行列である： F=(a1,1⋯a1,K⋮⋱⋮aKc,1⋯aKc,K)F = \begin{pmatrix} a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}

通信モデル：

  • 第1ラウンド：サーバーがクエリQ1,iをユーザーiに送信し、ユーザーiがメッセージXiを返信する
  • 第2ラウンド：サーバーが存続ユーザー集合U1を通知し、クエリQ^{U1}_{2,i}を送信し、ユーザーiがY^{U1}_iを送信する

制約条件

  1. デコード可能性：サーバーが所望の線形結合を誤りなく計算できる
  2. セキュリティ：サーバーが目標計算結果を超えるユーザー入力情報を取得できない
  3. プライバシー：ユーザーがサーバーの需要行列Fを推測できない

Kc=1の場合のスキーム

核心的な考え方

乗法的暗号化需要と加法的暗号化モデルを組み合わせ、ランダム変数tを通じてサーバーの需要を暗号化する。

詳細なステップ

段階1（クエリ生成）：

  • サーバーがt ∈ Fq{0}をランダムに選択
  • クエリを定義：Q1,i=1ta1,iQ_{1,i} = \frac{1}{ta_{1,i}}、i ∈ K

段階2（鍵生成）：

  • 各ユーザーiに対してZiを生成し、F^L_q上に均一に分布
  • ZiをU個の部分鍵に分割：Zim ∈ F^{L/U}_q
  • MDSマトリックスMを使用してエンコード：[Z~i]j=([Zi]1,…,[Zi]U)⋅M:,j[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}

段階3（第1ラウンド伝送）：

  • ユーザーiが送信：Xi=Wi+Q1,iZiX_i = W_i + Q_{1,i}Z_i

段階4（第2ラウンド伝送）：

  • ユーザーj ∈ U1が集約エンコード部分鍵を送信：∑i∈U1[Z~i]j\sum_{i \in U_1}[\tilde{Z}_i]_j
  • サーバーがMDSデコードを通じて∑i∈U1Zi\sum_{i \in U_1} Z_iを復元

復号プロセス

サーバーが計算： ∑i∈U11Q1,iXi=∑i∈U11Q1,iWi+∑i∈U1Zi\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∑i∈U1a1,iWi=∑i∈U11Q1,iWit \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の場合のスキーム

核心的な考え方

第2ラウンド伝送でロバスト対称プライベート計算を利用してセキュリティとプライバシーを保証する。

詳細なステップ

段階1（鍵生成）：

  • 各i ∈ Kに対して、F^L_qからランダムにZiを選択
  • すべてのユーザーが鍵を共有：Pi = (Zi)i∈K
  • L/(U-1)個の公開ランダム変数を鍵マスクとして共有

段階2（第1ラウンド伝送）：

  • ユーザーiが送信：Xi=Wi+ZiX_i = W_i + Z_i

段階3（第2ラウンド伝送）：

  • サーバーがKc個の鍵結合を復元する必要：∑i∈U1an,iZi\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の場合、容量領域は： R∗={(R1,R2):R1≥1,R2≥1U}\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の場合、速率タプル(R1=1,R2=KcU−1)(R_1 = 1, R_2 = \frac{K_c}{U-1})は到達可能である。

定理6（逆向き界限）： 任意の到達可能速率は以下を満たす必要がある：R1≥1,R2≥KcUR_1 \geq 1, R_2 \geq \frac{K_c}{U}

パフォーマンス分析

  1. 最適性：Kc=1のケースは理論的最適に達する
  2. 準最適性：2≤Kc<Uのケースでは、第1ラウンド速率は最適、第2ラウンド速率は係数2以内で最適： Kc/(U−1)Kc/U=UU−1≤2\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2
  3. ベースラインとの比較：直接繰り返しスキームと比較して、新しいスキームは第1ラウンド速率をKcから1に削減し、第2ラウンド速率を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に対して第1ラウンド最適、第2ラウンド準最適のパフォーマンスを実現した
  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の古典的情報論的セキュリティ結果

総合評価：これは安全集約とプライバシー保護計算の交差領域における重要な貢献をした高品質な理論論文である。実用性の面ではまだ改善の余地があるが、その理論的革新と厳密な分析は後続研究の堅実な基礎を提供している。