Secure Summation via Subset Sums: A New Primitive for Privacy-Preserving Distributed Machine Learning
For population studies or for the training of complex machine learning models, it is often required to gather data from different actors. In these applications, summation is an important primitive: for computing means, counts or mini-batch gradients. In many cases, the data is privacy-sensitive and therefore cannot be collected on a central server. Hence the summation needs to be performed in a distributed and privacy-preserving way. Existing solutions for distributed summation with computational privacy guarantees make trust or connection assumptions - e.g., the existence of a trusted server or peer-to-peer connections between clients - that might not be fulfilled in real world settings. Motivated by these challenges, we propose Secure Summation via Subset Sums (S5), a method for distributed summation that works in the presence of a malicious server and only two honest clients, and without the need for peer-to-peer connections between clients. S5 adds zero-sum noise to clients' messages and shuffles them before sending them to the aggregating server. Our main contribution is a proof that this scheme yields a computational privacy guarantee based on the multidimensional subset sum problem. Our analysis of this problem may be of independent interest for other privacy and cryptography applications.
Code (1)
Tasks
BIG-bench Machine LearningPrivacy PreservingSimilar Papers 제목 키워드 기반
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation
We consider training models on private data that are distributed across user devices. To ensure privacy, we add on-device noise and use secure aggregation so that only the noisy sum is revealed to the server. We present …
Federated LearningQuantizationDifferential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation
Computing the noisy sum of real-valued vectors is an important primitive in differentially private learning and statistics. In private federated learning applications, these vectors are held by client devices, leading to…
Federated LearningCombinatorial privacy: Packing splinters in polytopes at scale for private bit sums via SecureHull
We present a scheme to obtain counts of 0’s and 1’s at a server based on private bit streams hosted by multiple clients. The goal is to obtain this solution at the server while maintaining privacy of client data. The bit…
Differentially Private Summation with Multi-Message Shuffling
In recent work, Cheu et al. (Eurocrypt 2019) proposed a protocol for $n$-party real summation in the shuffle model of differential privacy with $O_{\epsilon, \delta}(1)$ error and $\Theta(\epsilon\sqrt{n})$ one-bit messa…
Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe
Modern federated and streaming learning systems often release intermediate models, so privacy must hold for the full trajectory under adaptive interaction. Motivated by participation privacy, we study single-edit neighbo…
Continual Learning