3 ms·

I don't like differential privacy very much. Take GPS data, for example: NYC has released a taxicab dataset showing the "anonymized" location of every pickup a

I don't like differential privacy very much. Take GPS data, for example: NYC has released a taxicab dataset showing the "anonymized" location of every pickup and dropoff. This is bad for privacy. One attack is that now if you know when and where someone got in a cab (perhaps because you were with them when they got in), you can find out if they were telling the truth to you about where they were going -- if there are no hits in the dataset showing a trip from the starting location that you know to the ending location that they claimed, then they didn't go where they said they did. Differential privacy researchers claim to help fix these problems by making the data less granular, so that you can't unmask specific riders: blurring the datapoints so that each location is at a city block's resolution, say. But that doesn't help in this case -- if no-one near the starting location you know went to the claimed destination, blurring doesn't help to fix the information leak. You didn't need to unmask a specific rider to disprove a claim about the destination of a trip. I think that flaws like these mean that we should just say that GPS trip data is "un-de-identifiable". I suspect the same is true for all sorts of other data. For example, Y chromosomes are inherited the same way that surnames often are, meaning that you can make a good guess at the surname of a given "deidentified" DNA sequence, and thus unmask its owner from a candidate pool, given a genetic ancestry database of the type that companies are rapidly building.

losteric 9y ago
It's been a couple years since I read the literature so I might be wrong, but iirc differential privacy fuzzes the number of matches instead of the data points themselves. That is, in your example differential privacy would precisely display the start and end points but the number of riders would be fuzzed (perhaps showing 4 departures and 2 arrivals at the respective location/time). Also, iirc, offline differential privacy can outright remove data points while online system can block sufficiently deanonymizing queries. One of the criticisms of differential privacy is that it can render the data useless... I definitely found that held true for my data. In the end, my company simply decided against releasing (or collecting) any customer data.
- yoz-y 9y ago
  Doesn't it also introduce noise into the dataset? It could modify rides at random, let's say that 10% of rides would have the start or end point swapped with some other ride or completely changed. That way the information in aggregate is still useful, but no one measurement is necessarily true and also you can not use the lack of a data point as a proof of anything.
  - losteric 9y ago
    > That way the information in aggregate is still useful, but no one measurement is necessarily true and also you can not use the lack of a data point as a proof of anything. This is great, succinct, description of the goals of differential privacy. > Doesn't it also introduce noise into the dataset? It could modify rides at random, let's say that 10% of rides would have the start or end point swapped with some other ride or completely changed. It can. There are variants, and offline/online systems operate differently.
rectang 9y ago
Amen. The obscuring only works against known techniques. So long as signal remains in the collective data, as the state of the art advances individual data streams will inevitably emerge.
bo1024 9y ago
You seem to have an incorrect version of differential privacy in mind. "Blurring the datapoints" as you describe would not satisfy differential privacy at all. DP would not allow an information leak of this kind, unless the data set was modeled in a very silly way.
obastani 9y ago
The attack you suggest is ruled out by differential privacy. The precise guarantee is a bit complicated. The first thing to note is that the output of a differentially private mechanism must be random. Then, the guarantee is that Pr[output] does not change by very much whether or not you are included in the dataset. In other words, even if you were omitted from the dataset, there the chance that the algorithm produced the same result is very similar. This definition rules out the attack you suggest. In particular, if you are removed from the dataset, then the probability of the output (i.e., a ride starts in the region) goes from very large to very small. Therefore, the algorithm you describe (i.e., adding noise to the start location) is not actually differentially private. The confusion arises because oftentimes adding noise is sufficient. For example, the average of n real numbers in [0,1] is affected by at most 1/(n-1) if you delete one point from the dataset. Therefore, you can just add a little bit of noise and the dataset becomes differentially private. For the dataset you describe, a sibling comment proposed the correct mechanism -- you have to add noise to the count returned by the query, not the start location. (Technically I think you could just add noise to the start location like you propose, but the amount of noise would have to be large enough that all the start locations overlap by a sufficient amount.)
- cjbprime 9y ago
  Thank you! Makes sense.
arnarbi 9y ago
> if there are no hits in the dataset showing a trip from the starting location that you know to the ending location that they claimed, then they didn't go where they said they did. As others have pointed out, differential privacy is not obtained just by blurring the points. But I'd like to point out that what you wrote above is closely related to exactly the original definition of DP. DP guarantees that you cannot get a statistically significant difference between a dataset with one element removed (e.g. a trip in your case). That implies that the difference is also insignificant if you add a point. In other words DP addresses exactly your concern here.

losteric 9y ago

It's been a couple years since I read the literature so I might be wrong, but iirc differential privacy fuzzes the number of matches instead of the data points themselves. That is, in your example differential privacy would precisely display the start and end points but the number of riders would be fuzzed (perhaps showing 4 departures and 2 arrivals at the respective location/time). Also, iirc, offline differential privacy can outright remove data points while online system can block sufficiently deanonymizing queries. One of the criticisms of differential privacy is that it can render the data useless... I definitely found that held true for my data. In the end, my company simply decided against releasing (or collecting) any customer data.

yoz-y 9y ago
Doesn't it also introduce noise into the dataset? It could modify rides at random, let's say that 10% of rides would have the start or end point swapped with some other ride or completely changed. That way the information in aggregate is still useful, but no one measurement is necessarily true and also you can not use the lack of a data point as a proof of anything.
- losteric 9y ago
  > That way the information in aggregate is still useful, but no one measurement is necessarily true and also you can not use the lack of a data point as a proof of anything. This is great, succinct, description of the goals of differential privacy. > Doesn't it also introduce noise into the dataset? It could modify rides at random, let's say that 10% of rides would have the start or end point swapped with some other ride or completely changed. It can. There are variants, and offline/online systems operate differently.

rectang 9y ago

Amen. The obscuring only works against known techniques. So long as signal remains in the collective data, as the state of the art advances individual data streams will inevitably emerge.

bo1024 9y ago

You seem to have an incorrect version of differential privacy in mind. "Blurring the datapoints" as you describe would not satisfy differential privacy at all. DP would not allow an information leak of this kind, unless the data set was modeled in a very silly way.

obastani 9y ago

The attack you suggest is ruled out by differential privacy. The precise guarantee is a bit complicated. The first thing to note is that the output of a differentially private mechanism must be random. Then, the guarantee is that Pr[output] does not change by very much whether or not you are included in the dataset. In other words, even if you were omitted from the dataset, there the chance that the algorithm produced the same result is very similar. This definition rules out the attack you suggest. In particular, if you are removed from the dataset, then the probability of the output (i.e., a ride starts in the region) goes from very large to very small. Therefore, the algorithm you describe (i.e., adding noise to the start location) is not actually differentially private. The confusion arises because oftentimes adding noise is sufficient. For example, the average of n real numbers in [0,1] is affected by at most 1/(n-1) if you delete one point from the dataset. Therefore, you can just add a little bit of noise and the dataset becomes differentially private. For the dataset you describe, a sibling comment proposed the correct mechanism -- you have to add noise to the count returned by the query, not the start location. (Technically I think you could just add noise to the start location like you propose, but the amount of noise would have to be large enough that all the start locations overlap by a sufficient amount.)

cjbprime 9y ago
Thank you! Makes sense.

arnarbi 9y ago

> if there are no hits in the dataset showing a trip from the starting location that you know to the ending location that they claimed, then they didn't go where they said they did. As others have pointed out, differential privacy is not obtained just by blurring the points. But I'd like to point out that what you wrote above is closely related to exactly the original definition of DP. DP guarantees that you cannot get a statistically significant difference between a dataset with one element removed (e.g. a trip in your case). That implies that the difference is also insignificant if you add a point. In other words DP addresses exactly your concern here.