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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Accelerating Simulations of Bitvector-Based LDP Protocols via Binomial Modeling

  • Yusuf Cemal Karatas,
  • M. Emre Gursoy

摘要

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.