The Privacy Blanket of the Shuffle Model
summary
Claims a single‑message shuffle protocol attains mean squared error Θ(n^{1/3}) (so estimation error Θ(n^{1/6})) with a matching lower bound, and achieves logarithmic per‑user communication. The implemented protocol uses randomized rounding into k+1 bins with probability 1−γ and uniform noise with probability γ; analysis couples shuffles and applies concentration (Hoeffding/Bennett). A general blanket decomposition of local randomizers yields privacy amplification formulas (regimes ~ε0/√n or ~ε0/log n); results are constructive and practical via numerical solvers.
AI-written summary · about
chapters (14)
- 0:00Intro
- 2:23Trust vs Accuracy
- 6:51Real Sum in the Shuffle Model
- 7:49Privacy Amplification by Shuffling
- 11:04Real Summation Protocol
- 12:59Analysis Overview
- 16:14Privacy Analysis
- 21:34Blanket of a Local Randomizer
- 25:28Example Blanket Decompositions
- 27:52Amplification: Proof Idea
- 32:05Getting the Bound
- 36:37Numerical Comparison
- 37:49Conclusion
- 40:14Lower Bound
related talks
27mOn Distributed Differential Privacy and Counting Distinct Elements
26mLocally Private Histograms in All Privacy Regimes
35mPrivacy amplification by random allocation
54mPrivacy Amplification from Structured Algorithmic Randomness
01h 00mDifferential Privacy And The Complexity Of Simple Queries
01h 00mDifferential Privacy: Fundamentals to Forefront I
01h 14mTutorial: Privacy, Part III
58mLarge-Scale Private Learning, Part III