Zero-Knowledge Position Verification Achieves Privacy for Location Proofs at Any Time

Researchers are tackling the fundamental challenge of proving one’s location without revealing more information than necessary. Uma Girish, Greg Gluch, and Shafi Goldwasser, alongside colleagues from Columbia and UC Berkeley , including Tal Malkin, Leo Orshansky, and Henry Yuen , present a new framework for ‘zero-knowledge position verification’. Their work extends existing ‘position verification’ protocols, allowing individuals to convincingly demonstrate statements about their whereabouts at specific times, such as proving they weren’t at a certain place, all while maintaining complete privacy regarding their broader movements. This breakthrough, built upon ‘position commitments’ , a novel primitive for privately recording location , represents a significant step towards secure and privacy-preserving location-based services and technologies.

Their work extends existing ‘position verification’ protocols, allowing individuals to convincingly demonstrate statements about their whereabouts at specific times, such as proving they weren’t at a certain place, all while maintaining complete privacy regarding their broader movements. This breakthrough addresses a critical gap in existing position verification schemes, which traditionally require full disclosure of location data, potentially compromising privacy. Central to this innovation is the ability to prove sophisticated statements about location over time, moving beyond simple “I am at location L” assertions. Experiments demonstrate the protocol’s capacity to verify claims about past locations, opening possibilities for applications requiring temporal proof of presence or absence.

This work opens the door to a new paradigm of privacy-preserving location-based services and cryptographic protocols. This research directly addresses vulnerabilities highlighted in recent investigations, such as the inadvertent exposure of sensitive movement data through fitness-tracking apps like Strava. A protocol capable of proving statements like “Alice completed a run with a particular shape within a given time,” while concealing the run’s geographic location, would directly mitigate such risks. Furthermore, the team envisions applications in critical areas like verifying compliance with international treaties, for example, confirming the absence of nuclear weapons in restricted zones, and enabling private alibis without revealing actual location. The construction of position commitments allows for a prover to establish their position at a specific time without immediate disclosure of location.,.

Position Commitments for Zero-Knowledge Location Proofs offer strong

Researchers engineered position commitments to serve as foundational building blocks for zero-knowledge proofs, mirroring classical techniques employing commitments for NP predicates. The study pioneered a method where a prover, after interacting with verifiers to establish the position commitment, a classical string derived from nice position verification protocols, engages in a zero-knowledge proof regarding a statement about the concealed position. Specifically, the prover demonstrates possession of an opening to the commitment revealing a point within a defined region, leveraging standard zero-knowledge proof systems for NP languages. This approach achieves position security against dishonest provers by combining the soundness of the proof with the statistical binding property of the position commitments.

The team constructed position commitments applicable to a broad class of position verification protocols, termed ‘nice protocols’, encompassing much of the existing literature. However, acknowledging a trade-off, scientists optimised the protocol by focusing on cases with fully classical messages and independently generated verifier challenges, substantially reducing computational demands. Experiments employ this optimisation to enhance the efficiency of the overall system, demonstrating a practical improvement in performance. Furthermore, the study investigated quantum position verification (QPV), acknowledging its recent growth and the challenges of achieving security with limited quantum entanglement. Researchers highlighted that unconditionally secure position verification remains impossible even in the quantum realm, citing the vulnerability to attacks utilising exponential entanglement, as demonstrated by previous work on instantaneous nonlocal quantum computation. This research views its contribution as a first step towards combining privacy and proofs of position, identifying avenues for future work including exploring the honest-verifier assumption and addressing potential information leakage through directional messaging.

Zero-knowledge proofs extend to complex spatiotemporal claims

Experiments demonstrate that quantum position verification schemes are vulnerable to spoofers employing exponential amounts of quantum entanglement, as highlighted by prior work [Vai03, BK11,0.1 formally states that a secure position verification protocol satisfying these properties can be upgraded to a zero-knowledge protocol for any finite set of spacetime positions.