- A nearly tight lower bound of $\tilde{\Omega}( \min(n^{1/4}, \sqrt{B}))$ on the error in the single-message shuffled model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are essentially optimal for single-message protocols. - A nearly tight lower bound of $\Omega\left(\frac{\log{B}}{\log\log{B}}\right)$ on the sample complexity with constant relative error in the single-message shuffled model. This improves on the lower bound of $\Omega(\log^{1/17} B)$ obtained by Cheu et al. (Eurocrypt 2019).
- Protocols in the multi-message shuffled model with $\mathrm{poly}(\log{B}, \log{n})$ bits of communication per user and $\mathrm{poly}\log{B}$ error, which provide an exponential improvement on the error compared to what is possible with single-message algorithms. They also imply protocols with similar error and communication guarantees for several well-studied problems such as heavy hitters, d-dimensional range counting, and M-estimation of the median and quantiles.
For the related selection problem, we also show a nearly tight sample complexity lower bound of $\Omega(B)$ in the single-message shuffled model. This improves on the $\Omega(B^{1/17})$ lower bound obtained by Cheu et al. (Eurocrypt 2019), and when combined with their $\tilde{O}(\sqrt{B})$-error multi-message algorithm, implies the first separation between single-message and multi-message protocols for this problem.
Category / Keywords: foundations / Differential Privacy, Shuffled Model, Anonymous Channel, Frequency Estimation, Range Counting Date: received 1 Dec 2019 Contact author: badihghazi at gmail com,badihghazi@google com,nzg@mit edu,ravi k53@gmail com,pagh@itu dk,ameyav@google com Available format(s): PDF | BibTeX Citation Version: 20191201:210301 (All versions of this report) Short URL: ia.cr/2019/1382