Computer Standards & Interfaces 97 (2026) 104112 Contents lists available at ScienceDirect Computer Standards & Interfaces journal homepage: www.elsevier.com/locate/csi Efficient and secure multi-user π‘˜NN queries with dynamic POIs updating Yining Jia a,b,c , Yali Liu a,b,c ,βˆ—, Congai Zeng a,b,c , Xujie Ding a,b,c , Jianting Ning d,e a School of Artificial Intelligence and Computer Science, Jiangsu Normal University, Xuzhou, Jiangsu Province, 221116, China b State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu Province, 210023, China c Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin, Guangxi Province, 541004, China d School of Cyber Science and Engineering, Wuhan University, Wuhan, Hubei Province, 430072, China e Faculty of Data Science, City University of Macau, 999078, Macao Special Administrative Region of China ARTICLE INFO ABSTRACT Keywords: The π‘˜-nearest neighbors (π‘˜NN) query is a key operation in spatial and multimedia databases, which is widely Cloud computing applied in fields such as electronic healthcare and Location-Based Services (LBS). With the rapid development Security of cloud computing, uploading private data of Data Owner (DO) to Cloud Servers (CS) has become a trend. kNN queries However, existing π‘˜NN queries schemes are not designed for multi-user environments, cannot timely update Dynamic POIs updating the points of interest (POIs) stored in CS, and suffer from low query efficiency. Therefore, this paper proposes efficient and secure multi-user π‘˜NN queries with dynamic POIs updating, named DESMπ‘˜NN, which achieves secure multi-user π‘˜NN queries. To improve query efficiency, DESMπ‘˜NN adopts a two-stage search framework, which consists of an initial filtering stage based on hierarchical clustering to effectively constrain the search range, followed by a more efficient precise search stage. Based on this framework, DESMπ‘˜NN designs a set of security protocols for efficient query processing and enables dynamic POIs updates. Meanwhile, DESMπ‘˜NN not only utilizes Distributed Two Trapdoors Public-Key Cryptosystem (DT-PKC) to enable multi-user queries but also ensures data privacy, query privacy, result privacy and access pattern privacy. Moreover, DESMπ‘˜NN can verify the correctness and completeness of queries results. Finally, security analysis proves that DESMπ‘˜NN meets the formal security definition of multiparty computation, and experimental evaluation shows that DESMπ‘˜NN improves query efficiency by up to 45.5% compared with existing π‘˜NN queries scheme. 1. Introduction and LBS systems. Once such information is exposed, it can lead to privacy leakage, commercial losses, or even public security risks [4]. LBS [1–3] are increasingly integrated into real-world applications, Therefore, to protect POIs from malicious access or theft by CS and such as ride-hailing platforms (e.g., Uber, DiDi), navigation systems unauthorized users, DO needs to encrypt them before outsourcing to (e.g., Google Maps, Baidu Maps), and online food delivery services. CS. In addition, security needs to be considered in query processing to These services heavily rely on POIs databases to provide personalized maintain efficiency and protect the confidentiality of POIs databases. and efficient responses to queries of query user (QU). Among various Although π‘˜NN queries have been widely studied in recent years, query types, the π‘˜NN query [4,5] is one of the most fundamental several limitations still hinder their applicability in practice. First, most methods, which aims to find the π‘˜ nearest POIs to a given query point. existing schemes [8,9] for π‘˜NN queries are based on static spatial With the rapid development of cloud computing [6,7], DO increasingly data [10], where the database remains unchanged within a certain outsource their POIs databases to CS, which provides scalable storage time interval. Consistent with this common setting, DESMπ‘˜NN also and massive computing resources. Well-known commercial platforms, assumes that POIs are static during query processing to enable fair such as Amazon Web Services and Google Cloud Platform, already performance comparison. However, in practice, POIs may change over provide such services to support efficient π‘˜NN queries in LBS. Although time, and their insertion or deletion frequency varies across different outsourcing databases to CS improves data accessibility and flexibility, it makes data more susceptible to unauthorized access threats. In prac- areas because these updates are driven by real-world change. In rapidly tice, POIs often contain sensitive or private information. For instance, developing areas where new facilities emerge or existing ones close POIs databases may include the locations of hospitals, government frequently, POI updates occur more frequently, whereas in more stable facilities, or user-related activity areas in intelligent transportation regions, such updates tend to be infrequent. This dynamic updates of βˆ— Corresponding author at: School of Artificial Intelligence and Computer Science, Jiangsu Normal University, Xuzhou, Jiangsu Province, 221116, China. E-mail address: liuyali@jsnu.edu.cn (Y. Liu). https://doi.org/10.1016/j.csi.2025.104112 Received 12 June 2025; Received in revised form 18 November 2025; Accepted 8 December 2025 Available online 11 December 2025 0920-5489/Β© 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies. Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 system construction is introduced. Section 6 presents the specific query procedure for DESMπ‘˜NN. Next, Section 7 analyzes computational com- plexity, communication complexity, and security. Section 8 provides an experimental evaluation of DESMπ‘˜NN. Section 9 concludes this paper. 2. Related work Secure Key-Sharing Query: Wong et al. [11] introduced a π‘˜NN queries scheme for encrypted data based on ASPE. However, ASPE re- lied on a secret matrix to transform data points and query points, which required secret key to be shared among all QUs and DO. Additionally, ASPE has been proven insecure against known-plaintext attacks [13]. To enhance query security, Elmehdwi et al. [15] developed a set of two-party computation protocols based on the Paillier cryptosystem. Although scheme [15] preserved the privacy of query results, QUs hold DO’s private key, and the query efficiency remains low. Moreover, scheme [16] employed Delaunay triangulation and order-preserving Fig. 1. Sample of the π‘˜NN query (π‘˜ = 2). encryption [18] to accurately solve the secure π‘˜NN problem. Neverthe- less, the encryption schemes in [16] are symmetric, which also required DO and QUs to share the key. Cui et al. [8] proposed an efficient, POIs reflects the continuous changes in the physical environment. As secure, and verifiable π‘˜NN queries scheme, which employed a secure shown in Fig. 1, π‘ˆ0 searches for the two nearest neighbors (π‘˜ = 2) index structure to ensure data security and result integrity, along with in a POIs database 𝐷 = {𝑝0 , … , 𝑝7 }. The original 2NN query 𝑄 was a set of novel protocols and verification strategies for various index {𝑝0 , 𝑝1 }. When a new and closer point 𝑝8 is inserted, the correct 2NN operations. However, the search complexity of scheme [8] was linearly result becomes {𝑝1 , 𝑝8 }. This example shows that any updates to the related to the database size, which led to a lack of scalability. To POI database, such as the insertion, modification, or deletion of POIs, address the efficiency issues in [8], Liu et al. [14] introduced a two- may change the query results. Therefore, dynamic updates must be sup- stage search framework for secure and verifiable π‘˜NN queries, which ported in outsourced POI databases. Second, existing schemes mostly integrated Edge Servers (ES) into the classic Twin-Cloud model by use Asymmetric-Scalar-Product-Preserving Encryption (ASPE) [11,12] leveraging adaptive encryption strategies and secure data partition- or pure homomorphic encryption algorithms to encrypt outsourced ing to optimize query performance. However, both scheme [8] and data. Unfortunately, ASPE has been demonstrated to be insecure under scheme [14] could not resolve the key-sharing issue. the known-plaintext attacks [13], and homomorphic operations lead to Secure Multi-User Query: To support multi-user π‘˜NN queries, re- a significant computational cost. These limitations raise the challenge searchers first focused on multi-key queries. Cheng et al. [17] imple- of designing an efficient and secure query mechanism. Finally, most mented π‘˜NN queries with multi-key support, where DO and QUs had solutions [14,15] assume a single-user setting, where all QUs share the their own keys, and each QU’s key was not shared with others. How- same secret key to enable computability of encrypted data across multi- ever, scheme [17] incurred high computational cost and lacked result user. In practice, the assumption of single-user setting has obvious verification. Subsequently, Liu et al. proposed the DT-PKC [19], which flaws. Once the unique key of any QUs is leaked, the entire encrypted also allowed different QUs to use different keys during queries. Building database can be completely decrypted, and the query content may also on the DT-PKC, Cheng et al. [20] and Nayak et al. [21] explored range be intercepted by the adversary. As illustrated in Fig. 1, in such a single- queries and keyword queries, respectively. Nevertheless, scheme [20] user setting, π‘ˆ1 and π‘ˆ2 can capture the query content and result of π‘ˆ0 and scheme [21] still suffered from computational cost and the inability and decrypt them using the same secret key as π‘ˆ0 . This highlights the to verify results. Cui et al. [9] introduced a method for secure and need for secure multi-user queries. verifiable π‘˜NN queries by utilizing DT-PKC, which encrypted grid and To resolve the aforementioned challenges, this paper proposes bucket divisions within the Voronoi diagram to maintain data security, DESMπ‘˜NN. The contributions of DESMπ‘˜NN are as follows: while also introducing a verification strategy to ensure the correctness and completeness of the query results. However, scheme [9] relied (1) Dynamic POIs Updating : DESMπ‘˜NN innovatively designs secure heavily on homomorphic encryption and data packing techniques, insertion and deletion protocols, which avoids the problem of which led to high computational cost and search complexity. Moreover, incorrect and incomplete query results. scheme [9] fails to address the issue of dynamic updates for POIs. (2) Efficient Query: DESMπ‘˜NN proposes an efficient two-stage In summary, the limitations in the existing π‘˜NN queries schemes search framework, which improves the query performance. are as follows: (1) The single-user queries schemes have a risk of key (3) Multi-User Query: DESMπ‘˜NN designs a series of secure protocols leakage. (2) The multi-user queries schemes have low efficiency. (3) based on DT-PKC, which achieves secure multi-user π‘˜NN queries. Most existing queries schemes unable to achieve dynamic updates of (4) Security & Performance: Security analysis shows that the pro- POIs. For ease of exhibition, we summarize the above works in Table posed DESMπ‘˜NN is secure. Additionally, experimental evalua- 1. tion shows that DESMπ‘˜NN improves query efficiency by up to 45.5% compared with existing π‘˜NN queries scheme on two real 3. Preliminaries datasets (California Road Network and Points of Interest, San Francisco Road Network1 ). 3.1. Voronoi diagram The rest of this paper is structured as follows. Section 2 presents related work. Section 3 describes preliminaries. The architecture and The Voronoi diagram [22] partitions the plane according to a set of security model of DESMπ‘˜NN is defined in Section 4. In Section 5, the points. Each Voronoi Cell (VC) corresponds to a point and contains all locations that are closer to this point than to any other. Two points are Voronoi neighbors if their cells share an edge, and the neighbor set of 1 https://users.cs.utah.edu/~lifeifei/SpatialDataset.htm. a point is denoted as 𝑉 𝑁(𝑝). 2 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 Table 1 Summary of existing π‘˜NN query works. Method Data privacy Query privacy Result privacy Access patterns Verifiable Multi-user POIs updating √ √ Wong [11] Γ— Γ— Γ— Γ— Γ— √ √ √ √ Elmehdwi [15] Γ— Γ— Γ— √ √ √ Choi [16] Γ— Γ— Γ— Γ— √ √ √ √ Cheng [17] Γ— Γ— Γ— √ √ √ √ √ Cui [8] Γ— Γ— √ √ √ √ Liu [14] Γ— Γ— Γ— √ √ √ √ √ √ Cui [9] Γ— √ Notations: β€˜ ’ represents the approach satisfies the condition; β€˜Γ—β€™ represents it fails to satisfy the condition. DESMπ‘˜NN introduces hierarchical clustering, which improves both the organization of spatial objects and the performance of query processing. As shown in Fig. 3, it presents an R-tree with a fanout of 𝑓 = 2, which is built from the POIs in 𝑅𝑒𝑐𝑑1 . In this construction, the data are first grouped by applying hierarchical clustering based on the Euclidean distance. This process is performed in two rounds, and the resulting clusters naturally determine the partitioning of the dataset, which is then used to build the tree structure. 3.3. Distributed two trapdoors public-key cryptosystem The DT-PKC [19] is a variant of the traditional double trapdoor decryption cryptosystem. Given a public key π‘π‘˜, a private key π‘ π‘˜, and Fig. 2. An example of Voronoi diagram. a strong private key 𝑆𝐾, the cryptosystem supports several algorithms that enable encryption, decryption, and collaborative key operations. First, encryption is carried out by the algorithm 𝐸𝑛𝑐. Given a message 𝑝 ∈ Z𝑁 and the public key π‘π‘˜, the algorithm outputs the ciphertext πΈπ‘π‘˜ (𝑝). The system then allows two types of decryption: (1) With the private key (π‘ π‘˜), the algorithm π‘Š 𝐷𝑒𝑐 takes πΈπ‘π‘˜ (𝑝) as input and recovers 𝑝. (2) With the strong private key (𝑆𝐾), the algorithm 𝑆𝐷𝑒𝑐 also decrypts πΈπ‘π‘˜ (𝑝) to obtain 𝑝. A distinctive feature of DT-PKC lies in the management of the strong private key. The algorithm π‘†π‘˜π‘’π‘¦π‘† enables the strong private key 𝑆𝐾 to be split into two partial strong private keys, 𝑆𝐾1 and 𝑆𝐾2 . This splitting supports a collaborative decryption mechanism in two steps: (1) In step 1, 𝑃 𝑆𝐷𝑒𝑐1 takes πΈπ‘π‘˜ (𝑝) and 𝑆𝐾1 as input, which results in a partially decrypted ciphertext 𝐢𝑇1 . Fig. 3. R-tree structure based on hierarchical clustering. (2) In step 2, 𝑃 𝑆𝐷𝑒𝑐2 completes the process by using 𝐢𝑇1 and 𝑆𝐾2 , which ultimately recovers 𝑝. For example, given a dataset 𝐷 that contains 16 POIs as shown in 3.4. Advanced comparable inner product encoding Fig. 2-(b), the Voronoi diagram is shown in Fig. 2-(a). Since 𝑉 𝐢(𝑝8 ) The CIPE𝑠 scheme [25] allows edges to determine whether a value shares a common edge with 𝑉 𝐢(𝑝𝑖 ) for 𝑖 ∈ {3, 4, 9, 11, 12, 13}, the lies within a query range based on encrypted data. Compared to the Voronoi neighbors of 𝑝8 include 𝑉 𝑁(𝑝8 ) = {𝑝3 , 𝑝4 , 𝑝9 , 𝑝11 , 𝑝12 , 𝑝13 }. original CIPE scheme, CIPE𝑠 enhances security by extending query Therefore, the search result of a 3NN query is 𝑅𝑒𝑠𝑒𝑙𝑑 = {𝑝9 , 𝑝11 , 𝑝13 }. vectors into random query matrices, which makes it more resilient to The Voronoi diagram has two useful properties for π‘˜NN verification: chosen plaintext attacks. (1) Given a query point π‘ž, the nearest neighbor of π‘ž is data point 𝑝, CIPE𝑠 supports several key algorithms for encryption and range query evaluation. First, the key generation algorithm 𝐺𝑒𝑛𝐾𝑒𝑦 takes a if π‘ž ∈ 𝑉 𝐢(𝑝). security parameter πœ… ∈ N as input and outputs a secret key π‘ π‘˜π‘ . The data (2) If data points 𝑝1 , … , π‘π‘˜ are the π‘˜(π‘˜ > 1) nearest neighbors of the encryption algorithm 𝐸𝑛𝑐𝐼 encrypts a plaintext π‘₯ into ciphertext 𝐸𝑐 (π‘₯) query point π‘ž, then 𝑝𝑖 belongs to 𝑉 𝑁(𝑝1 ) βˆͺ β‹― βˆͺ 𝑉 𝑁(π‘π‘–βˆ’1 ), for with π‘ π‘˜π‘ . To perform queries, the query encryption algorithm 𝐸𝑛𝑐𝑄 𝑖 = 2, … , π‘˜. transforms a query range 𝑄 = [𝑏𝑙 , 𝑏𝑒 ] into an encrypted range 𝐸𝑐 (𝑄). Finally, the calculation algorithm πΆπ‘Žπ‘™ compares the encrypted value 3.2. R-tree index based on hierarchical clustering 𝐸𝑐 (π‘₯) with the encrypted query range 𝐸𝑐 (𝑄) and outputs a comparison result: βˆ’1 if π‘₯ < 𝑏𝑙 , 1 if π‘₯ > 𝑏𝑒 , and 0 if π‘₯ ∈ [𝑏𝑙 , 𝑏𝑒 ]. The R-tree index [23] organizes spatial objects into nested rect- angles, known as Minimum Bounding Rectangles, to enable efficient 4. System architecture and security model querying of spatial data, such as range queries [24] and nearest neigh- bor searches. However, the efficiency of the R-tree strongly depends This section introduces the system architecture and security model on how the data are grouped during construction. To address this, of DESMπ‘˜NN. A summary of notations is given in Table 2. 3 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 Table 2 verification object 𝑉 𝑂 to the QU (Step 7). The QU then verifies the Summary of notations. correctness of the result before finalizing the query. 𝐷 A spatial dataset that includes 𝑛 points {𝑃1 , … , 𝑃𝑛 } 𝑉𝐷 Voronoi diagram built from 𝐷 π‘ π‘˜π‘ The secret key for CIPE𝑠 scheme 4.2. Security model π‘ π‘˜0 , π‘π‘˜0 The secret/public key for DO π‘ π‘˜π‘’ , π‘π‘˜π‘’ The secret/public key for users DESMπ‘˜NN is designed to address three security threats. First, CS 𝑆𝐾, 𝑆𝐾1 , 𝑆𝐾2 Strong private key and partial ones 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , βˆ—) The first step of partial decryption cannot be fully trusted and may tamper with query results. Second, CS 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , βˆ—, βˆ—) The second step of partial decryption may act as honest-but-curious adversaries that attempt to infer sensitive 𝑄, 𝐸𝑐 (𝑄) A query coverage and its encrypted range information from the encrypted data. Third, QUs themselves may be π‘ž, πΈπ‘π‘˜0 (π‘ž) A query point and its encrypted coordinates curious and try to learn the query information of others. 𝑃𝑖 , πΈπ‘π‘˜0 (𝑃𝑖 ) A POI and its encrypted coordinates To counter the risk of result tampering, DESMπ‘˜NN incorporates a π‘‡Μ‚π‘Ÿπ‘’π‘’π‘… , 𝑇 π‘Ÿπ‘’π‘’π‘… The encrypted/clear R-tree index built from 𝐷 Μ‚ 𝑃 𝐷, 𝑃 𝐷 The encrypted/clear preprocessed data built from 𝑉 𝐷 verification mechanism that ensures both correctness and complete- Μ‚ 𝑄 , 𝑅𝑒𝑐𝑑𝑄 𝑅𝑒𝑐𝑑 The encrypted/clear range query generated for 𝑄 ness [27]. Correctness requires that every returned point 𝑝 ∈ 𝑅𝑒𝑠𝑒𝑙𝑑 𝐼𝑅 The immediate result remains unmodified and originates from the authentic database, while Μ‚ 𝑅𝑒𝑠𝑒𝑙𝑑 𝑅𝑒𝑠𝑒𝑙𝑑, The encrypted/clear result in the exact search phase completeness guarantees that all true π‘˜NN results are included and no 𝐻(βˆ—) A hash function 𝑉𝑂 The verification object irrelevant points are omitted. The other two threats are addressed by designing a secure index and a set of novel secure protocols that jointly preserve multiple dimensions of privacy [4,28]. Specifically, data privacy ensures that the database 𝐷 remains hidden from the CS; query privacy requires that the content of a QU’s query 𝑆𝑄 is concealed from both the CS and other QUs; result privacy guarantees that only the QU can access the returned 𝑅𝑒𝑠𝑒𝑙𝑑; and access-pattern privacy prevents the CS from learning which database entries satisfy a given query. It is noteworthy that during system setup stage, CCS is prevented from compromising or collaborating with CSS. Furthermore, collusion between CS and QUs must be prevented throughout the query process. 5. DESMπ’ŒNN construction This section first introduces an optimized two-stage search frame- work that supports efficient and secure multi-user π‘˜NN queries with dynamic POIs updating. Subsequently, several well-designed secure protocols are proposed to enable private π‘˜NN search operations on the two-stage search framework. 5.1. Two-stage search framework Fig. 4. System architecture. DESMπ‘˜NN adopts a two-stage search framework, which consists of an initial filtering stage based on hierarchical clustering to effectively constrain the search range, followed by a precise search stage to 4.1. System architecture achieve efficient querying. Initial Filtering Stage: DO first preprocesses the dataset by using DESMπ‘˜NN employs a two-stage framework: an initial filtering stage hierarchical clustering to construct a suitable 𝑇 π‘Ÿπ‘’π‘’π‘… . Each node in the on ESs and a precise search stage on dual cloud servers. To protect tree is encrypted by using the CIPE𝑠 .EncI algorithm to ensure security. privacy, the system adopts a dual-cloud architecture [8,9,14,26], where The 𝑇̂ π‘Ÿπ‘’π‘’π‘… is then uploaded to ESs. When a QU at position (π‘₯π‘ž , π‘¦π‘ž ) collusion-resilient protocols ensure both efficiency and security beyond initiates a query, they define a scope 𝐿 and construct a rectangle π‘…π‘’π‘π‘‘π‘ž traditional single-cloud settings. As shown in Fig. 4, the architecture centered at (π‘₯π‘ž , π‘¦π‘ž ) with edge length 𝐿. Each dimension of π‘…π‘’π‘π‘‘π‘ž is involves several entities with distinct roles. encrypted by using the CIPE𝑠 .EncQ algorithm and sent to the nearby In the setup phase (Step 1), the Certified Authority (CA) generates Μ‚π‘ž over 𝑇̂ ES. The ES evaluates 𝑅𝑒𝑐𝑑 π‘Ÿπ‘’π‘’π‘… to generate 𝐼𝑅, which efficiently cryptographic keys: (π‘π‘˜0 , π‘ π‘˜0 ) for the DO, (π‘π‘˜π‘–π‘’ , π‘ π‘˜π‘–π‘’ ) for each QU, and narrows down the candidate objects. a split strong key (𝑆𝐾1 , 𝑆𝐾2 ), which are respectively assigned to the Precise Search Stage: Once receiving (πΈπ‘π‘˜0 (π‘ž), π‘˜) and 𝐼𝑅 from ES, two cloud servers (CSS and CCS). All public keys are shared among the the dual-cloud servers collaboratively execute secure protocols over the entities. The DO then prepares the dataset. For sensitive data (Step 2), preprocessed dataset to obtain the exact π‘˜ nearest neighbors (𝑅𝑒𝑠𝑒𝑙𝑑). it preprocesses 𝑉 𝐷 into 𝑃 𝐷, encrypts 𝑃 𝐷 with DT-PKC to obtain 𝑃 ̂𝐷, The servers also generate a verification object (𝑉 𝑂) and send it with and uploads it to CSS. For less sensitive data (Step 3), it builds an R-tree the 𝑅𝑒𝑠𝑒𝑙𝑑 back to QU for checking. This stage ensures both accuracy index 𝑇 π‘Ÿπ‘’π‘’π‘… , encrypts it with CIPE𝑠 , and distributes the encrypted index and security of the π‘˜NN search. π‘‡Μ‚π‘Ÿπ‘’π‘’π‘… to ESs for efficient query filtering. When a QU issues a query (Step 4), it constructs 𝑆𝑄 = (𝑅𝑒𝑐𝑑 Μ‚π‘ž , πΈπ‘π‘˜ 5.2. Data pre-processing 0 (π‘ž), π‘˜) and sends it to a nearby ES. The ES evaluates 𝑅𝑒𝑐𝑑 Μ‚π‘ž over π‘‡Μ‚π‘Ÿπ‘’π‘’π‘… , filters candidate results 𝐼𝑅, and forwards them together with To support DESMπ‘˜NN, DO preprocesses the dataset before outsourc- (πΈπ‘π‘˜0 (π‘ž), π‘˜) to CSS (Step 5). Next, CSS and CCS jointly execute secure ing, which aims to protect sensitive information while retaining the protocols (Step 6), and return the final result set 𝑅𝑒𝑠𝑒𝑙𝑑 along with a structural relationships required for queries. First, DO constructs a 4 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 Voronoi diagram 𝑉 𝐷 from the dataset 𝐷, and encrypts the coordinates Algorithm 1 Secure Squared Distance Computation of each POI and query point π‘ž using DT-PKC. For every POI 𝑝𝑖 ∈ Require: CSS has πΈπ‘π‘˜0 (π‘₯1 ), πΈπ‘π‘˜0 (𝑦1 ), πΈπ‘π‘˜0 (π‘₯2 ), πΈπ‘π‘˜0 (𝑦2 ); 𝑉 𝐷, a unique label ξˆΈπ‘– = 𝐻(π‘₯𝑖 |𝑦𝑖 ) is generated through the SHA- CSS has 𝑆𝐾1 , π‘π‘˜0 ; CCS has 𝑆𝐾2 , π‘π‘˜0 ; 256 hash function, which serves as a compact identifier. Subsequently, Ensure: πΈπ‘π‘˜0 (|π‘₯1 βˆ’ π‘₯2 |2 + |𝑦1 βˆ’ 𝑦2 |2 ); DO obtains the neighborhood 𝑉 𝑁(𝑝𝑖 ) and its corresponding label set // Calculation in CSS: 𝑉 π‘ξˆΈ(𝑝𝑖 ), then employs DT-PKC to encrypt the packaged 𝑉 𝑁(𝑝𝑖 ) after 1: Choose 4 random numbers π‘Ÿ1 , π‘Ÿ2 , π‘Ÿ4 , π‘Ÿ5 ∈ Z𝑁 ; applying data packaging technology [29]. This technique helps handle 2: Randomly choose the functionality 𝐹 ∈ {0, 1}; multiple values together, which makes encryption more straightfor- 3: if 𝐹 = 1 then ward. To guarantee integrity, a signature 𝑆𝐼𝐺𝑝𝑖 = 𝐻(𝐻(𝑝𝑖 )|𝐻(𝑉 𝑁(𝑝𝑖 ))) 4: πΈπ‘π‘˜0 (𝐴) ← πΈπ‘π‘˜0 (π‘₯1 ) βˆ— πΈπ‘π‘˜0 (π‘₯2 )π‘βˆ’1 ; is created, where 𝐻(𝑉 𝑁(𝑝𝑖 )) is obtained by hashing all neighbors 5: πΈπ‘π‘˜0 (𝐡) ← πΈπ‘π‘˜0 (𝑦1 ) βˆ— πΈπ‘π‘˜0 (𝑦2 )π‘βˆ’1 ; together as 6: else if 𝐹 = 0 then 𝐻(𝑉 𝑁(𝑝𝑖 )) = 𝐻(𝐻(𝑝𝑉 𝑁1 )|𝐻(𝑝𝑉 𝑁2 )|...|𝐻(𝑝𝑉 π‘π‘šπ‘Žπ‘₯ )). 7: Swap π‘₯1 with π‘₯2 and 𝑦1 with 𝑦2 ; β€²β€² β€²β€² 8: π‘Ž ← πΈπ‘π‘˜0 (𝐴)π‘Ÿ1 , 𝑏 ← πΈπ‘π‘˜0 (𝐡)π‘Ÿ2 ; Intuitively, this signature ensures any tampering with 𝑝𝑖 or its neighbors β€² β€²β€² β€² 9: π‘Ž ← 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , π‘Ž ), 𝑏 ← 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , 𝑏 ); β€²β€² can be detected. Since homomorphic encryption requires uniform input β€²β€² β€²β€² β€² β€² 10: Send π‘Ž , 𝑏 , π‘Ž , 𝑏 and πΈπ‘π‘˜0 (𝐴), πΈπ‘π‘˜0 (𝐡) to CCS; length, DO also performs incremental obfuscation: if a POI has fewer // Calculation in CCS: neighbors than the maximum in 𝑉 𝐷, dummy neighbors are added to 11: Choose a random number π‘Ÿ3 ∈ Z𝑁 ; conceal the actual degree. Afterward, each POI is represented by a β€²β€² β€² β€²β€² β€² 12: π‘Ž ← 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , π‘Ž , π‘Ž ), 𝑏 ← 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , 𝑏 , 𝑏 ); sextuple 13: if π‘Ž > 0 then 14: 𝐸1 ← πΈπ‘π‘˜0 (𝐴); (πΈπ‘π‘˜0 (𝑖𝑑), πΈπ‘π‘˜0 (𝑝𝑖 ), πΈπ‘π‘˜0 (𝑉 𝑁(𝑝𝑖 )), ξˆΈπ‘–, 𝑉 π‘ξˆΈ(𝑝𝑖 ), 𝑆𝐼𝐺𝑝𝑖 ), 15: else if πΈπ‘π‘˜0 (π‘Ÿ3 ) βˆ— πΈπ‘π‘˜0 (𝐴)π‘βˆ’1 = πΈπ‘π‘˜0 (π‘Ÿ3 ) then which combines encrypted attributes, hashed labels, and a verifiable 16: 𝐸1 ← πΈπ‘π‘˜0 (π‘Ÿ3 )0 ; signature. 17: else To further protect access pattern privacy, DO divides the sextuple 18: 𝐸1 ← πΈπ‘π‘˜0 (𝐴)π‘βˆ’1 ; table into buckets [8,9] of size 𝑀, which ensures queries operate over 19: Apply the same steps to 𝑏 to obtain 𝐸2 ; fixed-size groups instead of revealing individual record access. Since 20: Send 𝐸1 , 𝐸2 to CSS; the final bucket may not be completely filled, DO pads it with randomly // Calculation in CSS: β€²β€² generated dummy records, which prevents inference attacks [30,31] 21: 𝑐 ← 𝐸1 βˆ— πΈπ‘π‘˜0 (π‘Ÿ4 ); β€² β€²β€² where an adversary could deduce whether two queries target the 22: 𝑐 ← 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , 𝑐 ); β€²β€² β€² same bucket based on its record count. At this point, DO completes 23: Apply the same steps to 𝐸2 , π‘Ÿ5 to obtain 𝑑 , 𝑑 ; β€²β€² β€² β€²β€² β€² preprocessing and securely outsources the bucketized sextuples to CSS. 24: Send 𝑐 , 𝑐 , 𝑑 , 𝑑 to CCS; // Calculation in CCS: β€²β€² β€² 5.3. Secure Square Distance Computation(SSDC) 25: 𝑐 ← 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , 𝑐 , 𝑐 ); 26: 𝑠 ← 𝑐 βˆ— 𝑐; β€²β€² β€² The goal of SSDC is to compute the secure squared distance without 27: Apply the same steps to 𝑑 , 𝑑 to obtain 𝑑, 𝑧; revealing any valid coordinate information to CSS and CCS. The process 28: Send πΈπ‘π‘˜0 (𝑠), πΈπ‘π‘˜0 (𝑧) to CSS; is shown in Algorithm 1. // Calculation in CSS: π‘βˆ’π‘Ÿ4 π‘βˆ’π‘Ÿ Initially, CSS randomly chooses 4 random numbers π‘Ÿ1 , π‘Ÿ2 , π‘Ÿ4 , π‘Ÿ5 ∈ 29: 1 ← πΈπ‘π‘˜0 (𝑠) βˆ— 𝐸1 βˆ— 𝐸1 4 βˆ— πΈπ‘π‘˜0 (π‘Ÿ4 βˆ— π‘Ÿ4 )π‘βˆ’1 ; π‘βˆ’π‘Ÿ5 π‘βˆ’π‘Ÿ Z𝑁 , and chooses the functionality 𝐹 ∈ {0, 1} (line 1–2). If 𝐹 = 1, CSS 30: 2 ← πΈπ‘π‘˜0 (𝑑) βˆ— 𝐸2 βˆ— 𝐸2 5 βˆ— πΈπ‘π‘˜0 (π‘Ÿ5 βˆ— π‘Ÿ5 )π‘βˆ’1 ; calculates the encrypted coordinate differences πΈπ‘π‘˜0 (𝐴), πΈπ‘π‘˜0 (𝐡) (line 31: π·π‘–π‘ π‘‘π‘Žπ‘›π‘π‘’ ← πΈπ‘π‘˜0 (|π‘₯1 βˆ’ π‘₯2 |2 + |𝑦1 βˆ’ 𝑦2 |2 ) ← 1 βˆ— 2 ; 3–5). If 𝐹 = 0, the procedure is the same except that the positions of π‘₯1 and π‘₯2 , as well as 𝑦1 and 𝑦2 , are swapped when computing the differences (line 6–7). To mask these values and avoid direct leak- 5.4. Secure Minimum Computation(SMC) age, CSS applies randomization with π‘Ÿ1 and π‘Ÿ2 (line 8). Subsequently, CSS partially decrypts the masked values π‘Žβ€²β€² , 𝑏′′ by using the PSDec1 The goal of SMC is to compare two secure squared distances ob- function to get π‘Žβ€² , 𝑏′ (line 9). Eventually, CSS sends π‘Žβ€²β€² , 𝑏′′ , π‘Žβ€² , 𝑏′ and tained by SSDC, determine the smaller one, and also obtain the corre- πΈπ‘π‘˜0 (𝐴), πΈπ‘π‘˜0 (𝐡) to CCS (line 10). sponding π‘–π‘‘π‘šπ‘–π‘› and ξˆΈπ‘šπ‘–π‘› . The process is shown in Algorithm 2. Upon receiving a series of encrypted values from CSS, CCS chooses To start with, CSS generates 7 random numbers and randomly a random number π‘Ÿ3 ∈ Z𝑁 and decrypts the encrypted values to obtain selects a functionality 𝐹 , in a manner similar to SSDC (line 1–2). If π‘Ž and 𝑏 (line 11–12). To conceal the sign information of the differences, 𝐹 = 1, CSS masks the differences between the distances, identifiers, CCS applies a randomized comparison procedure (line 13–18). Specifi- and location labels by incorporating random numbers either as mul- cally, depending on the outcomes of π‘Ž versus 0 and related conditions, tiplicative factors or as exponents (line 3–10). For example, the key CCS produces three possible cases and outputs 𝐸1 accordingly; this step design prevents CSS from learning whether π‘₯1 βˆ’ π‘₯2 or 𝑦1 βˆ’ 𝑦2 is positive πΈπ‘π‘˜0 (𝛼) ← (πΈπ‘π‘˜0 (𝑑1 ) βˆ— πΈπ‘π‘˜0 (𝑑2 )π‘βˆ’1 )π‘Ÿπ›Ό or negative. The same process is repeated for 𝑏 to obtain 𝐸2 (line 19). Finally, CCS returns 𝐸1 , 𝐸2 to CSS (line 20). ensures that CCS cannot infer the exact magnitude of 𝑑1 and 𝑑2 with Upon receiving a series of encrypted values from CCS, CSS further no less than 1/2 probability, which enables to preserve the magnitude randomizes 𝐸1 and 𝐸2 with π‘Ÿ4 and π‘Ÿ5 , then partially decrypts them to relationship with semantic security. If 𝐹 = 0, the roles of 𝑑1 and 𝑑2 are produce (𝑐 β€²β€² , 𝑑 β€²β€² ) and (𝑐 β€² , 𝑑 β€² ), and sends these values to CCS (line 21–24). swapped, and the same randomization procedure follows (line 11–12). CCS completes the decryption (line 25), squares the plaintexts to derive After randomization, CSS partially decrypts one of the masked values 𝑠 = 𝑐 2 and 𝑧 = 𝑑 2 (line 26–27), and sends back πΈπ‘π‘˜0 (𝑠), πΈπ‘π‘˜0 (𝑧) (line to obtain 𝛼1 and sends it together with the corresponding encrypted 28). Finally, CSS combines these ciphertexts through homomorphic terms to CCS (line 13–14). operations to obtain 1 and 2 , and computes the secure squared Upon receiving these values, CCS decrypts 𝛼1 to obtain 𝛼2 (line 15). distance as π·π‘–π‘ π‘‘π‘Žπ‘›π‘π‘’ = 1 βˆ— 2 . By checking whether the bit-length of 𝛼2 exceeds half modulus size, CCS 5 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 decides whether 𝑑1 or 𝑑2 is smaller, and records this decision in a flag token is then partially decrypted using 𝑆𝐾1 , producing an auxiliary 𝑀 (line 16–19). Using 𝑀 and the remaining encrypted values from CSS, value that, together with the token, is stored in a permuted list under CCS computes three encrypted auxiliary terms that encode the correct a pseudo-random permutation to prevent linkability (line 7–9). After selection of the minimum distance, identifier, and label (line 20–22). completing all comparisons, CSS sends the resulting table to CCS for These results, along with 𝑀, are then sent back to CSS (line 23). further processing (line 10). On the CCS side, the server initializes an empty set and parses Algorithm 2 Secure Minimum Computation the received tokens (line 11–12). Each token is decrypted with 𝑆𝐾2 , Require: CSS has πΈπ‘π‘˜0 (𝑑1 ), πΈπ‘π‘˜0 (𝑑2 ), πΈπ‘π‘˜0 (𝑖𝑑1 ), πΈπ‘π‘˜0 (𝑖𝑑2 ), and whenever a decryption reveals equality between an element of 𝑆 Μ‚1 πΈπ‘π‘˜0 (1 ), πΈπ‘π‘˜0 (2 ); and 𝑆̂2 , the corresponding index is added to the set (line 13–15). This CSS has 𝑆𝐾1 , π‘π‘˜0 ; CCS has 𝑆𝐾2 , π‘π‘˜0 ; set, containing the indices of overlapping elements, is then returned to Ensure: πΈπ‘π‘˜0 (π‘‘π‘šπ‘–π‘› ), πΈπ‘π‘˜0 (π‘–π‘‘π‘šπ‘–π‘› ), πΈπ‘π‘˜0 (ξˆΈπ‘šπ‘–π‘› ); CSS (line 16). Finally, CSS uses the inverse permutation to locate the // Calculation in CSS: original positions and removes the identified elements from 𝑆 Μ‚1 (line 1: Choose 7 random numbers π‘Ÿπ›Ό , π‘Ÿπ›½ , π‘Ÿπ›Ύ , π‘Ÿπ›Ώ , π‘Ÿπœ– , π‘Ÿπœ , π‘Ÿπœ‚ ∈ Z𝑁 ; 17–19). The remaining encrypted elements constitute the secure set 2: Randomly choose the functionality 𝐹 ∈ {0, 1}; difference 𝑆̂′ , which represents all values in 𝑆1 but not in 𝑆2 (line 20). 3: if 𝐹 = 1 then Algorithm 3 Secure Set Difference 4: πΈπ‘π‘˜0 (𝛼) ← (πΈπ‘π‘˜0 (𝑑1 ) βˆ— πΈπ‘π‘˜0 (𝑑2 )π‘βˆ’1 )π‘Ÿπ›Ό ; 5: πΈπ‘π‘˜0 (𝛽) ← (πΈπ‘π‘˜0 (𝑑1 ) βˆ— πΈπ‘π‘˜0 (𝑑2 )π‘βˆ’1 βˆ— πΈπ‘π‘˜0 (π‘Ÿπ›½ )); Require: CSS has two sets of encrypted values Μ‚1 = {πΈπ‘π‘˜ (π‘₯1 ), ..., πΈπ‘π‘˜ (π‘₯𝑀 )}; 𝑆 6: πΈπ‘π‘˜0 (𝛾) ← (πΈπ‘π‘˜0 (𝑑2 ) βˆ— πΈπ‘π‘˜0 (𝑑1 )π‘βˆ’1 βˆ— πΈπ‘π‘˜0 (π‘Ÿπ›Ύ )); 0 0 Μ‚2 = {πΈπ‘π‘˜ (𝑦1 ), ..., πΈπ‘π‘˜ (𝑦𝑇 )}; 𝑆 7: πΈπ‘π‘˜0 (𝛿) ← (πΈπ‘π‘˜0 (𝑖𝑑1 ) βˆ— πΈπ‘π‘˜0 (𝑖𝑑2 )π‘βˆ’1 βˆ— πΈπ‘π‘˜0 (π‘Ÿπ›Ώ )); 0 0 CSS has 𝑆𝐾1 ; CCS has 𝑆𝐾2 ; 8: πΈπ‘π‘˜0 (πœ–) ← (πΈπ‘π‘˜0 (𝑖𝑑2 ) βˆ— πΈπ‘π‘˜0 (𝑖𝑑1 )π‘βˆ’1 βˆ— πΈπ‘π‘˜0 (π‘Ÿπœ– )); β€² Ensure: CSS obtains an encrypted difference set 𝑆̂ ; 9: πΈπ‘π‘˜0 (𝜁) ← (πΈπ‘π‘˜0 (1 ) βˆ— πΈπ‘π‘˜0 (2 )π‘βˆ’1 βˆ— πΈπ‘π‘˜0 (π‘Ÿπœ )); // Calculation in CSS: 10: πΈπ‘π‘˜0 (πœ‚) ← (πΈπ‘π‘˜0 (2 ) βˆ— πΈπ‘π‘˜0 (1 )π‘βˆ’1 βˆ— πΈπ‘π‘˜0 (π‘Ÿπœ‚ )); 1: Initialize 𝑇 to an empty table; 11: else if 𝐹 = 0 then Μ‚1 do 2: for the π‘–βˆ’th element πΈπ‘π‘˜0 (π‘₯𝑖 ) ∈ 𝑆 12: Swaps the roles of 𝑑1 , 𝑖𝑑1 , 1 with 𝑑2 , 𝑖𝑑2 , 2 . 3: Initialize 𝑑 to an empty list; 13: 𝛼1 ← 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , πΈπ‘π‘˜0 (𝛼)); Μ‚2 in random order do 4: for all πΈπ‘π‘˜0 (𝑦𝑗 ) ∈ 𝑆 14: Send 𝛼1 , πΈπ‘π‘˜0 (𝛼), πΈπ‘π‘˜0 (𝛽), πΈπ‘π‘˜0 (𝛾), πΈπ‘π‘˜0 (𝛿), πΈπ‘π‘˜0 (πœ–), 5: Generate a random number π‘Ÿπ‘–,𝑗 ; πΈπ‘π‘˜0 (𝜁), πΈπ‘π‘˜0 (πœ‚) to CSS; 6: 𝑑𝑖,𝑗 [0] ← (πΈπ‘π‘˜0 (π‘₯𝑖 ) βˆ— πΈπ‘π‘˜0 (𝑦𝑗 )π‘βˆ’1 )π‘Ÿπ‘–,𝑗 ; // Calculation in CCS: 7: 𝑑𝑖,𝑗 [1] ← 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , 𝑑𝑖,𝑗 [0]); 15: 𝛼2 ← 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , πΈπ‘π‘˜0 (𝛼), 𝛼1 ); 8: Append 𝑑𝑖,𝑗 to t; 16: if πΏπ‘’π‘›π‘”π‘‘β„Ž(𝛼2 ) > πΏπ‘’π‘›π‘”π‘‘β„Ž(𝑁)βˆ•2 then 9: 𝑇 [πœ‹(𝑖)] ← 𝑑; 17: 𝑀 ← 1; 10: Send 𝑇 to CCS; 18: else // Calculation in CCS: 19: 𝑀 ← 0; 11: Initialize 𝑉 to an empty set; 20: πΈπ‘π‘˜0 (πœƒ) ← (πΈπ‘π‘˜0 (𝛽)1βˆ’π‘€ βˆ— πΈπ‘π‘˜0 (𝛾)𝑀 )π‘βˆ’1 ; 12: for 𝑖 ∈ [𝑀] do 21: πΈπ‘π‘˜0 (πœ—) ← (πΈπ‘π‘˜0 (𝛿)1βˆ’π‘€ βˆ— πΈπ‘π‘˜0 (πœ–)𝑀 )π‘βˆ’1 ; 13: Parse 𝑇 [𝑖] as (𝑑𝑖,1 , ..., 𝑑𝑖,𝑇 ); 22: πΈπ‘π‘˜0 (πœ„) ← (πΈπ‘π‘˜0 (𝜁)1βˆ’π‘€ βˆ— πΈπ‘π‘˜0 (πœ‚)𝑀 )π‘βˆ’1 ; 14: if βˆƒπ‘‘π‘–,𝑗 ∈ 𝑇 [𝑖] ∩ 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , 𝑑𝑖,𝑗 [0], 𝑑𝑖,𝑗 [1]) then 23: Send 𝑀, πΈπ‘π‘˜0 (πœƒ), πΈπ‘π‘˜0 (πœ—), πΈπ‘π‘˜0 (πœ„) to CSS; 15: Add 𝑖 into set 𝑉 ; // Calculation in CSS: 16: Send 𝑉 to CSS; 24: if 𝑠 = 𝑀 then // Calculation in CSS: 25: πΈπ‘π‘˜0 (π‘‘π‘šπ‘–π‘› ) = πΈπ‘π‘˜0 (𝑑2 ) βˆ— πΈπ‘π‘˜0 (πœƒ) βˆ— πΈπ‘π‘˜0 (𝑀)π‘Ÿπ›Ύ βˆ— 17: for each element 𝑖 in 𝑉 do (πΈπ‘π‘˜0 (1 βˆ’ 𝑀))π‘Ÿπ›½ ; 18: 𝑗 ← πœ‹ βˆ’1 (𝑖); 26: πΈπ‘π‘˜0 (π‘–π‘‘π‘šπ‘–π‘› ) = πΈπ‘π‘˜0 (𝑖𝑑2 ) βˆ— πΈπ‘π‘˜0 (πœ—) βˆ— πΈπ‘π‘˜0 (𝑀)π‘Ÿπœ– βˆ— 19: Remove the π‘—βˆ’th element πΈπ‘π‘˜0 (π‘₯𝑗 ) from 𝑆 Μ‚1 ; (πΈπ‘π‘˜0 (1 βˆ’ 𝑀))π‘Ÿπ›Ώ ; Μ‚β€² ← 𝑆̂1 ; 20: 𝑆 27: πΈπ‘π‘˜0 (ξˆΈπ‘šπ‘–π‘› ) = πΈπ‘π‘˜0 (2 ) βˆ— πΈπ‘π‘˜0 (πœ„) βˆ— πΈπ‘π‘˜0 (𝑀)π‘Ÿπœ‚ βˆ— (πΈπ‘π‘˜0 (1 βˆ’ 𝑀))π‘Ÿπœ ; 28: else 5.6. Secure Insertion(SI) 29: Swaps the roles of 𝑑2 , 𝑖𝑑2 , 2 with 𝑑1 , 𝑖𝑑1 , 1 . To support secure data insertion in databases, DESMπ‘˜NN innova- At the end of Algorithm 2, CSS computes 3 encrypted values: tively proposes a secure insertion protocol. When DO inserts a new POI πΈπ‘π‘˜0 (π‘‘π‘šπ‘–π‘› ), πΈπ‘π‘˜0 (π‘–π‘‘π‘šπ‘–π‘› ), πΈπ‘π‘˜0 (ξˆΈπ‘šπ‘–π‘› ) via homomorphic encryption. The into the database, two key problems must be addressed. computation applies to 𝑠 = 𝑀 and 𝑠 β‰  𝑀 (line 24-29). In this way, the protocol securely determines the minimum distance and its associated β€’ How to determine the insertion position of the POI? information without revealing any intermediate values. β€’ How to update 𝑇 π‘Ÿπ‘’π‘’π‘… and 𝑉 𝐷? 5.5. Secure Set Difference(SSD) The first problem can be effectively resolved by CIPE𝑠 . First, DO generates an insertion query rectangle 𝑅𝑒𝑐𝑑𝑖𝑛𝑠 for the POI to be inserted, The goal of SSD is to securely compute the set difference between similar to generating a query rectangle π‘…π‘’π‘π‘‘π‘ž for the query point π‘ž in the two encrypted sets, which allows CSS to obtain the elements in 𝑆1 initial filtering stage, where the 𝐿 of the rectangle can be customized. that are not in 𝑆2 , without exposing any plaintext values. To achieve Then, DO encrypts each dimension of 𝑅𝑒𝑐𝑑𝑖𝑛𝑠 with CIPE𝑠 .EncQ algo- Μ‚1 and 𝑆 this, CSS holds the encrypted sets 𝑆 Μ‚2 together with 𝑆𝐾1 , while rithm and sends 𝑅𝑒𝑐𝑑 Μ‚ 𝑖𝑛𝑠 to ES near the inserted POI. ES will evaluate CCS holds 𝑆𝐾2 . The protocol begins with CSS initializing an empty the obtained 𝑅𝑒𝑐𝑑̂ Μ‚ 𝑖𝑛𝑠 over 𝑇 π‘Ÿπ‘’π‘’π‘… to obtain the insertion position. table and iteratively processing each encrypted element in 𝑆 Μ‚1 (line Once the insertion position is determined, the label of the inserted 1–2). For each comparison with an element in 𝑆 Μ‚2 , CSS generates a POI can be added to the 𝑇 π‘Ÿπ‘’π‘’π‘… , thus completing the update of 𝑇 π‘Ÿπ‘’π‘’π‘… . random blinding factor and constructs a masked comparison token To address the problem of how to update 𝑉 𝐷, the Bowyer-Watson that conceals the difference between the two values (line 3–6). This algorithm [32,33] is introduced. The Bowyer-Watson algorithm is an 6 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 incremental method that updates 𝑉 𝐷 by progressively updating the Delaunay triangulation. When inserting a new point, algorithm first identifies all the affected triangles, then removes them and reconstructs the triangulation mesh by using the new point and the boundary of the cavity, which ensures that the new Delaunay triangulation is valid. Since 𝑉 𝐷 and Delaunay triangulation are duals, when the Delaunay triangulation is updated by using the Bowyer-Watson algorithm, 𝑉 𝐷 is updated accordingly. When a new generating point is inserted, the shape and boundaries of the Voronoi cells are adjusted. Therefore, DO obtains the updated Voronoi diagram based on the Bowyer-Watson algorithm and can obtain the encrypted id of the newly inserted POI: πΈπ‘π‘˜0 (𝑖𝑑𝑖𝑛𝑠 ), the encrypted inserted POI: πΈπ‘π‘˜0 (𝑝𝑖𝑛𝑠 ), the label of the newly inserted POI: ξˆΈπ‘–π‘›π‘  , the encrypted Voronoi neighbors: πΈπ‘π‘˜0 (𝑉 𝑁(𝑝𝑖𝑛𝑠 )), the encrypted labels of Voronoi neighbors: πΈπ‘π‘˜0 (𝑉 π‘ξˆΈ(𝑝𝑖𝑛𝑠 )), and the signature: 𝑆𝐼𝐺𝑖𝑛𝑠 used for verification. Finally, these six values are Fig. 5. Secure insertion and deletion in R-tree. (For interpretation of the organized into a tuple and sent to CSS for storage. As shown in Fig. references to color in this figure legend, the reader is referred to the web version of this article.) 5, the secure insertion in the R-tree is highlighted with green lines. Algorithm 4 Secure π‘˜NN Query Require: CSS has 𝐼𝑅, πΈπ‘π‘˜0 (π‘ž), 𝑆𝐾1 ; CCS has 𝑆𝐾2 ; diagrams. The key idea behind dynamic deletion and update algorithm Ensure: CSS obtains the encrypted search result 𝑅𝑒𝑠𝑒𝑙𝑑; is that Voronoi diagrams and Delaunay triangulations are dual to each // Calculations in CSS and CCS: other: the vertices of Delaunay triangles correspond to the vertices of 1: CSS initializes 𝑅, 𝐢, 𝐷𝑒 to empty sets; Voronoi diagram, and the edges of Delaunay triangles correspond to the 2: for each triple (πΈπ‘π‘˜0 (𝑝𝑖 ), πΈπ‘π‘˜0 (𝑖𝑑𝑖 ), πΈπ‘π‘˜0 (ξˆΈπ‘– )) ∈ 𝐼𝑅 do edges of Voronoi diagram. The Delaunay triangulation-based Voronoi 3: CSS appends πΈπ‘π‘˜0 (𝑃𝑖 ) to 𝐢; diagram dynamic deletion and update algorithm leverages the duality 4: CSS with input (𝐢, πΈπ‘π‘˜0 (π‘ž), 𝑆𝐾1 , π‘π‘˜0 ) and CCS with input (𝑆𝐾2 , π‘π‘˜0 ) of Delaunay triangles to efficiently update Voronoi diagram. When a run SSDC protocol, and CSS obtains {π·π‘–π‘ π‘‘π‘Žπ‘›π‘π‘’1 , ..., π·π‘–π‘ π‘‘π‘Žπ‘›π‘π‘’|𝐢| }; point is deleted, the corresponding Delaunay triangles are removed, 5: if |𝐢| β‰₯ π‘˜ then and the algorithm updates the connectivity of affected neighboring |𝐢| 6: ({π·π‘–π‘ π‘‘π‘Žπ‘›π‘π‘’π‘– , πΈπ‘π‘˜0 (𝑖𝑑𝑖 ), πΈπ‘π‘˜0 (ξˆΈπ‘– )}𝑖=1 , 𝑆𝐾1 , π‘π‘˜0 ) as triangles to maintain the Delaunay condition, which ensures that input in CSS and CCS with input (𝑆𝐾2 , π‘π‘˜0 ) run the triangulation is reconstructed. Then, based on the new Delaunay SMC protocol, and CSS puts (πΈπ‘π‘˜0 (π‘–π‘‘π‘–βˆ— ))π‘˜π‘–=1 triangulation, Voronoi diagram’s boundaries are updated to ensure the into 𝑅𝑒𝑠𝑒𝑙𝑑; 7: else correct topological structure of the diagram. |𝐢| Similarly, DO obtains the updated 𝑉 𝐷 and the labels of affected 8: ({π·π‘–π‘ π‘‘π‘Žπ‘›π‘π‘’π‘– , πΈπ‘π‘˜0 (𝑖𝑑𝑖 ), πΈπ‘π‘˜0 (ξˆΈπ‘– )}𝑖=1 , 𝑆𝐾1 , π‘π‘˜0 ) as input in CSS and CCS with input (𝑆𝐾2 , π‘π‘˜0 ) run POIs ξˆΈπ‘Žπ‘“ 𝑓 𝑒𝑐𝑑𝑖 , the encrypted Voronoi neighbors πΈπ‘π‘˜0 (𝑉 𝑁(π‘π‘Žπ‘“ 𝑓 𝑒𝑐𝑑𝑖 )), the SMC protocol, and CSS puts (πΈπ‘π‘˜0 (𝑖𝑑1βˆ— )) into encrypted labels of Voronoi neighbors πΈπ‘π‘˜0 (𝑉 π‘ξˆΈ(π‘π‘Žπ‘“ 𝑓 𝑒𝑐𝑑𝑖 )), and the 𝑅𝑒𝑠𝑒𝑙𝑑 and puts (πΈπ‘π‘˜0 (ξˆΈβˆ—1 )) into 𝐷𝑒; signature π‘†πΌπΊπ‘Žπ‘“ 𝑓 𝑒𝑐𝑑𝑖 used for verification. Finally, these four values are 9: CSS and CCS collaborate to run SCR protocol to get the row organized into a quadruple and sent to CSS, which updates the database corresponding to the πΈπ‘π‘˜0 (𝑖𝑑1βˆ— ); based on the labels of the affected POIs. As shown in Fig. 5, the secure 10: CSS with input (πΈπ‘π‘˜0 (𝑉 π‘ξˆΈ(π‘βˆ—1 )), 𝐷𝑒, 𝑆𝐾1 ) and CCS with input 𝑆𝐾2 β€² deletion in the R-tree is highlighted with red lines. run SSD protocol, and CSS obtains 𝑉 π‘ξˆΈ (π‘βˆ—1 ); β€² 11: for πΈπ‘π‘˜0 (𝑝𝑗 ) ∈ πΈπ‘π‘˜0 (𝑉 𝑁(π‘βˆ—1 )) ∩ 𝑉 π‘ξˆΈ (π‘βˆ—1 ) do Algorithm 5 Secure Transformation 12: CSS puts πΈπ‘π‘˜0 (𝑝𝑗 ) into 𝐢 and πΈπ‘π‘˜0 (ξˆΈπ‘— ) into 𝐷𝑒; 13: CSS and CCS collaborate to run SSD and SMC protocols to select Require: CSS has πΈπ‘π‘˜0 (π‘Ž), 𝑆𝐾1 ; the POI closest to π‘ž from 𝐢 again, and removing it from 𝐢; CCS has 𝑆𝐾2 ; 14: CSS inserts πΈπ‘π‘˜0 (𝑖𝑑2βˆ— ) into 𝑅𝑒𝑠𝑒𝑙𝑑; Ensure: CSS obtains πΈπ‘π‘˜π‘’ (π‘Ž); 15: while |𝑅| < π‘˜ // Calculations in CSS: 16: Repeat line 9-14; 1: Choose one random number π‘Ÿ ∈ Z𝑁 ; 2: πΈπ‘π‘˜0 (𝛼) = πΈπ‘π‘˜0 (π‘Ž) βˆ— πΈπ‘π‘˜0 (π‘Ÿ); β€² 3: 𝛼 ← 𝑃 𝑆𝐷𝑒𝑐1(𝑆𝐾1 , πΈπ‘π‘˜0 (𝛼)); 5.7. Secure Deletion(SD) β€² 4: Send πΈπ‘π‘˜0 (𝛼), 𝛼 to CCS; // Calculations in CCS: To support secure data deletion in database, DESMπ‘˜NN innovatively 5: 𝛼 ← 𝑃 𝑆𝐷𝑒𝑐2(𝑆𝐾2 , πΈπ‘π‘˜0 (𝛼), 𝛼 ); β€² proposes a secure deletion protocol. First, DO generates an deletion 6: Send πΈπ‘π‘˜π‘’ (𝛼) to CSS; query rectangle 𝑅𝑒𝑐𝑑𝑑𝑒𝑙 for the POI to be deleted, where the 𝐿 of the // Calculations in CSS: rectangle can be customized. Then, DO encrypts each dimension of 7: πΈπ‘π‘˜π‘’ (π‘Ž) = πΈπ‘π‘˜π‘’ (𝛼) βˆ— πΈπ‘π‘˜π‘’ (π‘Ÿ)π‘βˆ’1 ; Μ‚ 𝑅𝑒𝑐𝑑𝑑𝑒𝑙 with the CIPE𝑠 .EncQ algorithm and sends 𝑅𝑒𝑐𝑑 𝑑𝑒𝑙 to ES near the Μ‚ deleted POI. ES will evaluate the obtained 𝑅𝑒𝑐𝑑 Μ‚ 𝑑𝑒𝑙 over 𝑇 π‘Ÿπ‘’π‘’π‘… to obtain the deletion position. Once the deletion position is determined, DO sends ξˆΈπ‘‘π‘’π‘™ , which is 6. DESMπ’ŒNN query processing the label of the POI, to ES near the deleted POI. ES deletes the POI label from the data at deletion location based on ξˆΈπ‘‘π‘’π‘™ sent by DO. At this point, the deletion update of 𝑇 π‘Ÿπ‘’π‘’π‘… is completed. This section provides a detailed introduction to DESMπ‘˜NN query Similar to SI protocol, DESMπ‘˜NN introduces a Delaunay processing, which consists of two parts: secure π‘˜NN query processing triangulation-based dynamic deletion and update algorithm for Voronoi and verification processing. 7 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 6.1. Secure π‘˜NN query processing β€’ Verifying completeness: Similar to correctness, completeness is de- fined as follows: all the points returned are valid solutions to the Based on comprehensive search framework, DESMπ‘˜NN proposes a π‘˜NN query, while the points not returned do not correspond to secure and verifiable query processing strategy, which is divided into the actual answers. First, assume that π‘βˆ—π‘– represents the 𝑖th nearest three steps as follows: point to the query point π‘ž in 𝑅𝑒𝑠𝑒𝑙𝑑. Subsequently, based on the properties of the Voronoi diagram, 𝑉 𝐢(π‘βˆ—π‘– ) can be derived from β€’ Step 1. Calculating k nearest neighbors: The specific details and 𝑉 𝑁(π‘βˆ—π‘– ) and π‘βˆ—π‘– . The specific process is divided into four steps: (1) procedures are illustrated in Algorithm 4. First, CSS will create determine the coordinates of the neighboring points; (2) calculate three new sets, which includes the result set 𝑅𝑒𝑠𝑒𝑙𝑑, the candidate the perpendicular bisectors between π‘βˆ—π‘– and each neighboring set 𝐢, and the deduplication set 𝐷𝑒 (line 1). After initial filtering point; (3) identify the intersection points of all these perpen- stage, CSS has 𝐼𝑅 = {(πΈπ‘π‘˜0 (𝑝𝑖 ), πΈπ‘π‘˜0 (𝑖𝑑𝑖 ), πΈπ‘π‘˜0 (ξˆΈπ‘– ))}. Next, CSS dicular bisectors, these intersection points form the vertices of will insert each encrypted POI πΈπ‘π‘˜0 (𝑝𝑖 ) from 𝐼𝑅 into 𝐢 (line the polygon, which represent the Voronoi cell; (4) connect these 2–3). Since CSS has already stored the encrypted query point vertices in either a clockwise or counterclockwise order to form πΈπ‘π‘˜0 (π‘ž), the SSDC protocol is executed for each intermediate POI the Voronoi cell surrounding the point π‘βˆ—π‘– . Thereafter, the final verification is conducted based on the two important properties to obtain the secure squared distance between each POI and the of the Voronoi diagram. The first step is to determine whether π‘ž query point (line 4). If |𝐢| β‰₯ π‘˜, which means that the required lies within 𝑉 𝐢(π‘βˆ—1 ). If it does, π‘βˆ—1 is confirmed as the nearest POI; π‘˜ POIs can be found in 𝐼𝑅, CSS and CCS will collaborate to otherwise, the verification process is terminated immediately. execute SMC protocol to obtain the desired π‘˜ POIs (line 5–6). If The second step is to test each point (except for π‘βˆ—1 ) in 𝑅𝑒𝑠𝑒𝑙𝑑 |𝐢| < π‘˜, CSS and CCS collaborate to execute the SMC protocol individually, which determines whether π‘βˆ—π‘– ∈ {𝑉 𝑁(π‘βˆ—1 ) βˆͺ β‹― βˆͺ to obtain the nearest POI, and insert the corresponding πΈπ‘π‘˜0 (𝑖𝑑1βˆ— ) 𝑉 𝑁(π‘βˆ—π‘–βˆ’1 )}, 𝑖 > 1. If it does, π‘βˆ—π‘– is confirmed as the 𝑖th nearest POI. into 𝑅𝑒𝑠𝑒𝑙𝑑, and the corresponding πΈπ‘π‘˜0 (ξˆΈβˆ—1 ) into 𝐷𝑒 (line 7–8). To further get the next nearest neighbor, CSS and CCS collaborate 7. Analysis to execute the SCR protocol [8,9], to get the row corresponding to the πΈπ‘π‘˜0 (𝑖𝑑1βˆ— ): πΈπ‘π‘˜0 (𝑉 𝑁(π‘βˆ—1 )), 𝑉 π‘ξˆΈ(π‘βˆ—1 ), π‘†πΌπΊπ‘βˆ— (line 9). CSS and 1 7.1. Computational complexity CCS collaborate to execute the SSD protocol, with two input sets 𝑉 π‘ξˆΈ(π‘βˆ—1 ) and 𝐷𝑒. CSS obtains 𝑉 π‘ξˆΈβ€² (π‘βˆ—1 ) (line 10). If one To verify the efficiency of DESMkNN, we analyze the computational POI πΈπ‘π‘˜0 (𝑃𝑗 ) in πΈπ‘π‘˜0 (𝑉 𝑁(π‘βˆ—1 )) also exists in 𝑉 π‘ξˆΈβ€² (π‘βˆ—1 ), πΈπ‘π‘˜0 (𝑝𝑗 ) complexity of all four entities involved in the system: DO, QU, ESs, and is added to 𝐢, and πΈπ‘π‘˜0 (ξˆΈπ‘— ) is added to 𝐷𝑒 (line 11–12). CSS dual-cloud servers. Let 𝑒𝑐 and 𝑑𝑐 denote the encryption and decryption and CCS collaborate to execute SSD protocol and SMC protocol, operations of CIPE𝑆 , and let 𝑒𝑑𝑑 and 𝑑𝑑𝑑 represent the encryption and which selects the POI closest to the query point from 𝐢 again decryption operations of DT-PKC. and removes it from 𝐢 (line 13). CSS inserts πΈπ‘π‘˜0 (𝑖𝑑2βˆ— ), which corresponds to the obtained point, into 𝑅𝑒𝑠𝑒𝑙𝑑 and checks whether (1) DO: In the data pre-processing stage, DO needs to generate the content in 𝑅𝑒𝑠𝑒𝑙𝑑 meets the requirements of π‘˜NN queries. If 𝑇 π‘Ÿπ‘’π‘’π‘… and 𝑉 𝐷 based on the database 𝐷. 𝑇 π‘Ÿπ‘’π‘’π‘… and the 𝑃 𝐷 not, Sπ‘˜Q will repeat line 9–14. generated from 𝑉 𝐷 are encrypted by using CIPE𝑆 and DT-PKC, respectively. Therefore, the total computational complexity is β€’ Step 2. Generating verification object : During secure π‘˜NN queries, 𝑂(𝑛)𝑒𝑐 + 𝑂(𝑛 βˆ— 𝑀)𝑒𝑑𝑑 , DESMπ‘˜NN also need to generate 𝑉 𝑂. By collaborating to execute the SCR protocol, CSS and CCS can obtain πΈπ‘π‘˜0 (𝑉 𝑁(𝑝𝑖 )) and where 𝑀 represents the maximum number of neighbors in 𝑉 𝐷. 𝑆𝐼𝐺𝑝𝑖 from the row, which corresponds to 𝑝𝑖 . Additionally, al- (2) QU : Due to the key conversion mechanism in Algorithm 5, QU gorithm 5 enables key conversion, which transforms πΈπ‘π‘˜0 (𝑉 𝑁(𝑝𝑖 )) only needs to perform a single DT-PKC decryption to obtain the into πΈπ‘π‘˜π‘’ (𝑉 𝑁(𝑝𝑖 )). At last, CSS adds πΈπ‘π‘˜π‘’ (𝑉 𝑁(𝑝𝑖 )) and πΈπ‘π‘˜π‘’ (𝑆𝐼𝐺𝑝𝑖 ) final result and 𝑉 𝑂. Thus, the computational cost is 𝑂(1)𝑑𝑑𝑑 . of each result point into 𝑉 𝑂. (3) ESs: The ESs perform initial filtering by evaluating the encrypted Μ‚π‘ž over the encrypted R-tree 𝑇̂ query rectangle 𝑅𝑒𝑐𝑑 π‘Ÿπ‘’π‘’π‘… to gen- β€’ Step 3. Returning results and verification object to QU : Based on erate the intermediate result set 𝐼𝑅. Their total computational secure protocols we proposed, CSS can directly retrieve the final complexity is 𝑂(π‘™π‘œπ‘”π‘› )𝑑𝑐 . results encrypted with π‘π‘˜π‘’ in order, without needing an additional (4) Dual-Cloud Servers: The dual-cloud servers undertake the pre- transformation process. Therefore, CSS puts the final points into cise search stage and therefore incur the highest computational 𝑅𝑒𝑠𝑒𝑙𝑑 and sends it, along with 𝑉 𝑂, to QU. complexity, as this stage requires executing several secure sub- protocols. Specifically, the SSDC protocol is used to compute 6.2. Verification processing the secure squared distance between the query point π‘ž and each POI in the intermediate result set 𝐼𝑅. The SMC protocol is re- sponsible for comparing encrypted distance values and obtaining QU utilizes 𝑅𝑒𝑠𝑒𝑙𝑑 and 𝑉 𝑂 to authenticate the correctness and the corresponding encrypted identifiers and location records. To completeness of 𝑅𝑒𝑠𝑒𝑙𝑑. determine the nearest POI among candidates, the SMC proto- β€’ Verifying correctness: Recall the definition of correctness described col must be executed 𝑛-1 times. In addition, the SSD protocol in the security model, which means that each returned point computes the set difference between two encrypted sets and must perform DT-PKC decryption |𝑆 Μ‚1 | βˆ— |𝑆 Μ‚2 | times. The overall 𝑝 ∈ 𝑅𝑒𝑠𝑒𝑙𝑑 remains unmodified and is an authentic entry in the complexity depends on whether the number of candidates in original database. To verify the correctness of 𝑅𝑒𝑠𝑒𝑙𝑑, QU first de- 𝐼𝑅 is greater than or smaller than π‘˜. When |𝐼𝑅| > π‘˜, the crypts 𝑉 𝑂 by using his private key π‘ π‘˜π‘’ to obtain {𝑉 𝑁(𝑝𝑖 ), 𝑆𝐼𝐺𝑝𝑖 }. SkQ protocol repeatedly invokes the SMC protocol to iteratively Next, QU uses the obtained 𝑉 𝑁(𝑝𝑖 ) to compute 𝐻(𝑉 𝑁(𝑝𝑖 )) and determine the top-π‘˜ POIs, which requires (|𝐼𝑅|βˆ’1+|𝐼𝑅|βˆ’π‘˜) βˆ— π‘˜βˆ•2 further calculates 𝐻(𝐻(𝑝𝑖 )|𝐻(𝑉 𝑁(𝑝𝑖 ))) (the specific method has executions in total. In this case, the computational complexity of been detailed in Data Pre-processing). Finally, QU only needs to the precise search stage is check whether 𝑆𝐼𝐺𝑝𝑖 matches the computed 𝐻(𝐻(𝑝𝑖 )|𝐻(𝑉 𝑁(𝑝𝑖 ))) to verify correctness. 𝑂(|𝐼𝑅| βˆ— π‘˜)(𝑒𝑑𝑑 + 𝑑𝑑𝑑 ), 8 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 Table 3 Computational complexity of existing approaches and DESMπ‘˜NN. DO QU ES Dual-cloud servers { 𝑂(|𝐼𝑅| βˆ— π‘˜)(𝑒𝑑𝑑 + 𝑑𝑑𝑑 ) DESMπ‘˜NN 𝑂(𝑛)𝑒𝑐 + 𝑂(𝑛 βˆ— 𝑀)𝑒𝑑𝑑 𝑂(1)𝑑𝑑𝑑 𝑂(π‘™π‘œπ‘”π‘› )𝑑𝑐 √ 𝑂(|𝐼𝑅| + π‘˜2 βˆ— 𝑀)𝑒𝑑𝑑 + 𝑂(|𝐼𝑅| + π‘˜ βˆ— ( 𝑛 + π‘˜ βˆ— 𝑀))𝑑𝑑𝑑 2 √ MSVπ‘˜NN [9] 𝑂(π‘š βˆ— 𝑔 + 𝑛 βˆ— 𝑀)𝑒𝑑𝑑 𝑂(1)𝑑𝑑𝑑 – 𝑂(π‘˜ βˆ— (𝑛 + 𝑀))𝑒𝑑𝑑 + 𝑂(π‘˜ βˆ— ( 𝑛 + 𝑀))𝑑𝑑𝑑 { 𝑂(|𝐼𝑅| βˆ— π‘˜)(𝑒𝑝 + 𝑑𝑝 ) SecVKQ [14] 𝑂(𝑛)𝑒𝑐 + 𝑂(𝑛 βˆ— 𝑀)𝑒𝑝 𝑂(1)(𝑒𝑐 + 𝑒𝑝 ) 𝑂(π‘™π‘œπ‘”π‘› )𝑑𝑐 𝑂(|𝐼𝑅| + π‘˜2 βˆ— 𝑀)(𝑒𝑝 + 𝑑𝑝 ) √ SVπ‘˜NN [8] 𝑂(π‘š2 βˆ— 𝑔 + 𝑛 βˆ— 𝑀)𝑒𝑝 𝑂(1)𝑑𝑝 – 𝑂(π‘˜ βˆ— (𝑛 + 𝑀))𝑒𝑝 + 𝑂(π‘˜ βˆ— ( 𝑛 + 𝑀))𝑑𝑝 Notations: Let 𝑛 represents the size of dataset 𝐷, π‘˜ represents the search parameter for π‘˜NN search, and 𝑀 represents the maximal number of Voronoi neighbors. π‘š refers to the number of grids, while 𝑔 represents the maximum number of grid points, as discussed in [8,9]. Table 4 Theorem 1. The DT-PKC cryptosystem described in Section 3 is seman- Comparison of communication costs (MB) under the setting of 𝐾 = tically secure under the assumed intractability of the DDH problem over {1024, 2048}. Zβˆ— 2 . This ensures that ciphertexts produced by DT-PKC reveal no infor- 𝑁 𝑛 DESMπ‘˜NN MSVπ‘˜NN mation about the underlying plaintexts, even to computationally bounded California San Francisco California San Francisco adversaries (The details of the proof can be referred to [19]). 1024 2048 1024 2048 1024 2048 1024 2048 1024 6.1 12.7 5.9 12.3 6.5 13.1 6.1 12.4 Theorem 2 (Composition Theorem [35]). If a protocol is composed of mul- 2048 12.8 27.8 11.9 25.6 14.3 31.4 13.9 30.7 tiple subprotocols, each of which is secure under the simulation paradigm, and all intermediate values are either random or pseudorandom, the com- posed protocol is secure. This theorem allows the security of DESMπ‘˜NN to When |𝐼𝑅| < π‘˜, the nearest POI is first identified by using |𝐼𝑅|βˆ’1 be deduced from the security of its individual subprotocols. SMC comparisons. Next, the SCR protocol is executed to locate the bucket row containing this POI, after which the remaining Theorem 3 (Security of SSDC). Assuming DT-PKC is semantically se- π‘˜ βˆ’ 1 POIs are obtained through the subsequent steps of SkQ. cure, the SSDC subprotocol securely computes encrypted squared distances In this case, the computational complexity of the precise search between the query point and candidate points in 𝐼𝑅 for semi-honest adver- stage is saries. √ 𝑂(|𝐼𝑅| + π‘˜2 βˆ— 𝑀)𝑒𝑑𝑑 + 𝑂(|𝐼𝑅| + π‘˜ βˆ— ( 𝑛 + π‘˜ βˆ— 𝑀))𝑑𝑑𝑑 . Proof. In SSDC, the cloud server’s view consists of the ciphertexts π‘Žβ€²β€² , 𝑏′′ , π‘Žβ€² , 𝑏′ , which are derived from plaintext differences scaled by where 𝑀 denotes the maximum number of neighbors in the random factors, and the encrypted comparison results 𝐸1 , 𝐸2 . The sim- Voronoi diagram. The comparison results between DESMπ‘˜NN ∏ ulated view 𝑠𝐢𝐢𝑆 (𝑆𝑆𝐷𝐢) is constructed by sampling all elements uni- and existing secure π‘˜NN query schemes are summarized in Table 3. formly at random from the appropriate domain. The semantic security of DT-PKC ensures that π‘Žβ€²β€² , 𝑏′′ , π‘Žβ€² , 𝑏′ are computationally indistinguish- Moreover, The computational complexity of POI insertion and dele- able from the corresponding simulated values (π‘Žβ€²β€² β€²β€² β€² β€² 𝑠 , 𝑏𝑠 , π‘Žπ‘  , 𝑏𝑠 ). Similarly, tion in DESMπ‘˜NN is 𝑂(π‘™π‘œπ‘”π‘› + π‘™π‘œπ‘”(𝑀1 )) on average, which is asymp- the randomized encryption of the comparison outcomes 𝐸1 , 𝐸2 ensures totically equivalent to 𝑂(π‘™π‘œπ‘”(𝑀1 𝑛)). Here, 𝑀1 represents the number that these values are indistinguishable from their simulated counter- of neighboring POIs affected by the local Voronoi diagram update. parts 𝐸1𝑠 , 𝐸2𝑠 . This demonstrates that the real execution reveals no This complexity arises from updating the encrypted R-tree and locally additional information beyond what is contained in the input and maintaining the Voronoi diagram. output, which confirms the security of SSDC. For CSS, the execu- ∏ tion image is 𝐢𝐢𝑆 (𝑆𝑆𝐷𝐢) = {𝐸1 , 𝐸2 }, and the simulated image is βˆπ‘  7.2. Communication complexity 𝐢𝐢𝑆 (𝑆𝑆𝐷𝐢) = {𝐸1𝑠 , 𝐸2𝑠 }. Since 𝐸1 , 𝐸2 are produced by randomized procedures, they are computationally indistinguishable from 𝐸1𝑠 , 𝐸2𝑠 , In this subsection, the communication cost incurred during the which further supports the security argument. entire query processing is evaluated. As shown in Table 4, it presents the communication cost of DESMπ‘˜NN compared with MSVπ‘˜NN. It is Theorem 4 (Security of SMC). Assuming DT-PKC is semantically secure, observed that DESMπ‘˜NN consistently incurs the lowest communication the SMC protocol securely compares encrypted distance values and returns cost. These experimental results align well with the theoretical analysis. encrypted identifiers or labels. 7.3. Security analysis Proof. In SMC, the server’s view contains ciphertexts (πΈπ‘π‘˜0 (𝛼), 𝛼1 , 𝛼2 ) ∏ and a local output bit 𝑀. The simulated view 𝑠𝐢𝐢𝑆 (𝑆𝑀𝐢) is obtained To establish the security of the proposed subprotocol, it is important by sampling all elements randomly. Semantic security guarantees that to highlight that the semantic security of the DT-PKC cryptosystem has (πΈπ‘π‘˜0 (𝛼), 𝛼1 ) are indistinguishable from their simulated counterparts been proven in [19]. Additionally, in accordance with the formal secu- (πΈπ‘π‘˜0 (𝛼)𝑠 , 𝛼1𝑠 ). Additionally, 𝛼2 is derived from random coin flips and rity definition of multiparty computation introduced in [29] and [34], is indistinguishable from 𝛼2𝑠 . The local output bit 𝑀 also matches the framework of the simulation paradigm proposed in [35] is adopted. the distribution of the simulated 𝑀𝑠 . Hence, the simulated view is Specifically, the simulation paradigm requires that the view of each computationally indistinguishable from the real view, which confirms participant in the protocol can be simulated based solely on its input the security of SMC. and output, which ensures that no participant gains any additional in- formation from the protocol. In other words, the real execution of each Theorem 5 (Security of DESMπ‘˜NN). If DT-PKC is semantically secure, subprotocol is computationally indistinguishable from its simulated DESMπ‘˜NN is secure under the semi-honest model. counterpart. For clarity, the SSDC and SMC are formally demonstrated as examples, and other protocols we proposed can be proven in a Proof. Since each subprotocol (SSDC, SMC, SSD, and others) produces similar manner. views indistinguishable from their respective simulated views, and all 9 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 Fig. 6. The data processing time with varying parameters. Fig. 7. Comparison of search time between MSVπ‘˜NN and DESMπ‘˜NN on two datasets (π‘˜ = 1 to 10). intermediate values are either DT-PKC ciphertexts or explicitly ran- 8.1. Parameter setting domized, the composition theorem applies. Consequently, the overall DESMπ‘˜NN protocol is secure, ensuring confidentiality of the database, The evaluation of DESMπ‘˜NN is carried out on a system equipped privacy of queries, and integrity of computation. with an Intel Core i7-14650HQ processor, clocked at 2.80 GHz, and 16 GB of RAM, which runs Windows 11. For this purpose, the DT- In DESMπ‘˜NN, a quantitative security comparison across existing PKC cryptosystem is implemented by using the JAVA development kit, methods is not conducted due to significant differences in their threat models, cryptographic assumptions, and supported functionalities, which forms the core element of the proposed protocol. which make such evaluation extremely difficult. Instead, DESMπ‘˜NN In the experiment, the dataset size 𝑛 ranges from 1024 to 2024. The focuses on formally achieving and proving multiple security properties search parameter π‘˜ is set between 1 and 10. The key size 𝐾 of the DT- that prior methods do not simultaneously provide. DESMπ‘˜NN ensures PKC cryptosystem are selected from {1024, 2048, 3072}. These settings data privacy, query privacy, result privacy, and access patterns privacy, apply to all values of 𝑛, π‘˜, 𝐾 in the experiment. While implementing the while also supporting result verification, multi-user querying, and MSVπ‘˜NN and SVπ‘˜NN schemes, the grid granularity is fixed at 90 and dynamic updates to the encrypted POIs database in outsourced POIs the cryptographic hash functions are implemented via HMAC-SHA-256. queries, which prior methods cannot achieve simultaneously. 8.2. Experiment results 8. Experimental evaluation The following analysis of the experimental results will focus on DO This section evaluates the computational cost of DESMπ‘˜NN by us- and Dual-Cloud Servers. It should be noted that the experiment results ing real-world datasets for spatial databases: California Road Network for the CIPE𝑠 scheme are not included, as its execution time is negligible and San Francisco Road Network. A comparison is made between compared to the DT-PKC cryptosystem. For example, the CIPE𝑠 scheme DESMπ‘˜NN and scheme MSVπ‘˜NN [9] in different phases. takes less than 1 s to retrieve 𝐼𝑅 from 1 million POIs. 10 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 Fig. 8. Comparison of search time between MSVπ‘˜NN and DESMπ‘˜NN on two datasets (𝐾 = 1024 to 3072). Fig. 9. Comparison of search time between MSVπ‘˜NN and DESMπ‘˜NN on two datasets (𝑛 = 1024 to 2024). Fig. 10. The search time of DESMπ‘˜NN on two datasets (𝐾 = 1024 to 3072). β€’ DO: The execution time in data preprocessing are shown in Fig. that in Fig. 7, both datasets (California Road Network and Points 6. The computational cost includes two components: the cost of Interest, San Francisco Road Network) are real-world datasets, of encrypting 𝑉 𝐷 and the cost of generating 𝑆𝐼𝐺. Experiment where realistic POI distributions result in consistent performance results show that MSVπ‘˜NN and SVπ‘˜NN require additional oper- gaps between DESMπ‘˜NN and MSVπ‘˜NN. Moreover, real-world ations such as grid partition, grid padding, and grid encryption, datasets often exhibit a high density of POIs. Due to the grid and thus perform worse in this stage. partitioning mechanism, MSVπ‘˜NN tends to be inefficient when handling real-world datasets. For example, in the California road β€’ Dual-Cloud Servers: As shown in Section 7, the execution time network dataset, when setting the fine-grained grid parameter π‘š in search stage is influenced by parameters 𝑛, π‘˜, 𝐾. Experiments in MSVπ‘˜NN to 32 (which is the optimal parameter for MSVπ‘˜NN), are conducted under different parameter settings to demonstrate the number of POIs contained within each grid reaches as high as the effectiveness of DESMπ‘˜NN. We can observe that the search 108. To utilize data packing techniques, the parameter 𝐾 needs time of DESMπ‘˜NN is significantly shorter than MSVπ‘˜NN, as shown to be adjusted to no less than 4096, which results in extremely in Figs. 7–9, primarily because MSVπ‘˜NN incurs a high computa- high computational costs. However, in DESMπ‘˜NN, well-designed tional cost when executing the critical SGC protocol. Please note data structures are employed to regulate the number of POIs 11 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 per partition, which keeps 𝐾 within a reasonable range and References prevents excessive computational overhead. As shown in Fig. 10, when 𝐼𝑅 is smaller than the query parameter π‘˜, the query time [1] R. Li, A. Liu, A. Wang, Fast and scalable range query processing with strong privacy protection for cloud computing, IEEE/ACM Trans. Netw. 24 (4) (2015) is significantly higher compared to when 𝐼𝑅 exceeds π‘˜, since 2305–2318. CS need to perform more calculations related to homomorphic [2] G. Xiao, F. Wu, X. Zhou, K. Li, Probabilistic top-k range query processing for encryption. For a given scheme, larger values of π‘˜ and 𝑛 increase uncertain databases, J. Intell. Fuzzy Syst. 31 (2) (2016) 1109–1120. query time by expanding the search space and raising computa- [3] K. Xue, S. Li, J. Hong, Y. Xue, N. Yu, P. Hong, Two-cloud secure database tional demands. Likewise, a larger 𝐾 leads to longer plaintexts for for numeric-related SQL range queries with privacy preserving, IEEE Trans. Inf. Forensic Secur. 12 (7) (2017) 1596–1608. encryption, which adds overhead from cryptographic operations. [4] Y. Miao, Y. Yang, X. Li, K.-K.R. Choo, X. Meng, R.H. Deng, Comprehensive survey on privacy-preserving spatial data query in transportation systems, IEEE Trans. In general, it can be concluded that DESMπ‘˜NN not only meets the Intell. Transp. Syst. 24 (12) (2023) 13603–13616. security requirements mentioned in Section 4 but also achieves higher [5] Y. Zhang, B. Wang, Z. Zhao, Verifiable and privacy-preserving π‘˜-NN query efficiency than scheme MSVπ‘˜NN in all stages of POI queries, with an scheme with multiple keys, IEEE Trans. Big Data 11 (3) (2024) 1434–1446. improvement of up to 45.5%. [6] Q. Liu, Y. Peng, J. Wu, T. Wang, G. Wang, Secure multi-keyword fuzzy searches with enhanced service quality in cloud computing, IEEE Trans. Netw. Serv. Manag. 18 (2) (2021) 2046–2062. 9. Conclusion [7] Q. Liu, Y. Peng, Q. Xu, H. Jiang, J. Wu, T. Wang, T. Peng, G. Wang, S. Zhang, 𝖬𝖠𝖱𝖲Mars: Enabling verifiable range-aggregate queries in multi-source This paper proposes efficient and secure multi-user π‘˜NN queries environments, IEEE Trans. Dependable Secur. Comput. 21 (4) (2024) 1994–2011. [8] N. Cui, X. Yang, B. Wang, J. Li, G. Wang, SVkNN: Efficient secure and verifiable with dynamic POIs updating, which preserves the privacy of data, k-nearest neighbor query on the cloud platform, in: Proc. of ICDE, 2020, pp. queries, results, access patterns and ensures the results are correct 253–264. and complete in a multi-user environment. Firstly, DESMπ‘˜NN proposes [9] N. Cui, K. Qian, T. Cai, J. Li, X. Yang, J. Cui, H. Zhong, Towards multi-user, a two-stage search framework to accelerate query speed. Secondly, secure, and verifiable π‘˜ NN query in cloud database, IEEE Trans. Knowl. Data DESMπ‘˜NN designs a series of novel secure protocols and a compact ver- Eng. 35 (9) (2023) 9333–9349. [10] H. Xie, Y. Guo, X. Jia, A privacy-preserving online ride-hailing system without ification strategy to facilitate the operation over the two-stage search involving a third trusted server, IEEE Trans. Inf. Forensics Secur. 16 (2021) framework. Finally, computational complexity, security analysis and 3068–3081. experimental evaluation demonstrate that DESMπ‘˜NN improves query [11] W. Wong, D. Cheung, B. Kao, N. Mamoulis, Secure kNN computation on efficiency by up tp 45.5% compared to MSVπ‘˜NN. In future research, encrypted databases, in: Proc. of SIGMOD, 2009, pp. 139–152. [12] Y. Zhu, R. Xu, T. Takagi, Secure k-NN computation on encrypted cloud data we plan to study π‘˜NN queries for multi-type POIs to address the without sharing key with query users, in: Proc. of IWSEC, 2013, pp. 55–60. limitation of single-type POI scenarios, where query results are too [13] B. Yao, F. Li, X. Xiao, Secure nearest neighbor revisited, in: Proc. of ICDE, 2013, homogeneous. Moreover, we will focus more on exploring the balance pp. 733–744. between security and efficiency. [14] Q. Liu, Z. Hao, Y. Peng, H. Jiang, J. Wu, T. Peng, G. Wang, S. Zhang, SecVKQ: Secure and verifiable kNN queries in sensor–cloud systems, J. Syst. Archit. 120 (2021) 102300. CRediT authorship contribution statement [15] Y. Elmehdwi, B.K. Samanthula, W. Jiang, Secure k-nearest neighbor query over encrypted data in outsourced environments, in: Proc. of ICDE, 2014, pp. Yining Jia: Writing – original draft, Software, Methodology, In- 664–675. vestigation, Conceptualization. Yali Liu: Writing – review & editing, [16] S. Choi, G. Ghinita, H.-S. Lim, E. Bertino, Secure kNN query processing in untrusted cloud environments, IEEE Trans. Knowl. Data Eng. 26 (11) (2014) Resources. Congai Zeng: Writing – review & editing. Xujie Ding: 2818–2831. Writing – review & editing. Jianting Ning: Writing – review & editing. [17] K. Cheng, L. Wang, Y. Shen, H. Wang, Y. Wang, X. Jiang, H. Zhong, Secure π‘˜ k-NN query on encrypted cloud data with multiple keys, IEEE Trans. Big Data Declaration of competing interest 7 (4) (2021) 689–702. [18] A. Boldyreva, N. Chenette, Y. Lee, A. O’neill, Order-preserving symmetric encryption, in: Proc. of EUROCRYPT, 2009, pp. 224–241. The authors declare that they have no known competing finan- [19] X. Liu, R.H. Deng, K.-K.R. Choo, J. Weng, An efficient privacy-preserving cial interests or personal relationships that could have appeared to outsourced calculation toolkit with multiple keys, IEEE Trans. Inf. Forensics influence the work reported in this paper. Secur. 11 (11) (2016) 2401–2414. [20] K. Cheng, Y. Shen, Y. Wang, L. Wang, J. Ma, X. Jiang, C. Su, Strongly secure and efficient range queries in cloud databases under multiple keys, in: Proc. of Acknowledgments INFOCOM, 2019, pp. 2494–2502. [21] S.K. Nayak, S. Tripathy, SEMKC: Secure and efficient computation over out- The authors thank the editor and the reviewers for their comments sourced data encrypted under multiple keys, IEEE Trans. Emerg. Top. Comput. and suggestions. This work was supported by the National Natural Sci- 9 (1) (2018) 414–428. ence Foundation of China under Grant No. 61702237, No. 62425205, [22] A. Okabe, B. Boots, K. Sugihara, S. Chiu, Spatial tessellations: Concepts and applications of voronoi diagrams, College Math. J. (2001). and No. 12441101, the Opening Foundation of State Key Laboratory [23] Y. Manolopoulos, A. Nanopoulos, A.N. Papadopoulos, Y. Theodoridis, R-Trees: for Novel Software Technology, Nanjing University under Grant No. Theory and Applications: Theory and Applications, Springer Science & Business KFKT2025B54, the Science and Technology Planning Foundation of Media, 2006. Xuzhou City under Grant No. KC22052, the Opening Foundation of [24] N. Cui, D. Wang, H. Zhu, J. Li, J. Xu, X. Yang, Enabling verifiable and secure range query in multi-user setting under cloud environments, IEEE Trans. Knowl. Guangxi Key Laboratory of Cryptography and Information Security, Data Eng. 36 (12) (2024) 8148–8163. Guilin University of Electronic Technology under Grant GCIS202114, [25] Q. Liu, S. Wu, S. Pei, J. Wu, T. Peng, G. Wang, Secure and efficient multi- the Postgraduate Research & Practice Innovation Program of Jiangsu attribute range queries based on comparable inner product encoding, in: Proc. Normal University under Grant 2024XKT2579, and the University- of CNS, 2018, pp. 1–9. Industry Collaborative Education Program of China under Grant No. [26] Y. Zhang, B. Wang, Z. Zhao, Secure k-NN query with multiple keys based on random projection forests, IEEE Internet Things J. 11 (9) (2023) 15205–15218. 202101374001. All authors have read and approved the final version [27] S. Wu, Q. Li, G. Li, D. Yuan, X. Yuan, C. Wang, ServeDB: Secure, verifiable, of the manuscript. and efficient range queries on outsourced database, in: Proc. of ICDE, 2019, pp. 626–637. Data availability [28] H.-I. Kim, H.-J. Kim, J.-W. Chang, A secure kNN query processing algorithm using homomorphic encryption on outsourced database, Data Knowl. Eng. 123 (2019) 101602. Data will be made available on request. [29] A. Liu, K. Zhengy, L. Liz, G. Liu, L. Zhao, X. Zhou, Efficient secure similarity computation on encrypted trajectory data, in: Proc. of ICDE, 2015, pp. 66–77. 12 Y. Jia et al. Computer Standards & Interfaces 97 (2026) 104112 [30] P. Williams, R. Sion, B. Carbunar, Building castles out of mud: practical access Congai Zeng received her M.Sc. in Electronic Information in pattern privacy and correctness on untrusted storage, in: Proc. of CCS, 2008, pp. 2024 from Jiangsu Normal University, China. Currently, she 139–148. is pursuing the Ph.D. degree in the Faculty of Information [31] M.S. Islam, M. Kuzu, M. Kantarcioglu, Access pattern disclosure on searchable Technology at Beijing University of Technology, China. Her encryption: ramification, attack and mitigation, in: Proc. of NDSS, vol. 20, 2012, research interests include Internet of Vehicles security and p. 12. privacy. [32] A. Bowyer, Computing dirichlet tessellations, Comput. J. 24 (2) (1981) 162–166. [33] D.F. Watson, Computing the n-dimensional delaunay tessellation with application to voronoi polytopes, Comput. J. 24 (2) (1981) 167–172. [34] J. Liu, J. Yang, L. Xiong, J. Pei, Secure skyline queries on cloud platform, in: Proc. of ICDE, 2017, pp. 633–644. [35] A.C.-C. Yao, How to generate and exchange secrets, in: Proc. of Sfcs, 1986, pp. 162–167. Xujie Ding received his B.Sc. in Software Engineering in 2023 from Jiangsu Normal University, China. Currently, he is pursuing the M.Sc. degree in the School of Artificial Intel- ligence and Computer Science at Jiangsu Normal University, Yining Jia received his B.Sc. in Computer Science and Tech- China. His research interests include privacy preservation nology in 2023 from Nanjing Forestry University, China. and secure data sharing technology in smart healthcare. Currently, he is pursuing the M.Sc. degree in the School of Artificial Intelligence and Computer Science at Jiangsu Normal University, China. His research interests include data privacy, query processing, information security. Jianting Ning received his Ph.D. in 2016 from Shanghai Jiao Tong University, China. He has been a Research Sci- entist at the School of Computing and Information Systems, Singapore Management University, and a Research Fellow at Yali Liu received her Ph.D. in 2014 from Nanjing Uni- the National University of Singapore. His research interests versity of Aeronautics and Astronautics, China. She is a include applied cryptography and information security. He senior member of China Computer Federation (CCF). She is currently a Professor with the School of Cyber Science has been a Research Scientist at Nanyang Technological and Engineering, Wuhan University, China, and with Fac- University, Singapore. She is currently a Professor in the ulty of Data Science, City University of Macau, China. He School of Artificial Intelligence and Computer Science at has published papers in major conferences/journals, such Jiangsu Normal University, China. Her research interests as ACM CCS, NDSS, ASIACRYPT, ESORICS, ACSAC, IEEE include information security, authentication and privacy- Transactions on Information Forensics and Security, and preserving technology, blockchain security and privacy, IEEE Transactions on Dependable and Secure Computing. vehicular ad hoc networks, cryptographic algorithms and protocols and their applications in Internet of things and mobile communication. 13