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?

  • 2
    $\begingroup$ Welcome to Cryptography S.E. Look, if I could point out an only concern, I would say that hash functions are not for privacy, secrecy, anonymity. B.T.W., someone else has to have access to the positions and check the hashes: What is your adversarial model concerning this third party? $\endgroup$ Mar 30 '20 at 16:57
  • $\begingroup$ Thanks for the reply @McFly. My thought was that by combining a 9 character string representing the location (geohash) with the current 5 minute block, and hashing the result, you get a string that is too difficult to calculate every possible permutation. Geohash uses 28 characters so 28^9 * 365*24*60/5 $\endgroup$
    – joshblour
    Mar 30 '20 at 17:56

Your solution is not resistant to a rainbow table attack. Furthermore, what if an adversary supposes your locality: ask you about your "private" location information, fake his/her one and tries to retrieve yours?

When you say "Anonymous location" and "without revealing the location" you are demanding a very difficult problem of Multiparty Computation: see MPC millionaire problem.

B.T.W, we can find more robust solutions that mix hash and location privacy: have you ever heard about "Spatial Bloom Filter"?

  • $\begingroup$ Spatial Bloom Filter looks promising! thanks for that. About the rainbow table, would adding a salt make it more resistant? $\endgroup$
    – joshblour
    Mar 31 '20 at 6:29
  • $\begingroup$ @joshblour, it depends on the adversarial model: does he/she have limited computing power, limited time to search? 'salts' in hash-based schemes makes that type of attack a lit bit harder. Therefore, can you think of an adversary who has a lot of time...? The adversarial model is everything: maybe this is the case for Geohash; people can defend it under a framed adversarial model. $\endgroup$ Apr 1 '20 at 13:43

With my ex-Platin hat on, there was some progress with a Schnorr-like protocol for "not far from" statement about distance. It was not quite finished and still lacks a few parts like producing 4-squares (Lagrange theorem) and adjusting protocol parameters in integers (not a prime field).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.