Local Differential Privacy (LDP) protects user privacy from the data collector. LDP protocols have been increasingly deployed in the industry. A basic building block is frequency oracle (FO) protocols, which estimate frequencies of values. While several FO protocols have been proposed, the design goal does not lead to optimal results for answering many queries. In this paper, we show that adding post-processing steps to FO protocols by exploiting the knowledge that all individual frequencies should be non-negative and they sum up to one can lead to significantly better accuracy for a wide range of tasks, including frequencies of individual values, frequencies of the most frequent values, and frequencies of subsets of values. We consider 10 different methods that exploit this knowledge differently. We establish theoretical relationships between some of them and conducted extensive experimental evaluations to understand which methods should be used for different query tasks.

View More Papers

When Malware is Packin' Heat; Limits of Machine Learning...

Hojjat Aghakhani (University of California, Santa Barbara), Fabio Gritti (University of California, Santa Barbara), Francesco Mecca (Università degli Studi di...

Read More

OmegaLog: High-Fidelity Attack Investigation via Transparent Multi-layer Log Analysis

Wajih Ul Hassan (University of Illinois Urbana-Champaign), Mohammad A. Noureddine (University of Illinois Urbana-Champaign), Pubali Datta (University of Illinois Urbana-Champaign),...

Read More

Genotype Extraction and False Relative Attacks: Security Risks to...

Peter Ney (University of Washington), Luis Ceze (University of Washington), Tadayoshi Kohno (University of Washington)

Read More

Towards Plausible Graph Anonymization

Yang Zhang (CISPA Helmholtz Center for Information Security), Mathias Humbert (armasuisse Science and Technology), Bartlomiej Surma (CISPA Helmholtz Center for...

Read More