Differentially private multi-party computation

We study the problem of multi-party computation under approximate (ϵ,δ) differential privacy. We assume an interactive setting with k parties, each possessing a private bit. Each party wants to compute a function defined on all the parties' bits. Differential privacy ensures that there remains uncertainty in any party's bit even when given the transcript of interactions and all the other parties' bits. This paper is a follow up to our work in [1], where we studied multi-party computation under (ϵ, 0) differential privacy. We generalize the results in [1] and prove that a simple non-interactive randomized response mechanism is optimal. Our optimality result holds for all privacy levels (all values of ϵ and δ), heterogenous privacy levels across parties, all types of functions to be computed, all types of cost metrics, and both average and worst-case (over the inputs) measures of accuracy.