Private Frequency Estimation via Residue Number Systems

We present $\textsf{ModularSubsetSelection}$ (MSS), a new algorithm for locally differentially private (LDP) frequency estimation. Given a universe of size $k$ and $n$ users, our $\varepsilon$-LDP mechanism encodes each input via a Residue Number System (RNS) over $\ell$ pairwise-coprime moduli $m0, \ldots, m{\ell-1}$, and reports a randomly chosen index $j \in [\ell]$ along with the perturbed residue using the statistically optimal $\textsf{SubsetSelection}$ (SS) (Wang et al. 2016). This design reduces the user communication cost from $\Theta\bigl(\omega \log2(k/\omega)\bigr)$ bits required by standard SS (with $\omega \approx k/(e^\varepsilon+1)$) down to $\lceil \log2 \ell \rceil + \lceil \log2 mj \rceil$ bits, where $m_j < k$. Server-side decoding runs in $\Theta(n + r k \ell)$ time, where $r$ is the number of LSMR (Fong and Saunders 2011) iterations. In practice, with well-conditioned moduli (i.e., constant $r$ and $\ell = \Theta(\log k)$), this becomes $\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 $\textsf{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 $\textsf{RAPPOR}$ (Erlingsson, Pihur, and Korolova 2014) across realistic $(k, \varepsilon)$ 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 significantly reduces a Bayesian attacker’s reconstruction accuracy compared to SS.