Lightweight Two-Party Secure Sampling Protocol for Differential Privacy
Authors: Masanobu Kii (NTT Social Information Laboratories), Atsunori Ichikawa (NTT Social Information Laboratories), Takayuki Miura (NTT Social Information Laboratories)
Volume: 2025
Issue: 1
Pages: 23–36
DOI: https://doi.org/10.56553/popets-2025-0003
Abstract: Secure sampling is a secure multiparty computation protocol that allows a receiver to sample random numbers from a specified non-uniform distribution. It is a fundamental tool for privacy-preserving analysis since adding controlled noise is the most basic and frequently used method to achieve differential privacy. The well-known approaches to constructing a two-party secure sampling protocol are transforming uniform random values into non-uniform ones by computations (e.g., logarithm or binary circuits) or table-lookup. However, they require a large computational or communication cost to achieve a strong differential privacy guarantee. This work addresses this problem with our novel lightweight two-party secure sampling protocol. Our protocol consists of random table-lookup from a small table with the 1-out of-n oblivious transfer and only additions. Furthermore, we provide algorithms for making a table to achieve differential privacy. Our method can reduce the communication cost for (1.0, 2^(-40))-differential privacy from 183GB (naive construction) to 7.4MB.
Keywords: multiparty computation, differential privacy, random number generation, secure sampling, private sampling
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
