Private Frequency Estimation via Residue Number Systems

We present Modular Subset Selection (MSS), a new algorithm for locally differentially private (LDP) frequency estimation. Given a universe of size k and n users, our ε-LDP mechanism encodes each input via a Residue Number System (RNS) over ℓ pairwise-coprime moduli m0, ..., m_{ℓ−1}, and reports a randomly chosen index j ∊ [ℓ] along with the perturbed residue using the statistically optimal Subset Selection (SS) mechanism. This design reduces the user communication cost from Θ(ω log₂(k/ω)) bits required by standard SS (with ω ≈ k/(e^ε+1)) down to ⌈ log₂ ℓ ⌉ + ⌈ log₂ m_j ⌉ bits, where m_j < k. Server-side decoding runs in Θ(n + r k ℓ) time, where r is the number of LSMR iterations. In practice, with well-conditioned moduli (i.e., constant r and ℓ = Θ(log k)), this becomes Θ(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 Projective Geometry Response (PGR), while avoiding the algebraic prerequisites and dynamic-programming decoder required by PGR. Empirically, MSS matches the estimation accuracy of SS, PGR, and RAPPOR across realistic (k, ε) 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.