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:

enter image description here

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?


1 Answer 1


One more hint: with $s=4$, try to show that one of the probabilities is zero (e.g. it is impossible to obtain the output $s$). No matter what you multiply zero by, the result is always zero… The other, on the other hand, is strictly positive. Can you take it from there?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.