Source-linked AI summary
FastSecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning
Swanand Kadhe, Nived Rajaraman, O. Ozan Koyluoglu, Kannan Ramchandran
TL;DR
Federated-learning updates can leak private training information, while existing secure aggregation protocols may be costly at the scale and dimensionality of modern FL. The paper introduces FastShare, an FFT-based multi-secret sharing scheme, and FastSecAgg, which uses it to provide strong privacy, dropout robustness, lower computation, and orderwise-competitive communication. The guarantees include security against adaptive adversaries and recovery despite random constant-fraction dropouts.
Problem
Federated-learning model updates can leak training data, while existing secure aggregation protocols incur high computation or communication costs and face dropout challenges at scale.
Method
FastSecAgg uses FastShare, an FFT-based multi-secret sharing scheme designed for federated learning and supporting information-theoretic privacy with tunable dropout and security parameters.
Results
FastSecAgg reduces computation costs, preserves orderwise communication costs when L exceeds N, tolerates random constant-fraction dropouts, and secures against adaptive adversaries.
Takeaways & Limitations
FastShare provides a cryptographic primitive for scalable secure aggregation and potentially other secure multi-party computation applications.
Takeaways & Limitations
The paper focuses on honest-but-curious clients and servers and leaves Byzantine-client secure aggregation as future work.
Abstract
from arXiv · showhide
Recent attacks on federated learning demonstrate that keeping the training data on clients' devices does not provide sufficient privacy, as the model parameters shared by clients can leak information about their training data. A 'secure aggregation' protocol enables the server to aggregate clients' models in a privacy-preserving manner. However, existing secure aggregation protocols incur high computation/communication costs, especially when the number of model parameters is larger than the number of clients participating in an iteration -- a typical scenario in federated learning. In this paper, we propose a secure aggregation protocol, FastSecAgg, that is efficient in terms of computation and communication, and robust to client dropouts. The main building block of FastSecAgg is a novel multi-secret sharing scheme, FastShare, based on the Fast Fourier Transform (FFT), which may be of independent interest. FastShare is information-theoretically secure, and achieves a trade-off between the number of secrets, privacy threshold, and dropout tolerance. Riding on the capabilities of FastShare, we prove that FastSecAgg is (i) secure against the server colluding with 'any' subset of some constant fraction (e.g. $\sim10\%$) of the clients in the honest-but-curious setting; and (ii) tolerates dropouts of a 'random' subset of some constant fraction (e.g. $\sim10\%$) of the clients. FastSecAgg achieves significantly smaller computation cost than existing schemes while achieving the same (orderwise) communication cost. In addition, it guarantees security against adaptive adversaries, which can perform client corruptions dynamically during the execution of the protocol.
1 INTRODUCTION
Federated learning keeps training data on clients, but shared model updates can still leak sensitive information, motivating secure aggregation. FastSecAgg addresses scalability and dropout challenges with FastShare, achieving strong privacy, efficient computation, and orderwise-competitive communication.
- Federated learning coordinates clients and a central server to train a shared model while keeping training data on clients’ devices.
- Model updates can leak information about training data through inference, inversion, or memorization attacks despite local data retention.The paper notes that even well-generalized deep models can leak training information, while some generative models may memorize sensitive data.
- Secure aggregation lets the server compute the sum of clients’ updates without learning any individual update and can compose with differential privacy.
- Existing protocols face massive participation, high-dimensional updates, dropouts, and a trade-off between computational or communication costs and privacy guarantees.The paper cites up to 10,000 participating users, model sizes reaching hundreds of millions of parameters, and dropouts of up to 10%.
- Naively applying Shamir secret sharing to length-L updates from N clients incurs O(LN^2) communication and computation, which is intractable at federated-learning scale.
- FastShare uses a finite-field FFT to share multiple secrets, providing information-theoretic security against a constant client fraction and recovery after random constant-fraction dropouts.For example, thresholds near 10% are supported, with O(N log N) recovery complexity and a trade-off between privacy and dropout parameters.
- FastSecAgg builds on FastShare and relaxes dropout guarantees from worst-case to random because privacy threats are adversarial whereas natural dropouts are non-adversarial.
- FastSecAgg requires O(L log N) computation per server and client, with server communication O(LN + N^2) and client communication O(L + N).When L exceeds N, its communication cost matches prior works orderwise while reducing server computation cost.
2 PROBLEM SETUP AND PRELIMINARIES
The paper models one federated-learning iteration as secure aggregation among clients and a server under an honest-but-curious threat model with collusion and random dropouts. It formalizes client updates, communication assumptions, and cryptographic preliminaries used by the protocol.
- 2.1 Federated Learning: Each client’s expected loss is defined over its local data distribution, and federated learning aims to minimize the sum of client losses.
- 2.1 Federated Learning: FedAvg selects N clients per iteration, initializes each local model from the current server model, and performs T mini-batch stochastic-gradient steps.
- 2.1 Federated Learning: Clients send model updates, which the server aggregates into the next global model; updates may be compressed and quantized before transmission.
- 2.1 Federated Learning: The protocol’s objective is to let the server securely compute the aggregate of clients’ updates for one FedAvg iteration.
- 2.2 Treat Model: The honest-but-curious model assumes parties follow the protocol while trying to learn other parties’ model updates from exchanged messages.
- 2.2 Treat Model: The server may collude with up to T selected clients, while a random subset of up to D clients may drop out during secure aggregation.
- 2.3 Cryptographic Preliminaries: Clients establish pairwise shared keys through a key-agreement protocol, and authenticated encryption provides confidentiality and message integrity.
3 FASTSHARE: FFT BASED SECRET SHARING
FastShare is a linear, information-theoretically secure multi-secret sharing scheme that uses finite-field FFTs and CRT-based layouts to generate shares and reconstruct secrets despite random client dropouts. Its design trades the number of secrets, privacy threshold, and dropout tolerance for O(N log N) computation.
- Scheme definition: FastShare forms the core of FastSecAgg as a linear multi-secret sharing scheme over a finite field, with privacy, dropout-resilience, and reconstruction requirements.It shares S field elements among N clients, while coalitions of up to T clients learn no information and random dropouts of up to D clients can be tolerated.
- Share generation: FastShare constructs a length-N signal by placing secrets and zeros at selected CRT-grid locations, filling remaining locations with independent random masks, then applying a finite-field FFT.The resulting Fourier coefficients are the client shares.
- Secret reconstruction: FastRecon first iteratively recovers missing shares using parity-check constraints induced by zero placement, then applies the inverse Fourier transform to obtain the secrets.The parity checks arise across rows and columns of the CRT-based 2D grid, enabling recovery from random missing shares.
- Security and trade-offs: S = (1−α)(1−2β)(1−δ0)(1−δ1)N secrets are generated with T = αβ(1−δ0)(1−δ1)N privacy and D = (1−(1−δ0)(1−δ1))N^2 dropout resilience.These parameters are accompanied by linearity guarantees.
- Security and trade-offs: For α = 1/2, β = 1/4, and δ0 = δ1 = 1/10, FastShare achieves S = 0.2N, T = 0.1N, and D = 0.095N.The example illustrates the scheme’s explicit trade-off among secret capacity, privacy threshold, and dropout tolerance.
- Efficiency: O(N log N) computation is achieved for FastShare and parallelized FastRecon through signal construction, FFTs, and iterative row-or-column recovery.A variant removes the parallelism requirement for sufficiently large N while retaining O(N log N) computation.
4 FASTSECAGG BASED ON FASTSHARE
FastSecAgg securely aggregates clients’ model updates by combining encrypted FastShare shares with a three-round protocol that reconstructs the aggregate despite random client dropouts.
- Protocol overview: Each client partitions its length-L update into vectors of at most S elements and treats each vector as S secrets for FastShare.FastShare produces shares that clients distribute through the server.
- Protocol overview: Clients encrypt pairwise shares before sending them through the server, preventing the server from reconstructing individual secrets.Shared keys are derived through key agreement and used to encrypt addressed shares.
- Protocol overview: Each surviving client decrypts and sums its received shares, then sends the resulting sum-share to the server in plaintext.FastShare linearity makes each sum-share a share of the aggregate secret vectors.
- Protocol overview: The server waits for sufficient responses and applies reconstruction to recover the aggregate, aborting if reconstruction fails for any update block.The protocol requires at least N − D responding clients in each relevant round.
- Protocol rounds: FastSecAgg uses three rounds: advertising keys, generating shares, and recovering the aggregate update.The protocol specification names these rounds Round 0, Round 1, and Round 2.
5 ANALYSIS
The analysis establishes FastSecAgg’s correctness, privacy, and efficiency, while comparing its cost and adversary robustness with prior secure aggregation protocols.
- Correctness and security: With at most D random client dropouts, FastSecAgg obtains the aggregate without aborting with probability at least 1 − 1/poly N.The probability is over the randomness in the dropouts.
- Correctness and security: FastSecAgg hides honest clients’ updates from the server colluding with up to T clients, beyond information inferable from the aggregate output.The guarantee holds irrespective of how and when clients drop out in the honest-but-curious setting.
- Efficiency: Each client has O(max{L, N} log N) computation and O(max{L, N}) communication cost.The costs include share generation, encryption or decryption, share addition, and transmission of N − 1 shares.
- Efficiency: The server has O(max{L, N} log N) computation and O(N max{L, N}) communication cost.Server computation includes recovering missing sum-shares and applying an inverse FFT.
- Comparison with prior works: Compared with TurboAgg and SecAgg+, FastSecAgg uses three rounds, O(L) per-client communication, and supports adaptive adversaries, though SecAgg+ has lower absolute communication.FastSecAgg’s server computation is smaller than SecAgg+ when L = Ω(N), with the same orderwise per-client communication cost.
- Scope: The paper focuses on honest-but-curious clients and servers and leaves secure aggregation against Byzantine clients as future work.Other cited works address settings where a fraction of clients are Byzantine.
A FINITE FIELD FOURIER TRANSFORM
The finite-field Fourier transform maps a length-N signal over F_q into a spectrum and provides an inverse mapping; subsampling causes frequency-domain aliasing, while circular shifts cause phase shifts.
- DFT and inverse DFT: For a finite field F_q with a primitive N-th root of unity ω, the DFT maps a length-N vector x to a length-N spectrum X.The transform is generated by ω and operates over F_q.
- DFT and inverse DFT: The inverse transform reconstructs the time-domain signal from the frequency-domain spectrum using powers of ω^-ij.The paper distinguishes x as the time-domain signal and X as the spectrum.
- Sampling and shifts: Subsampling a signal in the time domain mixes, or aliases, its frequency components according to the sampling period.For a period n dividing N, the shorter DFT of the subsampled signal is related to the original N-length DFT.
- Sampling and shifts: A circular time-domain shift produces a frequency-domain phase shift, multiplying the j-th frequency component by ω^-tj.The relation is stated for a circular shift by t.
B PROOF OF LEMMA
The lemma proof combines finite-field aliasing and circular-shift properties to characterize transformed, shifted, and subsampled signals whose time-domain entries are zero.
- Proof setup: The proof defines shifted-and-subsampled signals x^(v)(↓n_i) and their shorter DFTs X^(v)(↓n_i).The shift index v ranges over the designated erasure-related positions.
- Proof setup: It applies the aliasing property to relate each shorter DFT component to components of the original spectrum.The relation is indexed by v and c for each sampling factor n_i.
- Proof steps: The circular-shift property supplies phase factors ω^-vj for the original frequency components.These factors are substituted into the aliasing relation.
- Proof steps: Because the constructed shifted-and-subsampled signals are zero vectors, their DFTs are also zero, yielding the stated constraints after simplification.The resulting identities hold over the specified ranges of u, v, and c.
C ANALYSIS OF FASTSHARE
FastShare’s analysis establishes dropout tolerance and information-theoretic security through product-code decoding and DFT/CRT-based linear algebra. The proof characterizes security by a rank condition and verifies it using grid shifts and span arguments.
- Dropout tolerance: FastShare recovers all shares from a random subset of N−D shares with probability at least 1−polyN, giving dropout tolerance D=(1−(1−δ0)(1−δ1))N.The recovery argument uses iterative peeling decoding on the product-code structure formed by FastShare’s shares.
- Information-theoretic security: The information-theoretic security condition is reduced to a linear-algebraic rank condition on submatrices of a DFT-derived matrix G.Shares are represented as X=G[s m]^T, with secrets s and uniformly random masks m.
- CRT grid proof: FastShare maps indices to a 2D grid via the Chinese remainder theorem, enabling the rank proof to use horizontal and vertical shifts of column sets.The CRT representation is compatible with the DFT structure and preserves span relations under shifts.
- Information-theoretic security: Security requires rank(G2)=rank(GP) for every colluding set P of size at most T=αβ(1−δ0)(1−δ1)N.This condition makes the secret columns lie in the span of mask columns, preventing the observed shares from reducing secret entropy.
- CRT grid proof: The proof constructs sets B, Y, C, Q, and L around the first dependent point, then propagates span relations by induction.The induction establishes Y⊆span(C), while the figures illustrate the relevant grid-set inclusions.
D CORRECTNESS OF FASTSECAGG
FastSecAgg correctness follows from secure key agreement, authenticated encryption, and FastShare’s linearity and dropout tolerance. Clients aggregate shares of partitioned inputs, and FastRecon recovers the aggregate when enough clients survive.
- Correctness foundation: FastSecAgg correctness combines key-agreement and authenticated-encryption correctness with FastShare’s linearity and D-dropout tolerance.These properties support the protocol’s message processing and reconstruction steps.
- Share aggregation: FastShare’s linearity makes each sum of shares a share of the sum of the corresponding client inputs.This lets the server reconstruct an aggregate rather than reconstructing each client input separately.
- Dropout recovery: At least N−D surviving clients in Round 2 provide the sum-shares needed for FastRecon’s dropout-tolerant reconstruction.The surviving clients form a random subset, matching FastShare’s reconstruction guarantee.
- Dropout recovery: FastRecon succeeds with probability at least 1−1/poly N for every input partition, and the aggregate reconstruction then succeeds with the same probability.The protocol avoids a union bound because all partitions share the same missing-index pattern.
E SECURITY OF FASTSECAGG
FastSecAgg’s security proof shows that threshold-limited shares reveal no information about client inputs and uses a hybrid argument to construct a simulator. The resulting protocol execution is computationally indistinguishable from the simulated execution.
- Partitioned sharing: FastSecAgg partitions each client input into ⌈L/S⌉ vectors and independently applies FastShare to each partition.Each instantiation uses private randomness, so the joint share distribution factors across partitions.
- Input privacy: For any set P of at most T clients, the shares they receive reveal no information about a client input.For every ui and vi, the corresponding share distributions observed by P are identical.
- Hybrid proof: The security proof begins with the real execution and replaces key-agreement operations with simulated ones through computationally indistinguishable hybrids.The hybrid sequence uses the security of the key-agreement protocol and FastShare’s privacy properties.
- Hybrid proof: A PPT simulator samples the final hybrid from z and the relevant client sets, yielding a view computationally indistinguishable from the real protocol output.The simulator’s distribution is computed from z, uM, C0, C1, and C2.
F COMPARISON OF FASTSHARE WITH SHAMIR’S SCHEME AND RELATION TO LOCALLY RECOVERABLE CODES
FastShare differs from Shamir’s multi-secret sharing by arranging zeros to create a product-code structure, rather than using a single Reed–Solomon codeword. The paper also relates a FastShare variant to locally recoverable codes.
- Comparison with Shamir’s scheme: Shamir’s multi-secret scheme uses a degree-(S+T−1) polynomial with S secrets and T random masks, recovering secrets from any S+T shares.Its N shares form a Reed–Solomon codeword with dimension S+T.
- Comparison with Shamir’s scheme: Fast polynomial interpolation algorithms may have large hidden constants, limiting their scalability despite favorable asymptotic notation.This caveat is stated for the interpolation algorithms used in comparison with Shamir’s scheme.
- Comparison with Shamir’s scheme: FastShare evaluates a degree-(N−1) polynomial at primitive N-th roots of unity, producing a product-code codeword with Reed–Solomon component codes.This differs structurally from Shamir’s Reed–Solomon construction.
- Comparison with Shamir’s scheme: FastShare places zeros judiciously in the signal to ensure product-code structure, whereas Shamir concatenates secrets, masks, and zeros.The zero placement is the key constructional distinction described in the comparison.
- Relation to locally recoverable codes: A FastShare variant is related to locally recoverable codes with coordinate groups forming MDS codes of specified locality and dimension.The paper connects this variant to efficient LRC constructions.