Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data
Olga Ohrimenko, Anthony I. Wirth, Hao Wu · 2022
Longitudinal data tracking under Local Differential Privacy (LDP) is a challenging task. Baseline solutions that repeatedly invoke a protocol designed for one-time computation lead to linear decay in the privacy or utility guarantee with respect to the number of computations. To avoid this, the recent approach of Erlingsson et al. (2020) exploits the potential sparsity of user data that changes only infrequently. Their protocol targets the fundamental problem of frequency estimation for longitudinal binary data, with l∞ error of O ((1 / ε) ⋅ (log d)3/2 ⋅ k ⋅ √ n ⋅ log (d / β)), where ε is the privacy budget, d is the number of time periods, k is the maximum number of changes of user data, and β is the failure probability. Notably, the error bound scales polylogarithmically with d, but linearly with k.