💻 computer science

Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification

This paper introduces Search-Bound Proximity Proofs (SBPP), a framework that binds encrypted geographic search sessions to zero-knowledge proximity proofs via decomposed, auditable components to close the authorization provenance gap and enable forensic re-association without modifying the underlying ZKP circuit or incurring significant performance overhead.

Original authors: Yoshiyuki Ootani

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yoshiyuki Ootani

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 at a massive, high-tech treasure hunt. The game works in two steps:

The Search: You ask the game master, "Where are the hidden chests near me?" The game master gives you a list of possible locations.
The Unlock: To actually open a chest, you must prove you are standing right next to it without telling the game master your exact GPS coordinates (to protect your privacy). You use a special "magic spell" (a Zero-Knowledge Proof) to say, "I am definitely within 10 meters of this chest," and the chest opens.

The Problem: The "Lost Receipt" Gap

In current versions of this game, there is a sneaky flaw.

Imagine you ask for the list of chests (Step 1). The game master gives you a list. Then, you use your magic spell to open a chest (Step 2).

If the game master is "honest but curious" (they follow the rules but like to snoop), they might delete the record of which list they gave you after a few minutes to save space. Later, if an auditor asks, "Who opened this chest and why did they get permission?", the game master looks at the magic spell.

The problem: The magic spell only says, "I am near Chest #5." It doesn't say, "I got permission to look for Chest #5 during Session #99."

Because the spell doesn't mention the specific session, a sneaky player could:

Get a list of chests in Session #99.
Wait for Session #100 to start.
Use the same magic spell from Session #99 to open a chest in Session #100.

To the game master, it looks like a valid unlock. But to the auditor, it's a lie. The player is claiming they were authorized in Session #100, but they actually got their permission in Session #99. This is called the Authorization Provenance Gap. It's like showing a ticket from yesterday's concert to get into today's show, and the bouncer can't tell the difference because the ticket doesn't have the date on it.

The Solution: SBPP (Search-Bound Proximity Proofs)

The author, Yoshiyuki Ootani, proposes a new system called SBPP. Think of it as adding a unique, unbreakable "Session ID" stamp directly onto the magic spell itself.

Here is how SBPP works, using a simple analogy:

1. The Session Token (The "Time-Stamped Wristband")

When you ask for the list of chests, the game master gives you a unique, random wristband (a Nonce). This wristband is tied to that specific 5-minute session.

2. The List of Chests (The "Merkle Root")

The game master gives you a list of possible chests. Instead of just sending the list, they turn the list into a single, unique digital fingerprint (a Merkle Root). It's like taking a photo of the entire list and turning it into a single, unchangeable seal.

3. The Magic Spell (The "Proof")

Now, when you cast your magic spell to open a chest, you don't just say "I am near the chest." You say:

"I am near the chest, AND I am wearing wristband #99, AND I am looking at the list with fingerprint #ABC."

The game master checks three things:

Is the wristband real and valid?
Does the fingerprint match the list they generated for that wristband?
Is the magic spell valid?

If you try to use a spell from Session #99 in Session #100, the spell will be looking for Wristband #99, but the game master is holding Wristband #100. The spell fails immediately.

Why This Matters: The "Forensic Audit"

The coolest part of SBPP is what happens after the game is over.

Imagine the game master deletes all the wristbands and lists to save space. An auditor comes in later to check the records.

Old System: The auditor sees a magic spell and a receipt. They can't prove if the receipt matches the spell because the link was broken when the data was deleted.
SBPP System: The auditor sees the magic spell, which contains the "fingerprint" of the list and the "wristband ID." They also have a signed receipt from the game master confirming, "Yes, I gave Wristband #99 and List Fingerprint #ABC to this user."

Even without the original database, the auditor can mathematically prove that the spell must have come from that specific session. It's like finding a receipt that has the exact same serial number as the item you bought, proving you didn't swap it with a fake one later.

The "Secret Sauce": No Magic Changes Needed

Usually, to fix a security hole, you have to rewrite the entire magic spell (the computer code). That's expensive and risky.

The author's genius is that SBPP doesn't change the magic spell at all. It just changes what information is fed into the spell. It's like taking a standard lock and just changing the key you put in it to include a date stamp. The lock works exactly the same way, but now it's impossible to use the wrong key.

Summary in Plain English

The Problem: Current systems let hackers reuse old permissions for new sessions because the "proof" doesn't remember which session it came from.
The Fix: SBPP forces the proof to include a unique "session ID" and a "fingerprint of the search results" inside the proof itself.
The Result: Even if the server deletes its memory, an auditor can look at the proof years later and say, "This proof was definitely authorized in Session X, not Session Y."
The Benefit: It makes location-based apps (like geo-fenced media or secure access) much more secure and legally accountable, without slowing them down or requiring a total system overhaul.

It's essentially giving every digital key a unique serial number that is permanently etched into the lock, so no one can ever swap keys and get away with it.

1. Problem Statement: The Authorization Provenance Gap

The paper addresses a critical security gap in location-based systems (LBS) that combine encrypted geographic search with zero-knowledge proximity proofs (ZKPP).

The Workflow: Typically, a client first performs an encrypted search to discover nearby content (e.g., "geo-drops") and then generates a ZKPP to prove they are physically near a specific item to unlock it.
The Gap: In current deployments, these two phases are decoupled. The search session state is often purged after the query, and the resulting ZKPP contains no information linking it back to the specific search session that authorized it.
The Consequence: Under an "honest-but-curious" server model, this creates an Authorization Provenance Gap. Once session state is deleted, there is no forensic way to cryptographically attribute a valid proof to its originating search session.
The Attack: This allows for Audit Re-association Attacks. An adversary can intercept a valid proof generated in Session A, and re-associate it with the authorization token of Session B (provided the target content parameters are identical). This creates misleading audit records where access is attributed to the wrong session, breaking forensic accountability in compliance-heavy environments (e.g., geofenced media access).

2. Methodology: Search-Bound Proximity Proofs (SBPP)

The authors propose Search-Bound Proximity Proofs (SBPP), a protocol that binds the search session directly to the zero-knowledge proof without modifying the underlying ZK circuit.

Core Mechanism

SBPP achieves binding by embedding session-specific and result-set-specific data into the public inputs of the ZK proof (specifically, the challenge digest). The protocol involves three main components:

Session Nonce ( $N$ ): A cryptographically random value generated by the server at the start of a search session.
Merkle Root ($root(R)$): A hash representing the set of candidate drops returned by the search.
Signed Receipt ( $\rho$ ): A server-signed artifact containing the session details, issued after the search but before the proof generation.

Protocol Flow

Session Initiation: The server generates a session ID ( $S$ ) and a random nonce ( $N$ ).
Encrypted Search: The client sends encrypted search tokens. The server returns a list of candidate drop IDs and computes a Merkle root over this result set.
Challenge Digest Construction: The client constructs a challenge digest ($cd$) by hashing a length-prefixed structure containing:
- Protocol version and Drop ID.
- Policy version and Epoch.
- Session Nonce ( $N$ ).
- Merkle Root ($root(R)$).
Proof Generation: The client generates a Groth16 proximity proof where $cd$ is a public input. The client also provides a Merkle membership proof for the specific drop they wish to unlock.
Verification: The server verifies the session is valid, checks that the proof's public input matches the stored nonce and root, and validates the Merkle path.
Offline Audit: To enable post-hoc auditing after session state is purged, the server provides a signed receipt. An auditor can re-verify the proof by checking the receipt signature, recomputing the digest from the receipt fields, and validating the Merkle path against the committed root.

3. Key Contributions

C1: Search-Authorized Proof (SAP) Security Notion: The paper formally defines SAP, establishing three security properties:
- P1 (Authorization Binding): A proof from Session A cannot be accepted for Session B.
- P2 (Result-Set Soundness): A proof cannot be accepted for a drop not in the authorized result set.
- P3 (Authorization Provenance): An adversary cannot produce a valid audit record that misattributes a proof to a different session context.
C2: Audit Re-association Attack: The authors demonstrate that "proof-external" authorization (where tokens are checked alongside the proof but not inside it) is vulnerable to re-association attacks when drop parameters recur across sessions.
C3: SBPP Protocol Design: A practical realization of SAP that requires no modification to the ZK circuit. It decomposes the binding into three auditable components (Nonce, Merkle Root, Receipt), enabling property-level fault isolation (e.g., distinguishing between a session rebinding attack and a result-set tampering attack).
C4: Comprehensive Evaluation: Extensive testing on synthetic data and real-world OpenStreetMap data (110k POIs) across nine protocol variants.

4. Results and Evaluation

Security:
- SBPP successfully blocks all six defined attack classes, including the critical Audit Re-association (A4b) and Cross-Session Substitution (A1/A2).
- Compared to "proof-external" baselines (V5–V7), which fail A4b, SBPP (and the internalized token hash baseline V8) provides cryptographic binding.
- SBPP offers superior fault isolation compared to V8. If an audit fails, SBPP can pinpoint the exact cause (nonce mismatch, Merkle failure, or signature failure), whereas V8 only reports a generic "hash mismatch."
Performance Overhead:
- Protocol Path: SBPP adds a negligible 27 µs (median) overhead over the baseline encrypted search (GridSE), representing a 7% increase.
- End-to-End: The total overhead is <0.03% of the total unlock time (dominated by the 42–125 ms ZK proof generation).
- Scalability: The Merkle root approach allows the server to maintain O(1) state per session (storing only the root hash) rather than the full result set, significantly reducing memory usage compared to stateful verification.
Mobile Performance:
- Proof generation on mobile devices (iPhone 16 Pro, POCO X7 Pro) ranges from 42 ms to 125 ms (warm start).
- Verification is extremely fast (9–26 ms).

5. Significance and Impact

Forensic Accountability: SBPP solves a previously unaddressed problem in privacy-preserving LBS: the inability to audit who authorized a specific access event after the fact. This is crucial for compliance in regulated industries (e.g., age-restricted content, geofenced advertising).
Circuit Agnosticism: By binding the session via public inputs (digest) rather than modifying the circuit constraints, SBPP is easily deployable with existing ZK infrastructure (e.g., Groth16 on BN128).
Design Principle: The paper establishes that session-distinguishing information must be committed inside the proof's public inputs to prevent re-association. External checks or log correlation are insufficient for cryptographic provenance.
Limitations: The system assumes an "honest-but-curious" server. It does not prevent a malicious server from omitting candidates or signing biased roots (fairness/completeness issues), nor does it prevent client-side location spoofing. These require orthogonal solutions like verifiable query processing or multi-sensor fusion.

In summary, SBPP provides a lightweight, cryptographically sound method to bridge the gap between encrypted search and zero-knowledge verification, ensuring that every proximity proof can be forensically traced back to its specific authorization session without compromising privacy or performance.