Name
Abstract | ||
|---|---|---|
There has been much recent work in the shuffle model of differential privacy, particularly for approximate d-bin histograms. While these protocols achieve low error, the number of messages sent by each user—the message complexity—has so far scaled with d or the privacy parameters. The message complexity is an informative predictor of a shuffle protocol’s resource consumption. We present a protocol whose message complexity is two when there are sufficiently many users. The protocol essentially pairs each row in the dataset with a fake row and performs a simple randomization on all rows. We show that the error introduced by the protocol is small, using rigorous analysis as well as experiments on real-world data. We also prove that corrupt users have a relatively low impact on our protocol’s estimates. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/SP46214.2022.9833614 | 2022 IEEE Symposium on Security and Privacy (SP) |
Keywords | DocType | ISSN |
Differential-Privacy,Shuffle-Model,Histograms,Attacks,Theory | Conference | 1081-6011 |
ISBN | Citations | PageRank |
978-1-6654-1317-6 | 0 | 0.34 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Albert Cheu | 1 | 2 | 3.08 |
| Maxim Zhilyaev | 2 | 0 | 0.34 |