The Power of Differentially Oblivious Shuffle in Distributed Privacy Mechanisms

Learn about the power and implications of differentially oblivious shuffles in distributed privacy mechanisms in this technical talk from the 2022 Symposium on Foundations of Responsible Computing. Explore how replacing traditional shufflers with differentially oblivious (DO) shuffles in distributed differential privacy mechanisms can lead to significant efficiency improvements while maintaining privacy-utility tradeoffs. Discover the optimal privacy amplification theorem that emerges when combining locally differentially private mechanisms with DO-shufflers, and examine practical applications in real summation and histograph problems. Understand why multi-message protocols in the DO-shuffle model prove more powerful than single-message approaches, with detailed proofs, examples, and visualizations demonstrating these concepts. Gain insights into how DO-shuffles can be implemented through trusted hardware or cryptography, offering a promising alternative to central data curator models in privacy-preserving computations.