PaperlayerView exact revision on arXiv

Source-linked AI summary

Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning

Yiping Ma, Jess Woods, Sebastian Angel, Antigoni Polychroniadou, Tal Rabin

arXiv:2308.09883v4cs.CRcs.LG

TL;DR

Federated learning needs repeated secure aggregation, but single-round protocols incur costly fresh setup when reused and individual weights can leak raw data. Flamingo reuses setup secrets across rounds and uses lightweight dropout resilience to reduce interactions. It reports faster summation and Extended MNIST training than repeated BBGLR.

  • Problem

    Repeatedly applying single-round secure aggregation in federated learning incurs costly fresh setup, while individual weights can leak information about raw data.

    Source: §1 · p. 1

  • Method

    Flamingo reuses setup secrets across multiple sums and uses a lightweight protocol in which a small number of clients help remove masks after input collection.

    Source: §1 · pp. 1–2

  • Results

    3× faster than BBGLR for a 10-round pure summation task; Extended MNIST convergence took about 40 minutes versus roughly 3.5 hours to reach the same training accuracy.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Flamingo’s design reduces overall federated-learning training time compared with running BBGLR multiple times.

    Source: §1 · p. 2

    Ensuring correctness against malicious client inputs is out of scope, and strong guarantees against such inputs remain an open problem.

    Source: §2.4 · p. 3

Abstract

from arXiv · show

This paper introduces Flamingo, a system for secure aggregation of data across a large set of clients. In secure aggregation, a server sums up the private inputs of clients and obtains the result without learning anything about the individual inputs beyond what is implied by the final sum. Flamingo focuses on the multi-round setting found in federated learning in which many consecutive summations (averages) of model weights are performed to derive a good model. Previous protocols, such as Bell et al. (CCS '20), have been designed for a single round and are adapted to the federated learning setting by repeating the protocol multiple times. Flamingo eliminates the need for the per-round setup of previous protocols, and has a new lightweight dropout resilience protocol to ensure that if clients leave in the middle of a sum the server can still obtain a meaningful result. Furthermore, Flamingo introduces a new way to locally choose the so-called client neighborhood introduced by Bell et al. These techniques help Flamingo reduce the number of interactions between clients and the server, resulting in a significant reduction in the end-to-end runtime for a full training session over prior work. We implement and evaluate Flamingo and show that it can securely train a neural network on the (Extended) MNIST and CIFAR-100 datasets, and the model converges without a loss in accuracy, compared to a non-private federated learning system.

1. Introduction

Flamingo addresses the cost and reliability challenges of applying single-round secure aggregation repeatedly in federated learning. It reuses setup secrets across rounds, limits post-submission interactions to a few decryptors, and reports faster training than repeated BBGLR.

1. Introduction

  • Single-round protocols face costly fresh setup when repeated, while federated learning also involves high-dimensional inputs, many clients, multiple rounds, and unstable devices.Individual model weights can leak information about raw data, motivating secure aggregation.Source: §1 · p. 1
  • Flamingo uses a one-time setup whose secrets can be reused across multiple sums, with clients masking each round’s inputs before sending them to the server.The server aggregates masked inputs, then a small randomly chosen group of decryptors helps remove the masks.Source: §1 · pp. 1–2
  • With fewer server-client interaction steps, Flamingo’s results include more clients than prior work under fixed failure probabilities and network conditions.The design requires all-client contact to collect inputs, while later interactions involve only a few decryptors.Source: §1 · p. 2
  • Only a small number of clients are contacted to remove masks, allowing other clients to leave after submitting their inputs without harming the result.This lightweight dropout-resilience mechanism reduces the need for clients to remain available throughout a round.Source: §1 · p. 2
  • Clients can unilaterally determine which pairwise masks to use in each round, rather than relying on the server to select their mask relationships.This graph-generation procedure changes how Flamingo chooses the client neighborhood used for masking.Source: §1 · p. 2
  • 3× faster than BBGLR for a 10-round pure summation task; Extended MNIST convergence took about 40 minutes versus roughly 3.5 hours to reach the same training accuracy.The 10-round comparison includes Flamingo’s one-time setup cost.Source: §1 · p. 2

2. Problem Statement

The section formalizes federated learning as repeated secure sums over randomly selected clients’ inputs, while accounting for dropouts, communication assumptions, and a static malicious adversary. It states Flamingo’s resilience and security properties and notes that correctness of malicious inputs is out of scope.

2. Problem Statement

  • The server seeks a secure sum of each round’s selected clients’ private weight vectors, then normalizes it into average weights; with dropouts, the goal is the largest possible contributing subset.Training repeats this process until convergence.Source: §2 · p. 2

2.1. Target deployment scenario

  • The target setting has 100K–10M total clients, 50–5,000 participants per round, 500–10,000 rounds, and heterogeneous devices that may stop responding.The surveyed input vectors typically have 1K–500K entries.Source: §2.1 · p. 2

2.2. Communication model

  • Client-server channels are private and authenticated; client-to-client messages are forwarded through the server with end-to-end encryption and authentication.Source: §2.2 · p. 2

2.3. Failure and threat model

  • The model includes honest dropouts and a static malicious adversary controlling the server and up to an η fraction of clients; Flamingo requires δD + ηD < 1/3.The malicious set stays fixed across rounds, while malicious clients may also drop out.Source: §2.3 · pp. 2–3

2.4. Properties

  • With all parties following the protocol, the server gets inputs from all online selected clients; against a malicious adversary, it learns a sum containing at least a 1 − δ − η fraction of selected clients.The section also defines sum accuracy as the fraction of selected clients represented in the final sum; unlike Flamingo, BBGLR may leak sums over multiple client partitions.Source: §2.4 · p. 3
  • Ensuring correctness against malicious client inputs is out of scope; bogus weights could produce a bad model, and strong guarantees against such inputs remain an open problem.Source: §2.4 · p. 3

3. Background

BBGLR provides dropout-resilient secure aggregation for a single round, using pairwise masks and secret sharing to recover masks after clients drop out. Repeating it for federated learning requires costly fresh setup and raises multi-round security concerns.

3.1. Cryptographic building blocks

  • PRGs expand seeds into pseudorandom strings, while PRFs derive pseudorandom outputs from keyed inputs.The section also introduces Shamir secret sharing and Diffie-Hellman key exchange as cryptographic building blocks.Source: §3.1 · pp. 3–4

3.2. The BBGLR protocol

  • BBGLR masks each client’s input with pairwise and individual masks, then reconstructs masks for offline and online clients to recover the sum.Recovery succeeds when enough neighbors provide the requested shares.Source: §3.2 · p. 4
  • Malicious servers can give clients inconsistent dropout labels to recover both mask types, while incorrect shares can cause reconstruction failure despite BBGLR’s hash check.BBGLR adds a neighbor consistency check against inconsistent labels, but insufficient error-correction threshold can still prevent reconstruction.Source: §3.2 · pp. 4–5

3.3. Using BBGLR for federated learning

  • BBGLR is designed for one aggregation round, so using it throughout federated learning requires a fresh, costly setup each round as client participation changes and masks cannot be reused.Its multi-round threat model also requires a semi-honest server during setup or costly per-round PKI key updates.Source: §3.2 · p. 4, §3.3 · p. 5

4. Efficient Multi-Round Secure Aggregation

Flamingo combines encrypted per-round mask seeds, threshold decryption, and locally generated round-specific graphs to support multi-round secure aggregation without repeating setup. Its protocol uses decryptors for recovery and cross-checking, rotates them for load balancing, and adds a defense against inconsistent models.

4.1. High-level ideas

  • Decryptors use encrypted mask seeds to recover masks for dropout clients, avoiding recovery requests to nearly all clients and adding only small ciphertexts to large input vectors.Clients submit masked vectors and seed ciphertexts; decryptors recover the relevant seeds through distributed decryption.Source: §4.1 · pp. 5–6
  • Long-term pairwise secrets derive fresh per-round mask seeds, while a shared random string lets clients locally generate neighbors in each round’s graph.The graph-generation communication cost is independent of γ, and ϵ is chosen so each round’s graph is connected with high probability.Source: §4.1 · p. 6

4.3. Setup phase

  • The setup distributes shared randomness and selects decryptors to run a modified DKG; parties may abort if the server’s message proxying prevents agreement on a valid key.The PKI stores clients’ public keys for pairwise-secret derivation, authenticated encryption, and signature verification.Source: §4.3 · p. 7, §4.2 · p. 7

4.4. Collection phase

  • Each collection round reports masked vectors and encrypted mask seeds, then decryptors cross-check client labels and graph conditions before reconstructing the masks.Decryptors abort unless the online clients meet the required fraction, form a connected graph, and have enough online neighbors.Source: §4.4 · p. 8

4.5. Malicious labeling across rounds

  • Decryptors bind ciphertexts and signed online/offline labels to the round number, helping prevent a malicious server from combining masks across different rounds.The cross-check ensures decryptors agree on the round number.Source: §4.5 · p. 8

4.6. Load balancing across decryptors

  • Decryptor duties rotate every R rounds, with proactive share updates to prevent an adversary from combining corrupt shares across transitions.The transition can also change the number of decryptors and the threshold; R is for load balancing, not dropout resilience or security.Source: §4.6 · pp. 8–9

4.7. Considerations in federated learning

  • Clients append the received model’s hash to per-round pairwise-mask seeds, so masks cancel when all clients receive the same model and do not otherwise.The paper describes this as a defense against a server sending inconsistent models, without overhead.Source: §4.7 · p. 9

5. Parameter Selection and Security Analysis

Flamingo’s parameter choices and security guarantees are stated under explicit dropout, corruption, graph-connectivity, and cryptographic assumptions. The full protocol provides dropout resilience and securely realizes its ideal functionality against a static malicious adversary.

5. Parameter Selection and Security Analysis

  • The parameter set includes N, T, per-round participant counts, threat-model quantities, security parameter κ, graph parameter ϵ, and decryptor count L.The stated collection-phase reconstruction condition is 2δD + ηD < 1/3.Source: §5 · p. 9, §5.2 · p. 9

5.1. Security of setup phase

  • Setup-phase security holds when δD + ηD < 1/3, assuming a PKI, trusted randomness, DDH, and the stated communication model.The theorem covers a malicious server and an η fraction of malicious clients.Source: §5.1 · p. 9

5.2. Security of collection phase

  • For collection, graph generation must ensure connectivity after removing dropout and malicious clients; the required lower bound on ϵ is deferred to Appendix C.The protocol’s ideal functionality allows an adversarially chosen set Mt, rather than the actual dropout set Ot, to determine the sum when the server is corrupted.Source: §5.2 · p. 9, §5.3 · p. 10

5.3. Main theorems

  • If 2δD + ηD < 1/3 and at most a δ fraction of clients drop out in a round, ΦT outputs the sum of non-dropped inputs except with probability 2^(−κ).This dropout-resilience theorem assumes all parties follow the protocol.Source: §5.3 · p. 10
  • Under 2δD + ηD < 1/3 and ϵ ≥ ϵ*(κ), ΦT securely realizes Fmal against a static malicious server and η fraction of clients, except with probability at most Tn · 2^(−κ+1).The theorem assumes a PKI, trusted initial randomness, PRG, PRF, asymmetric and symmetric authenticated encryption, and signatures; ElGamal permits basing security on DDH.Source: §5.3 · p. 10

6. Implementation

The implementation integrates Flamingo into a high-fidelity simulator and instantiates its cryptographic operations with standard primitives. It also uses shared reconstruction coefficients to parallelize decryption work.

Implementation

  • The code uses AES counter mode for the PRG, AES-GCM for authenticated encryption, and ECDSA over P-256 for signatures.The implementation is 1.7K lines of Python; BBGLR is 1.1K lines.Source: §6 · p. 10

Distributed decryption

  • Flamingo’s distributed decryption uses threshold ElGamal: the secret key is shared among L parties and is never reconstructed.Decryption tolerates dropouts when more than ℓ parties respond, and Alice communicates with each party once.Source: §6 · p. 10
  • The implementation uses ElGamal over P-256, mapping PRF outputs to curve points with hash-to-field and SSWU before hashing them with SHA256.The server decrypts the points and hashes them to recover the same pairwise-mask PRG input.Source: §6 · pp. 10–11

Optimizations

  • Flamingo’s reconstruction uses one set of interpolation coefficients for all shares and applies the resulting linear combinations in parallel.The server may use only the threshold number of shares; BBGLR computes separate coefficient sets for each client.Source: §6 · p. 11

Simulation framework

  • The implementation integrates Flamingo into ABIDES, a high-fidelity simulator supporting tens of thousands of clients and configurable pairwise network latencies.ABIDES is described as an open-source simulator designed for AI research in financial markets.Source: §6 · p. 11

7. Asymptotic Costs

Flamingo uses fewer client-server round trips per summation than BBGLR, while their total asymptotic communication costs are similar. Its reconstruction step also waits on a smaller responder group.

Communication costs

  • 6 round trips for BBGLR versus 3 for Flamingo per summation; Flamingo’s report step involves all selected clients, while its other two steps contact decryptors.The text notes that round-trip latency and tail latency can materially affect aggregation runtime.Source: §7 · p. 11

Client and server costs

  • Flamingo’s reconstruction needs responses from only 1/3 of decryptors, whereas BBGLR waits for the vast majority of clients.This is presented as a reason Flamingo is expected to wait less during reconstruction.Source: §7 · p. 11
  • Flamingo and BBGLR have similar total asymptotic costs over T rounds, but their numbers of round trips differ substantially.A decryptor in Flamingo additionally incurs O(δAnt + (1 − δ)nt + ϵn_t^2) computation in round t.Source: §7 · p. 11

8. Experimental Evaluation

The evaluation measures communication, computation, and completion time for secure aggregation, then tests full-session training on EMNIST and CIFAR100. It reports lower running time than BBGLR and compares model accuracy with non-private training.

8.1. Experimental environment

  • The evaluation used ABIDES network-delay simulation, and the authors identify client-server round trips as a key contributor to end-to-end completion time, especially for geodistributed clients.The simulated setup used a 21-microsecond to 53-millisecond base-delay range with default jitter.Source: §8.1 · p. 12

8.2. Secure aggregation costs and completion time

  • Per-round total communication was similar, while Flamingo’s computation costs were slightly higher; network delay made those added costs negligible to completion time.Flamingo’s report step has slightly higher client and server costs, and its reconstruction step slightly higher server cost.Source: §8.2 · pp. 12–13, Figure 6 · p. 12, Figure 7 · p. 12
  • On 1K clients, Flamingo completed aggregation 3× faster than BBGLR, including its one-time setup and one secret key transfer.Less frequent key transfers would make the improvement more significant.Source: Figure 8 · p. 13, §8.2 · p. 13
  • With the same starting number of clients, Flamingo achieved better sum accuracy than BBGLR; the gap grew with shorter waiting times.Shorter waits excluded more clients at each step.Source: §8.2 · p. 13, Figure 8 · p. 13

8.3. Feasibility of a full private training session

  • EMNIST and CIFAR100 did not converge until about rounds 150 and 200, respectively, though accuracy continued to improve slightly afterward.The evaluation used 128 clients and δ = 1%.Source: §8.3 · pp. 13–14
  • 5.5× lower running time than BBGLR on EMNIST and 4.8× on CIFAR100; versus the non-private baseline, running time was 1.4× and 1.7× higher, respectively.The running-time comparisons cover full training sessions.Source: Figure 10 · p. 14, §8.3 · p. 14
  • Flamingo’s integer encoding did not measurably affect final-model accuracy compared with floating-point FedAvg on the same datasets.The accuracy metric is TensorFlow’s sparse categorical accuracy score.Source: §8.3 · p. 14, Figure 10 · p. 14

9. Extension with robustness

The extension adds detection of malicious-client behavior but does not guarantee output delivery. If it terminates, it returns the correct sum; otherwise, it can abort and detect an incorrect output.

9. Extension with robustness

  • The extension detects malicious-client behavior but, like BBGLR, does not provide guaranteed output delivery.The extension is described in Appendix E.1.Source: §9 · p. 14
  • If it terminates, the extension outputs the correct sum of participating clients’ inputs; otherwise, it aborts and detects an incorrect output, but cannot identify the malicious client.Source: §9 · p. 14
  • The authors say this security notion is not practically meaningful currently because malicious clients can provide arbitrary inputs; it could matter if input validity can be confirmed.They cite possible input-validation mechanisms as future context.Source: §9 · p. 14

10. Related Work

The related-work discussion compares pairwise masking with MPC and homomorphic-encryption approaches for private sums. It also contrasts Flamingo with a separate multi-round protocol that uses reusable secrets.

Pairwise masking

  • Pairwise masking uses pairwise masks to hide individual inputs while supporting efficient vector encryption and server summation; Flamingo reduces round-trip complexity across multiple sums.BBGLR is identified as the state-of-the-art in this line of work.Source: §10 · p. 14

MPC

  • Secret-sharing MPC can tolerate dropouts, but high communication makes it a poor fit for large federated-learning inputs.Non-interactive addition protocols require many zero shares for long vectors, cannot reuse those shares across rounds, and are not resilient to even one dropout.Source: §10 · pp. 14–15

Additively homomorphic encryption

  • Threshold additive homomorphic encryption requires clients to encrypt vectors and a committee to decrypt the aggregate, which is expensive for large inputs.The passage names Paillier and lattice-based schemes as examples.Source: §10 · p. 15
  • An LWE-based homomorphic PRG approach has higher computation and communication costs than pairwise-masking works, including Flamingo, due partly to large required moduli.Source: §10 · p. 15

Multi-round setting

  • A separate multi-round protocol with reusable secrets suits small input domains but requires brute-force discrete-log decryption for large domains; Flamingo has no input-domain restriction.A variant supports arbitrary domains using DDH-based class groups, a more involved assumption than DDH.Source: §10 · p. 15

11. Discussion

The discussion identifies boundaries in client participation, adversary behavior, and the residual privacy leakage of secure aggregation. It also notes that Flamingo can aggregate functions beyond sums using affine aggregatable encodings.

11. Discussion

  • Flamingo can compute max/min as well as sums using affine aggregatable encodings.Source: §11 · p. 15
  • The training-session client set is fixed in advance; handling clients that dynamically join remains unexplored.Source: §11 · p. 15
  • Flamingo assumes a static adversary across rounds; adaptive changes to compromised parties during execution remain uninvestigated.The discussion notes that within-round adaptive adversaries have not been considered in the federated-learning setting.Source: §11 · p. 15
  • Secure aggregation reduces but does not eliminate input leakage, and a cited attack can recover overall training-data label proportions.The discussion also reports a bound finding that leakage reduces linearly with the number of clients.Source: §11 · p. 15

Appendix A. Failure and threat model details

  • The corrupted-client rate among decryptors, ηD, is not assumed equal to the overall rate η because the decryptor set is small.By contrast, the corrupted fraction in the larger contributor set can be considered equal to η.Source: Appendix A · p. 18

B.2. Setup phase and distributed key generation

The setup establishes distributed keys and shares, while collection uses decryptors to support aggregation across rounds. The appendix describes transferring shares between decryptor sets and selecting their size to bound corruption risk.

B.2. Setup phase and distributed key generation

  • With δD + ηD < 1/3, ΠDKG satisfies the stated correctness and security properties against a malicious server and up to ηD fraction of malicious participants.Honest parties may abort or finish without shares; the server can still decrypt because malicious parties hold shares.Source: §B.2 · p. 19

B.3. Collection phase

  • At each collection round, the server notifies the selected clients St, who can fetch neighbors’ public keys and pre-fetch keys for coming rounds to reduce runtime.Source: §B.3 · p. 20

B.4. Transfer shares

  • When decryptor shares are transferred, the new set combines reshared evaluations; under ηD + δD < 1/3 for both sets, the DKG correctness and security argument applies.A malicious adversary learns no information but can cause aborts.Source: §B.4 · pp. 20, 22

C.1. The number of decryptors

  • For η = δD = 1%, L = 60 gives a 1.6 × 10−5 probability, while L = 120 gives 2.6 × 10−10 probability.These probabilities concern the decryptor set meeting the required corruption bound.Source: §C.1 · p. 22

C.2. Proof of Lemma 1

This material bounds random-graph disconnection and outlines the ideal-world security analysis for setup and collection. It also states a dropout condition under which online decryptors can reconstruct secrets.

C.2. Proof of Lemma 1

  • For n = 1024, ϵ ≥ 0.02 keeps the stated failure probability below 10−6, requiring at least 41 neighbors when δ = η = 0.01.The probability bound is depicted in Figure 14.Source: §C.2 · p. 22, Figure 14 · p. 22

D.1. Security definition

  • Secure realization requires a simulator whose real-world and ideal-world execution output distributions are statistically or computationally indistinguishable.Source: §D.1 · p. 22

D.2. Ideal functionalities

  • The proof defines ideal functionalities for Flamingo, setup, and a single collection round, and models initial randomness with Frand.Frand returns a uniform value in {0, 1}λ, where λ is the PRG-seed length.Source: §D.2 · p. 22

D.3. Proof of Theorem 1

  • When the server is honest, the communication model is equivalent to secure broadcast and Πsetup securely realizes Fsetup; for a corrupted server, the proof simulates its view.The simulator aborts if it does not receive 2ℓ+1 valid signatures on the specified public keys.Source: §D.3 · pp. 22–23

D.4. Proof of Theorem 2

  • If 2δD + ηD < 1/3, online decryptors can reconstruct the secrets despite the modeled setup and collection-round dropouts.Source: §D.4 · p. 23

D.5. Proof of Theorem 3

The proof establishes single-round security through a sequence of hybrids, then bounds failures across rounds. The robust extension adds checks that detect incorrect outputs and fix client inputs after submission.

D.5. Proof of Theorem 3

  • The simulator replaces honest clients’ masks and inputs with random masks and zero vectors in hybrids that preserve the adversary’s view.The proof assumes a random oracle for the group-to-mask mapping; it also uses ElGamal and symmetric-encryption security to justify indistinguishability.Source: §D.5 · p. 24
  • With δD + ηD < 1/3, Πsum securely realizes F(t) except with probability at most n · 2^-κ+1.The simulation can fail if the graph disconnects or a client has only malicious online neighbors; across T rounds, the stated failure probability is Tn2^-κ+1.Source: §D.5 · pp. 24–25
  • The multi-round proof treats per-round pairwise masks as PRF outputs indexed by round, reducing distinguishability between rounds to breaking PRF security.It also programs the random oracle so CHOOSESET outputs the selected client sets.Source: §D.5 · p. 25

E.1. Robust protocol

  • Πsum-robust fixes client inputs after the report step and lets an honest server detect incorrect outputs caused by malicious clients.A proof of decryption lets the server exclude bogus partial decryptions; at least 2ℓ + 1 honest online decryptors suffice to reconstruct the result.Source: §E.1 · p. 25
  • The robust protocol verifies proofs of masking and uses distributed key correctness to check that recovered masks match the committed masks.It also encrypts individual mask seeds with ElGamal and has decryptors prove correct decryption.Source: §E.1 · p. 25

E.2. Security proof

Theorem 4 proves security for the robust Flamingo extension under stated threat-model and cryptographic assumptions. Its proof uses a simulator and hybrids to relate real and ideal executions.

E.2. Security proof

  • When 2δD + ηD < 1/3 and ϵ ≥ ϵ*(κ), ΨT securely computes Fmal-robust except with probability Tn · 2^-κ+1.The theorem assumes the listed cryptographic primitives and permits a static malicious adversary controlling the server and specified client fractions.Source: §E.2 · p. 26
  • The simulator includes the DKC step and sends abort to the ideal functionality if DKC aborts.The proof concludes that ΨT securely realizes Fmal-robust in the random oracle model.Source: §E.2 · p. 26
  • The simulator replaces honest clients’ masks with random masks and their inputs with zeros, while preserving the adversary’s view across the hybrids.The proof also replaces honest decryptors’ labels with offline/online labels obtained from Rdrop.Source: §E.2 · p. 26

Related papers

Loading 2308.09883v4…