2025/02/05 by Anders Aamand, Aamand, Anders, Fabrizio Boninsegna +7 · 1 voice · 1 citation
#cs.CR
paper · pdf · doi:10.48550/arxiv.2502.02990
Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two adaptive algorithms for estimating one quantile (e.g.~the median) when each user holds a single data point lying in a domain [B] that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). In the adaptive setting we present an ε-LDP algorithm which can estimate any quantile within error α only requiring O((log B)/(ε2α2)) users, and an (ε,δ)-shuffle DP algorithm requiring only \widetildeO(((1)/(ε2)+(1)/(α2))log B) users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in B. We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-ε regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.