[wackspurt]

Apparently, DP has some detractors. I was told by my signal processing professor that differential privacy wasn't really a solution for privacy preserving data analysis. He said something along these lines: "if I know something about the underlying data distribution (Gaussian, etc.), it is possible to wash out the randomness."

Now, I don't understand DP well enough and information theory/signal processing still seems a bit like "dragons be here" to me. But, I want to take a stab at trying to reason why he said that.

For example, take randomized response (the only DP technique I understand). That is vulnerable to a longitudinal attack: a person can query repeatedly to wash out the randomness. If you think about it, isn't it the almost the inverse of a repetition code (error correction)? There, you're trying to use redundancy (repetition) to remove noise.

[telchar]

You're right that with repeated sampling you can learn more about the data set. If I understand it correctly, I think the solution to that in DP is that you have a limit to how many times you can make your repeated query before you have spent your privacy budget and are cut off. The idea is that for a given budget level you are limited to fewer queries than you would need to learn enough to de-anonymize the data set.

If your signal processing professor was already taking that into account then I would be curious to know how that attack would work.