Lotto: Secure Participant Selection against Adversarial Servers in Federated Learning

Lotto: Secure Participant Selection against Adversarial Servers in Federated Learning

Speakers: Zhifeng Jiang, Peng Ye, Shiqi He, Wei Wang, Ruichuan Chen, Bo Li

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=ufqhtEWOrLw

Overview

The talk "Lotto: Secure Participant Selection against Adversarial Servers in Federated Learning" introduces a pioneering framework designed to fortify the privacy and security of Federated Learning (FL) against a significant, previously unaddressed vulnerability: the malicious FL server. Presented by Zhifeng Jiang from HKUST and collaborators, Lotto directly confronts the challenge of ensuring an honest majority among selected participants, even when the central server orchestrating the FL process is adversarial. This work is critical because existing privacy-preserving techniques like Secure Aggregation (SA) and Differential Privacy (DP), while foundational, are shown to be inherently fragile if a malicious server can manipulate which clients participate in a training round.

The core problem Lotto addresses is the server's unilateral control over participant selection. In traditional FL setups, the server determines which clients contribute to each training round, typically through random sampling or by selecting clients based on performance metrics. However, if this server is malicious, it can collude with dishonest clients to form a "dishonest majority," thereby subverting the very mechanisms meant to protect user data. Lotto provides the first secure participant selection framework that probabilistically guarantees an honest majority, significantly enhancing the robustness of FL systems. Its importance lies in closing a critical security gap, ensuring that the integrity of privacy-preserving FL is maintained from the initial selection phase through to model aggregation.

Background

▶ Watch: The core problem: malicious server creates dishonest majority (2:20)

Federated Learning (FL) has emerged as a powerful paradigm for collaborative machine learning, allowing multiple clients (e.g., mobile devices, organizations) to train a shared model without centralizing their raw data. This inherent data locality is a primary appeal, addressing concerns about data privacy and regulatory compliance. Clients compute local model updates based on their private datasets, and these updates are then aggregated by a central server to improve the global model.

While keeping data on-device is a crucial first step, it is widely acknowledged to be insufficient for comprehensive privacy. Prior research has demonstrated that even local model updates, when observed individually by a server, can be exploited to reconstruct sensitive training data with high fidelity. To counter this, FL systems commonly integrate two advanced privacy-enhancing technologies:

1. Secure Aggregation (SA): This cryptographic protocol ensures that the server can compute the sum of local updates (the global model update) without seeing any individual client's contribution. It guarantees that only the aggregated sum, not the discrete components, is revealed.
2. Differential Privacy (DP): DP further strengthens privacy by adding controlled, random noise to the aggregated update. This noise makes it statistically difficult to infer information about any single user's data from the global update, effectively blurring any potential data fingerprints. In practice, DP noise is often added collaboratively, with each participant contributing an even share of the noise to their local update before aggregation.

Despite the apparent synergy of FL, SA, and DP, a critical vulnerability persists: the assumption of honest participants and a benign server-client interaction model. The underlying mechanisms of SA and DP rely on the premise that all participating clients truthfully contribute their share of noise and follow the protocol. However, if a malicious server can influence participant selection, this assumption breaks down. A server acting adversarially can collude with dishonest clients, deliberately selecting them to form a dishonest majority.

If dishonest clients choose not to add their required share of DP noise, the server will observe a less noisy global update, enabling it to infer more sensitive information from the remaining honest participants. More alarmingly, if the proportion of dishonest participants exceeds a certain threshold, the entire Secure Aggregation protocol can fail, allowing the server to directly inspect individual local updates, potentially with minimal or no noise. This effectively nullifies the privacy guarantees of both SA and DP. The problem is exacerbated by the fact that in most FL setups, the server alone dictates participant selection, whether through random sampling or "informed selection" based on metrics like data quality or system speed. This unilateral control presents a clear attack vector for a malicious server seeking to compromise the system's privacy by strategically selecting dishonest clients. Before Lotto, there was no robust solution to prevent a malicious server from growing such a dishonest majority.

Key Findings

▶ Watch: Solving 'unlisted client' challenge with probabilistic game (4:30)

Lotto represents a significant advancement in the security of Federated Learning by addressing the fundamental weakness of server-controlled participant selection. The key findings and contributions of this work are:

1. First Secure Participant Selection Framework: Lotto is presented as the first framework specifically designed to secure participant selection in FL against an adversarial server. It fills a critical gap, ensuring that the integrity of privacy-preserving FL is maintained from the very first step of participant recruitment.
2. Probabilistic Guarantee of Honest Majority: The framework is rigorously proven to ensure that, with high probability, the fraction of dishonest clients in the selected participant cohort will be very close to their base rate in the overall population. This means if the general client population has an honest majority, Lotto guarantees that the selected participants will also maintain an honest majority, effectively thwarting the server's attempt to engineer a dishonest one.
3. Minimal Performance Overhead: Despite its strong security guarantees, Lotto introduces remarkably low performance overhead. Evaluation results demonstrate that its runtime latency is no more than 10% higher than baseline FL, and its communication footprint is negligible. This makes Lotto a practical solution for real-world FL deployments.
4. Effective for Informed Selection: Lotto successfully extends its security guarantees to "informed selection" scenarios, where clients are chosen based on specific metrics. By approximating informed selection with a verifiable random selection process, Lotto achieves comparable time-to-accuracy performance to state-of-the-art unsecure selectors, proving that its security measures do not compromise model training efficiency.
5. Robust against Prediction and Manipulation: Through the innovative use of Verifiable Random Functions (VRFs) and a probabilistic verification mechanism, Lotto eliminates the server's ability to predict which clients will join a round or to manipulate the selection process by ignoring honest clients.

Technical Deep Dive

▶ Watch: Concrete example of probabilistic defense against adversaries (5:00)

Lotto tackles the challenge of secure participant selection by addressing two primary selection methodologies: random selection and informed selection. Its technical core revolves around client-side verification and the strategic use of cryptographic primitives.

Securing Random Selection

The traditional approach to random selection in FL involves the server computing a random function for each client, often using the client's public key and the current round index as inputs. This generates a client- and round-specific random number, which the server then uses to select clients based on predefined criteria (e.g., selecting clients whose random numbers fall within a certain range). The fundamental flaw here is the server's ability to deviate from this process, manipulating selection to favor dishonest clients.

Lotto's initial defense introduces mutual verification among clients. The high-level idea is that if a client is claimed to join, other participants should be able to verify whether its associated random number falls within the predefined range. This ensures that any client selected is chosen by chance, according to the protocol, rather than by server manipulation. While this is a good starting point, Lotto identifies and resolves two key challenges for practical deployment.

Challenge 1: Unseen Clients and Dishonest Majority Growth

The first challenge arises from clients who are not on the server's announced participant list. How can other clients know if these unlisted clients were genuinely associated with random numbers outside the selection range, or if the server deliberately ignored honest clients (either before or after computing their random functions) to prevent them from joining? This loophole allows a malicious server to still circumvent mutual verification and grow a dishonest majority.

Lotto addresses this by requiring each participant to perform two additional verifications:

1. Verify List Size: The participant list seen by the client must be sufficiently large, meeting a predefined minimum threshold (e.g., 200 participants).
2. Verify Selection Chance: The predefined selection range (which dictates the probability of any given client being selected) must be sufficiently small (e.g., a selection chance no smaller than 0.1%).

By combining these two checks, Lotto plays a probabilistic game with the adversary. The argument is that if the required minimum number of participants is P_min and the selection chance is C, then for a server to achieve a dishonest majority (e.g., >50% dishonest participants), it would need to ignore an implausibly large number of honest clients. For instance, if the system requires a minimum of 200 participants and the selection chance is 0.1%, then with 99% probability, the proportion of dishonest participants will not exceed 50%. This implies that the server cannot arbitrarily ignore honest clients unless it controls an extremely large fraction of the total client population – in the example given, more than 80,000 clients. This makes it practically infeasible for a malicious server to subvert the selection process by simply ignoring honest clients.

Challenge 2: Predictability and Side-Channel Attacks

The second challenge stems from the predictability of selection outcomes in the traditional random selection model. Since the inputs for computing the random functions (public key, round index) are public, the server can predict which specific clients will be selected for future rounds. This predictability opens a side-channel attack: a malicious server can concentrate its resources on compromising a known future participant before the round begins, turning an otherwise honest client into a dishonest one. This targeted attack is far more efficient than randomly compromising clients.

To close this vulnerability, Lotto leverages Verifiable Random Functions (VRFs). Unlike common random functions, a VRF's output is generated using a secret key, which is never disclosed publicly. Crucially, a VRF also produces a proof alongside its output. Anyone holding the corresponding public key can use this proof to verify the correctness of the generated random number without knowing the secret key.

Lotto integrates VRFs by allowing each client to self-sample itself using its own secret key. This process ensures that:

• Unpredictability: The selection outcome is no longer predictable for the server, as it does not possess the clients' secret keys.
• Verifiability: Other participants can still verify the correctness of the self-sampling process using the publicly available proof and the client's public key.

This elegant solution effectively eliminates the side-channel attack vector, as the server cannot know in advance which clients will be selected and thus cannot pre-emptively target them for compromise.

Securing Informed Selection

Informed selection aims to choose participants based on specific user-defined metrics, such as data quality, device speed, or connectivity. The major challenge here is the lack of verifiable client metrics. A malicious server or dishonest clients can easily produce or report fake metrics to manipulate the selection process.

Lotto's approach to securing informed selection is to introduce verifiable randomness. The framework proposes to approximate each informed selection process with a random selection one, but critically, one that is secured by Lotto's VRF-based mechanisms. While this is an approximation, the evaluation results demonstrate that it remains highly effective, achieving performance comparable to state-of-the-art unsecure informed selectors. The detailed approximation methodology is elaborated in the accompanying paper.

Demo / Proof of Concept

▶ Watch: Using Verifiable Random Functions for unpredictable selection (6:40)

While the talk did not feature a live software demonstration, the effectiveness and practicality of Lotto were substantiated through comprehensive evaluation results, which serve as a robust proof of concept. These evaluations focused on both the security guarantees and the performance overheads of the proposed framework.

Security Guarantees

Lotto's primary security claim is its ability to ensure an honest majority among selected participants with high probability. The research provides a formal proof demonstrating that if Lotto is used for participant selection, the fraction of dishonest clients in the selected cohort will be "very close to the base rate" of dishonest clients in the overall population. This means that if the initial client population has an honest majority, Lotto guarantees that the selected participants will also reflect this honest majority.

A concrete case study was presented to illustrate this:

• Population Size: 200,000 clients.
• Base Dishonest Rate: 0.5% of clients are dishonest.
• Target Participants: 200 clients per round.

In a scenario without Lotto, a dishonest server could easily populate any fraction of the 200 participants with dishonest clients. However, with Lotto in place, the server faces "increasing difficulty" in growing a dishonest cohort. Specifically, the success rate for a malicious server to ensure that at least 10% of the selected participants are dishonest is "very close to zero." This empirically validates Lotto's ability to prevent a malicious server from engineering a dishonest majority.

Performance Overhead

Lotto was evaluated across various FL testbeds and population scales to assess its practical viability. The results demonstrated minimal performance impact:

• Runtime Performance: Measured by latency per round, Lotto introduced "no more than 10%" additional overhead compared to baseline FL. This small increase in latency is considered acceptable for the significant security benefits it provides.
• Communication Overhead: The footprint induced per round, a measure of communication overhead, was found to be "negligible." This is crucial for FL, where communication efficiency, especially for edge devices, is often a bottleneck.

Effectiveness as Secure Selector for Informed Selection

For informed selection, where Lotto employs an approximation strategy, its effectiveness was compared against Orchestra, a state-of-the-art unsecure selector optimized for time-to-accuracy performance. The evaluation focused on comparing their performance in terms of time-to-accuracy, which measures how quickly the model reaches a desired accuracy level. The results showed that Lotto's time-to-accuracy performance "does match" that of Orchestra. This indicates that despite introducing an approximation to secure the informed selection process, Lotto does not significantly compromise the model's training efficiency, making it a highly effective and practical secure selector.

Defensive Implications

▶ Watch: Addressing informed participant selection challenges (7:30)

The "Lotto" framework provides critical insights and actionable strategies for defenders in the Federated Learning ecosystem. The talk highlights that traditional privacy mechanisms like Secure Aggregation (SA) and Differential Privacy (DP) are insufficient on their own if the participant selection process is vulnerable to a malicious server. Consequently, FL practitioners and security architects must integrate secure participant selection as a foundational element of their defense strategy.

Here are key defensive implications:

1. Prioritize Secure Participant Selection: Defenders must recognize that the integrity of FL privacy mechanisms begins with participant selection. Relying solely on SA and DP without securing the selection phase leaves a critical attack surface open. Implementing frameworks like Lotto is no longer optional but a necessity for robust privacy.

1. Assume an Adversarial Server: The core premise of Lotto is an adversarial server. Defenders should adopt this threat model, assuming that the central orchestrator of FL might attempt to manipulate participant cohorts. This shift in mindset necessitates proactive measures to decentralize trust in selection.

1. Implement Client-Side Verification: Empowering clients to verify aspects of the selection process is crucial. This includes:

• Mutual Verification: Clients should verify that selected participants' random numbers fall within the specified range.
• Cohort Integrity Checks: Clients must verify that the announced participant list meets minimum size requirements and that the selection chance is appropriately small. This probabilistic defense makes it economically infeasible for a server to ignore honest clients en masse.

1. Adopt Verifiable Random Functions (VRFs): To counter prediction-based side-channel attacks, VRFs are indispensable. By allowing clients to self-sample using secret keys and providing verifiable proofs, VRFs ensure that the server cannot predict future participants, thereby preventing targeted client compromises. Defenders should explore cryptographic libraries and frameworks that support VRF implementation.

1. Rethink Informed Selection: When using informed selection criteria (e.g., data quality, device speed), defenders must be wary of unverifiable metrics. Lotto's approach of approximating informed selection with verifiable randomness offers a secure alternative. While it's an approximation, the demonstrated matching time-to-accuracy performance suggests it's a viable trade-off for security.

1. Monitor for Anomalous Selection Patterns: Even with Lotto, continuous monitoring of participant selection patterns and the overall distribution of honest/dishonest clients (if assessable) can provide an additional layer of defense. Any significant deviation from the expected base rate of dishonest clients could signal an attempted circumvention.

1. Consider the Cost of Attack: Lotto's probabilistic security makes it prohibitively expensive for an adversary to achieve a dishonest majority. Defenders should leverage this economic disincentive, understanding that increasing the required minimum number of participants and reducing the selection chance enhances security.

By adopting these defensive strategies, organizations deploying Federated Learning can significantly enhance the privacy, integrity, and trustworthiness of their systems, moving beyond the limitations of isolated privacy mechanisms to a more holistic security posture.

Key Takeaways

• Critical Vulnerability Addressed: Federated Learning's privacy (Secure Aggregation, Differential Privacy) is compromised if a malicious server can manipulate participant selection to form a dishonest majority.
• Lotto is First-of-its-Kind: It's the first secure participant selection framework specifically designed to protect FL against adversarial servers.
• Probabilistic Security Guarantee: Lotto ensures, with high probability, that the selected participant cohort maintains an honest majority, aligning closely with the base rate of honest clients in the total population.
• Verifiable Random Functions (VRFs) are Key: VRFs prevent server prediction of participant selection, thwarting targeted client compromise attacks by enabling clients to self-sample with verifiable proofs.
• Low Performance Overhead: Lotto achieves strong security with minimal impact on FL performance, showing less than 10% runtime latency overhead and negligible communication footprint.
• Effective for Informed Selection: It securely handles informed selection by approximating it with verifiable randomness, maintaining comparable time-to-accuracy performance to unsecure baselines.

About the Speaker(s)

The talk "Lotto: Secure Participant Selection against Adversarial Servers in Federated Learning" was a collaborative effort. The speakers and contributors include Zhifeng Jiang, who presented the work, and his colleagues Peng Ye and Wei Wang, all affiliated with HKUST. Further contributions came from Shiqi He and Bo Li from the University of Michigan, and Ruichuan Chen from Nokia Bell Labs.