技術要約: NFSA: 2層秘密分散を用いた単一サーバーによる非フォワードセキュア集計

1. 問題提起

連合学習（Federated Learning: FL）は、データをローカルに保持したまま共同でのモデル訓練を可能にするが、モデルの更新値（勾配）の送信には依然としてプライバシーのリスクが伴う。サーバーが個々のユーザーの入力を学習せず、集計されたモデルのみを学習できるようにするために、セキュア集計プロトコルが必要となる。

既存のサーバーベースのセキュア集計プロトコルは、特にクロスデバイスのシナリオにおいて、主に2つの課題に直面している：

1. ユーザーの脱落と鍵の転送: ユーザーの脱落に対処するため、プロトコルは多くの場合、Shamirの秘密分散（SS）のような閾値秘密分散を使用し、ユーザーは秘密鍵を「ホルダー（保持者）」（他のユーザーや委員会）と共有する。単一サーバーの設定では、ユーザー間で直接通信することはできないため、サーバーはこれらの秘密のシェアを転送しなければならない。この転送は、重大な通信オーバーヘッド（$N$をユーザー数、$M$をホルダー数としたとき、1ラウンドあたり$O(NM)$）とセキュリティリスクを導入する。なぜなら、サーバーは転送されるシェアを改ざんしたり学習したりしないことを保証する必要があるためである（多くの場合、認証付き暗号が必要となる）。
2. 通信効率: 高次元のモデルパラメータと多数のユーザーは、帯域幅のボトルネックを生み出す。Key-homomorphic Pseudo-Random Function（KhPRF）を用いた最近の「ワンショット」集計スキームは、相互作用のラウンド数を削減するが、「暗号文の拡張」という問題に悩まされる。Almost KhPRF（LWR/LWEに基づく）は、ユーザー数に比例するノイズを導入するため、干渉を避けるためにモデル更新値に余分なスペースを確保する必要があり、これが総通信量（$O(RN \log N)$）を増加させる。

2. 手法

本論文では、秘密のシェアをサーバーが転送する必要性を排除し、新しいエンコーディング手法を通じて通信オーバーヘッドを削減するように設計された、単一サーバーFLシナリオ向けのプロトコルであるNFSA（Non-Forward Secure Aggregation）を提案する。

2.1 2層秘密分散 (Two-Layer Secret Sharing: TLSS)

転送の問題に対処するため、著者らは、機密性の高いシェアをサーバーが中継することなくセキュアな集計を可能にする、2つの層の秘密分散を組み合わせたTLSSを導入する：

• 第1層 (閾値SS): ユーザーの脱落を処理するためにShamirの秘密分散を使用する。ユーザーの秘密（例：KhPRFの鍵）は、シェア $s_m$ に分割され、$M$ 個のホルダーに配布される。
• 第2層 (PRFを用いた加法型SS): $s_m$ をサーバーに直接送り転送させる代わりに、ユーザーは $s_m$ を2つの加法的シェア $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$ に分割する。
  • $s_{m}^{A1}$ は、ユーザーとホルダー $P_m$ の間で事前交渉された共有鍵 $\kappa_{d,m}$ によって生成される疑似乱数関数（PRF）を用いて生成される。
  • $s_{m}^{A2}$ は、$s_{m}^{A2} = s_m - s_{m}^{A1} \mod p$ として計算される。
  • ユーザーは $s_{m}^{A2}$ のみをサーバーに送信する。
  • サーバーはホルダー $P_m$ にタグを送り、ホルダーは自身の共有鍵を用いて $s_{m}^{A1}$ を計算し、サーバーに送り返す。
  • サーバーは $s_m = s_{m}^{A1} + s_{m}^{A2}$ を再構成し、Shamirの再構成を進める。
• 結果: サーバーはユーザーとホルダーの間で秘密のシェアを転送することがなくなり、これにより $O(NM)$ の転送オーバーヘッドと、転送されるシェアに対する認証付き暗号の必要性が排除される。

2.2 Almost KhPRFのためのCRTエンコーディング

Almost KhPRFのノイズによる通信拡張に対処するため、著者らは**中国剰余定理（CRT）**に基づく新しいエンコーディング手法を提案する：

• 問題: 既存の手法は、入力 $x_i$ を $y_i = \Delta x_i - F(k_i, \tau)$ としてマスクする。正しくデコードするためには、$\Delta$ がユーザー数 $n$ よりも大きくなければならず、各要素のビット長が $\log_2(n+1)$ 増加する。
• 解決策: 著者らは、CRTを用いて入力ベクトルの $d_c$ 個の要素を単一の整数にパッキングする。
  • 入力要素は、異なる素数法（moduli） $p_i$ に拡張される。
  • これらは単一の要素 $\mathbb{Z}_{p_c}$ （ここで $p_c = \prod p_i$）へと結合される。
  • マスクされた集計は、これらのパッキングされた要素に対して実行される。
• 利点: これにより、KhPRFの呼び出し回数が $d_c$ 分の1に減少し、Almost KhPRFのノイズによる要素ごとの拡張を回避することで、総通信量を大幅に削減できる。

2.3 NFSAプロトコル

プロトコルは2つのフェーズで動作する：

1. オフラインフェーズ: ユーザーとデクリプター（ホルダー）は、共有鍵を確立するための鍵合意（Key Agreement: KA）を行う。これはステートレスであり、一度だけ行われる。
2. オンラインフェーズ (ワンショット):
   • マスキング: 各ユーザーはKhPRFの鍵を生成し、TLSSを介して（サーバーに加法的シェアのみを送信して）共有し、CRTパッキングされたalmost KhPRFを用いてモデルの更新値をマスクする。
   • アンマスキング: デクリプターは、加法的シェアの和を計算し（TLSSの準同型性を利用）、それをサーバーに送る。サーバーはグローバルなKhPRFの鍵を再構成し、グローバルなマスクを生成し、集計された暗号文をアンマスクしてモデルの更新値を復元する。

3. 主な貢献

1. TLSSスキーム: 単一サーバーFLにおいて、サーバーが秘密のシェアを転送する必要性を排除する、新しい2層秘密分散スキーム。これは、鍵共有のための通信オーバーヘッドを削減し、転送されるデータに対する認証付き暗号の要件を取り除く。
2. Almost KhPRFのためのCRTエンコーディング: 複数の入力をバッチ処理するために中国剰余定理を利用した、新しい入力エンコーディング手法。これにより、KhPRFの呼び出し回数を減らし、Almost KhPLFのノイズによるモデル更新値の拡張問題を緩和する。
3. NFSAプロトコル: TLSSとCRTエンコーディングを組み合わせた、コンパクトなワンショット・セキュア集計プロトコル。これは、単一サーバーかつ中間データの転送なしに、高次元データの集計をサポートする。

4. 実験結果

著者らはPythonでプロトコルを実装し、OPAスキーム（TLSSやCRTパッキングを使用せずにShamirのSSとKhPRFを使用するもの）と比較した。

• TLSSの性能: 従来の転送を伴うShamirのSSと比較して、TLSSは50個のホルダーと鍵を共有する場合、ホルダーの通信オーバーヘッドを約57%削減し、計算時間を95%（64ビットモジュラスの場合）削減した。サーバーによる転送の排除により、総オーバーヘッドは大幅に低減した。
• CRTエンコーディングの性能: CRTパッキング（$d_c=4$）を使用することで、ユーザーのマスキング時間はOPAと比較して3.72倍高速化し、通信トラフィックは1.40倍減少した。
• エンドツーエンドのNFSA性能:
  • ユーザーオーバーヘッド: 100人のユーザーにおいて、NFSAは通信効率をほぼ100倍向上させ（特にデクリプターの通信）、ユーザーの計算時間を（入力長に応じて）**51%から75%**削減した。
  • サーバーオーバーヘッド: サーバーの計算時間はOPAと比較して約**50%削減され、サーバーの通信トラフィックは25%**減少した。
  • デクリプターオーバーヘッド: デクリプターの通信量は、OPAの約19MBからNFSAの約0.19MBへと、100倍近く削減された。

5. 重要性と主張

本論文は、NFSAが単一サーバーにおけるセキュア集計の決定的なボトルネックであるサーバー転送に対処することを主張している。秘密分散プロセスをサーバーの転送ロールから切り離すことで、攻撃対象領域（attack surface）と通信コストを大幅に低減できる。CRTエンコーディングの統合は、Almost KhPRFの効率性をさらに最適化し、高次元のFLモデルへの適用を可能にする。

著者らは、NFSAを**セミホネスト（半誠実）**な環境における非常に効率的なソリューションとして位置づけている。OPAは（SCRAPEやZKPのような検証メカニメントを通じて）悪意のある設定においてより強力な保証を提供する一方で、NFSAはセミホネストモデルにおいて優れた効率性を達成することを認めている。本研究は、NFSAが現実世界のFLアプリケーションに対してスケーラブルで実用的であることを示唆しているが、悪意のある設定への検証可能性の拡張や、CRTパッキングされた入力の検証の洗練には今後の課題が残されている。