Hacker News Reader

Comment by thanksforfish | Hacker News Reader

> 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.

View on HN

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.

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.

In a sense urban area, that would help. In small towns, or out in the country? Not a chance.

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.

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!

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?

I like your added protections. Allowing people to filter their reported data might be enough to convince people to use it even without additional security.

Don't use sha256 for the hash, we need a slow hash like bcrypt or scrypt. Since entries only need to be updated when moving between time boxes or space boxes we can in fact configure this to be quite slow.

You could make it a bit more robust by requiring clients to upload a minimum number of unique hashes with their query then respond only with an "exposed" or "not exposed" response. Then you can check for clients that are repeatedly uploading the same hashes to weed out brute forcers.

I think it would be pretty impractical to brute force all possible space-time blocks. Even if you just wanted to look at the state of California over 24 hours you're looking at 1.0952599e+12 hashes [0]. Say your rig can try 500k hashes a second, that's still almost a month. So now you know the rough locations of every infected person in California over the course of one day, you still have to disentangle the movements of overlapping users. You can make this even harder by requiring people to loiter in a space box for a minimum amount of time before creating an entry, so travel by bike/train/plane/automobile wont be tracked at all.

Clearly the scheme is resistant against mass de-anonymization, but if you knew some specific locations where you thought a specific person might go you could target those space-boxes and, assuming there are not many other infected users in the area, get a sense of when that person was at those places.

[0] 163,696 sq miles = 4.563583e+12 sqft = 45,635,830,000 100sqft space boxes * 24 = 1.0952599e+12

Ah good point about overlapping location data for sick users, that would add ambiguity.

This approach still puts a lot of trust in the server. Every client needs to upload their hashes to the server, so if the group running the server wanted to reverse the hashes they'd get everyone's location, not just sick people. The server would also know which hashes were popular, indicating that they are crowded areas like a city or event center. From a tracking perspective the fact that two people were in the same location is useful to start making inferences, even if the location isn't known.

Reply on news.ycombinator.com