Efficient and Secure Range Counting over Distributed Geographic Data with Query Range Protection Haoxin Yang1 , Pinghui Wang1,∗ , Zhe Hou2 , Tian Zhou1 , Guangmingzi Yang2 , Zehua Lei2 , Rundong Li1 , Yutong Song1 , Yongyuan Peng1 , Fangming Dong1 , Xiaohong Guan1
arXiv:2607.04194v1 [cs.DS] 5 Jul 2026
1 Xi’an Jiaotong University, 2 China Mobile System Integration Co., Ltd {yhxaxx1,xjtulirundong,Sunny52012,butter0210field,dfming}@stu.xjtu.edu.cn,[email protected] [email protected],{tianzhou,xhguan}@xjtu.edu.cn,[email protected],[email protected]
ABSTRACT
1
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-inrange 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 55× smaller errors and 37× speedup compared to baseline protocols.
In geographic information systems (GIS), range counting is a fundamental task that returns the number of distinct geographic records falling within a given query range. It supports a variety of geographic analysis and decision-making tasks. With the growing scale of data and the prevalence of multiorganizational data silos, range counting increasingly needs to be performed over distributed geographic datasets owned by multiple data holders. This gives rise to the Distributed Range Counting (DRC) problem, which computes the number of records whose associated locations fall within a query range over the union of all datasets. Such scenarios naturally arise in applications where geographic data is held by multiple organizations with their own infrastructures. For example, a car-hailing user queries the number of available cars located within a pickup region to estimate the expected waiting time, while car location records are distributed across different car-hailing companies [23, 32]. Similarly, a resident estimates the number of infection cases located within a geographic region using data held by several hospitals to assess local infection risk [45]. In addition, an urban planner analyzes population or traffic density by counting records located within queried geographic regions using data from multiple agencies [8, 30]. In these scenarios, the query user only requires an aggregated range count, while both the data holders’ datasets and the query range are highly sensitive. Consequently, such applications involve two privacy properties: data privacy, ensuring that each data holder’s records remain confidential, and query privacy, preventing disclosure of the user’s query range, which may reveal personal information such as location or health status. For instance, a query range centered around a user’s home exposes their residential area, while repeated queries near a hospital can imply potential health issues. These properties are mandated by major data protection regulations [7, 20, 34]. Existing DRC schemes fail to meet the two properties simultaneously. To achieve high efficiency, most Data-Private works [8, 23, 32] only protect data privacy, while leaving the query range in plaintext. In these designs, the query user submits the plaintext query range to each data holder, who computes a partial range count—the number of records in its dataset that fall within the range. Data holders then protect their partial counts via encryption or differential privacy noise before a central aggregator sums them to derive the final range count. While efficient, this design exposes the query range and thus violates query privacy. Protecting query privacy typically incurs substantial computational overhead. Existing Query-Private protocols [1, 38, 40] and Exact multiparty computation (MPC) solutions [12, 15] achieve
PVLDB Reference Format: Haoxin Yang1 , Pinghui Wang1,∗ , Zhe Hou2 , Tian Zhou1 , Guangmingzi Yang2 , Zehua Lei2 , Rundong Li1 , Yutong Song1 , Yongyuan Peng1 , Fangming Dong1 , Xiaohong Guan1 . Efficient and Secure Range Counting over Distributed Geographic Data with Query Range Protection. PVLDB, 19(2): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/jackson-maybe/PPRC. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 19, No. 2 ISSN 2150-8097. doi:XX.XX/XXX.XX
∗ Pinghui Wang is the corresponding author.
INTRODUCTION
4
DH 1
3 1
o1 : ( x1 , y1 ) o2 : ( x2 , y2 ) o5 : ( x5 , y5 )
2
5 6
Input: query range Output: range count = 3
DH 2
o2 : ( x2 , y2 ) o3 : ( x3 , y3 ) o7 : ( x7 , y7 )
Table 1: Comparison of distributed range counting protocols under the PDRC requirements. Accuracy indicates the robustness against overcounting errors caused by data overlap. Privacy indicates protection of both data and query privacy. Efficiency reflects scalability to large datasets. Symbols and #denote Yes and No, respectively. For Privacy, G #denotes protection of only data privacy.
record
Data Holder (DH)
7
DH 3
o3 : ( x3 , y3 ) o4 : ( x4 , y4 ) o6 : ( x6 , y6 )
② ③ ② ③ ② ③ Central Aggregator ①Enc(
)
Protocol
④Enc(3)
Data-Private [8, 23, 32] Query-Private [1, 38, 40] Exact MPC [12, 15]
Query User
Figure 1: An example of private distributed range counting.
Accuracy
Privacy
# #
# G
PPRC query privacy using fully homomorphic encryption or secret sharing. These approaches conduct point-in-range evaluation through secure comparisons between record coordinates and encrypted range boundaries. However, secure comparisons require expensive cryptographic operations, such as bit decomposition and polynomial evaluation, leading to prohibitive computation costs at scale. Moreover, most existing DRC protocols assume that datasets across data holders contain no overlapping records, which is frequently violated in real-world scenarios—for example, in a carrecord Data Holder (DH) hailing scenario, a7 driver can be registered with multiple car-hailing companies. Thus, simply summing partial counts—as done in both Data-Private and Query-Private protocols—leads to large overestimation errors. On the other hand, while Exact MPC solutions [12, 15] support privacy-preserving deduplication, they rely on costly operations such as oblivious sorting and secure comparisons, making them impractical at scale. These limitations motivate a stronger problem formulation, which we call Private Distributed Range Count (PDRC), explicitly capturing the key challenges that are not jointly addressed by existing protocols. PDRC requires simultaneously achieving: (1) Accuracy: which ensures accurate range counting over distinct records by correctly deduplicating overlaps across data holders; (2) Bilateral Privacy: which protects both data privacy and query privacy, preventing any leakage about data holders’ datasets or the query range; (3) Efficiency: which provides high efficiency and scalability for practical deployment on large datasets. Fig. 1 illustrates an example with three data holders containing overlapping records, where the correct range count over distinct records is 3. Throughout the process, both the query range and the data holders’ datasets must remain private. Table 1 further shows that existing protocols fail to satisfy accuracy, bilateral privacy, and efficiency simultaneously. To address the PDRC problem, we propose PPRC, the first protocol that jointly achieves accurate range counting over overlapping datasets, bilateral privacy, and practical efficiency. Within PPRC, secure range evaluation and privacy-preserving aggregation are jointly designed to enable efficient query-private processing and lightweight deduplication. Specifically, PPRC makes two key technical contributions. First, we design the Private Range Predicate (PRP), a range-predicate abstraction that enables efficient point-inrange evaluation while protecting the query range. PRP reformulates range evaluation as secure membership tests via encrypted Bloom filters. This abstraction replaces costly secure comparisons with cheaper secure multiplications, greatly reducing the overall
Efficiency # #
computational cost. PRP exposes an accuracy-efficiency tradeoff controlled by the Bloom filter size. Larger Bloom filter sizes improve query accuracy, but incur higher computational overhead. In addition, larger query ranges require larger Bloom filter encodings, which also increase the computational cost. Second, we propose Oblivious Linear Counting (OLC), a secure aggregation scheme designed to efficiently and securely aggregate PRP results from overlapping datasets. OLC adapts the classic Linear Counting sketch [37] to the encrypted domain, introducing two key technical optimizations to ensure practical performance and privacy: (i) an efficiency optimization that restructures the sketch aggregation logic to substitute expensive cryptographic multiplications with lightweight additions, drastically reducing the computation cost; and (ii) a privacy optimization that ensures no information is leaked beyond the final range count. Its accuracy-efficiency tradeoff is controlled by the sketch size: larger sketches improve counting accuracy at a higher computational cost. Our main contributions are summarized as follows: • We formalize the Private Distributed Range Count (PDRC) problem, which requires efficiency, bilateral privacy, and accuracy over overlapping datasets. We propose PPRC, the first protocol that satisfies these requirements simultaneously. • We design the Private Range Predicate (PRP) technique, a rangepredicate abstraction that transforms point-in-range tests into secure membership tests, thereby eliminating expensive secure comparisons. • We propose Oblivious Linear Counting (OLC), a secure aggregation scheme tailored for overlapping datasets. OLC achieves practical efficiency by substituting expensive cryptographic operations with lightweight additions, and simultaneously ensures no information leakage beyond the final range count. • We theoretically analyze the accuracy, efficiency, and security of PPRC. Furthermore, experiments on real-world and synthetic datasets show that PPRC achieves up to 55× smaller errors and 37× speedup compared with baseline protocols.
2 PROBLEM FORMULATION 2.1 Distributed Range Count We consider 𝐼 ∈ N+ data holders. Each data holder 𝑖 ∈ {1, . . . , 𝐼 } holds a geographic dataset 𝐷𝑖 . In these datasets, each record is 2
represented as 𝑜 = (id, 𝑥, 𝑦), where id denotes a unique entity identifier and (𝑥, 𝑦) denotes the associated geographic coordinates. Different data holders may have overlapping records, and we denote Ð𝐼 𝐷 = 𝑖=1 𝐷𝑖 as the set of all distinct records. Our goal is to compute the range count 𝑅𝐶, i.e., the number of distinct records in 𝐷 whose geographic locations fall within a query range 𝑅 provided by the query user. The query range is a rectangle 𝑅 = ( [𝑥 l, 𝑥 r ], [𝑦l, 𝑦r ]), where [𝑥 l, 𝑥 r ] and [𝑦l, 𝑦r ] represent the ranges along the 𝑥- and 𝑦-dimensions, respectively. For a record 𝑜 = (id, 𝑥, 𝑦), we define the in-range indicator 1𝑅 (𝑜) = 1 if 𝑥 ∈ [𝑥 l, 𝑥 r ] ∧ 𝑦 ∈ [𝑦l, 𝑦r ], and 0 otherwise. The range count is then defined as: ∑︁ 𝑅𝐶 = 1𝑅 (𝑜).
• Data Privacy: The dataset of each DH should remain confidential. Neither the other DHs nor the CA can infer any information about it, and the QU learns no additional information about DHs’ datasets beyond the final range count. • Query Privacy: Only the QU knows the plaintext query range, while DHs and the CA gain no knowledge about it. • Efficiency: The protocol should be highly efficient and scalable for large datasets in real-world settings.
3 PRELIMINARIES 3.1 Bloom Filter Bloom filter [18] is a classic data structure used to solve the membership test problem, i.e., determining whether an element belongs to a given set. For a set 𝑈 , the Bloom filter encodes all elements of 𝑈 into an array of 𝑀 bits, denoted as BF[𝑚], 1 ≤ 𝑚 ≤ 𝑀. Initially, all bits in the array are set to 0. Then, we choose 𝐾 independent hash functions {ℎ 1, . . . , ℎ𝐾 }, each mapping 𝑢 ∈ 𝑈 uniformly to an index in {1, . . . , 𝑀 }. To encode 𝑢 ∈ 𝑈 into BF, we set BF[ℎ𝑘 (𝑢)] = 1 for 1 ≤ 𝑘 ≤ 𝐾. After encoding all elements of 𝑈 into the BF, we can test whether an element 𝑢 ′ belongs to 𝑈 by checking whether BF[ℎ𝑘 (𝑢 ′ )] = 1 for all 1 ≤ 𝑘 ≤ 𝐾. If any bit is 0, 𝑢 ′ is definitely not in 𝑈 . If all bits are 1, 𝑢 ′ is in 𝑈 with a high probability. Notably, a Bloom filter can produce false positive. Assuming the cardinality of 𝑈 is 𝜇, the false positive probability can be computed as: 𝜇 𝑓𝑝 = (1 − (1 − 𝑀1 ) 𝐾 𝜇 ) 𝐾 ≈ (1 − 𝑒 −𝐾 𝑀 ) 𝐾 .
𝑜 ∈𝐷
Unlike conventional single-data-holder settings [1, 42, 44], our problem focuses on distributed range counting over overlapping datasets, where secure duplicate elimination across multiple data holders is required. We focus on rectangular ranges, naturally capturing real-world workloads like car-hailing in grid-structured cities.
2.2
System Model
Our system comprises three entities: the Data Holders (DHs), the Central Aggregator (CA), and the Query User (QU). Each DH holds a private dataset and strictly follows the protocol for computations on its data. The CA securely aggregates encrypted information from the DHs and sends the encrypted result to the QU. In practice, the CA can be a third-party server or one of the DHs. The QU generates the homomorphic encryption keys, sends the encrypted range to DHs via the CA, and receives the encrypted query result from the CA. Furthermore, the QU is the sole entity that obtains the plaintext of the range count.
2.3
3.2
Fully Homomorphic Encryption (FHE) is a family of cryptographic schemes that enables computations directly over encrypted data [4]. Typically, an FHE scheme supports the following homomorphic computations: i) Add-I: E(𝑚 1 ) + E(𝑚 2 ) → E(𝑚 1 + 𝑚 2 ); ii) Add-II: E(𝑚 1 ) +𝑚 2 → E(𝑚 1 +𝑚 2 ); iii) Mul-I: E(𝑚 1 ) · E(𝑚 2 ) → E(𝑚 1 · 𝑚 2 ); iv) Mul-II: E(𝑚 1 ) ·𝑚 2 → E(𝑚 1 ·𝑚 2 ), where 𝑚 1 and 𝑚 2 are plaintexts, and E(𝑚 1 ) and E(𝑚 2 ) are their corresponding FHE ciphertexts. In our proposed protocol, we employ the FHE scheme as a cryptographic tool and exploit its addition and multiplication homomorphic properties. Our protocol is instantiated using the Symmetric Homomorphic Encryption (SHE) scheme proposed by Mahdikhani et al. [26], which has been used in several searchable encryption schemes [22, 33, 42, 44]. To evaluate the impact of the underlying homomorphic encryption scheme, we additionally instantiate our protocol with the representative RLWE-based FHE scheme BFV [16] and report the comparison in our experimental evaluation. Compared with RLWE-based schemes such as BFV [16] and BGV [5], the adopted SHE scheme relies only on modular integer arithmetic instead of polynomial-ring operations, resulting in lower computational overhead and more compact ciphertexts. These properties make it particularly suitable for lightweight protocols. Despite its simplicity, the SHE scheme is CPA-secure, ensuring that encryptions of plaintexts are computationally indistinguishable. Furthermore, although symmetric, it can be converted into a publickey setting [41]. Specifically, two encryptions of zero, denoted as E(0)1 and E(0)2 , generated with different random values, are published as public parameters. Consequently, any message 𝑚 can be encrypted by a DH using these public parameters as E(𝑚) = (𝑚 +𝑟 1 ·E(0)1 +𝑟 2 ·E(0)2 ) mod N , where 𝑟 1, 𝑟 2 are random integers.
Threat Model
The QU, CA, and DHs are assumed to be honest-but-curious, i.e., they strictly follow the protocol but attempt to infer additional information from protocol execution. In particular, the QU attempts to infer DHs’ private datasets beyond the query result. The CA and each DH attempt to learn the query range submitted by the QU, the query result, or other DHs’ private datasets. We assume that the CA may collude with one or more DHs, and that DHs may collude among themselves. We also assume that the QU does not collude with the CA or any DH. Such collusion is outside the scope of our threat model because it would allow the QU to obtain intermediate protocol information through the colluding party, potentially enabling inference of additional private information from the DHs’ datasets beyond the query result.
2.4
Fully Homomorphic Encryption
Design Goal
In this work, our goal is to propose an efficient and secure protocol to compute the range count across overlapping datasets. Specifically, the following properties should be satisfied: • Accuracy: The computed range count should reflect the number of distinct records within the query range, eliminating duplicated contributions caused by overlaps among datasets. 3
Table 2: Notations in our protocol Notation
Definition
𝑅 𝑀 𝐾 𝐼 𝐷𝑖 𝐷𝑖∗ 𝑁 𝑆 𝑆′
the query range held by the QU the bit length of the Bloom filter the number of hash functions of the Bloom filter the number of DHs the private dataset held by DH 𝑖 the set of records in 𝐷𝑖 falling within 𝑅 the number of records in the union of {𝐷𝑖 }𝑖=1,...,𝐼 the counter length of the LC sketch the number of counters set to 0 in the LC sketch
3.3
To overcome this, we propose the PRP technique, which reformulates point-in-range evaluation as secure membership tests and implements them using encrypted Bloom filters. This design replaces costly secure comparisons with homomorphic multiplications, thereby improving efficiency. Concretely, the QU encodes all values in [𝑥 ℓ , 𝑥𝑟 ] into a Bloom filter BFx with 𝐾 hash functions ℎ x1, . . . , ℎ x𝐾 , and similarly encodes [𝑦ℓ , 𝑦𝑟 ] into BFy . Each bit in these filters is encrypted individually using FHE, and the encrypted Bloom filters, together with the corresponding hash functions, are sent to the DHs via the central aggregator (CA). For a record 𝑜 = (id, 𝑥, 𝑦), a DH computes the encrypted 𝑥-membership indicator by homomorphically multiplying the 𝐾 ciphertexts corresponding to indices ℎ x1 (𝑥), . . . , ℎ x𝐾 (𝑥):
Mergeable Count Estimation Sketches
E(𝐿x ) =
Mergeable count estimation sketches [13, 17, 37] are compact probabilistic data structures that estimate the union count, i.e., the number of distinct records in the union of multiple datasets. One of the most well-known sketches is the linear counting (LC) sketch [37], which provides accurate estimates for small union counts. It is suitable for scenarios such as online ride-hailing, where users query the count of nearby cars, and the count is typically small. The LC sketch comprises 𝑆 counters, all initialized to 0. Each data record 𝑜 is uniformly hashed to one of the counters using a hash function ℎ, i.e., LC[ℎ(𝑜)] = 1. Let 𝑆 ′ denote the number of zero ′ counters; the estimated count is 𝑅𝐶 = −𝑆 ln 𝑆𝑆 . To merge multiple sketches, all DHs use the same hash function ℎ, ensuring identical records map to the same counters. The sketches are then merged via the bitwise OR to counters with the same indices. The union count can be computed through the merged sketch.
4
E BFx [ℎ x𝑘 (𝑥)] ,
𝑘=1
and analogously obtains E(𝐿y ) for the 𝑦-coordinate. The encrypted in-range indicator for “𝑜 lies in the query range” is then E(𝐿) = E(𝐿x ) · E(𝐿y ), which performs the logical AND of the two membership tests. PRP eliminates costly secure comparisons and replaces them with only 𝑂 (𝐾) homomorphic multiplications per record, while revealing no information about the query range. (2) Deduplicated aggregation: How to compute the range count across overlapping DHs’ datasets without leaking any information about these datasets? Each DH now holds encrypted in-range indicators for its records after PRP. A natural method is for each DH to construct an FHE-encrypted Linear Counting (LC) sketch of length 𝑆, where every in-range record with E(𝐿) = E(1) is hashed to a counter. Each DH sends its encrypted sketch to the CA, and the CA homomorphically merges sketches by simulating bitwise OR across counters, and forwards the aggregated encrypted sketch to the QU for decryption and estimation. However, this approach faces two major limitations: (i) Efficiency: In FHE, the OR operation corresponds to ciphertext multiplication, which is computationally expensive and becomes infeasible at large scale; (ii) Privacy: If the QU directly obtains the decrypted sketch along with the LC hash function ℎ, it can conduct an inference attack. Specifically, for any record 𝑜, if ℎ(𝑜) = 𝑠 and the 𝑠-th counter is 0, then 𝑜 does not appear in any DH; otherwise, the QU learns that 𝑜 exists in at least one DH. PPRC addresses the limitations by designing the OLC scheme. OLC adapts the Linear Counting sketch [37] to the encrypted domain, introducing two key optimizations: (1) Efficiency optimization. Instead of costly homomorphic ORs, the CA aggregates LC sketches by element-wise homomorphic addition, a much cheaper operation. The aggregated encrypted sketch can be sent to the QU, who decrypts it, counts the number 𝑆 ′ of zero counters, and applies the standard LC estimator to obtain the range count: ′ 𝑅𝐶 = − 𝑆 ln 𝑆𝑆 .
PPRC PROTOCOL
In this section, we present our PPRC protocol for solving the PDRC problem. We first introduce the basic idea of PPRC in Section 4.1. We then describe its two core components, namely Private Range Predicate (PRP) and Oblivious Linear Counting (OLC). The main notations are summarized in Table 2.
4.1
𝐾 Ö
Basic Idea
The goal of PPRC is to enable a query user (QU) to obtain the count of distinct records falling within a rectangular range 𝑅 = ([𝑥 ℓ , 𝑥𝑟 ], [𝑦ℓ , 𝑦𝑟 ]) across multiple data holders (DHs), without leaking 𝑅 or the DHs’ private datasets, and while scaling to millions of records. Achieving this goal raises two technical challenges. (1) Range evaluation: How can a DH determine, in encrypted form, whether a record 𝑜 = (id, 𝑥, 𝑦) lies within the query range 𝑅 without revealing 𝑅? The goal is not for the DH to learn the plaintext range-evaluation result, but to compute an encrypted indicator E(𝐿), where 𝐿 = 1 indicates that 𝑜 lies within 𝑅 and 𝐿 = 0 otherwise. A direct approach is to encrypt the interval endpoints [𝑥 ℓ , 𝑥𝑟 ] and [𝑦ℓ , 𝑦𝑟 ] using fully homomorphic encryption (FHE), and then perform secure comparisons [38, 40, 42] of 𝑥 with [𝑥 ℓ , 𝑥𝑟 ] and 𝑦 with [𝑦ℓ , 𝑦𝑟 ] directly on the encrypted data. However, secure comparisons under FHE involve heavy cryptographic operations such as bit decomposition or polynomial evaluation. When applied to millions of records per DH, these operations incur prohibitive overhead, making such solutions impractical in practice.
(2) Privacy optimization. The above inference attack exploits the fact that counter indices and values directly reveal membership information. To prevent this leakage, the CA applies two lightweight transformations that do not alter the range count result: (i) 4
最好加文字说明，加图标表示 参与方功能
Query User
Central Aggregator
Algorithm 1: PRP Initialization Input : Query range (𝑅 = [𝑥 ℓ , 𝑥𝑟 ], [𝑦ℓ , 𝑦𝑟 ]) held by the QU, where 𝑥 ℓ , 𝑥𝑟 , 𝑦ℓ , 𝑦𝑟 ∈ N. Result : FHE keys (𝑝𝑝, 𝑠𝑘), encrypted Bloom filters E(BFx ), E(BFy ), and hash function sets Hx, Hy . 1 The QU generates the public parameters 𝑝𝑝 = (E(0)1, E(0)2 ), secret key 𝑠𝑘 for FHE; 2 The QU generates independent hash functions Hx = {ℎ x1, . . . , ℎ x𝐾 } and Hy = {ℎ y1, . . . , ℎ y𝐾 } for BFx and BFy constructions, respectively; 3 The QU sets all counters of BFx to 0 and BFy to 0; 4 foreach 𝑥 = 𝑥 ℓ , 𝑥 ℓ + 1, . . . , 𝑥𝑟 do 5 for 𝑘 = 1, . . . , 𝐾 do 6 BFx [ℎ x𝑘 (𝑥)] = 1;
Data Holder i
Generate ( pp, sk ) R BFx , BFy pp, E(BFx ), E(BFy )
PRP
pp, E(BFx ), E(BFy )
Compute E( L(ni ) ) indicating whether each on(i ) lies within R {on( i ) , E( L(ni ) )}nNi 1 E(LCi )
E(LCi )
OLC
Aggregate E(LCi ) to E(LC) Obfuscate and mask E(LC) E(LC)
foreach 𝑦 = 𝑦ℓ , 𝑦ℓ + 1, . . . , 𝑦𝑟 do for 𝑘 = 1, . . . , 𝐾 do 9 BFy [ℎ y𝑘 (𝑦)] = 1;
7
Decrypt E(LC) to obtain RC
8
Figure 2: The workflow of the PPRC protocol.
for 𝑚 = 1, . . . , 𝑀 do Encrypt BFx [𝑚] into E(BFx [𝑚]); 12 Encrypt BFy [𝑚] into E(BFy [𝑚]);
10
11
counter-index obfuscation, which permutes the order of encrypted counters so indices cannot be linked to records, and (ii) non-zero masking, which multiplies each counter ciphertext by a random non-zero plaintext scalar, preserving zero values while randomizing non-zero magnitudes. These transformations ensure the QU can only learn the final count 𝑅𝐶, but nothing about which records or DHs contributed to specific counters. In summary, PPRC integrates PRP with OLC to enable efficient, accurate, and privacy-preserving distributed range counting. PPRC follows a two-stage protocol, as illustrated in Fig. 2. In the first stage, PRP enables each DH to efficiently compute encrypted in-range indicators for its records without learning 𝑅. In the second stage, OLC securely aggregates these encrypted results to compute the final range count while correctly handling overlapping records. We next describe PRP and OLC in detail.
4.2
13 14
The QU transmits E(BFx ), E(BFy ), Hx, Hy, 𝑝𝑝 to CA; CA forwards E(BFx ), E(BFy ), Hx, Hy, 𝑝𝑝 to 𝐼 DHs;
To construct E(BFx ) for the 𝑥−dimension range [𝑥 ℓ , 𝑥𝑟 ], the QU executes the following procedure: (1) Setup (Lines 2-3). All counters BFx [𝑚] are set to 0 for 𝑚 = 1, . . . , 𝑀, and 𝐾 independent hash functions Hx = {ℎ x1, . . . , ℎ x𝐾 } are generated, each mapping 𝑥 uniformly to an index in {1, . . . , 𝑀 }. (2) Insertion (Lines 4-6). The QU inserts each 𝑥 in {𝑥 ℓ , 𝑥 ℓ +1, . . . , 𝑥𝑟 } into BFx . Concretely, for each 𝑥, the QU sets BFx [ℎ x𝑘 (𝑥)] = 1 for all 𝑘 = 1, . . . , 𝐾. (3) Encryption (Line 11). Each counter BFx [𝑚] is encrypted into E(BFx [𝑚]) using 𝑠𝑘, for all 𝑚 = 1, . . . , 𝑀. The construction of E(BFy ) follows the same procedure as E(BFx ). Together, BFx and BFy encode the query range in the two coordinate dimensions. Accordingly, the Bloom filter length 𝑀 is determined by the encoded range size and the target false-positive rate, and is independent of the DHs’ dataset size. PRP Execution. In PRP Execution, each DH 𝑖 performs range evaluation using the encrypted Bloom filter representation generated from the query range. For each record (id𝑛(𝑖 ) , 𝑥𝑛(𝑖 ) , 𝑦𝑛(𝑖 ) ) ∈ 𝐷𝑖 , DH 𝑖 computes an encrypted in-range indicator E(𝐿𝑛(𝑖 ) ), where 𝐿𝑛(𝑖 ) = 1 if the record lies within the query range, and 𝐿𝑛(𝑖 ) = 0 otherwise. This is achieved by reformulating point-in-range testing as secure membership evaluation over the transformed representation. The procedure is summarized in Algorithm 2. Concretely, we exploit homomorphic multiplications to evaluate Bloom filter membership tests. For each 𝑥𝑛(𝑖 ) , DH 𝑖 computes:
Private Range Predicate (PRP)
PRP enables each DH to evaluate whether its records satisfy the query range in encrypted form. It consists of two steps: Initialization and Execution. In the Initialization step, the QU encodes the query range 𝑅 into encrypted Bloom filters and sends them to DHs. In the Execution step, each DH performs encrypted range evaluation to compute one encrypted in-range indicator E(𝐿𝑛(𝑖 ) ) for each record 𝑜𝑛(𝑖 ) , where 𝐿𝑛(𝑖 ) = 1 indicates that 𝑜𝑛(𝑖 ) lies within 𝑅, and 𝐿𝑛(𝑖 ) = 0 otherwise. These encrypted indicators are then used as the input to OLC for computing the range count. Next, we detail the two steps. PRP Initialization. In PRP Initialization, the QU generates encrypted variables and sends them to the CA and DHs. Specifically, the QU generates the public parameters 𝑝𝑝 = (E(0)1, E(0)2 ) and secret key 𝑠𝑘 for FHE, two sets of independent hash functions for Bloom filter construction, and two encrypted Bloom filters E(BFx ), E(BFy ) representing the query range 𝑅 in the 𝑥 and 𝑦 dimensions. The QU then sends 𝑝𝑝, hash functions, and the encrypted Bloom filters to the CA, which subsequently forwards them to each DH 𝑖 = 1, . . . , 𝐼 . The pseudocode is provided in Algorithm 1.
(𝑖 ) E(𝐿x𝑛 )=
𝐾 Ö 𝑘=1
5
E(BFx [ℎ x𝑘 (𝑥𝑛(𝑖 ) )]),
Query User BFx
Algorithm 2: PRP Execution Input : Encrypted Bloom filters {E(BFx ), E(BFy )} and the 𝑁𝑖 held by DH 𝑖. records {(𝑥𝑛(𝑖 ) , 𝑦𝑛(𝑖 ) )}𝑛=1 𝑁𝑖 Result : Encrypted in-range indicators {E(𝐿𝑛(𝑖 ) )}𝑛=1 indicating whether each record lies within 𝑅. /* Each DH 𝑖 executes locally: */ 1 foreach 𝑛 = 1, . . . , 𝑁𝑖 do Î𝐾 (𝑖 ) E(BFx [ℎ x𝑘 (𝑥𝑛(𝑖 ) )]); ) = 𝑘=1 2 E(𝐿x𝑛 Î (𝑖 ) 𝐾 3 E(𝐿y𝑛 ) = 𝑘=1 E(BFy [ℎ y𝑘 (𝑦𝑛(𝑖 ) )]); (𝑖 ) (𝑖 ) (𝑖 ) ); 4 E(𝐿𝑛 ) = E(𝐿x𝑛 ) · E(𝐿y𝑛
x1( i ) {x1 , x2 }? hx2
1
E(BFx ) E(0) E(1) E(1) E(0) E(0) E(1) E(0) E(1)
hx1 0
E(1) E(1) E(1) x1( i ) {x1 , x2 }
0
hx2
hx1
1
x2( i ) {x1 , x2 } ? hx2
0
E(BFx ) E(0) E(1) E(1) E(0) E(0) E(1) E(0) E(1)
hx2 1
E(1) E(0) E(0) x2( i ) {x1 , x2 }
Figure 3: Example for checking whether 𝑥𝑛(𝑖 ) lies within {𝑥 1, 𝑥 2 } without revealing the query range. The length of the Bloom filter is 𝑀 = 8, and the number of hash functions is Rqy { y1 , y2 } 𝐾 = 2. For clarity, only the procedure for the 𝑥-coordinate is h h hq 2 hq 2 q1 illustrated; the 𝑦-coordinate isq1 processed analogously.
(𝑖 ) where 𝐿x𝑛 = 1 if 𝑥𝑛(𝑖 ) ∈ [𝑥 ℓ , xr ] and 0 otherwise. The intuition is as follows. If 𝑥𝑛(𝑖 ) ∈ [𝑥 ℓ , 𝑥𝑟 ], then for each 𝑘 = 1, . . . , 𝐾, we have (𝑖 ) BFx [ℎ x𝑘 (𝑥𝑛(𝑖 ) )] = 1, and thus 𝐿x𝑛 = 1. Conversely, if 𝑥𝑛(𝑖 ) ∉ [𝑥 ℓ , 𝑥𝑟 ], (𝑖 ) then at least one of these positions is 0, leading to 𝐿x𝑛 = 0. (𝑖 ) The computation for E(𝐿y𝑛 ), indicating whether 𝑦𝑛(𝑖 ) ∈ [𝑦ℓ , 𝑦𝑟 ], (𝑖 ) follows an analogous process, where 𝐿y𝑛 = 1 indicates 𝑦𝑛(𝑖 ) ∈ (𝑖 ) [𝑦ℓ , 𝑦𝑟 ] and 𝐿y𝑛 = 0 otherwise. Since (𝑥𝑛(𝑖 ) , 𝑦𝑛(𝑖 ) ) lies within 𝑅 if and only if (𝑥𝑛(𝑖 ) ∈ [𝑥 ℓ , 𝑥𝑟 ]) ∧ (𝑦𝑛(𝑖 ) ∈ [𝑦ℓ , 𝑦𝑟 ]), the final encrypted in-range indicator E(𝐿𝑛(𝑖 ) ) is (𝑖 ) (𝑖 ) then obtained as: E(𝐿𝑛(𝑖 ) ) = E(𝐿x𝑛 ) · E(𝐿y𝑛 ). Compared with secure comparisons under FHE, this design transforms the point-in-range evaluation into a lightweight sequence of encrypted Bloom filter lookups. The resulting encrypted in-range indicators require only 𝑂 (𝐾) homomorphic multiplications per record, making the protocol scalable in practice. Running Example. Fig. 3 illustrates the PRP with a simple example for the 𝑥-coordinate. Suppose QU encodes the range {𝑥 1, 𝑥 2 } into an encrypted Bloom filter E(BFx ) and sends it to DHs. To determine whether 𝑥 1(𝑖 ) lies within the range, DH 𝑖 computes the hash positions ℎ x1 (𝑥 1(𝑖 ) ) and ℎ x2 (𝑥 1(𝑖 ) ), retrieves the corresponding encrypted bits {E(1), E(1)} from E(BFx ), and performs homomorphic (𝑖 ) multiplication: E(𝐿x1 ) = E(1) × E(1) = E(1), indicating that 𝑥 1(𝑖 ) is within the range. For another record 𝑥 2(𝑖 ) , one of the retrieved (𝑖 ) bits equals E(0), yielding E(𝐿x2 ) = E(0), which shows that 𝑥 2(𝑖 ) is outside the range. The same procedure is then performed on the 𝑦-dimension, and a record is considered within the query range only if both dimensions satisfy their corresponding conditions.
4.3
hx1
hx1 1 {x1 , x2 }
/ /
Data Holder i
0
hd 1
E(1) E(0) E(1) E(0) E(0) E(1) E(0) E(1)
parameter determined by the target estimation accuracy and the expected range count. Each DH 𝑖 then encodes its records into the ( j) ( j) encrypted sketch by leveraging theDencrypted j {d1 , d 2 } in-range indicators (𝑖 ) (𝑖 ) E(𝐿𝑛 ) derived from PRP, hwhere 𝐿𝑛hd1 = 1h if record 𝑜𝑛(𝑖 )hqlies within 2 d1 d2 ( j) range 𝑅 and 0 otherwise. Specifically, the sketch is updated as: E( Bd ) E(1) E(0) E(1) E(0) E(1) E(0) E(0) E(1) (𝑖 ) E(LC𝑖([ℎ(𝑜 )]) = E(LC𝑖 [ℎ(𝑜𝑛(𝑖 ) )]) + E(𝐿𝑛(𝑖(d)(). i) d ( i ) , E(𝑛L( i ) )) , E( L( i ) )) 1
1
2
2
hd 2 hd 1 counter is increhd 1 For each record 𝑜𝑛(𝑖 ) , if 𝐿h𝑛d(𝑖2 ) = 1, the corresponding (i ) E( B E(0) E(0) E(1) E(0) itE(0) E(0) E( E(0) E(0) E(1) E(0) E(0) E(0) 1 ) E(1) E(0) B2( i ) ) E(0) E(1) Therefore, mented by one; otherwise, remains unchanged. only (i , j ) (i ) LC sketch ( j) (i , j ) in-range records contribute to the sketch, enabling the E( L ) E( B ) E(B ) E(1) d 2( i ) D j ( i ) ( j ) ( i ) 2 1 ) E( B ) E(B ) E(2) d D 2 d E( L 1 d 1 j to compute the range count. Multiple in-range records may hash to the same counter, which is expected in Linear Counting and Rqx a{xfixed-length enables compact representation using sketch. 1 , x2 } hq 2 (2) Secure Aggregation (Lines 8-13). Each DH 𝑖 transmits its enhq1 hq1 hq 2 crypted sketch E(LC CA E(0) thenE(1) aggregates E(𝑖B) to ) the E(0) CA. E(1) The E(0) E(1) E(0) E(1) counters with the same index across all encrypted sketches: E(LC[𝑠]) = Í𝐼 𝑖=1 E(LC𝑖 [𝑠]), 𝑠 = 1, . . . , 𝑆. To mitigate information leakage from decrypted counters, the CA applies two lightweight transformations that preserve the standard LC estimator: (i) counter-index obfuscation, which permutes the order of counters to break linkage between indices and records; and (ii) non-zero masking, which multiplies each non-zero counter by a random non-zero plaintext integer, preserving zeros while randomizing magnitudes. These lightweight transformations preserve the number of zero counters and therefore do not affect the LC estimator, which depends solely on the count of zeros. As a result, the QU can correctly recover the range count while gaining no information about individual record membership or the contributions of specific DHs, providing robustness against inference attacks with minimal computational overhead. (3) Decryption & Estimation (Lines 14-17). The CA transmits E(LC) to the QU, who decrypts it into LC using the secret key 𝑠𝑘. The QU then counts the number of zero counters 𝑆 ′ in the decrypted sketch. Following the standard Linear Counting estimator [37], the ′ fraction of zero counters 𝑆𝑆 approximates the probability that a counter remains unoccupied after all in-range records are inserted. Therefore, the number of inserted records, i.e., the range count, is estimated as 𝑆′ 𝑅𝐶 = −𝑆 ln . 𝑆
Oblivious Linear Counting (OLC)
During OLC, each DH locally constructs an encrypted LC sketch based on its records and PRP-generated encrypted indicators, the CA securely aggregates the encrypted sketches from all 𝐼 DHs, and the QU computes the final range count 𝑅𝐶 from the aggregated result. The pseudocode of OLC is given in Algorithm 3, which consists of three steps: Local Encoding, Secure Aggregation, and Decryption & Estimation. (1) Local Encoding (Lines 1-7). Each DH 𝑖 initializes its sketch LC𝑖 with all counters set to 0, and encrypts it into E(LC𝑖 ) using the public parameters 𝑝𝑝. Besides, all DHs agree on a global public hash function ℎ that maps each record uniformly into {1, . . . , 𝑆 }, where 𝑆 is the counter length of the sketch. The length 𝑆 is a tunable 6
Method 2
Algorithm 3: Oblivious Linear Counting (OLC) Input
𝑖 = 1, . . . , 𝐼 . Result : The QU obtains the range count 𝑅𝐶. /* Step 1: Local Encoding by DHs 1 All DHs agree on the global public hash function ℎ : 𝑜 → {1, . . . , 𝑆 } for sketch construction; 2 foreach DH 𝑖 = 1, . . . , 𝐼 do 3 foreach 𝑠 = 1, . . . , 𝑆 do 4 Initialize the sketch counter LC𝑖 [𝑠] = 0; 5 Encrypt LC𝑖 [𝑠] into E(LC𝑖 [𝑠]) using 𝑝𝑝; 6 7
Data Holder i
(o1(i ) ,E(1)) h(o1(i ) ) 1
𝑁𝑖 held by DH 𝑖, where : Dataset {(𝑜𝑛(𝑖 ) , E(𝐿𝑛(𝑖 ) ))}𝑛=1
E(LCi ) E(5) +E(1) E(3) E(0) E(7) +E(0) E(0) E(1)
Inserted
*/
Shuffle encrypted counters in E(LC); /* Step 3: Decryption & Estimation by QU 14 The CA sends E(LC) to the QU; 15 The QU decrypts E(LC) into LC using 𝑠𝑘; ′ 16 Count the number of zero-value counters 𝑆 in LC; 𝑆′ 17 Compute the range count: 𝑅𝐶 = −𝑆 log 𝑆 ;
Uninserted E(LCi )
Central Aggregator
E(30) E(13) E(23) E(0) E(16) E(0) E(0) E(2)
Step 2 I E(LC) E(LCi ) i 1
Permutation E(13) E(2) E(0) E(30) E(0) E(16) E(23) E(0)
E(LC[ s ]) E(LC[ s]) * Randint()
foreach 𝑛 = 1, . . . , 𝑁𝑖 do E(LC𝑖 [ℎ(𝑜𝑛(𝑖 ) )]) = E(LC𝑖 [ℎ(𝑜𝑛(𝑖 ) )]) + E(𝐿𝑛(𝑖 ) );
/* Step 2: Secure Aggregation by CA 8 Each DH 𝑖 sends its E(LC𝑖 ) to the CA; 9 foreach 𝑠 = 1, . . . , 𝑆 do 10 Aggregate encrypted sketches: Í𝐼 E(LC[𝑠]) = 𝑖=1 E(LC𝑖 [𝑠]); 11 Generate a plaintext random integer 𝑟 ; 12 Compute E(LC[𝑠]) = E(LC[𝑠]) · 𝑟 ;
Step 1
(o2(i ) , E(0)) h(o2(i ) ) 5
E(26) E(40) E(0) E(90) E(0) E(80) E(46) E(0)
E(LC)
Query User
*/
Step 3
E(26) E(40) E(0) E(90) E(0) E(80) E(46) E(0)
E(LC)
Decryption 26
40
0
90
0
80
46
0
S'3
RC S ln
S' S
Figure 4: Example for the OLC in the PPRC protocol. Here, the length of LC sketches 𝑆 is set to 8.
13
the LC sketch. Then the estimator used in PPRC satisfies
*/
ˆ ˆ 2𝛽𝑁 + 𝑤 −1𝑒 −𝑡 − 1 𝑅𝐶 𝑅𝐶 ) = E( − 1) = , 𝑅𝐶 𝑅𝐶 2𝑅𝐶 √︃ 𝑡 𝑆 ( 𝑒𝑤 − 1) ˆ ˆ − 𝑅𝐶 𝑅𝐶 𝑅𝐶 StdError( ) = Std( )= . 𝑅𝐶 𝑅𝐶 𝑅𝐶 Bias(
𝑡= . Similarly, we obtain Var(𝑆 ′ ) = E((𝑆 ′ ) 2 ) − (E(𝑆 ′ )) 2 ≈ 𝑆 −𝑡 2 𝑆𝑤𝑒 − 𝑆𝑤 𝑒 −2𝑡 . Let 𝑉 = 𝑆 ′ /𝑆 and define 𝑓 (𝑉 ) = − ln 𝑉 . Applying a secondˆ = 𝑆 𝑓 (𝑉 ) around order Taylor expansion to the LC estimator 𝑅𝐶 ˆ ˆ ≈ 𝑅𝐶 + 𝛽𝑁 + 𝑤 −1𝑒 𝑡 −1 . Therefore, Bias( 𝑅𝐶 E(𝑉 ) yields E(𝑅𝐶) 2 𝑅𝐶 ) = 𝛽 (𝑁 −𝑅𝐶 )
PPRC ANALYSIS
ˆ
2𝛽𝑁 +𝑤 −1 𝑒 −𝑡 −1
𝑅𝐶 E( 𝑅𝐶 − 1) = . 2𝑅𝐶 ˆ ≈ Using the first-order approximation further yields Var(𝑅𝐶) 𝑆 (𝑒 𝑡 /𝑤−1) . Then, taking the square root yields the standard error: 𝑅𝐶 2
In this section, we formally analyze the accuracy, efficiency, and security of the PPRC protocol.
5.1
(2)
Proof Sketch. After PRP execution, the number of objects identified within the query range is 𝑅𝐶 + 𝑟 , where 𝑟 denotes the number of false positives introduced by the two independent Bloom filters. Since each filter has a false positive rate 𝑓𝑝 , we have E(𝑟 ) = (𝑓𝑝 ) 2 𝑁 = 𝛽𝑁 . Besides, 𝑟 follows a binomial distribution: 𝑟 ∼ 𝑁 −𝑅𝐶 (𝛽)𝑟 (1 − 𝛽) 𝑁 −𝑅𝐶 −𝑟 . 𝑟 During OLC, PPRC uses the LC sketch estimator for 𝑅𝐶 + 𝑟 elements. Let 𝑆 ′ denote the number of zero counters in the aggregated sketch. Based on the standard analysis of the LC sketch, we ob 𝛽 𝑁 −𝑅𝐶 tain E(𝑆 ′ ) = 𝑆𝑤 1 − 𝑆 ≈ 𝑆𝑤𝑒 −𝑡 , where 𝑤 = (1 − 𝑆1 ) 𝑅𝐶 and
This approach enables the QU to obtain the range count without learning any individual record, thus preserving data privacy. Running Example. Fig. 4 illustrates the workflow of the OLC using an example with sketch length 𝑆 = 8. Each DH 𝑖 locally constructs an encrypted sketch E(LC𝑖 ), which encodes only the in-range records. The CA then performs secure aggregation by summing the encrypted counters across DHs, followed by counter-index obfuscation and non-zero masking, ensuring that the QU cannot infer any information about DHs’ datasets even after decryption. Finally, the QU decrypts the aggregated sketch. After decryption, the QU observes 𝑆 ′ = 3 zero counters out of 𝑆 = 8. This means that 5 counters have been occupied by hashed in-range records. Applying the LC estimator gives 𝑅𝐶 = −8 ln( 38 ), which is the estimated range count.
5
(1)
ˆ
Accuracy Analysis
√︃ 𝑡 𝑆 ( 𝑒 −1)
𝑤 StdError( 𝑅𝐶 . 𝑅𝐶 ) = 𝑅𝐶 Due to space limitations, the detailed derivation of the accuracy analysis is available in our public repository.1 □
Theorem 5.1. Suppose the true range count is 𝑅𝐶, the estimated ˆ and the false positive rate of the Bloom filters is 𝑓𝑝 . Define value is 𝑅𝐶, 𝛽 (𝑁 −𝑅𝐶 ) 2 𝛽 = (𝑓𝑝 ) , 𝑡 = , and 𝑤 = (1 − 𝑆1 ) 𝑅𝐶 , where 𝑁 is the number 𝑆 of records in the union of {𝐷𝑖 }𝑖=1,...,𝐼 and 𝑆 is the counter length of
1 https://github.com/jackson-maybe/PPRC
7
Table 3: Theoretical computation cost, communication cost, and communication rounds of PPRC. #Ciphertext Mults QU DH CA
QU
PRP OLC
– 𝑂 (𝐾𝑁 ) – –
– –
𝑂 (𝑀) – – 𝑂 (𝑆)
Total
– 𝑂 (𝐾𝑁 )
–
𝑂 (𝑀) 𝑂 (𝑆) 𝑂 (𝐼𝑀 + 𝑆)
Component
5.2
Data Sent DH CA 𝑂 (𝐼𝑀) 𝑂 (𝑆)
Proof. The proof follows the standard simulation-based security definition for semi-honest adversaries. The definition demonstrates that if a party can simulate the adversary’s view without access to any private inputs, the protocol preserves the confidentiality of private inputs without any information leakage. Let 𝑆𝑖𝑚 A denote a simulator that simulates the view of the adversary A during protocol execution. During PRP, the adversary A observes only the encrypted query Bloom filters, E(BFx ) and E(BFy ), and the encrypted indicators computed locally by DHs. Due to the CPA-security of the FHE scheme [26], all these ciphertexts are computationally indistinguishable from encryptions of random values. Therefore, a simulator 𝑆𝑖𝑚 A can efficiently generate an indistinguishable view without access to the underlying plaintexts. Furthermore, since each encrypted indicator E(𝐿𝑛(𝑖 ) ) hides its plaintext, A cannot determine whether it encrypts 0 or 1, nor test whether two ciphertexts encrypt the same plaintext. As a result, A cannot distinguish which records lie within the query range and which do not, and thus obtain no information about the query range from the encrypted indicators. In the OLC, each DH 𝑖 constructs an encrypted LC sketch E(LC𝑖 ) and the CA aggregates these encrypted sketches. During this process, the adversary A receives encrypted LC sketches from uncorrupted DHs. It is easy for 𝑆𝑖𝑚 A to generate values computationally indistinguishable from these ciphertexts based on the CPA-security of the SHE scheme. Thus, the simulator 𝑆𝑖𝑚 A can simulate the adversary’s view without private inputs, proving PPRC satisfies simulation-based security. Therefore, a semi-honest adversary corrupting up to 𝐼 DHs and the CA gains no private information. □
Rounds 2 2 4
Protocol Efficiency
We theoretically analyze the computation cost, communication cost, and communication rounds of PPRC in Table 3. The analysis is organized by the two protocol components, PRP and OLC, and further specifies the workloads of the three entities: the QU, a single DH, and the CA. Since ciphertext–ciphertext multiplications (Mul-I operations defined in Section 3.2) dominate the runtime, we use their counts (#Ciphertext Mults) to measure the computational cost, while omitting other lower-overhead operations from the asymptotic analysis. Communication cost is measured by the total amount of transmitted data, while communication rounds are measured by the number of message exchanges. PRP. The technique consists of the PRP Initialization and PRP Execution steps. In PRP Initialization, the QU encrypts the Bloom filter representation of the query range and sends it to the CA, incurring 𝑂 (𝑀) communication, where 𝑀 denotes the bit length of Bloom filters. The CA then forwards the encrypted Bloom filters to the 𝐼 DHs, resulting in 𝑂 (𝐼𝑀) data sent. No ciphertext multiplications are required in this step. In the PRP Execution, each DH locally determines whether its records fall within the query range using the encrypted Bloom filters. For each record, the DH requires 𝑂 (𝐾) ciphertext multiplications, as shown in Algorithm 2. Hence, the total computational cost is 𝑂 (𝐾𝑁 ) ciphertext multiplications per DH, where 𝑁 denotes the average number of records among the 𝐼 DHs. Since this step is performed entirely locally, it incurs no communication cost. Consequently, considering the communication flow in both steps, PRP requires two communication rounds: QU→CA→DH. OLC. After PRP, each DH securely encodes its in-range records into an encrypted LC sketch E(LC𝑖 ) of size 𝑂 (𝑆) and sends it to the CA. The CA then aggregates these encrypted sketches through elementwise addition to obtain the encrypted sketch E(LC) of size 𝑂 (𝑆), which is then sent to the QU for decryption. Benefiting from the optimized aggregation design, OLC requires no ciphertext multiplications and incurs only linear communication cost in 𝑆. Following this transmission pattern, OLC also requires two communication rounds: DH→CA→QU. Overall. The total computational cost is thus dominated by 𝑂 (𝐾𝑁 ) ciphertext multiplications at the DH, and the total communication cost is 𝑂 (𝐼𝑆 + 𝐼 𝑀). Combining the interaction patterns of PRP and OLC, the protocol requires four communication rounds.
5.3
6 EVALUATION 6.1 Experimental Setup Datasets. We evaluate PPRC on three real-world datasets: Yelp [11], Brightkite, and Gowalla [9], as well as a synthetic dataset for scalability analysis. • Real-world Datasets. Yelp is a business dataset containing merchant locations across multiple regions, and we extract 21,900 geographic records in Florida from Yelp. Brightkite and Gowalla are location-based social network datasets with 115,383 and 196,561 user check-ins. • Synthetic Dataset. We generate synthetic locations uniformly within the region of San Francisco (latitude: 37.5–37.9, longitude: −122.6–−122.2). The dataset size varies from 104 to 107 records to evaluate scalability. Following [42], we scale locations to integers, where each integer represents a 20m line, and each area corresponds to a 20m × 20m grid. Query ranges are randomly generated as rectangular regions. We use 2 km × 2 km ranges as the default setting, and evaluate the impact of different range sizes in Section 6.4. To simulate distributed data settings, each of the 𝐼 DHs receives a randomly sampled fraction 𝑃 of the global dataset as its private dataset. We set 𝑃 ∈ [0.05, 0.1, 0.15, 0.2] and 𝐼 ∈ [5, 10, 15, 20]. Due to space limitations, additional results and implementation details are available at our public repository.
Protocol Security
Theorem 5.2. When a semi-honest adversary A corrupts up to 𝐼 DHs and the CA, PPRC guarantees that A cannot access any information about the final range count result, the query range, or the private datasets of uncorrupted DHs.
Metrics. Our experiments evaluate both accuracy and efficiency. • Accuracy Metrics. We use the Mean Absolute Error (MAE) and Mean Relative Error (MRE) to assess accuracy. Let 𝑅𝐶 denote 8
2−1 5
10
I
15
20
MRE I
15
0.10
P
0.15
(e) MAE vs. 𝑃 , Yelp
21 −1
20
(b) MAE vs. 𝐼 , Brightkite
27 25 23 21
2−10.05
21 −1
2 2−3 2−5 2−7 5
211 29 27 25 3 20.05
0.20
P
0.15
10
I
15
20
0.20
21
21 −1
(f) MAE vs. 𝑃 , Brightkite
0.10
P
0.15
10
I
15
20
(d) MRE vs. 𝐼 , Brightkite
−1
2 2−3 2−5 2−70.05
MRE 0.10
2 2−3 2−5 2−7 5
(c) MRE vs. 𝐼 , Yelp
MAE
MAE
(a) MAE vs. 𝐼 , Yelp
10
LL-Count
MRE
211 29 27 25 23 5
FM-Count
2 2−3 2−5 2−70.05
MRE
27 25 23 21
RCC
MAE
MAE
PPRC
0.20
(g) MRE vs. 𝑃 , Yelp
0.10
P
0.15
0.20
(h) MRE vs. 𝑃 , Brightkite
Figure 5: Accuracy comparison with varying numbers of DHs (𝐼 ) and proportions of the global dataset held by each DH (𝑃). ˆ 𝑗 the estimated answer in the 𝑗the ground-truth count and 𝑅𝐶 th run. Then, the MAE and MRE can be calculated as: MAE = ˆ 𝑗 −𝑅𝐶 | | 𝑅𝐶 1 Í𝐽 1 Í𝐽 ˆ . 𝑗=1 |𝑅𝐶 𝑗 − 𝑅𝐶 | and MRE = 𝐽 𝑗=1 𝐽 𝑅𝐶 • Efficiency Metrics. We measure Time and Communication overhead. Time includes the end-to-end latency from generating the query range to obtaining the final plaintext range count. Communication is the total data exchanged among the QU, CA, and DHs.
randomness parameter used during encryption. The resulting 8192bit public modulus (2𝑘 0 ) provides at least 128-bit security against factorization attacks, while the 160-bit randomness (𝑘 2 ) guarantees semantic security. PPRC has bounded multiplicative depth and therefore does not require bootstrapping. For baseline methods whose circuit depth exceeds this limit, ciphertext refreshing follows the bootstrapping protocol in [44]. Unless otherwise specified, Bloom filters use 𝐾 = 7 hash functions, satisfying the SHE noise budget. The default false positive rate is set to 𝑓𝑝 = 10−4 to balance accuracy and communication costs. The Bloom filter size 𝑀 is computed using the standard formula in Section 3.1. All experiments are conducted on a local area network (LAN) with 2 Gbit/s bandwidth and an average latency of 0.076 ms. Each entity runs on a server with an Intel Xeon E5-2690 CPU (8 cores, 2.6GHz). All results are averaged over 100 runs.
Baselines. We compare PPRC with two categories of representative baselines under comparable threat models. • State-of-the-art protocols. These protocols are selected to represent the two major classes of prior privacy-preserving range counting solutions: encryption-based and MPC-based methods. We include RCC [1], which employs homomorphic encryption for bilateral privacy and securely aggregates partial counts from multiple DHs, and TVA [15], an MPC-based protocol supporting exact range counting over overlapped datasets. Since TVA produces exact results, its estimation error is omitted. • Sketch-based variants. To evaluate different sketch estimators and aggregation schemes, we implement FM-Count and LL-Count by replacing the OLC component in PPRC with secure variants of FM [17] and LogLog [13] sketches, respectively. We also implement LC-Count, which adopts the same Linear Counting estimator [37] as PPRC but uses secure bitwise-OR aggregation. As LC-Count and PPRC employ identical estimators, they achieve the same accuracy, and we therefore omit the accuracy results of LC-Count. The counter length of these sketches 𝑆 is selected from {1K, 2K, 3K, 4K}.
6.2
Accuracy Comparison
In this section, we compare the accuracy of PPRC with RCC, FMCount, and LL-Count. The results consistently show that PPRC is several times more accurate than the other protocols. The Effect of 𝐼 . Fig. 5(a)-(d) report MAE and MRE as the number of DHs varies over 𝐼 ∈ {5, 10, 15, 20}. Here we set 𝑃 = 0.1 and 𝑆 = 2K. As 𝐼 increases, MAE increases while MRE decreases for PPRC, FM-Count, and LL-count; for RCC, both the MAE and MRE increase. Furthermore, PPRC is several times more accurate than RCC, FM-Count, and LL-Count. For example, in Fig. 5(a) (Yelp dataset), PPRC reduces the MAE by an average of 55.79×, 4.90×, and 12.69× compared with RCC, FM-Count, and LL-Count, respectively. Fig. 5(b)-(d) corroborate these findings. The Effect of 𝑃. Fig. 5(e)-(h) show MAE and MRE as 𝑃 varies over {0.05, 0.1, 0.15, 0.2}, where 𝑃 denotes the proportion of each DH’s private dataset relative to the global real-world dataset. We fix 𝐼 = 10 and 𝑆 = 2K. As 𝑃 increases, PPRC, FM-Count, and LLCount exhibit increasing MAE but decreasing MRE, whereas RCC
Implementation. We implement our PPRC using C++. The hash functions we used are MurmurHash [2] with various random seeds. By default, all experiments adopt the SHE scheme [42] as the homomorphic encryption primitive. For SHE, we follow the parameter settings in [42] and set 𝑘 0 = 4096, 𝑘 1 = 80, and 𝑘 2 = 160, where 𝑘 0 denotes the modulus size, 𝑘 1 is the plaintext length, and 𝑘 2 is the
9
211 29 27 25 231K
FM-Count
2−11K
2K
S
3K
4K
(a) MAE vs. 𝑆 , Yelp
S
3K
21
21
−1
−1
2 2−3 2−5 2−71K
MRE 2K
4K
LL-Count
(b) MAE vs. 𝑆 , Brightkite
2 2−3 2−5 2−71K
MRE
27 25 23 21
RCC
MAE
MAE
PPRC
2K
S
3K
4K
(c) MRE vs. 𝑆 , Yelp
2K
S
3K
4K
(d) MRE vs. 𝑆 , Brightkite
Figure 6: Accuracy comparison with varying sketch counter lengths (𝑆).
100
10−1
5
10
I
15
20
(a) Time vs. 𝐼 , 𝑃 = 0.1, Yelp
10 10
1
100
10−1
FM-Count
5
10
I
15
20
(b) Time vs. 𝐼 , 𝑃 = 0.1, Brightkite
LL-Count
10
2
10
10
1
101
100
Time (s)
10
1
LC-Count 2
Time (s)
10
RCC
Time (s)
Time (s)
PPRC 2
TVA
2
100
10−1 0.05 0.1 0.15 0.2 P
10−1 0.05 0.1 0.15 0.2 P
(c) Time vs. 𝑃 , 𝐼 = 10, Yelp
(d) Time vs. 𝑃 , 𝐼 = 10, Brightkite
Figure 7: Time cost comparison with various 𝐼 and 𝑃. shows increases in both metrics. Besides, our PPRC remains several times more accurate than RCC, FM-Count, and LL-Count. Fig. 5(e) presents the MAE results for the Yelp dataset. On average, PPRC is 55.30, 4.79, and 12.65 times more accurate than RCC, FM-Count, and LL-Count. The other results show consistent results. The Effect of 𝑆. Fig. 6(a)-(d) evaluate the effect of the sketch counter length 𝑆 ∈ {1K, 2K, 3K, 4K} under 𝑃 = 0.1 and 𝐼 = 10. As expected, increasing 𝑆 reduces errors for all sketch-based protocols. The results for RCC remain constant, as RCC does not use sketches. PPRC is several times more accurate than RCC, FM-Count, and LL-Count. As shown in Fig. 6(a), our PPRC is on average 44.61, 4.95, and 11.03 times more accurate than RCC, FM-Count, and LL-Count. Similar trends are observed in Fig. 6(b)–(d).
6.3
communication cost of all protocols increases. As 𝑃 increases, only TVA incurs higher communication overhead, while the costs of the other protocols remain unchanged due to their use of fixed-size encrypted sketches or fixed-format query messages. Furthermore, the communication cost of PPRC is several times lower than that of LC-Count, FM-Count, LL-Count, and TVA. Specifically, Fig. 8(b) presents the Communication cost for the Brightkite dataset with various 𝐼 . On average, PPRC reduces the communication cost by 4.75, 4.79, 4.75, and 10.50 times compared with LC-Count, FM-Count, LL-Count, and TVA. Although RCC incurs lower communication costs, it is less accurate and computationally less efficient than PPRC. Consistent results are shown in Fig. 8(a), (c), and (d). The Effect of 𝑆. Fig. 9(a) evaluates the Time costs across varying sketch counter lengths 𝑆 ∈ {1K, 2K, 3K, 4K}, with 𝐼 = 10 and 𝑃 = 0.1. Since RCC and TVA do not use count estimation sketches, their costs remain constant regardless of 𝑆. While the Time cost of all sketch-based protocols increases with 𝑆. Furthermore, PPRC is dozens of times faster than the other protocols. In Fig. 9(a), PPRC is on average 9.29, 44.92, 44.79, 44.57, and 20.86 times faster than RCC, LC-Count, FM-Count, LL-Count, and TVA. Scalability Evaluation. We evaluate the scalability of our PPRC on synthetic datasets with varying total numbers of data records |𝑈 | ∈ {104, 105, 106, 107 }. Here, we fix 𝐼 = 10, 𝑃 = 0.1, and 𝑆 = 2K. Since the communication cost consists of fixed-size sketches and remains constant regardless of |𝑈 |, we report only the Time cost. Fig. 9(b) shows that the Time cost of PPRC increases linearly with |𝑈 |, aligning with theoretical analysis. In addition, the Time cost of PPRC is dozens of times lower than that of other protocols. For |𝑈 | = 107 , the Time cost of PPRC is only 88.733 s. On average, PPRC is 9.47, 13.21, 13.65, 13.33, and 25.07 times faster than RCC, LC-Count, FM-Count, LL-Count, and TVA, respectively.
Efficiency Comparison
This section evaluates the efficiency of PPRC, RCC, LC-Count, FMCount, LL-Count, and TVA. The results show that PPRC is dozens of times more efficient than the other protocols. Time Cost. Fig. 7(a)-(d) report the Time cost with respect to the number of DHs 𝐼 ∈ {5, 10, 15, 20} and the data proportion 𝑃 ∈ {0.05, 0.1, 0.15, 0.2}. We set 𝐼 = 10, 𝑃 = 0.1, and 𝑆 = 2K as default. As 𝐼 and 𝑃 increase, the Time cost of all protocols grows. Besides, PPRC is dozens of times faster than RCC, LC-Count, FM-Count, LL-Count, and TVA. For example, in Fig. 7(b) (Brightkite dataset), PPRC is on average 9.37, 33.89, 36.87, 36.36, and 30.16 times faster than RCC, LC-Count, FM-Count, LL-Count, and TVA, respectively. Consistent trends are shown in Fig. 7(a), (c), and (d). Communication Cost. Fig. 8(a)-(d) presents the Communication cost concerning 𝐼 ∈ {5, 10, 15, 20} and 𝑃 ∈ {0.05, 0.1, 0.15, 0.2}. We also set 𝐼 = 10, 𝑃 = 0.1, and 𝑆 = 2K as default. As 𝐼 increases, the 10
102 101 100
FM-Count
103
Comm (MB)
104 103 102 101 100
Comm (MB)
103
LC-Count
5
10
I
15
20
(a) Comm vs. 𝐼 , 𝑃 = 0.1, Yelp
102 101
5
10
I
15
100 0.05 0.1 0.15 0.2 P
20
(b) Comm vs. 𝐼 , 𝑃 = 0.1, Brightkite
(c) Comm vs. 𝑃 , 𝐼 = 10, Yelp
LL-Count
TVA
104 103 102 101 100 0.05 0.1 0.15 0.2 P
Comm (MB)
RCC
Comm (MB)
PPRC
(d) Comm vs. 𝑃 , 𝐼 = 10, Brightkite
Figure 8: Communication cost comparison with various 𝐼 and 𝑃. LL-Count TVA
PPRC
105
104
101
103
103
100
10−1 1K
2K
S
3K
4K
(a) Time vs. 𝑆 , Brightkite
Time (s)
102
101
10−1 104
102
105 106 |U |
101 0.05 0.1 0.15 0.2 P
107
(b) Time vs. |𝑈 | , Synthetic dataset
(a) Time vs. 𝑃
Figure 9: Time cost comparison with various 𝑆 and |𝑈 |.
TVA
104 103 102 101 100 0.05 0.1 0.15 0.2 P (b) Comm vs. 𝑃
Figure 10: Time and communication costs under various sampling proportions (𝑃), using the BFV implementation in the Microsoft SEAL library.
Performance under BFV Encryption. To demonstrate protocol generality, we replace the underlying SHE scheme with the widely used BFV scheme [16] provided by the Microsoft SEAL library [6]. This scheme uses an 8192-degree polynomial modulus and a 218-bit ciphertext modulus to ensure 128-bit security. For fair comparison, RCC adopts the same BFV configuration. The number of hash functions is set to 𝐾 = 3 to satisfy the noise budget constraint. We conduct experiments on the Brightkite dataset with 𝐼 = 20, 𝑆 = 1K, and 𝑃 ∈ {0.05, 0.1, 0.15, 0.2}, as shown in Fig. 10. As shown in Fig. 10(a), PPRC achieves the lowest runtime across all 𝑃 (7–9 seconds). This efficiency is mainly due to the batching capability of BFV, enabling SIMD-style evaluation over thousands of packed records within a single ciphertext. Besides, PPRC is up to 12.4× faster than RCC and 17.7× faster than TVA. Fig. 10(b) reports the communication overhead. TVA incurs the highest communication cost. Although RCC requires lower communication than PPRC, PPRC maintains bounded communication cost below 500 MB while achieving considerably higher accuracy and better computational efficiency. These results confirm that the efficiency advantage of PPRC does not rely on a specific FHE instantiation.
6.4
RCC
Comm (MB)
LC-Count FM-Count
Time (s)
Time (s)
PPRC RCC
expands from 1 km to 5 km (i.e., area from 1 km × 1 km square to 5 km × 5 km). PPRC demonstrates remarkable performance stability with respect to the query range size: the Time cost increases only slightly from 1.14 s to 1.50 s, even as the range expands by 25×. This is because the computational complexity of PPRC is primarily dominated by operations dependent on the number of data records, regardless of the query range size. Meanwhile, the communication cost grows from 46.1 MB to 142.3 MB. This is expected, since the encrypted Bloom filter size increases from 1.09 MB to 5.47 MB as the query range side length expands from 1 km to 5 km, resulting in higher communication costs. Impact of False Positive Rate (𝑓𝑝 ). Fig. 11(b) illustrates the tradeoff between accuracy (measured by MAE) and communication cost when varying 𝑓𝑝 from 10−2 to 10−6 . A lower 𝑓𝑝 implies higher accuracy but requires larger Bloom filters, leading to higher communication cost. We observe a sharp decline in MAE as 𝑓𝑝 decreases from 10−2 to 10−4 , where the error drops drastically from 192.6 to 28.7. However, further reducing 𝑓𝑝 beyond 10−4 yields diminishing returns. For instance, decreasing 𝑓𝑝 from 10−5 to 10−6 only reduces the MAE marginally (from 16.6 to 15.3), yet the communication cost continues to rise steadily. Therefore, we select 𝑓𝑝 = 10−4 as the optimal default parameter, as it strikes the best balance between high accuracy and low communication cost.
Parameter Analysis
We utilize the Brightkite dataset to evaluate how the query range size and the Bloom filter’s false positive rate (𝑓𝑝 ) impact the performance of PPRC. Impact of the Query Range Size. In PRP, larger query ranges require larger Bloom-filter encodings, which increases computation and communication overhead. We therefore evaluate how query range size affects overall system performance. Fig. 11(a) reports the Time and communication costs as the query range side length
7
RELATED WORK
Private geographic query (PGQ) schemes can be classified into two categories: outsourcing-data-based (OD-PGQ) and distributeddata-based (DD-PGQ). In OD-PGQ, DHs encrypt and outsource 11
1 0
150 100 50
0 1 2 3 4 5 Query Side Length (km)
(a) Results for different range sizes
300 200 100
MAE Comm.
150 100 50
0 0 10−2 10−3 10−4 10−5 10−6 False Positive Rate (fp)
they provide weaker privacy guarantees, as the released perturbed data remains close to the original data. Despite recent progress, existing DD-PGQ schemes either assume non-overlapping datasets or incur prohibitive overhead when protecting query privacy. Thus, achieving efficient, query-private, and deduplicated range counting over distributed geographic data remains an open challenge, which our work aims to address.
Comm. (MB)
2
Time Comm.
Comm. (MB) MAE
Time (s)
3
(b) Results for different 𝑓𝑝
8
Figure 11: The PPRC results for different query range sizes and Bloom filter’s false positive rates 𝑓𝑝 .
DISCUSSION
Functional extensions. Although PPRC is designed for rectangular range counting, it can be naturally extended to support arbitrary spatial regions (e.g., circular or polygonal areas), without modifying its core protocol. Specifically, Geohash-based encoding [19] and prefix compression [25] can represent target regions as compact prefix sets, which are directly compatible with the existing PRP and OLC design. Beyond the extension, another important future direction is to optimize PPRC for single-source range counting and single-point queries, which are naturally supported by our framework but are not the primary focus of this work. Supporting multiple QUs. Although PPRC is described under a single-QU setting, it can be extended to support multiple QUs because each query execution is independent. Concurrent requests can therefore be handled through the standard request-level parallelization at the DHs. To mitigate potential information leakage when the same QU submits multiple queries, PPRC can be complemented with standard orthogonal mechanisms such as query auditing, privacy-budget enforcement, rate limiting, or differential privacy. Besides, batch query scheduling and preprocessing of query-independent data structures can further improve the overall system throughput without changing the core protocol design in high-throughput settings. Extension beyond geographic data. While motivated by geographic range counting, PPRC is not inherently restricted to geographic data. Its design only assumes that records can be represented as points in a multidimensional domain and that queries can be formulated as bounded multidimensional ranges. Under this abstraction, PPRC can naturally support other range-counting scenarios, such as healthcare, sensor, and business analytics, without changing the core protocol.
their datasets to a third party, which processes user queries over the protected data. In DD-PGQ, multiple DHs retain their datasets locally and jointly process user queries. OD-PGQ. Early works like CryptDB [27] utilize Order-Preserving Encryption (OPE) to encrypt the plaintext, which is later shown to be vulnerable to inference attacks [35]. Subsequent works improve index structures for secure range queries [21, 24, 35]. With the development of location-based services, [10, 36] design secure schemes to support geographic keyword queries. However, they are limited to the Boolean keyword test, i.e., determining whether a query keyword set is fully contained in a given keyword set. To address this, Song et al. [29] and Zhang et al. [42] design secure schemes supporting geographic keyword similarity queries based on Euclidean similarity and Jaccard similarity, respectively. TVA [15] supports deduplication to the encrypted database and thus supports more complicated queries. More recently, Zhang et al. [40] improve the flexibility by supporting arbitrary query ranges. Beyond encrypted databases, OD-PGQ systems also utilize Function Secret Sharing (FSS) [12] and trusted execution environments like Intel SGX [3, 43]. However, these systems typically rely on outsourced computation with non-colluding servers or trusted hardware. In contrast, our setting assumes that each DH retains its data locally, which is common in cross-organizational applications where raw datasets cannot be outsourced due to privacy or regulatory constraints. DD-PGQ. In practical scenarios, geographic queries often span private datasets held by multiple DHs who are unwilling to outsource data due to privacy concerns, rendering OD-PGQ approaches unsuitable. To address this, DD-PGQ schemes have been proposed. Shi et al. [28] first investigate approximate range aggregation queries without privacy considerations, followed by Hu-fu [31], the first DD-PGQ scheme based on cryptographic tools. Zhang et al. [39] introduce efficient and secure algorithms for approximate k-nearest neighbor queries across distributed datasets. RCC [1] supports exact range queries while protecting the privacy of the query range. To alleviate this bottleneck, recent works [8, 23] incorporate differential privacy (DP) [14]. Their core idea is to release DP-perturbed values. Li et al. [23] introduce FedGroup, a private range counting scheme that combines cryptographic tools with DP to securely group DHs and adds DP noise at the group level. Chen et al. [8] propose U-DPAP, a DP-only range counting scheme. This scheme groups similar data and injects noise into the groups. While offering improved efficiency, they are less accurate than cryptography-based solutions due to noise injection into the query result. Moreover,
9
CONCLUSION
In this paper, we propose PPRC, the first protocol for Private Distributed Range Counting (PDRC) that simultaneously achieves accuracy across overlapping datasets, bilateral privacy, and practical efficiency. PPRC adopts a secure sketching framework that integrates a secure range predicate (PRP) with an efficient aggregation scheme (OLC). Specifically, PRP reformulates secure point-in-range evaluation as a secure membership test using encrypted Bloom filters, enabling efficient range evaluation without disclosing the query range. OLC securely aggregates overlapped partial results through lightweight cryptographic additions while ensuring no leakage beyond the final count. We provide a formal analysis of the accuracy, efficiency, and security of PPRC. Experiments on realworld and synthetic datasets demonstrate that PPRC achieves up to 55× lower errors and 37× faster performance compared to baseline protocols, establishing it as a practical solution to PDRC. 12
REFERENCES
[25] Rui Li, Alex X Liu, Huanle Xu, Ying Liu, and Huaqiang Yuan. 2020. Adaptive secure nearest neighbor query processing over encrypted data. IEEE Transactions on Dependable and Secure Computing 19, 1 (2020), 91–106. [26] Hassan Mahdikhani, Rongxing Lu, Yandong Zheng, Jun Shao, and Ali A. Ghorbani. 2020. Achieving O(log3 n) Communication-Efficient Privacy-Preserving Range Query in Fog-Based IoT. IEEE Internet of Things Journal 7, 6 (2020), 5220–5232. [27] Raluca Ada Popa, Catherine MS Redfield, Nickolai Zeldovich, and Hari Balakrishnan. 2011. CryptDB: Protecting confidentiality with encrypted query processing. In SOSP. 85–100. [28] Yexuan Shi, Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Bolin Ding, and Lei Chen. 2021. Efficient approximate range aggregation over large-scale spatial data federation. IEEE Transactions on Knowledge and Data Engineering 35, 1 (2021), 418–430. [29] Fuyuan Song, Zheng Qin, Liang Xue, Jixin Zhang, Xiaodong Lin, and Xuemin Shen. 2021. Privacy-preserving keyword similarity search over encrypted spatial data in cloud computing. IEEE Internet of Things Journal 9, 8 (2021), 6184–6198. [30] Feiyang Sun, Pinghui Wang, Junzhou Zhao, Nuo Xu, Juxiang Zeng, Jing Tao, Kaikai Song, Chao Deng, John CS Lui, and Xiaohong Guan. 2021. Mobile data traffic prediction by exploiting time-evolving user mobility patterns. IEEE Transactions on Mobile Computing 21, 12 (2021), 4456–4470. [31] Yongxin Tong, Xuchen Pan, Yuxiang Zeng, Yexuan Shi, Chunbo Xue, Zimu Zhou, Xiaofei Zhang, Lei Chen, Yi Xu, Ke Xu, et al. 2022. Hu-fu: Efficient and secure spatial queries over data federation. PVLDB 15, 6 (2022), 1159. [32] Yongxin Tong, Yuxiang Zeng, Yang Song, Xuchen Pan, Zeheng Fan, Chunbo Xue, Zimu Zhou, Xiaofei Zhang, Lei Chen, Yi Xu, et al. 2025. Hu-Fu: efficient and secure spatial queries over data federation. The VLDB Journal 34, 2 (2025), 19. [33] Xinqi Tu, Haiyong Bao, Rongxing Lu, Cheng Huang, and Hong-Ning Dai. 2023. PMRK: Privacy-preserving multidimensional range query with keyword search over spatial data. IEEE Internet of Things Journal 11, 6 (2023), 10464–10478. [34] Paul Voigt and Axel Von dem Bussche. 2017. The eu general data protection regulation (gdpr). Springer International Publishing 10, 3152676 (2017), 10–5555. [35] Peng Wang and Chinya V Ravishankar. 2013. Secure and efficient range queries on outsourced databases using Rp-trees. In ICDE. 314–325. [36] Xiangyu Wang, Jianfeng Ma, Ximeng Liu, Robert H Deng, Yinbin Miao, Dan Zhu, and Zhuoran Ma. 2020. Search me in the dark: Privacy-preserving boolean range query over encrypted spatial data. In INFOCOM. 2253–2262. [37] Kyu-Young Whang, Brad T Vander-Zanden, and Howard M Taylor. 1990. A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Systems 15, 2 (1990), 208–229. [38] Haining Yu, Hongli Zhang, Xiaohua Jia, Xiao Chen, and Xiangzhan Yu. 2021. pSafety: Privacy-preserving safety monitoring in online ride hailing services. IEEE Transactions on Dependable and Secure Computing 20, 1 (2021), 209–224. [39] Kaining Zhang, Yongxin Tong, Yexuan Shi, Yuxiang Zeng, Yi Xu, Lei Chen, Zimu Zhou, Ke Xu, Weifeng Lv, and Zhiming Zheng. 2023. Approximate k-nearest neighbor query over spatial data federation. In DASFAA. 351–368. [40] Songnian Zhang, Rongxing Lu, Hui Zhu, Yandong Zheng, Yunguo Guan, Fengwei Wang, Jun Shao, and Hui Li. 2024. Performance Enhanced Secure Spatial Keyword Similarity Query With Arbitrary Spatial Ranges. IEEE Trans. Inf. Forensics Secur. 19 (2024), 5272–5285. [41] Songnian Zhang, Rongxing Lu, Hui Zhu, Yandong Zheng, Yunguo Guan, Fengwei Wang, Jun Shao, and Hui Li. 2024. Performance enhanced secure spatial keyword similarity query with arbitrary spatial ranges. IEEE Transactions on Information Forensics and Security 19 (2024), 5272–5285. [42] Songnian Zhang, Suprio Ray, Rongxing Lu, Yunguo Guan, Yandong Zheng, and Jun Shao. 2022. Efficient and privacy-preserving spatial keyword similarity query over encrypted data. IEEE Transactions on Dependable and Secure Computing 20, 5 (2022), 3770–3786. [43] Xinyi Zhang, Qichen Wang, Cheng Xu, Yun Peng, and Jianliang Xu. 2024. FedKNN: Secure Federated k-Nearest Neighbor Search. SIGMOD (2024), 1–26. [44] Yandong Zheng, Rongxing Lu, Yunguo Guan, Jun Shao, and Hui Zhu. 2021. Efficient and privacy-preserving similarity range query over encrypted time series data. IEEE Transactions on Dependable and Secure Computing 19, 4 (2021), 2501–2516. [45] Laura C Zwiers, Diederick E Grobbee, Alicia Uijl, and David SY Ong. 2024. Federated learning as a smart tool for research on infectious diseases. BMC Infectious Diseases 24, 1 (2024), 1327.
[1] Rasoul Akhavan Mahdavi, Haoyan Ni, Dimitry Linkov, and Florian Kerschbaum. 2023. Level up: Private non-interactive decision tree evaluation using levelled homomorphic encryption. In CCS. 2945–2958. [2] Austin Appleby. 2008. Murmurhash. https://sites.google.com/site/murmurhash (2008). [3] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. 2017. Prochlo: Strong privacy for analytics in the crowd. In SOSP. 441– 459. [4] Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. 2018. Fast Homomorphic Evaluation of Deep Discretized Neural Networks. In CRYPTO, Vol. 10993. Springer, 483–512. [5] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory 6, 3 (2014), 13:1–13:36. [6] Hao Chen, Kim Laine, and Rachel Player. 2017. Simple encrypted arithmetic library-SEAL v2. 1. In International conference on financial cryptography and data security. 3–18. [7] Jihong Chen and Jiabin Sun. 2021. Understanding the chinese data security law. International Cybersecurity Law Review 2, 2 (2021), 209–221. [8] Yahong Chen, Xiaoyi Pang, Xiaoguang Li, Hanyi Wang, Ben Niu, and Shengnan Hu. 2025. U-DPAP: Utility-aware Efficient Range Counting on Privacy-preserving Spatial Data Federation. SIGMOD 3, 1 (2025), 1–25. [9] Eunjoon Cho, Seth A Myers, and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In SIGKDD. 1082–1090. [10] Ningning Cui, Jianxin Li, Xiaochun Yang, Bin Wang, Mark Reynolds, and Yong Xiang. 2019. When geo-text meets security: Privacy-preserving boolean spatial keyword queries. In ICDE. 1046–1057. [11] Yelp dataset. [n.d.]. [Online]. https://www.kaggle. com/yelp-dataset/yelp-dataset ([n. d.]). [12] Emma Dauterman, Mayank Rathee, Raluca Ada Popa, and Ion Stoica. 2022. Waldo: A private time-series database from function secret sharing. In SP. 2450–2468. [13] Marianne Durand and Philippe Flajolet. 2003. Loglog counting of large cardinalities. In European Symposium on Algorithms. 605–617. [14] Cynthia Dwork. 2006. Differential privacy. In International colloquium on automata, languages, and programming. 1–12. [15] Muhammad Faisal, Jerry Zhang, John Liagouris, Vasiliki Kalavri, and Mayank Varia. 2023. { TVA } : A multi-party computation system for secure and expressive time series analytics. In USENIX Security. 5395–5412. [16] Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive (2012). [17] Philippe Flajolet and G Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences 31, 2 (1985), 182–209. [18] Shahabeddin Geravand and Mahmood Ahmadi. 2013. Bloom filter applications in network security: A state-of-the-art survey. Computer Networks 57, 18 (2013), 4047–4064. [19] Ruoyang Guo, Bo Qin, Yuncheng Wu, Ruixuan Liu, Hong Chen, and Cuiping Li. 2021. Luxgeo: Efficient and security-enhanced geometric range queries. IEEE Transactions on Knowledge and Data Engineering 35, 2 (2021), 1775–1790. [20] Erin Illman and Paul Temple. 2019. California consumer privacy act. The Business Lawyer 75, 1 (2019), 1637–1646. [21] Panagiotis Karras, Artyom Nikitin, Muhammad Saad, Rudrika Bhatt, Denis Antyukhov, and Stratos Idreos. 2016. Adaptive indexing over encrypted numeric data. In SIGMOD. 171–183. [22] Beibei Li, Ziqing Zhu, Linghao Zhang, Zhengwei Chang, Liang Zhao, and Arun Kumar. 2023. EPPSQ: Achieving efficient and privacy-preserving statistics queries over encrypted data in smart grids. Future Generation Computer Systems 149 (2023), 265–279. [23] Maocheng Li, Yuxiang Zeng, and Lei Chen. 2023. Efficient and accurate range counting on privacy-preserving spatial data federation. In DASFAA. 317–333. [24] Rui Li, Alex X Liu, Ann L Wang, and Bezawada Bruhadeshwar. 2015. Fast and scalable range query processing with strong privacy protection for cloud computing. IEEE/ACM Transactions On Networking 24, 4 (2015), 2305–2318.
13