Privacy Amplification via Shuffled Check-Ins
This work addresses privacy concerns in distributed systems for users and organizations, offering a novel protocol with enhanced privacy guarantees, though it builds incrementally on existing differential privacy and shuffling techniques.
The paper tackles the problem of achieving strong privacy guarantees in distributed computation by introducing a shuffled check-in protocol that allows clients to independently decide participation, eliminating server-initiated subsampling. The result shows tight privacy guarantees through privacy amplification with improved privacy accounting using Rényi differential privacy, and includes the first evaluation of generic shuffling mechanisms like Gaussian mechanism in this distributed setting.
We study a protocol for distributed computation called shuffled check-in, which achieves strong privacy guarantees without requiring any further trust assumptions beyond a trusted shuffler. Unlike most existing work, shuffled check-in allows clients to make independent and random decisions to participate in the computation, removing the need for server-initiated subsampling. Leveraging differential privacy, we show that shuffled check-in achieves tight privacy guarantees through privacy amplification, with a novel analysis based on R{é}nyi differential privacy that improves privacy accounting over existing work. We also introduce a numerical approach to track the privacy of generic shuffling mechanisms, including Gaussian mechanism, which is the first evaluation of a generic mechanism under the distributed setting within the local/shuffle model in the literature. Empirical studies are also given to demonstrate the efficacy of the proposed approach.