Details

Autor(en) / Beteiligte

• Cheu, Albert
• Zhilyaev, Maxim

Titel

Differentially Private Histograms in the Shuffle Model from Fake Users

Ist Teil von

• 2022 IEEE Symposium on Security and Privacy (SP), 2022, p.440-457

Ort / Verlag

IEEE

Erscheinungsjahr

2022

Quelle

IEEE Xplore

Beschreibungen/Notizen

• 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.