Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption - Rastogi, Vibhor; Nath, Suman (Microsoft Research, 2009)
We propose the first differentially private aggregation algorithm for distributed time-series data that offers good practical utility without any trusted server. This addresses two important challenges in participatory data-mining applications where (i) individual users wish to publish temporally correlated time-series data (such as location traces, web history, personal health data), and (ii) an untrusted third-party aggregator wishes to run aggregate queries on the data. To ensure differential privacy for time-series data despite the presence of temporal correlation, we propose the Fourier Perturbation Algorithm (FPA). Standard differential privacy techniques perform poorly for time-series data. To answer n queries, such techniques can result in a noise of Theta(n) to each query answer, making the answers practically useless if n is large. Our FPA algorithm perturbs the Discrete Fourier Transform of the query answers. For answering n queries, FPA improves the expected error from Theta(n) to roughly Theta(k) where k is the number of Fourier coefficients that can (approximately) reconstruct all the n query answers. Our experiments show that k << n for many real-life data-sets resulting in a huge error-improvement for FPA. To deal with the absence of a trusted central server, we propose the Distributed Laplace Perturbation Algorithm (DLPA) to add noise in a distributed way in order to guarantee differential privacy. To the best of our knowledge, DLPA is the first distributed differentially private algorithm that can scale with a large number of users: DLPA outperforms the only other distributed solution for differential privacy proposed so far, by reducing the computational load per user from O(U) to O(1) where U is the number of users.