Selective MPC: Distributed Computation of Differentially Private Key-Value Statistics
This work addresses the challenge of efficiently and accurately processing key-value data in privacy-sensitive distributed environments, representing a domain-specific advancement in secure computation.
The paper tackled the problem of computing statistics over key-value data in a distributed setting without a trusted central party, achieving results such as computing statistics over 10,000 keys in 20 seconds and scaling to 30 servers with results for a single key in under a second. It introduced selective multi-party computation to improve accuracy and efficiency compared to existing local differentially private and naive multi-party computation methods.
Key-value data is a naturally occurring data type that has not been thoroughly investigated in the local trust model. Existing local differentially private (LDP) solutions for computing statistics over key-value data suffer from the inherent accuracy limitations of each user adding their own noise. Multi-party computation (MPC) maintains better accuracy than LDP and similarly does not require a trusted central party. However, naively applying MPC to key-value data results in prohibitively expensive computation costs. In this work, we present selective multi-party computation, a novel approach to distributed computation that leverages DP leakage to efficiently and accurately compute statistics over key-value data. By providing each party with a view of a random subset of the data, we can capture subtractive noise. We prove that our protocol satisfies pure DP and is provably secure in the combined DP/MPC model. Our empirical evaluation demonstrates that we can compute statistics over 10,000 keys in 20 seconds and can scale up to 30 servers while obtaining results for a single key in under a second.