Paper 2011/005

Is privacy compatible with truthfulness?

David Xiao

Abstract

In the area of privacy-preserving data mining, a differentially private mechanism intuitively encourages people to share their data because they are at little risk of revealing their own information. However, we argue that this interpretation is incomplete because external incentives are necessary for people to participate in databases, and so data release mechanisms should not only be differentially private but also compatible with incentives, otherwise the data collected may be false. We apply the notion of \emph{truthfulness} from game theory to this problem. In certain settings, it turns out that existing differentially private mechanisms do not encourage participants to report their information truthfully. On the positive side, we exhibit a transformation that takes truthful mechanisms and transforms them into differentially private mechanisms that remain truthful. Our transformation applies to games where the type space is small and the goal is to optimize an insensitive quantity such as social welfare. Our transformation incurs only a small additive loss in optimality, and it is computationally efficient. Combined with the VCG mechanism, our transformation implies that there exists a differentially private, truthful, and approximately efficient mechanism for any social welfare game with small type space. We also study a model where an explicit numerical cost is assigned to the information leaked by a mechanism. We show that in this case, even differential privacy may not be strong enough of a notion to motivate people to participate truthfully. We show that mechanisms that release a perturbed histogram of the database may reveal too much information. We also show that, in general, any mechanism that outputs a synopsis that resembles the original database (such as the mechanism of Blum et al. (STOC '08)) may reveal too much information.

Note: Generalized transformation, small typo fixes.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ITCS 2013
Keywords
privacygame theoryincentives
Contact author(s)
david xiao @ gmail com
History
2012-11-23: last of 4 revisions
2011-01-05: received
See all versions
Short URL
https://ia.cr/2011/005
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/005,
      author = {David Xiao},
      title = {Is privacy compatible with truthfulness?},
      howpublished = {Cryptology ePrint Archive, Paper 2011/005},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/005}},
      url = {https://eprint.iacr.org/2011/005}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.