Efficient Secure Aggregation for Federated Learning

Federated Learning (FL) is a collaborative machine learning approach where a global model is trained without requiring clients to share their raw, private data. Instead, clients compute updates to the model locally on their devices and send only these updates to a central server. The server then aggregates these updates to improve the global model. This is used in applications like mobile keyboard predictions (Apple’s QuickType, Google’s Gboard) and collaborative analysis of sensitive healthcare data.

However, a significant privacy challenge remains: the model updates themselves, while not raw data, can still be reverse-engineered to extract sensitive information from the training data. The goal of private FL is to prevent this leakage.

The Secure Aggregation Problem

The server’s primary task during aggregation is to compute the average, or effectively the sum, of all client updates. The core problem, therefore, becomes one of secure aggregation: how can the server learn the sum of all client inputs (the updates) without learning any individual input?

This can be framed as a Multi-Party Computation (MPC) problem for the summation function, with specific constraints:

• Only the server learns the final output (the sum).
• The server provides no input to the computation.
• The clients provide the inputs, which must remain private.

Unique Constraints of Federated Learning

Generic MPC protocols are often unsuitable for the FL environment due to a unique set of operational constraints:

• No Inter-Client Interaction: Clients are typically mobile devices that cannot be expected to establish direct communication channels with each other. This rules out protocols that require peer-to-peer interaction, such as running a Distributed Key Generation (DKG) protocol.
• One-Shot Protocol: Clients should send a single message to the server and then be free to go offline. They cannot be required to stay online to participate in multi-round protocols or wait for a response from the server. This is critical because devices may lose connectivity or be turned off at any moment.
• Single Server Architecture: Solutions should not rely on multiple, non-colluding servers, as this is often not a practical assumption.
• Robustness to Dropouts: The protocol must successfully complete the aggregation even if a subset of clients drops out mid-process.
• Preventing Residual Leakage: A malicious server in a one-shot protocol could try to learn individual inputs by selectively choosing which client messages to include in the aggregation. The protocol must prevent the server from computing sums on arbitrary subsets of the inputs.

The Committee-Based Approach

To address these constraints, recent work, including the proposed protocol Tacita, utilizes a committee. This is a set of parties that assist the server in the decryption process, allowing the clients to remain “one-shot”. The clients send their encrypted data and are done. The server then interacts with the committee to get the final result. This design helps prevent the residual leakage attack, as the committee can enforce that decryption only happens on a valid, aggregated set of inputs.

Prior work like Vilo and OPA also use this model. However, Vilo requires the committee to run a DKG, and OPA can have high communication costs between the server and the committee.

Tacita: A New Protocol for Secure Aggregation

The presented work, Tacita, is a protocol that satisfies all the FL-specific constraints while achieving constant communication complexity. It relies on two novel cryptographic primitives.

1. Homomorphic Silent Threshold Encryption

To avoid the need for a DKG, Tacita uses Silent Threshold Encryption, a primitive that allows for threshold encryption without an interactive setup.

• Each member of the committee generates their own keys independently (e.g., BLS keys).
• A common public key for the committee can be computed on the fly by anyone, simply by aggregating the individual public keys of the selected committee members.
• Clients encrypt their model updates under this aggregated public key.
• Decryption is achieved when a threshold of committee members provides partial decryptions. A key insight is that this witness encryption scheme, where a BLS signature is the witness for decryption, can be made homomorphic. This allows the server to sum the encrypted updates directly, resulting in a single ciphertext that encrypts the sum of the inputs.

2. Multi-Key Linearly Homomorphic Threshold Signatures (MKLHTS)

To protect against a malicious server that might send an individual client’s ciphertext to the committee for decryption, clients must sign their ciphertexts. Sending all individual signatures to the committee would create a communication bottleneck, violating the goal of constant communication.

Tacita solves this with a new primitive: Multi-Key Linearly Homomorphic Threshold Signatures. This scheme has a powerful property:

Signatures on different messages (M1, M2, …) created by different clients under their own unique secret keys can be aggregated into a single, constant-size signature. This aggregate signature efficiently proves the validity of the sum of the messages (M1 + M2 + …) under the sum of the public keys.

The Tacita Protocol Flow

The final protocol operates as follows:

1. Clients: Each client encrypts its model update xi using the homomorphic silent threshold encryption scheme, using the committee’s aggregated public key. They then sign the resulting ciphertext with their own key using the MKLHTS scheme. They send the single ciphertext and single signature to the server. This is a one-shot operation.
2. Server: The server receives ciphertexts and signatures from all participating clients.
   • It homomorphically adds all the ciphertexts to get a single aggregated ciphertext, which encrypts the sum of all updates.
   • It aggregates all the MKLHTS signatures into a single, constant-size signature.
3. Server-to-Committee: The server sends the single aggregated ciphertext and the single aggregated signature to the committee.
4. Committee: The committee first verifies the aggregated signature. If valid, it confirms the server aggregated the inputs correctly. The members then perform partial decryptions on the aggregated ciphertext and send them back to the server.
5. Server: The server combines the partial decryptions to recover the final plaintext sum of all the model updates.

This design achieves all the desired properties: it’s a one-shot protocol for clients, requires no DKG, uses a single server, and has constant-size communication between all parties, making it highly suitable for the constrained environment of Federated Learning.

• Tags:
• Privacy
• Cryptography
• Homomorphic Encryption
• Federated Learning
• Secure Aggregation
• MPC
• Threshold Signatures
• Tacita Protocol