With a dataset, conclusions are formed through a series of observations in the form of queries. If the query function is sensitive to the presence or absence of a single record, an adversary can perform linkage attacks to identify individuals in an otherwise anonymized dataset. Recent advances in the field of differential privacy (DP) provides privatizing mechanisms with provable guarantees. In this project, we implement two functions that implement various DP mechanisms for potential inclusion in the Wolfram Function Repository. The first function equips a dataset with a DP mechanism, which is then deployed to the cloud as an APIFunction, with privacy parameters that are set at the discretion of the data curator. The second function is used by data analysts to perform basic queries. By introducing a privacy budget, excessive queries can be discouraged, hence reducing the chance of executing linkage attacks on the dataset.
Why privacy is important
Why privacy is important
Many existing datasets are, in one way or another, gathered from individuals for research in hopes of identifying overall statistics or patterns that will generalize to other individuals not included in the dataset. Unfortunately, naive data anonymization that removes individual-specific fields like names and addresses are insufficient to protect against linkage attacks exploiting small differences between publicly available datasets. In 2008, Narayan and Shmatikov demonstrated a linkage attack against anonymized data provided by Netflix using records from the Internet Movie Database (IMDb) [1]. These privacy breaches can discourage individuals to participate in studies that rely heavily on surveys or other data-gathering studies.
Randomized response
Randomized response
An old technique in the social sciences called randomized response is used for gathering binary (Yes/No) responses to satisfying a certain predicate , which is possibly embarrassing or incriminating.
In[]:=
p=0.5;trueResponse=RandomChoice[{True,False}];randomizedResponse=If[RandomReal[]<p,trueResponse,RandomChoice[{True,False}]]
Out[]=
True
Setting the parameter p achieves varying levels of privacy, with p = 0 as the least private mechanism and p=1 as the most private mechanism.
In[]:=
Table[{p,BarChart[{{p/2,1-p/2},{1-p/2,p/2}},ChartLabels{True,False},ChartLegends{"true response = False","true response = True"},PlotRange{Automatic,{-0.2,1}}]},{p,{0,0.5,1}}]//TableForm
Out[]//TableForm=
0 | |||
0.5 | |||
1 |
The framework implemented in this project operates similarly in that it uses randomized mechanisms to provide answers to a family of queries and guarantee a certain level of privacy.
Defining differential privacy
Defining differential privacy
In essence, any particular entry is anonymized whenever any statistic about the entire dataset is about the same regardless of the presence or absence of that entry. Let 1 and 2 be two datasets differing in the absence/presence of exactly one element. Informally, a randomized mechanism ℳ provides differential privacy if the outputs due to 1 and 2 are approximately equally likely.
The following definition, due to Dwork et al [2], introduces privacy parameters ϵ and δ that specifies the extent that the output due to neighboring databases are approximately equally likely. We say that a mechanism is (ϵ, δ) differentially private if Prob[ℳ(1) ∈ ] ≤ exp(ϵ) Prob[ℳ(1) ∈ ] + δ for all possible queries on neighboring datasets 1 and 2. A mechanism is more differentially-private if the privacy parameters are both close to zero.
The following definition, due to Dwork et al [2], introduces privacy parameters ϵ and δ that specifies the extent that the output due to neighboring databases are approximately equally likely. We say that a mechanism is (ϵ, δ) differentially private if Prob[ℳ(1) ∈ ] ≤ exp(ϵ) Prob[ℳ(1) ∈ ] + δ for all possible queries on neighboring datasets 1 and 2. A mechanism is more differentially-private if the privacy parameters are both close to zero.
The following example shows that queries can be sensitive to small changes in the dataset.
In[]:=
dataset=Dataset[<|"Name"#[[1]],"Grade"#[[2]]|>&/@Transpose[{{"Alice","Bob","Charlie","Diane","Eve"},{53,79,81,87,58}}]];datasetWithoutCharlie=dataset[Select[#Name!="Charlie"&]];query=Length@Select[#,#["Grade"]≥70&]&(*numberofstudentswhopassed*);<|datasetquery[dataset],datasetWithoutCharliequery[datasetWithoutCharlie]|>
Out[]=
Protecting data from sensitive queries
Protecting data from sensitive queries
Not all queries are created equal. In the differential privacy framework, data curators can anonymize the result of a query depending on its sensitivity to small changes in the dataset. Less sensitive queries will be answered more truthfully than more sensitive queries. As a simple example, consider the query, “What is the average number of eyes of people in the dataset?” If we are sure that every entry in the dataset has two eyes, then we can safely answer the query truthfully because the result will remain unchanged even if we remove any single entry in the dataset.
Most queries, however, produce different results when small, “differential” changes are introduced to a dataset. For such queries, a data collector needs to be careful not to provide answers that can be tied to a specific individual. Such “anonymizing” mechanisms need to be put in place especially when certain individuals possess a rare set of conditions, as in medical records.
Most queries, however, produce different results when small, “differential” changes are introduced to a dataset. For such queries, a data collector needs to be careful not to provide answers that can be tied to a specific individual. Such “anonymizing” mechanisms need to be put in place especially when certain individuals possess a rare set of conditions, as in medical records.
The illustration below shows the behavior of the Laplace mechanism for a query with sensitivity = 1.0
In[]:=
{Table[Plot[{PDF[LaplaceDistribution[2,1/ϵ],x],PDF[LaplaceDistribution[3.,1/ϵ],x]},{x,0,5},FillingAxis,PlotRange{{0,5},{0,ϵ/2}},ExclusionsNone],{ϵ,{10.,1.,0.1}}],Table[Plot[Abs@Log[PDF[LaplaceDistribution[2,1/ϵ],x]/PDF[LaplaceDistribution[3.,1/ϵ],x]],{x,0,5},PlotRange{Automatic,{0,1.1ϵ}}],{ϵ,{10.,1.,0.1}}]}//TableForm[#,TableHeadings{{"PDFs","log-likelihood ratio"},{"ϵ=10. (least secure)","ϵ=1.","ϵ=0.1 (most secure)"}}]&
Out[]//TableForm=
ϵ=10. (least secure) | ϵ=1. | ϵ=0.1 (most secure) | |
PDFs | |||
log-likelihood ratio |
In general, the sensitivity depends on the query itself. Consider a simple example:
In[]:=
data=Dataset[<|"Name"#[[1]],"Grade"#[[2]],"OS"#[[3]],"HoursOfSleep"#[[4]]|>&/@Transpose[{{"Alice","Bob","Charlie","Debbie","Eve"},{53,79,81,87,58},{"Windows","Linux","Linux","Mac","Linux"},{10.,9.,3.,8.,2.}}]]
Out[]=
The following query asks for the average grade of those who use Linux
In[]:=
query=Function[data,Mean[data[Select[#OS"Linux"&],"Grade"]]];query[data]//N
Out[]=
72.6667
Single-entry removals strongly affects the query result:
In[]:=
Dataset@Table[<|"Removed entry"name,"Resulting Dataset"data[Select[#Name≠name&]],"Query Result"query[data[Select[#Name≠name&]]]|>,{name,{"Alice","Bob","Charlie","Debbie","Eve"}}]
Out[]=
The sensitivity is calculated as the maximum deviation from the original value: 80 - 72.667 = 7.33
Providing isolation between raw data and data analysts
Providing isolation between raw data and data analysts
To ensure privacy, data analysts must not be able to access the data in its raw form. In this project, we used a CloudObject to deploy an APIFunction. For the sake of illustration, we have the following CloudObject implementation for the randomized Yes/No response
Data curator creates a CloudObject to be shared to a data analyst
Data analyst uses the CloudObject to perform a query
Without restrictions, the true value can be inferred from repeated queries. The example below illustrates that the true value (False) can be recovered from the majority count.
Examples
Examples
Basic example
Basic example
Create a dataset
Use the differentialPrivacyFunction to deploy an APIFunction to the cloud.
A user only sees an APIFunction
Performing a new query decreases the remaining PrivacyBudget and appends the query-result pair into the Cache.
Repeating a query simply returns the previous result stored in the Cache.
Queries going beyond the PrivacyBudget will be unanswered.
The Cache contains return all answered queries.
Working with ResourceData
Working with ResourceData
Take some entries from ResourceData, and add a differentially-private mechanism:
Data analysts queries the average value of HHType1Income where HHType5TransitTrips > 5 using a more secure DP object created using the default setting.
Data analysts queries the average value of HHType1Income where HHType5TransitTrips > 5 using a less secure DP object.
Conclusions and Future Work
Conclusions and Future Work
In this project, we implemented two functions for making datasets differentially private. We created a differentially-private APIFunction currently supports Sum, Average, and Count queries through an SQL-like format. Using the Wolfram Languages native support for deploying CloudObjects, we can ensure that data analysts are able to perform queries on a dataset without accessing it in its raw form. Directions for future work include enriching the function to support other common database queries, such as categorical queries and order statistics. Extensive tests are recommended to ensure that the configured privacy level is obeyed.
Acknowledgment
Acknowledgment
I wish to acknowledge Christian Pasquel for his patient assistance in developing this project. His ideas kept the implementations grounded to potential real-life usage of differential privacy. I also would like to thank everyone from WSS 2020 TAs for their very helpful posts on Slack.
References
References
1
.A. Narayanan and V. Shmatikov, “Robust De-anonymization of Large Sparse Datasets,” 2008 IEEE Symposium on Security and Privacy (sp 2008), Oakland, CA, 2008, pp. 111-125, doi: 10.1109/SP.2008.33.
2
.C. Dwork, F. McSherry, K. Nissim & A. Smith (2016). Calibrating noise to sensitivity in private data analysis. Theory of cryptography conference. Springer, Berlin, Heidelberg, 2006.