⚛️ quantum physics

Private Proofs of When and Where

This paper introduces and constructs zero-knowledge position verification protocols that allow entities to privately prove sophisticated statements about their past and present locations using standard position verification and post-quantum one-way functions, centered around a new primitive called position commitments.

Original authors: Uma Girish, Greg Gluch, Shafi Goldwasser, Tal Malkin, Leo Orshansky, Henry Yuen

Published 2026-02-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Uma Girish, Greg Gluch, Shafi Goldwasser, Tal Malkin, Leo Orshansky, Henry Yuen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove to a group of friends that you are currently standing in the middle of a park, without them needing to see you or know exactly where in the park you are.

In the world of cryptography, this is called Position Verification. Usually, to prove you are somewhere, you have to send a signal back and forth with people at the edges of the park. Because light (and radio waves) takes time to travel, they can calculate exactly where you are based on how fast your reply arrives.

However, there's a big problem: Privacy.
If you prove you are in the park, you've just revealed your location. What if you want to prove something more specific, like "I was not near the crime scene yesterday," or "I stayed within the borders of this country," without revealing your actual coordinates?

This paper introduces a new magic trick called Zero-Knowledge Position Verification. It allows you to prove a statement about your location (like "I was here") without revealing the actual "where" or "when," and without giving away any other details about your life.

Here is how the authors solved this puzzle, explained through simple analogies.

1. The Problem: The "Spy" vs. The "Guard"

In the past, scientists tried to prove location using classical physics (like radio signals). But clever spies (adversaries) figured out they could fake it. If two spies stood at different spots and shared information instantly, they could trick the guards into thinking a single person was in the middle of the park.

To fix this, we use Quantum Physics. Quantum particles have a special rule: you can't copy them perfectly (the "No-Cloning Theorem"). This makes it much harder for spies to fake their location. But even with quantum physics, if you prove you are at a specific spot, you lose your privacy.

2. The Solution: The "Time-Traveling Sealed Envelope"

The authors invented a new tool called a Position Commitment. Think of this as a magical, time-traveling sealed envelope.

Here is how it works:

The Setup: You (the prover) are going to be at a specific spot at a specific time. You don't tell the guards where.
The Commitment: Instead of saying "I am here," you create a massive, encrypted "web" of signals. You send out thousands of tiny, encrypted messages to the guards, timed perfectly so they arrive exactly when they would if you were at any possible spot in the allowed area.
- Analogy: Imagine you are in a dark room with 100 microphones. You whisper a secret code into a specific microphone. But to hide which one you used, you have a robot whisper the same code into all 100 microphones at the exact same time, but encrypted. The guards hear the whispers, but they can't tell which one is the "real" one because they are all encrypted.
The Binding: You lock the key to these messages in a digital safe (a cryptographic commitment) and hand the safe to the guards. You cannot change the key later.
The Reveal: Later, you decide to prove a statement. You open the safe, give them the key, and say, "The real message was for the spot at the North Gate."
The Check: The guards unlock the specific message for the North Gate. If it matches the timing and the quantum rules, they know you were actually there. If you try to lie and say you were at the South Gate, the message won't match, and they will catch you.

3. The "Zero-Knowledge" Magic

The cool part is the Zero-Knowledge aspect.
While the guards are waiting for you to open the safe, they see a constant stream of encrypted noise. Because of the laws of quantum mechanics and encryption, this stream of noise looks exactly the same whether you are at the North Gate, the South Gate, or the East Gate.

The Analogy: Imagine a magician who has a deck of cards. He shuffles them and deals them face down. He asks you to pick a card. He doesn't tell you which card you picked, but he proves he didn't cheat. In this paper, the "deck of cards" is the stream of encrypted messages. The guards see the shuffle, but they can't tell which card (location) you actually picked until you reveal it. Even then, they only learn that you were at the North Gate, not how you got there or what you did before.

4. Why This Matters

This technology solves real-world privacy headaches:

The "Strava" Problem: Remember when fitness apps accidentally revealed the secret bases of military generals because they tracked their jogging routes? With this system, a general could prove, "I ran a 5-mile loop," without the app ever knowing where the loop was.
Nuclear Treaties: A country could prove, "Our nuclear weapon is inside our borders," without revealing the secret base's coordinates to the world.
Alibis: You could prove to a judge, "I was not at the crime scene at 2:00 PM," without having to reveal that you were actually at a coffee shop three blocks away.

5. The Catch (The "Malicious" Problem)

The paper admits one weakness. This system works perfectly if the people checking your location (the verifiers) are honest but curious. But what if they are evil and want to trick you?

The "Flashlight" Attack: If the verifiers are malicious, they could shine a "flashlight" (send a directional signal) only at one specific spot. If you respond, they know you are there. If you don't, they know you aren't.
The Fix: The authors suggest that if the verifiers are limited to only sending "broadcast" signals (like a radio station that everyone hears) rather than "flashlights" (lasers pointed at one person), the system remains secure. This is like saying, "We can't prove you are in the park if you are the only one listening to the radio, but if everyone is listening, we can't trick you."

Summary

This paper takes the complex idea of "proving where you are" and adds a layer of "proving it without showing your face." By using Quantum Physics (to stop faking) and Mathematical Locks (to hide the details), they created a system where you can prove your location history is honest, without ever giving up your privacy. It's like proving you have a ticket to the movie without showing your ID or telling the theater which seat you sat in.

1. Problem Statement

Position Verification (PV) is a cryptographic protocol where a prover attempts to convince a set of verifiers of their physical location $L$ at a specific time $t$ . While secure PV is impossible in a purely classical setting (due to colluding adversaries spoofing signals), it is feasible in the Quantum Position Verification (QPV) model, leveraging principles like the no-cloning theorem and the speed of light constraint.

However, standard QPV protocols suffer from a fundamental privacy flaw: to prove "I am at location $L$ ," the prover must reveal their exact coordinates. In many real-world scenarios, users need to prove statements about their location without revealing the location itself. Examples include:

Proving one was not near a crime scene (an alibi) without revealing where they actually were.
Proving compliance with treaties (e.g., "No nuclear weapons in Antarctica") without revealing the exact location of the device.
Privacy-preserving fitness tracking (proving a run shape without revealing the route).

The central question addressed by the paper is: Can we construct Zero-Knowledge Position Verification (ZK-PV) protocols? That is, can a prover prove a statement about their spacetime position (e.g., "I was in region $R$ ") without revealing any information about their specific coordinates within $R$ ?

2. Methodology and Core Primitive

The authors introduce a new cryptographic primitive called Position Commitment and use it to construct ZK-PV protocols.

A. Position Commitment

A Position Commitment allows a prover to commit to a specific spacetime point $(L, t)$ without revealing it immediately. Later, the prover can "open" the commitment to reveal $(L, t)$ , and the verifiers can verify that the prover was indeed at that location at that time.

Hiding: During the commit phase, the verifiers learn nothing about the specific point chosen.
Binding: The prover cannot change the committed point later. Crucially, the binding property is positional: the prover must have physically occupied the space-time point to open the commitment successfully.

Construction of Position Commitment:
The construction relies on two assumptions:

Post-Quantum One-Way Functions (OWF): Used for encryption and classical bit commitments.
"Nice" Singleton Position Verification Protocols: A class of existing QPV protocols (e.g., $f$ $f$ -BB84) that are:
- One-round (Verifiers send, Prover responds immediately).
- Classical response (Prover sends a classical bit/string).
- Capable of verifying any point within the convex hull of the verifiers.

The Protocol (Encrypt-Then-Verify):

Setup: The prover generates a secret key $sk$ and commits to it using a classical commitment scheme.
Commit Phase:
- Verifiers broadcast challenges for every possible point in a target spacetime region $S$ simultaneously.
- The honest prover, located at $(L^*, t^*) \in S$ , receives the specific challenge for their true location.
- The prover computes the correct response for $(L^*, t^*)$ and encrypts it with $sk$.
- For all other points in $S$ , the prover sends "dummy" encrypted messages (e.g., encryption of $\perp$ ) timed to arrive exactly when the verifiers expect a response for those fake locations.
- This creates a transcript where verifiers receive a stream of encrypted messages consistent with any point in $S$ , making the prover's true location indistinguishable.
Reveal Phase:
- The prover reveals $sk$ and the claimed location $(L^*, t^*)$ .
- Verifiers decrypt the message corresponding to $(L^*, t^*)$ and verify it against the original challenge. They also check that the commitment to $sk$ is valid.
- Due to the Statistical Position Binding property, a cheating prover cannot generate a valid commitment that opens to a location they did not physically occupy, even if they have bounded entanglement.

B. From Position Commitment to Zero-Knowledge

Once a prover has created a Position Commitment $\rho$ for a hidden location, they can prove statements about that location using standard Zero-Knowledge Proofs (ZK) for NP languages.

The statement to be proven is: "I possess an opening to commitment $\rho$ such that the revealed location belongs to region $R$ ."
Since the underlying commitment is computationally hiding (due to OWF) and the ZK proof reveals nothing beyond the validity of the statement, the resulting protocol is Zero-Knowledge.

3. Key Contributions

Formalization of ZK Position Verification: The authors define ZK-PV using a simulation-based security definition, ensuring that the verifiers' view can be simulated without knowing the prover's exact location within the allowed region.
Introduction of Position Commitment: They define and construct this new primitive, which bridges the gap between physical location constraints and cryptographic commitments.
Main Theorem (Theorem 1.1): They prove that assuming Post-Quantum One-Way Functions and the existence of "nice" singleton QPV protocols (secure against adversaries with bounded entanglement $E$ $E$ ), one can construct a ZK-PV protocol for any finite spacetime region $R$ $R$ .
- The resulting protocol is secure against adversaries sharing $E/2$ entangled qubits.
- It achieves Honest-Verifier Computational Zero-Knowledge.
Optimization (Protocol 2): They propose an optimized construction for protocols where verifier messages are classical and broadcast (e.g., [LLQ22]). This reduces the computational load from exponential in the size of the region $|S|$ to polynomial, making the scheme more practical.

4. Results and Security Analysis

Completeness: Honest provers are accepted with high probability.
Soundness (Position Security): Dishonest provers (spoofers) who do not occupy the claimed location cannot pass the verification with more than negligible probability, provided they share limited entanglement. The security reduction relies on the hardness of breaking the underlying QPV protocol and the binding property of the commitment.
Zero-Knowledge: The protocol is zero-knowledge against semi-honest verifiers (who follow the protocol but try to learn more from the transcript).
- Limitation: The paper notes that achieving ZK against malicious verifiers is difficult. Malicious verifiers can perform a "poke-around" attack by sending directional messages to specific zones and observing if the prover responds, thereby deducing the prover's location. The authors conjecture that if verifiers are restricted to broadcast-only messages (and provers can distinguish broadcast from directional), malicious-verifier ZK might be achievable.

5. Significance and Impact

Privacy in Geospatial Cryptography: This work solves a critical privacy gap in quantum cryptography. It enables the verification of physical properties (location) without compromising the sensitive data (exact coordinates) associated with them.
New Primitive: The concept of "Position Commitment" is a novel building block that may find applications beyond ZK-PV, such as creating private, auditable logs of movement (e.g., for legal alibis or compliance tracking).
Bridging Physics and Cryptography: The construction elegantly combines physical constraints (speed of light, unclonability) with standard cryptographic assumptions (OWF) to achieve a goal that is impossible with either approach alone.
Practical Applications: The paper highlights immediate use cases in:
- Legal: Private alibis.
- National Security: Verifying treaty compliance (e.g., nuclear non-proliferation) without revealing military secrets.
- Consumer Privacy: Secure fitness tracking and location-based services without data leakage.

In summary, the paper establishes that Zero-Knowledge Position Verification is theoretically possible under standard cryptographic assumptions and bounded quantum entanglement, providing a robust framework for privacy-preserving location proofs in the quantum era.