Abstract
We study the problem of private vector mean estimation in the shuffle modelof privacy where $n$ users each have a unit vector $v^{(i)} \in\mathbb{R}^d$.We propose a new multi-message protocol that achieves the optimal error using$\tilde{\mathcal{O}}\left(\min(n\varepsilon^2,d)\right)$ messages per user.Moreover, we show that any (unbiased) protocol that achieves optimal errorrequires each user to send $\Omega(\min(n\varepsilon^2,d)/\log(n))$ messages,demonstrating the optimality of our message complexity up to logarithmicfactors. Additionally, we study the single-message setting and design aprotocol that achieves mean squared error$\mathcal{O}(dn^{d/(d+2)}\varepsilon^{-4/(d+2)})$. Moreover, we show that anysingle-message protocol must incur mean squared error $\Omega(dn^{d/(d+2)})$,showing that our protocol is optimal in the standard setting where $\varepsilon= \Theta(1)$. Finally, we study robustness to malicious users and show thatmalicious users can incur large additive error with a single shuffler.