Is it possible to know if two geographic locations are within a certain distance of each other without revealing the location?
I'm thinking about contact tracing during the COVID-19 outbreak. Assuming users have an app that records their location history, more specifically where the stopped and spend a few minutes. When a user is diagnosed with COVID-19 imagine they could share where and when they've been somewhere but without revealing the actual location and time. Other users could compare their own location history and know if there's a match.
Here's what I'm thinking so far, but I'm not sure if it's secure or not:
Let's say that locations within roughly 7.5 meters and 7.5 minutes of each other are considered a match.
- Take your coordinates with enough precision up to 5 meters
- Take the 5 meter squares around you, so you have a 3x3 grid
- Take the current time rounded to the nearest 5 minutes
- Take the 5 minutes before and 5 minutes after
- Hash each combination of coordinate squares and 5 minute intervals
Now you have a set of 27 hashes. Other users can hash their own location and time (with the same precision) and see if it matches any of your hashes, but otherwise cannot know where or when that set of hashes corresponds to.
Granted, it's not precise there's a margin of error (is it 2.5?) but that's acceptable IMO.
Would this work?