Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption

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.

paper.pdf
PDF file

Publisher  Microsoft Research
© 2009 Microsoft Corporation. All rights reserved.

Details

TypeTechReport
NumberMSR-TR-2009-186
> Publications > Differentially Private Aggregation of Distributed Time-Series with Transformation and Encryption