Private Frequency Estimation Via Residue Number Systems

2025/11/14 by Héber H. Arcolezi, Arcolezi, Héber H.
Computer Science · #Cryptography and Residue Arithmetic #Cryptography and Data Security #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.2511.11569

Abstract

We present \textsfModularSubsetSelection (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 m₀, …, 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 Θ(ωlog₂(k/ω)) bits required by standard SS (with ω≈ k/(e^ε+1)) down to \lceil log₂ ℓ \rceil + \lceil log₂ m_j \rceil bits, where m_j < k. Server-side decoding runs in Θ(n + r k ℓ) 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 \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, ε) 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.

Citations

• Revisiting Locally Differentially Private Protocols: Towards Better Trade-offs in Privacy, Utility, and Attack Resistance
• Private federated discovery of out-of-vocabulary words for Gboard
• Bounding Training Data Reconstruction in DP-SGD
• Private Frequency Estimation via Projective Geometry
• Inverting Gradients -- How easy is it to break privacy in federated learning?
• Collecting Telemetry Data Privately
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Discrete Distribution Estimation under Local Privacy
• Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias

Related

• Private Frequency Estimation via Projective Geometry
• Local Differentially Private Frequency Estimation based on Learned Sketches
• When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery
• Frequency Estimation in the Shuffle Model with Almost a Single Message
• Optimal Compression of Locally Differentially Private Mechanisms