Benchmarking Secure Sampling Protocols for Differential Privacy

Differential privacy (DP) is widely employed to provide privacy protection for individuals by limiting information leakage from the aggregated data. Two well-known models of DP are the central model and the local model. The former requires a trustworthy server for data aggregation, while the latter requires individuals to add noise, significantly decreasing the utility of aggregated results. Recently, many studies have proposed to achieve DP with Secure Multi-party Computation (MPC) in distributed settings, namely, the distributed model, which has utility comparable to central model while, under specific security assumptions, preventing parties from obtaining others' information. One challenge of realizing DP in distributed model is efficiently sampling noise with MPC. Although many secure sampling methods have been proposed, they have different security assumptions and isolated theoretical analyses. There is a lack of experimental evaluations to measure and compare their performances. We fill this gap by benchmarking existing sampling protocols in MPC and performing comprehensive measurements of their efficiency. First, we present a taxonomy of the underlying techniques of these sampling protocols. Second, we extend widely used distributed noise generation protocols to be resilient against Byzantine attackers. Third, we implement discrete sampling protocols and align their security settings for a fair comparison. We then conduct an extensive evaluation to study their efficiency and utility. Our experiments show that (1) malicious protocols based on a technique called bitwise sampling are more efficient than other methods, and using an oblivious data structure can reduce the circuit size in high-security regimes, (2) the cost of realizing malicious security is high, under the assumption of semi-honest, using a method named distributed noise generation is much more efficient, and (3) the utility loss caused by sampling noise in MPC is small, which to a certain extent eliminates utility concerns when using the DDP protocol in practice. We also opensource our code The code of our benchmark is now available at https://github.com/yuchengxj/Secure-sampling-benchmark . CCS Concepts • Security and privacy → Privacy-preserving protocols.