The Privacy Blanketof the Shuffle Model
Borja Balle

Joint work with J. Bell, A. Gascón and K. Nissim
Arxiv: 1903.02837

εεεεεεεTrustCentralLocal

Accuracy

Trust vs Accuracy

Θ(1)

Local

1/2

Trust

CentralStatistical
QueriesΘ(n )q : 𝕏 → [0,1]Fq(x1, …, xn) =n∑
i=1

q(xi)

Accuracy

Trust vs Accuracy

Θ(1)

Trust

Central

Shuﬄe
1/2

Θ(n )

Local

Statistical
Queriesq : 𝕏 → [0,1]Fq(x1, …, xn) =n∑
i=1

q(xi)

Accuracy

Trust vs Accuracy

Θ(1)

Trust

CentralO(1)ShuﬄeO(√n) messages[CSUZZ19]

Θ(n )single message

1/2

Θ(n )

Local

StatisticalQueries

1/6

q : 𝕏 → [0,1]Fq(x1, …, xn) =n∑
i=1

q(xi)

Accuracy

Trust vs Accuracy

The Shuffle Model
ℛ:𝕏→𝕐

x1
x2

ℛ

y1

ℛ

y2

ℛyn

⋮
xn

Local Randomizer[BEMMRLRKTS17; EFMRTT19; CSUZZ19]

The Shuffle Model
ℛ:𝕏→𝕐

x1
x2

ℛ

y1

ℛ

y2

⋮
xn

ℛ

yn

Local Randomizern

𝒮:𝕐 →𝕐nyσ(1)𝒮𝜎 randompermutation

yσ(2)

yσ(n)

Trusted Shuﬄer[BEMMRLRKTS17; EFMRTT19; CSUZZ19]

The Shuffle Modelℛ:𝕏→𝕐x1x2ℛy1ℛy2⋮
xnℛynLocal Randomizern

𝒮:𝕐 →𝕐nyσ(1)𝒮𝜎 random
permutation

Privacy Analysis

𝒮∘ℛn(𝜀,𝛿)-DPyσ(2)Utility Analysis

nyσ(n)𝒜∘𝒮∘ℛ

Trusted Shuﬄer[BEMMRLRKTS17; EFMRTT19; CSUZZ19]

Real Sum in the Shuffle Model• Problem Statement• n users, each holding a number in [0,1], estimate the sum• Previous Work [CSUZZ, Eurocrypt 2019]1/2), communication O(1)Onemessage:errorO(n•1/2)
Multiplemessages:
error
O(1),communicationO(n•• Our Result1/6), communication O(log n)Onemessage:
error
𝛩(n•

Privacy Amplification by Shuffling• Problem Statement• Characterize the privacy of shuﬄed mechanisms in terms of the privacyof its local randomizers• Previous Work [EFMRTT, SODA 2019]• Shuﬄe-then-randomize (with adaptativity):• Our Result• Randomize-then-shuﬄe (one randomizer):ε = O (ε0 log(1/δ)/n )for 𝜀0 = O(1)ε = O ((ε0 ∧ 1)eε0

for 𝜀0 <= 0.5 log(n) + O(1)log(1/δ)/n )Real Summation Protocol• Discretize [0,1] into k+1 bins of equal length
1 2ℛ : [0,1] → 0, , , …,1{ k k}• Apply randomized rounding and randomized response with prob. 𝛾ℛ(xi) =Round(xi)∼wp 1 − γ{Uniform∼wp γ• After shuﬄing, add all the messages and remove the bias
𝒜( y )⃗ = deBiasn(∑)
i=1yi

Analysis Overview• Bound the MSE (ie. variance) of the protocol (as a function of k and 𝛾)𝔼(𝒜 ∘ ℛ ( x )⃗ −n2∑ )
ixi

n=O+O
γn()
( k2 )
RoundingUniform• Analyze privacy of the protocol (as a function of k and 𝛾)
k log(1/δ)γ=O( nε 2 )(𝜀,𝛿)-DP• Optimize over k to minimize errorn𝖬𝖲𝖤(𝒜 ∘ ℛ ) = O(n1/3log (1/δ)
ε 4/3)
2/3

2/3 1/3

k = Õ(ε n )Privacy Analysis
x1

ℛx2

ℛx3

ℛx4

ℛx5

ℛx6

ℛ

Privacy Analysis

x2

ℛx3

ℛx4

ℛx5

ℛx6

ℛ01

ℛ

2/3x101

1/3ℛ

Privacy Analysis
11x6ℛ01ℛ

1x52/3ℛ

1/3x400ℛ

1x32/3ℛ

1/3x200ℛ2/3+ γ⋅= (1 − γ) ⋅x1

𝒰1/3

1ℐ0ℛ

Privacy Analysis
11x6ℐ01𝒰

1x52/3𝒰

1/3x400𝒰

1x32/3ℐ

1/3x200ℐ2/3+ γ⋅= (1 − γ) ⋅x1

𝒰

1/3

1ℐ0ℛ

Privacy Analysis
11x6ℐ01𝒰

1x52/3𝒰

1/3x400𝒰

1x3

εε ε2/3ℐ

1/3x200ℐ2/3+ γ⋅= (1 − γ) ⋅x1

𝒰

1/3

1ℐ0ℛ

Privacy Analysis
110112/3ℐ

1/3x6000𝒰

1x52/3𝒰

1

1/3x4xn and blanket

0𝒰

1x3εε ε2/3ℐ

1/3x200ℐ

2/3+ γ⋅= (1 − γ) ⋅x1

𝒰

1/3

1ℐ0ℛ

Privacy Analysis
11100

1

12/30

1

12/3

1/30

ℐ

1x6x’n and blanket

1/3𝒰

2/3x5xn and blanket

0𝒰

1/3x40

𝒰

1x30

εε ε

2/3

ℐ

1/3x200ℐ

2/3+ γ⋅= (1 − γ) ⋅x1

𝒰

1/3

1ℐ0ℛ

Privacy Analysis
11x6ℐ0Bin (n − 1, k + 1 ) + 1

112/3

1/30

12/3

1/30ℙ1𝒰

12/3x510

γx’n and blanket

1/3𝒰xn and blanket

0x40𝒰

1x30

εε ε2/3ℐ

1/3x200ℐ

2/3+ γ⋅= (1 − γ) ⋅x1

𝒰

1/3

1ℐ0ℛ

Bin (n − 1, k + 1 )γ

≥ek log(1/δ)γ=O( nε 2 )ε≤δ

Lower Bound• Theorem: Any (𝜀,𝛿)-DP one-message shuﬄed protocol for realsummation with n inputs in [0,1] and 𝛿 < 0.5 must have

11/3−ε𝖬𝖲𝖤 = Ω n min e , − δ{})2(• Proof Sketch
1. Reduction to i.i.d. case where aggregation is summation and randomizer maps to[0,1] (apply optimal Bayesian denoising)
2. Take inputs to be uniform on partition of [0,1] in n1/3 equally spaced points
3. Prove two lower bounds on MSE, interpolate them, and couple them through privacy

Amplification by Shuffling• Theorem: Shuﬄing n copies of any 𝜀0-LDP randomizer with blanket
parameter 𝛾 gives (𝜀,𝛿)-DP withε2ε0γ(e + 1) (e − e4n(e ε − 1)−ε0 2)(e − 1)⋅ exp −0.86n γ ∧≤δε−εε20γ(e + 1) (e − e 0)2 )(ε2Amplification by Shuffling• Theorem: Shuﬄing n copies of any 𝜀0-LDP randomizer with blanket
parameter 𝛾 gives (𝜀,𝛿)-DP with
ε2ε0γ(e + 1) (e − e4n(e ε − 1)−ε0 2)(e − 1)⋅ exp −0.86n γ ∧≤δε−εε20γ(e + 1) (e − e 0)2 )(ε2• Corollary: Shuﬄing n copies of an 𝜀0-LDP randomizer gives (𝜀,𝛿)-DP with
ε = O ((ε0 ∧ 1)eε0log(1/δ)/n )ε0 ≤ log(n/log(1/δ))/2

Blanket of a Local Randomizer
11

102/3

12/3

1/300

12/3

1/3

00

1/3+ γ⋅= (1 − γ) ⋅Randomized
Response01

Blanket of a Local Randomizer
11102/3

12/3

1/3

00

12/3

1/3

00

1/3+ γ⋅= (1 − γ) ⋅Randomized
Response01• Theorem (Blanket Decomposition): Every 𝜀0-LDP randomizer admits a(unique maximal) mixture decomposition where one of the components isindependent of the input

Blanket of a Local Randomizer
11102/3

12/3

1/300

12/3

1/300

1/3+ γ⋅= (1 − γ) ⋅RandomizedResponse01• Theorem (Blanket Decomposition): Every 𝜀0-LDP randomizer admits a(unique maximal) mixture decomposition where one of the components is
independent of the inputℛ(x) = (1 − γ)ℛ′(x) + γωℛ:𝕏→𝕐ℛ′ : 𝕏 → 𝕐ω ∈ Dist(𝕐 )e−ε0≤γ≤1

Blanket of a Local Randomizer11

12/30

12/3

1/300

12/3

1/300

1/3+ γ⋅= (1 − γ) ⋅RandomizedResponse01• Theorem (Blanket Decomposition): Every 𝜀0-LDP randomizer admits a(unique maximal) mixture decomposition where one of the components is
independent of the inputℛ(x) = (1 − γ)ℛ′(x) + γωℛ:𝕏→𝕐ℛ′ : 𝕏 → 𝕐
ω ∈ Dist(𝕐 )e−ε0≤γ≤1Blanket Constructionγ=∫𝕐 x∈𝕏

min pℛ(x)(y)dypω(y) =minx∈𝕏 pℛ(x)(y)γωωωωExample Blanket Decompositions
𝜀0-LDP RR on [k]𝜀0-LDP Laplace on [0,1]𝜎2 Gaussian on [0,1]kγ= εe 0+k−1
γ=eε0−22γ = 2ℙ[N(0,σ ) ≤ − 1/2]

Amplification: Proof Idea
• General idea
• Couple who samples from the blanket in both executions• Reveal the identity of who samples from the blanket (joint convexity)• Remove the data from the users in 1…n-1 who sampled from R’ (post-processing)• Define privacy amplification random variableY∼ωℛL = Lx,x′ =εpℛ(x)(Y) − e pℛ(x′)(Y)pω(Y)ε𝔼[L] = 1 − e < 0γ(e−ε0−eε+ε0ε0) ≤ L ≤ γ(e − e• Reduce to bounding expectation, apply concentration for bounded r.v.’sBin(n,γ)

1nεn⃗sup (ℙ[𝒮 ∘ ℛ ( x ) ∈ E] − e ℙ[𝒮 ∘ ℛ ( x ′⃗ ) ∈ E]) ≤ 𝔼
Li∑γn[]
Ei=1+ε−ε0)Getting the Bound• Applying Hoeﬀding’s inequality we getBin(n,γ)

1γ(e + 1) (e − e𝔼Li ≤ε − 1)γn [ ∑4n(e]i=1ε+2ε0−ε0 2)(e − 1)⋅ exp −0.86n γ ∧ε−εε200)2 )γ(e+1)(e−e(ε• Refinements:• Use mechanism-specific bounds on L and 𝛾• Alternative concentration bounds, eg. Bennett’s inequality

2

Numerical Comparison
ε(n, ε0)

ε0(n, ε)ε0(n, ε)Conclusion• Matching upper and lower bounds for one-message, one-randomizer realsummation in the shuﬄe model1/6) and communication O(log n)
Error
𝛩(n•

• First tight shuﬄe-native lower bound• General and flexible privacy amplification bounds for randomize-thenshuﬄe one-randomizer protocols in the shuﬄe model• Simple analysis via privacy blanket, without subsampling