(2021) Continuous Release of Data Streams under both Centralized and Local Differential Privacy.
|
Text
dp_cont.pdf Download (1MB) | Preview |
Abstract
We study the problem of publishing a stream of real-valued data satisfying differential privacy (DP). One major challenge is that the maximal possible value in the stream can be quite large, leading to enormous DP noise and bad utility. To reduce the maximal value and noise, one way is to estimate a threshold so that values above it can be truncated. The intuition is that, in many scenarios, only a few values are large; thus truncation does not change the original data much. We develop such a method that finds a suitable threshold with DP. Given the threshold, we then propose an online hierarchical method and several post-processing techniques. Building on these ideas, we formalize the steps in a framework for the private publishing of streaming data. Our framework consists of three components: a threshold optimizer that privately estimates the threshold, a perturber that adds calibrated noise to the stream, and a smoother that improves the result using post-processing. Within our framework, we also design an algorithm satisfying the more stringent DP setting called local DP. Using four real-world datasets, we demonstrate that our mechanism outperforms the state-of-the-art by a factor of $6-10$ orders of magnitude in terms of utility (measured by the mean squared error of the typical scenario of answering a random range query).
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Conference: | CCS ACM Conference on Computer and Communications Security |
| Depositing User: | Zhikun Zhang |
| Date Deposited: | 07 Oct 2021 08:59 |
| Last Modified: | 07 Oct 2021 08:59 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3488 |
Actions
Actions (login required)
 |
View Item |