all InfoSec news
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
April 17, 2024, 4:11 a.m. | Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Samson Zhou, Kunal Talwar
cs.CR updates on arXiv.org arxiv.org
Abstract: We study the problem of private vector mean estimation in the shuffle model of 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 error requires each user to send $\Omega(\min(n\varepsilon^2,d)/\log(n))$ messages, demonstrating the optimality of our message complexity up to logarithmic factors. Additionally, we study the single-message …
arxiv cs.cr cs.ds cs.it cs.lg error math.it message messages privacy private problem protocol shuffle study
More from arxiv.org / cs.CR updates on arXiv.org
Jobs in InfoSec / Cybersecurity
Senior Security Engineer - Detection and Response
@ Fastly, Inc. | US (Remote)
Application Security Engineer
@ Solidigm | Zapopan, Mexico
Defensive Cyber Operations Engineer-Mid
@ ISYS Technologies | Aurora, CO, United States
Manager, Information Security GRC
@ OneTrust | Atlanta, Georgia
Senior Information Security Analyst | IAM
@ EBANX | Curitiba or São Paulo
Senior Information Security Engineer, Cloud Vulnerability Research
@ Google | New York City, USA; New York, USA