Private Frequency Estimation Via Residue Number Systems

We present textsfModularSubsetSelection (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 ℓ pairwise-coprime moduli m0, ldots, mℓ-1, and reports a randomly chosen index j ∈ [ℓ] along with the perturbed residue using the statistically optimal textsfSubsetSelection (SS) (Wang et al. 2016). This design reduces the user communication cost from Thetabigl(ω log2(k/ω)bigr) bits required by standard SS (with ω ≈ k/(e^varepsilon+1)) down to lceil log2 ℓ rceil + lceil log2 mj rceil bits, where mj < k. Server-side decoding runs in Theta(n + r k ℓ) time, where r is the number of LSMR (Fong and Saunders 2011) iterations. In practice, with well-conditioned moduli (textiti.e., constant r and ℓ = 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 textsfProjectiveGeometryResponse (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 textsfRAPPOR (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 achieves the lowest reconstruction-attack success rate among all evaluated LDP protocols.