Scaling Two-Party Differentially Private Selection

Abstract

We consider the problem of differentially private (DP) selection in the two-party setting. This problem can be solved with excellent utility guarantee in the central setting, but the distributed case is much less studied. Existing solutions use secure multi-party computation (MPC) techniques to simulate computation in the central model, which are not sufficiently scalable to large candidate sets. This work provides a new protocol for two-party DP selection that achieves sublinear runtime in the MPC phase. Our design lets each party locally trim the candidate set before participating in an MPC protocol. Based on this heuristic, we provide two variations, one of which reveals each party’s trimmed candidate set and the other does not. We evaluate our method on public datasets based on review counts and location check-ins. The results demonstrate that the variant hiding the trimmed candidate sets outperforms the other variant in both utility and efficiency. Furthermore, our solution is able to offer competitive utility to the traditional solution at a significantly lower computation cost in lower privacy regimes.