Differential privacy for relational algebra: improving the sensitivity bounds via constraint systems

Catuscia Palamidessi 1, 2 Marco Stronati 1, 2
2 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Differential privacy is a modern approach in privacy-preserving data analysis to control the amount of information that can be inferred about an individual by querying a database. The most common techniques are based on the introduction of probabilistic noise, often defined as a Laplacian parametric on the sensitivity of the query. In order to maximize the utility of the query, it is crucial to estimate the sensitivity as precisely as possible. In this paper we consider relational algebra, the classical language for queries in relational databases, and we propose a method for computing a bound on the sensitivity of queries in an intuitive and compositional way. We use constraint-based techniques to accumulate the information on the possible values for attributes provided by the various components of the query, thus making it possible to compute tight bounds on the sensitivity.
Type de document :
Communication dans un congrès
Wiklicky, Herbert and Massink, Mieke. QAPL - Tenth Workshop on Quantitative Aspects of Programming Languages, Apr 2012, Tallin, Estonia. Open Publishing Association, 85, pp.92-105, 2012, Electronic Proceedings in Theoretical Computer Science. <10.4204/EPTCS.85.7>


https://hal.inria.fr/hal-00760688
Contributeur : Marco Stronati <>
Soumis le : mercredi 5 décembre 2012 - 11:22:15
Dernière modification le : vendredi 10 juillet 2015 - 01:02:12

Fichier

paper.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Catuscia Palamidessi, Marco Stronati. Differential privacy for relational algebra: improving the sensitivity bounds via constraint systems. Wiklicky, Herbert and Massink, Mieke. QAPL - Tenth Workshop on Quantitative Aspects of Programming Languages, Apr 2012, Tallin, Estonia. Open Publishing Association, 85, pp.92-105, 2012, Electronic Proceedings in Theoretical Computer Science. <10.4204/EPTCS.85.7>. <hal-00760688>

Exporter

Partager

Métriques

Consultations de
la notice

181

Téléchargements du document

103