Fredrik Meisingseth, Christian Rechberger, Fabian Schmid
ePrint Report
There is rising interest in combining Differential Privacy (DP) and Secure Multiparty Computation (MPC) techniques to protect distributed database query evaluations from both adversaries taking part in the computation and those observing the outputs. This requires implementing both the query evaluation and noise generation parts of a DP mechanism directly in MPC. While query evaluation can be done using existing highly optimized MPC techniques for secure function evaluation, efficiently generating the correct noise distribution is a more novel challenge.
Due to the inherent nonlinearity of sampling algorithms for common noise distributions, this challenge is quite non-trivial, as is evident from the substantial number of works proposing protocols for multiparty noise sampling. In this work, we propose a new approach for joint noise sampling that leverages recent advances in multiparty lookup table (LUT) evaluations. The construction we propose is largely agnostic to the target noise distribution and builds on obliviously evaluating the LUT at an index drawn from a distribution that can be very cheaply generated in MPC, thus translating this cheap distribution into the much more complicated target noise distribution. In our instantiation, the index is a concatenation of cheaply biased bits, and we approximate a discrete Laplace distribution to a negligible statistical distance. We demonstrate the concrete efficiency of the construction by implementing it using 3-party replicated secret sharing (RSS) in the honest-majority setting with both semi-honest and malicious security. In particular, we achieve sub-kilobyte communication complexity, being an improvement over the state-of-the-art by several orders of magnitude and a computation time of a few milliseconds. Samples of a discrete Laplace distribution are generated with (amortized over $1000$ samples) 362 bytes of communication and under a millisecond computation time per party in the semi-honest setting. Using recent results for batched multiplication checking, we have an overhead for malicious security that, per sample, amortizes to below a byte of communication and 10 ms of runtime.
Finally, our open-source implementation extends the online-to-total communication trade-off for MAESTRO-style lookup tables which might be of independent interest.
