Private Frequency Estimation Via Residue Number Systems

We present $\mathsf{\text{ModularSubsetSelection}}$ (MSS), a new algorithm for locally differentially private (LDP) frequency estimation. Given a universe of size $k$ and $n$ users, our $\epsilon$-LDP mechanism encodes each input via a Residue Number System (RNS) over $\mathrm{\ell }$ pairwise-coprime moduli $m_0,\dots ,m_{\mathrm{\ell }-1}$, and reports a randomly chosen index $j\in [\mathrm{\ell }]$ along with the perturbed residue using the statistically optimal $\mathsf{\text{SubsetSelection}}$ (SS) (Wang et al. 2016). This design reduces the user communication cost from $\mathrm{\Theta }(\omega {\log }_2(k\mathrm{/}\omega ))$ bits required by standard SS (with $\omega \approx k\mathrm{/}(e^{\epsilon }+1)$) down to $\lceil {\log }_2\mathrm{\ell }\rceil +\lceil {\log }_2{m}_j\rceil$ bits, where $m_j<k$. Server-side decoding runs in $\mathrm{\Theta }(n+rk\mathrm{\ell })$ time, where $r$ is the number of LSMR (Fong and Saunders 2011) iterations. In practice, with well-conditioned moduli ($\mathit{\text{i.e.}}$, constant $r$ and $\mathrm{\ell }=\mathrm{\Theta }(\log k)$), this becomes $\mathrm{\Theta }(n+k\log k)$. We prove that MSS achieves worst-case MSE within a constant factor of state-of-the-art protocols such as SS and $\mathsf{\text{ProjectiveGeometryResponse}}$ (PGR) (Feldman et al. 2022) while avoiding the algebraic prerequisites and dynamic-programming decoder required by PGR. Empirically, MSS matches the estimation accuracy of SS, PGR, and $\mathsf{\text{RAPPOR}}$ (Erlingsson, Pihur, and Korolova 2014) across realistic $(k,\epsilon )$ settings, while offering faster decoding than PGR and shorter user messages than SS. Lastly, by sampling from multiple moduli and reporting only a single perturbed residue, MSS achieves the lowest reconstruction-attack success rate among all evaluated LDP protocols.