crypto-geofence

Is it possible for me to check if I'm inside a geofence, without revealing my location to the server, and without the server giving me the true geofence?

Video at DEF-CON Crypto & Privacy Village 2018: https://www.youtube.com/watch?v=ySl2ywGiFkw

What is homomorphic encryption?

Homomorphic encryption is a new technique where you can perform arithmetic operations on encrypted numbers. It's possible with a few different algorithms, including the factoring-based one used here (Paillier). In the future it might be better to use a quantum-resistent algorithm based on lattice cryptography.

If you send the encrypted numbers and a public key, another computer can perform arithmetic on the number and scalar values without seeing the actual values.

Applying it to Geofences

Encrypted coordinates and the public key are POSTed to the server

Originally I was hoping to find if you were in the box by testing this:

latitude_offset = (north - latitude) * (south-latitude)

The number would be negative for south < latitude < north, and positive in any other condition. It would also be difficult to find north and south by factoring the result. Unfortunately, multiplying encrypting numbers is not possible in the Paillier cryptosystem. I got this funny error:

Anyway, you can obfuscate offsets by multiplying by a random scalar instead:

north_offset = (north - latitude) * random()
south_offset = (south - latitude) * random()

One of the offsets should be positive and the other negative, but the random factor makes it difficult to figure out the true offset to the geofence. Combined with rate-limiting, this could make your fence exta-secret.

Going forward

I would like to:

• calculate geofences for more complex shapes, by breaking them into rectangles or triangles
• calculate distance, using a different cryptosystem which allows multiplication

Libraries used

Using Brian Thorne's homomorphicjs on the client, and Australia NICTA's Python-Paillier on the server

License

MIT license