Search papers, labs, and topics across Lattice.
This paper identifies a critical authorization provenance gap in location-based systems that combine encrypted geographic search with zero-knowledge proximity proofs, where proofs cannot be reliably attributed to their originating search sessions. They formalize this gap as the search-authorized proof (SAP) security notion and demonstrate the vulnerability through a concrete audit re-association attack. To address this, they introduce Search-Bound Proximity Proofs (SBPP), a novel approach that binds session-identifying information to the proof without modifying the ZKP circuit, enabling offline auditability and property-level fault isolation.
Location-based systems are vulnerable to forensic misattribution attacks because zero-knowledge proximity proofs lack session-identifying information, but Search-Bound Proximity Proofs fix this without modifying the ZKP circuit.
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. Search-Bound Proximity Proofs (SBPP) realize the SAP requirements without modifying the ZKP circuit: session nonce, Merkle-root result-set commitment, and signed receipt are decomposed into independently auditable components, enabling property-level fault isolation in offline audit. Experiments on synthetic and real-world data (110,776 OpenStreetMap POIs) show sub-millisecond absolute overhead on a 125 ms Groth16 baseline.
