Efficient and Secure Range Counting over Distributed Geographic Data with Query Range Protection

• URL: http://arxiv.org/abs/2607.04194v1
• Date: Sun, 05 Jul 2026 09:36:17 GMT
• Title: Efficient and Secure Range Counting over Distributed Geographic Data with Query Range Protection
• Abstract summary: Range counting raises substantial privacy concerns when data is distributed across multiple organizations.<n>Existing privacy-preserving protocols focus on protecting datasets, but cannot simultaneously achieve efficiency, query privacy, and accuracy on overlapping data.<n>We propose PPRC, the first protocol that jointly satisfies all the privacy, efficiency, and accuracy requirements.
• Score: 21.52397359712602
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Range counting is a core primitive in geographic information systems. When data is distributed across multiple organizations, conducting range counting raises substantial privacy concerns. Existing privacy-preserving protocols focus on protecting organizations' datasets, but cannot simultaneously achieve efficiency, query privacy, and accuracy on overlapping data. Typical protocols process query range in plaintext for efficient point-in-range evaluation, since query-private designs rely on expensive secure comparisons. Moreover, most works assume non-overlapping datasets across organizations, which leads to huge errors in overlapping scenarios. In this paper, we propose PPRC, the first protocol that jointly satisfies all the privacy, efficiency, and accuracy requirements. PPRC makes two key technical contributions. First, we design the Private Range Predicate (PRP) technique that supports efficient point-in-range evaluation while protecting the query range. PRP reformulates range evaluation as encrypted membership tests, effectively replacing costly secure comparisons with faster secure multiplications. Second, we propose Oblivious Linear Counting (OLC), an aggregation scheme that efficiently and securely aggregates partial results from organizations with overlapping data. OLC involves only lightweight cryptographic operations and ensures that no information is leaked beyond the final range count. We theoretically analyze the accuracy, efficiency, and security of PPRC. Experiments on real-world and synthetic datasets show that PPRC achieves up to 55x smaller errors and 37x speedup compared to baseline protocols.

Related papers

• CauTion: Knowing When to Trust LLMs for Ensemble Causal Discovery [51.07538881798502]
  Large language models (LLMs) offer a promising source of domain knowledge to complement statistical inference.<n>We propose CauTion, a framework that reliably integrates LLM domain knowledge into an ensemble of statistical causal discovery algorithms.<n>CauTion consistently outperforms both data-centric and LLM-augmented baselines.
  arXiv  Detail & Related papers  (2026-06-02T13:07:43Z)
• Perfectly-Private Analog Secure Aggregation in Federated Learning [51.61616734974475]
  In federated learning, multiple parties train models locally and share their parameters with a central server, which aggregates them to update a global model.<n>In this paper, a novel secure parameter aggregation method is proposed that employs the torus rather than a finite field.
  arXiv  Detail & Related papers  (2025-09-10T15:22:40Z)
• Conformal Prediction for Privacy-Preserving Machine Learning [83.88591755871734]
  Using AES-encrypted variants of the MNIST dataset, we demonstrate that Conformal Prediction methods remain effective even when applied directly in the encrypted domain.<n>Our work sets a foundation for principled uncertainty quantification in secure, privacy-aware learning systems.
  arXiv  Detail & Related papers  (2025-07-13T15:29:14Z)
• Data Poisoning Attacks to Locally Differentially Private Range Query Protocols [15.664794320925562]
  Local Differential Privacy (LDP) has been widely adopted to protect user privacy in decentralized data collection.<n>Recent studies have revealed that LDP protocols are vulnerable to data poisoning attacks.<n>We present the first study on data poisoning attacks targeting LDP range query protocols.
  arXiv  Detail & Related papers  (2025-03-05T12:40:34Z)
• EVA-S2PLoR: Decentralized Secure 2-party Logistic Regression with A Subtly Hadamard Product Protocol (Full Version) [2.1010315462623184]
  This paper proposes an efficient, verifiable, and accurate security 2-party logistic regression framework (EVA-S2PLoR)<n>It achieves accurate nonlinear function through a subtly secure hadamard product protocol and its derived protocols.<n>High efficiency and precision are guaranteed by the asynchronous flow on floating point numbers and the few number of fixed communication rounds.
  arXiv  Detail & Related papers  (2025-01-09T13:19:59Z)
• When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery [7.746385592375338]
  Local Differential Privacy protocols have been successfully deployed in real-world scenarios by tech companies like Google, Apple, and Microsoft.<n>We propose a Generalized Count Mean Sketch protocol that captures many existing frequency estimation protocols.<n>We present a novel protocol for collecting data within unknown domain, as our frequency estimation protocols only work effectively with known data domain.
  arXiv  Detail & Related papers  (2024-12-23T05:50:11Z)
• Accelerating Privacy-Preserving Medical Record Linkage: A Three-Party MPC Approach [1.7999333451993955]
  This paper presents a novel and efficient PPRL based on a secure 3-party computation framework. We demonstrate that our method preserves the linkage quality of the state-of-the-art PPRL method while achieving up to 14 times faster performance.
  arXiv  Detail & Related papers  (2024-10-28T23:13:01Z)
• Enabling Privacy-preserving Model Evaluation in Federated Learning via Fully Homomorphic Encryption [1.9662978733004604]
  Federated learning has become increasingly widespread due to its ability to train models collaboratively without centralizing sensitive data.<n>The evaluation phase presents significant privacy risks that have not been adequately addressed in the literature.<n>We propose a novel evaluation method that leverages fully homomorphic encryption.
  arXiv  Detail & Related papers  (2024-03-21T14:36:55Z)
• A Survey of Secure Computation Using Trusted Execution Environments [80.58996305474842]
  This article provides a systematic review and comparison of TEE-based secure computation protocols. We first propose a taxonomy that classifies secure computation protocols into three major categories, namely secure outsourced computation, secure distributed computation and secure multi-party computation. Based on these criteria, we review, discuss and compare the state-of-the-art TEE-based secure computation protocols for both general-purpose computation functions and special-purpose ones.
  arXiv  Detail & Related papers  (2023-02-23T16:33:56Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Collaborative Training between Region Proposal Localization and Classification for Domain Adaptive Object Detection [121.28769542994664]
  Domain adaptation for object detection tries to adapt the detector from labeled datasets to unlabeled ones for better performance. In this paper, we are the first to reveal that the region proposal network (RPN) and region proposal classifier(RPC) demonstrate significantly different transferability when facing large domain gap.
  arXiv  Detail & Related papers  (2020-09-17T07:39:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.