An increasingly popular method for computing aggregate statistics while
preserving users’ privacy is local differential privacy (LDP). Under this
model, users perturb their data before sending it to an untrusted central party
to be processed. Key value data is a naturally occurring data type that has not
been thoroughly investigated in the local trust model. Existing 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)
is a common alternative to LDP that removes the requirement for a trusted
central party while maintaining accuracy; 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. We show 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.

By admin