Private Frequency Estimation via Residue Number Systems

We present ModularSubsetSelection (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 Sub-setSelection (SS) (Wang et al. 2016) . This design reduces the user communication cost from Θ ω log 2 (k/ω) bits required by standard SS (with ω ≈ k/(e ε + 1)) down to ⌈log 2 ℓ⌉ + ⌈log 2 mj⌉ bits, where mj < k. Server-side decoding runs in Θ(n + rkℓ) time, where r is the number of LSMR (Fong and Saunders 2011) 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 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 RAPPOR (Erlingsson, Pihur, and Korolova 2014) 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 reconstructionattack success rate among all evaluated LDP protocols.