I apologize I am new to statistics so I do not know all terms and concepts.

My current algorithm for adding noise to multiple-choice favorite color data is this:

x = rand(1)
if x > .5:
    return original_color
if x < .5:
    y = rand(1)
    if y > .67:
        return "blue"
    else if y > .33:
        return "red"
        return "green"

From this I get a "private" dataset and will calculate how many people's favorite color is red.

My question is: how can I calculate whether this is differentially private? I know I need to calculate the chance that this algorithm yields any given number of reds, and the chance that a dataset with one changed row would have the same number of reds. I keep getting stuck.

Assume the original dataset has 100 rows: 50 red, 30 blue, 20 green. Then for each row there is a

.5 (chance of red) x .5(chance noise is added) x .66 (chance noise added is not red) probability that a red will be subtracted and a

.5 (chance of not red) x .5(chance noise is added) x .33 (chance noise added is red) probability that a red will be added.

How do I synthesize this information to calculate whether the algorithm is differentially private? Can anyone point me in the right direction? Furthermore, is my algorithm completely naive? Thank you!


You're adding noise to each data point, so you're doing local differential privacy. This means you need to consider, for each data point $i$, each output color $c$ and each pairs of colors $c_1$, $c_2$ what is the maximum ratio of:

$$ \frac{P(\text{noised_color}(i)=c|\text{original_color}(i)=c_1)}{P(\text{noised_color}(i)=c|\text{original_color}(i)=c_2)} $$

In your case, the numerator is maximized when $c=c_1$ (it's $\frac{1}{2}+\frac{1}{2}\times\frac{1}{3}=\frac{2}{3}$ — the probability of returning the true answer directly plus the probability of returning the correct answer at random), and minimal when $c\neq c_1$ (it's $\frac{1}{2}\times\frac{1}{3}=\frac{1}{6}$ — the probability of returning $c$ at random). The maximal value of the ratio is thus $4=e^{2\ln(2)}$, so your scheme is $\varepsilon$-differentially private with $\varepsilon=2\ln(2)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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