[woozyolliew]

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]

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]

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.

[CodesInChaos]

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.

[mirker]

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.

[sa1]

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?

[dragonwriter]

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.

[IneffablePigeon]

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.

[nprateem]

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