Scalable and Differentially Private Distributed Aggregation in the Shuffled Model

Abstract

Federated learning promises to make machine learning feasible on distributed, private datasets by implementing gradient descent using secure aggregation methods. The idea is to compute a global weight update without revealing the contributions of individual users. Current practical protocols for secure aggregation work in an "honest but curious" setting where a curious adversary observing all communication to and from the server cannot learn any private information assuming the server is honest and follows the protocol. A more scalable and robust primitive for privacy-preserving protocols is shuffling of user data, so as to hide the origin of each data item. Highly scalable and secure protocols for shuffling, so-called mixnets, have been proposed as a primitive for privacy-preserving analytics in the Encode-Shuffle-Analyze framework by Bittau et al., which was later analytically studied by Erlingsson et al. and Cheu et al.. The recent papers by Cheu et al., and Balle et al. have given protocols for secure aggregation that achieve differential privacy guarantees in this "shuffled model". Their protocols come at a cost, though: Either the expected aggregation error or the amount of communication per user scales as a polynomial $n^{\Omega (1)}$ in the number of users $n$. In this paper we propose simple and more efficient protocol for aggregation in the shuffled model, where communication as well as error increases only polylogarithmically in $n$. Our new technique is a conceptual "invisibility cloak" that makes users' data almost indistinguishable from random noise while introducing zero distortion on the sum.

17 pages, 1 figure, 1 table, 2 algorithms

References in corpus (3)

• Deep Learning with Differential Privacy
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Differentially Private Summation with Multi-Message Shuffling

Cited by in corpus (18)

• Survey on Federated Learning Threats: concepts, taxonomy on attacks and defences, experimental study and challenges
• A Field Guide to Federated Optimization
• Privacy in Deep Learning: A Survey
• Federated Learning for Healthcare Informatics
• Private Summation in the Multi-Message Shuffle Model
• Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches
• Differentially Private Summation with Multi-Message Shuffling
• On the Power of Multiple Anonymous Messages
• Dynamic Fusion based Federated Learning for COVID-19 Detection
• Improved Summation from Shuffling
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Shuffle Private Stochastic Convex Optimization
• Differentially Private Multi-Armed Bandits in the Shuffle Model
• Connecting Robust Shuffle Privacy and Pan-Privacy
• Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning
• Improving Utility and Security of the Shuffler-based Differential Privacy
• Differential Privacy in the Shuffle Model: A Survey of Separations
• Privacy Enhancement via Dummy Points in the Shuffle Model