Amplification by Shuffling without Shuffling
Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications …, 2023•dl.acm.org
Motivated by recent developments in the shuffle model of differential privacy, we propose a
new approximate shuffling functionality called Alternating Shuffle, and provide a protocol
implementing alternating shuffling in a single-server threat model where the adversary
observes all communication. Unlike previous shuffling protocols in this threat model, the per-
client communication of our protocol only grows sub-linearly in the number of clients.
Moreover, we study the concrete efficiency of our protocol and show it can improve per-client …
new approximate shuffling functionality called Alternating Shuffle, and provide a protocol
implementing alternating shuffling in a single-server threat model where the adversary
observes all communication. Unlike previous shuffling protocols in this threat model, the per-
client communication of our protocol only grows sub-linearly in the number of clients.
Moreover, we study the concrete efficiency of our protocol and show it can improve per-client …
Motivated by recent developments in the shuffle model of differential privacy, we propose a new approximate shuffling functionality called Alternating Shuffle, and provide a protocol implementing alternating shuffling in a single-server threat model where the adversary observes all communication. Unlike previous shuffling protocols in this threat model, the per-client communication of our protocol only grows sub-linearly in the number of clients. Moreover, we study the concrete efficiency of our protocol and show it can improve per-client communication by one or more orders of magnitude with respect to previous (approximate) shuffling protocols. We also show a differential privacy amplification result for alternating shuffling analogous to the one for uniform shuffling, and demonstrate that shuffling-based protocols for secure summation based a construction of Ishai et al. remain secure under the Alternating Shuffle. In the process we also develop a protocol for exact shuffling in single-server threat model with amortized logarithmic communication per-client which might be of independent interest.
ACM Digital Library
Showing the best result for this search. See all results