arXiv CSopen access

Efficient and Privacy-Preserving Distribution Statistics Analytics on Mobile Spatial Data

IEEE TRANSACTIONS ON MOBILE COMPUTING

1

Efficient and Privacy-Preserving Distribution Statistics Analytics on Mobile Spatial Data

arXiv:2605.25791v1 [cs.CR] 25 May 2026

Xuhao Ren, Chuan Zhang, Member, IEEE, Mingyang Zhao, Ruichen Zhang, Member, IEEE, Liehuang Zhu, Senior Member, IEEE, Dusit Niyato, Fellow, IEEE, Bin Xiao, Fellow, IEEE

Abstract—With the rapid development of mobile computing technology, massive amounts of spatial data are continuously generated from various mobile terminals and sensing devices, such as smartphones, connected vehicles, and drones. Performing efficient distributed statistical analysis on this data is crucial for real-time mobile computing applications. However, the constrained and dynamic nature of mobile environments exacerbates the privacy challenge: centralizing sensitive data for analysis risks severe privacy leaks, while existing privacypreserving techniques often introduce excessive overhead or inaccuracies In this paper, we design, implement, and evaluate the first system that supports efficient and privacy-preserving distribution statistics analysis for mobile spatial data. First, we propose eSpat-B, which leverages two non-colluding servers and a newly designed improved distributed point functions (DPF) with octree partitioning. Furthermore, considering the frequent updates of spatial data, we propose another more efficient scheme, eSpat+. The core idea of this scheme is to utilize a K-Dimensional tree for spatial partitioning, combine it with incremental DPF for performing statistics analysis, and design an efficient update algorithm. Security analysis demonstrates that our schemes effectively protect data privacy throughout the statistical process. Theoretical analysis and experimental results on real-world mobile trajectory datasets demonstrate that our proposed schemes achieve a reduction of approximately 1.2× in computation overhead, 20× in communication overhead, and maintain 100% accuracy. Index Terms—Spatial distribution statistics analysis, distributed point functions, privacy-preserving

I. I NTRODUCTION

T

HE proliferation of mobile and IoT devices has led to an explosion of spatial data—characterized by latitude, longitude, and often altitude—generated continuously from vehicles, drones, smartphones, and other moving entities [1]. In mobile computing paradigms, this type of continuously updated, location-aware data stream is essential for a wide range of dynamic applications, such as real-time traffic management This work is supported by the National Natural Science Foundation of China (Grant No. 62472032), and the Young Elite Scientists Sponsorship Program by CAST (Grant No. 2023QNRC001). Xuhao Ren, Chuan Zhang, and Liehuang Zhu are with the School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing 100081, China, and also with the Shandong Key Laboratory of Energy Industry Internet Big Data Technology, Jinan 250003, Shandong, China. Email: {xuhaor, chuanz, liehuangz}@bit.edu.cn. Mingyang Zhao and Bin Xiao are with the Department of Computing, The Hong Kong Polytechnic University, Hong Kong. Email: [email protected] and [email protected]. Ruichen Zhang and Dusit Niyato are with the College of Computing and Data Science, Nanyang Technological University, Singapore. Email: {ruichen.zhang, dniyato}@ntu.edu.sg. Chuan Zhang is the corresponding author.

in connected vehicles [2], environmental sensing via mobile sensors [3], and responsive urban planning [4]. Analyzing the distribution of such data through spatial statistics provides valuable insights into movement patterns, density hotspots, and resource utilization across geographic regions [5]–[7]. The core task of spatial distribution statistics analysis can be defined as: given a stream or set of mobile spatial data points (e.g., vehicle locations and UAV trajectories) [8] and a predefined spatial partitioning (grid or region), to efficiently and accurately compute statistical summaries—such as density, coverage, or frequency—over these partitions. For instance, a mobility service may analyze vehicle distribution to optimize fleet allocation; a city operator might assess crowd density across zones for public safety management [9], [10]. However, conducting such statistical analysis typically requires collecting data at a central server, which raises serious privacy concerns in mobile contexts [11]–[14]. Mobile spatial data often contains sensitive trajectory and location information, and its exposure could lead to tracking, profiling, or other security breaches [15]. A straightforward solution is to encrypt data before uploading, but this introduces significant computational and communication overhead. Moreover, dynamic and streaming nature of mobile data demands efficient handling of frequent updates—a challenge overlooked by many static privacy-preserving methods. Inaccurate or delayed statistics analysis in mobile scenarios can directly impact system performance and safety. For example, inefficient routing in vehicular networks may increase travel time and energy consumption, while imprecise UAV location analytics could raise collision risks or lead to violations of no-fly zones. Therefore, achieving efficient, accurate, and privacy-preserving distribution statistics analysis over mobile spatial data in practical, resourceconstrained environments remains a critical challenge. Some privacy-preserving techniques can be applied to achieve spatial distribution statistics analysis, including searchable encryption (SE) [22]–[27], privacy-preserving range queries (PPRQ) [16], [28]–[31], and private statistics [17], [32]–[34]. Firstly, SE enables querying encrypted data while preserving privacy. For example, Chamani et al. [35] introduced a blockchain-based multi-user SE scheme that preserves data/query privacy with high efficiency, while Le et al. [36] further optimized multi-user searchable encryption by concealing all statistical information. In the PPRQ domain, Tong et al. [28] proposed a distributed point functions (DPF)-Bloom filter scheme for privacy-preserving Boolean range queries, and Huang et al. [37] enhanced scalability via DPF-scrambled Bloom filters for multi-client keyword search. However, when

IEEE TRANSACTIONS ON MOBILE COMPUTING

2

TABLE I C OMPARISON WITH RELATED WORKS Schemes

Security Primitives

PPRQ [16]

Symmetric encryption

PPDA [17]

Homomorphic encryption

DDP [18]

Differential privacy

Prio [19]

Multi-party computation

Sketch [20]

N/A

Standard DPF [21]

Function secret sharing

Our scheme

Function secret sharing

3D Statistics

applied to spatial distribution statistics analysis, these methods generate per-region indexes and match all spatial data, yielding redundant results that degrade statistical efficiency. Finally, in private statistics, approaches like those proposed by Guo et al. [32] introduce the SketchPolymer, which efficiently estimates the tail contributors of items in a data stream through early filtering and value split sharing techniques. Furthermore, Boneh et al. [38] introduced a system for securely computing heavy hitters in a two-server setting to prevent obtaining sensitive data directly. Based on this, Mouris et al. [39] significantly improved communication efficiency by introducing a threeserver setting. However, the above works focus on one or twodimensional data, limiting their applicability to spatial data. Afterwards, Hong et al. [40] proposed a perturbation mechanism designed to minimize the expected error of perturbed locations. Cunningham et al. [41] proposed a local differential privacy mechanism based on perturbed trajectory data, which solves the problem of output limitation and low practicality of existing mechanisms due to their failure to incorporate users’ independent public knowledge. Although privacy protection is achieved in a lightweight way, the introduction of noise leads to inaccurate statistical results [42], [43]. In summary, there is a lack of an efficient distribution statistical scheme for spatial data that can achieve privacy protection. Based on the above requirements, we design the first system that supports efficient and privacy-preserving distribution statistics analysis for spatial data, which comprises two schemes. To be specific, we design the scheme, eSpat-B, based on improved DPF, where DPF is combined with octree partitioning and regions are divided using Gray code to achieve privacy protection. To further improve efficiency, we also present an advanced scheme, eSpat+, which is designed using K-Dimensional (KD)-tree encoding, incremental DPF, and an efficient update algorithm. Table I shows the comparison of our scheme with previous works in terms of requirements. In summary, the main contributions of this paper are: We explore and analyze the challenges and requirements for privacy-preserving spatial distribution statistics analysis, and propose a system that ensures spatial data privacy while achieving efficient and accurate statistics analysis. • We propose a basic spatial data distribution statistics analysis scheme, eSpat-B. Specifically, eSpat-B encodes space using Gray code and combines the DPF with octree partitioning to design an improved DPF algorithm. This scheme allows for the generation of key shares •

Privacy

High Efficiency

Accuracy

that are distributed across two non-colluding servers and ensures data privacy while enabling efficient distribution of statistics. • To further improve the performance of spatial distribution statistics analysis and update efficiency, we design an advanced scheme called eSpat+. Specifically, we encode space using a KD-tree and leverage incremental DPF to protect privacy. In addition, considering the frequent updates of spatial data, we design an efficient update algorithm that reduces overhead by optimizing updates within the same parent region. • We perform extensive security analysis to validate the robustness of our schemes and demonstrate their efficiency through extensive experiments, confirming their practical applicability and high performance. The rest of the paper is structured as follows. Section III presents the background of our scheme. We provide the related work in Section II. In Section IV, we give a problem formulation of our scheme, including the system model, threat model, definitions of our work, and design goals. We give the scheme details in Section V, followed by a security analysis in Section VI. Next, performance evaluation is discussed in Section VII. Finally, we conclude this paper in Section VIII. II. R ELATED W ORK In this part, we introduce some existing technologies that can be used to achieve privacy-preserving spatial distribution statistics analysis. A. Searchable Encryption Searchable encryption (SE) allows for the efficient retrieval of encrypted data while preserving the privacy of both the encrypted data and the search queries [44], [45]. Boneh et al. [46] introduced the idea of asymmetric searchable encryption, also known as Public-Key encryption with Keyword Search (PEKS), and developed the initial PEKS system utilizing bilinear mapping. Subsequently, to cater to diverse user requirements, searchable encryption schemes capable of fulfilling a range of functions have been progressively put forward. Golle et al. [47] initially introduced a PEKS scheme enabling connected keyword searches, significantly enhancing search result accuracy. Curtmola et al. [48] enhanced the index structure of SE to boost retrieval efficiency and introduced the initial SE system utilizing an inverted index for this purpose. Tong et al. [49] employed Bloom filters and KSW encryption to enable

IEEE TRANSACTIONS ON MOBILE COMPUTING

privacy-preserving Boolean range queries. They also used CP-ABE to establish fine-grained temporary access control, thereby improving the security of encrypted data. Liang et al. [50] used the enhanced CSC Bloom filter structure to achieve efficient retrieval, addressing the common issues of high false positives and identifier correlation found in traditional Bloom filters. To prevent malicious cloud servers from falsifying partial search results, Li et al. [51] used homomorphic MAC and random challenge methods to authenticate the accuracy and completeness of the results. SE can be used to achieve privacy distribution statistics analysis. Specifically, we can first store the UAV location in the server through encryption technology, and then use SE to retrieve UAV information within a specific range, and then perform statistics analysis. However, since the UAV location is updated in real-time, the server storage overhead will increase, because all locations need to be retrieved before statistics are performed, which reduces the statistical efficiency. B. Privacy-Preserving Range Query A privacy-preserving range query involves an encrypted query range and a collection of encrypted values. It aims to disclose all encrypted values within the encrypted query range without compromising the confidentiality of the query range and values. Tong et al. [52] and Song et al. [53] used similar product coding and curve fitting techniques to encode the query range and query value into two vectors. Subsequently, they utilized an enhanced kNN approach to encrypt the vectors for retrieval purposes. Gong et al. [54] transform spatial information into vectors using Gray coding and Bloom filtering. They employ an enhanced kNN approach to secure the vectors for enabling Boolean range queries. Nevertheless, as kNN is vulnerable to known plaintext attacks [55], [56], the security of the aforementioned schemes is inadequate. Guan et al. [57] enhanced the security of the query scheme by introducing a method for detecting rectangular distance intersections. They achieved this by incorporating inner product-preserving encryption and utilizing encryption techniques involving bilinear mapping and Bloom filters. Wang et al. [58] used symmetric homomorphic encryption (SHE) to encrypt both the query range and value. They utilized two servers to determine the size of the ciphertext to execute the range query. Tong et al. [49] and Miao et al. [59] transformed spatial data into vectors using distinct conversion techniques and applied KSW and SHE for secure retrieval, respectively. While these approaches enable secure range queries, both SHE and traditional symmetric encryption methods incur significant computational overhead, leading to reduced query efficiency. To enhance the security and effectiveness of range queries, Wang et al. [60] and Miao et al. [61] used symmetric key hidden vector encryption [62] to encrypt both the data and the converted vectors of the query range. Private distribution statistics analysis can be achieved through range queries. Specifically, an index is first generated for each statistical area, and then the location is matched with all indices. This will generate a large number of useless intermediate results, resulting in a waste of computing resources and low statistical efficiency.

3

C. Private Data Statistics If the server needs to calculate a collection of all client strings, the involved parties can utilize a dual-server mixing network [63]. In this setup, each client encrypts her string with onion encryption to two servers, who then shuffle and decrypt the group of strings, respectively. Employing verifiable shuffles [64] is essential to prevent any misconduct by the servers. An alternative approach involves employing a universally secure two-party computation [65]–[67] for the RAM program. In this method, each client shares an extra secret component of its input string with every server. Subsequently, the servers execute a universally secure multi-party computation on the RAM program. This computation processes inputs (one string from each client) and determines the quantity of heavy hitters present. The count-min sketch [19] is a data structure designed for identifying approximate heavy hitters within streaming algorithms. In a study by Melis et al. [20], it was demonstrated that secure aggregation methods could enable each client to anonymously input its string into a data structure. In cases where the specific heavy hitters are not predetermined, such as in our scenario, a series of n-like counting data structures (with each client managing an n-bit string) can be employed to tally the heavy hitters. Obviously, the above private data statistics analysis can only process one-dimensional data and cannot process three-dimensional data, such as UAV locations. III. BACKGROUND A. Gray Code Gray Code [68], [69], also known as Reflected Binary Code, is a special form of binary encoding, characterized by the fact that only one binary bit changes between adjacent codes. A d-dimensional Gray code can be represented as shown below, with ′ |′ being the concatenation operator and Gd representing the vector of a Gray code instance at step d. For example, G1 = (0, 1), and d > 1, Gd = (g1 , g2 , . . . , g2d ), Gd+1 = (0|g1 , 0|g2 , . . . , 0|g2d , . . . , 1|g2d , . . . , 1|g1 ). As shown in Fig. 1, this is a two-dimensional spatial code. In a D × D grid, the Gray code needed to represent all cells has a length of 2⌈log2 D⌉ . For a spatial point U , we represent the Gray code of U as gU ← Gray(U ). To perform statistical analysis in three-dimensional space, we adopt the encoding method outlined in this paper: G3 = (000, 001, 011, 010, 110, 111, 101, 100). In the quad-tree partition, each internal node divides the current spatial region into four child regions, and each leaf node represents a final spatial subregion; the Gray code is used to encode the root-toleaf path, thereby assigning a unique Gray-code-based index to each leaf region. B. Distributed Point Functions (DPF) The DPF introduced in [21] is modeled by a function fx,y whose output is non-zero only when the input matches the fixed string x; for every other input, the result is identically zero. Concretely, a two-party DPF over a finite field F is realized by the following pair of algorithms: λ • DPF.Gen(1 , x, y) → (k0 , k1 ): on input a security parameter λ, an index string x ∈ {0, 1}n , and a payload value

IEEE TRANSACTIONS ON MOBILE COMPUTING

00

01

11

10

00

0000

0001

0011

0010

01

0100

0101

0111

0110

11

1100

1101

1111

1110

10

1000

1001

1011

1010

4

𝑣0

𝑣00

U0 U1

𝑣01

𝑣000 𝑣001 𝑣010

U2

𝑣10

𝑣0′

+

𝑣11

𝑣011 𝑣100 𝑣101 𝑣110

𝐄𝐯𝐚𝐥(𝐤 𝟎 ,⋅)

𝑣111

′ 𝑣00

′ 𝑣000

𝑣1′

′ 𝑣01

′ ′ 𝑣001 𝑣010

′ 𝑣10

′ 𝑣11

′ ′ ′ ′ 𝑣101 𝑣011 𝑣100 𝑣110

𝐄𝐯𝐚𝐥(𝐤 𝟏 ,⋅)

𝜷𝟏

0

= ′ 𝑣111

0

0

0

0

0

0

0

0

𝜷𝟐

0

𝜷𝟑

0

Sum of 𝐄𝐯𝐚𝐥(⋅) results

Fig. 2. For instance, with a depth of n = 3, a designate point α = 110, the values on the path are β1 ∈ G1 , β2 ∈ G2 , β3 ∈ G3 within specific finite groups G1 , G2 , G3 , and the key generation is denoted as Gen(α, β1 , β2 , β3 ) → (k0 , k1 ).

U0 : 0110 U1 : 1100 U2 : 1001 U0 U1

Gray Code

𝑣1

U2

Quad-tree

•

Fig. 1. Example of Quad-tree and Gray code. The left part depicts a Quadtree, a hierarchical data structure that recursively partitions a two-dimensional spatial region into four child nodes. The right part shows the Gray code assigned to the leaf cells of the Quad-tree.

y ∈ F, this routine produces two correlated keys k0 and k1 . ′ ′ • DPF.Eval(i, kb , x ) → yb : given party identifier b ∈ {0, 1}, a key kb , and any x′ ∈ {0, 1}n , the algorithm returns the share yb′ . The correctness requirement for the two-party DPF is expressed as follows. ( y, if x′ = x ′ ′ DPF.Eval(k0 , x ) + DPF.Eval(k1 , x ) = . 0, otherwise (1) Theorem 3.1 (Security of DPF [21]): When a party P0 or P1 is compromised by a PPT adversary A, there is a PPT algorithm SIM such that the outputs of the two experiments below cannot be distinguished computationally, given the leakage of the point function f ’s input and output sizes, i.e., LDP F (f ) = (|x|, |y|) : DP F λ • REAL (1 ): Output (DP F.Gen(1λ , x, y)) → (k0 , k1 ); DP F λ • IDEAL (1 ): Output SIM (1λ , LDP F (f )). Notice that Eq. 1 is computed in the finite field F. The security property of the DPF suggests that an attacker who acquires either k0 or k1 (but not both) cannot learn any details about the point α or its corresponding value β. C. Incremental Distributed Point Functions A typical DPF [21] effectively splits a non-zero vector of size 2n at a specific point. The standard DPF divides the data into a binary tree structure where one leaf node stores a nonzero value β, with the remaining nodes holding zeros. This method entails distributing a unique value β at each index. Conversely, the incremental DPF distributes values at every index prefix. (Refer to Fig. 2) Specifically, a two-party incremental DPF scheme, defined by a finite group G1 , . . . , Gn , comprises two procedures: λ • IDPF.Gen(1 , α, β1 , . . . , βn ) → (k0 , k1 ). Given a security parameter λ, a string α ∈ {0, 1}n and values β1 ∈ G1 , . . . , βn ∈ Gn , output two incremental DPF keys.

IDPF.Eval(i, ki , x) → Gl . For party index b ∈ {0, 1}, an incremental DPF key kb , and prefix x ∈ {0, 1}l , this algorithm outputs a secret-shared value located at index x. The computation is split into two internal routines: EvalNext advances the current state while producing the next share, and EvalPrefix delivers the corresponding share ybl .

For all α ∈ {0, 1}n , output values β1 , . . . , βn ∈ G, keys (k0 , k1 ), the following equation holds: ( βl , x ∈ α , IDPF.Eval(k0 , x) + IDPF.Eval(k1 , x) = 0, otherwise (2) where the x has a length of l, and the operation is conducted within the finite group Gl . D. KD-Tree KD-tree [70] is a tree structure designed for processing kdimensional spatial data, where k is the spatial dimension. Every node partitions the space along a specific dimension and allocates the data to its left and right child nodes. The partitioning method of the KD-tree is as follows. During the construction process, the median of a dimension is usually selected as the partition point to ensure the balance of the tree. • In each layer, the partitioning dimensions are selected in a cyclic order to ensure that the data in each dimension can be effectively partitioned. •

Let us take the two-dimensional plane as an example. As shown in Fig. 3, some points are randomly selected as the division criteria. The horizontal line is the x-axis. The left side of the x-axis is the point whose horizontal coordinate is less than the coordinate, and the right side is the point whose vertical coordinate is greater than the coordinate. The vertical line is the y-axis. The upper side of the y-axis is the point whose vertical coordinate is greater than the coordinate, and the lower side is the point whose vertical coordinate is less than the coordinate. IV. P ROBLEM F ORMULATION In this section, we introduce the system and threat model examined in our work. It then outlines the definition of eSpat.

IEEE TRANSACTIONS ON MOBILE COMPUTING

5

x-axis y-axis

𝑝4

𝑝5

𝑝8

𝑝9

𝑝2 𝑝1

𝑝3

𝑝7

𝑝6

𝑝3

𝑝10 𝑝1

𝑝2

𝑝4

𝑝5

𝑝10 𝑝8

𝑝1

𝑝2

𝑝9

Fig. 3. The figure demonstrates the recursive space-partitioning mechanism of a KD-tree in a two-dimensional plane. Left: The coordinate plane with explicitly labeled x-axis and y-axis. The space is first split by a vertical line at a selected median x-coordinate, dividing the region into left and right subregions. Each subregion is then further divided by a horizontal line at a median y-coordinate, and the process continues alternately between axes. The resulting axis-aligned partitions are shown, with example data points distributed within the cells. Right: The corresponding binary tree representation, where each internal node denotes a split along one axis and leaf nodes represent the final partitions.

A. System Model and Threat Model System model. Our scheme consists of three entities: clients, cloud servers, and the requester. • Clients. Each client is responsible for uploading spatial data and utilizing an improved DPF to generate key shares that protect privacy. By using key sharing, the uploaded data can be securely processed by the servers without exposing the original spatial data. • Cloud servers. The two servers receive key shares uploaded by the client and perform aggregation on the shares without accessing the spatial data, thereby ensuring privacy protection. After completing the aggregation, the servers send the results to the requester for the final synthesis of the distribution statistics. • Requester. The requester receives the aggregated results from two servers and performs the final statistics analysis of these results to obtain the distribution of spatial data. Threat model. We assume that the client is honest, i.e., it accurately uploads real-time spatial data information as requested; the server and requester are assumed to be semihonest. That is, although the server and requester follow the protocol to perform calculations, they may try to infer specific data from the received information. To ensure privacy, we consider that the two servers do not collude and therefore process the data independently [38], [71]–[74]. This assumption is commonly made in two-server privacy-preserving computation and can be instantiated by deploying the two servers under independent administrative domains.1 . B. Definitions Let D = {p1 , p2 , . . . , pn } denote a set of spatial data records, where each pi represents a location point in the spatial domain. Given a query region R, the goal of spatial distribution statistics in this paper is to compute the number of data records located within R. Formally, the output is a single count cR = |{pi ∈ D | pi ∈ R}|. 1 To prevent collusion, incentive mechanisms based on game theory [75] can be designed to penalize malicious cooperation and encourage honest behavior, which we leave as future work.

Thus, in this work, the term “distribution” specifically refers to count-based spatial statistics over queried regions. Each query returns the number of records in the specified region, rather than a density, frequency, or a count vector over all regions. We focus on the count result because it is the fundamental statistic for spatial distribution analysis and directly reflects the number of records within the queried region. Density or frequency can be further derived from the count when the region size or total number of records is available, while returning a count vector over all regions would provide broader information than required by a single query. Based on the above model, we define an efficient spatial data distribution statistics analysis scheme called eSpat. In eSpat, we first partition the statistical space into multiple sub-areas, each assigned a unique code. Clients map their spatial data to these encoded sub-areas and generate key shares (k0 , k1 ). The server aggregates these shares via secure distributed computation and returns partial results to the requester, who then merges them to obtain the complete statistical distribution. Definition 1 (eSpat): eSpat consists of three algorithms: • Setup(): This function generates a pseudo-random generator and a pseudo-random group element in G by transforming a random string of length λ. • eSpat.KeyGen(λ, α, β) → (k0 , k1 ): With a security parameter denoted as λ, a string represented by α, and values β, this algorithm provides keys (k0 , k1 ). • eSpat.Eval(b, kb , x) → yb : This algorithm takes as input server b, along with corresponding key kb , and string x. It generates a value yb . Since spatial data is constantly updating, clients need to upload updated data in real-time. Generally, clients need to upload a key to offset the old data information, and then reupload the new key for the updated data. C. Design Goals The main design goal is to achieve efficient spatial distribution statistics analysis while protecting the privacy of spatial data. Specifically, the design goals of the proposed scheme are summarized as follows. • Confidentiality. The scheme ensures the privacy of spatial data while preventing specific information from being inferred from statistical results. • Functionality. The scheme supports accurate spatial data distribution statistics analysis, allowing clients to share spatial data in a private manner. • Efficiency. We design the scheme to minimize computational and communication overhead, enabling timely spatial distribution statistics analysis. V. P RIVACY-P RESERVING D ISTRIBUTION S TATISTICS In this section, we first propose a scheme called eSpat-B based on the Gray code and octree. To improve performance, we design another spatial distribution statistics analysis scheme called eSpat+ based on incremental DPF, which is introduced in detail below. The workflow is illustrated in Fig. 4.

IEEE TRANSACTIONS ON MOBILE COMPUTING

6

Gray Code and Key Generation

Key Evaluation and Processing (0)

k10 → Server 0 k11 → Server 1

encode

Server 0

′ ′ sRRL t ′RRL sRRR t ′RRR

′ ′ sLLL t ′LLL sLLR t ′LLR

(𝐬𝐋𝐋𝐋 ∥ 𝐭 𝐋𝐋𝐑 ∥ ⋯ ||𝐬𝐑𝐑𝐋 ∥ 𝐭 𝐑𝐑𝐋 𝐬𝐑𝐑𝐑 𝐭 𝐑𝐑𝐑 ) ⊕ [𝐭 𝐥−𝟏 ⋅ 𝐤 𝐍 𝐛]

kN 0 → Server 0 k1N → Server 1

s1

Data Points

division

k10 → Server 0 k11 → Server 1

division

k 20 → Server 0 k12 → Server 1

kN 0 → Server 0 k1N → Server 1 Data Points

Aggregation

PRG

(0)

(0)

t1

PRG Server 1

 KD-tree and Key Generation

3d-spatial

(0)

t0

k 20 → Server 0 k12 → Server 1

encode

3d-spatial

s0

′′ ′′ ′′ sLLL t ′′ LLL sLLR t LLR

′′ ′′ ′′ sRRL t ′′ RRL sRRR t RRR

 Key Evaluation and Processing (0)

s0

Server 0

sL′

t ′L

 Aggregation

(0)

t0

PRG sR′

The value of black circle is the number of clients in each spatial.

t ′R (𝐬𝐋 ∥ 𝐭 𝐋 ∥ 𝐬𝐑 ∥ 𝐭 𝐑 ) ⊕ [𝐭 𝐥−𝟏 ⋅ 𝐤 𝐍 𝐛]

(0) (0) s1 t1

Server 1

sL′′

t ′′ L

PRG sR′′

t ′′ R

Fig. 4. Workflow of eSpat-B and eSpat+. In eSpat-B shown in the upper part, step ① maps spatial data to Gray-code-based octree indices and generates DPF key shares. In eSpat+ shown in the lower part, step ① performs KD-tree-based spatial division and generates prefix-oriented incremental DPF key shares. Steps ② and ③ are similar in both schemes: the two non-colluding servers evaluate the received key shares, and the requester aggregates the returned partial results to obtain the final statistics.

A. eSpat-B: Basic eSpat Scheme 1) Main Idea: Each client uploads key shares, generated through a key generation algorithm, to two servers, which aggregate the shares for distribution statistics analysis on spatial data. If standard DPF is used to perform spatial distribution statistics, it incurs high computational overhead due to its binary tree structure. Since spatial data distribution statistics analysis requires tripling the tree height, the efficiency of DPF is heavily constrained by this factor [21], [38]. To overcome this limitation, we improve DPF by integrating Gray code for spatial encoding and utilizing an octree structure for indexing sub-regions, which reduces computational complexity and enhances efficiency for three-dimensional spatial distribution statistics analysis. To construct our scheme, each spatial data point is encoded as gU ← Gray(U ) (U is the spatial data point), and the statistical area is divided accordingly. Each parent area is divided into 8 subareas (3 bits define a spatial area), ensuring that the parent code is a common prefix of subarea codes. The client then generates two key shares via eSpat.KeyGen and sends them to the servers, which use eSpat.Eval to aggregate key shares. The requester computes the final statistical result. 2) Scheme Details: eSpat-B mainly consists of three steps: key generation, data processing, and data statistics. Each client possesses a spatial data encoding α, which is encoded using Gray code. We will now elaborate on the specifics of the distribution statistics analysis process. Setup: This step establishes a pseudo-random generator G : {0, 1}λ → {0, 1}8λ+8 and a pseudo-random group element in G that transforms a random string of length λ denoted as ConvertG′ : {0, 1}λ → G′ , where G′ := {0, 1}λ × G. Key generation. In this step, each client generates keys to

safeguard the privacy of spatial data. Specifically, each client derives a spatial data code α using Gray code and generates key shares through eSpat.KeyGen. These key shares are then transmitted to the cloud servers. eSpat.KeyGen(1λ , α, β) → (k0 , k1 ): The client decomposes the data encoding α into a bit sequence (α1 , α2 , . . . , αn ). For each bit αi , its value (e.g., 000, 001, 010) determines a Keep path for the correct path and generates Lose paths for incorrect ones (Alg. 1 Lines 7-23), where LLL, LLR, . . . , RRL, RRR denote eight directions in the octree. The client starts by generating random seeds (0) (0) (0) s0 and s1 for two servers and sets control bits t0 = 0 (0) and t1 = 1. During the main loop, the client processes each bit αi , applying XOR operations to combine selected Keep and Lose paths. This path information is accumulated in sCW [i] and tCW [i] (Alg. 1 Lines 25-30). Next, once the entire bit sequence is processed, the accumulated path data is used to generate final key shares k0 and k1 , where CW (l) is the correction words of lth layer. The detailed algorithm is shown in Alg. 1. Data processing. The server b receives key shares from each client and utilize eSpat.Eval to aggregate them. Next, each server sends the aggregated results to the requester. eSpat.Eval(b, kb , x) → yb : This algorithm is conducted by servers and is responsible for computing and aggregating the key shares kb from each client to obtain the partial result of the statistical spatial x. Each server first decomposes kb into the initial seed s(0) , control bit t(0) , and correction words CW (l) for each level. Then, each server iteratively processes each bit xl , selecting the Keep path (representing the correct path) or Lose paths (representing incorrect paths) based on the bit value, thereby updating the data information τ (l) . At each

IEEE TRANSACTIONS ON MOBILE COMPUTING

Algorithm 1: eSpat.KeyGen λ

Input: 1 , α, β Output: k0 , k1 n 1 Set α = α1 , . . . , αn ∈ {0, 1} be the bit decomposition, where αi ∈ (000, 001, . . .); (0) (0) λ λ 2 Select randomly s0 ← {0, 1} and s1 ← {0, 1} ; (0) (0) 3 Let t0 = 0 and t1 = 1; 4 for l = 1 to n do LLL LLR LLR RLL RLL RRR 5 sLLL b ||tb ||sb ||tb || . . . ||sb ||tb ||sb (l−1) RRR 6 ||tb ← G(sb ) for b = 0, 1; 7 if αl = 000 then 8 Keep ← LLL, Lose1 ← LLR,. . ., 9 Lose4 ← RLL,. . .,Lose7 ← RRR; 10 end 11 if αl = 001 then 12 Keep ← LLR, Lose1 ← LLL,. . ., 13 Lose4 ← RLL, . . .,Lose7 ← RRR; 14 end 15 . . .; 16 if αl = 101 then 17 Keep ← RRL, Lose1 ← LLL,. . ., 18 Lose4 ← RLL, . . ., Lose7 ← RRR; 19 end 20 if αl = 100 then 21 Keep ← RRR, Lose1 ← LLL,. . ., 22 Lose4 ← RLL, . . .,Lose7 ← RRL; 23 end 24 sKeep CW ← 0; 25 for i = 1 to 7 do Lose[i] Lose[i] 26 sCW [i] ← s0 ⊕ s1 , Lose[i] Lose[i] 27 tCW [i] ← t0 ⊕ t1 , Keep 28 sKeep CW ← sCW ⊕ sCW [i] , 29 end Keep 30 tKeep ⊕ tKeep ⊕ 1; 1 CW ← t0 (l) (l−1) Keep 31 tb ← tb ⊕ tb · tKeep CW for b = 0, 1; (l) (l−1) Keep 32 sb ← sb ⊕ tb · sKeep CW for b = 0, 1; Keep Keep (l) 33 CW ← sCW ||tCW ||sCW [1] ||tCW [1] ||sCW [2] ||tCW [2] || . . . ||sCW [7] ||tCW [7] ; 34 end n (n) (n) (n+1) 35 CW ← (−1)t1 [β−Convert(s0 )+Convert(s1 )]; (0) (0) (1) 36 Let kb ← sb ||tb ||CW || . . . ||CW (n+1) for b = 0, 1; 37 return (k0 , k1 )

level, each server parses the path fragments sLLL , sLLR , . . . according to the current bit xl and updates the values of s(l) and t(l) . After completing all levels, the algorithm uses the final seed s(n) , control bit t(n) , and final path information CW (n+1) to compute the output yb (Alg.2 Line 18). The resulting yb is the aggregated partial statistical result based on the key shares. Next, servers send yb to the requester. The specific algorithm is presented in Alg. 2. Data statistics and update. After receiving the aggregated results, the requester can obtain the distribution of spatial data

7

Algorithm 2: eSpat.Eval Input: b, kb , x Output: yb (0) (0) 1 Parse kb = s ||t ||CW (1) || . . . ||CW (n+1) ; 2 for l = 1 to n do Keep 3 Parse CW (l) = sKeep CW ||tCW ||sCW [1] ||tCW [1] ||sCW [2] ||tCW [2] || . . . ||sCW [7] ||tCW [7] ; 4 τ (l) ← G(s(l−1) ) ⊕ (t(l−1) · CW (l) ); 5 Parse τ (l) = sLLL ||tLLL ||sLLR ||tLLR || . . . ||sRRL ||tRRL ||sRRR 6 ||tRRR ∈ {0, 1}8λ+8 ; 7 if xl = 000 then 8 s(l) ← sLLL ,t(l) ← tLLL ; 9 end 10 if xl = 001 then 11 s(l) ← sLLR , t(l) ← tLLR ; 12 end 13 . . .; 14 if xl = 100 then 15 s(l) ← sRRR , t(l) ← tRRR ; 16 end 17 end b (n) 18 yb = (−1) [Convert(s ) + t(n) · CW (n+1) ] ∈ G; 19 return yb

as follows: ( eSpat.Eval(k0 , x) + eSpat.Eval(k1 , x) =

1, 0,

x=α . (3) x ̸= α

When the spatial data changes, it updates the data by generating two key shares. First, the client generates key shares to offset the old data and sends them to the server to remove its influence from the statistics of the original data. Then, the client generates new key shares representing the updated data and sends these key shares to the server for aggregation. Specifically, the client generates the offset key share through the eSpat.KeyGen(1λ , αold , −1), and then calculates the new key share through eSpat.KeyGen(1λ , αnew , 1) again. B. eSpat+: Incremental DPF-Based Scheme 1) Differences and Improvements: Firstly, compared to the basic scheme, eSpat+ encodes the statistical region using a KD-tree, a multidimensional spatial segmentation structure that divides space into sub-regions. This approach reduces redundancy in region segmentation. By improving spatial indexing efficiency, KD-tree encoding enables faster positioning and statistics processing. Secondly, eSpat+ utilizes incremental DPF to implement prefix statistics. While the standard DPF in the basic scheme handles precise data statistics, the incremental DPF enables prefix matching, allowing for the simultaneous processing of multiple sub-regions. This enhancement facilitates the direct calculation of statistical results for multiple areas during range statistics, significantly boosting efficiency. Finally, eSpat+ incorporates an efficient update mechanism to address the frequent position changes of spatial data. Unlike

IEEE TRANSACTIONS ON MOBILE COMPUTING

the basic scheme, which requires a complete update of key shares for every position change, eSpat+ updates only the key share for the affected area once. Since spatial data is often confined to small shifts between sub-areas, focusing on these movements during updates improves efficiency by approximately 50%, making the system more suitable for realtime spatial applications. Compared with eSpat-B, eSpat+ improves update efficiency by exploiting prefix sharing in the KD-tree partition. In eSpat-B, each updated spatial record is encoded as a complete spatial index, and the corresponding DPF keys need to be regenerated and evaluated for that complete index. Therefore, updates are handled at the granularity of individual encoded points or regions. In contrast, eSpat+ organizes the spatial domain as a KD-tree, where each node represents a spatial subregion and the path from the root to the node forms a prefix. The incremental DPF operates on these prefixes. When a spatial record is inserted, deleted, or modified, only the prefixes associated with the affected KD-tree subregions need to be updated. Unaffected subregions keep their previous states and do not need to be recomputed. Moreover, if multiple updated records fall under the same parent region, they share the same prefix in the KD-tree. In this case, eSpat+ can aggregate these updates at the shared prefix level, avoiding repeated DPF generation and evaluation for each individual record. This prefix-based update mechanism reduces both computation and communication overhead, which explains the better update efficiency of eSpat+. 2) Detailed Scheme Construction: Similar to eSpat-B, eSpat+ also mainly includes key generation, data processing, and statistics. In the construction of the eSpat+ solution, the core is to adopt a static and publicly available KD-tree as the spatial index structure. The dividing points of all internal nodes of this tree are predetermined and made public during the system initialization. These dividing points are selected based on the median to ensure the generation of a balanced depth and evenly partitioned index tree. The specific choice of split points within the KD-tree does not affect the cryptographic correctness or privacy guarantees of the computation. Instead, these points define the spatial granularity and boundaries of the statistical query itself, which are predetermined by the system or specified by the requester based on the analysis needs (e.g., dividing a city into administrative districts or uniform grids). Each internal node splits a spatial region along one dimension, and each branch corresponds to one partitioning decision. Therefore, the path from the root to any node defines a prefix, where each bit records the left/right branching decision at one KD-tree split. Each prefix represents the spatial subregion associated with that node. Incremental DPF uses these prefixes to update only the affected subregions, thereby avoiding recomputation over the entire spatial domain. Setup. In Alg. 3, a 3-dimensional tree is constructed by recursively dividing the point set to create a hierarchical structure. The algorithm begins by determining the splitting axis based on the current depth, cycling through the x, y, and z axes. It then sorts the points along the current axis and selects the median point as the node. The point set is split into left and right subsets, and the algorithm recursively builds the

8

left and right subtrees, incrementing the depth at each level to switch the splitting axis. Recursion stops when no points remain, resulting in a balanced 3D tree. Additionally, similar to the Setup in eSpat-B, a pseudo-random generator G is established: G : {0, 1}λ → {0, 1}2λ+2 , and ConvertG′ → G′ . Algorithm 3: 3D-Tree Construction Input: A set of points in 3D space, depth = 0 Output: Root of the constructed 3D KD-Tree 1 Function BuildKDTree(points, depth): 2 if points is empty then 3 return NULL; 4 5 6 7 8

9

10

axis = depth mod 3; Sort points by the current axis; median = len(points)//2; node = newN ode(points[median]); node.lef t = BuildKDTree(points[:median], depth + 1); node.right = BuildKDTree(points[median + 1:], depth + 1); return node;

Key generation. In Alg. 4, the client initializes random (0) (0) (0) (0) seeds s0 and s1 , sets control bits t0 and t1 , and defines the initial depth as 0. For each level l, the client determines the splitting axis (cycling through x, y, and z axes), selects a Keep path based on its coordinate, and accumulates the path information for both Keep and Lose paths. Similar to eSpat-B, (l) (l) this process updates strings sb and tb . After all levels are processed, the accumulated information is used to generate final key shares. Then, the client generates new key shares when spatial data (0) (0) is updated. It initializes random seeds s0 and s1 , and control (0) (0) bits t0 = 0 and t1 = 1. The client calls eSpat+.KeyGen three times: first for the public region R(x0 , y0 , z0 ), then for the old range R(x′ , y ′ , z ′ ) to remove its influence, and finally for the updated range R(x′′ , y ′′ , z ′′ ) to include the new data. The client then combines the key shares and correction words into k0 , k1 , and pp, ppold , and ppnew . Details refer to Alg. 5. Data processing. Each server interprets the input key share and the correction word set pp to statistically analyze the distribution of the range R(x), R(y), R(z), where R(·) denotes · > node.value. The server initializes the depth and processes the seed and CW (l) . It then selects the axis based on the current depth, and compares the node’s coordinates with the specified range. Depending on whether the node coordinates fall within the range, the server chooses the left (L) or right (R) path, updating the state with sL , tL or sR , tR . After processing all levels, the server returns the final result ybl and stl . The detailed algorithm is shown in Alg. 6. Next, each server performs prefix statistics by calling eSpat+.EvalNext at each level, using the previous key share and the current CW (j) along with the range. This produces updated results (stjb , ybj ) at each level (Alg. 7 Line 5). After iterating through all levels, the server returns the accumulated

IEEE TRANSACTIONS ON MOBILE COMPUTING

Algorithm 4: eSpat+.KeyGen λ

Input: 1 , ((x0 , y0 , z0 ), (G1 , β1 ), . . . , (Gn , βn )) Output: k0 , k1 , pp (0) (0) λ λ 1 s0 ← {0, 1} and s1 ← {0, 1} ; (0) (0) 2 t0 = 0 and t1 = 1, depth = 0; 3 for l = 1 to n do (l−1) 4 sLb ||tLb ||sRb ||tRb ← G(sb ) for b = 0, 1; 5 axis = depth mod 3; 6 if axis = 0 then 7 if x0 < node.x then 8 Keep ← Lef t, Lose ← Right; 9 else 10 Keep ← Right, Lose ← Lef t; 11 end 12 end 13 else if axis = 1 then 14 if y0 < node.y then 15 Keep ← Lef t, Lose ← Right; 16 else 17 Keep ← Right, Lose ← Lef t; 18 end 19 end 20 else 21 if z0 < node.z then 22 Keep ← Lef t, Lose ← Right; 23 else 24 Keep ← Right, Lose ← Lef t; 25 end 26 end 27 sCW ← sLose ⊕ sLose 0 1 ; L L L 28 tCW ← t0 ⊕ t1 ⊕ αl ⊕ 1, tRCW ← tR0 ⊕ tR1 ; (l) (l−1) 29 tb ← tKeep ⊕ tb · tKeep CW for b = 0, 1; b (l) (l−1) Keep 30 s̃b ← sb ⊕ tb · sCW for b = 0, 1; (l) (l) (l) 31 sb ||Wb ← ConvertGl (s̃b ) for b = 0, 1; (l) (l) (l) (l) 32 WCW ← (−1)t1 · [βl − W0 + W1 ]; (l) 33 CW (l) ← sCW ||tLCW ||tRCW ||WCW ; 34 depth + +; 35 end (n) ′ (n) (n) ′ (n) ′ ′ 36 s0 = s0 , s1 = s1 , t0 = t0 , t1 = t1 ; (0) 37 Let kb ← sb for b = 0, 1; (1) 38 Let pp ← CW , . . . , CW (n) ; ′ ′ ′ ′ 39 return (k0 , k1 , pp), (s0 , s1 , t0 , t1 )

result ybl , which represents the partial statistical result. In Alg. 8, when the spatial data is updated, the server evaluates the new data and ensures the correctness of the aggregation results. The server initializes s(0) = kb and t(0) = b, and interprets the common correction words set pp, along with old and new information ppold and ppnew . The server first processes the common data by calling eSpat+.EvalNext for each layer, then separately evaluates the old and new data, adjusting the result by subtracting the impact of old data. The final updated result yb,new is returned. Data statistics. Similar to eSpat-B, the requester can obtain

9

Algorithm 5: eSpat+.MoveGen Input: 1λ ,((R(x0 , y0 , z0 ),(G1 ,β1 ),. . . ,(Gm ,βm )), (R(x′ , y ′ , z ′ ),(Gm+1 ,βm+1 ),. . . ,(Gn ,βn )), ′ (R(x′′ , y ′′ , z ′′ ),(Gm+1 ,βm+1 ),. . . ,(Gn ,βn′ ))) Output: k0 , k1 , pp, ppold , ppnew (0) R (0) R λ λ 1 s0 ←− {0, 1} and s1 ←− {0, 1} ; (0) (0) 2 Let t0 ← 0 and t1 ← 1; 3 (s0 , s1 , t0 , t1 , pp) ← eSpat+.KeyGen (1λ , (R(x0 , y0 , z0 ), (G1 , β1 ), . . . , (Gm , βm ))); 4 (s0 , s1 , t0 , t1 , ppold ) ← eSpat+.KeyGen (1λ , (R(x′ , y ′ , z ′ ), (Gm+1 , βm+1 ), . . . , (Gn , βn ))); (s0 , s1 , t0 , t1 , ppnew ) ← eSpat+.KeyGen ′ (1λ , (R(x′′ , y ′′ , z ′′ ), (Gm+1 , βm+1 ), . . . , (Gn , βn′ ))); (0) 5 Let kb ← sb for b = 0, 1; 6 return (k0 , k1 , pp, ppold , ppnew )

the spatial distribution of spatial data by directly adding the partial results ybl from the two servers. VI. T HEORETICAL A NALYSIS In this section, we theoretically analyze the security and complexity of eSpat-B and eSpat+. A. Security Analysis In this part, we analyze the security of eSpat-B and eSpat+. Then, we prove that both schemes can protect data privacy. Theorem 6.1: eSpat-B and eSpat+ can protect the privacy of spatial data if the keys are indistinguishable from the perspective of the servers. Proof: Following the standard simulation-based security framework and hybrid-argument technique for DPF/FSS-based two-server protocols [21], [76], [77]. We prove the privacy of the proposed schemes by reducing it to the security of the underlying DPF primitive under the semi-honest and noncolluding two-server model. Let ViewSb denote the view of server Sb , where b ∈ {0, 1}. For each execution, ViewSb consists of the public parameters, the key shares received from users, the local evaluation results computed by Sb , and the messages sent to the requester. Since the two servers are assumed to be non-colluding, each server only observes its own key shares and local computation results. For eSpat-B, each spatial record is first encoded into a spatial index according to the Gray-code-based spatial encoding. The client then generates two DPF keys for this encoded point and sends one key to each server. By the security of DPF, any single DPF key is computationally indistinguishable from a key generated for any other point in the same domain. Therefore, for any two spatial records p0 and p1 , the key share received by a single server in an execution for p0 is computationally indistinguishable from that in an execution for p1 . Since the local evaluation result for a server is computed deterministically from its received key and public parameters, it does not reveal any information beyond the server’s key share. Thus, the view of each server is computationally indistinguishable for different spatial records.

IEEE TRANSACTIONS ON MOBILE COMPUTING

Algorithm 6: eSpat+.EvalNext Input: b, stl−1 b , ppl , R(x), R(y), R(z) Output: stl , ybl l−1 1 Interpret stb = s(l−1) ||t(l−1) ; (l−1) 2 Interpret G(s ) = ŝL ||t̂L ||ŝR ||t̂R ; (l) 3 Interpret CW = sCW ||tLCW ||tRCW ||WCW ; l 4 τ ← (ŝL ||t̂L ||ŝR ||t̂R ) ⊕ (t(l−1) · [sCW ||tLCW ||sCW ||tRCW ]); l L L R R 2λ+2 5 Interpret τ = s ||t ||s ||t ∈ {0, 1} ; axis = l mod 3; if axis = 0 then 8 if R(x) == (x < node.x) then 9 s̃(l) ← sL , t(l) ← tL ; 10 else 11 s̃(l) ← sR , t(l) ← tR ; 12 end 13 end 14 else if axis = 1 then 15 if R(y) == (y < node.y) then 16 s̃(l) ← sL , t(l) ← tL ; 17 else 18 s̃(l) ← sR , t(l) ← tR ; 19 end 20 end 21 else 22 if R(z) == (z < node.z) then 23 s̃(l) ← sL , t(l) ← tL ; 24 else 25 s̃(l) ← sR , t(l) ← tR ; 26 end 27 end (l) (l) 28 s ||W ← ConvertGl (s̃(l) ); l (l) (l) 29 st ← s ||t ; l b (l) 30 yb ← (−1) · [W + t(l) · WCW ]; l l 31 return (st , yb ) 6 7

More formally, suppose there exists a probabilistic polynomial-time adversary A that can distinguish the view of a server in eSpat-B generated from two different spatial records with non-negligible advantage. Then, we can construct a distinguisher B against the underlying DPF. Given a DPF challenge key corresponding to one of two possible points, B embeds this key as the server-side key share in the simulated execution of eSpat-B and generates all other public information honestly. If A distinguishes which spatial record was used, B can distinguish which DPF key was generated, contradicting the key indistinguishability of DPF. The argument for eSpat+ is analogous, except that the spatial domain is represented by KD-tree prefixes and the client uses IDPF keys to support prefix-based evaluation. Each KD-tree node corresponds to a spatial subregion, and the rootto-node path defines the prefix used in IDPF. By the security of IDPF, the key share held by any single server is computationally indistinguishable for different prefixes. Therefore, a single server cannot infer which KD-tree prefix, and hence

10

which spatial subregion, is associated with the user’s data beyond the public information. If a server-side adversary could distinguish two different prefixes in eSpat+, it would directly yield a distinguisher against the IDPF primitive. Consider a sequence of hybrid executions in which the DPF/IDPF keys generated for the real spatial records are replaced one by one with keys generated for alternative records or prefixes. Each adjacent pair of hybrids differs only in one DPF/IDPF key share. By the key indistinguishability of the underlying DPF/IDPF, these two hybrids are computationally indistinguishable to any single server. By a standard hybrid argument, the real execution is computationally indistinguishable from the final hybrid execution. Therefore, each server’s view contains no information about users’ spatial records other than the public parameters and the final aggregate statistics disclosed to the requester. Hence, under the semi-honest and non-colluding two-server assumption, the privacy of eSpat-B and eSpat+ follows from the security of the underlying DPF and IDPF primitives, respectively. Theorem 6.1 is thus proven. B. Complexity Analysis As shown in Table II, we compare the complexity between eSpat, DPF, and other schemes that can be used to achieve spatial data distribution statistics analysis. The key symbols used in the table are defined as follows: N denotes the total number of clients, M represents the number of spatial regions, n is the bit-length of the spatial data encoding string, and l is the prefix length involved in a query (l ≤ n). The term |B| is a parameter specific to the LiangTC [50], indicating the size of its Bloom filter. For computational cost, TEXP , Tpair , TP RF , TAES , and TP RG denote the time units for performing a modular exponentiation, a bilinear pairing, a pseudorandom function (PRF) evaluation, an AES encryption/decryption, and a pseudorandom generator (PRG) operation, respectively. The storage or communication overhead is measured in units of the security parameter λ. In terms of computational complexity for KeyGen, the LiangTC [50] requires O(|B| + N )TEXP , incurring costs linear in both its Bloom filter size and the number of clients, and relies on expensive modular exponentiation. The LiangTIFS [78] has a complexity of O(N n + M )TP RF + O(M )TAES , involving both PRF and AES operations. The standard DPF [21] requires O(n2 )TP RG . In contrast, the BonehS&P [38] achieves a linear complexity of O(n)TP RG . The proposed eSpat-B has O(n)TP RG , while eSpat+ matches the linear efficiency of BonehS&P with O(n)TP RG . For the Eval phase, the computational cost of LiangTC is O(M N )Tpair , which is quadratic in the number of regions and clients and uses the computationally heavy bilinear pairing operation. LiangTIFS requires O(log N )TAES . The standard DPF needs O(n)TP RG . BonehS&P achieves a more efficient complexity of O(l)TP RG , which depends only on the query prefix length. The proposed eSpat-B requires O(n)TP RG , similar to [21], and eSpat+ achieves O(l)TP RG , matching the efficiency of BonehS&P in this regard. Regarding storage/communication complexity for KeyGen, LiangTC requires O(|B| + N )λ, LiangTIFS needs O(N n +

IEEE TRANSACTIONS ON MOBILE COMPUTING

M )λ, and the standard DPF uses O(n2 )λ. BonehS&P requires O(n)λ. Correspondingly, eSpat-B requires O(n)λ, and eSpat+ requires O(n)λ. For the Eval phase, the storage overheads are O(|B| + M log N )λ for LiangTC, O(log N )λ for LiangTIFS, and O(n)λ for the standard DPF. BonehS&P achieves a constant storage overhead of O(1)λ. The proposed eSpat-B requires O(n)λ, while eSpat+ matches the constant overhead of O(1)λ, the same as BonehS&P. Algorithm 7: eSpat+.EvalPre Input: b, kb , pp, r(x, y, z) ∈ R(x, y, z) Output: ybl (0) 1 s = kb and t(0) = b; (1) 2 Interpret pp = CW , . . . , CW (n) ; 0 (0) (0) 3 stb ← s ||t ; 4 for j = 1 to l do 5 (stjb , ybj ) ← eSpat+.EvalNext(b, stj−1 , CW (j) , r(x, y, z)); b 6 end l 7 return yb

Algorithm 8: eSpat+.MoveEval Input: b, kb , pp, ppold , ppnew ,R(x0 , y0 , z0 ),R(x′ , y ′ , z ′ ), R(x′′ , y ′′ , z ′′ ) l Output: yb,new (0) 1 Set s = kb and t(0) = b; (1) 2 Interpret pp = CW , . . . , CW (m) (m+1) (n) ppold = CWold , . . . , CWold (n) (m+1) ppnew = CWnew , . . . , CWnew ; 0 (0) (0) 3 stb ← s ||t ; 4 for j = 1 to m do 5 (stjb , ybj ) ← eSpat+.EvalNext(b, stj−1 , CW (j) , R(x0 , y0 , z0 )); b 6 end 0 0 m 7 stb,old = stb,new = stb ; 8 for l = m + 1 to n do l 9 (stlb,old , yb,old )← (l) ′ ′ ′ eSpat+.EvalNext(b, stl−1 b,old , CWold , R(x , y , z )); l (stlb,new , yb,new )← (l) ′′ ′′ ′′ eSpat+.EvalNext(b, stl−1 b,new , CWnew ,R(x , y , z )); l l l yb,new = yb,old + yb,new ; l 10 return yb,new 11 end

VII. E XPERIMENTAL E VALUATION In this section, we present the detailed experimental setups. Then, we offer an overview of the experimental results. A. Experimental Settings Configuration. The eSpat-B and eSpat+ are employed to tackle distribution statistical issues in certain applications.

11

Similar to Ref. [38], the security parameter is set to 128 bits. The test platform’s configuration includes an AMD Ryzen 9 7945HX processor, an NVIDIA GeForce GTX 4070 graphics card, and 64 GB of system memory, with Java version 11.0.4. As for baselines, we select representative schemes from different categories of privacy-preserving data analytics. Specifically, LiangTC [50] is a searchable encryption scheme based on Bloom filters for secure keyword search over encrypted data. LiangTIFS [78] is a privacy-preserving range query scheme that supports efficient encoded queries using symmetric cryptographic techniques. BonehS&P [38] is a two-server private aggregation framework based on function secret sharing, designed for efficient and secure computation of aggregate statistics. In addition, we adopt two local differential privacy schemes, denoted as LDP1 [40] and LDP2 [41], which protect privacy by injecting noise into data. These baselines are chosen because they represent different technical paradigms closely related to our problem, including searchable encryption, range query, private aggregation, and differential privacy, thereby providing a comprehensive comparison. Dataset. We use the real Geolife2 and T-Drive3 to evaluate our schemes. The Geolife GPS trajectory dataset includes 17, 621 trajectories with time-stamped latitude, longitude, and altitude points from 182 users. The T-Drive trajectory dataset contains a one-week trajectory of 10, 357 taxis. The total number of points in this dataset is about 15 million, and the total distance of the trajectories reaches 9 million kilometers. We first divide the area according to the gray code. To perform analysis, we extract geospatial positions from the dataset and securely upload them to the servers for aggregation. Metric. We measure the following two indicators: (1) Time costs: we evaluate the time costs of key generation, key evaluation, and update; (2) Communication costs: we evaluate the communication overhead of clients and server; (3) Accuracy: we compare the accuracy of different DP schemes. B. Experimental Results Time costs for key generation. As shown in Figs. 5a and 5b, key generation time increases with encoding string length and data records. BonehS&P incurs higher costs due to tree height extension, LiangTIFS suffers from inefficient key construction, and LiangTC faces increased overhead as the data scale grows. In contrast, eSpat-B uses optimized DPF and octree partitioning, while eSpat+ improves scalability with KD-tree encoding and incremental DPF. For example, at 128 bits, eSpat+ and eSpat-B take 160 ms and 300 ms, compared to 424 ms for BonehS&P, 987 ms for LiangTC, and 730 ms for LiangTIFS. Similarly, with 500 data records, eSpat+ and eSpat-B take 20 and 65 s, much less than 95 s for BonehS&P, 300 s for LiangTC, and over 210 s for LiangTIFS. Time costs for key evaluation. As shown in Figs. 5c and 5d, key evaluation time increases with encoding string length and data records. BonehS&P incurs higher costs due to tree traversal, LiangTIFS suffers from inefficiencies in 2 https://www.microsoft.com/en-us/download/details.aspx?id=52367 3 https://www.microsoft.com/en-us/research/publication/t-drive-trajectorydata-sample/

IEEE TRANSACTIONS ON MOBILE COMPUTING

12

TABLE II C OMPLEXITY BETWEEN eSpat AND OTHER BASELINES . N OTE THAT THE COMPLEXITIES LISTED IN THE TABLE OMIT SOME OPERATIONS WITH VERY LOW TIME AND STORAGE OVERHEAD , WHICH CAN BE NEGLECTED . Computation LiangTC [50]

LiangTIFS [78]

DPF [21]

BonehS&P [38]

eSpat-B

eSpat+

O(|B| + N )TEXP O(M N )Tpair

O(N n + M )TP RF + O(M )TAES O(logN )TAES

O(n2 )TP RG O(n)TP RG

O(n)TP RG O(l)TP RG

O(n)TP RG O(n)TP RG

O(n)TP RG O(l)TP RG

LiangTC [50]

LiangTIFS [78]

DPF [21]

BonehS&P [38]

eSpat-B

eSpat+

O(|B| + N )λ O(|B| + M log N )λ

O(N n + M )λ O(logN )λ

O(n2 )λ O(n)λ

O(n)λ O(1)λ

O(n)λ O(n)λ

O(n)λ O(1)λ

KeyGen Eval

Storage

10

10

eSpat+

2

1

8

16

32 64 String Length

10

LiangTC LiangTIFS

BonehS&P eSpat-B

300 400 Data Records

10

200

300 400 Data Records

10

eSpat-B

eSpat+

2

LiangTC LiangTIFS

16

LiangTC LiangTIFS

20 10

32 String Length

64

8

10

8

16

BonehS&P eSpat_B

BonehS&P

2

eSpat+

32 64 String Length

128

10

200

eSpat+

200

300 400 Data Records

500

(f) Update time w.r.t data records.

eSpat+

400

eSpat-B

1

100

16

32 String Length

64

128

100

200

300 Data Records

400

10

3 LiangTC LiangTIFS

BonehS&P eSpat_B

eSpat+

2

8

500

BonehS&P eSpat_B

eSpat+

200 100

100

200

300 400 Data Records

500

(j) Total time w.r.t data records.

LiangTC LiangTIFS BonehS&P eSpat-B eSpat+

20 10

Communication cost(KB)

LiangTC LiangTIFS

Communication cost(KB)

300

0 8

16

32 String Length

64

128

(k) Communication cost of clients.

16

32 64 String Length

128

(i) Total time w.r.t string length.

(g) Statistics time w.r.t string length. (h) Statistics time w.r.t data records. Time (s)

BonehS&P eSpat-B

0

0

0

LiangTC LiangTIFS

0

128

(e) Update time w.r.t string length.

eSpat+

Time (ms)

30

BonehS&P eSpat_B

8

500

(d) KeyEval time w.r.t data records.

2

500

10 100

Time (ms)

200

10

(b) KeyGen time w.r.t data records. (c) KeyEval time w.r.t string length. BonehS&P

1

eSpat+

1

eSpat+

2

BonehS&P eSpat-B

2

100

Time (ms)

Time (ms)

10

3

10

LiangTC LiangTIFS

128

(a) KeyGen time w.r.t string length. 10

10

3

Time (ms)

BonehS&P eSpat-B

Time (ms)

10

LiangTC LiangTIFS

3

Time (ms)

10

Time (s)

Time (ms)

KeyGen Eval

10 10 10

4

LiangTC LiangTIFS BonehS&P eSpat-B eSpat+

2

0

8

16

32 String Length

64

128

(l) Communication cost of servers.

Fig. 5. Performance evaluation of eSpat-B and eSpat+ against baseline schemes. Results demonstrate that eSpat+ achieves the best efficiency in terms of computation time and communication cost for both clients and servers. For example, eSpat+ reduces key generation time by over 60% and client communication by over 75% compared to strong baselines at 128-bit length.

decryption and data reconstruction operations, and LiangTC scales linearly with evaluation points. In contrast, eSpat-B reduces time using the improved DPF, while eSpat+ further improves efficiency with KD-tree partitioning and incremental DPF. For example, at 128 bits, eSpat-B and eSpat+ take 80 ms and 2 ms, respectively, compared to over BonehS&P (90 ms), LiangTC (900 ms), and LiangTIFS (580 ms). Similarly, for 500 data records, eSpat+ and eSpat-B take 18 ms and 150 ms, much lower than 190 ms for BonehS&P, 1000 ms for LiangTC, and over 870 ms for LiangTIFS. Time costs for update. As shown in Figs. 5e and 5f, we evaluate the key update time with encoding string length and data records. LiangTC and LiangTIFS are excluded as they do not handle key updates. As string length and data

records increase, time costs rise, but eSpat-B and eSpat+ outperform BonehS&P. BonehS&P incurs higher costs due to full key regeneration during updates, while eSpat-B and eSpat+ improve efficiency using optimized and incremental DPF. For example, at 128 bits, eSpat+ and eSpat-B take 150 ms and 170 ms, compared to over 250 ms for BonehS&P. For 500 data records, eSpat+ takes 35 ms, much less than 100 ms for eSpat-B and 150 ms for BonehS&P. Time costs for statistics. As shown in Figs. 5g and 5h, we evaluate the statistics time, which refers to the requester-side aggregation time. As these numbers increase, time costs rise. LiangTC and LiangTIFS incur higher costs due to the need to match all indices. In contrast, BonehS&P only needs to add up the shares received from the server, and the same applies

IEEE TRANSACTIONS ON MOBILE COMPUTING

LDP1

1.0

LDP2

-25.00%

-30.00%

-31.00%

-36.00%

0.5

0.0

8

16

32 String Length

64

Accuracy

eSpat-B eSpat+ -25.00%

LDP1

-30.00%

-38.00%

0.5

0.0

8

16

32 String Length

64

128

(c) Accuracy on T-Drive w.r.t string length.

LDP2

-17.00%

-17.00%

-16.00%

0.5

1.0 -35.00%

LDP1

-21.00%

100

200

300 400 Data Records

500

(b) Accuracy on Geolife w.r.t data records.

LDP2

-32.00%

eSpat-B eSpat+

-29.00%

0.0

128

(a) Accuracy on Geolife w.r.t string length. 1.0

Accuracy

eSpat-B

-18.00% eSpat+

Accuracy

Accuracy

1.0

13

eSpat-B eSpat+

LDP1

LDP2

-34.00%

-31.00%

100

200

-27.00%

-27.00%

-26.00%

0.5

0.0

300 400 Data Records

500

(d) Accuracy on T-Drive w.r.t data records.

Fig. 6. Accuracy comparison of the proposed eSpat schemes against local differential privacy baselines (LDP1, LDP2) on real-world trajectory datasets. The results demonstrate that both eSpat-B and eSpat+ consistently achieve 100% accuracy across different encoding string lengths and data volumes, as they perform exact computations without noise.

to eSpat+ and eSpat-B. For instance, at 128 bits, BonehS&P, eSpat+ and eSpat-B take 0.1 ms, compared to 540 ms for LiangTC, and 410 ms for LiangTIFS. For 500 data records, eSpat+ and eSpat-B also take 0.1 ms, significantly lower than LiangTC and LiangTIFS. Total time. As shown in Figs. 5i and 5j, we evaluate the total time with the encoding string and data records. The reasons for the differences are discussed in earlier experiments. Specifically, at 128 bits, eSpat+ and eSpat-B take 160 and 300 ms, compared to BonehS&P (424 ms), LiangTC (987 ms), and LiangTIFS (730 ms). Similarly, with 500 data records, eSpat+ and eSpat-B take 20 and 65 s, much less than BonehS&P (95 s), LiangTC (300 s), and LiangTIFS (210 s). Communication overhead. As shown in Figs. 5k and 5l, we evaluate communication overhead with different encoding string length. The communication costs of eSpat-B, eSpat+, and the baselines increase with string length. eSpat+ achieves the lowest communication cost due to incremental DPF with KD-tree partitioning. In contrast, eSpat-B incurs quadratic costs due to linear-sized keys at each prefix tree level, while BonehS&P, leveraging incremental DPF, incurs higher costs due to greater tree height, though still lower than eSpat-B. LiangTC and LiangTIFS need to generate binary trees and keys for the servers, leading to the highest communication costs. For instance, at 128 bits, eSpat+ incurs 1.2 kilobyte (KB) for client communication and 7 KB for server communication, significantly lower than 5 KB and 70 KB for BonehS&P, 16 KB and 1000 KB for eSpat-B, and over 20 KB and 20000 KB for LiangTC and LiangTIFS. Accuracy. As shown in Fig. 6, we compare the accuracy under different encoding string lengths and numbers of data records. LDP1 and LDP2 are representative local differential privacy schemes. The results show that eSpat-B and eSpat+ consistently achieve 100% accuracy, while LDP1 and LDP2 achieve lower accuracy due to the randomized noise introduced for privacy protection. The 100% accuracy of our schemes

follows from their exact cryptographic computation. Specifically, each spatial record is encoded into its corresponding spatial index, the two servers compute secret-shared partial results via DPF/IDPF evaluation, and the requester aggregates these shares to recover the exact count. Since no noise or approximation is introduced, the recovered result is identical to the plaintext counting result. For LDP-based schemes, when the encoding string becomes longer, the spatial partition becomes finer, and even small perturbations may shift records across region boundaries, reducing accuracy. As the number of data records increases, the relative impact of noise is reduced, so the accuracy improves and gradually stabilizes. Overall, these approaches reflect different design choices: our schemes provide exact analytics under cryptographic assumptions, whereas LDP schemes provide local privacy at the cost of accuracy loss. These approaches represent different design choices: our schemes prioritize exact analytics under cryptographic assumptions, whereas LDP schemes offer a stronger local privacy model at the cost of accuracy loss. VIII. C ONCLUSION In this paper, we have proposed efficient and privacypreserving distribution statistics analysis schemes for spatial data, which achieve accurate statistics while preserving spatial data privacy. First, we have designed eSpat-B, which combines distributed point functions and octree partitioning to guarantee both privacy and efficiency. Building upon this, we have introduced eSpat+, which further reduces computational and communication overheads by leveraging KD-tree and incremental DPF. In addition, we have also designed an efficient update algorithm to process the frequent updates of spatial data. Security analysis and experimental results have validated the robustness and high performance of eSpat-B and eSpat+. R EFERENCES [1] J. Xue, H. Zhou, H. Huang, G. Wen, Y. Xu, X. Huang, and X. Shen, “Fdran empowered multiple base stations cooperative isac for low-altitude

IEEE TRANSACTIONS ON MOBILE COMPUTING

networks,” IEEE Transactions on Network Science and Engineering, vol. 13, pp. 6927–6943, 2026. [2] Q. Chen, Z. Guo, W. Meng, S. Han, C. Li, and T. Q. Quek, “A survey on resource management in joint communication and computing-embedded sagin,” IEEE Communications Surveys & Tutorials, vol. 27, no. 3, pp. 1911–1954, 2024. [3] J. Akram, W. Hussain, R. H. Jhaveri, R. S. Rathore, and A. Anaissi, “Dynamic gnn-based multimodal anomaly detection for spatial crowdsourcing drone services,” Digital Communications and Networks, 2025. [4] Y. Fang, Y. Liang, B. Hui, Z. Shao, L. Deng, X. Liu, X. Jiang, and K. Zheng, “Efficient large-scale traffic forecasting with transformers: A spatial data management perspective,” in Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, 2025, pp. 307–317. [5] S. Wandelt, S. Wang, C. Zheng, and X. Sun, “Aerial: A meta review and discussion of challenges toward unmanned aerial vehicle operations in logistics, mobility, and monitoring,” IEEE Transactions on Intelligent Transportation Systems, 2023. [6] N. H. Motlagh, P. Kortoçi, X. Su, L. Lovén, H. K. Hoel, S. B. Haugsvær, V. Srivastava, C. F. Gulbrandsen, P. Nurmi, and S. Tarkoma, “Unmanned aerial vehicles for air pollution monitoring: A survey,” IEEE Internet of Things Journal, 2023. [7] M. A. Istiak, M. M. Syeed, M. S. Hossain, M. F. Uddin, M. Hasan, R. H. Khan, and N. S. Azad, “Adoption of unmanned aerial vehicle (uav) imagery in agricultural management: A systematic literature review,” Ecological Informatics, p. 102305, 2023. [8] Y. Chen, S. Sun, M. Liu, B. Ai, Y. Wang, and Y. Liu, “Energyefficient over-the-air computation in uav-assisted iiot networks,” IEEE Transactions on Mobile Computing, 2025. [9] X. Yuan, S. Hu, W. Ni, X. Wang, and A. Jamalipour, “Deep reinforcement learning-driven reconfigurable intelligent surface-assisted radio surveillance with a fixed-wing uav,” IEEE Transactions on Information Forensics and Security, 2023. [10] J. Xue, K. Yu, T. Zhang, H. Zhou, L. Zhao, and X. Shen, “Cooperative deep reinforcement learning enabled power allocation for packet duplication urllc in multi-connectivity vehicular networks,” IEEE Transactions on Mobile Computing, vol. 23, no. 8, pp. 8143–8157, 2024. [11] W. Zhang, M. Zhao, Z. Sun, C. Zhang, J. Liang, L. Zhu, and S. Guo, “Vspatial: Enabling private and verifiable spatial keywordbased positioning in 6g-oriented iot,” IEEE Journal on Selected Areas in Communications, vol. 42, no. 10, pp. 2954–2969, 2024. [12] C. Zhang, X. Luo, J. Liang, X. Liu, L. Zhu, and S. Guo, “Pota: Privacy-preserving online multi-task assignment with path planning,” IEEE Transactions on Mobile Computing, vol. 23, no. 5, pp. 5999–6011, 2023. [13] F. Song, J. Liang, C. Zhang, Z. Fu, Z. Qin, and S. Guo, “Achieving efficient and privacy-preserving location-based task recommendation in spatial crowdsourcing,” IEEE Transactions on Dependable and Secure Computing, vol. 21, no. 4, pp. 4006–4023, 2023. [14] J. Liang, S. Guo, Z. Hong, E. Zhou, C. Zhang, and B. Xiao, “Secpq: Secure prediction queries on encrypted outsourced databases,” IEEE Transactions on Dependable and Secure Computing, 2025. [15] J. Shao, X. Qin, J. Gao, Y. Li, L. Xin, and P. Zhang, “Collaborate for real-time gain: Semantic-based robotic communication in 3d object tracking,” IEEE Transactions on Mobile Computing, 2025. [16] Q. Huang, J. Du, G. Yan, Y. Yang, and Q. Wei, “Privacy-preserving spatio-temporal keyword search for outsourced location-based services,” IEEE Transactions on Services Computing, vol. 15, no. 6, pp. 3443– 3456, 2022. [17] L. Wu, S. Fu, Y. Luo, H. Yan, H. Shi, and M. Xu, “A robust and lightweight privacy-preserving data aggregation scheme for smart grid,” IEEE Transactions on Dependable and Secure Computing, vol. 21, no. 1, pp. 270–283, 2023. [18] J. Bell, A. Gascon, B. Ghazi, R. Kumar, P. Manurangsi, M. Raykova, and P. Schoppmann, “Distributed, private, sparse histograms in the twoserver model,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, pp. 307–321. [19] H. Corrigan-Gibbs and D. Boneh, “Prio: Private, robust, and scalable computation of aggregate statistics,” in 14th USENIX symposium on networked systems design and implementation (NSDI 17), 2017, pp. 259–282. [20] L. Melis, G. Danezis, and E. De Cristofaro, “Efficient private statistics with succinct sketches,” arXiv preprint arXiv:1508.06110, 2015. [21] E. Boyle, N. Gilboa, and Y. Ishai, “Function secret sharing: Improvements and extensions,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016, pp. 1292–1303.

14

[22] Y. Yang, Y. Hu, R. Li, X. Dong, Z. Cao, J. Shen, and S. Dou, “Lse: Efficient symmetric searchable encryption based on labeled psi,” IEEE Transactions on Services Computing, vol. 17, no. 2, pp. 563–574, 2024. [23] B. Chen, T. Xiang, D. He, H. Li, and K.-K. R. Choo, “Bpvse: Publicly verifiable searchable encryption for cloud-assisted electronic health records,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 3171–3184, 2023. [24] X. Zhang, W. Wang, P. Xu, L. T. Yang, and K. Liang, “High recovery with fewer injections: Practical binary volumetric injection attacks against dynamic searchable encryption,” in 32nd USENIX Security Symposium (USENIX Security 23). Anaheim, CA: USENIX Association, 2023, pp. 5953–5970. [25] W. Zhang, M. Zhao, Z. Sun, C. Zhang, J. Liang, L. Zhu, and S. Guo, “Vspatial: Enabling private and verifiable spatial keywordbased positioning in 6g-oriented iot,” IEEE Journal on Selected Areas in Communications, vol. 42, no. 10, pp. 2954–2969, 2024. [26] Y. Xu, H. Cheng, X. Liu, C. Jiang, X. Zhang, and M. Wang, “Pcse: Privacy-preserving collaborative searchable encryption for group data sharing in cloud computing,” IEEE Transactions on Mobile Computing, 2025. [27] F. Song, Y. Gao, M. Zhao, C. Zhang, Z. Qin, and B. Xiao, “Highdimensional and secure spatial keyword query with arbitrary ranges in mobile cloud,” IEEE Transactions on Mobile Computing, 2025. [28] Q. Tong, X. Li, Y. Miao, Y. Wang, X. Liu, and R. H. Deng, “Beyond result verification: Efficient privacy-preserving spatial keyword query with suppressed leakage,” IEEE Transactions on Information Forensics and Security, vol. 19, pp. 2746–2760, 2024. [29] F. Wang, H. Zhu, G. He, R. Lu, Y. Zheng, and H. Li, “Efficient and privacy-preserving arbitrary polygon range query scheme over dynamic and time-series location data,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 3414–3429, 2023. [30] X. Wang, Z. Fang, C. Gong, Y. Liang, X. Ma, and J. Ma, “Enabling secure keyword-associated spatio-temporal range query in mobile cloud,” IEEE Transactions on Mobile Computing, 2025. [31] H. Wu, Z. Peng, J. Xiao, L. Xue, C. Lin, and S.-H. Chung, “Hex: Encrypted rich queries with forward and backward privacy using trusted hardware,” IEEE Transactions on Dependable and Secure Computing, 2025. [32] J. Guo, Y. Hong, Y. Wu, Y. Liu, T. Yang, and B. Cui, “Sketchpolymer: Estimate per-item tail quantile using one sketch,” in Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023, pp. 590–601. [33] L. Assouline and B. Minaud, “Weighted oblivious ram, with applications to searchable symmetric encryption,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2023, pp. 426–455. [34] Y. Tao, A. Gilad, A. Machanavajjhala, and S. Roy, “Differentially private explanations for aggregate query answers,” The VLDB Journal, vol. 34, no. 2, p. 20, 2025. [35] J. G. Chamani, Y. Wang, D. Papadopoulos, M. Zhang, and R. Jalili, “Multi-user dynamic searchable symmetric encryption with corrupted participants,” IEEE Transactions on Dependable and Secure Computing, vol. 20, no. 1, pp. 114–130, 2021. [36] T. Le, R. Behnia, J. Guajardo, and T. Hoang, “{MUSES}: Efficient {Multi-User} searchable encrypted database,” in 33rd USENIX Security Symposium (USENIX Security 24), 2024, pp. 2581–2598. [37] C. Huang, D. Liu, A. Yang, R. Lu, and X. Shen, “Multi-client secure and efficient dpf-based keyword search for cloud storage,” IEEE Transactions on Dependable and Secure Computing, vol. 21, no. 1, pp. 353–371, 2023. [38] D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, and Y. Ishai, “Lightweight techniques for private heavy hitters,” in 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021, pp. 762–776. [39] D. Mouris, P. Sarkar, and N. G. Tsoutsos, “Plasma: Private, lightweight aggregated statistics against malicious adversaries,” Proceedings on Privacy Enhancing Technologies, 2024. [40] D. Hong, W. Jung, and K. Shim, “Collecting geospatial data under local differential privacy with improving frequency estimation,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 7, pp. 6739–6751, 2022. [41] T. Cunningham, G. Cormode, H. Ferhatosmanoglu, and D. Srivastava, “Real-world trajectory sharing with local differential privacy,” arXiv preprint arXiv:2108.02084, 2021. [42] H. Huang, C. Sun, Z. Shi, W. Zhang, J. Cang, and F. Xiao, “Differential privacy space decomposition algorithm based on hierarchical model,” IEEE Transactions on Mobile Computing, 2025.

IEEE TRANSACTIONS ON MOBILE COMPUTING

[43] Y. He, M. Wang, X. Deng, P. Yang, Q. Xue, and L. T. Yang, “Personalized local differential privacy for multi-dimensional range queries over mobile user data,” IEEE Transactions on Mobile Computing, 2025. [44] R. Zhang, R. Xue, and L. Liu, “Searchable encryption for healthcare clouds: A survey,” IEEE Transactions on Services Computing, vol. 11, no. 6, pp. 978–996, 2017. [45] J. Qiu, Z. Tian, C. Du, Q. Zuo, S. Su, and B. Fang, “A survey on access control in the age of internet of things,” IEEE Internet of Things Journal, vol. 7, no. 6, pp. 4682–4696, 2020. [46] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword search,” in Advances in CryptologyEUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23. Springer, 2004, pp. 506–522. [47] P. Golle, J. Staddon, and B. Waters, “Secure conjunctive keyword search over encrypted data,” in Applied Cryptography and Network Security: Second International Conference, ACNS 2004, Yellow Mountain, China, June 8-11, 2004. Proceedings 2. Springer, 2004, pp. 31–45. [48] R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky, “Searchable symmetric encryption: improved definitions and efficient constructions,” in Proceedings of the 13th ACM conference on Computer and communications security, 2006, pp. 79–88. [49] Q. Tong, X. Li, Y. Miao, X. Liu, J. Weng, and R. H. Deng, “Privacypreserving boolean range query with temporal access control in mobile computing,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 5, pp. 5159–5172, 2022. [50] Y. Liang, J. Ma, Y. Miao, D. Kuang, X. Meng, and R. H. Deng, “Privacypreserving bloom filter-based keyword search over large encrypted cloud data,” IEEE Transactions on Computers, vol. 72, no. 11, pp. 3086–3098, 2023. [51] X. Li, Q. Tong, J. Zhao, Y. Miao, S. Ma, J. Weng, J. Ma, and K.K. R. Choo, “Vrfms: Verifiable ranked fuzzy multi-keyword search over encrypted data,” IEEE Transactions on Services Computing, vol. 16, no. 1, pp. 698–710, 2022. [52] Q. Tong, Y. Miao, H. Li, X. Liu, and R. H. Deng, “Privacy-preserving ranked spatial keyword query in mobile cloud-assisted fog computing,” IEEE Transactions on Mobile Computing, vol. 22, no. 6, pp. 3604–3618, 2021. [53] F. Song, Z. Qin, L. Xue, J. Zhang, X. Lin, and X. Shen, “Privacypreserving keyword similarity search over encrypted spatial data in cloud computing,” IEEE Internet of Things Journal, vol. 9, no. 8, pp. 6184– 6198, 2021. [54] Z. Gong, J. Li, Y. Lin, J. Wei, and C. Lancine, “Efficient privacypreserving geographic keyword boolean range query over encrypted spatial data,” IEEE Systems Journal, vol. 17, no. 1, pp. 455–466, 2022. [55] H. Delfs, H. Knebl, and H. Knebl, Introduction to cryptography. Springer, 2002, vol. 2. [56] W. Lin, K. Wang, Z. Zhang, and H. Chen, “Revisiting security risks of asymmetric scalar product preserving encryption and its variants,” in 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2017, pp. 1116–1125. [57] Y. Guan, R. Lu, Y. Zheng, S. Zhang, J. Shao, and G. Wei, “Achieving privacy-preserving discrete frechet distance range queries,” IEEE Transactions on Dependable and Secure Computing, vol. 20, no. 3, pp. 2097–2110, 2022. [58] F. Wang, H. Zhu, G. He, R. Lu, Y. Zheng, and H. Li, “Efficient and privacy-preserving arbitrary polygon range query scheme over dynamic and time-series location data,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 3414–3429, 2023. [59] Y. Miao, C. Xu, Y. Zheng, X. Liu, X. Meng, and R. H. Deng, “Efficient and secure spatial range query over large-scale encrypted data,” in 2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS). IEEE, 2023, pp. 1–11. [60] X. Wang, J. Ma, F. Li, X. Liu, Y. Miao, and R. H. Deng, “Enabling efficient spatial keyword queries on encrypted data with strong security guarantees,” IEEE Transactions on Information Forensics and Security, vol. 16, pp. 4909–4923, 2021. [61] Y. Miao, Y. Yang, X. Li, Z. Liu, H. Li, K.-K. R. Choo, and R. H. Deng, “Efficient privacy-preserving spatial range query over outsourced encrypted data,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 3921–3933, 2023. [62] S. Lai, S. Patranabis, A. Sakzad, J. K. Liu, D. Mukhopadhyay, R. Steinfeld, S.-F. Sun, D. Liu, and C. Zuo, “Result pattern hiding searchable encryption for conjunctive queries,” in Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, 2018, pp. 745–762.

15

[63] D. L. Chaum, “Untraceable electronic mail, return addresses, and digital pseudonyms,” Communications of the ACM, vol. 24, no. 2, pp. 84–90, 1981. [64] C. A. Neff, “A verifiable secret shuffle and its application to evoting,” in Proceedings of the 8th ACM conference on Computer and Communications Security, 2001, pp. 116–125. [65] G. Fanti, V. Pihur, and Ú. Erlingsson, “Building a rappor with the unknown: Privacy-preserving learning of associations and data dictionaries,” arXiv preprint arXiv:1503.01214, 2015. [66] S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis, “Secure two-party computation in sublinear (amortized) time,” in Proceedings of the 2012 ACM conference on Computer and communications security, 2012, pp. 513–524. [67] S. Lu and R. Ostrovsky, “Distributed oblivious ram for secure two-party computation,” in Theory of Cryptography Conference. Springer, 2013, pp. 377–396. [68] J. R. Bitner, G. Ehrlich, and E. M. Reingold, “Efficient generation of the binary reflected gray code and its applications,” Communications of the ACM, vol. 19, no. 9, pp. 517–521, 1976. [69] X. Wang, J. Ma, X. Liu, R. H. Deng, Y. Miao, D. Zhu, and Z. Ma, “Search me in the dark: Privacy-preserving boolean range query over encrypted spatial data,” in IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 2253–2262. [70] Y. Zhao, Y. Wang, J. Zhang, C. Fu, M. Xu, and D. Moritz, “Kd-box: Line-segment-based kd-tree for interactive exploration of large-scale time-series data,” IEEE Trans. Vis. Comput. Graph., vol. 28, no. 1, pp. 890–900, 2022. [71] S. Sharma, Y. Li, S. Mehrotra, N. Panwar, K. Kumari, and S. Roychoudhury, “Information-theoretically secure and highly efficient search and row retrieval,” Proceedings of the VLDB Endowment, vol. 16, no. 10, pp. 2391–2403, 2023. [72] Y. Zhang, J. Bater, K. Nayak, and A. Machanavajjhala, “Longshot: Indexing growing databases using mpc and differential privacy,” Proceedings of the VLDB Endowment, vol. 16, no. 8, pp. 2005–2018, 2023. [73] I. Damgård, H. Keller, B. Nelson, C. Orlandi, and R. Pagh, “Differentially private selection from secure distributed computing,” in Proceedings of the ACM Web Conference 2024, 2024, pp. 1103–1114. [74] B. Balle, J. Bell-Clark, A. Cheu, A. Gascon, J. Katz, M. Raykova, P. Schoppmann, and T. Steinke, “Hash-prune-invert: Improved differentially private heavy-hitter detection in the two-server model,” in 2025 IEEE Symposium on Security and Privacy (SP). IEEE, 2025, pp. 2903– 2918. [75] C. Dong, Y. Wang, A. Aldweesh, P. McCorry, and A. Van Moorsel, “Betrayal, distrust, and rationality: Smart counter-collusion contracts for verifiable cloud computing,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 211– 227. [76] O. Goldreich, Foundations of Cryptography, Volume 2: Basic Applications. Cambridge University Press, 2004. [77] N. Gilboa and Y. Ishai, “Distributed point functions and their applications,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2014, pp. 640– 658. [78] Y. Liang, J. Ma, Y. Miao, Y. Su, and R. H. Deng, “Efficient and privacypreserving encode-based range query over encrypted cloud data,” IEEE Transactions on Information Forensics and Security, 2024.

Xuhao Ren received his B.S. degree in the School of Information Engineering of Sichuan Agricultural University, Sichuan, China, in 2022. He is currently a master’s student in the School of Cyberspace Science and Technology, Beijing Institute of Technology. His research interests include applied cryptography.

IEEE TRANSACTIONS ON MOBILE COMPUTING

Chuan Zhang (Member, IEEE) received his Ph.D. degree in computer science from Beijing Institute of Technology, Beijing, China, in 2021. From Sept. 2019 to Sept. 2020, he worked as a visiting Ph.D. student with the BBCR Group, Department of Electrical and Computer Engineering, University of Waterloo, Canada. He is currently an associate professor at the School of Cyberspace Science and Technology, Beijing Institute of Technology. His research interests include applied cryptography, machine learning, and blockchain.

Mingyang Zhao is currently a PhD student, supervised by Prof. Xiao Bin, at The Hong Kong Polytechnic University, Hong Kong. He received his B.S. degree in 2021 and his M.S. degree in 2024 from Beijing Institute of Technology, Beijing, China. From June 2023 to August 2023, and from July 2024 to August 2025, he was a Research Assistant at The Hong Kong Polytechnic University, supervised by Prof. Guo Song and Prof. Xiao Bin, respectively. His research interests include applied cryptography, Web 3.0 security, and post-quantum security.

Ruichen Zhang (Member, IEEE) received the B.E. degree from Henan University (HENU), China, in 2018, and the Ph.D. degree from Beijing Jiaotong University (BJTU), China, in 2023. He is currently a Post-Doctoral Research Fellow with the College of Computing and Data Science, Nanyang Technological University (NTU), Singapore. In 2024, he was a Visiting Scholar with the College of Information and Communication Engineering, Sungkyunkwan University, Suwon, South Korea. He has been the Managing Editor of IEEE Transactions on Network Science and Engineering since 2025. His research interests include LLMempowered networking, reinforcement learning-enabled wireless communication, generative AI models, and heterogeneous networks.

Liehuang Zhu (Senior Member, IEEE) received his Ph.D. degree in computer science from Beijing Institute of Technology, Beijing, China, in 2004. He is currently a professor at the School of Cyberspace Science and Technology, Beijing Institute of Technology. His research interests include security protocol analysis and design, group key exchange protocols, wireless sensor networks, and cloud computing.

Dusit Niyato (Fellow, IEEE) is a professor in the College of Computing and Data Science, at Nanyang Technological University, Singapore. He received B.Eng. from King Mongkuts Institute of Technology Ladkrabang (KMITL), Thailand and Ph.D. in Electrical and Computer Engineering from the University of Manitoba, Canada. His research interests are in the areas of mobile generative AI, edge intelligence, quantum computing and networking, and incentive mechanism design.

16

Bin Xiao (Fellow, IEEE) is a professor at Department of Computing, the Hong Kong Polytechnic University, Hong Kong. Prof. Xiao received the B.Sc and M.Sc degrees in Electronics Engineering from Fudan University, China, and Ph.D. degree in computer science from University of Texas at Dallas, USA. His research interests include AI and network security, data privacy, and blockchain systems. He published more than 180 technical papers in international top journals and conferences. Currently, he is the associate editor of IEEE IoTJ, IEEE TCC, and IEEE TNSE. He has been the associate editor of Elsevier JPDC from 2016 to 2021. He is the vice chair of IEEE ComSoc CISTC committee. He has been the track co-chair of IEEE ICDCS2022, the symposium track co-chair of IEEE ICC2020, ICC 2018 and Globecom 2017, and the general chair of IEEE SECON 2018. He is a fellow of IEEE, the member of ACM and CCF.