3 ms·
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
by 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 agoI 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.