Accelerating simulations of bitvector-based LDP protocols via binomial modeling

Abstract

Local Differential Privacy (LDP) has recently emerged as a popular standard for privacy-preserving data collection, and bitvector-based LDP protocols such as RAPPOR and OUE are widely used in both academic and industrial applications. To evaluate LDP protocols and applications, researchers commonly rely on simulation-based experiments, where multiple users’ perturbations are simulated sequentially on one computer. While faithful to protocol definitions, this approach incurs substantial execution times, especially for large user populations and domains. To address this concern and enable fast simulations, in this paper, we propose a novel simulation methodology for bitvector-based LDP protocols. Our key insight is to model the collective effect of randomized perturbation using Binomial random variables, avoiding the need to simulate each user individually. We theoretically and empirically show that this strategy reduces computational complexity while producing unbiased estimations with identical variance to RAPPOR and OUE. Furthermore, we empirically show that our method reduces execution times from several minutes to less than a second, yielding multiple orders of magnitude improvement. Overall, our work offers a fast and scalable method for simulating bitvector-based LDP protocols, with direct applicability to existing works and simulation platforms.