Paper 2015/701

Differentially private instance-based noise mechanisms in practice

Sébastien Canard, Baptiste Olivier, and Tony Quertier

Abstract

Differential privacy is a widely used privacy model today, whose privacy guarantees are obtained to the price of a random perturbation of the result. In some situations, basic differentially private mechanisms may add too much noise to reach a reasonable level of privacy. To answer this shortcoming, several works have provided more technically involved mechanisms, using a new paradigm of differentially private mechanisms called instance-based noise mechanisms. In this paper, we exhibit for the first time theoretical conditions for an instance-based noise mechanism to be (epsilon, delta) differentially private. We exploit the simplicity of these conditions to design a novel instance-based noise differentially private mechanism. Conducting experimental evaluations, we show that our mechanism compares favorably to existing instance-based noise mechanisms, either regarding time complexity or accuracy of the sanitized result. By contrast with some prior works, our algorithms do not involve the computation of all local sensitivities, a computational task which was proved to be NP hard in some cases, namely for statistic queries on graphs. Our framework is as general as possible and can be used to answer any query, which is in contrast with recent designs of instance-based noise mechanisms where only graph statistics queries are considered.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
AnonymityDifferential Privacy
Contact author(s)
tony quertier @ gmail com
History
2017-06-01: revised
2015-07-14: received
See all versions
Short URL
https://ia.cr/2015/701
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/701,
      author = {Sébastien Canard and Baptiste Olivier and Tony Quertier},
      title = {Differentially private instance-based noise mechanisms in practice},
      howpublished = {Cryptology ePrint Archive, Paper 2015/701},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/701}},
      url = {https://eprint.iacr.org/2015/701}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.