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

Computer Science > Cryptography and Security [Submitted on 5 Apr 2026] Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification Yoshiyuki Ootani 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. Comments: 11 pages, 1 figure, 5 tables. Preprint version; submitted to IEEE Transactions on Information Forensics and Security Subjects: Cryptography and Security (cs.CR); Networking and Internet Architecture (cs.NI) Cite as: arXiv:2604.03902 [cs.CR]   (or arXiv:2604.03902v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.03902 Focus to learn more Submission history From: Yoshiyuki Ootani [view email] [v1] Sun, 5 Apr 2026 00:14:00 UTC (91 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.NI References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)