tml

CIS 6261: Trustworthy Machine Learning (Spring 2023) Homework 2 — Data Privacy & Differential Privacy Name: Your Name Here March 22, 2023 This is an individual assignment. Academic integrity violations (i.e., cheating, plagiarism) will be reported to SCCR! The official CISE policy recommended for such offenses is a course grade of E. Additional sanctions may be imposed by SCCR such as marks on your permanent educational transcripts, dismissal or expulsion. Reminder of the Honor Pledge: On all work submitted for credit by Students at the University of Florida, the following pledge is either required or implied: “On my honor, I have neither given nor received unauthorized aid in doing this assignment.” Instructions Please read the instructions and questions carefully. Write your answers directly in the space provided. Compile the tex document and hand in the resulting PDF. For this assignment, you will solve several data privacy problems. The third problem asks you to implement a differential privacy mechanism using Python3. Use the code skeleton provided and submit the completed source file(s) alongside with the PDF. Note: bonus points you get on this assignment *do* carry across assignments. 1

Problem 1: Syntactic Metrics (20 pts) Consider the data set depicted in Table 1 . Answer the following questions. (Justify your answers as appropriate.) Age Zip Code Sex Diagnosis 40-49 32605 M COVID-19 30-39 32607 M Broken Leg 30-39 32607 M Cancer 40-49 32611 F Heart Disease 20-29 32607 F Asthma 20-29 32607 F Heart Disease 40-49 32611 M Hypertension 40-49 32611 F COVID-19 Table 1: Anonymized Data Set 1. 1. (5 pts) What are the quasi-identifier(s)? What are the sensitive attribute(s)? In this dataset, the quasi-identifiers are the combination of Age, Zip Code, and Sex, because When linked with external data, quasi-identifiers are a collection of attributes or variables in a dataset that can potentially identify people. These characteristics do not immediately reveal an individual’s identity, but when combined with additional data, they can be used to re-identify or de-anonymize someone. The sensitive attribute in this dataset is the diagnosis column because a sensitive attribute is an attribute or variable in a dataset that contains private or sensitive data regarding an individual. 2. (5 pts) What is the largest integer k such that the data set satisfies k -anonymity? What is the largest integer l such that the data set satisfies l -diversity? Your answer here. 3. (10 pts) Modify the data set using generalization and suppression to ensure that it satisfies 4- anonymity and 3-diversity. Here we are looking for a solution that minimally affects the utility of the data. Write the modified data set below. The intervals 40-49 have four rows, and all other remaining intervals have four rows as well, thus we have four anonymity and three diversity. Age Zip Code Sex Diagnosis 40-49 326** * COVID-19 30-39 326** * Broken Leg 30-39 326** * Cancer 40-49 326** * Heart Disease 20-29 326** * Asthma 20-29 326** * Heart Disease 40-49 326** * Hypertension 40-49 326** * COVID-19 2

4. (5 pts) Give an example of a database X (with a least 5 entries) such that the local sensitivity of f t given threshold t = 0 . 3 is 0. First give the definition of local sensitivity then answer the question. Definition: Local sensitivity evaluates how much a function’s output varies when a single record in the input database is added, removed, or updated. X = Suppose we have a database X consisting of 5 binary values indicating whether a student has committed a certain crime or not: x= { 1,0,1,1,1 } then g(x) is 4 and x is 5 then g ( x ) / | x | is 0.8 greater than threshold limit(0.3) and f t is 1 .If we modify the 4th values as to 0 then X1 is { 1,0,1,0,1 } then g(x1) is 3 and | X 1 | is 5 then g ( x 1) / | X | is 0.6 it is greater than threshold limit f t is 1 .now calculating the local sensitivity is difference between f t ( x ) and f t ( x 1) i.e | 1 − 1 | =0 Now let’s consider the following mechanisms. For each of them, you are asked to prove or disprove whether they satisfy differential privacy. (To prove differential privacy you need to show that the mech- anism satisfies the definition. To disprove you can simply give a counterexample.) Recall the definition of (pure) ε -differential privacy. Definition 1. A randomized algorithm F satisfies ε - differential privacy (for ε > 0 ) if for any two neighboring databases X, X ′ and any S ⊆ Range( F ) : Pr {F ( X ) ∈ S } ≤ e ε Pr {F ( X ′ ) ∈ S } . 5. (5 pts) Mechanism A: F ( X ) = f t ( X ). That is the mechanism simply returns the output of f t . This mechanism does not satisfy ε -differential privacy. Consider two neighboring databases, X and X’, which differ only in one element. Assume X has a 0 in that entry and X’ has a 1.Let t represent the f t thresholdvalue. letsbesetofpossibleoutcome = 0,1 andeventbetheoutputoff t is 1 . p = pr F ( X ) ∈ S = Pr { f t ( X ) } = 1 p 1 = pr F ( X 1 ) ∈ S = Pr { f t ( X 1 ) } = 1 Now, since X and X’ differ in only one entry, the output of ft on these databases can differ by at most 1/n, where n is the size of the database. This is because if X and X’ have n entries and differ in only one entry, then the maximum difference in the number of 1s between X and X’ is 1. Now, suppose t = 0.5, and let = ln (2) . Then we have: e = e l n (2) = 2 Let X be the database where all entries are 0, except for one entry which is 1. Let X’ be the database where all entries are 0. Then we have: p=1/n p 1 = 0 Pr { p = 1 /n } ≤ Pr { p 1 = 0 } 6. (5 pts) Mechanism B: F ( X ) = thresh 0 . 5 ( f t ( X ) + z ), where z ∼ Lap(0 , b ) for b = ∆ f t ε . That is the mechanism computes the output of f t , adds Laplace noise to it, and then thresholds the value to 0.5 before returning it. Prove or disprove. Your answer here. 7. (5 pts) Mechanism C: F ( X ) = thresh t ( g ( X )+ z | X | ), where z ∼ Lap(0 , b ) for b = ∆ g ε . That is the mechanism computes the output of g , adds Laplace noise to it (calibrated to g), and then thresholds the value to t before returning it. Prove or disprove. Your answer here. 4

8. (5 pts) Mechanism D: F ( X ) = flip p ( f t ( X )), where flip p : { 0 , 1 } → { 0 , 1 } is a function to randomly flip the bit based on a biased coin flip p ∈ [0 , 1] (probability of heads is p ). Let flip p ( x ) = 1 − x with probability p (the coin comes up heads) and flip p ( x ) = x with probability 1 − p (the coin comes up tails). In other words, this mechanism computes the output of f on the database and then randomly flips it with probability p . For what value of p (if any) does mechanism D satisfy ε -differential privacy? Prove or disprove. State the relationship (if any) between p and ε . Your answer here. 5

Your answer here. 3. (5 pts) Now calculate the privacy budget of computing the mean GPA query using the Gaussian mechanism and then invoking the Exponential mechanism 10 times to get (10 random samples of) the most popular CISE course. Give an expression for both naive/sequential composition and advanced composition. The expression should be in terms of ε and δ assuming each query satisfies ( ε 0 , δ 0 )-DP. Naive composition: Your answer here. Advanced composition: Your answer here. 4. (5 pts) Given you answer to the previous question, which composition theorem would you apply in which scenario? (Justify your answer.) Your answer here. 5. (5 pts) Now go back to the code in main () for problem 3.2 and locate the hardcoded course list that the Exponential mechanism uses. Why is the list of courses not computed directly from the dataset? (Justify your answer.) Your answer here. 7