Location-based services (LBS) routinely answer \(k\)-nearest neighbor (kNN) queries over users’ locations and points of interest, but revealing precise locations and query patterns poses serious privacy risks. Existing systems rely largely on heuristic dummy generation and query fragmentation, and typically argue privacy via entropy or attack-specific reasoning under restricted adversary models. In this paper, we present a new framework for location and query obfuscation in kNN-based LBS that provides formal privacy guarantees and is explicitly evaluated against modern machine-learning-based adversaries. We introduce Geo-Obfus, a spatially differentially private dummy generation mechanism that satisfies geo-indistinguishability, and Query-Obfus, a distributionally private query obfuscation scheme that protects sensitive query attributes, both integrated into an efficient two-stage kNN processing pipeline. We derive theoretical guarantees for location privacy, query privacy, and their composition over repeated queries, analyze the utility loss in terms of kNN accuracy and latency, and evaluate robustness against optimal Bayesian inference and neural classifiers trained to distinguish real locations and queries from dummies. Using real and synthetic mobility datasets, we show how privacy parameters control the trade-off between formal privacy and kNN utility and demonstrate that Geo-Obfus and Query-Obfus substantially reduce the success rate of learning-based attacks compared with heuristic dummy and fragmentation methods, providing a principled, learning-resistant foundation for privacy-preserving kNN services.
Location-based services (LBS) routinely answer \(k\)-nearest neighbor (kNN) queries over users’ locations and points of interest, but revealing precise locations and query patterns poses serious privacy risks. Existing systems rely largely on heuristic dummy generation and query fragmentation, and typically argue privacy via entropy or attack-specific reasoning under restricted adversary models. In this paper, we present a new framework for location and query obfuscation in kNN-based LBS that provides formal privacy guarantees and is explicitly evaluated against modern machine-learning-based adversaries. We introduce Geo-Obfus, a spatially differentially private dummy generation mechanism that satisfies geo-indistinguishability, and Query-Obfus, a distributionally private query obfuscation scheme that protects sensitive query attributes, both integrated into an efficient two-stage kNN processing pipeline. We derive theoretical guarantees for location privacy, query privacy, and their composition over repeated queries, analyze the utility loss in terms of kNN accuracy and latency, and evaluate robustness against optimal Bayesian inference and neural classifiers trained to distinguish real locations and queries from dummies. Using real and synthetic mobility datasets, we show how privacy parameters control the trade-off between formal privacy and kNN utility and demonstrate that Geo-Obfus and Query-Obfus substantially reduce the success rate of learning-based attacks compared with heuristic dummy and fragmentation methods, providing a principled, learning-resistant foundation for privacy-preserving kNN services.
