PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Differential Privacy via Shuffling

Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, Maxim Zhilyaev

arXiv:1808.01394v3cs.CRcs.DS

TL;DR

The paper asks how distributed differential privacy can achieve useful accuracy without trusting a central server or relying on costly MPC. It introduces and analytically studies a shuffled model that anonymously permutes user messages, finding central-like accuracy for sum queries but an intermediate position for restricted selection problems.

  • Problem

    Local differential privacy protects users and scales easily but has limited accuracy, while central-model utility requires trusting a collector and MPC alternatives remain costly for large deployments.

  • Method

    The paper studies a shuffled model that adds an anonymous shuffler, which randomly permutes locally generated user messages before a data collector analyzes them.

  • Results

    The shuffled model essentially matches centralized error for Boolean counting queries, while one-message protocols for variable selection require exponentially more samples than central protocols.

  • Takeaways & Limitations

    Shuffling provides central-like utility for some queries while giving evidence that its power remains strictly between the central and local models for selection.

  • Takeaways & Limitations

    The paper’s lower-bound results do not apply to protocols sending multiple messages through the shuffler, and an associated communication tradeoff remains open.

Abstract

from arXiv · show

We consider the problem of designing scalable, robust protocols for computing statistics about sensitive data. Specifically, we look at how best to design differentially private protocols in a distributed setting, where each user holds a private datum. The literature has mostly considered two models: the "central" model, in which a trusted server collects users' data in the clear, which allows greater accuracy; and the "local" model, in which users individually randomize their data, and need not trust the server, but accuracy is limited. Attempts to achieve the accuracy of the central model without a trusted server have so far focused on variants of cryptographic MPC, which limits scalability. In this paper, we initiate the analytic study of a shuffled model for distributed differentially private algorithms, which lies between the local and central models. This simple-to-implement model, a special case of the ESA framework of [Bittau et al., '17], augments the local model with an anonymous channel that randomly permutes a set of user-supplied messages. For sum queries, we show that this model provides the power of the central model while avoiding the need to trust a central server and the complexity of cryptographic secure function evaluation. More generally, we give evidence that the power of the shuffled model lies strictly between those of the central and local models: for a natural restriction of the model, we show that shuffled protocols for a widely studied selection problem require exponentially higher sample complexity than do central-model protocols.

1 Introduction

Distributed differential privacy balances privacy, utility, scalability, and trust. The shuffled model adds anonymous message permutation to local protocols, matching central-model accuracy for some queries while remaining weaker for restricted selection tasks.

  • Motivation: Local differential privacy lets users retain control of their data through simple, scalable one-message protocols, but sharply limits utility.The local model avoids fully trusting the collector, yet often requires enormous datasets and has mainly been deployed by companies with billions of users.
  • Motivation: Cryptographic MPC can avoid a trusted collector, but its computation, communication, interaction, and maintenance costs hinder large deployments.The paper therefore seeks simpler distributed primitives that retain stronger utility without general secure function evaluation.
  • The shuffled model: The shuffled model augments local differential privacy with an anonymous channel that randomly permutes user messages before analysis.The paper treats the shuffler as an abstract service and studies it as an intermediate model between local and central privacy.
  • Positive results: For Boolean-valued counting queries, a simple non-interactive shuffled protocol essentially matches centralized error, and bounded real-valued queries are also supported with additional communication.These protocols suffice to implement algorithms in the statistical queries model, including gradient descent.
  • Negative results: For variable selection, one-message shuffled protocols have exponentially larger sample complexity than central protocols, while remaining polynomially better than local protocols.This comparison supports a strict ordering of central, shuffled, and local models for selection accuracy under the one-message restriction.

2 Overview of Results

The shuffled model combines local randomization with anonymous shuffling, enabling central-like accuracy for statistical queries while retaining distributed deployment properties. The paper also shows that one-message shuffled protocols face strong lower bounds for variable selection and histograms.

  • Model: The shuffled model sends user-encoded messages through a random permutation before analysis, with one-message protocols restricting each user to m = 1.Privacy is defined for the shuffled collection of all users’ messages.
  • Positive results: Theorem 2.1 gives bounded real-valued statistical queries shuffled-model error that nearly matches the best central-model utility.The protocol is (ε,δ)-differentially private under the theorem’s stated parameter conditions.
  • Positive results: Boolean-valued queries admit a simple protocol in which each user sends a single one-bit message after randomized response.The protocol estimates sums of bits and is described as having a slightly nicer guarantee and form.
  • Positive results: The protocol for real-valued queries requires Θ(ε√n) bits per user, unlike local protocols that use one bit but incur larger error.The paper states that whether this communication tradeoff is necessary remains open.
  • Negative results: For one-message shuffled protocols, private randomization can be transformed into a local-DP protocol with ε increased by ln n.This transformation lets the authors import local-model lower bounds.
  • Negative results: Variable selection requires n = Ω(d^1/17) samples in the one-message shuffled model, whereas the central model solves it with n = O(log d).The lower bound holds even when data are drawn iid from a product distribution.
  • Negative results: One-message shuffled histogram protocols have error growing polylogarithmically with domain size, unlike central-model histograms with no domain-size dependence.The central guarantee extends even to infinite domains.
  • Negative results: The lower-bound proofs do not apply to protocols sending multiple messages, and the paper leaves the general model’s exact power open.Applying the bit-sum protocol repeatedly gives n = ˜O(d) samples in the general shuffled model, but improvement is unknown.

3 Model and Preliminaries

The shuffled model represents protocols as randomized encoding, permutation, and analysis, with privacy applied to the shuffled message set. The section also establishes post-processing and composition tools for analyzing privacy and accuracy.

  • Privacy tools: Post-processing preserves (ε,δ)-differential privacy, and shuffled protocols can be composed while using the shuffler once.Composition changes the privacy parameters according to the stated ε′ and δ′ + Tδ bounds.
  • Protocol structure: A distributed protocol consists of a randomized encoder R, a shuffler S, and an analyzer A.R maps each user’s datum to messages, S uniformly permutes all messages, and A estimates the target function.
  • Protocol structure: The shuffled model includes one-message protocols as the case m = 1, while general protocols may send multiple messages per user.Privacy parameters may depend on the number of users n.
  • Privacy definition: Shuffled-model privacy is defined by the differential privacy of the encoded messages after shuffling, before analysis.The full analyzer inherits these guarantees through post-processing.
  • Accuracy: Accuracy is defined as producing an estimate within distance α of the target function with probability at least 1 −β.The distance measure is application-dependent and guarantees may depend on n.

4 A Protocol for Boolean Sums

The Boolean-sum protocol randomizes a subset of users’ bits, leaves the remaining inputs unchanged, shuffles the resulting messages, and debiases their sum. Its privacy analysis yields parameters that support central-model-level accuracy.

  • Protocol: The protocol Pλ estimates the sum of n Boolean inputs using a randomization parameter λ that trades privacy against accuracy.When λ = n, every output is independent of its input and privacy is trivially (0,0).
  • Protocol: A random set of λ users sends random bits, while the remaining users send their input bits; the shuffled output is shifted and scaled into an unbiased sum estimator.Each user sends one message.
  • Accuracy: The resulting parameter choice gives a shuffled Boolean-sum protocol whose error essentially matches centralized algorithms.The section derives the final accuracy statement from the error theorem and the privacy-calibrated choice of λ.
  • Privacy analysis: The privacy proof analyzes an equivalent counting process Cλ and transfers its guarantees to Pn,λ through post-processing and distributional equivalence.The auxiliary analysis proceeds through fixed and randomly sampled sets of randomized users.
  • Privacy analysis: Randomly selecting the users who randomize improves privacy by roughly a factor of 1 −s/n when the selected set has size s close to n.This amplification is central to the privacy analysis for random subsets.

5 A Protocol for Sums of Real Numbers

The real-sum protocol extends the Boolean protocol by randomized rounding inputs in [0,1] into bits, running shuffled bit-sum protocols, and averaging their estimates. Multiple rounds reduce rounding error but require multiple messages.

  • Protocol: The protocol estimates sums of bounded real inputs in [0,1] by randomly rounding each input to Boolean values with the same expected value.The rounding encoder can output r bits per user.
  • Accuracy: The encoder’s additional rounding error decreases as r increases, but the resulting real-sum protocol is not one-message.Randomized rounding introduces a second source of error alongside the bit-sum protocol’s error.
  • Protocol: The rounded bits are processed by multiple copies of the shuffled Boolean-sum protocol, and the resulting estimates are averaged.This construction uses composition to analyze privacy.
  • Guarantees: For sufficiently large n and suitable λ,r, the real-sum protocol is both (ε,δ)-differentially private and accurate for every input vector in [0,1]^n.The privacy guarantee follows from composition of the private bit-sum protocols.
  • Accuracy: When ε < 1/√n, one rounding repetition suffices because rounding error is smaller than the bit-sum protocol’s existing error.For larger ε, the construction uses more elaborate rounding with r > 1.

6 Lower Bounds for the Shuffled Model

The lower-bound analysis shows that one-message shuffled protocols can be transformed into local protocols with comparable accuracy and weaker privacy, transferring local-model impossibility results. This yields strong separations from the central model for selection and histograms.

  • One-message model: In the one-message shuffled model, each user applies an identical local randomizer and sends one indivisible message to the shuffler.The section studies the consequences of this restriction for central-versus-shuffled sample complexity.
  • Shuffled-to-local transformation: The transformation gives local privacy εL = 8(εS + ln n) with zero δ, while preserving accuracy up to the stated parameter changes.The guarantee assumes εS ≤ 1 and δS < n^-8.
  • Lower bounds: Local-model impossibility results therefore imply related impossibility results for one-message shuffled protocols, producing strong central-model separations.The argument relies on the local randomizer itself satisfying non-trivial local differential privacy.
  • Shuffled-to-local transformation: A private one-message shuffled protocol can be transformed into a local protocol with the same output distribution and therefore the same accuracy.The transformed local protocol incorporates shuffling into its analyzer.
  • Selection: For selection, multi-message shuffled protocols need ˜O((1/ε^2)d log d) samples, whereas the central model needs only O((1/ε) log d).Selection asks for a coordinate whose aggregate bit value is approximately maximal.
  • Histograms: For histograms, the central and one-message shuffled models are qualitatively different: the domain size D may be infinite centrally but must be bounded in the one-message model.The comparison follows from the transferred local lower bound and the central-model guarantee.

A Privacy of Bit Sum Protocol

The section establishes differential privacy for the bit-sum protocol by bounding its parameter λ, with the privacy analysis proceeding through Claim 4.6.

  • Claim 4.6 expresses the privacy of Cλ in terms of λ.
  • For δ > 0 and n ≥ λ satisfying the stated logarithmic condition, the privacy claim applies.
  • The proof applies Claim 4.5 to each term in the sum.
  • Because ε1(s) decreases with s, the bound is maximized at the lower bound on s.
  • The resulting bounds complete the privacy proof for the protocol.

B Accuracy of Bit Sum Protocol

The bit-sum protocol is analyzed through its randomized messages, whose independent contributions yield accuracy guarantees; an appropriate λ matches the Gaussian mechanism’s error order while preserving differential privacy.

  • The protocol’s error can achieve ˜O((1/ε)log(1/δ)) for sufficiently large target ε.
  • Each randomized message is analyzed through its mean and variance before deriving concentration bounds for the summed estimate.
  • The output is a rescaled sum of independent messages, enabling mean-and-variance calculations by linearity of expectation.
  • Corollary B.3 gives a high-probability accuracy guarantee for Pn,λ under the stated constraints on β and λ.
  • With λ chosen as in Lemma 4.8, the bit-sum error has the same order as the Gaussian mechanism.
  • There exists λ such that Pn,λ is (ε,δ)-differentially private and satisfies the stated accuracy bound with probability at least 1 −β.

C Accuracy of Real Sum Protocol

The real-sum protocol extends the bit-sum construction through randomized bit encodings, then combines privacy composition with concentration bounds to obtain accuracy guarantees.

  • The real-sum protocol’s error is analyzed by choosing parameters λ and r.
  • Each real-valued input is encoded as r bits, forming the collection B of randomized encoding bits.
  • Only one encoding bit is random, while the remaining bits contribute ⌊xi · r⌋ to the encoding sum.
  • The encoded estimator is unbiased and concentrated for fixed encodings of the real-valued inputs.
  • Theorem 5.5 bounds the real-sum protocol’s error after choosing λ and r to satisfy (ε,δ)-differential privacy.
  • Privacy follows by composing the bit-sum protocol’s guarantees across the encoded bits.

D From Approximate DP to Pure DP for Local Protocols

This section extends an approximate-DP local protocol to a pure-DP counterpart while preserving accuracy up to a constant-factor change in failure probability.

  • The extension targets local protocols that are both (ε,δ)-differentially private and (α,β)-accurate.
  • For ε > 2/3 and n ≥ 3, the construction produces an (8ε,0)-differentially private protocol.
  • The transformed protocol remains (α,4β)-accurate with respect to the same function.
  • The proof constructs a new randomizer from the original local randomizer, with parameters selected later for privacy and accuracy.

D.1 Privacy Analysis

The transformed local randomizer Rk,T preserves differential privacy with an explicit privacy guarantee. Its analysis bounds the output probabilities by conditioning on the random binary selection bits and applying concentration to their sum.

  • (8ε,0)-differential privacy holds for Rk,T when k ∈(0,2e^-2ε) and T ∈N.This is stated as Claim D.2 for any (ε,δ)-differentially private base algorithm R.
  • Rk,T samples auxiliary outputs vt from R(c) and selects among them using random bits bt, returning the selected value yk,T.The randomizer takes x, k, and T, while using black-box access to R and a public reference input c.
  • When no bit is set, the selected index is uniform over [T]; when bits are set, the index is uniform over the positions whose bits equal one.The privacy proof separates these cases when bounding each summand.
  • The denominator involves a sum of independent Bernoulli variables with expectations in [L,U], enabling a comparison with binomial random variables.The analysis uses a concentration corollary for Bernoulli variables with heterogeneous expectations bounded between L and U.
  • The distribution of the auxiliary vector V is independent of the private value x, allowing a symmetric completion of the privacy argument.This independence supports comparing neighboring inputs through the same auxiliary-output distribution.

D.2 Accuracy Analysis

The accuracy analysis compares the transformed protocol with the original protocol by controlling the statistical distance between their randomized outputs. Under suitable parameter choices, the transformed protocol retains α accuracy with error probability at most 4β.

  • The transformed protocol Pn,k,T remains (α,4β)-accurate for suitable parameters.This is the stated accuracy guarantee obtained from the privacy-preserving transformation.
  • The accuracy proof uses independent auxiliary variables vi,t for each user and repetition, with 2n·T such variables in total.The variables bi,t and vi,t are indexed by user i and repetition t.
  • The proof first shows that Yk,T is statistically close to Y, then applies the same analysis function An to both output distributions.The statistical-distance contribution is bounded by 3β, which combines with the original β error to yield 4β.
  • If event E2 does not occur, every transformed user output lies in its corresponding Good(c,xi) set, so Yk,T lies in the product set Good.This restricts the transformed outputs to values supported by the base randomizer on the reference input.
  • The proof decomposes the transformed error probability according to output vectors whose probability increases or decreases relative to the original distribution.The set I contains output vectors with positive probability difference ΔY.
  • The parameter-selection argument chooses k and an integer T so that the transformed error term βk,T is at most 4β.Claim D.9 supplies an integer T with βk,T ≤4β, completing the accuracy guarantee.

E Concentration Inequalities

The appendix states three concentration inequalities used in the paper: Chernoff, Hoeffding, and Bernstein bounds. They cover independent binary variables, bounded independent variables, and centered bounded variables with variance control, respectively.

  • Chernoff’s bound applies to independent {0,1}-valued random variables with a common mean.The theorem provides a tail bound for every β > 0.
  • Hoeffding’s inequality applies to independent random variables with a common mean and values bounded in (a,b).It is stated for every β > 0.
  • Bernstein’s inequality applies to independent mean-zero variables bounded in [−1,1] with variance σ^2 > 4.The appendix states this bound for every β > 0.
Loading 1808.01394v3…