Search papers, labs, and topics across Lattice.
This paper introduces PPRC, a novel protocol for range counting that addresses the challenges of privacy, efficiency, and accuracy in distributed geographic data settings, particularly when datasets overlap. By employing the Private Range Predicate (PRP) technique, PPRC reformulates range evaluations into encrypted membership tests, significantly reducing the need for expensive secure comparisons. Experimental results demonstrate that PPRC achieves up to 55x smaller errors and 37x faster processing times compared to existing protocols, marking a substantial advancement in privacy-preserving geographic information systems.
PPRC achieves unprecedented efficiency and accuracy in range counting over overlapping datasets while ensuring query privacy, outperforming existing protocols by a wide margin.
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.
