Secure Multi-Party Computation (SMC) Protocols for Aggregation

Secure Multi-Party Computation (SMC) takes a cryptographic approach to achieving privacy, contrasting with methods like Differential Privacy which add noise. The primary goal of SMC in federated learning is to allow the central server to compute the aggregate of client updates (typically the sum or weighted average) without learning any individual client's update. Imagine multiple parties, each holding a private input (their model update $u_i$), wanting to compute a joint function (the sum $\sum u_i$) without revealing their inputs to each other or to the aggregating server.

The Core Principle: Computing on Secret Shares

Many practical SMC protocols for secure aggregation rely on the concept of secret sharing. The general idea is to split each client's private update vector $u_i$ into multiple pieces, called shares. These shares are distributed in such a way that:

1. An individual share reveals little to no information about the original update $u_i$.
2. A specific function (like summation) can be computed directly on the shares.
3. The result of the function computed on the shares corresponds to the function applied to the original secret values.
4. The original secret values $u_i$ cannot be reconstructed unless a sufficient number of shares (often all, or a predefined threshold) are combined, which is prevented by the protocol design.

Additive Secret Sharing for Aggregation

A common and relatively efficient technique for secure summation is additive secret sharing. Let's walk through a simplified protocol involving $N$ clients and a server, designed to compute $S = \sum_{i=1}^{N} u_i$ without the server learning any $u_i$.

1. Pairwise Mask Generation: Before sending updates, each pair of clients $(i, j)$ with $i < j$ needs to agree on a large random number (or vector) $m_{ij}$. This mask must be known only to clients $i$ and $j$. This can be achieved using techniques like Diffie-Hellman key exchange to establish pairwise symmetric keys, which then seed pseudo-random number generators (PRNGs) on both clients to generate the same $m_{ij}$ independently.

2. Client-Side Masking: Each client $i$ masks its update vector $u_i$ using the pairwise masks it shares with other clients. It computes a masked update $u'_i$:

   $$u'_i = u_i + \sum_{j > i} m_{ij} - \sum_{j < i} m_{ji} \pmod{M}$$

   Here, $M$ is a large integer defining the finite field or ring over which the computations are performed. The additions and subtractions are typically element-wise for vectors. Essentially, client $i$ adds masks it generated with clients having higher indices and subtracts masks generated by clients with lower indices.

3. Sending to Server: Each client $i$ sends only its masked update $u'_i$ to the server.

4. Server-Side Aggregation: The server simply sums the masked updates it receives:

   $$S' = \sum_{i=1}^{N} u'_i \pmod{M}$$

5. Mask Cancellation: Let's examine the sum $S'$. When the server sums the $u'_i$, every mask $m_{ij}$ (where $i < j$) appears exactly twice: once positively in $u'_i$ (from the term $+\sum_{k > i} m_{ik}$) and once negatively in $u'_j$ (from the term $-\sum_{k < j} m_{jk}$). Therefore, all masks cancel each other out in the final sum:

   $$S' = \sum_{i=1}^{N} \left( u_i + \sum_{j > i} m_{ij} - \sum_{j < i} m_{ji} \right) = \sum_{i=1}^{N} u_i + \sum_{i=1}^{N} \sum_{j > i} m_{ij} - \sum_{i=1}^{N} \sum_{j < i} m_{ji} \pmod{M}$$

   Since every $m_{ij}$ appears once positively and once negatively, the sum simplifies to:

   $$S' = \sum_{i=1}^{N} u_i = S \pmod{M}$$

   The server obtains the exact sum $S$ without ever seeing any individual $u_i$.

Interaction flow for secure aggregation using additive secret sharing. Clients establish pairwise secrets (dashed lines), mask their updates locally, and send masked updates (blue arrows) to the server. The server sums these, and the masks cancel out, revealing only the aggregate sum (yellow arrow).

Security Assumptions and Measures

This additive sharing scheme provides security against an honest-but-curious server. The server follows the protocol correctly but might try to infer information from the messages it receives (the $u'_i$). Since $u'_i$ is effectively $u_i$ plus a sum/difference of random values unknown to the server (as each $m_{ij}$ involves a client $j \neq i$), $u'_i$ reveals no information about $u_i$ to the server, assuming the masks are cryptographically random.

However, this basic scheme has limitations:

• Collusion: If the server colludes with one or more clients, they might be able to reconstruct the updates of non-colluding clients. For instance, if the server colludes with Client 1, it knows $u'_1$. It also knows all masks $m_{1j}$ involving Client 1. This compromises the privacy of other clients.
• Client Dropouts: If a client computes its masked share $u'_i$ but drops out before sending it to the server, the server will compute an incorrect sum because the masks involving the dropped client won't fully cancel out. Aggregation protocols need mechanisms to handle dropouts, often involving threshold cryptography (like Shamir's Secret Sharing) or more complex interactive protocols.
• Computational and Communication Overhead:
  • Setup: Establishing pairwise secrets incurs communication and computation overhead (e.g., exchanges).
  • Masking: Clients perform extra additions/subtractions. For high-dimensional models, this is generally manageable.
  • Communication: The size of the update sent ($u'_i$) is the same as the original update ($u_i$). However, the setup phase adds communication rounds. More protocols often require multiple rounds of interaction between clients or between clients and the server.

Shamir's Secret Sharing and Threshold Cryptography

Shamir's Secret Sharing (SSS) is another foundational technique adaptable for SMC. In $(t, n)$-SSS, a secret is split into $n$ shares such that any $t$ shares can reconstruct the secret, but $t-1$ shares reveal nothing. This can be used for aggregation by having clients share their updates using SSS. Aggregation can be performed on the shares (due to the homomorphic properties of polynomial interpolation used in SSS). SSS provides inherent robustness against up to $n-t$ dropouts (if $t$ clients successfully submit shares) and security against collusion of up to $t-1$ parties. However, SSS typically involves more complex operations (polynomial evaluation/interpolation) compared to simple additive sharing.

Comparison with DP and HE

• SMC vs. DP: SMC aims to prevent the server from learning anything about individual updates, providing strong input privacy against the server. DP allows the server to see (noisy) updates but provides formal guarantees about what can be inferred about any individual's data contributing to that update, even from the final model. They address different privacy aspects. SMC doesn't directly protect against inference attacks on the final aggregated model.
• SMC vs. HE: Both SMC and HE allow computation (aggregation) without revealing raw inputs to the server. HE involves clients encrypting updates, server computing on ciphertexts, and decryption (often requiring a central or multi-party decryption). HE can sometimes impose higher computational overhead than specific SMC protocols, especially for complex computations, but might require less client-to-client interaction than some SMC schemes. The choice often depends on the specific performance requirements, security assumptions, and system architecture.

"Designing practical SMC-based FL systems involves carefully balancing security guarantees against computational and communication costs, and handling practical issues like client dropouts."