A differentially private mechanism of optimal utility for a region of priors
| Autor: | Konstantinos Chatzikokolakis, Catuscia Palamidessi, Ehab ElSalamouny |
|---|---|
| Přispěvatelé: | Concurrency, Mobility and Transactions (COMETE), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Inria large scale initiative CAPPRIS, David A. Basin and John C. Mitchell, ANR-09-BLAN-0169,PANDA(2009), European Project: 295261,EC:FP7:PEOPLE,FP7-PEOPLE-2011-IRSES,MEALS(2011), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X) |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Mathematical optimization
Class (set theory) Computer science Optimal mechanism [SCCO.COMP]Cognitive science/Computer science [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] 0102 computer and information sciences 02 engineering and technology privacy 01 natural sciences Measure (mathematics) Information sensitivity 010201 computation theory & mathematics utility 020204 information systems Prior probability Convex polytope Information leakage 0202 electrical engineering electronic engineering information engineering Security Differential privacy Computer Science::Databases database |
| Zdroj: | 2nd Conference on Principles of Security and Trust (POST 2013) 2nd Conference on Principles of Security and Trust (POST 2013), Mar 2013, Rome, Italy. pp.41-62, ⟨10.1007/978-3-642-36830-1_3⟩ Lecture Notes in Computer Science ISBN: 9783642368295 POST |
| DOI: | 10.1007/978-3-642-36830-1_3⟩ |
| Popis: | International audience; The notion of differential privacy has emerged in the area of statistical databases as a measure of protection of the participants' sensitive information, which can be compromised by selected queries. Differential privacy is usually achieved by using mechanisms that add random noise to the query answer. Thus, privacy is obtained at the cost of reducing the accuracy, and therefore the "utility", of the answer. Since the utility depends on the user's side information, commonly modelled as a prior distribution, a natural goal is to design mechanisms that are optimal for every prior. However, it has been shown that such mechanisms do not exist for any query other than counting queries. Given the above negative result, in this paper we consider the problem of identifying a restricted class of priors for which an optimal mechanism does exist. Given an arbitrary query and a privacy parameter, we geometrically characterise a special region of priors as a convex polytope in the priors space. We then derive upper bounds for utility as well as for min-entropy leakage for the priors in this region. Finally we define what we call the "tight-constraints mechanism" and we discuss the conditions for its existence. This mechanism has the property of reaching the bounds for all the priors of the region, and thus it is optimal on the whole region. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|