Lower bounds in differential privacy

Abstract

This is a paper about private data analysis, in which a trusted curator holding a confidential database responds to real vector-valued queries. A common approach to ensuring privacy for the database elements is to add appropriately generated random noise to the answers, releasing only these {\em noisy} responses. In this paper, we investigate various lower bounds on the noise required to maintain different kind of privacy guarantees.

Corrected some minor errors and typos. To appear in Theory of Cryptography Conference (TCC) 2012

Cited by in corpus (5)

• Beating Randomized Response on Incoherent Matrices
• Differentially Private Online Learning
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• A Learning Theory Approach to Non-Interactive Database Privacy
• On the Relation Between Identifiability, Differential Privacy and Mutual-Information Privacy