Privacy Protection in Location-based Federated k-Nearest Neighbor Queries

The proliferation of autonomous data owners (a.k.a silos) across diverse computing environments has created significant challenges for collaborative data processing with privacy guarantees. This is particularly acute for locationbased services that rely on the federated k-Nearest Neighbor (kNN) query. As a fundamental operation, federated kNN enables collaboration across data silos without centralizing raw data. However, existing privacy-preserving solutions for federated kNN queries show a critical imbalance, as they primarily protect silo data privacy while largely neglecting user privacy.This privacy imbalance manifests in three key limitations of current approaches. First, they typically require users to disclose precise query locations to data silos or coordinators, creating direct privacy risks. Second, even when employing data obfuscation techniques, risks of location leakage persist, often at the cost of reduced query accuracy. Third, the raw data or data distributions may still be inferred by different silos through intermediate results during the query process.To address these gaps, this research introduces a novel dual-privacy preserving framework that simultaneously protects both user privacy and silo data privacy for location-based federated kNN queries. The core of our solution is the synergistic integration of Private Information Retrieval (PIR) and Homomorphic Encryption (HE). PIR enables users to retrieve specific database items without revealing which items are accessed. This perfectly conceals their query intention. Complementarily, Paillier homomorphic encryption allows essential geometric computations (e.g., distance calculations) to be performed directly on encrypted data. This shields both the users’ locations and the silos’ raw data during computation.Our framework operates through four sequential phases ensuring continuous privacy protection: (1) Query Generation, where the user cryptographically encodes their location. (2) Federated Encrypted Database Preparation, where a DataBroker coordinates the creation of an encrypted, aggregated dataset from all silos. (3) Top-k Selection, a secure protocol where the user and DataBroker collaboratively identify the k nearest neighbors without exposing intermediate results. (4) Federated Response Delivery, where the user employs PIR to obtain the final k records without accessing any extraneous information.We validate the framework through comprehensive theoretical analysis and empirical evaluation. The security analysis formally proves that the protocol achieves provable privacy guarantees under the semi-honest adversarial model. It reveals no information beyond the query output. The experimental evaluation, based on a Java implementation, demonstrates the framework’s practical efficiency. Results show that the computational overhead scales polynomially with key parameters while consistently providing stronger privacy protection than baseline approaches.This work makes three main contributions. First, it proposes the first dedicated dual-privacy framework that systematically addresses the privacy imbalance in federated kNN queries. Second, it demonstrates a strategy for effectively combining PIR and HE to establish complementary, end-to-end privacy guarantees. Third, it provides a foundational step towards trustworthy federated spatial query processing. This has significant implications for privacy-sensitive domains like location-based services, healthcare, and finance. Future work will extend the framework to malicious security models and optimize it for real-time applications.