Privacy-Preserving Systems (Differential Privacy, Federated Learning)

TL;DR: Privacy-preserving systems shift the boundary of what an operator ever sees, rather than treating privacy as post-hoc access control. Five techniques dominate production: differential privacy (calibrated noise so no single record changes outputs meaningfully), federated learning (raw data stays on-device, only model updates travel), secure aggregation (cryptographic sums without individual visibility), homomorphic encryption (compute on ciphertext), and trusted execution environments (hardware-attested enclaves). Google's Gboard stack combines FL, secure aggregation, and DP-FTRL to achieve user-level zCDP of rho = 0.81, stronger than the US Census's rho = 2.63 ^[1]. No single primitive covers both a compliance obligation and a threat model. The design question is which layering makes the cost acceptable.

Learning Objectives#

After this module, you will be able to:

• Apply differential privacy to a real aggregation query and choose an epsilon
• Describe federated learning and its communication-vs-privacy trade-offs
• Explain secure aggregation well enough to design a federated training protocol
• Recognize when homomorphic encryption is applicable (and when it is still too slow)
• Select the right privacy primitive for a given threat model using a decision tree
• Combine techniques (DP + FL + SecAgg) as production systems actually do

Intuition#

You run a hospital consortium. Ten hospitals want to know the average length of stay for pneumonia patients, but no hospital will share its patient records with the others. One approach: each hospital adds a small random number to its average before reporting it. The noise is large enough that you cannot reverse-engineer any single hospital's true value, but small enough that the combined average is still useful. That is differential privacy.

Now suppose the hospitals want to train a shared AI model for pneumonia risk prediction. No hospital sends patient data anywhere. Instead, each hospital downloads the current model, trains it on local records for a few hours, and sends back only the weight changes. A coordinator averages those changes and updates the global model. That is federated learning.

But wait. If the coordinator can see each hospital's individual weight update, a clever attacker could reconstruct patient records from those gradients. So the hospitals add pairwise random masks that cancel when summed. The coordinator sees only the aggregate. That is secure aggregation.

Finally, one hospital wants a cloud service to run a query on its encrypted patient database without ever decrypting it. That is homomorphic encryption, and it is 1,000x to 100,000x slower than plaintext ^[2]. For most workloads, you pick a faster primitive and accept a different trust model.

The rest of this chapter gives you the formal tools to make these choices.

Theory#

Differential privacy fundamentals#

A randomized algorithm M is (epsilon, delta)-differentially private if for all neighboring datasets D, D' (differing in one record) and all output sets S:

Pr[M(D) in S] <= e^epsilon * Pr[M(D') in S] + delta

Epsilon controls the privacy-utility trade-off. Smaller epsilon means stronger privacy but noisier outputs. Delta is the probability of a catastrophic privacy failure; set it to less than 1/n where n is the dataset size ^[3].

Mechanisms. Pure DP (delta = 0) uses Laplace noise with scale = L1-sensitivity / epsilon. Approximate DP (delta > 0) uses Gaussian noise calibrated to L2 sensitivity. The Gaussian mechanism gives tighter composition bounds, which matters when you run many queries.

Composition. Every query on the same data spends privacy budget. Basic composition says k queries at epsilon each cost k * epsilon total. Advanced composition (Renyi DP, zero-concentrated DP) gives tighter accounting. Google's DP-FTRL uses tree-aggregation with negatively correlated noise to avoid the amplification-via-sampling assumption that is hard to enforce on drifting device populations ^[1:1].

Epsilon in the wild. The US Census 2020 used epsilon = 19.61 total (17.14 for persons, 2.47 for housing) ^[4]. Apple deploys per-datum epsilon of 1 to 2 but daily composed budgets up to 16 ^[5]. Google's Gboard achieves rho = 0.81 zCDP at the user level ^[1:2]. There is no universal "good epsilon." Calibrate against your utility requirements and threat model.

Local vs. central DP. In central DP, a trusted curator sees raw data and adds noise to query outputs. In local DP, each user adds noise before data leaves their device. Local DP requires roughly sqrt(n) times larger epsilon than central DP for the same utility, because noise is not amortized across users. Apple chose local DP because they refuse to be the trusted curator ^[6].

In central DP the curator sees raw data and is trusted to add noise correctly. In local DP noise is injected on-device so the aggregator never sees raw values.

Libraries. Google's differential-privacy (C++, Go, Java), OpenDP (Rust/Python, Harvard), Tumult Analytics (Spark-native), Opacus (PyTorch DP-SGD), TensorFlow Privacy (moments accountant). Google's library separates builder inputs (epsilon, delta, sensitivity) from mechanism selection, the API pattern every production DP system converges on.

Federated learning and FedAvg#

Federated learning is a distributed training protocol where a coordinator sends a model to many clients, each client trains on local data, and only weight updates return for aggregation ^[7].

The canonical algorithm is FedAvg (McMahan et al., 2017): per round, sample a subset of available clients; each runs E epochs of local SGD; the server takes a weighted average of client updates by local dataset size. FedAvg reduces communication rounds by 10x to 100x versus synchronized SGD on non-IID mobile data ^[7:1].

Cross-device vs. cross-silo. Cross-device FL involves millions of unreliable clients with tiny local datasets (Gboard: 6,500 devices per round, 2,000 rounds, 6 days of training ^[1:3]). Cross-silo FL involves tens of stable participants (hospitals, banks) with large local datasets and reliable connectivity.

Variants. FedProx adds a proximal term penalizing client drift on non-IID data. FedOpt uses server-side adaptive optimizers (Adam, Adagrad). Personalization layers (FedPer, meta-learning) give each client a customized head while sharing a global backbone.

Frameworks. Flower (a widely-used open-source FL framework as of 2025), TensorFlow Federated, PySyft (OpenMined), NVIDIA FLARE (enterprise cross-silo).

Secure aggregation#

Secure aggregation lets a server compute the sum of user-held vectors without learning any individual vector ^[9].

In Bonawitz et al. (2017), each pair of clients (i, j) derives a shared mask via Diffie-Hellman. Client i adds +mask and client j adds -mask to their updates. When the server sums all n updates, pairwise masks cancel. Shamir secret sharing of each client's seed (threshold t) lets the server recover masks for clients that drop out mid-round ^[9:1].

Each round: server broadcasts model, clients train locally and mask updates pairwise, server aggregates the masked sum and adds DP noise before applying the update.

Per-client communication is O(n) for masking plus O(n) for Shamir shares, giving O(n^2) total across the round ^[9:2]. Sparse-graph variants (e.g., Choi et al. 2020) reduce per-client communication to O(log n) by replacing the complete pairwise-mask graph with an Erdos-Renyi random graph, taking total communication from O(n^2) to O(n log n) while preserving reliability and privacy guarantees ^[10]. Flamingo extends to multi-round aggregation with a one-time setup.

Homomorphic encryption and MPC#

Homomorphic encryption (HE) lets specific operations on ciphertexts correspond to operations on plaintexts after decryption. Partial HE supports one operation (Paillier: additive). Fully HE (FHE) supports arbitrary circuits but incurs 1,000x to 100,000x slowdown ^[2:1].

Modern FHE schemes: BFV and BGV (exact integer arithmetic, SIMD batching), CKKS (approximate real arithmetic, ideal for ML inference), TFHE (fast boolean gates, cheap bootstrapping). Libraries: Microsoft SEAL, OpenFHE, Zama Concrete/TFHE-rs, Google HEIR (MLIR-based compiler).

When to use HE: narrow, high-sensitivity queries where no party should see plaintext. Microsoft's Password Monitor uses SEAL to check breached credentials without exposing the password to the server ^[11]. For general ML training or real-time serving, HE is too slow. Use TEEs or MPC instead.

Secure multi-party computation (MPC) lets n parties jointly compute a function such that each party learns only the output, not the others' inputs. Yao's Garbled Circuits (two-party), GMW (multi-party), and Shamir secret sharing are the foundations. Meta and Mozilla's Interoperable Private Attribution (IPA) uses three-party MPC for ad attribution, reporting 18 GB network cost per 1M records at roughly $1.44 in cloud egress ^[12].

Trusted execution environments#

TEEs provide hardware-isolated execution with encrypted memory and remote attestation. The client verifies what code is running before sending data.

Intel SGX (enclaves with encrypted RAM) was deprecated on client CPUs (11th Gen onward), partly due to side-channel attacks like Foreshadow ^[13], but remains on Xeon server parts. Intel TDX and AMD SEV-SNP provide VM-level confidential compute. AWS Nitro Enclaves isolate from the parent EC2 instance via vsock. Apple Private Cloud Compute (PCC, June 2024) is a full Apple-silicon server stack with Secure Enclave, measured Secure Boot, a transparency log of production binaries, and non-targetability via oblivious HTTP routing ^[14]. Apple offers up to $1,000,000 for arbitrary code execution on a PCC node ^[14:1].

Signal's Private Contact Discovery uses SGX enclaves with an oblivious hash-table construction to prevent access-pattern side channels. Clients verify the MRENCLAVE value via remote attestation before transmitting address-book hashes ^[15].

The client verifies the remote enclave's measurement against a trusted transparency log before sending any sensitive data. Apple PCC extends this pattern with Oblivious HTTP relays so Apple cannot preferentially route a user to a compromised node ^[14:2].

Choosing the right primitive#

Start from whether a trusted curator exists. Derive the primitive from the threat model and latency budget.

When NOT to use these techniques: (1) Low-sensitivity data where access control suffices. (2) Pre-aggregated data where individual records are already gone. (3) Compliance-only scenarios where pseudonymization satisfies the regulator. (4) Tight latency budgets that cannot absorb FHE or MPC overhead. Privacy engineering has real costs. Apply it where the threat model demands it.

Real-World Example#

Google's Gboard federated learning stack is the most complete production deployment combining FL, secure aggregation, and differential privacy ^[1:4].

The problem: Train a next-word prediction model on what users actually type, without collecting their keystrokes on a server.

The solution: A 1.3M-parameter recurrent neural network trained via DP-FTRL (Differentially Private Follow-the-Regularized-Leader). Each round, 6,500 devices are sampled. Each device trains locally on its typing history, computes a weight update, masks it via secure aggregation, and sends the masked update to the server. The server sums the masked updates (pairwise masks cancel), adds calibrated Gaussian noise for DP, and applies the noisy aggregate to the global model. Training takes 2,000 rounds over 6 days ^[1:5].

Key design decisions:

• DP-FTRL over DP-SGD: DP-SGD requires uniformly random device sampling, which is infeasible when devices check in only when idle, charging, and on WiFi. DP-FTRL uses tree-aggregation with negatively correlated noise that avoids this assumption ^[1:6].
• User-level DP: All data on one device counts as one user. The formal guarantee is rho = 0.81 zCDP at the user level, stronger than the US Census's rho = 2.63 ^[1:7].
• Device participation cap: Each device participates at most once every 24 hours, bounding per-user contribution to the aggregate.
• Open-sourced: Production parameters published in TensorFlow Federated and TensorFlow Privacy for reproducibility.

Deployments beyond Gboard: Apple uses local DP for iOS/macOS telemetry (emoji usage, new words, Safari domains) with Count-Mean Sketch and Hadamard CMS ^[6:1]. Hospital consortia use cross-silo FL via NVIDIA FLARE for radiology models without sharing patient images.

Trade-offs#

Common Pitfalls#

Exercise#

Design an anonymous voting system for user preference data ("which product feature should we build next?"). Specify the privacy technique (DP for aggregate counts? secure aggregation for per-category votes? both?), the epsilon and privacy budget, and how you prevent a single user from casting 10,000 votes. Include the threat model explicitly.

Key Takeaways#

• Differential privacy is the only provable, composable privacy guarantee that survives arbitrary post-processing. Epsilon choice is a policy decision, not a technical one.
• Federated learning keeps data on-device but is not private by itself. Gradient inversion attacks reconstruct inputs. Always pair FL with secure aggregation and DP.
• Secure aggregation (Bonawitz et al. 2017) is the cryptographic primitive that makes FL privacy-preserving. O(n^2) total in the original protocol; sparse-graph variants (Choi et al. 2020) reduce per-client cost to O(log n) and total cost to O(n log n) ^[10:1].
• Homomorphic encryption is too slow (1,000x to 100,000x) for general workloads. Reserve it for narrow, high-sensitivity queries like password breach checks.
• TEEs offer near-native speed but shift trust to the silicon vendor. Side-channel history (Foreshadow, SGAxe) means you cannot rely on hardware alone.
• Production systems combine primitives: Google's Gboard uses FL + SecAgg + DP-FTRL simultaneously. No single technique covers both compliance and threat model.
• Privacy is a system property, not a library call. Data Residency and Compliance covers the regulatory context that motivates these techniques.

Further Reading#

• The Algorithmic Foundations of Differential Privacy - Dwork and Roth's canonical 280-page reference, free online. Read chapters 1 to 3 before choosing an epsilon for any production system.
• Communication-Efficient Learning of Deep Networks from Decentralized Data - McMahan et al.'s FedAvg paper, the foundation of federated learning. Essential for understanding communication-computation trade-offs.
• Practical Secure Aggregation for Privacy-Preserving Machine Learning - Bonawitz et al.'s CCS 2017 protocol. The canonical secure aggregation construction used in production at Google.
• Federated Learning with Formal Differential Privacy Guarantees - Google Research blog on the Gboard DP-FTRL deployment with production parameters.
• Apple: Learning with Privacy at Scale - Apple's description of CMS, HCMS, and SFP with deployed parameters. The best public reference for local DP at scale.
• Apple Private Cloud Compute Security Guide - Apple's full security architecture for attested cloud AI inference. Sets the bar for TEE transparency.
• Signal: Private Contact Discovery - Signal's engineering writeup of SGX plus oblivious hash-table contact discovery. A masterclass in TEE threat modelling.
• Deep Learning with Differential Privacy - Abadi et al.'s DP-SGD and moments accountant paper. Required reading before using Opacus or TF Privacy.

Flashcards#

References#