1
Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification
arXiv:2604.03902v1 [cs.CR] 5 Apr 2026
Yoshiyuki Ootani
Abstract—Location-based systems that combine encrypted geographic search with zero-knowledge proximity proofs typically treat the two phases as independent. Under an honest-but-curious server, this leaves an authorization provenance gap: once session state is purged, no forensic procedure can attribute a proof to its originating search session, because the proof’s public inputs encode no session-identifying information. We formalize this gap as the search-authorized proof (SAP) security notion and show via a concrete audit re-association attack that proof-external mechanisms (where authorization evidence remains outside the proof) cannot prevent forensic misattribution when the same drop parameters recur across sessions. SearchBound Proximity Proofs (SBPP) realize the SAP requirements without modifying the ZKP circuit: session nonce, Merkleroot result-set commitment, and signed receipt are decomposed into independently auditable components, enabling property-level fault isolation in offline audit. Experiments on synthetic and realworld data (110 776 OpenStreetMap POIs) show sub-millisecond absolute overhead on a 125 ms Groth16 baseline. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. Index Terms—searchable encryption, zero-knowledge proofs, authorization provenance, forensic audit, geographic access control
I. I NTRODUCTION EO-CONTENT systems—applications that bind digital content to physical locations—are a growing class of location-based services (LBS). Examples include locationlocked media (“geo-drops”), geofenced access control, and place-based augmented reality. These systems share a common two-phase workflow: 1) Discovery. The client queries the server to find nearby content (e.g., “what drops are within 1 km of me?”). 2) Verification. The client proves proximity to a specific piece of content to unlock it (e.g., via GPS check, zeroknowledge proof, or visual verification). In current deployments, these phases are decoupled: discovery uses plaintext geohash queries that reveal the user’s approximate location to the server, while verification uses a separate cryptographic mechanism (such as a Groth16 proximity proof) that reveals nothing about the user’s exact coordinates. This creates what we call the search-verify gap— more precisely, an authorization provenance gap: once session
G
Yoshiyuki Ootani is an independent researcher based in Japan (e-mail: [email protected]).
state is purged, no audit record can forensically attribute a proof to its originating search session, because the proof’s public inputs encode no session-identifying information. Prior work has addressed parts of this problem in isolation. Encrypted geographic search systems [1]–[3] replace plaintext geospatial queries with encrypted or tokenized search mechanisms that hide the user’s coordinates from the server. Pairing-based zero-knowledge arguments such as Groth16 [4], when instantiated as a proximity circuit [5], allow the user to prove they are within a radius R of a target without revealing their exact location. However, to our knowledge, prior work has not studied binding encrypted geographic discovery to zero-knowledge proximity verification via the proof transcript, leaving the authorization provenance gap open. A natural first attempt is to check a session nonce alongside the proof at the application layer. We show (§VII) that this does not suffice: because the nonce is not committed inside the proof, the proof can be separated from its session context and re-associated with a different session (A1/A2). Stronger alternatives such as signed authorization tokens or MAC-based result binding also fall short: because their proofs remain session-agnostic, an adversary can re-associate a valid proof with a different session’s token, forging a misleading audit record (§V-C). Under an honest-but-curious server, this matters for forensic accountability: in geo-content platforms subject to compliance audit (e.g., geofenced access control, locationgated media), post-hoc review must attribute each proof to its originating authorization. If an adversary swaps a proof’s authorization token, the audit record misattributes the access to a different session. Log-level correlation is heuristic and defeatable; only cryptographic commitment in the proof’s public inputs makes misattribution detectable. We formalize this as the SAP security notion (§V) and present SBPP as a practical decomposition: a session nonce (P1), a Merkle-root digest (P2), and a signed receipt (P3). Any internalized-token design with equivalent content (V8 in our comparison) achieves the same security level; SBPP’s advantage is property-level fault isolation and format-independent audit (§VIII). SBPP certifies provenance of the issued context, not search correctness (§VIII). Contributions. C1 We define the search-authorized proof (SAP) security notion (P1–P3), identify six attack classes including forensic audit misattribution (A4b), and establish design
2
requirements for the committed content required by each property (§III, §V). C2 We exhibit an audit re-association attack showing that proof-external authorization is vulnerable to P3 violation whenever the same drop parameters recur across sessions—a common scenario within epoch windows (§V-C). C3 We present SBPP, a deployable realization of the SAP requirements that achieves property-level fault isolation (each failure mode maps to a distinct component), O(1) compact verifier state, and no circuit modification (§IV). C4 We evaluate on synthetic and real-world (OSM) distributions, nine protocol variants, and two mobile devices (§VII). Prior artifact and novel contributions. The Zairn platform [5] provides three pre-existing components used in this work: (i) a GridSE-style encrypted search module, (ii) a Groth16 proximity-proof circuit (474 constraints), and (iii) a proof-level context binding mechanism that embeds drop ID, policy version, and epoch in the challenge digest to prevent cross-drop transfer (A3). New to this paper: the SAP security notion (P1–P3) and design requirements; the audit re-association attack and proof-external separation; the SBPP practical decomposition (Core/Full); and the nine-variant evaluation including OSM real-world data. The prior artifact [5] provides implementation components (SSE module, Groth16 circuit, context binding); the security notion, separation argument, and full evaluation are introduced here.
II. BACKGROUND A. Searchable Symmetric Encryption Searchable symmetric encryption (SSE) enables keyword search over encrypted data [6], [7]. In the geographic setting, GridSE [1] encodes locations as geohash strings and generates HMAC-based index tokens at multiple precision levels. A searcher generates tokens for their location and its neighbors; the server performs set intersection over opaque tokens without learning coordinates. The standard SSE leakage profile includes: (i) search pattern (whether two queries are identical), (ii) access pattern (which documents match), and (iii) volume pattern (how many documents match) [8]. Geographic SSE inherits all three.
B. Zero-Knowledge Proximity Proofs A zero-knowledge proximity proof (ZKPP) allows a prover to convince a verifier that they are within radius R of a target location (tlat , tlon ) without revealing their exact coordinates [4]. In Zairn’s implementation [5], the prover generates a Groth16 proof over a Circom circuit (474 constraints on BN128) with public inputs including the target coordinates, radius, and a challenge digest—a hash that binds the proof to a specific application context (drop ID, policy version, epoch).
C. Context Binding The Zairn platform [5] implements context binding for ZKPPs: embedding application-level identifiers (drop ID, policy version, epoch) in the proof’s public inputs to prevent cross-drop proof transfer. The challenge digest is computed as: contextDigest = H(LP(D, pv, e)) (1) where LP(·) denotes length-prefixed canonical encoding and H is SHA-256 reduced modulo the BN128 scalar field order q. SBPP extends this by adding the search session nonce N to the encoding (§IV-C). Crucially, the prior proof-level binding [5] addresses only proof-level binding (which drop a proof is for) and does not consider the discovery phase at all. SBPP addresses protocol-level binding (which search session a proof belongs to), a complementary and non-overlapping concern. III. P ROBLEM S TATEMENT AND T HREAT M ODEL A. System Model We consider a geo-content system with three roles: • Drop creator: Publishes location-bound content with encrypted index tokens and a ZKP verification key. • Client (searcher/prover): Searches for nearby drops and generates proximity proofs to unlock them. Holds a shared search key k for HMAC token generation (provisioned per content-access tier; key distribution is orthogonal to SBPP). • Server: Stores encrypted index tokens and drop metadata. Performs token matching and proof verification. B. Adversary Model We consider two adversary types: Privacy adversary (honest-but-curious server). The server follows the protocol correctly but attempts to learn the client’s location from observed messages—search tokens, access patterns, volume patterns, and proof submission timing [8]. This is the standard SSE adversary model [8], [9]. Integrity adversary (active client / network attacker). An adversary who can intercept, replay, substitute, or reassociate protocol messages. This adversary attempts crosssession proof substitution (A1), re-association (A2), result-set escape (A4), or delayed replay (A5). Cross-drop transfer (A3) is handled by the underlying context binding [5]. SBPP primarily targets the integrity adversary under an HBC server. A malicious server can omit candidates, sign biased roots, or refuse sessions; SBPP does not guarantee search completeness or fairness (see §VIII). Per-query SSE leakage is unchanged from GridSE (§V). C. The Search-Verify Gap Definition 1 (Authorization Provenance Gap). A geo-content protocol has an authorization provenance gap if, after serverside session state is purged, no forensic procedure can cryptographically attribute a proof to the search session that authorized it—i.e., the proof’s committed public inputs encode no session-identifying information.
3
Client
3) Client generates encrypted search tokens T = {HMAC(k, gridse:index:p:gi )} for center geohash g0 and neighbors g1 , . . . , g8 at precision p selected for the search radius. 4) Client sends T to the server. 5) Server performs set intersection against stored index tokens and returns matching drop IDs with metadata. 6) Server builds a binary Merkle tree over sorted candidate IDs {D1 , . . . , Dk } and stores only the Merkle root root(R) in the session record. 7) Client selects a drop D to unlock. 8) Client computes the SBPP challenge digest:
Server initSession()
1 S, N, texp 2
3
T ← HMAC(k, “gridse:p:gh”) T (opaque tokens)
4 candidate drop IDs 5 select drop D 6–7 cd ← H(LP(. . . , N, root)) generate π + Merkle path
cd = H(LP(SBPP-v1, D, pv, e, N, root(R)))
π, public signals, S 8
grant / deny
verify π check N = NS 10
9
Fig. 1. SBPP protocol. After token matching (step 5), the server computes a Merkle root over the result set (step 6). The client embeds both N and the root in the ZKP challenge digest (step 8) and submits a Merkle membership proof for the selected drop. Search tokens (step 3) do not contain N .
D. Attack Classes The authorization provenance gap enables the following attack classes: A1: Cross-session proof substitution. A proof generated in session S1 is submitted in S2 . Without proof-level session binding, the server cannot detect this from the proof transcript alone. A2: Cross-session re-association. An attacker intercepts a legitimate proof and submits it under a different session. A3: Cross-drop transfer. A proof for drop D1 is submitted for D2 . Prevented by context binding [5] (drop ID in digest). A4a: Result-set escape (online). A proof for a drop D ∈ /R is submitted. The deployed verifier catches this via an explicit membership check D ∈ R, but this requires the server to retain R in session state. A4b: Result-set escape (audit). After server-side R is purged, can an auditor verify from the stored audit record that the proof was authorized for a drop in the result set? Without a committed root in pub and authenticated openings, no. A5: Delayed proof replay. A client caches search results, waits, then submits a proof. Session TTL and consumption mitigate this. IV. SBPP P ROTOCOL A. Protocol Overview Fig. 1 shows the SBPP message sequence. The protocol proceeds as follows: 1) Client requests a search session. 2) Server generates a cryptographically random nonce N , session ID S, and expiry time texp . Stores (S, N, texp ).
(2)
and generates a Groth16 proximity proof π with cd as a public input (pub[7]). 9) Client sends π, public signals, session ID S, and a Merkle membership proof for D to the server. 10) Server verifies: (a) S is a valid, non-expired session with nonce N and root root(R); (b) the proof’s challenge digest matches Eq. 2; (c) the Merkle membership proof for D is valid against root(R); (d) the Groth16 proof π is valid. 11) Server returns grant (and consumes the session) or deny. Unless otherwise noted, the steps above describe Full SBPP in compact-online mode, where the verifier stores only a Merkle root and checks a membership witness. Core SBPP is obtained by omitting root(R) from the challenge digest, omitting the Merkle witness, and retaining R server-side for the explicit online membership check (V4a). B. Session Management Sessions are server-side state with three properties: • Uniqueness: Nonce N is 256 bits of cryptographic randomness (collision probability < 2−128 after 264 sessions). • Expiry: Default TTL of 5 minutes. Expired sessions reject all operations. • Consumption: A session is consumed (deleted) after one successful proof verification. This prevents proof replay within the same session. Server-side state depends on the verifier mode. In Core/stateful mode, the server stores (N, texp , R) and enforces online authorization via D ∈ R; state is O(|R|) per session. In Full/compact mode, the server stores (N, texp , root(R))—a single hash value regardless of |R|; state is O(1) per session. In both modes, total active sessions are bounded by the concurrent user count (5-minute TTL, one-time consumption). C. Search-Proof Binding The binding between search and verification is achieved through the nonce N : • The search phase operates within session S associated with nonce N . • The proof phase includes N in the challenge digest (Eq. 2), which becomes a public input to the Groth16 circuit.
4
•
The server verifies that the proof’s challenge digest matches the nonce stored for session S.
Because the challenge digest is a SHA-256 hash over length-prefixed fields including N , changing N changes the digest with overwhelming probability (collision resistance). The Groth16 proof commits to the digest as a public input, so it cannot be modified post-generation without invalidating the proof (soundness of Groth16).
D. Digest-Based Binding The existing circuit [5] accepts a challenge digest as public input pub[7] but does not recompute it internally. The authorization context (N, root, D, pv, e) is bound to the proof through a commitment chain: (1) the prover computes cd = H(LP(. . .)) over the full authorization context and supplies it as pub[7]; (2) Groth16 soundness ensures π is valid only for the committed pub[7]; (3) the verifier independently recomputes H(LP(. . .)) from its own session record and checks equality with pub[7]; (4) SHA-256 collision resistance and LP injectivity ensure that equality implies agreement on N , root, D, pv, and e. Thus, the authorization context is instancebound to the proof via pub[7]: the verifier independently recomputes the digest and checks equality, so any context mismatch is detected without circuit-internal processing. This preserves: No new trusted setup or verification key. Circuit constraints unchanged (474). • Backward compatibility with non-SBPP flows. • •
A domain separator SBPP-v1 as the first LP field prevents downgrade attacks.
E. Result-Set Binding Session binding (Eq. 2) ties the proof to a session but not to the specific drops returned in that session. Full SBPP closes this gap by committing a Merkle root [10] of the authorized result set inside the challenge digest (and thus inside pub[7]). The server builds a binary Merkle tree over sorted candidate IDs and stores only the root root(R). The client recomputes the tree locally and embeds the root in Eq. 2. When unlocking drop D, the client also submits a Merkle membership proof. This binds the proof to (i) session (N ), (ii) drop (D), and (iii) result set (root(R)). Forging requires breaking Merkle or Groth16 security.
G. Receipt-Backed Offline Audit To satisfy P3 after session state is purged, the server issues a signed session receipt ρ = Signsrv (S, N, texp , root(R), mode, pv, e) after the result set and Merkle root are computed. The audit log retains (ρ, D, merklePath, pub, π), where π is the full Groth16 proof (∼724 B)—retaining π (not only its hash) is necessary for independent re-verification. An auditor replays authorization via four checks: (i) server signature on ρ; (ii) recomputation of cdfull from receipt fields; (iii) Merkle membership of D; (iv) Groth16 proof verification. The proof’s pub[7] commits the authorization context; ρ and merklePath serve as authenticated openings that an auditor checks against that instance binding, yielding authorization provenance (P3) independent of mutable session state. The audit log may be held by the server operator or an independent compliance party; the auditor needs only the server’s public signing key—no session state, MAC secrets, or token format knowledge. V. S ECURITY A NALYSIS A. Search-Authorized Proofs A search-authorized proof scheme consists of five algorithms: λ • Issue(1 ) → (S, N, texp ): server creates a session with random nonce. • Search(S, T ) → (R, root(R), ρ): server matches tokens, builds Merkle tree, signs receipt. • Prove(D, N, root, w) → (π, pub): client generates ZKP with cd in pub[7]. • Verify(S, π, pub, D, merklePath) → {0, 1}: server checks session, digest, Merkle witness, and proof. • Audit(π, pub, D, merklePath, ρ) → {0, 1}: offline reverification using receipt signature, digest recomputation, Merkle membership, and Groth16 verification—no live session state. We define three security properties. P1 and P2 are binding/soundness requirements; P3 captures whether an adversary can produce a misleading audit record. Definition 2 (Search-Authorized Proof). Let Π be a NIZK proof system with public inputs and Q a search protocol that returns a candidate set R within a session S. A searchauthorized proof (SAP) scheme for (Π, Q) satisfies: P1 (Authorization binding). A valid proof for drop D under session S cannot be accepted under any S ′ ̸= S.
F. Verifier Modes
P2 (Result-set soundness). A valid proof for D ∈ / RS cannot be accepted under S.
Full SBPP supports three modes: (1) Stateful online: server stores R, checks D ∈ R directly (O(|R|) state). (2) Compact online: server stores only the Merkle root (O(1) state); client submits a membership witness. (3) Offline audit: after state is purged, an auditor re-verifies from τaudit = (π, pub, D, merklePath, ρ)—the committed pub[7] plus authenticated openings. Core SBPP supports (1) only; Full supports all three.
P3 (Authorization provenance). Consider an adversary A that interacts with oracles OIssue , OSearch , OProve (obtaining honest session transcripts and proofs), and then outputs a ∗ candidate audit record τaudit = (π ∗ , pub∗ , D∗ , mp ∗ , ρ∗ ). A ∗ wins if Audit(τaudit ) = 1 but π ∗ was generated by OProve under a different authorization context (N ′ , root ′ ) from the one claimed by ρ∗ —i.e., N ′ ̸= Nρ∗ or root ′ ̸= root ρ∗ . P3 requires Pr[A wins] ≤ negl(λ).
5
We distinguish the proof transcript τ = (π, pub) from the audit transcript τaudit , which additionally includes the Merkle witness and signed receipt. SBPP instantiates this definition: Core satisfies P1, Full satisfies P1+P2, and Full with signed receipts satisfies P1+P2+P3. Before showing how, we first establish what must be committed—a design requirement that constrains any SAP scheme, not just SBPP. B. Necessity of Committed Content Observation 1 (Formal Requirements). For any SAP scheme built over a sound NIZK: • P1 requires session-distinguishing pub. If pub(S1 , D) = pub(S2 , D) for S1 ̸= S2 with the same (D, pv, e), then π valid under S1 is also valid under S2 , violating P1. • P3 requires server authentication of committed values. pub is client-supplied; without an authenticated artifact (receipt), a client can fabricate (N, root) and pass audit. Remark (Design Rationale for P2). P2 under compact verification (o(n) verifier state) strongly suggests a result-set commitment in pub. With 2n possible result sets and o(n) bits of state, the verifier cannot distinguish all membership queries from state alone (pigeonhole). A commitment in pub checked via a witness is the standard approach; we state this as a design rationale rather than a formal impossibility. Justification of Observation 1. P1: By NIZK soundness, V (pub, π) is deterministic. If pub is session-independent, any π valid under S1 is accepted under S2 —violating P1. P3: pub is prover-supplied. Without server authentication, the prover can fabricate (N, root) and produce a valid proof and Merkle witness for any self-chosen R, passing audit with fabricated context. Implications. These design requirements constrain any SAP scheme: P1 and P3 impose formal requirements (provably necessary), while P2 imposes a strong design requirement under compact verification. SBPP instantiates them with minimal constructions: a random nonce, a Merkle root (O(1) state), and a signed receipt. The separation below shows that proofexternal designs, which omit the first two ingredients from pub, are vulnerable to audit re-association. C. Separation: Proof-External Authorization Definition 3 (Proof-external authorization). An authorization mechanism is proof-external if the authorization evidence (capability token, MAC, etc.) is verified alongside the NIZK proof but is not committed as a public input to the proven statement. Proposition (Audit Re-Association Attack). For proofexternal authorization schemes in which the same (D, pv, e) can appear across sessions, we construct an attack in which the adversary produces a misleading audit record that passes verification yet misattributes the proof to a different session. Attack construction. Suppose an adversary observes two honest sessions S1 , S2 for the same drop D (same pv, epoch). In a
proof-external scheme, both sessions produce proofs π1 , π2 whose public inputs agree on all session-independent fields (since pub does not encode the session). The adversary constructs a forged audit record by pairing π1 (generated under S1 ) with the authorization evidence from S2 (e.g., a signed capability token σ2 or receipt ρ2 ). This record passes audit: σ2 verifies (valid signature), π1 verifies (valid proof for the same pub), yet the proof was generated under S1 ̸= S2 . Precondition. This is a conditional separation: the attack requires two sessions for the same (D, pv, e). Epoch rotation reduces the eligible pool; the attack is most potent within an epoch window—a realistic scenario for frequently accessed content. Under SBPP, this attack fails: π1 commits to cd(S1 , D) which embeds NS1 , while the receipt from S2 contains NS2 ̸= NS1 , so the digest recomputation in audit step (ii) produces a mismatch. Scope and limitations. This separation concerns authorization provenance, not online authorization. V5/V7 provide effective online binding and may be entirely sufficient for deployments without post-hoc audit. Why log-level mitigations are insufficient. One might argue that enriching the audit log with heuristic metadata (timestamps, IPs, correlation IDs) could prevent re-association. We show this is insufficient in principle. The NIZK verification function V (pub, π) is deterministic and depends only on pub. For a session-agnostic proof, V returns 1 for any session sharing (D, pv, e). No external data— regardless of its richness—can change V ’s output or create a cryptographic link between π and a specific session. An adversary who holds two valid (πi , σi ) pairs can swap them; the audit log sees two individually valid records (V accepts both, both signatures verify) with no cryptographically detectable inconsistency. Heuristic correlators (e.g., timestamp proximity) are probabilistic, can be defeated by timing manipulation, and do not compose into a verifiable proof of provenance. This is exactly the gap that design requirement (1) identifies: session-distinguishing information must be in pub for any SAP scheme. Log enrichment operates outside pub and therefore cannot substitute. Table I confirms: V5–V7 pass A1–A4a but fail A4b. D. Sufficiency: SBPP Satisfies P1–P3 We now show that SBPP satisfies the properties identified by the design requirements above. We write NS for the session nonce, root S for the committed Merkle root, and define: cdcore (S, D) = H(LP(SBPP-v1, D, pv, e, NS ))
(3)
cdfull (S, D) = H(LP(SBPP-v1, D, pv, e, NS , root S )) (4) E. Session Binding Soundness Definition 4 (Core SBPP Verification). Verifycore (S, τ ) accepts transcript τ = (π, pub, D) under session S iff: (i) S is valid and non-expired; (ii) pub[7] = cdcore (S, D); (iii) π is a valid Groth16 proof over pub.
6
Theorem 1 (Core Session Binding). If SHA-256 is collisionresistant and Groth16 is sound, then for any PPT adversary A that generates transcript τ ∗ using a nonce N ∗ ̸= NS : Pr[Verifycore (S, τ ∗ ) = 1] ≤ negl(λ). Proof sketch. Verifycore requires pub[7] = cdcore (S, D) = H(LP(. . . , NS )). Since LP is injective, LP(. . . , N ∗ ) ̸= LP(. . . , NS ) for N ∗ ̸= NS . By Groth16 soundness, pub[7] is the digest actually committed in π. For acceptance, A must therefore find a SHA-256 collision, which succeeds only with negligible probability. F. Cross-Session Isolation Theorem 2 (Cross-Session Isolation). For sessions S1 , S2 with N1 ̸= N2 , any transcript τ1 accepted under S1 is rejected under S2 : Pr[Verifycore (S2 , τ1 ) = 1] ≤ negl(λ). Proof sketch. τ1 commits to cdcore (S1 , D) which embeds N1 . Verification under S2 expects cdcore (S2 , D) with N2 ̸= N1 . By injectivity of LP and collision resistance of H, the digests differ except with negligible probability.
Win1 (Session rebinding). A produces τ such that Verify(S, τ ) = 1 but τ was generated using NS ′ ̸= NS . Win2 (Unauthorized drop). A produces τ for drop D such that Verify(S, τ ) = 1 but D ∈ / RS . ∗ Win3 (Audit re-association). A produces τaudit such that ∗ Audit(τaudit ) = 1 but π was generated under a different ∗ authorization context from what τaudit claims. Theorem 4 (SAP Security of Full SBPP). Under SHA-256 collision resistance, Groth16 soundness, LP injectivity, Merkle target-binding security, and EUF-CMA security of the receipt signature scheme, the advantage of any PPT A in the SAP security game (Definition 6) is negligible: Pr[Win1 ∨ Win2 ∨ Win3 ] ≤ negl(λ). Proof sketch. Win1 : given A that wins, we build a SHA-256 collision finder or Groth16 soundness breaker (Theorems 1–2). Win2 : given A that wins, we build a Merkle second-preimage finder (Theorem 3). Win3 : A must either forge the receipt signature (contradicting EUF-CMA) or produce a valid Merkle witness for D ∈ / R under the signed root (contradicting Merkle security), or produce a digest collision (contradicting SHA256). Each reduction loses at most a polynomial factor. Full reductions are in Appendix A (Win1 → Theorem 5, Win2 → Theorem 6, Win3 → Theorem 7).
G. Transcript-Level Result-Set Authorization Definition 5 (Full SBPP Verification). Verifyfull (S, τ ) extends Core verification with: (iv) the Merkle membership witness for D is valid against root S committed in cdfull (S, D). Theorem 3 (Transcript-Level Authorization (A4b)). For any D ∈ / R (the candidate set committed by root S ), no PPT adversary can cause Verifyfull (S, τ ) = 1, assuming Merkle target-binding security (no PPT adversary can produce a valid path for D ∈ / R against a committed root), instantiated via SHA-256. Proof sketch. cdfull (S, D) includes root S . Acceptance requires a valid Merkle witness that reconstructs root S from the leaf H(LP(SBPP-LEAF, D)). For D ∈ / R, producing such a witness requires either forging a membership path against the committed root or finding a second-preimage/collision in the Merkle hash construction, both of which succeed only with negligible probability. Core enforces A4a via online D ∈ R check. Theorem 3 adds that result-set authorization is verifiable from τaudit alone (A4b). H. End-to-End Security We now state a composite security theorem that unifies P1– P3. Definition 6 (SAP Security Game). An adversary A interacts with: OIssue (obtain fresh (S, N, texp )), OSearch (submit tokens, receive R, root, ρ), OProve (request honest proofs for chosen (S, D)), and OVerify (submit (τ, S) for online check). A sees all oracle outputs and network messages. A wins if it achieves any of:
I. Leakage Analysis Following the SSE leakage taxonomy [8], plaintext search reveals the user’s geohash cell directly. Encrypted search (GridSE/SBPP) reveals only the access pattern (which k tokens matched)—qualitatively different (content-based vs. location-based) but not zero [11]–[13]. Per-query, SBPP and GridSE have identical SSE leakage. SBPP’s improvement is in cross-phase leakage: session binding (Theorem 2) prevents re-association of proofs with different search sessions, and session consumption prevents replay. Residual leakage. SSE access patterns (deterministic HMAC; mitigated by ORAM [14]), volume patterns, and timing correlation remain. These are inherent to the SSE layer and orthogonal to SBPP. VI. I MPLEMENTATION We implement SBPP in Zairn [5] (∼740 new/modified LOC) by reusing the existing encrypted search module and Groth16 circuit (474 constraints, BN128) without modification. All fields use length-prefixed UTF-8 encoding with domain separators (SBPP-v1, SBPP-LEAF, SBPP-NODE). SHA-256 outputs are mapped to the BN128 scalar field by modular reduction. Cross-language test vectors and canonicalization details are provided in the open-source release [5]. The implementation includes 151 unit and integration tests. VII. E VALUATION We address five research questions: RQ1 leakage profile vs. plaintext/GridSE; RQ2 attack prevention vs. naive composition; RQ3 binding correctness; RQ4 protocol-path overhead; RQ5 scalability, mobile latency, and deployment properties.
7
TABLE I ATTACK M ATRIX (N = 100 TRIALS ). ✓ = BLOCKED ; × = SUCCEEDS . V5–V7: PROOF - EXTERNAL ; V8: INTERNALIZED TOKEN HASH ( STRONGEST BASELINE ). Attack
V1
V2
V3
V4a
V4b
V5
V6
V7
V8
A1: Cross-session A2: Re-association A3: Cross-drop A4a: Result-set (online) A4b: Auth. provenance A5: Delayed replay
× × ✓ × × ×
× × ✓ × × ×
× × ✓ × × ✓
✓ ✓ ✓ ✓ × ✓
✓ ✓ ✓ ✓ ✓ ✓
✓ ✓ ✓ ✓ × ✓
✓ ✓ ✓ ✓ × ✓
✓ ✓ ✓ ✓ × ✓
✓ ✓ ✓ ✓ ✓∗ ✓
∗
V8 passes A4b if the token contains equivalent content (session nonce + result-set root).
A. Setup Synthetic drops are distributed uniformly at random in the Tokyo metropolitan area (35.6–35.8◦ N, 139.6–139.9◦ E). We additionally evaluate under a clustered distribution and under real-world data: 110,776 OpenStreetMap POIs (amenities, shops, tourism, leisure) in the same bounding box, fetched via the Overpass API. All experiments run on Node.js v24 on a consumer laptop (x86-64). Scripts are in the open-source repository [5]. B. RQ1: Leakage Profile Per-query SSE leakage (search pattern, access pattern, volume pattern [8]) is identical for GridSE and SBPP—the same tokens are sent. Plaintext search additionally reveals the user’s geohash cell. SBPP’s improvement is orthogonal: authorization provenance (A1/A2/A4b in Table I). Crossquery Jaccard similarity is >0.98 for all schemes (inherent to geohash). C. RQ2: Naive Composition vs. SBPP A key question is whether the session binding must be embedded in the proof’s public inputs, or whether simpler alternatives suffice. We compare nine protocol variants against six attack classes (N = 100 trials each): V1 Plaintext search + ZKP (no encrypted search, no session binding). V2 GridSE + ZKP (encrypted search, no session binding in proof). V3 GridSE + app-layer nonce (server checks nonce separately, but nonce is not in the proof digest). V4a SBPP Core (session nonce in proof digest; server also performs D ∈ R check). V4b SBPP Full (nonce + Merkle root in proof; transcript-level authorization via membership proof). V5 Signed capability (server signs sidecar token binding session + drop; not in proof). V6 Per-drop signed permit (authorization-only baseline; no ZKP—does not prove proximity). V7 MAC-bound result authorization (server computes MAC over result set; MAC key is server secret). V8 Internalized token hash (hash of signed capability token committed in pub[7]; strongest proof-internalized baseline). Table I reports the results.
TABLE II P ROTOCOL -PATH L ATENCY (µS , 1,000 DROPS ; EXCLUDES G ROTH 16 PROVING , WHICH IS IDENTICAL ACROSS SCHEMES ) Scheme
Med.
Mean
P95
P99
Plaintext GridSE SBPP
2.9 390.8 417.9
13.1 410.6 441.2
55.3 567.2 641.7
94.8 647.2 764.1
A1–A4a and A5 are prevented by all session-aware variants via server-side checks. The critical row is A4b. Among proof-external designs (V5–V7), none passes: re-association succeeds because proofs are session-agnostic. V8 (internalized token hash) commits an opaque signedtoken hash in pub[7], achieving A4b when the token includes equivalent content. V8 validates the SAP principle that internalization is necessary; the comparison axis between V8 and SBPP is therefore not security superiority but audit semantics: V8 couples authorization evidence into one hash, so an auditor must reconstruct the full token to check any single property. SBPP decomposes the committed content into three independently auditable components (nonce → P1, Merkle root → P2, receipt → P3), enabling property-level fault isolation, O(1) compact-mode state, and verifier-state discipline (the server never stores R in Full mode). D. RQ3: Binding Validation All eleven scenarios produce outcomes consistent with the design requirements and Theorems 1–4 (100/100 trials each). These are implementation sanity checks; security rests on the cryptographic assumptions. Fault-localization validation (V8 vs. SBPP). We inject three fault types into audit records (N = 100 each): session rebinding (swap nonce), result-set tampering (alter root), and fabricated context (forge receipt signature). Full SBPP localizes each: nonce mismatch (100/100), Merkle witness failure (100/100), and receipt signature failure (100/100) respectively. V8 returns undifferentiated “hash mismatch” in all three cases (100/100)—confirming the fault-isolation advantage in Table V. E. RQ4: Protocol-Path Overhead Table II reports median latency over 1,000 iterations with 100-iteration warmup. SBPP adds 27 µs median over GridSE (+7%), broken down as: session creation 17 µs, challenge digest 1.9 µs, session validation <1 µs. The dominant cost in both GridSE and SBPP is HMAC token generation (359 µs), which is identical. Both encrypted schemes are ∼140× slower than plaintext geohash encoding (2.9 µs), but remain under 0.5 ms median— well within interactive latency budgets. Important caveat. The 7% overhead is for the protocol path only (session management, token generation, digest computation), not for the full unlock flow. Groth16 proof generation (42–125 ms warm on mobile; Table III) dominates the userperceived latency and is identical across all schemes. The full end-to-end overhead of SBPP over GridSE is thus ∼0.03 ms on a ∼125 ms baseline (<0.03%).
8
J. Offline Audit Replay
TABLE III M OBILE P ROOF L ATENCY ( WARM , n = 30) POCO X7 Pro
iPhone 16 Pro
125 128 181 340 26 936
42 43 51 192 9 935
Prove median (ms) Prove mean (ms) Prove P95 (ms) Prove cold (ms) Verify median (ms) Payload (B)
TABLE IV M ERKLE -ROOT V ERIFIER S CALING
100 sessions: build Merkle trees, generate audit records, purge session state, re-verify from τaudit alone. All 100 pass. The SBPP-specific audit overhead (receipt signature check, digest recomputation, Merkle membership) is ∼4.4 µs per record; Groth16 proof re-verification adds 9–26 ms (Table III), dominating the audit cost. Under Core SBPP (V4a), audit fails—no committed root—confirming A4b requires Full SBPP. K. Cross-Session Re-Association
|R|
Build (ms)
Prove (µs)
Verify (µs)
Steps
100 1 000 5 000 10 000 20 000 50 000
0.2 1.6 5.2 12.4 27.6 54.2
20 25 29 60 68 133
11 19 122 227 460 1137
7 10 13 14 15 16
F. RQ5: Scalability and Real-World Distribution Token matching scales linearly: 0.04 ms at 1,000 drops to 5.2 ms at 100,000 (radius 1 km). Precision is moderate (0.45–0.61) due to geohash coarseness; recall is >0.92. Under 110,776 OpenStreetMap POIs (Tokyo bounding box), match count is ∼2.7× higher than uniform due to real-world clustering, but precision improves (0.60 vs. 0.54) and recall stays >0.93. Per-query SSE leakage is identical for GridSE and SBPP under all distributions. G. Session Consumption Atomicity Four scenarios (N = 1,000 each): sequential double-submit (second always rejected), parallel double-submit (exactly one accepted), expiry boundary (correct in 100%), bulk 10,000session lifecycle (exact counts). The in-memory store is singlethreaded; multi-instance deployments require database-level atomic guards.
Over 1,000 sessions, an adversary who matches (D, pv, e) across session boundaries re-associates proofs in 71.8% of cases for V2/V3 (below 100% because epoch rotation reduces the eligible pool). Under SBPP (V4a/V4b), the success rate is 0%—the session nonce in pub makes each proof sessionspecific. This is SBPP’s primary cross-phase improvement; per-query SSE leakage is unchanged. Payload and audit storage. Full mode adds ∼320 B per unlock (Merkle path); audit records total ∼1.5 kB each (∼45 GB/month at 1 M unlocks/day). L. Concurrency, Malicious Server, Isolation Atomic consumption. Under DB-level WHERE consumed=false guards (N = 1,000), concurrent double-submit achieves exactly-one acceptance in 100% of trials. Malicious server impact. We test five malicious behaviors (N = 100 each): candidate omission (detectable with honest reference root, 100%); biased root signing (not detectable— receipt authenticates what was issued, not correctness); predictable nonce (enables cross-user transfer; random nonces prevent this); session refusal (not detectable—DoS); authorization forgery (impossible—0% forgery rate). These confirm P1– P3 under HBC server while showing the completeness/fairness boundary. Multi-client isolation. 100 k sessions in ∼1 s (∼19.5 MB). Concurrent issue+verify (K = 10–500) all correct. Crosssession isolation: 0/9,900 cross-access attempts succeeded.
H. Mobile End-to-End Latency Table III reports warm-run results (n = 30) on Xiaomi POCO X7 Pro (Android, Chrome 146, 8-core, 8 GB) and iPhone 16 Pro (iOS 18.7, Safari 26.2). Warm proof generation is 42–125 ms median; including SBPP overhead (0.4 ms), the complete unlock is under 130 ms. Cold-start penalties (192–340 ms) reflect WASM compilation. Safari is ∼3× faster than Chrome for both phases. I. Merkle State Compression Table IV compares per-session state and verification overhead for the stateful and Merkle-root verifier modes. Compact-mode state is 104 B regardless of |R| (vs. ∼11 kB stateful at 1,000). Tree construction scales to 54 ms at 50,000. Merkle verification scales from 19 µs to 1.1 ms—negligible vs. Groth16 (9–26 ms).
VIII. D ISCUSSION A. What SBPP Protects and What It Does Not Core SBPP prevents cross-session proof substitution (A1/A2) and enables online result-set authorization (A4a). Full SBPP lifts authorization to the transcript level (A4b), enabling offline auditability. Both levels prevent delayed replay (A5) via session TTL and consumption. Core ensures proofs belong to their originating session; Full additionally commits the authorization context via Merkle root and witness. Combined with signed receipts, this yields replayable authorization provenance under HBC server. SBPP does not address: • SSE access pattern leakage. Deterministic tokens reveal whether two queries target the same cell. This is inherent to SSE; volume-hiding SSE or ORAM [14], [15] would mitigate it at significant performance cost.
9
TABLE V V8 VS . F ULL SBPP: AUDIT P ROPERTIES
A4b (provenance) Fault localization Auditor prerequisites Token-format changes
V8 (opaque)
Full SBPP
✓∗ No Token format Breaks audit
✓ Yes Public key only Transparent
hash mismatch hash mismatch hash mismatch
nonce mismatch Merkle failure sig. failure
Failure-mode diagnostics Session rebinding (A1/A2) Result-set escape (A4b) Fabricated context (P3) ∗
If token contains equivalent content.
Location spoofing. SBPP assumes the client’s coordinates are genuine. Spoofing resistance requires orthogonal mechanisms (trust scoring, multi-sensor fusion [16], [17]). • Malicious server. SBPP assumes an honest-but-curious server. P1–P3 guarantee that accepted proofs are bound to the authorization context the server issued, but not that the server issued honestly (e.g., it could omit candidates or sign a biased root). Extending to malicious servers requires verifiable query processing [18].
•
B. Why Not Simpler Alternatives? Internalized token hash (V8). V8 commits an opaque signedtoken hash in pub[7], validating the SAP principle that internalization is necessary. However, V8 is an ad-hoc instantiation that couples all authorization evidence into a single hash, whereas SBPP provides the practical decomposition of SAP requirements into independently verifiable components. This decomposition matters for forensic practice. Example: if an audit record fails, SBPP localizes the failure—a nonce mismatch indicates session rebinding (A1/A2), a Merkle witness failure indicates result-set escape (A4b), and a receipt signature failure indicates fabricated context (P3 violation). With V8’s opaque hash, all three failure modes produce the same symptom (hash mismatch), and the auditor cannot distinguish them without reconstructing the full token. The security contribution of this paper is the SAP notion and the proof-external separation; SBPP is a practical realization that enables property-level fault isolation in audit. Multi-instance deployment. Session consumption in the prototype uses an in-memory store (single-threaded). In production, atomic consumption maps to a database UPDATE ... WHERE consumed = false or a Redis compareand-swap; the Merkle root and receipt are stateless and require no cross-instance coordination. Toward stronger privacy. Volume-hiding search and ORAMbased retrieval [14], [15] would reduce access-pattern leakage orthogonally to SBPP. IX. R ELATED W ORK Encrypted geographic search and leakage. GridSE [1] introduced prefix-based SSE for geographic queries; later work explored geometric range search and practical private
range search [2], [3]. SSE leakage and its exploitation are also well-studied [8], [9], [11], [12]; recent work studies privacy-preserving and verifiable spatial queries over encrypted data [19], [20]. SBPP is complementary: it preserves per-query SSE leakage while binding search authorization to a later proof. Location proofs and authentication. Groth16 [4] underlies pairing-based ZKP proximity proofs. Prior location-proof and location-authentication schemes typically assume trusted witnesses, infrastructure, or trusted location sources [17], [21]– [28]. SBPP instead binds an encrypted search session to a ZKP-based unlock flow. Authenticated data structures and verifiable composition. Full SBPP’s Merkle-root commitment is related to authenticated data structures [10], [18], [29], [30]. More broadly, SBPP addresses the composition problem of binding a query result to a subsequent cryptographic action—a pattern that arises whenever search and verification are separate protocol phases. Spatial cloaking and differential privacy address orthogonal query-side privacy goals [13], [31], [32]. X. C ONCLUSION We introduced the search-authorized proof (SAP) security notion for systems that compose encrypted geographic search with zero-knowledge proximity verification: three properties (P1–P3) that formalize when an audit transcript (proof, receipt, and Merkle witness) can forensically attest the proof’s originating authorization. We exhibited an audit re-association attack showing that proof-external mechanisms leave this boundary open, and established design requirements for the committed content required by each property. The principal scientific contributions are the SAP notion and the proof-external separation; SBPP is a practical realization, decomposing the required committed content into a session nonce (P1), a Merkle root (P2), and a signed receipt (P3) via a digest-based binding chain requiring no circuit modification. Protocol-path overhead is 7% in a single-instance prototype; DB-backed atomic consumption and multi-client isolation were validated in targeted experiments, though productionscale multi-instance deployment remains future work. SBPP operates under an honest-but-curious server and guarantees that accepted proofs are bound to the authorization context the server issued—not that the server issued honestly. Search completeness, fairness, and SSE access-pattern leakage are outside its scope. Extending to malicious servers via verifiable query processing, and reducing per-query leakage via ORAM, are key directions for future work. Artifacts are available at [5]. AI U SAGE D ISCLOSURE Generative AI tools (OpenAI ChatGPT and Anthropic Claude) were used for coding assistance, literature search, and editorial refinement during manuscript preparation. All AI-assisted outputs were reviewed, edited, and validated by the author, who takes full responsibility for the content of the manuscript.
10
D ECLARATION OF C OMPETING I NTEREST The author declares no competing interests. A PPENDIX A P ROOF OF T HEOREM 4 (SAP S ECURITY ) Audit algorithm. Audit(π, pub, D, mp, ρ): (1) verify Sigsrv (ρ); (2) extract (N, root, pv, e) from ρ; (3) recompute cd′ ← H(LP(SBPP-v1, D, pv, e, N, root)); check pub[7] = cd′ ; (4) verify Merkle path mp for leaf H(LP(SBPP-LEAF, D)) against root; (5) verify π over pub via Groth16. Return 1 iff all checks pass. Notation. “Different authorization context” means N ′ ̸= N (session difference) or root ′ ̸= root (result-set difference). Theorem 5 (Win1 Reduction). If A wins Win1 , we construct a SHA-256 collision finder B (Groth16 soundness ensures π ∗ fixes pub∗ [7], which is the starting point of the reduction). Proof. A outputs τ ∗ = (π ∗ , pub∗ , D) accepted by Verifyfull (S, τ ∗ ) (nonce NS ), but π ∗ was generated with N ′ ̸= NS . Verification requires pub∗ [7] = cdfull (S, D), which embeds NS . By Groth16 soundness, π ∗ fixes pub∗ [7]. Since π ∗ was generated with N ′ , we have pub∗ [7] = H(LP(. . . , N ′ , . . .)). Acceptance gives H(LP(. . . , NS , . . .)) = H(LP(. . . , N ′ , . . .)). LP injectivity ensures the preimages differ: B outputs this pair as a SHA-256 collision. Theorem 6 (Win2 Reduction). If A wins Win2 , we construct B that breaks Merkle authentication security (target-binding: given a root r and a set R, find D ∈ / R and a path mp such that mp verifies for D against r). Proof. A outputs (π, pub, D, mp) accepted under S with D ∈ / RS . The honest tree built over RS does not contain leaf H(LP(SBPP-LEAF, D)), yet mp verifies against root S . B forwards (D, mp, root S , RS ) to the Merkle challenger, breaking target-binding. Theorem 7 (Win3 Reduction). If A wins Win3 , we construct either an EUF-CMA forger, a SHA-256 collision finder, or a Merkle target-binding breaker. ∗ Proof. A outputs τaudit passing all five Audit checks, but π was generated under A′ ̸= A. Case (a): session difference (N ′ ̸= N ). Step (1) verifies the receipt signature on ρ. Either ρ was forged (B breaks EUFCMA) or ρ is honest and authenticates N . Step (3) recomputes cd′ with N ; since π was generated with N ′ , acceptance yields a SHA-256 collision (as in Win1 ). Case (b): result-set difference (root ′ ̸= root). Either ρ is forged (EUF-CMA) or the digest equality yields a collision. If D ∈ / R under the honest root, step (4) yields a Merkle target-binding break (as in Win2 ).
By a union bound, Pr[Win1 ∨ Win2 ∨ Win3 ] ≤ AdvCR SHA-256 + Merkle EUF-CMA AdvSound + Adv + Adv , all negligible under Groth16 target-bind Sig standard assumptions.
R EFERENCES [1] R. Guo, J. Li, and S. Yu, “GridSE: Towards practical secure geographic search via prefix symmetric searchable encryption,” in Proc. 33rd USENIX Security Symposium, 2024, pp. 5413–5430. [2] S. K. Kermanshahi, S.-F. Sun, J. K. Liu, R. Steinfeld, S. Nepal, W. F. Lau, and M. H. A. Au, “Geometric range search on encrypted data with forward/backward security,” IEEE Trans. Dependable and Secure Computing, vol. 19, no. 1, pp. 698–716, 2022. [3] I. Demertzis, S. Papadopoulos, O. Papapetrou, A. Deligiannakis, and M. Garofalakis, “Practical private range search revisited,” in Proc. ACM SIGMOD, 2016, pp. 185–198. [4] J. Groth, “On the size of pairing-based non-interactive arguments,” in Advances in Cryptology—EUROCRYPT 2016, ser. LNCS, vol. 9666, 2016, pp. 305–326. [5] Zairn Contributors, “Zairn: Open-source location sharing & geoanchored content platform,” 2026, software, Zenodo release, v0.6.0. [6] D. X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” in Proc. IEEE Symposium on Security and Privacy, 2000, pp. 44–55. [7] M. Chase and S. Kamara, “Structured encryption and controlled disclosure,” in Advances in Cryptology—ASIACRYPT 2010, ser. LNCS, vol. 6477, 2010, pp. 577–594. [8] D. Cash, P. Grubbs, J. Perry, and T. Ristenpart, “Leakage-abuse attacks against searchable encryption,” in Proc. ACM CCS, 2015, pp. 668–679. [9] R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky, “Searchable symmetric encryption: Improved definitions and efficient constructions,” J. Computer Security, vol. 19, no. 5, pp. 895–934, 2011. [10] R. C. Merkle, “A certified digital signature,” in Advances in Cryptology—CRYPTO ’89 Proceedings, ser. Lecture Notes in Computer Science, vol. 435, 1990, pp. 218–238. [11] S. Kamara, A. Kati, T. Moataz, T. Schneider, A. Treiber, and M. Yonli, “SoK: Cryptanalysis of encrypted search with LEAKER: A framework for LEakage attacK evaluation on real-world data,” in Proc. IEEE EuroS&P, 2022, pp. 90–108. [12] E. M. Kornaropoulos, N. Moyer, C. Papamanthou, and A. Psomas, “Leakage inversion: Towards quantifying privacy in searchable encryption,” in Proc. ACM CCS, 2022, pp. 1829–1842. [13] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux, “Quantifying location privacy,” in Proc. IEEE Symposium on Security and Privacy, 2011, pp. 247–262. [14] O. Goldreich and R. Ostrovsky, “Software protection and simulation on oblivious RAMs,” J. ACM, vol. 43, no. 3, pp. 431–473, 1996. [15] E. Stefanov, M. van Dijk, E. Shi, T.-H. H. Chan, C. Fletcher, L. Ren, X. Yu, and S. Devadas, “Path ORAM: An extremely simple oblivious RAM protocol,” J. ACM, vol. 65, no. 4, pp. 18:1–18:26, 2018. [16] W. Liu and P. Papadimitratos, “Guardian positioning system (GPS) for location based services,” in Proc. ACM WiSec, 2025, pp. 88–99. [17] S. Capkun and J.-P. Hubaux, “Secure positioning in wireless networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 2, pp. 221–232, 2006. [18] F. Li, M. Hadjieleftheriou, G. Kollios, and L. Reyzin, “Authenticated index structures for aggregation queries,” ACM Trans. Inf. Syst. Secur., vol. 13, no. 4, pp. 32:1–32:35, 2010. [19] Y. Miao, Y. Yang, X. Li, Z. Liu, H. Li, K.-K. R. Choo, and R. H. Deng, “Efficient privacy-preserving spatial range query over outsourced encrypted data,” IEEE Trans. Inf. Forensics Security, vol. 18, pp. 3921– 3933, 2023. [20] Z. Mei, J. Zeng, C. Zhang, S. Yao, S. Zhang, H. Wang, H. Li, and J. Shi, “Efficient and verifiable range query scheme for encrypted geographical information in untrusted cloud environments,” ISPRS Int. J. Geo-Inf., vol. 13, no. 8, p. 281, 2024. [21] W. Luo and U. Hengartner, “Proving your location without giving up your privacy,” in Proc. ACM HotMobile, 2010, pp. 7–12. [22] ——, “VeriPlace: A privacy-aware location proof architecture,” in Proc. ACM GIS, 2010, pp. 23–32. [23] Z. Zhu and G. Cao, “APPLAUS: A privacy-preserving location proof updating system for location-based services,” in Proc. IEEE INFOCOM, 2011, pp. 1889–1897. [24] X. Wang, A. Pande, J. Zhu, and P. Mohapatra, “STAMP: Enabling privacy-preserving location proofs for mobile users,” IEEE/ACM Trans. Networking, vol. 24, no. 6, pp. 3276–3289, 2016. [25] F. Zafar, A. Khan, A. Anjum, C. Maple, and M. A. Shah, “Location proof systems for smart Internet of Things: Requirements, taxonomy, and comparative analysis,” Electronics, vol. 9, no. 11, p. 1776, 2020. [26] H. Hu, J. Xu, Q. Chen, and Z. Yang, “Authenticating location-based services without compromising location privacy,” in Proc. ACM SIGMOD, 2012, pp. 301–312.
11
[27] J. Camenisch, D. A. Ortiz-Yepes, and F.-S. Preiss, “Strengthening authentication with privacy-preserving location verification of mobile phones,” in Proc. ACM WPES, 2015, pp. 37–48. [28] Y. Zheng, M. Li, W. Lou, and Y. T. Hou, “Location based handshake and private proximity test with location tags,” IEEE Trans. Dependable and Secure Computing, vol. 14, no. 4, pp. 406–419, 2017. [29] A. Miller, M. Hicks, J. Katz, and E. Shi, “Authenticated data structures, generically,” in Proc. ACM POPL, 2014, pp. 411–423. [30] C. Papamanthou, R. Tamassia, and N. Triandopoulos, “Optimal verification of operations on dynamic sets,” in Advances in Cryptology— CRYPTO 2011, ser. LNCS, vol. 6841, 2011, pp. 91–110. [31] M. Gruteser and D. Grunwald, “Anonymous usage of location-based services through spatial and temporal cloaking,” in Proc. ACM MobiSys, 2003, pp. 31–42. [32] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: Differential privacy for location-based systems,” in Proc. ACM CCS, 2013, pp. 901–914.