                                                                 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
