84
We introduce Zero-Knowledge Location Privacy (ZKLP), enabling users to prove to third parties that they are within a specified geographical region while not disclosing their exact location. ZKLP supports varying levels of granularity, allowing for customization depending on the use case. To realize ZKLP, we introduce the first set of Zero-Knowledge Proof (ZKP) circuits that are fully compliant to the IEEE 754 standard for floating-point arithmetic.
Our results demonstrate that our floating point circuits amortize efficiently, requiring only $64$ constraints per multiplication for $2^{15}$ single-precision floating-point multiplications. We utilize our floating point implementation to realize the ZKLP paradigm. In comparison to a baseline, we find that our optimized implementation has $15.9 \times$ less constraints utilizing single precision floating-point values, and $12.2 \times$ less constraints when utilizing double precision floating-point values. We demonstrate the practicability of ZKLP by building a protocol for privacy preserving peer-to-peer proximity testing - Alice can test if she is close to Bob by receiving a single message, without either party revealing any other information about their location. In such a configuration, Bob can create a proof of (non-)proximity in $0.26 s$, whereas Alice can verify her distance to about $470$ peers per second.
Imagine you want use Google Home to manage your home (questionable decision, but bare with me for a moment). Whenever you get near your house it should turn on your lights and starts up the heating so it’s nice and toasty when you get home. In order to do this you need to constantly send your GPS data to Google so they can track when you get near your home. Even if your location data is slightly obfuscated (e.g. by rounding to nearest mile or some hexagonal grid) they still get a rough estimate of your location. What this paper uses is a “thing” called SNARK. You can think of it (for this example) like a function that computes if you are near your house or not. You then execute that SNARK on your local device with your current exact GPS coordinates. The result of that operation is a signed result that is the proof if you are near your house or not, without actually telling where exactly you are. This proof can then be sent to Google without much fear of giving them any data they don’t need. The privacy aspect is especially interesting whenever you are not nearby: it will just tell Google that you are not at home, they have absolutely no idea if you are at work, or in Australia, or on the Moon or wherever else. I think the main thing they did in this paper is to define some operations on SNARKs that lets you compute proximity efficiently.
Wait, that’s a dumb design. On a (way) older phone I had some automation running and all that location triggering was done on the phone and only connected to my home when I was in fact near it. Google (or any role party) shouldn’t need to receive live geo location updates.
No, that’s what I’m suggesting. The proposed method in the paper makes no use of GPS, instead it’s some peer-to-peer network.