Loading...
Please wait, while we are loading the content...
Similar Documents
Personalised Differential Privacy Summary of POPL ’ 15 paper “ Differential Privacy : Now It ’ s Getting Personal ”
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ebadi, Hamid Sands, David |
| Copyright Year | 2015 |
| Abstract | Differential privacy provides a way to get useful information about sensitive data without revealing much about any one individual. It enjoys many nice compositionality properties not shared by other approaches to privacy, including, in particular, robustness against side-knowledge. Designing differentially private mechanisms from scratch can be a challenging task. One way to make it easier to construct new differential private mechanisms is to design a system which allows more complex mechanisms (programs) to be built from differentially private building blocks in principled way, so that the resulting programs are guaranteed to be differentially private by construction. This paper is about a new accounting principle for building differentially private programs. This approach is based on a simple generalisation of classic differential privacy which we call Personalised Differential Privacy (PDP). In PDP each individual has its own personal privacy level. We describe ProPer, a interactive system for implementing PDP which maintains a privacy budget for each individual. When a primitive query is made on data derived from individuals, the provenance of the involved records determines how the privacy budget of an individual is affected: the number of records derived from Alice determines the multiplier for the privacy decrease in Alice’s budget. This offers some advantages over previous systems, in particular its fine-grained character allows better utilisation of the privacy budget than mechanisms based purely on the concept of global sensitivity, and it applies naturally to the case of a live database where new individuals are added over time. We provide a formal model of the ProPer approach, prove that it provides personalised differential privacy, and describe a prototype implementation based on McSherry’s PINQ system. Differential privacy is a relatively new notion of privacy [1–3]. The theory shows that by adding the right amount of noise to statistical queries, one can get useful results at the same time as providing a quantifiable notion of privacy. Its definition does not involve a syntactic condition on the data itself, but rather it is a condition formed by comparing the results of a query on any database with or without any one individual: a query Q (a randomised function) is ε-differentially private if the difference in probability of any query outcome on a data-set only varies by a factor of e (approximately 1 + ε for small ε) whenever an individual is added or removed. Research on differential privacy has developed a variety of query mechanisms that provide differential privacy for a useful range of statistical problems. A few works have focussed more on 2 Personalised Differential Privacy composition principles that allow new differential private mechanisms to design a system which allows more complex mechanisms (programs) to be built from differentially private building blocks in principled way, so that the resulting programs are guaranteed to be differentially private by construction [6, 5, 7]. PINQ [6] is the starting point for the present work. PINQ-style Global Privacy Budget PINQ is an implementation of interactive differential privacy which ensures, at runtime, that queries adhere to a global privacy budget. Third-party client code freely decides how sensitive data sets should be processed and queried. The run-time system ensures that this does not break a specified privacy budget ε. PINQ builds on a collection of standard differentially private primitive queries, together with simple composition principles – mathematical properties enjoyed by the definition of differential privacy. One central principle is that multiple queries (e.g. with differential privacy ε1 and ε2 respectively) have an additive effect (ε1+ε2) on the overall differential privacy. Another central idea is to track sensitivity of functions to measure how much a change in the input might affect the value of the data. Together, these components allow the system to track how much to deduct from the global privacy budget on each invocation of a primitive query. Limitations of the Global Privacy Budget In a batch system where all computations are described up-front as a monolithic program, a global budget is reasonable. In an interactive system, however, there are several limitations to this style of accounting. Imagine a scenario involving a large data set of individuals – a cross-set of the population – containing various information about health and lifestyle. Let us suppose, further, that we aim for ε-differential privacy for some specified value of ε. On Monday the analyst selects all the people from the database who have a particular blood type, AB-negative, and constructs an algorithm which extracts information about them as part of medical research. Since just 0.6% of the population have this blood type, the proportion of the database involved in this study is relatively small, but the database is known to be big enough for it to be meaningful. Let us suppose that the cost of this analysis, according to the system, is ε1. Now on Tuesday the analyst gets a new task, to extract information about the lifestyle of smokers, towards an advertising campaign for nicotine gum. This is a significantly larger portion of the database, possibly overlapping Monday’s research group. The analyst has ε− ε1 left to spend. If ε1 is large, the analyst has blown the budget by analysing the small group, even though that study did not touch the data of the larger part of the population. PINQ offers a way around this problem by adding non-standard database primitives. Here we would partition the data into (AB−, not AB−) and perform the two studies in parallel, with cost being the maximum of the cost of the two studies. This leads to a batch-style reasoning and an unnatural programming style. But it also has another limitation. What if the database is live – we obtain new data over time, or if data is continually being added? A global budget forces us to be unnecessarily pessimistic about new as-yet unexploited data. Personalised Differential Privacy This paper addresses these issues by offering a simple generalisation of differential privacy called personalised differential privacy (PDP) [4] which permits each individual to have a personalised privacy budget. The definition supports generalised versions of the composition principles upon which systems like PINQ are based, and moreover enjoys a Personalised Differential Privacy 3 number of properties which allow for less wasteful compositional principles. For example, any query about the drinking habits of adults offers 0-differential privacy for Adrian, aged 13, as it does for any records of individuals which enter the database after the query has been made. Definition 1 (Personalised (Big Epsilon) Differential Privacy). We say that data sets A and B differ on record r, written A r ∼ B, if A can be obtained from B by adding the record r, or vice-versa. Let E be a function from records to non-negative real numbers. A randomized query Q provides E -differential privacy if for all records r, and all A r ∼ B, and any set of outputs S ⊆ range(Q), we have: Pr[Q(A) ∈ S] ≤ Pr[Q(B) ∈ S]× e (r) Personalised differential privacy allows each individual (record) to have its own personal privacy level. This may turn out to be a useful concept in its own right, but its main purpose in this work is as a generalisation that permits a more fine-grained accounting in the construction of classical differentially private mechanisms, and one which plays well with dynamic databases. The following proposition summarises the relation to “small-epsilon” differential privacy: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://tpdp.computing.dundee.ac.uk/abstracts/TPDP_2015_8.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
