Technical Summary: NFSA: Non-Forward Secure Aggregation with One Server via Two Layer Secret Sharing

1. Problem Statement

Federated Learning (FL) enables collaborative model training while keeping data local, but the transmission of model updates (gradients) still poses privacy risks. Secure aggregation protocols are required to ensure that the server learns only the aggregated model, not individual user inputs.

Existing server-based secure aggregation protocols face two primary challenges, particularly in cross-device scenarios:

1. User Dropout and Key Forwarding: To handle user dropouts, protocols often use threshold Secret Sharing (SS), such as Shamir's SS, where users share secret keys with "holders" (other users or committees). In single-server settings, users cannot communicate directly; thus, the server must forward these secret shares. This forwarding introduces significant communication overhead ($O(NM)$ per round, where $N$ is users and $M$ is holders) and security risks, as the server must be trusted not to tamper with or learn the forwarded shares (often requiring Authenticated Encryption).
2. Communication Efficiency: High-dimensional model parameters and large numbers of users create bandwidth bottlenecks. Recent "one-shot" aggregation schemes using Key-homomorphic Pseudo-Random Functions (KhPRF) reduce interaction rounds but suffer from "ciphertext expansion." Almost KhPRF (based on LWR/LWE) introduces noise proportional to the number of users, necessitating extra space in model updates to avoid interference, which increases total communication volume ($O(RN \log N)$).

2. Methodology

The paper proposes NFSA (Non-Forward Secure Aggregation), a protocol designed for a single-server FL scenario that eliminates the need for the server to forward secret data and reduces communication overhead through a novel encoding method.

2.1 Two-Layer Secret Sharing (TLSS)

To address the forwarding issue, the authors introduce TLSS, which combines two layers of secret sharing to enable secure aggregation without server relaying of sensitive shares:

• Layer 1 (Threshold SS): Uses Shamir's Secret Sharing to handle user dropouts. A user's secret (e.g., a KhPRF key) is split into shares $s_m$ distributed to $M$ holders.
• Layer 2 (Additive SS with PRF): Instead of sending $s_m$ directly to the server for forwarding, the user splits $s_m$ into two additive shares: $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$.
  • $s_{m}^{A1}$ is generated using a Pseudo-Random Function (PRF) keyed by a pre-negotiated shared key $\kappa_{d,m}$ between the user and holder $P_m$.
  • $s_{m}^{A2}$ is computed as $s_m - s_{m}^{A1} \mod p$.
  • The user sends only $s_{m}^{A2}$ to the server.
  • The server sends a tag to the holder $P_m$, who computes $s_{m}^{A1}$ using their shared key and sends it back to the server.
  • The server reconstructs $s_m = s_{m}^{A1} + s_{m}^{A2}$ and proceeds with Shamir's reconstruction.
• Result: The server never forwards secret shares between users and holders, eliminating the $O(NM)$ forwarding overhead and the need for Authenticated Encryption on shares.

2.2 CRT Encoding for Almost KhPRF

To address the communication expansion caused by almost KhPRF noise, the authors propose a new encoding method based on the Chinese Remainder Theorem (CRT):

• Problem: Existing methods mask inputs $x_i$ as $y_i = \Delta x_i - F(k_i, \tau)$. To decode correctly, $\Delta$ must be larger than the number of users $n$, increasing the bit length of each element by $\log_2(n+1)$.
• Solution: The authors pack $d_c$ elements of the input vector into a single integer using CRT.
  • Input elements are extended to distinct prime moduli $p_i$.
  • These are combined into a single element in $\mathbb{Z}_{p_c}$ (where $p_c = \prod p_i$).
  • The masked aggregation is performed on these packed elements.
• Benefit: This reduces the number of KhPRF calls by a factor of $d_c$ and significantly reduces the total communication volume by avoiding the per-element expansion of $\Delta$.

2.3 The NFSA Protocol

The protocol operates in two phases:

1. Offline Phase: Users and decryptors (holders) perform a Key Agreement (KA) to establish shared keys. This is stateless and performed once.
2. Online Phase (One-Shot):
   • Masking: Each user generates a KhPRF key, shares it via TLSS (sending only additive shares to the server), and masks their model update using the CRT-packed almost KhPRF.
   • Unmasking: Decryptors compute the sum of their additive shares (leveraging TLSS homomorphism) and send them to the server. The server reconstructs the global KhPRF key, generates the global mask, and unmask the aggregated ciphertext to recover the model update.

3. Key Contributions

1. TLSS Scheme: A novel two-layer secret sharing scheme that eliminates the need for a server to forward secret shares in single-server FL. It reduces communication overhead for key sharing and removes the requirement for authenticated encryption on forwarded data.
2. CRT Encoding for Almost KhPRF: A new input encoding method that utilizes the Chinese Remainder Theorem to batch multiple inputs. This reduces the number of KhPRF calls and mitigates the model update expansion issue caused by almost KhPRF noise, lowering both computational and communication overhead.
3. NFSA Protocol: A compact, one-shot secure aggregation protocol combining TLSS and CRT encoding. It supports high-dimensional data aggregation with a single server and no intermediary data forwarding.

4. Experimental Results

The authors implemented the protocol in Python and compared it against the state-of-the-art OPA scheme (which uses Shamir's SS and KhPRF without TLSS or CRT packing).

• TLSS Performance: Compared to traditional Shamir's SS with forwarding, TLSS reduced holder communication overhead by approximately 57% and computation time by 95% (for 64-bit modulus) when sharing secrets with 50 holders. Total overhead was significantly lower due to the elimination of server forwarding.
• CRT Encoding Performance: Using CRT packing ($d_c=4$) reduced user masking time by 3.72$\times$ and communication traffic by 1.40$\times$ compared to OPA.
• End-to-End NFSA Performance:
  • User Overhead: For 100 users, NFSA improved communication efficiency by nearly 100 times (specifically for decryptor communication) and reduced user computation time by 51% to 75% (depending on input length).
  • Server Overhead: Server computation time was reduced by approximately 50%, and server communication traffic was reduced by 25% compared to OPA.
  • Decryptor Overhead: Decryptor communication was reduced from ~19MB (OPA) to ~0.19MB (NFSA), a reduction of nearly 100 times.

5. Significance and Claims

The paper claims that NFSA addresses the critical bottleneck of server forwarding in single-server secure aggregation. By decoupling the secret sharing process from the server's relay role, it significantly lowers the attack surface and communication costs. The integration of CRT encoding further optimizes the efficiency of almost KhPRF, making it viable for high-dimensional FL models.

The authors position NFSA as a highly efficient solution for semi-honest environments. They acknowledge that while OPA offers stronger guarantees in malicious settings (via verification mechanisms like SCRAPE and ZKP), NFSA achieves superior efficiency in the semi-honest model. The work suggests that NFSA is scalable and practical for real-world FL applications, though future work is needed to extend its verifiability to malicious settings and refine the verification of CRT-packed inputs.