Privacy and Federated Learning:

Principles, Techniques and Emerging Frontiers
AAAI Workshop of Privacy Preserving Artificial Intelligence (PPAI-21)

Brendan
McMahanPresenting the work of many

Kallista
BonawitzPeter
KairouzTutorial Outline
Part 1: What is Federated Learning?
Part 2: Privacy for Federated Technologies
Part 2.1: Private Aggregation & Trust
Part 2.2: Differentially Private Federated Training
Part 3: Other topics (very brief)

Part I: What is Federated Learning?

Data is born at the edge

Billions of phones & IoT devices constantly generate data
Data enables better products and smarter models

Can data live at the edge?
Data processing is moving on device:● Improved latency● Works oﬄine● Better battery life
● Privacy advantages
E.g., on-device inference for mobile
keyboards and cameras.

Can data live at the edge?
Data processing is moving on device:● Improved latency● Works oﬄine● Better battery life
● Privacy advantages
E.g., on-device inference for mobile
keyboards and cameras.
What about analytics?
What about learning?

Cross-device federated learning
admin

serverclientdevicesfederatedtraining
model
development
engineermodel
deployment

Applications of cross-device federating learning
What makes a good application?

Example applications●

On-device data is more relevant
than server-side proxy data●

Language modeling for mobile
keyboards and voice recognition●

On-device data is privacy
sensitive or large●●

Labels can be inferred naturally
from user interaction

Image classification forpredicting which photos people
will share...

●Gboard: next-word prediction
Federated RNN (compared to prior n-gram model):● Better next-word prediction accuracy: +24%
● More useful prediction strip: +10% more clicks

Federated modelcompared to baseline

A. Hard, et al. Federated
Learning for Mobile Keyboard
Prediction. arXiv:1811.03604

Other federated models in Gboard
Emoji prediction● 7% more accurate emoji predictions● prediction strip clicks +4% more
● 11% more users share emojis!

Action prediction
When is it useful to suggest a gif, sticker, or
search query?
● 47% reduction in unhelpful suggestions● increasing overall emoji, gif, and sticker
sharesDiscovering new words
Federated discovery of what words people
are typing that Gboard doesn’t know.

Ramaswamy, et al. Federated Learning
for Emoji Prediction in a Mobile
Keyboard.
arXiv:1906.04329.

T. Yang, et al. Applied Federated
Learning: Improving Google Keyboard
Query Suggestions. arXiv:1812.02903

M. Chen, et al. Federated Learning
Of Out-Of-Vocabulary Words.
arXiv:1903.10635

Cross-device federated learning at Apple"Instead, it relies primarily on a technique calledfederated learning, Apple’s head of privacy, Julien
Freudiger, told an audience at the Neural Processing
Information Systems conference on December 8.
Federated learning is a privacy-preserving
machine-learning method that was first introduced
by Google in 2017. It allows Apple to train different
copies of a speaker recognition model across all its
users’ devices, using only the audio data available
locally. It then sends just the updated models back toa central server to be combined into a master model.
In this way, raw audio of users’ Siri requests neverleaves their iPhones and iPads, but the assistantcontinuously gets better at identifying the rightspeaker."

https://www.technologyreview.com/2019/12/11/131629/apple-ai-personalizes-siri-federated-learning/Federated Learning

Federated learning is a machine learning setting wheremultiple entities (clients) collaborate in solving a machinelearning problem, under the coordination of a central serveror service provider. Each client's raw data is stored locally andnot exchanged or transferred; instead, focused updates
intended for immediate aggregation are used to achieve thelearning objective.
deﬁnition proposed in
Advances and Open Problems in Federated Learning (arxiv/1912.04977)

Federated learning - defining characteristics
Data is generated locallyand remains decentralized.
Each client stores its own
data and cannot read thedata of other clients. Data
is not independently or
identically distributed.

serverclients

A central orchestration
server/service coordinates thetraining, but never sees raw data.

Cross-silo federated learning

admin
serverfederatedtraining

federatedtraining

Cross-silo federated learning from Intel"The University of Pennsylvania and chipmaker Intel are forming apartnership to enable 29 heatlhcare and medical research institutions
around the world to train artificial intelligence models to detect brain
tumors early.""The program will rely on a technique known as federated learning,which enables institutions to collaborate on deep learning projects
without sharing patient data. The partnership will bring in institutions in
the U.S., Canada, U.K., Germany, Switzerland and India. The centers –which include Washington University of St. Louis; Queen’s University inKingston, Ontario; University of Munich; Tata Memorial Hospital in
Mumbai and others – will use Intel’s federated learning hardware andsoftware."[1] https://medcitynews.com/2020/05/upenn-intel-partner-to-use-federated-learning-ai-for-early-brain-tumor-detection/[2] https://www.allaboutcircuits.com/news/can-machine-learning-keep-patient-privacy-for-tumor-research-intel-says-yes-with-federated-learning/[3] https://venturebeat.com/2020/05/11/intel-partners-with-penn-medicine-to-develop-brain-tumor-classifier-with-federated-learning/[4] http://www.bio-itworld.com/2020/05/28/intel-penn-medicine-launch-federated-learning-model-for-brain-tumors.aspx

Cross-silo federated learning from NVIDIA"Federated learning addresses this challenge, enabling different
institutions to collaborate on AI model development without sharing
sensitive clinical data with each other. The goal is to end up withmore generalizable models that perform well on any dataset,
instead of an AI biased by the patient demographics or imaging
equipment of one specific radiology department."[1] https://blogs.nvidia.com/blog/2020/04/15/federated-learning-mammogram-assessment/[2] https://venturebeat.com/2020/04/15/healthcare-organizations-use-nvidias-clara-federated-learning-to-improve-mammogram-analysis-ai/[3] https://medcitynews.com/2020/01/nvidia-says-it-has-a-solution-for-healthcares-data-problems/[4] https://venturebeat.com/2020/06/23/nvidia-and-mercedes-benz-detail-self-driving-system-with-automated-routing-and-parking/Cross-device federated learning

Cross-silo federated learning

millions of intermittently
available client devices

small number of clients(institutions, data silos),high availabilityX

coordinating
servercoordinating
serverCross-device federated learningclients cannot be indexed
directly (i.e., no use ofclient identifiers)

X

Cross-silo federated learning
each client has an identity or
name that allows the system toaccess it specifically

Selection iscoarse-grained
coordinating
servercoordinating
serverAlice

Bob
Updates areanonymousCross-device federated learning

Cross-silo federated learning

Server can only access a (possibly
biased) random sample of clients oneach round.

Most clients participate in every
round.

Large population => most clients only
participate once.

coordinating
serverround 1

Clients can run algorithms thatmaintain local state across rounds.

coordinating
serverround 1

Cross-device federated learning

Cross-silo federated learning

Server can only access a (possibly
biased) random sample of clients oneach round.

Most clients participate in every
round.

Large population => most clients only
participate once.

coordinating
serverClients can run algorithms thatmaintain local state across rounds.

coordinating
serverround 2round 2(completely new set of devices participate)(same clients)

Cross-device federated learning

Cross-silo federated learning

communication is often the
primary bottleneck

communication or computation
might be the primarybottleneck

X

coordinating
servercoordinating
serverCross-device federated learning

horizontal orvertically partitioned data

featuresfeaturesexamplesexampleshorizontally partitioned data

Cross-silo federated learning

X

coordinating
servercoordinating
serverDistributed datacenter machine learning

cloud
data

servers

engineerFL terminology●

Clients - Compute nodes also holding local data, usually belonging to one
entity:○○○○●IoT devices
Mobile devices
Data silos
Data centers in different geographic regions

Server - Additional compute nodes that coordinate the FL process but don't
access raw data. Usually not a single physical machine.

Characteristics of the federated learning setting
Datacenter distributed learning

Cross-silofederated learning

Cross-device
federated learning

Setting

Training a model on a large but"flat" dataset. Clients are computenodes in a single cluster ordatacenter.

Training a model on siloed data.
Clients are different organizations(e.g., medical or financial) or
datacenters in different geographicalregions.

The clients are a very large number of mobile
or IoT devices.

Data distribution

Data is centrally stored, so it canbe shuffled and balanced acrossclients. Any client can read any
part of the dataset.

Data is generated locally and remains decentralized. Each client stores its own
data and cannot read the data of other clients. Data is not independently or identically
distributed.

Orchestration

Centrally orchestrated.

A central orchestration server/service organizes the training, but never sees raw data.

Wide-area
communication

None (fully connected clients in
one datacenter/cluster).

Typically hub-and-spoke topology, with the hub representing a coordinating service
provider (typically without data) and the spokes connecting to clients.

Data availability

All clients are almost always available.

Only a fraction of clients are available at any
one time, often with diurnal and othervariations.

Distribution scale

Typically 1 - 1000 clients.

Massively parallel, up to 1010 clients.

Typically 2 - 100 clients.

Adapted from Table 1 in Advances and Open Problems in Federated Learning (arxiv/1912.04977)

Characteristics of the federated learning setting
Datacenter distributed learning

Cross-silofederated learning

Cross-device
federated learning

Addressability

Each client has an identity or name that allows the system to access it
specifically.

Clients cannot be indexed directly (i.e., no useof client identifiers)

Client statefulness

Stateful --- each client may participate in each round of the computation,
carrying state from round to round.

Generally stateless --- each client will likely
participate only once in a task, so generally
we assume a fresh sample of never before
seen clients in each round of computation.

Primary bottleneck

Computation is more often thebottleneck in the datacenter, wherevery fast networks can beassumed.

Communication is often the primarybottleneck, though it depends on the task.
Generally, federated computations uses wi-fi
or slower connections.

Reliability of clients

Relatively few failures.

Data partition axis

Data can be partitioned /re-partitioned arbitrarily acrossclients.

Might be computation orcommunication.

Highly unreliable --- 5% or more of the clients
participating in a round of computation are
expected to fail or drop out (e.g., because thedevice becomes ineligible when battery,
network, or idleness requirements fortraining/computation are violated).
Partition is fixed. Could be
example-partitioned (horizontal) or
feature-partitioned (vertical).

Fixed partitioning by example (horizontal).

Adapted from Table 1 in Advances and Open Problems in Federated Learning (arxiv/1912.04977)

Fully decentralized (peer-to-peer) learning?
engineerFully decentralized (peer-to-peer) learning

Characteristics of FL vs decentralized learning

Federated learning

Fully decentralized(peer-to-peer) learning

Orchestration

A central orchestration server/service organizes
the training, but never sees raw data.

No centralized orchestration.

Wide-area
communication pattern

Typically hub-and-spoke topology, with the hub
representing a coordinating service provider(typically without data) and the spokes
connecting to clients.

Peer-to-peer topology.

Adapted from Table 3 in Advances and Open Problems in Federated Learning (arxiv/1912.04977)

Cross-Device Federated LearningModeldevelopment
workflow
servercloud
data

Train & evaluate
on cloud dataengineerModeldevelopment
workflow
serverclients

Final model
validation steps

engineerModeldevelopment
workflow
serverclients

Deploy model
to devices
for on-device
inferenceengineerFederated
training

Train & evaluate
on decentralized
data

serverclients

engineerFederated learning

opted-indata device

Need me?

Federated learning

data device

Need me?
Not nowFederated learning

data device

Need me?
Yes!

Federated learning

data device updated
model

initial model

engineerFederated learning(ephemeral)
data device updated
model

initial model

engineerFederated learning

updateddata device model

Privacy principle

Focused collection
Devices report only what isneeded for this computation

initial model

engineerFederated learning
Privacy principle

Ephemeral reports
Server never persists
per-device reports

updateddata device model

initial model

engineerFederated learning
combinedmodel

updateddata device model

Privacy principle∑

Only-in-aggregate
Engineer may only
access combined
device reports

initial model

engineerFederated learning
combinedmodel
data device(another)initial model
engineerFederated learning(another)combinedmodel
data device∑(another)initial model
engineerFederated learning
Typical orders-of-magnitude(another)
100-1000sof clients per roundcombined
model
1000s of rounds to convergencedata device

1-10 minutes per round∑(another)initial model
engineerFederated Averaging (FedAvg) algorithm(another)combinedmodel

Server computes
overall update using
a simple weighted
average.

data device

Devices run multiple
steps of SGD on theirlocal data to computean update.

∑(another)initial model
McMahan, et al. Communication-Eﬃcient Learning of Deep
Networks from Decentralized Data. AISTATS 2017.

engineerBeyond Learning: Federated
Analytics

Beyond learning: federated analytics

Sunﬂower

19%

Dance Monkey
Rockstarcovid-19$ moon$sun$

Shape of You
Closer

33%
36%
38%

Geo-location heatmaps

Frequently typed
out-of-dictionary words

t
Ea

Wo
rk
Fa
mi
ly
Re
ad

Sle
ep

TV
Wa
lk

sun$ covid-19$

Re

moon$

st

23%

Popular songs, trends,
and activities

Federated analytics
Federated analytics is the practice of applying data science methods tothe analysis of raw data that is stored locally on users’ devices. Like
federated learning, it works by running local computations over eachdevice’s data, and only making the aggregated results — and never any
data from a particular device — available to product engineers. Unlike
federated learning, however, federated analytics aims to support basic
data science needs.

definition proposed in https://ai.googleblog.com/2020/05/federated-analytics-collaborative-data.html

Federated analytics
●
●
●
●
●
●
●
●

Federated histograms over closed sets
Federated quantiles and distinct element counts
Federated heavy hitters discovery over open sets
Federated density of vector spaces
Federated selection of random data subsets
Federated SQL
Federated computations?
etc...

Interactive algorithms

Non-interactive algorithms

Similar to learning, theon-device computation is afunction of a server state

Unlike learning, theon-device computation does
not depend on a server state

coordinating
serverZhu et. al. Federated Heavy Hitters Discovery
with Differential Privacy AISTATS’20.

coordinating
serverErlingsson et. al. RAPPOR: Randomized
Aggregatable Privacy-Preserving Ordinal
Response CCS’14.

Part II: Privacy for Federated
Learning and Analytics

Aspects of Privacy
The why, what, and how of using data.
Why?

Why use this data? The user understands and supports theintended use of the data.

Transparency & consent

What?

What is computed? When data is released, ensure it does notreveal any user's private information.

Limited inﬂuence of any individual

How?
Security & data minimization

How and where does the computation happen? Release data to
as few parties as possible. Minimize the attack surface where
private information could be accessed.

Aspects of Privacy
The why, what, and how of using data.
Why?

Why use this data? The user understands and supports theintended use of the data.

Transparency & consent

What?

What is computed? When data is released, ensure it does notreveal any user's private information.

Limited inﬂuence of any individual

How?
Security & data minimization

How and where does the computation happen? Release data to
as few parties as possible. Minimize the attack surface where
private information could be accessed.

Privacy

ML on sensitive data: privacy vs. utility

UtilityPrivacy

ML on sensitive data: privacy vs. utility

perception
UtilityPrivacy

ML on sensitive data: privacy vs. utility

today
perception
Utility

1.

Policy2.

Technology

ML on sensitive data: privacy vs. utility (?)

Privacy

goal

today

Utility

1.

Policy2.

New Technology
Push the pareto frontierwith better technology.
Make achieving highprivacy and utility
possible.

ML on sensitive data: privacy vs. utility (?)

Privacy

goal

t
r
o
f
, ef

pu
m
Co

n
o
i
t
ta

Utility

1.

Policy2.

New Technology
Push the pareto frontierwith better technology.
Make achieving highprivacy and utility
possible with less work.

serverclientdevicesfederatedtraining

model
deployment

model
development
engineerWhat private information might an actor learn?

serverclientdevicesfederatedtraining

model
deployment

model
development
engineerWhat private information might an actor learn
with access to ...
… thedevice?
serverclientdevicesfederatedtraining
model
development
engineer... thenetwork?

What private information might an actor learn
with access to ...

… the server?
serverclientdevices... the releasedmodels andmetrics?

federatedtraining
model
development
engineerWhat private information might an actor learn
with access to ...

serverclientdevicesfederatedtraining

model
deployment

model
development
engineer… the deployedmodel?

What private information might an actor learn
with access to ...
… thedevice?

… the server?
serverclientdevices... the releasedmodels andmetrics?

federatedtraining

model
deployment

model
development
engineer... thenetwork?

… the deployedmodel?

How much do I need to trust …
… thedevice?

… the server?
serverclientdevices... the releasedmodels andmetrics?

federatedtraining

model
deployment

model
development
engineer... thenetwork?

… the deployedmodel?

Privacy principles guiding FL

Minimize data exposure

clientdevices

Anonymous
ephemeral
updates

serverfederated
Early aggregation,
training
minimum retention
Focused collection

model
deployment

model
development
engineer

Only-in-aggregate
releaseHow
What

What private information might an actor learn
with access to ...
… thedevice?
serverclientdevicesfederatedtraining

model
deployment

model
development
engineer... thenetwork?

Encryption, at rest and on the wire
… thedevice?
serverclientdevicesfederated
Encryption
training

model
deployment

model
development
engineer... thenetwork?

How
What

What private information might an actor learn
with access to ...

… the server?
serverclientdevicesfederatedtraining

model
deployment

model
development
engineerWhat private information might an actor learn
with access to ...

… the server?
serverclientdevicesfederatedtraining
Local
Differential
Privacymodel
deployment

model
development
engineerHow

Warner. Randomized response. 1965.
Kasiviswanathan, et. al. What can we learn privately? 2011.

What

What private information might an actor learn
with access to ...

… the server?
serverclientdevicesfederatedtraining

model
deployment

model
development
engineer

Ideally, nothing, even with root access.

How
What

What private information might an actor learn… the server?
serverclientdevices

Secure Enclaves,(hardware),Secure Multi-Party
Computation model(crypto)model
deployment

development
engineer

Ideally, nothing, even with root access.

How
What

What private information might an actor learn
with access to ...

serverclientdevices... the releasedmodels andmetrics?

federatedtraining

model
deployment

model
development
engineerHow
What… the deployedmodel?

What private information might an actor learn
with access to ...

serverclientdevicesfederatedtraining... the releasedmodels andmetrics?

Centralmodel
Differential
model
deployment
Privacydevelopment
engineerHow
What

Dwork and Roth. The Algorithmic
Foundations of Differential Privacy. 2014.

… the deployedmodel?

What private information might an actor learn
with access to ...

serverclientdevicesfederatedtraining... the releasedmodels andmetrics?

Empirical privacy
auditing model
model(e.g. secret deployment
sharer,development
membership inference)engineerHow
What… the deployedmodel?

Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, Dawn Song.
The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks. 2018.
Congzheng Song, Vitaly Shmatikov. Auditing Data Provenance in Text-Generation Models. 2018.
Matthew Jagielski, Jonathan Ullman, Alina Oprea. Auditing Differentially Private Machine Learning: How Private is Private SGD? 2020.

Private Aggregation & TrustDistributing Trust for Private Aggregation

Distributing Trust for Private Aggregation
1

Trusted “third party”+∑
third-partyDistributing Trust for Private Aggregation
1

Trusted “third party”

2

Trusted Execution Environments

+

∑ +
∑
third-party
trustedhardware

Distributing Trust for Private Aggregation
1

Trusted “third party”

2

Trusted Execution Environments+

3

Trust via Cryptography

+

∑ +
∑
third-party
trustedhardware∑cryptography

Secure Aggregation

Communication
Eﬃcient
for Vectors & Tensors

Robustto Clients GoingOﬄine
Conﬁdential + Proprietary

Random positive/negative pairs, aka antiparticles
Alice
Devices cooperate to sample random
pairs of 0-sum perturbations vectors.
Bob

Matched pair sums to 0

Carol

Random positive/negative pairs, aka antiparticles
Alice
Devices cooperate to sample random
pairs of 0-sum perturbations vectors.
Bob

Carol

Add antiparticles before sending to the server
Alice

Bob
+

+
+

+

+

+

Each contribution looks
random on its own...

Carol

The antiparticles cancel when summing contributions
Alice

Bob
+

+

∑
+

+

+

+

Each contribution looks
random on its own...
but paired antiparticles
cancel out when summed.

Carol

Revealing the sum.
Alice

Bob
+

+

∑
+

+

+

+

Each contribution looks
random on its own...
but paired antiparticles
cancel out when summed.

CarolBut there are two challenges...

Conﬁdential + Proprietary

Alice1. These vectors are big!
How do users agree efficiently?

Bob

Carol

Alice

Bob
+

+

∑
+

+

+

+

2. What if someone drops out?

Carol

AliceThat's
bad.
Bob
+

+

∑

+

+

2. What if someone drops out?

Carol

Pairwise Diﬃe-Hellman Key Agreement
Alice

a

Secret

Bob

b

Carol

c

Pairwise Diﬃe-Hellman Key Agreement
Alicea
Safe to reveal(cryptographicallyhard to infer secret)Secret

ga
Bob

b
gb

Carol

Public parameters: g, (mod p)

g

c

c

Pairwise Diﬃe-Hellman Key Agreement
Alice
Because gx are public, we canshare them via the server.

a

Bob

ga
gb
gc

b

Carol

c

Pairwise Diﬃe-Hellman Key Agreement
Alice

gb
gc

Saves a copy

a

Bob

ga
gb
gc

ga
gc

Carol

ga
gb

c

b

Pairwise Diﬃe-Hellman Key Agreement
Alice

gb
gc

a

Combine withsecret

Carol

ga
gb

c

Bob

ga
gc

b

Pairwise Diﬃe-Hellman Key Agreement
Alice

gb
gc

a
gba gcaCommutative op→ Shared secret!

Carol

ga
gb

c
g gbc
ac

Bob

ga
gc

b
gab gcb

Pairwise Diﬃe-Hellman Key Agreement
Alice
Secrets are scalars, but….

agba gca
Bob
Shared secret!

b
gab gcb

Carol

c
g gbc
ac

Pairwise Diﬃe-Hellman Key Agreement + PRNG Expansion
Alice
Secrets are scalars, but….
Use each secret to seed apseudorandom number generator,
generate paired antiparticle vectors.
PRNG(gba) →=-a
gba gca
Bob
Shared secret!

b
gab gcb

Carol

c
g gbc
ac

Pairwise Diﬃe-Hellman Key Agreement + PRNG Expansion
Alice
Secrets are scalars, but….

a

Use each secret to seed apseudorandom number generator,
generate paired antiparticle vectors.

Bob

PRNG(gba) →

b

=-

Carol

c

Pairwise Diﬃe-Hellman Key Agreement + PRNG Expansion
Alice
Secrets are scalars, but….
Use each secret to seed apseudorandom number generator,
generate paired antiparticle vectors.

Bob

PRNG(gba) →

b

=-

1.

Eﬃciency via pseudorandom generator

2.

Mobile phones typically don't support
peer-to-peer communication anyhow.

3.

aFewer secrets = easier recovery.

Carol

c

k-out-of-n Threshold Secret Sharing
Goal: Break a secret into n pieces, called shares.
● <k shares: learn nothing● ≥k shares: recover s perfectly.
Each line isa share2-out-of-3 secret sharing:s
x-coordinate of theintersection is the secretk-out-of-n Threshold Secret Sharing
Goal: Break a secret into n pieces, called shares.
● <k shares: learn nothing● ≥k shares: recover s perfectly

?

?

?

k-out-of-n Threshold Secret Sharing
Goal: Break a secret into n pieces, called shares.
● <k shares: learn nothing● ≥k shares: recover s perfectly

s

s

s

Users make shares of their secrets
Alice

a

Bob

b

Carol

c

And exchange with their peers
Alice

a

Bob

b

Carol

c

AliceThat's
bad.
Bob
+

+

∑

+

+
Carol

Alice

Bob
+

+

∑

+

ga
gb
gc

b?

+
Carol

Alice

Bob
+

+

∑

+

ga
gb
gc

+
Carol

Alice

Bob
+

+

∑

+

ga
gb
gc

+
Carol

Alice

Bob
+

+

∑

+

ga
gb b
gc

+
Carol

Alice

Bob
+

+

∑

ga
b
gc

+

+
Carol

Alice

Bob
+

+

∑

ga
b
gc

+

+
Carol

Alice

Bob
+

+

∑

ga
b
gc

+

+

Enough honest users + a high enough threshold⇒ dishonest users cannot reconstruct the secret.

CarolAlice

Bob
+

+

∑

ga
b
gc

+

+

Enough honest users + a high enough threshold⇒ dishonest users cannot reconstruct the secret.
However….

Carol

Alice

Bob
+

+

∑

ga
b

late.

+

+

gc
+

+
Carol

Alice

Bob
+

+

∑

ga
b

late.

+

+

gc
+

+
Carol

Oops.

Alice

Bob
+

+
+

+

+

+
Carol

Alice

Bob
+

+

+

+

+

+

+

+

+
Carol

Alice

a
Bob

b

Carol

c

Alice

a
Bob

b

Carol

c

Alice
abc :
:

Bob
abc :
:

Carol
abc :
:

Alice
abc :
:

Bob
+

+

+

+

+

+
Carol
abc :
:

Alice
abc :
:

Bob
+

+

+

( , b, )?
+

+

+
Carol
abc :
:

Alice
abc :
:

+

+

+

+

+

+

Bob

abc :
:

abc :
:

Carol
abc :
:

Alice
abc :
:

+

+

Bob

abc :

+

:

b
+

+

+

abc :
:

Carol
abc :
:

Alice
abc :
:

+

+

Bob

abc :

+

:

b
+

+

+

abc :
:

Carol
abc :
:

Alice
abc :
:

+

+

Bob

abc :

+

:

b
+

+

+

abc :
:

Carol
abc :
:

Alice
abc :
:

+

+

∑

Bob

abc :

+

:

b
+

+

+

abc :
:

Carol
abc :
:

Alice
abc :
:

Bob
+

+

+

∑

b
+

+

late.

abc :

+

+

+

:

+
Carol
abc :
:

Alice
abc :
:

Bob
+

+

+

∑

b
+

+

+

late.

abc :

+

+

+

:

Permanent.
(honest users
already gave b)

Carol
abc :
:

Secure Aggregation

K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan,
S. Patel, D. Ramage, A. Segal, K. Seth. Practical Secure
Aggregation for Privacy-Preserving Machine Learning. CCS’17.

Interactive Cryptographic Protocol
Each phase, 1000 clients + server interchange
messages over 4 rounds of communication.

∑

SecureRobust⅓ malicious clients+ fully observed server

⅓ clients can drop out

Communication EﬃcientServer aggregates users'
updates, but cannot inspect
the individual updates.

# Params

Bits/Param# Users

Expansion

220 = 1 m

16

210 = 1 k

1.73x

224 = 16 m

16214 = 16 k

1.98x

CCS 2017
K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan,
S. Patel, D. Ramage, A. Segal, K. Seth. Practical Secure
Aggregation for Privacy-Preserving Machine Learning.

Complete Graphof pairwise masks, secret shares

CCS 2017

CCS 2020

K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan,
S. Patel, D. Ramage, A. Segal, K. Seth. Practical Secure
Aggregation for Privacy-Preserving Machine Learning.

J. Bell, K. Bonawitz, A. Gascon, T. Lepoint, M. Raykova
Secure Single-Server Aggregation with (Poly)Logarithmic
Overhead.

Complete Graphof pairwise masks, secret shares

Random Harary(n, k)

n clients, k neighbors, random node assignmentsk = O(log n)Secure Aggregation
K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B.
McMahan, S. Patel, D. Ramage, A. Segal, K. Seth. Practical
Secure Aggregation for Privacy-Preserving Machine
Learning. CCS 2017.

ServerProtocolComputation
Bonawitz et al.
(CCS 2017)
Bell et al.
(CCS 2020)
Insecure
Solution

J. Bell, K. Bonawitz, A. Gascon, T. Lepoint, M. Raykova
Secure Single-Server Aggregation with (Poly)Logarithmic
Overhead. CCS 2020.

ClientCommunication

Computation

Communication

CCS 2017

CCS 2020

K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan,
S. Patel, D. Ramage, A. Segal, K. Seth. Practical Secure
Aggregation for Privacy-Preserving Machine Learning.

J. Bell, K. Bonawitz, A. Gascon, T. Lepoint, M. Raykova
Secure Single-Server Aggregation with (Poly)Logarithmic
Overhead.

Complete Graphof pairwise masks, secret shares

Random Harary(n, k)

n clients, k neighbors, random node assignmentsk = O(log n)Cheaper!

Cost of 1 million cohorts, each of 1000 clients

Cost of a single cohort of 1 billion clients

Sparse Federated Learning & Analytics●●●

Embedding-based models○

Word-based Language Models○

Object Recognition

Compound models○

Multiple ﬁxed domains
e.g. locations, companies, etc○

Genre/cluster models○

Pluralistic models

Federated Analytics

Sparse Federated Learning & Analytics

SparseAggregation∑

Sliced Model
DownloadSparse Federated Learning & Analytics

PrivateSparseAggregation∑

Private Sliced
Model Download

a

0

b

0

c
d
e

Encrypted 1-Hot Query Vector

Vector of Model Slices (1 per element)

Private Sliced Model Download // Private Information Retrieval010

I want d.
d = 00010.
0

0

0

1

0

×

0

=

0

b

×

0

=

0

c

×

0

=

0

d

×

1

=

d

e

×

0

=

0

Encrypted 1-Hot Query VectoraPrivate Inner
Product via
Homomorphic
Encryption

Vector of Model Slices (1 per element)

Private Sliced Model Download // Private Information Retrieval∑dI want d.
d = 00010.
0

0

d

0

1

d

0

Private Sparse Aggregation // Shuffling via Secure Aggregation← Vector with message-sized slots← Clients choose a random slot

Private Sparse Aggregation // Shuffling via Secure Aggregation
Birthday "Paradox": conﬂicts are likely, even with quite large vectors← Vector with message-sized slots← Clients choose a random slot

Private Sparse Aggregation // Shuffling via Secure Aggregation
Invertible Bloom Lookup Tables (IBLTs)← (pseudonym+message)-sized slots← Clients choose random pseudonym,
map to k slots using hash functions

Private Sparse Aggregation // Shuffling via Secure Aggregation
Invertible Bloom Lookup Tables (IBLTs)← Server recovers (pseudonym+message)
for all non-conﬂict slots

Private Sparse Aggregation // Shuffling via Secure Aggregation
Invertible Bloom Lookup Tables (IBLTs)← Server recovers (pseudonym+message)
for all non-conﬂict slots
Then removes all copies from vector

Private Sparse Aggregation // Shuffling via Secure Aggregation
Invertible Bloom Lookup Tables (IBLTs)← Server recovers (pseudonym+message)
for all non-conﬂict slots
Then removes all copies from vector
De-conﬂicting more slots

Private Sparse Aggregation // Shuffling via Secure Aggregation
Invertible Bloom Lookup Tables (IBLTs)← Server recovers (pseudonym+message)
for all non-conﬂict slots
Then removes all copies from vector
De-conﬂicting more slots
Repeat until all messages extracted(or no more progress)

Private Sparse Aggregation // Shuffling via Secure Aggregation
Invertible Bloom Lookup Tables (IBLTs)

J. Bell, K. Bonawitz, A. Gascon, T. Lepoint, M. Raykova
Secure Single-Server Aggregation with (Poly)Logarithmic
Overhead. CCS 2020.

Figure 4. Expected fraction of messages recovered and probabilityof recovering all messages against the length 𝑙 of the vectors
used. For this the number of clients is 𝑛 = 10000 and each inserts
their message in 𝑐 = 3 places.

Vector Length ~= 1.3x messages!

Differentially Private Federated
Training

Differential
Privacy

Differential privacy is the statistical science of trying to learn
as much as possible about a group while learning
as little as possible about any individual in it.

Andy Greenberg
Wired 2016.06.13

Differential
Privacy

D

Query

Model
M(D)

Differential
Privacy

D

Query

Model
M(D)

D'

Query

Model
M(D')

Differential
Privacy

D

Query

Model
M(D)

D'

Query

Model
M(D')

(ε, δ)-Differential Privacy: The distribution of theoutput M(D) (a trained model) on database (training
dataset) D is nearly the same as M(D′) for all
adjacent databases D and D′∀S: Pr[M(D)∊S] ≤ exp(ε) ∙ Pr[M(D′)∊S] + δRecord-level
Differential
Privacy

D

Query

Model
M(D)

D'

Query

Model
M(D')

(ε, δ)-Differential Privacy: The distribution of theoutput M(D) (a trained model) on database (training
dataset) D is nearly the same as M(D′) for all adjacentdatabases D and D′
adjacent: Sets D and D’ differ only bypresence/absence of one example

M. Abadi, A. Chu, I.
Goodfellow, H. B.
McMahan, I. Mironov, K.
Talwar, & L. Zhang. Deep
Learning with Differential
Privacy. CCS 2016.

User-level
Differential
Privacy

D

Query

Model
M(D)

D'

Query

Model
M(D')

(ε, δ)-Differential Privacy: The distribution of theoutput M(D) (a trained model) on database (training
dataset) D is nearly the same as M(D′) for all adjacentdatabases D and D′
adjacent: Sets D and D’ differ only bypresence/absence of one example user

H. B. McMahan, et al.
Learning Differentially
Private Recurrent
Language Models.
ICLR 2018.

Iterative training with differential privacy

1. Sample a batch of clients uniformly at random

D

r4
r7
r10

r1780

Iterative training with differential privacy

2. Clip each update to maximum L2 norm S

D

r4

Clip to S

r7
r10

r1780

Clip to S

Iterative training with differential privacy

3. Average clipped updates

D

r4

Clip to S

r7
r10

r1780

Average

Clip to S

Iterative training with differential privacy

4. Add noiseD

r4

Clip to S

+

r7
r10

r1780

Average

Clip to S

Iterative training with differential privacy

5. Incorporate into modelD

r4

Clip to S

+

r7
r10

r1780

Average

Clip to S

Updatemodel

There are many details and possibilities

Back to federated learning
data device(another)combinedmodel

updatedmodel∑

initial model

engineerDifferentially private federated learning

data device

Clip updates to limit
a user’s contribution(bounds sensitivity)

Server adds noise
proportional tosensitivity whencombining updates

∑

model

+

updated modelDifferential privacy for language models
LSTM-based predictive language model.
10K word dictionary, word embeddings ∊ℝ96, state ∊ℝ256, parameters: 1.35M. Corpus=Reddit posts, by author.

(4.634, 1e-9)-DP with 763k users(1.152, 1e-9)-DP with 1e8 users
𝔼[users per minibatch] = 5k
𝔼[tokens per minibatch] = 8m

H. B. McMahan, et al. Learning
Differentially Private Recurrent
Language Models. ICLR 2018.

Locally differentially private federated learning

data device

updated model

Clip update and add
noise on eachdevice∑+model

Warner. Randomized response. 1965.
Kasiviswanathan, et. al. What can we learn privately? 2011.

Central DP:

Local DP:easier to get high utility with good privacy

requires much weaker trust assumptions

Can we combine the best of both worlds?

Distributed Differential Privacy

Distributing Trust for Private Aggregation
1

Trusted “third party”

2

Trusted Execution Environments+

3

Trust via Cryptography

+

∑ +
∑
third-party
trustedhardware∑cryptography

Distributed DP via secure aggregation
Noisy/Clipped
updates are
securely summed

Clip update and add
data
devicenoise oneach
device+∑model

𝜀local = 1+𝜀central = 0.1

differentiallyprivateupdated model

Distributed DP via secure aggregation
Challenges faced●●●●

SecAgg operates on a finite group (finite precision) with modulo arithmetic
Discrete Gaussian random variables are not closed under summation
Discrete distributions with finite tails lead to catastrophic privacy failures
Tight DP accounting needs to be fundamentally rederived

Solutions needed●●●●

A family of discrete mechanisms that mesh well with SecAgg’s modulo arithmetic
Closed under summation or have tractable distributions upon summation
Can be sampled from exactly and efficiently using random bits
Exact DP guarantees with tight accounting and no catastrophic failures

The distributed discrete Gaussian mechanism

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (on arXiv)

The distributed discrete Gaussian mechanism
L2 Clip

Discretize

Add Discrete
Gaussian

ModuloClipping

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (on arXiv)

The distributed discrete Gaussian mechanism
L2 Clip

Scale

Discretize

RandomRotation

Add Discrete
Gaussian

Randomized
Quantization

ModuloClipping

The distributed discrete Gaussian mechanism...

L2 Clip

Discretize

Add Discrete
Gaussian

ModuloClipping...

∑

Back to Reals

Dequantization

InverseRotation

InverseScaleFederated EMNIST Classification●●●

Classifying handwritten digits/letters grouped by their writers
Total writers/clients = 3400, number of clients per round = 100
671,585 training examples, 62 classes, model size = 1M parameters

Centralized Continuous GaussianDistributed Discrete Gaussian (18 bits)
Distributed Discrete Gaussian (16 bits)
Distributed Discrete Gaussian (14 bits)
Distributed Discrete Gaussian (12 bits)

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (on arXiv)

StackOverflow Tag Prediction●●●

Predicting the tags of the sentences on Stack Overflow with Logistic Regression
Total users/clients = 342477, number of clients per round = 60
Tags vocab size = 500, Tokens vocab size = 10000, model size = 5M parameters

Centralized Continuous GaussianDistributed Discrete Gaussian (18 bits)
Distributed Discrete Gaussian (16 bits)
Distributed Discrete Gaussian (14 bits)
Distributed Discrete Gaussian (12 bits)

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (on arXiv)Precise DP Guarantees for
Real-World Cross-Device FL

Iterative training with differential privacy

1. Sample a batch of clients uniformly at random

D

r4
r7
r10

r1780

Challenges●

There is no fixed or known database / dataset / population size●

Client availability is dynamic due to multiple system layers and participation
constraints○●"Sample from the population" or "shuffle devices" don't work out-of-the-box

Clients may drop out at any point of the protocol, with possible impacts on
privacy and utility

For privacy purposes, model the environment (availability, dropout) as the
choices of Nature (possibly malicious and adaptive to previous mechanism
choices)Goals●Robust to Nature's choices (client availability, client dropout) in that privacy
and utility are both preserved, possibly at the expense of forward progress.

●

Self-accounting, in that the server can compute a precise upper bound on
the (ε,δ) of the mechanism using only information available via the protocol.

●

Local selection, so most participation decisions are made locally, and as few
devices as possible check-in to the server●

Good privacy vs. utility tradeoffs

Random Check-ins

Clients

RandomCheck-Ins

Training
Round

1
2
...

Part III: Other topics

Improving efficiency and effectiveness
Make trained models
smaller?
Reduce wall-clock training
time?

Personalize for eachdevice?
serverclientdevicesfederatedtraining

model
deployment

model
development
Do more with fewer
devices or less resources
per device?

Support ML workflows likedebugging andhyperparameter searches?

engineer

Solve more types of ML
problems (RL, unsupervisedand semi-supervised, active
learning, ...)?

Ensuring fairness and addressing sources of bias
Bias in training data(amount, distribution)?

serverclientdevicesfederatedtraining

model
deployment

model
Bias in which devices
development
successfully send updates?
engineer
Bias in device availability?

Inference populationdifferent than training
population?

Robustness to attacks and failures
Inference-time evasionattacks

Compromised device
sending malicious
updates
serverclientdevicesfederatedtraining

model
deployment

model
development
Devices training oncompromised data (datapoisoning)

Device dropout, data
corruption in transmission

engineer

Advances and Open Problems in FL
58 authors from 25 top institutions
arxiv.org/abs/1912.04977