Say I would like to create an app that would allow users to organize treasure hunts for their parties. The host of the party would create a list of GPS coordinates for each hiding spot and distribute the list to the guests. At the treasure hunt, guests would then use the app – offline – to get alerts when they are close to a hiding spot, record how long they took to find each treasure, etc.

Given the above setup, a moderately tech-savvy user will just look at the list of GPS coordinates and spoil the hunt. To what degree can this be avoided? In this example, obfuscation would probably be sufficient, but I am interested in the general case.

I’ve considered distributing the list in this form: HASH(QUANTIZE(latitude) || QUANTIZE(longitude)) with the quantization level set to allow the app to give hints at the appropriate distance, but I’m not sure if this could be tweaked to still be difficult to attack.

Is this a know problem? Are there any standard techniques or approaches that can be (practically) applied to it? I'd also appreciate pointers to related questions/papers.

  • 1
    Your original idea, with a random pepper should be good enough. By pepper what I mean is $hash(value + pepper)$; say pepper is 10 bits, so in average you'll need to do $2^{9}$ rounds to verify the hash. And you can make it harder as you want, as you increase the size of the pepper. – zetaprime Oct 9 at 18:36
up vote 1 down vote accepted

There's no cryptographic way to keep users from faking their location without trusted hardware. There's also no good way to keep users from running multiple copies of whatever algorithm verifies a location guess in parallel, again without trusted hardware.

The best that can be done for an offline system is to make the is_coordinate_close() function expensive to compute. Still a user can then either bring a powerful portable computer or connect to remote computing capacity to brute force the data set you provide. Additionally, increasing the cost of the function increases the power consumption of your app.

There are two options that get rid of this tradeoff:

  • cryptographic secrets at the locations (EG:QR codes)
  • DRM capable hardware (Phone as trusted third party)
  • Thanks, making is_coordinate_close expensive might be OK, but I guess the input being restricted to geographic coordinates makes brute-forcing it too easy. I was sort of hoping there might be some way of transforming the problem that I'd overlooked. – user786653 Oct 11 at 6:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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