Samplable Anonymous Aggregation for Private Federated Data Analysis
This work addresses the gap between locally and centrally differentially private algorithms for federated learning, offering a solution that enhances utility without requiring strong trust assumptions, which is significant for privacy-sensitive applications in distributed data analysis.
The paper tackles the problem of designing scalable protocols for private federated data analysis by proposing a new primitive called Samplable Anonymous Aggregation, which computes aggregates over random subsets of inputs and leads to better privacy-utility trade-offs for fundamental tasks, as demonstrated through improved guarantees compared to prior methods.
We revisit the problem of designing scalable protocols for private statistics and private federated learning when each device holds its private data. Locally differentially private algorithms require little trust but are (provably) limited in their utility. Centrally differentially private algorithms can allow significantly better utility but require a trusted curator. This gap has led to significant interest in the design and implementation of simple cryptographic primitives, that can allow central-like utility guarantees without having to trust a central server. Our first contribution is to propose a new primitive that allows for efficient implementation of several commonly used algorithms, and allows for privacy accounting that is close to that in the central setting without requiring the strong trust assumptions it entails. {\em Shuffling} and {\em aggregation} primitives that have been proposed in earlier works enable this for some algorithms, but have significant limitations as primitives. We propose a {\em Samplable Anonymous Aggregation} primitive, which computes an aggregate over a random subset of the inputs and show that it leads to better privacy-utility trade-offs for various fundamental tasks. Secondly, we propose a system architecture that implements this primitive and perform a security analysis of the proposed system. Our design combines additive secret-sharing with anonymization and authentication infrastructures.