The Privacy Blanket of the Shuffle Model

Borja Balle; James Bell; Adria Gascon; Kobbi Nissim

Source-linked AI summary

The Privacy Blanket of the Shuffle Model

Borja Balle, James Bell, Adria Gascon, Kobbi Nissim

arXiv:1903.02837v2Mar 7, 2019cs.LGcs.CRstat.ML

TL;DR

The paper studies how anonymous shuffling changes the privacy, accuracy, and trust properties of differential privacy relative to local and curator models. It introduces an optimal single-message protocol for summing real values, proves a matching lower bound, and develops privacy amplification bounds based on a privacy blanket. The results place single-message shuffling strictly between the curator and local models while extending amplification analysis to broader parameter ranges.

Problem
The paper addresses limited understanding of the accuracy and privacy amplification achievable by single-message shuffle-model protocols for real-valued summation.
Method
The paper combines a single-message shuffled local-randomizer protocol, a lower-bound analysis, and a privacy-blanket decomposition for amplification bounds.
Results
The protocol sums values in [0, 1] with O(log n)-bit communication and O(n1/6) standard deviation, while matching lower bounds establish optimal accuracy.
Takeaways & Limitations
Single-message shuffling achieves accuracy substantially better than local protocols but remains less accurate than curator-model differential privacy for the studied summation problem.
Takeaways & Limitations
The shuffle model’s privacy guarantee degrades with the fraction of users who deviate from the protocol, and Gaussian-mechanism amplification bounds are left for future work.

Abstract

from arXiv · show

This work studies differential privacy in the context of the recently proposed shuffle model. Unlike in the local model, where the server collecting privatized data from users can track back an input to a specific user, in the shuffle model users submit their privatized inputs to a server anonymously. This setup yields a trust model which sits in between the classical curator and local models for differential privacy. The shuffle model is the core idea in the Encode, Shuffle, Analyze (ESA) model introduced by Bittau et al. (SOPS 2017). Recent work by Cheu et al. (EUROCRYPT 2019) analyzes the differential privacy properties of the shuffle model and shows that in some cases shuffled protocols provide strictly better accuracy than local protocols. Additionally, Erlingsson et al. (SODA 2019) provide a privacy amplification bound quantifying the level of curator differential privacy achieved by the shuffle model in terms of the local differential privacy of the randomizer used by each user. In this context, we make three contributions. First, we provide an optimal single message protocol for summation of real numbers in the shuffle model. Our protocol is very simple and has better accuracy and communication than the protocols for this same problem proposed by Cheu et al. Optimality of this protocol follows from our second contribution, a new lower bound for the accuracy of private protocols for summation of real numbers in the shuffle model. The third contribution is a new amplification bound for analyzing the privacy of protocols in the shuffle model in terms of the privacy provided by the corresponding local randomizer. Our amplification bound generalizes the results by Erlingsson et al. to a wider range of parameters, and provides a whole family of methods to analyze privacy amplification in the shuffle model.

1 Introduction

The shuffle model inserts anonymous message shuffling between local randomization and analysis, occupying a trust and accuracy position between the local and curator models. This work develops a single-message real-valued summation protocol, matching lower bound, and privacy-amplification analysis.

Trust assumptions: The model’s privacy guarantee degrades when users deviate because users’ messages help protect one another’s privacy.Unlike the curator model, privacy responsibility is not entirely held by a trusted curator.
Shuffle model: The shuffle model anonymously permutes users’ privatized messages before an untrusted analyzer processes them.Single-message protocols apply a local randomizer, shuffle the resulting messages, and then post-process them.
Private summation: The proposed summation protocol is unbiased, uses one O(log n)-bit message per user, and has standard deviation Oε,δ(n1/6) for inputs in [0, 1].It uses randomized rounding and a randomized-response privacy blanket over a finite fixed-point domain.
Private summation: Any single-message shuffled summation protocol has mean squared error of order Ω(n1/3), matching the protocol’s accuracy order.The lower-bound argument uses input distributions that constrain the local randomizer’s expected square error.
Position among models: The single-message shuffle model is strictly between curator and local differential privacy models in achievable summation accuracy.The paper reports more accurate protocols than the local model but does not attain curator-model accuracy.
Privacy amplification: The privacy blanket decomposes a local randomizer’s output into input-independent and input-dependent components, enabling generic amplification bounds without subsampling amplification.The resulting bound extends prior analyses to local privacy levels logarithmic in n.

2 Preliminaries

The preliminaries position the single-message shuffle model between curator and local differential privacy by anonymizing one locally randomized message per user before analysis. They define the protocol, privacy view, secure shuffling abstraction, and MSE-based utility measures.

Curator and local models: Curator DP assumes a trusted collector adds noise centrally, whereas local DP requires each user to randomize independently before sending data to an analyzer.
Shuffle model: The single-message shuffle model anonymizes one message per user through a random permutation unknown to the data collector.
Protocol definition: A shuffle protocol consists of a local randomizer R and analyzer A, with privacy required for their combination after shuffling.
Secure shuffling: Perfect shuffling means the collector learns the multiset of messages, equivalently a histogram counting occurrences rather than user-message associations.
Utility measure: Accuracy for real summation is evaluated using MSE, including fixed-input, worst-case, and input-distribution averages.

3 The Privacy of Shuffled Randomized Response

This section analyzes a single-message shuffled randomized-response protocol for private histograms. Its privacy comes from random reports that form a shared blanket, while the theorem gives a parameterized (ε, δ)-DP guarantee and motivates a broader amplification view.

Protocol: The protocol applies k-ary randomized response: with probability 1 − γ it reports the true value, and with probability γ it reports a uniformly random domain element.
Protocol: Approximately γn users contribute random reports and the remaining users contribute truthful reports, yielding a histogram decomposed into random and data-dependent components.
Privacy analysis: The privacy argument assumes the server knows which users randomized and all other users’ inputs, thereby proving privacy under a stronger adversarial view.
Privacy intuition: A user’s input is hidden when that user contributes a blanket report independent of the input; otherwise the random histogram masks the truthful value.
Privacy guarantee: Theorem 3.1 establishes (ε, δ)-DP for the shuffled mechanism under parameter constraints including ε ≤ 1 and a prescribed choice of γ.
Proof scope: The ε ≤ 1 assumption is a technical convenience for the Chernoff-based proof; Bennett’s inequality can provide a similar result without that restriction.
Amplification interpretation: The analysis interprets the protocol as privacy amplification: shuffling n copies of an ε0-LDP randomizer yields curator-level (ε, δ)-DP for a broader parameter regime.

4 Optimal Summation in the Shuffle Model

The paper develops a single-message shuffle protocol for summing values in [0, 1], then proves that its mean-squared-error rate is optimal.

Protocol: The protocol estimates sums of real inputs xi ∈ [0, 1] using a parameterized local randomizer and analyzer in the single-message shuffle model.Users apply randomized rounding to fixed-point inputs, then randomized response and postprocessing estimate the sum.
Protocol: Randomized rounding makes the fixed-point encoding unbiased and contributes mean squared error at most 1/(4k^2).The encoding uses a Bernoulli variable to preserve the expected value of each rounded input.
Accuracy: For every ε ≤ 1, δ ∈ (0, 1], and n ∈ N, suitable parameters give an (ε, δ)-differentially private protocol for real summation.The protocol also yields an unbiased estimator for statistical queries in the same model.
Accuracy: Choosing k = (n/c)1/3 yields mean squared error O(c2/3n1/3), with parameters selected to satisfy differential privacy.The resulting estimator is unbiased, so its mean squared error equals its variance.
Lower bound: Any differentially private single-message shuffle protocol for real summation has MSE Ω(n1/3), establishing optimality and an accuracy separation from curator and local models.The lower-bound proof reduces protocols to a randomizer with image [0, 1] and a summing analyzer, then constructs an input distribution forcing the error rate.

5 Privacy Amplification by Shuffling

The paper develops privacy amplification bounds for shuffled local randomizers using a general privacy-blanket decomposition. The bounds recover earlier dependencies for small local privacy and extend amplification to broader parameter regimes.

Main bound: Shuffling n copies of an ε0-LDP randomizer with ε0 = O(log(n/log(1/δ))) gives ε = O((ε0 ∧ 1)e^ε0√(log(1/δ)/n)).This is the paper’s asymptotic amplification guarantee for the shuffled mechanism.
Main bound: The bound matches earlier dependencies when ε0 = O(1) and extends amplification beyond that regime.For constant central privacy, ε0 = O(log(ε^2n/log(1/δ))) suffices for any pure LDP randomizer.
Privacy blanket: The analysis decomposes each local output distribution into input-dependent and input-independent components using total variation similarity γR and a blanket distribution ωR.The blanket component occurs with probability γR and is independent of the user’s input.
Calibration: The method yields a nonlinear relation F(ε, ε0, γ, n) ≤ δ and supports mechanism-specific numerical calibration in addition to asymptotic bounds.Exact γ values can provide tighter bounds for particular mechanisms.
Privacy blanket: Any ε0-LDP local randomizer has total variation similarity γ ≥ e−ε0, linking local privacy directly to the probability of input-independent outputs.The probability of sampling from the blanket increases as the local mechanism becomes more private.
Scope: The presented concentration analysis does not cover the Gaussian mechanism because its privacy-amplification variables are unbounded.The paper leaves concentration methods that do not rely on boundedness for future work.

6 Experimental Evaluation

The evaluation finds that the paper’s generic privacy-amplification bounds improve on prior bounds, while Bennett-based and mechanism-specific analyses often yield further gains over Hoeffding-based alternatives.

Our generic bounds give significantly smaller ε values than the prior bound from [14].The comparison is made for generic randomizers, whose prior constants were not optimized.
Bennett is better than Hoeffding for large n, whereas Hoeffding is better for small n with generic local randomizers.This comparison concerns the generic-randomizer bounds in panel (i).
Mechanism-specific information improves the Hoeffding bound, and Bennett remains better than Hoeffding for every evaluated mechanism.The Bennett advantage is especially pronounced for randomized response with k = 100.
The gain from Bennett over Hoeffding is greater for randomized response with k = 100 than for other mechanisms.For fixed ε0 and large k, the total variation similarity of randomized response is close to 1.
Bennett bounds also provide a significant advantage over Hoeffding when the randomized-response domain size grows with the parameter t.
The paper attributes practical importance to maximizing ε0 for the local randomizer while maintaining a prescribed privacy level for the shuffled protocol.The stated consequence is more accurate protocols under that privacy calibration.

7 Conclusion

The conclusion establishes a separation among curator, shuffle, and local models and presents an optimal single-message summation protocol alongside a privacy-blanket framework for amplification bounds.

The single-message shuffle model cannot match curator-model accuracy but can be significantly more accurate than the local model.
The protocol for summing n real values in [0, 1] uses O(log n)-bit communication and has O(n^1/6) standard deviation.The paper also provides a matching accuracy lower bound for this problem.
The paper introduces the privacy blanket of a local randomizer to obtain generic amplification bounds that improve on prior work.The framework covers results by Erlingsson et al. and Cheu et al.
The privacy-blanket proof does not rely on privacy amplification by subsampling, unlike the proofs in [14] [11].
The blanket decomposition may also be useful beyond the shuffle model, including in studying interactivity in local differential privacy.The conclusion notes that Joseph et al. used a generalization of this decomposition.

A.1 Proofs from Section 5.1

The appendix derives total variation similarity and blanket distributions for randomized response, Laplace, and Gaussian local randomizers, including an explicit Laplace result.

For an ε0-LDP randomized response mechanism over [k], the appendix derives a minimum-output-probability expression used in the blanket analysis.
The proof of the randomized-response lemma uses ε0-local differential privacy together with symmetry or distribution-specific calculations.
The Laplace mechanism is analyzed through its density and a decomposition of γR into two integrals.
γR = e^-ε0/2 for the analyzed Laplace mechanism.The same argument shows that its blanket distribution is again Laplace.
For a Gaussian local randomizer, γR is expressed using tail probabilities of Gaussian variables with variance σ^2.

A.2 Proof of Lemma 5.3

The proof of Lemma 5.3 bounds shuffled-output divergence by decomposing local randomizers into blanket and non-blanket components, conditioning on blanket-sampling users, and reducing the analysis to their count.

Each local-randomizer distribution is decomposed as μx = (1 − γ)νx + γω, separating a data-dependent component from the blanket distribution.
The shuffled protocol output is represented as a random multiset of independently randomized user messages.Neighboring inputs produce multisets Y and Y′ that differ in one user’s randomized message.
Conditioning on the subset B of users sampling from the blanket reduces the divergence analysis to conditional output distributions for each B.The probability of a particular B depends on its size through γ^|B|(1 − γ)^(n−1−|B|).
The proof uses joint convexity and a post-processing-type inequality to control the divergence between shuffled outputs.
A multiset inequality permits ignoring users who do not sample from the blanket before expressing the remaining divergences through privacy-amplification random variables.
Because blanket samples are independent and identically distributed, the conditional analysis depends on B only through m = |B|.This yields the random multiset Wm of m blanket samples.

A.3 Other Proofs from Section 5.2

These proofs establish privacy amplification bounds for shuffled local randomizers by decomposing privacy loss and applying concentration inequalities. The resulting mechanism is (ε, δ)-differentially private under the stated parameter conditions.

Privacy blanket: The blanket distribution is used to separate input-independent randomness from input-dependent output distributions in the privacy-loss analysis.The proof expands the definition of ω and uses ε0-LDP constraints to bound the resulting expressions.
Privacy amplification: Hoeffding’s inequality yields a privacy amplification bound for generic ε0-LDP local randomizers.The argument relies on concentration of the summed privacy-loss variables and the preceding bounds on their tails.
Privacy amplification: The analysis bounds the expectation of the positive privacy loss by applying Lemmas 5.4 and 5.5 to sums of independent privacy-loss variables.The proof uses total variation similarity γ and ε0-local differential privacy to instantiate the parameters in the concentration bound.
Privacy amplification: The mechanism M is (ε, δ)-DP when the derived inequality holds, with the stated assumption ε0 ≤ log(n / log(1/δ))/2 used to select the constant c.The proof combines inequalities (7) and (8) before applying the parameter assumption.

A.4 Proofs from Section 5.3

These proofs specialize the concentration analysis to randomized response and Laplace mechanisms. They derive moment bounds and compare Hoeffding- and Bennett-based privacy amplification bounds for specific local randomizers.

Concentration bounds: Bennett’s inequality provides an alternative concentration bound for the summed privacy-loss variables under the stated assumptions.The proof uses the same general privacy-loss framework while replacing the Hoeffding step with Bennett’s inequality.
Randomized response: For randomized response, the blanket distribution is uniform and the data-dependent distribution is concentrated on the input.For an ε0-LDP randomized response mechanism on [k], ω(y) = 1/k and νx(y) = I[y = x].
Randomized response: The randomized-response privacy-loss analysis derives a second-moment expression involving γ, ε, and the domain size k.The resulting expression is EL2 = γ2(1 −eε)2 + (1 −γ)2k(e2ε + 1) + 2γ(1 −γ)(1 −eε)2.
Laplace mechanism: The Laplace mechanism’s blanket distribution is a Laplace density centered at 1/2 for inputs on [0, 1].The proof identifies it as ω(y) = ε0/2 e−ε0|y−1/2| and then bounds the relevant quantities for x ∈ [0, 1].
Evaluation: Figure 3 compares privacy-amplification bounds across generic and specific local randomizers, fixed ε0 or ε settings, and Hoeffding versus Bennett analyses.One panel considers δ = n−2, while another evaluates randomized response with domain size k = n1/3.