5 ms·

This seems like a potential use-case for differential privacy. Normally DP is used for protecting individuals within aggregates, but the careful analysis of ho

This seems like a potential use-case for differential privacy. Normally DP is used for protecting individuals within aggregates, but the careful analysis of how much (and what kind) of noise to add could be brought to bear here.

mirker 5y ago
It’s only a partial solution; you still need to limit the queries. Otherwise, just sample a large number of coordinates and average out the noise.
- pageandrew 5y ago
  What about a constant, random, per-match offset? An error applied to a match's position that can't be averaged out, because it is always wrong by the exact same amount. Use a different error in a different direction for each unique match so one can't figure it out once and apply it system wide. I suppose the downside is that this could put someone else at risk if the tweaked position happens to be on top of their house.
  - mirker 5y ago
    It’s the same thing but more time consuming. If you knew this was happening, you’d create N accounts, match with the same person, and average queries over account pairs. Also, if the error is constrained to be the same, then the attack is reduced to estimating the radius of a circle where you are given points on the perimeter, which you should be able to do in very few queries (3?). I haven’t worked out the triangulation math but you’d basically solve for x^2+y^2=r^2.
  - CodesInChaos 5y ago
    1. The attacker can use multiple accounts to collect data, so an offset specific to the viewer wouldn't work 2. If you can collect the offset location over a longer time, you can correlate it with likely travel paths (e.g. along major roads) to figure out what the offset is.
- dragonwriter 5y ago
  Yeah, its an overcomplicated, breakable solution. Just decide the minimum safe uncertainty, assign grid cells that provide it, and only report distance quantized to grid cells.
  - mirker 5y ago
    Agreed, but you still have some trouble if the grid cell is aligned next to a body of water or some other obstruction, since you can deduce a higher certainty then.
  - IneffablePigeon 5y ago
    Every time this comes up a hundred people decide you "just" need to quantize, and that does help but is still vulnerable in multiple ways, including if you have low "valid location" density (think a grid cell that is 95% water) or if you're on a boundary and flip between two cells. It's easy to mitigate the normal case but takes more thought to mitigate the edge cases.
- sa1 5y ago
  Apple’s coarse location, iirc, chooses your location in such a manner that it can’t be averaged out. Maybe by limiting updates as well?
  - mirker 5y ago
    One way is to hash the user_ID to generate the “noise” that is consistent for that user. Then repeated queries are the same, so the average is identical to all samples. Averages only work if your samples aren’t correlated.
nprateem 5y ago
I can't see a problem with adding a random, static offset to users' locations that is rotated daily.

mirker 5y ago

It’s only a partial solution; you still need to limit the queries. Otherwise, just sample a large number of coordinates and average out the noise.

pageandrew 5y ago
What about a constant, random, per-match offset? An error applied to a match's position that can't be averaged out, because it is always wrong by the exact same amount. Use a different error in a different direction for each unique match so one can't figure it out once and apply it system wide. I suppose the downside is that this could put someone else at risk if the tweaked position happens to be on top of their house.
- mirker 5y ago
  It’s the same thing but more time consuming. If you knew this was happening, you’d create N accounts, match with the same person, and average queries over account pairs. Also, if the error is constrained to be the same, then the attack is reduced to estimating the radius of a circle where you are given points on the perimeter, which you should be able to do in very few queries (3?). I haven’t worked out the triangulation math but you’d basically solve for x^2+y^2=r^2.
- CodesInChaos 5y ago
  1. The attacker can use multiple accounts to collect data, so an offset specific to the viewer wouldn't work 2. If you can collect the offset location over a longer time, you can correlate it with likely travel paths (e.g. along major roads) to figure out what the offset is.
dragonwriter 5y ago
Yeah, its an overcomplicated, breakable solution. Just decide the minimum safe uncertainty, assign grid cells that provide it, and only report distance quantized to grid cells.
- mirker 5y ago
  Agreed, but you still have some trouble if the grid cell is aligned next to a body of water or some other obstruction, since you can deduce a higher certainty then.
- IneffablePigeon 5y ago
  Every time this comes up a hundred people decide you "just" need to quantize, and that does help but is still vulnerable in multiple ways, including if you have low "valid location" density (think a grid cell that is 95% water) or if you're on a boundary and flip between two cells. It's easy to mitigate the normal case but takes more thought to mitigate the edge cases.
sa1 5y ago
Apple’s coarse location, iirc, chooses your location in such a manner that it can’t be averaged out. Maybe by limiting updates as well?
- mirker 5y ago
  One way is to hash the user_ID to generate the “noise” that is consistent for that user. Then repeated queries are the same, so the average is identical to all samples. Averages only work if your samples aren’t correlated.

nprateem 5y ago

I can't see a problem with adding a random, static offset to users' locations that is rotated daily.