Differentially Private Resource Allocation

Summary

Recent studies have shown that systems with limited resources like Metadata-private Messenger (MPM) suffer from side-channel attacks under resource allocation (RA). In the case of MPM, which is designed to keep the identities and activities of both callers and callees private from network adversaries, an attacker can compromise a victim’s friends and keep calling the victim to infer whether the victim is busy, which breaks the privacy guarantee of MPM. In this work, we systematically study how to protect the privacy of RA against the aforementioned attacks with differential privacy (DP). Though DP has been tested by Angel et al. (IEEE S&P 2020) in protecting RA, which lets the allocator add dummy requests following a biased Laplace distribution to hide the existence of the victim and then assign resources randomly, we identify that this approach does not leverage the uncertainty from the attacker’s view, thus leading to a loose bound of DP. As a result, more than 40% of the resources are wasted to satisfy DP. To make the DP solutions more practical, we precisely model the RA process from the attacker’s view and present a thorough study of the noisy allocation mechanisms by considering different distributions, scales, and biases of noise. We identify four new mechanisms and prove that they all follow ϵ -DP (Angel et al. follow (ϵ, δ)-DP). Through theoretical and empirical analysis, we found these approaches can outperform Angel et al. by a large margin in privacy-utility tradeoff.