I have to prove some differential privacy in a exercise i'm doing.
I have this table, and problem description:
A research institution publishes study results about political preferences. In order to preserve privacy of the participants, the results of the study are output only via the query interface, where count queries of the form “output count of records in D that satisfy Q” are allowed, with Q as conditions on either gender, age, marital status, education or political preference (defined as either “liberal” or “conservative”). Acceptable queries are e.g.: – C(Q(D)) = Count of records in D where gender = “male”, age = “50- 59”, marital status = “married” and political views = “liberal” – C(Q(D)) = Count of records in where age = “20-29” or “30-39”, education != “never married” and political views = “conservative” Assume that an adversary has the list of participants (= the dataset D) of the study and knows the name, gender, age, education and marital status for each of them, see Table 1.
And my dataset looks like this:
The first exercise sounds like this:
a) Come up with a query that would allow the adversary to find out the political views of Laura Pohlman.
Which I solved with thissimple query:
C(Q(D)) = Count of records in D where gender = "female", age =20-29", eduaction = "upper secondary education" and political views = "liberal"
But now I have a harder exercise, that sounds like this:
c) Instead of outputting error for small counts, the system implements privacy protection by adding noise to the query, namely,outputting 𝐴(𝐷)=𝐶(𝑄(𝐷))+𝑋 where 𝐶(𝑄(𝐷)) is a real count of records in 𝐷that satisfy 𝑄, and 𝑋 is random noise that is uniformly distributed on the interval [−3,3].Prove that the resulting algorithm 𝐴 still does not ensure differential privacy for any real number𝜀. Hint: define 𝐷 as the dataset in Table 1, 𝐷’as the same dataset excluding Laura Pohlman. Then considerthe conditions𝑄you used in solving a)for defining 𝐴(𝐷)=𝐶(𝑄(𝐷))+𝑋 and 𝐴(𝐷’)=𝐶(𝑄(𝐷’))+𝑋 correspondingly, and show that for 𝑠=4 there is noreal number 𝜀 so that: 𝑃(𝐴(𝐷)=𝑠) ≤ 𝑒^𝜀𝑃(𝐴(𝐷’)=𝑠)
I have no idea how to solve this.
If I, as the exercise suggests set s=4, then I then noice that X is must be three. I don't know what that says about the probabilities though.
can someone help?