Source-linked AI summary
Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errors
Timothy Stevens, Christian Skalka, Christelle Vincent, John Ring, Samuel Clark, Joseph Near
TL;DR
Federated learning must protect private training data without relying on a trusted central curator, yet secure aggregation can be computationally expensive. This paper presents FLDP, which combines differential privacy with LWE-based secure aggregation, and reports accurate models with practical training time and improved efficiency.
Problem
Federated training must protect sensitive user data because trained models can leak training information, while centralized collection requires trust in the server.
Source: §1 · p. 1Method
FLDP combines differential privacy with a secure aggregation protocol based on Learning With Errors, without requiring a trusted server.
Source: §1 · p. 1Results
FLDP achieves accuracy comparable to central-model differentially private approaches, reporting 95% on MNIST for ε ≤2 and 70% on CIFAR-10 for ε ≤4.
Source: §1 · p. 2Takeaways & Limitations
FLDP’s accurate federated models are trainable within a feasible time frame for practical applications, particularly where accuracy and low trust burdens matter.
Source: §7 · p. 13Protocol 4 is secure against semi-honest adversaries, but a malicious party can broadcast an incorrect sum and corrupt the final result.
Source: §4.4 · p. 7
Abstract
from arXiv · showhide
Federated machine learning leverages edge computing to develop models from network user data, but privacy in federated learning remains a major challenge. Techniques using differential privacy have been proposed to address this, but bring their own challenges -- many require a trusted third party or else add too much noise to produce useful models. Recent advances in \emph{secure aggregation} using multiparty computation eliminate the need for a third party, but are computationally expensive especially at scale. We present a new federated learning protocol that leverages a novel differentially private, malicious secure aggregation protocol based on techniques from Learning With Errors. Our protocol outperforms current state-of-the art techniques, and empirical results show that it scales to a large number of parties, with optimal accuracy for any differentially private federated learning scheme.
1 Introduction
Centralized training raises privacy, trust, and computational concerns, while federated learning can still expose private information through client updates. The paper introduces FLDP, combining differential privacy with efficient secure aggregation, and reports accuracy comparable to central-model approaches.
1 Introduction
- Centralized training burdens data centers and requires trust in the server; privacy-conscious users may withhold data, potentially affecting accuracy.Trained models can also leak information about their training data [37] [41].Source: §1 · p. 1
- Federated learning shifts training computation to the edge, but server-visible client updates may reveal training data [37] [41].Source: §1 · p. 1
- FLDP reduces communication expansion from 2x to 1.7x for 500 length-20,000 vectors and cuts server computation to a few seconds.Its security is based on LWE, with differential-privacy noise also serving as the LWE noise term.Source: §1 · p. 1
- The protocol targets scalable, efficient, accurate differentially private federated learning without requiring a trusted server.It combines distributed discrete Gaussian noise, gradient clipping, and secure aggregation.Source: §1 · p. 1
- The reported accuracy is 95% on MNIST for ε ≤2 and 70% on CIFAR-10 for ε ≤4, comparable to central-model differentially private deep learning.Source: §1 · p. 2
1.1 Contributions
- The contributions include malicious-secure aggregation, end-to-end FLDP for malicious clients and server, and analytic and empirical support for scalability and near-central-model accuracy.Source: §1.1 · p. 2
2 Overview
The paper frames distributed differentially private learning as a way to train without centralizing sensitive data, while noting that federated updates alone do not ensure privacy. It presents an efficient secure-aggregation protocol and outlines the paper’s subsequent analyses and experiments.
2 Overview
- The goal is a differentially private model without revealing private data to the server or other clients.Source: §2 · p. 2
2.1 Background: General Problem Setting
- Federated learning keeps training data local, but gradients sent to the server can still expose information; differential privacy adds noise to address model privacy.Local differential privacy protects clients against a malicious server but can add too much noise for useful deep neural network models [10].Source: §2.1 · p. 2
2.2 Efficient Secure Aggregation in the Differential Privacy Setting
- FLDP reduces client communication complexity to O(m+k) and server communication complexity to O(mk) for k parties and length-m vectors.Table 1 summarizes communication and computation complexities against prior approaches.Source: §2.2 · p. 3, Table 1 · p. 3
2.3 Paper Roadmap
- The paper proceeds from an ideal trusted-server functionality to LWE-based malicious-secure aggregation, then analyzes complexity and evaluates scalability and model accuracy.Source: §2.3 · p. 3
3 Differentially Private Federated Learning
This section adapts central-model differentially private SGD to distributed training by clipping and perturbing client gradients. Its trusted aggregation functionality is later implemented without a trusted third party.
3 Differentially Private Federated Learning
- The privacy analysis uses Rényi differential privacy and parallel composition over disjoint minibatches, with tighter analyses also applicable.Source: §3 · p. 3
3.1 FLDP: Distributed DP SGD
- The trusted-party functionality is replaced by an MPC protocol in Section 4.Source: §3.1 · p. 4
- FLDP adapts distributed SGD by having clients compute clipped, noise-perturbed gradients for aggregation and model updates.The approach uses per-example gradient clipping, following the central-model approach, and adds noise to satisfy differential privacy.Source: §3 · p. 3, §3.1 · p. 4
- The distributed noisy-batch-gradient functionality sums client gradients with Gaussian noise, yielding the same noisy gradient sum as the central model under a trusted third party.Source: §3.1 · p. 4
- Individual clients add only a fraction of the noise needed for meaningful privacy, so the guarantee depends on correctly summing their noise with gradients.This differs from local differential privacy, where each client adds sufficient noise on its own.Source: §3.1 · p. 4
7 F sends ˆG to the untrusted server
The distributed privacy analysis relies on aggregating client noise, but the initial functionality exposes risks under malicious behavior and requires a trusted third party. The paper describes MPC to remove that requirement under an honest-majority assumption.
7 F sends ˆG to the untrusted server
- The noisy gradient sum and its privacy accounting are derived under the trusted-third-party functionality.Source: §7 · p. 4
3.2 Security & Privacy Risks of FLDP
- Protocol 1's differential-privacy guarantee requires a trusted third party to execute Functionality 2.Source: §3.2 · p. 4
- Malicious clients can omit their required noise, weakening the privacy guarantee as their fraction grows.The analysis assumes an honest majority and relaxes the guarantee to a weaker form.Source: §3.2 · p. 4
- An MPC protocol is described to implement the functionality against an actively malicious server, assuming an honest majority of clients.Source: §3.2 · p. 5
- The privacy analysis must account for discrete Gaussian noise because the continuous-Gaussian sum property it relies on does not hold for discrete Gaussians.Source: §3.2 · p. 5
4 LWE-Based Secure Aggregation
The section replaces trusted-server gradient aggregation with a client-to-client secure aggregation protocol. LWE-based masks let the server aggregate encrypted vectors while residual error supplies differential-privacy noise, and the masking protocol reduces client communication.
4.3 LWE-Based Masking of Input Vectors
- LWE-based masks let clients send encrypted vectors for server aggregation, while MPC among clients computes the aggregate mask without revealing individual masks.The LWE decision problem makes the mask indistinguishable from a uniform vector; the aggregate masks cannot be perfectly reconstructed from their sum.Source: §4 · p. 5, §4.3 · p. 6
4 LWE-Based Secure Aggregation
- The residual errors in the aggregated vector sum are sufficient to satisfy (ε,δ)-differential privacy.The errors remain because individual masks cannot be perfectly reconstructed from their sum.Source: §4 · p. 5
4.1 Background: Learning with Errors
- LWE search asks for the secret from samples, while the decision problem distinguishes LWE samples from uniformly random pairs; under the stated conditions, the problems are equivalent.Regev’s result applies when q is prime and polynomial in n, with the stated error-distribution condition.Source: §4.1 · p. 5
4.2 Background: Multiparty Computation
- MPC lets independent data owners compute a shared output without revealing private inputs to one another or a third party.Here, the shared function is gradient aggregation, replacing a trusted third party in secure function evaluation.Source: §4.2 · p. 5
- FLDP uses packed Shamir sharing, whose packed variant improves communication efficiency by placing up to k −t −1 values in one set of shares.Shamir sharing supplies the additive homomorphic property used for secure vector aggregation.Source: §4.2 · pp. 5–6
4.3 LWE-Based Masking of Input Vectors
- Protocol 3 reduces client communication from O(log(q)mk) to O(log(q)(m+n+k)) by securely aggregating only a length-n vector.Each client sends its length-m masked vector once and uses packed secret sharing on the length-n vector.Source: §4.3 · pp. 6–7
4.4 Vector Aggregation
The section implements secure vector aggregation with packed Shamir sharing, then adapts reconstruction to detect maliciously broadcast sums. The verification uses extra shares and avoids communication among clients.
4.4 Vector Aggregation
- Protocol 4 uses packed Shamir sharing to aggregate the clients’ secret vectors, which are typically small (m ≤800).Each client shares packed portions of its vector; clients combine shares and reconstruct the summed vector.Source: §4.4 · p. 7
- Protocol 4 is secure against semi-honest adversaries, but a malicious client can broadcast an incorrect sum and cause an incorrect result.Traditional reconstruction may not detect this because corrupting a single share can change the reconstructed result.Source: §4.4 · p. 7
4.5 Malicious-Secure Vector Aggregation
- Reconstructing from subsets of t and t +1 shares and comparing the results detects cheating; disagreement makes clients abort.Applying this procedure to Protocol 4 yields malicious security, and the extra shares require no client-to-client communication.Source: §4.5 · p. 7
4.6 Security Analysis
The section states a simulator-based security analysis for Protocol 3 and describes the LWE parameterization used to assess security. It also outlines how gradients are encoded as finite-field elements for MPC.
4.6 Security Analysis
- Theorem 1 states that a PPT simulator exists for the security analysis of Protocol 3.The analysis considers client inputs and views, the server’s view, corrupt parties, and a maliciously secure aggregation protocol.Source: §4.6 · pp. 7–8
4.6.1 LWE parameters
- Each LWE parameter tuple (n,q,β) is evaluated for security, and Table 2 lists parameter choices with at least 128 bits of security.Here n is the secret dimension, q the field size, and βq the width of the error distribution.Source: §4.6.1 · p. 8
4.7 Encoding and Decoding Gradients
- Gradients are flattened, clipped, and encoded as fixed-point values before conversion to finite-field elements.The experiments use 16-bit numbers with four digits of decimal precision, sufficient for model conversion on MNIST and CIFAR-10.Source: §4.7 · p. 8
4.8 Malicious Secure FLDP
The section implements malicious-secure FLDP by replacing ideal noisy-gradient aggregation with MPC, and analyzes privacy for sums of discrete Gaussian noise. It also gives client and server runtime bounds, including the higher server cost with dropouts or malicious security.
4.8 Malicious Secure FLDP
- Protocol 6 implements Functionality 2 using MPC to sum encoded noisy gradients, replacing the ideal aggregation functionality in FLDP.It computes the gradient and adds noise as in the ideal functionality, while using Protocol 4 to sum the vectors.Source: §4.8 · p. 8
- Proposition 1 bounds Rényi divergence for sums of discrete Gaussians and yields almost identical privacy results to the continuous-Gaussian analysis.The reported ε values from the two analyses are so close that their resulting graphs are indistinguishable.Source: §4.8 · p. 9
4.9 Algorithmic Complexity
- Client computation takes O(mn+klog(k)) time, while server computation takes O(mk+mn+klog(k)) without dropouts and O(mk+mn+k2) with dropouts or malicious adversaries.Client runtime includes matrix-vector multiplication and packed FFT share generation; malicious security or dropouts raise server reconstruction cost to O(k2).Source: §4.9 · p. 9
- The complexity analysis treats q and n as constants, although n can be chosen small relative to q in practice.The stated LWE hardness requirement is that q be polynomial in n.Source: §4.9 · p. 9
5 Evaluation
FLDP’s evaluation tests whether its secure aggregation scales and whether it trains accurate models, finding scalable performance and accuracy comparable to central-model differentially private training. The experiments use separate training and MPC simulation phases.
5 Evaluation
- The evaluation addresses secure-aggregation performance and model accuracy, reporting that FLDP scales to realistic batch sizes and trains models comparably to central-model differentially private algorithms.Training gradients are saved and then aggregated in a separate MPC simulation; this avoids simulating 128 neural networks in parallel, a memory issue specific to running many clients on one machine.Source: §5 · p. 9
5.1 Experiment 1: Masking Scalability
- FLDP’s masking protocol is evaluated across federation configurations with no dropouts and a 25% dropout rate, assuming semi-honest adversaries and a single aggregation server.The experiments set β = 3.2/q and assume clients broadcast the sum of shares to the server.Source: §5.1 · pp. 9–10
5.1.1 Experimental Performance
- Client computation takes less than half a second in every tested configuration, while server computation is under 5 seconds without dropouts and remains much faster than Bonawitz et al. with dropouts.Server time grows linearly with vector size and quadratically with client count; dropout timings are an upper bound that faster interpolation may improve.Source: §5.1.1 · p. 10
5.2 Experiment 2: Model Accuracy
- The accuracy experiments use TensorFlow models on MNIST and CIFAR-10, with per-example gradient noise and clipping at C = 5 to satisfy differential privacy.They vary batch size and noise, average accuracy over four trials, and calculate ε post hoc for δ = 10−5.Source: §5.2 · p. 10
5.2.1 MNIST
- MNIST reaches 98.7% mean validation accuracy over four trials, compared with 99.2% for the no-noise baseline.Larger batch sizes tend to improve accuracy, especially at small privacy budgets; the paper attributes this to gradient-average sensitivity decreasing with batch size.Source: §5.2.1 · p. 11
5.2.2 CIFAR-10
- With batch size 64, CIFAR-10 reaches 70.0% mean validation accuracy over four trials, versus 77.4% for the same architecture without differential privacy.The paper reports this private-model performance as in line with central-model differentially private performance.Source: §5.2.2 · p. 12
5.2.3 Comparison With Centralized Differential Privacy
- Within 3% of equivalent central-model accuracy for a given privacy budget, FLDP’s private models show accuracy highly comparable to Abadi et al. [2].The table reports averages over four trials; the comparison uses batch size 64 and δ = 10−5.Source: §5.2.3 · p. 12, Table 4 · p. 13
6 Related Work
Prior work applies secure multiparty computation to distributed computation and differential privacy, but scalability remains a challenge. The paper also situates FLDP among prior privacy systems and notes a security-reduction gap for its small fixed LWE noise parameter.
Secure multiparty computation
- Many MPC protocols work best with two or three parties and cost at least quadratically as party counts grow, though cited protocols reach 128 and 110 parties.Wang et al. use garbled circuits, while Chida et al. use secret sharing.Source: §6 · p. 13
MPC for differentially private deep learning
- Prior differentially private deep-learning approaches require a semi-honest curator or two non-colluding curators, while secure aggregation targets the many-client setting [38].Kairouz et al. provide a framework for differentially private federated learning using existing secure aggregation protocols [26].Source: §6 · p. 13
Security for distributed differential privacy
- Honeycrisp and Orchard use distributed protocols for database-style queries, while ShrinkWrap and CRYPTε use existing MPC frameworks.Source: §6 · p. 13
Learning with Errors
- For small fixed βq, the authors report no known security reductions or known attacks exploiting the small constant standard deviation; they note similar choices in FrodoKEM and a recommendation.Regev's and Peikert's cited reductions apply under other parameter conditions.Source: §6 · p. 13
7 Conclusion
The conclusion presents FLDP as a way to train accurate federated models with differential privacy without a trusted data aggregator, including against powerful, colluding adversaries. The authors report feasible training times for practical applications and identify gradient compression and other data problems as future directions.
7 Conclusion
- FLDP provides differential privacy without a trusted data aggregator, and the authors report accurate models trainable within a feasible time frame for practical applications.They frame the approach as especially relevant when accuracy and low trust burdens are critical, including against powerful, colluding adversaries.Source: §7 · p. 13
- Gradient compression could reduce communication overhead and batch time for larger models, potentially improving scalability with model complexity [28].Source: §7 · p. 13
- The authors suggest adapting FLDP's noise-addition and secure-aggregation methods to privacy-preserving database queries without a central database.Source: §7 · p. 13
A Proof of security
The proof uses a simulator and a hybrid argument to establish security for FLDP in the malicious threat model. It concludes that the simulator no longer needs honest clients' inputs and that the result also covers the semi-honest model.
A Proof of security
- Theorem 2 states that a PPT simulator exists for the protocol's security claim, with the proof proceeding through a hybrid argument.The setup names the clients, corrupt parties, server, ideal functionality, and aggregation protocol.Source: A Proof of security · p. 16
- The hybrids replace ideal outputs, secret-vector sums, and client values with simulated or random values, relying on the LWE assumption and one-time-pad definition.The steps also replace the secure aggregation run with its ideal simulation.Source: A Proof of security · p. 16
- The simulator no longer needs honest clients' inputs, establishing security in the malicious threat model; that model subsumes the semi-honest model.Source: A Proof of security · p. 16