We obtain a new protocol for binary counting in the $\varepsilon$-shuffle-DP model with error $O(1/\varepsilon)$ and expected communication $\tilde{ O}\left(\frac{ \log n}{ \varepsilon}\right)$ messages per user. Previous protocols incur either an error of $O(1/\varepsilon^{ 1.5})$ with $O_\varepsilon(\log{ n})$ messages per user (Ghazi et al., ITC 2020) or an error of $O(1/\varepsilon)$ with $O_\varepsilon(n^{ 2.5})$ messages per user (Cheu and Yan, TPDP 2022). Using the new protocol, we obtained improved $\varepsilon$-shuffle-DP protocols for real summation and histograms.
Categories: cs.DS cs.CR