3 ms·

> they could just have their location file uploaded (anonymously) Anonymity is going to be hard, even with traditional methods, but I don't think a person's lo

> they could just have their location file uploaded (anonymously) Anonymity is going to be hard, even with traditional methods, but I don't think a person's location history can ever be anonymous. Especially when presented with timestamps and spanning days. People generally spend a lot of time, or at least their night, in their home. > This is one of those network paradox problems where you need lots of people for the network to be useful, but the network has to be useful to attract lots of people. How do you solve that? Bake it into an existing app that already has the network, I.E. Facebook.

georgeam 7y ago
In principle it could be installed as a system/default app on Android and iOS by Google and Apple respectively. Even more reach for people that haven't installed Facebook.
c22 7y ago
I think you can get around this. Break the physical space up into blocks, say 100' square. Break the time component into 1 hour blocks. Concatenate the space and time components and hash them, then upload the hashes. If someone wants to see if they've potentially been exposed they can just hash their own time/location history and see if it gets a hit against the database.
- LyndsySimon 7y ago
  In a sense urban area, that would help. In small towns, or out in the country? Not a chance.
  - c22 7y ago
    Why not? To correlate any meaningful data an attacker would have to reverse a significant portion of the database. The most serious attack I see would be a brute force over time of Bob's location segment. At most this gives Eve retroactive information about when Bob was home after Bob has tested positive and uploaded his data. It still doesn't give any insight into where Bob went when he left except perhaps in extremely sparse areas. Our imaginary service can help reduce the impact of this attack further by rate limiting requests and discarding old data as soon as it's no longer relevant. This failure mode is probably still less intrusive than the current system of asking people in quarantine to detail all of their recent movements. Ironically, you might achieve better anonymity by making the time and space boundaries smaller, but at the expense of more false negatives when checking for exposure.
- sunemai 7y ago
  If you are able to check whether you've been in a "dangerous" space-time box yourself, then you are probably also able to check where these boxes are, I suppose? One way would be brute force hashing all possible space-time blocks and comparing with the public hashed list. This mechanism was why I abandoned the space-time box approach to begin with - but if you have an idea for a workaround, please get in touch!
  - thanksforfish 7y ago
    It's a "hash of a small search space" problem. Here's the best I got: 1. Each client will sha256 hash their space-time box (lat,lon,timestamp each rounded to some suitable size). This is their space-time box hash. 2. Each client takes the first N bytes of their space-time box hash and registers it with a service. This must occur within M hours, to limit after the fact analysis. These are privately stored on the server and deleted after R days (R ~= 14 for corona virus IIRC). 3. Each person can blacklist certain places, like their home from getting reported. When home you probably know who you interact with, and don't need software to help. Also times, most people can probably recall who they sleep with so bedtime->alarm doesn't need to be tracked. 4. Someone gets sick. They can now choose to report and share their fine grained location history with the service. Ideally people choose to report and share for the sake of public health. They (or realistically a trusted healthy person) can shift through the location stats to see if there's any locations to skip (again, at home and sleeping times probably don't need to be reported as most folks recall who was there). 5. The service records the fine grained location data and notifies the app for everyone who reported a space-time hash prefix that matches. This will notify lots of non-matches as we only reported the first N bytes. 6. Each notified client then looks at their space-time hash and sends additional bytes to the service, checking if they match one by one. If a mismatch is found the client stops. The service refuses to allow this type of lookup except from clients that previously registered a matching hash prefix. Someone needs to do the math to pick a good value for N and others. This provides some protection from the service deanonymizing people and tries hard to only share matches with clients that were matched. How's that work?
    - c22 7y ago

georgeam 7y ago

In principle it could be installed as a system/default app on Android and iOS by Google and Apple respectively. Even more reach for people that haven't installed Facebook.

c22 7y ago

I think you can get around this. Break the physical space up into blocks, say 100' square. Break the time component into 1 hour blocks. Concatenate the space and time components and hash them, then upload the hashes. If someone wants to see if they've potentially been exposed they can just hash their own time/location history and see if it gets a hit against the database.

LyndsySimon 7y ago
In a sense urban area, that would help. In small towns, or out in the country? Not a chance.
- c22 7y ago
  Why not? To correlate any meaningful data an attacker would have to reverse a significant portion of the database. The most serious attack I see would be a brute force over time of Bob's location segment. At most this gives Eve retroactive information about when Bob was home after Bob has tested positive and uploaded his data. It still doesn't give any insight into where Bob went when he left except perhaps in extremely sparse areas. Our imaginary service can help reduce the impact of this attack further by rate limiting requests and discarding old data as soon as it's no longer relevant. This failure mode is probably still less intrusive than the current system of asking people in quarantine to detail all of their recent movements. Ironically, you might achieve better anonymity by making the time and space boundaries smaller, but at the expense of more false negatives when checking for exposure.
sunemai 7y ago
If you are able to check whether you've been in a "dangerous" space-time box yourself, then you are probably also able to check where these boxes are, I suppose? One way would be brute force hashing all possible space-time blocks and comparing with the public hashed list. This mechanism was why I abandoned the space-time box approach to begin with - but if you have an idea for a workaround, please get in touch!
- thanksforfish 7y ago
  It's a "hash of a small search space" problem. Here's the best I got: 1. Each client will sha256 hash their space-time box (lat,lon,timestamp each rounded to some suitable size). This is their space-time box hash. 2. Each client takes the first N bytes of their space-time box hash and registers it with a service. This must occur within M hours, to limit after the fact analysis. These are privately stored on the server and deleted after R days (R ~= 14 for corona virus IIRC). 3. Each person can blacklist certain places, like their home from getting reported. When home you probably know who you interact with, and don't need software to help. Also times, most people can probably recall who they sleep with so bedtime->alarm doesn't need to be tracked. 4. Someone gets sick. They can now choose to report and share their fine grained location history with the service. Ideally people choose to report and share for the sake of public health. They (or realistically a trusted healthy person) can shift through the location stats to see if there's any locations to skip (again, at home and sleeping times probably don't need to be reported as most folks recall who was there). 5. The service records the fine grained location data and notifies the app for everyone who reported a space-time hash prefix that matches. This will notify lots of non-matches as we only reported the first N bytes. 6. Each notified client then looks at their space-time hash and sends additional bytes to the service, checking if they match one by one. If a mismatch is found the client stops. The service refuses to allow this type of lookup except from clients that previously registered a matching hash prefix. Someone needs to do the math to pick a good value for N and others. This provides some protection from the service deanonymizing people and tries hard to only share matches with clients that were matched. How's that work?
  - c22 7y ago