arXiv CS open access

Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search Haoyu Wang

Yandi Zhang

arXiv:2608.16488v1 [cs.DB] 17 Aug 2026

Xidian University Xi’an, China hyw2004@stu.xidian.edu.cn

Yingfan Liu∗

Jiadong Xie

Xidian University The Chinese University of Xi’an, China Hong Kong ydzhang_2@stu.xidian.edu.cn Hong Kong SAR, China jdxie@se.cuhk.edu.hk

Xidian University Xi’an, China liuyingfan@xidian.edu.cn

Hui Li

Jeffrey Xu Yu

Jiangtao Cui

Xidian University Xi’an, China hli@xidian.edu.cn

The Hong Kong University of Science and Technology (Guangzhou) Guangzhou, China jeffreyxuyu@hkustgz.edu.cn

Xi’an University of Posts and Telecommunications Xi’an, China Xidian University Xi’an, China cuijt@xupt.edu.cn

ABSTRACT Range-filtered approximate nearest neighbor search (RFANNS) is an important primitive for vector databases; it retrieves vectors that are similar to a query and satisfy a numerical range predicate, but existing RFANNS indexes expose vectors, attributes, and queries in plaintext. This assumption is unsuitable for outsourced vector databases, where sensitive data and queries must be protected from an honest-but-curious cloud server. To the best of our knowledge, this is the first study that systematically formulates and evaluates privacy-preserving RFANNS over outsourced encrypted vector databases. Our approach separates range localization from encrypted vector search: an authorized user maps the query range to a compact set of nodes in a local N-ary attribute tree, and the server searches only the corresponding proximity graph sub-indices over encrypted vectors. To reduce expensive encrypted comparisons, we use a filter-and-refine pipeline that first retrieves coarse candidates with approximate distance-comparison-preserving encryption and then reranks a small candidate set with exact distance-comparison encryption. We then analyze the computation, storage, communication, and leakage of the protocol. Experiments on four widely used vector datasets show that our method improves the QPS–Recall trade-off over representative secure adaptations of existing RFANNS approaches, scaling effectively to large datasets. PVLDB Reference Format: Haoyu Wang, Yandi Zhang, Jiadong Xie, Yingfan Liu, Hui Li, Jeffrey Xu Yu, and Jiangtao Cui. Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search. PVLDB, 20(1): XXX-XXX, 2027. doi:XX.XX/XXX.XX PVLDB Artifact Availability: ∗ Yingfan Liu is the corresponding author.

This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 20, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

The source code, data, and/or other artifacts have been made available at https://github.com/meimeimeiarc/PP-RFANNS.

INTRODUCTION

With the increasing adoption of vector representations, objects such as images [11, 27] and texts [7, 31] are encoded as high-dimensional vectors that capture their semantic information. Vector similarity search is commonly supported by 𝑘-approximate nearest neighbor search (𝑘-ANNS), which has become a fundamental component of vector databases and retrieval-augmented generation [1, 15]. In many applications, pure 𝑘-ANNS is insufficient because the returned objects must also satisfy structured constraints. For example, an e-commerce user may search for products visually similar to a query image within a specified price range, while a multimedia application may retrieve similar objects appearing within a temporal interval. These scenarios motivate range-filtered approximate nearest neighbor search (RFANNS), where each object consists of a vector and a numerical attribute, and each query contains a query vector and a range predicate over the attribute domain. Recent plaintext RFANNS methods [6, 12, 33, 37] combine vector indices such as HNSW [22] with range-aware structures such as segment trees and B-trees, achieving efficient range-constrained vector search. However, they assume that vectors, attributes, and queries are available in plaintext. This assumption is unsuitable for outsourced data management, where data owners rely on cloud servers for storage and query processing but wish to protect database vectors, numerical attributes, query vectors, and query ranges. This motivates privacy-preserving range-filtered approximate nearest neighbor search (PP-RFANNS). In this setting, a data owner outsources an encrypted vector database to an honest-but-curious cloud server, and authorized users issue encrypted RFANNS queries. The server should return high-quality approximate neighbors satisfying the range predicate, without learning the protected database and query contents beyond explicitly characterized leakage. Supporting PP-RFANNS is challenging because it requires simultaneously satisfying three conflicting goals: security, accuracy,

Cloud Server (CS)

and efficiency, because encryption usually destroys the direct usability of conventional vector indices and attribute filters. In particular, exact secure distance comparison [20, 43] is often much more expensive than plaintext distance computation, while secure range checking over encrypted attributes can introduce significant cryptographic overhead or require additional interaction [41]. Furthermore, existing approaches do not directly resolve this tension. Plaintext RFANNS methods violate the privacy requirement, while privacy-preserving ANNS methods [4, 20, 26, 28, 38, 44] support only pure vector search and do not efficiently handle range predicates. Straightforward secure adaptations also suffer from selectivity-sensitive bottlenecks: secure pre-filtering performs expensive encrypted vector search over all qualified objects, secure post-filtering requires substantial over-fetching under low selectivity, and encrypted adaptations of dedicated RFANNS indices such as iRangeGraph [37] repeatedly invoke costly secure range checks as new neighbors are inspected during online graph traversal. To address these limitations, we propose a practical PP-RFANNS scheme that decouples range localization from encrypted vector search. Our scheme employs an N-ary tree–HNSW hybrid index. The N-ary tree, maintained by the query user, hierarchically organizes the attribute domain, while the cloud server stores an HNSW sub-index for each tree node over the encrypted vectors in its interval. Given a query, the query user locally maps the range predicate to a compact set of matched tree nodes, after which the cloud server searches only the corresponding encrypted HNSW sub-indices. We further design a filter-and-refine query strategy. During filtering, the server uses DCPE ciphertexts [9], which approximately preserve distance ordering, to efficiently retrieve coarse candidates from the matched sub-indices. It then merges these candidates and applies DCE-based exact distance comparison [20] only to a reduced candidate set. This design avoids online encrypted range checking and limits expensive exact comparisons while preserving high search accuracy. Moreover, we analyze the computation, communication, storage, and security properties of the proposed scheme under the honest-but-curious model, and explicitly characterize the leakage arising from the encrypted vector representations, index structures, and query execution. Experiments on widely used vector datasets show that our method achieves consistently better efficiency–accuracy trade-offs than representative secure adaptations of existing RFANNS approaches across different query selectivities, while scaling effectively to larger datasets. At 𝑅𝑒𝑐𝑎𝑙𝑙@10 = 0.95, PP-RFANNS improves query throughput by at least two orders of magnitude over the secure baselines. Our main contributions are summarized as follows. ➊ We formulate the PP-RFANNS problem over outsourced encrypted data and identify the security, accuracy, and efficiency challenges arising from the joint processing of vector similarity and range predicates. ➋ We propose an N-ary tree–HNSW hybrid index that separates local range localization from server-side encrypted vector search, allowing the server to search only the sub-indices relevant to the query range. ➌ We design a filter-and-refine query strategy that combines efficient DCPE-based candidate retrieval with DCE-based exact refinement, balancing query efficiency and search accuracy. ➍ We provide cost and security analyses and conduct extensive experiments demonstrating that the proposed scheme consistently

4 2

Data Owner (DO)

1 Authorized

Database

Secret Keys

Query User (QU)

Query (𝒗𝒒 , [𝒍𝒒 , 𝒓𝒒 ], 𝒌)

Figure 1: The system model of PP-RFANNS.

outperforms representative secure adaptations under different settings.

PRELIMINARIES

In this section, we present the system model and threat model, followed by our problem definition and design goals.

2.1

System Model

As shown in Figure 1, the system consists of three participants: a data owner (DO), a query user (QU), and a cloud server (CS). Data Owner (DO): The DO holds a database of objects, denoted as 𝑂 = {𝑜𝑖 }𝑛𝑖=1 , where each 𝑜𝑖 = (𝑣𝑖 , 𝑎𝑖 ) consists of a 𝑑-dimensional vector 𝑣𝑖 ∈ R𝑑 and a numerical attribute 𝑎𝑖 ∈ A ⊂ Z 1 . The DO encrypts the objects into ciphertexts and outsources them to the CS. To support efficient PP-RFANNS queries, the DO builds a privacypreserving index and distributes it to the CS. Besides, the DO sends the secret keys for trapdoor generation to the authorized QUs. Query User (QU): An RFANNS query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘) includes three parts, i.e., (1) the query vector 𝑣𝑞 ∈ R𝑑 , the query range [𝑙𝑞 , 𝑟𝑞 ] ⊂ A and the number 𝑘 of returned neighbors. To protect the query 𝑞, the QU encrypts 𝑞 into the query trapdoor 𝑇𝑞 according to the secret keys, and then sends 𝑇𝑞 to the CS. Cloud Server (CS): The CS stores the encrypted objects and the auxiliary index from the DO to answer efficient PP-RFANNS queries. Once the query trapdoor 𝑇𝑞 is received from the QU, it conducts the search process over the encrypted objects and the index and returns the results to the QU.

2.2

Threat Model

We consider an outsourced PP-RFANNS setting involving a DO, authorized QUs, and one or more CSs that store encrypted data and participate in query processing. The DO and authorized QUs are assumed to be honest and follow the prescribed procedures. In particular, they do not disclose secret keys, plaintext objects, or plaintext queries to the CSs or any unauthorized party. The CSs are assumed to be honest-but-curious. They faithfully store the outsourced encrypted objects, maintain the required server-side indices, and execute the prescribed query-processing protocols, but 1 This setting can be naturally extended to 𝑎 ∈ R through IEEE 754 sortable integer 𝑖 encoding, where A represents the attribute domain. Specifically, floating-point values can be transformed into order-preserving integer keys, such that their numerical order is preserved after encoding. As a result, range queries over real-valued attributes can be equivalently processed in the encoded integer domain.

• Accuracy. The scheme should return high-quality 𝑘-ANN of the query vector 𝑣𝑞 from the qualified vector set 𝑉[𝑙𝑞 ,𝑟𝑞 ] . • Efficiency. The scheme should support efficient PP-RFANNS query processing at the CS, while incurring low computation overhead at the QU and low communication overhead between the QU and the CS.

may attempt to infer sensitive information from their respective views. Such views may include encrypted objects, query trapdoors, server-side index structures, intermediate protocol messages, and query-execution traces. If a PP-RFANNS scheme employs multiple CSs, its assumptions regarding possible collusion among them must be explicitly specified by that scheme. Encrypted indexing and query processing may inevitably expose scheme-dependent structural, access-pattern, and cryptographic information, such as index topology, accessed objects, range-checking outcomes, and distance-comparison information. The precise leakage depends on the adopted scheme. We characterize the leakage of our proposed scheme in Section 5.

2.3

In this section, we first review plaintext RFANNS methods, privacypreserving range query and privacy-preserving 𝑘-ANNS (PP-ANNS) methods, and then discuss the secure adaptations of existing RFANNS methods to answer PP-RFANNS.

Problem Definition

3.1

Given an object set 𝑂, let 𝑉 = {𝑣𝑖 |𝑜𝑖 ∈ 𝑂 } be the vector set and 𝐴 = {𝑎𝑖 |𝑜𝑖 ∈ 𝑂 } be the set of attribute values. For a query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘), let 𝑂 [𝑙𝑞 ,𝑟𝑞 ] = {𝑜𝑖 |𝑎𝑖 ∈ [𝑙𝑞 , 𝑟𝑞 ]} be the set of qualified objects and 𝑉[𝑙𝑞 ,𝑟𝑞 ] = {𝑣𝑖 |𝑜𝑖 ∈ 𝑂 [𝑙𝑞 ,𝑟𝑞 ] } be the qualified vector set.

Plaintext RFANNS Methods

Existing RFANNS methods can be divided into general-purpose approaches and dedicated methods. General-purpose approaches include pre-filtering [30, 34, 40], post-filtering [30, 34], and ACORN [25]. Pre-filtering performs brute-force search over the objects satisfying the range predicate, whereas post-filtering first conducts global 𝑘-ANNS and then removes unqualified results. ACORN modifies HNSW [22] by enlarging node degrees and restricting traversal to qualified nodes. Dedicated RFANNS methods [6, 12, 19, 33, 37, 45] combine range-aware structures, such as segment trees [6, 37] or B-trees [12], with PG indexes. By restricting graph search to rangerelevant partitions or edges, they achieve substantially better query performance than general-purpose approaches. Among the dedicated methods, iRangeGraph [37] builds a segmenttree-based multi-layer index, where each tree node maintains a PG index, called an elemental graph, over the objects in its attribute interval. During query processing, it dynamically selects in-range edges from the relevant elemental graphs to build a range-dedicated graph during traversal. This online edge-selection procedure requires range checks over candidates. Issue: These methods solve RFANNS by exploiting plaintext data, which should be protected in our privacy-preserving scenarios, and violate the goal of security. Hence, they cannot solve PP-RFANNS.

Definition 2.1 (𝑘-ANNS). Given a vector set 𝑉 ⊂ R𝑑 , a query vector 𝑣𝑞 ∈ R𝑑 and an integer 𝑘, 𝑘-ANNS returns 𝑘 sufficiently close neighbors in 𝑉 to 𝑣𝑞 . As the underlying search primitive of RFANNS and PP-RFANNS, the k-ANNS problem has been studied for a few decades. According to recent studies [2, 17, 32], proximity graphs (PG) such as HNSW [22], NSG [8] and ALMG [36] have been the SOTA 𝑘-ANNS methods. A PG treats each vector in 𝑉 as a graph vertex and builds edges between each node and its closest neighbors in 𝑉 . Different PGs share the same vertex set but have different edge sets due to various edge selection strategies. Notably, PG is the building block of the mainstream RFANNS methods and our PP-RFANNS scheme in this work. Definition 2.2 (RFANNS). Given an object set 𝑂 and a query 𝑞, RFANNS returns the 𝑘-ANN of 𝑣𝑞 over the vector set 𝑉[𝑙𝑞 ,𝑟𝑞 ] . Definition 2.3 (PP-RFANNS). Given an encrypted representation 𝐶𝑂 of 𝑂 and a query trapdoor 𝑇𝑞 generated for a query 𝑞, PPRFANNS returns the identifiers of 𝑘-ANN of 𝑣𝑞 from the set 𝑉[𝑙𝑞 ,𝑟𝑞 ] by operating over encrypted data and encrypted queries.

3.2

Privacy-Preserving Range Query

Privacy-preserving range queries retrieve encrypted records whose numerical attributes fall within a query interval [𝑙𝑞 , 𝑟𝑞 ], while protecting the attribute values and query bounds from the cloud server. Existing solutions mainly rely on Order-Preserving/OrderRevealing Encryption (OPE/ORE), Searchable Symmetric Encryption (SSE), or Symmetric Homomorphic Encryption (SHE). OPE/ORE-based methods [3, 13, 14] and SSE-based methods [5, 24, 29] support efficient range retrieval through encrypted indices, but reveal information such as ciphertext order, search patterns, access patterns, or result sizes. SHE-based methods [21, 41, 42] evaluate range predicates directly over encrypted attributes and avoid explicitly revealing their global order. A basic construction evaluates the encrypted range predicate independently for each examined record. Existing schemes reduce this cost through auxiliary index structures, which limit the number of examined records, and optimized SHE constructions, such as iSHE [41], which improve the efficiency of each encrypted predicate evaluation. Nevertheless, repeated range checks can still incur substantial cryptographic

The security of a PP-RFANNS scheme depends on both the guarantees of its underlying cryptographic primitives and the information exposed by its encrypted index and query execution. In this work, we do not claim a new simulation-based security result for the complete composition. Instead, we rely on the established security properties of the adopted primitives and explicitly characterize the additional leakage of the complete protocol in Section 5.

2.4

LIMITATIONS OF EXISTING WORKS

Design Goals

Our goal is to design a practical PP-RFANNS scheme satisfying the following requirements. • Security. The scheme should protect the plaintext database vectors and numerical attributes, as well as the query vectors, numerical query bounds, and exact distance values, against an honest-but-curious CS, except for the information explicitly revealed by the underlying encryption primitives, the server-side index, and query execution. 3

(a) Secure Pre-filtering QU

Query q Trapdoor Generation

(b) Secure Post-filtering QU

Indexed Secure Range Query with iSHE

Query q

Qualified Vectors

Trapdoor Generation

CS DCPE-based HNSW Global PP-ANNS 𝒌’ -ANN

Brute-Force Vector Search with DCE

which fits Secure Post-filtering and PP-iRangeGraph. OPE/OREbased alternatives reveal the global order of encrypted attributes, while range-SSE introduces a different encrypted-index leakage profile. Using the same iSHE-based protocol provides a consistent basis for comparing the three query-processing strategies. Secure Pre-filtering. Given a query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘), the QU generates the query trapdoor and sends it to the CS. The CS searches a B-tree over encrypted attributes and selectively invokes iSHE, to identify the qualified vectors. It then performs brute-force DCEbased distance comparisons over all qualified vectors and returns pre the top-𝑘 results. Let 𝑚𝑞 be the number of iSHE checks and 𝑠𝑞 pre the query selectivity. The query cost includes 𝑚𝑞 𝐶 rc for range checking and 𝑂 (𝑠𝑞 𝑛 log 𝑘) DCE comparisons. Although the B-tree reduces range checks, the exhaustive encrypted vector search becomes expensive at high selectivity. Secure Post-filtering. Secure Post-filtering first performs global PP-ANNS [20] over the entire encrypted vector database. Specifically, the CS searches a DCPE-based HNSW index and retrieves the global top-𝑘 ′ candidates, where 𝑘 ′ ≥ 𝑘. It then performs iSHE-based range checks over these candidates, and applies DCE refinement to the qualified candidates to obtain the final top-𝑘 results. The main difficulty is selecting 𝑘 ′ . Under low selectivity, a small 𝑘 ′ may return fewer than 𝑘 qualified results and require repeated searches, whereas a large 𝑘 ′ incurs unnecessary encrypted vector search and iSHE-based range-checking overhead. Consequently, Secure Post-filtering performs poorly for low-selectivity queries. PP-iRangeGraph. PP-iRangeGraph adapts iRangeGraph by encrypting both the vectors and numerical attributes. The CS iteratively searches the DCPE-based elemental graphs. In each iteration, it selects a node 𝑢 for expansion and collects its candidate neighbors from the relevant elemental graphs. For every inspected neighbor, the CS invokes iSHE to determine whether its encrypted attribute satisfies the query predicate. Qualified neighbors are then used to update the DCPE-based coarse candidate set. After the graph search terminates, the CS applies DCE refinement to the DCPEbased coarse candidates and returns the top-𝑘 results. If 𝑚𝑞 neighbors are inspected, PP-iRangeGraph performs 𝑚𝑞 iSHE-based range checks during graph traversal, followed by DCE refinement on the final candidate set. Repeated iSHE invocation during graph traversal incurs substantial cryptographic computation, inter-server communication, and interaction overhead. Issue: In the secure adaptations, all three baselines use iSHE-based range checking. Under our threat model, the resulting ciphertexts are decrypted by a non-colluding auxiliary server, which introduces substantial cryptographic computation, communication, and interaction overhead. Beyond this common cost, the three methods exhibit different selectivity-sensitive bottlenecks. Secure Pre-filtering reduces the number of range checks through an encrypted range index, but still performs exhaustive DCE-based distance comparison over all qualified objects and therefore becomes expensive at high selectivity. Secure Post-filtering applies range checks to candidates returned by global PP-ANNS and may require substantial overfetching or repeated searches at low selectivity. PP-iRangeGraph repeatedly invokes range checking as new neighbors are inspected during online graph traversal, causing persistent cryptographic and interaction overhead. Consequently, none of these adaptations

CS DCPE-based iRangeGraph

Query q Trapdoor Generation 𝑻𝒒𝟑

𝑻𝒒𝟐

𝑻𝒒𝟏

iSHE Range Checks

Foreach Expanded Node u Neighbor Collection iSHE Range Checks DCPE Computations DCE Refinement

Top-k IDs

Figure 2: The illustrations of secure adaptations

computation and, when decryption is delegated to a non-colluding auxiliary server, inter-server communication and interaction overhead. Issue: These methods focus on secure range query over encrypted attributes, but do not support high-dimensional encrypted vector search. Hence, they cannot directly solve PP-RFANNS.

3.3

Privacy-Preserving ANNS Methods

Existing privacy-preserving ANNS (PP-ANNS) methods protect outsourced vectors and auxiliary ANN indices, while using encrypted indices to reduce the search space. According to whether vector distances can be evaluated directly over ciphertexts, they can be broadly classified into distance-incomparable and distancecomparable approaches. Distance-incomparable approaches, including AES- and PIRbased schemes [26, 28, 44], cannot support distance-guided search at the CS. Although an auxiliary index may identify a candidate subset, the QU must retrieve and decrypt candidates or interactively access encrypted index entries, resulting in substantial communication and QU-side computation. Distance-comparable methods employ primitives such as ASPE [16, 23, 35, 39], DCPE [9], AME [43], HE [10, 38], or DCE [20] to enable distance-guided search over encrypted vectors. However, indices built from plaintext vectors may reveal proximity relationships, while secure distance evaluation at every search step can be expensive. Moreover, ASPE-based schemes have known security weaknesses [16, 18, 20], DCPE preserves only approximate distance order, and AME- and HE-based methods incur relatively high computational overhead. Liu et al. [20] address these issues by constructing HNSW directly over DCPE-encrypted vectors. The CS first uses DCPE for efficient coarse retrieval and then applies DCE only to the reduced candidate set for exact reranking. This design supports efficient encrypted graph search while limiting the number of expensive exact distance comparisons. Issue: They focus on pure ANNS without handling attribute values, and thus cannot directly support efficient PP-RFANNS.

3.4

Secure Adaptations of RFANNS

We consider simple adaptations of three representative RFANNS methods in the encrypted setting, denoted as secure pre-filtering, secure post-filtering, and PP-iRangeGraph, as illustrated in Figure 2. We instantiate all three secure adaptations with iSHE-based range checking. iSHE naturally supports candidate-wise range checks, 4

Object Set

��

�DCPE �

Attribute �1 �2

...

�2

Vector

...

ID �1

2 N-ary Tree Construction

Vector Encryption

��

�1

Attribute Set � �2

�3

...

HNSW sub-indices construction HNSW Set �

QU 1

�n

�DCE �

Key Generation ��DCPE ��DCE

Range Localization

... ...

��1

Figure 3: The workflow of secure index construction

Query Initialization � = (�� , [�� , �� ], �)

��2

��3

Trapdoor Generation ��DCE ��DCPE

Results

Top-k IDs

Query Request

��

Selected Node Query Range

(�� , �DCPE , � �DCE � , �)

Return Results

Matched Sub-index Search ��1

��2

��3

Top-�0

Merge and Refine

Merge and Sort by DCPE distances

�DCE �

Refine by Secure Distance Comparisons with DCE

Top-k IDs

Figure 4: The workflow of secure query processing provides consistently efficient PP-RFANNS query processing across different selectivities.

For DCPE, we adopt the Scale-and-Perturb (SAP) construction in [9]. Given the secret key 𝑆𝐾DCPE = (𝑠, 𝛽), the DO generates the ciphertext as 𝐶 𝑣DCPE = 𝑠 · 𝑣 + 𝜆𝑣 , where 𝑠 ∈ R+ is a random scaling factor and 𝜆𝑣 is a random vector sampled from the 𝑑-dimensional ball centered at the origin with radius 𝑠𝛽/4. The resulting ciphertext 𝐶 𝑣DCPE ∈ R𝑑 approximately preserves the distances among vectors. Encrypting one vector requires 𝑂 (𝑑) time and 𝑂 (𝑑) space. For DCE, the DO first generates the secret key 𝑆𝐾DCE = {𝑀1, 𝑀2, 𝑀3, 𝜋1, 𝜋2, 𝑟 1, 𝑟 2, 𝑟 3, 𝑟 4, 𝑘𝑣 1, 𝑘𝑣 2, 𝑘𝑣 3, 𝑘𝑣 4 }. Here, 𝑀1 , 𝑀2 , and 𝑀3 are random invertible matrices, 𝜋 1 and 𝜋2 are random permutation functions, 𝑟 1, . . . , 𝑟 4 are random scalars, and 𝑘𝑣 1, . . . , 𝑘𝑣 4 are random masking vectors. The DO then computes the DCE ciphertext as 𝐶 𝑣DCE ← DCE.Enc(𝑣, 𝑆𝐾DCE ). The encryption consists of two main steps. First, vector randomization permutes, splits, and pads 𝑣 with random values, producing an intermediate vector 𝑣¯ ∈ R𝑑+8 . Second, vector transformation applies random matrix transformations and element-wise masking to 𝑣¯, producing the ciphertext 𝐶 𝑣DCE = (𝑣¯1′ , 𝑣¯2′ , 𝑣¯3′ , 𝑣¯4′ ), where each component satisfies 𝑣¯′𝑗 ∈ R2𝑑+16 . Therefore, each DCE ciphertext contains 8𝑑 +64 scalar values. Since the encryption involves matrix–vector multiplications over matrices whose dimensions are linear in 𝑑, its computational complexity is 𝑂 (𝑑 2 ), while its space complexity is 𝑂 (𝑑). After encrypting all vectors, the DO obtains 𝐶𝑉DCPE = {𝐶 𝑣DCPE | 𝑣 ∈ 𝑉 } and 𝐶𝑉DCE = {𝐶 𝑣DCE | 𝑣 ∈ 𝑉 }. N-ary Tree Construction. Given the numerical attribute set 𝐴 = {𝑎 1, 𝑎 2, . . . , 𝑎𝑛 }, the DO constructs a range-aware N-ary tree T to hierarchically organize 𝐴. The DO first sorts the objects according to their attribute values and determines the minimum and maximum values, denoted by 𝑎 min and 𝑎 max , respectively. The root node of T represents the entire attribute domain [𝑎 min, 𝑎 max ] and contains all objects in 𝑂. The tree is then constructed recursively in a topdown manner. For each non-leaf node 𝑡𝑛 associated with an interval [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ] ⊂ 𝐴 and an object subset 𝑂𝑡𝑛 = {𝑜𝑖 |𝑜𝑖 ∈ 𝑂, 𝑎𝑖 ∈ [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ]}, the DO partitions [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ] into at most 𝑏 non-overlapping and 1 , 𝑟 1 ], . . . , [𝑙 𝑚 , 𝑟 𝑚 ], where 𝑚 ≤ 𝑏. The consecutive sub-intervals, [𝑙𝑡𝑛 𝑡𝑛 𝑡𝑛 𝑡𝑛 𝑗 corresponding object subset is divided as 𝑂𝑡𝑛 = {𝑜𝑖 ∈ 𝑂𝑡𝑛 | 𝑎𝑖 ∈ 𝑗 𝑗 [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ]}, and a child node is created for each nonempty subset 𝑗 𝑂𝑡𝑛 . The intervals of all child nodes jointly cover the interval of 𝑖 , 𝑟 𝑖 ] ∩ [𝑙 𝑗 , 𝑟 𝑗 ] = ∅ for any 𝑖 ≠ 𝑗. their parent node and satisfy [𝑙𝑡𝑛 𝑡𝑛 𝑡𝑛 𝑡𝑛 To obtain a balanced tree, the partition boundaries are selected according to the sorted attribute values such that the child nodes

OUR PP-RFANNS SCHEME

In this section, we present our PP-RFANNS scheme. The key idea is to decouple range localization from encrypted vector search, such that the CS searches only the secure vector sub-indices corresponding to the query range. We first give an overview of the scheme, and then describe secure index construction, secure query processing, and cost analysis.

4.1

Overview

Our proposed PP-RFANNS scheme consists of two main procedures: secure index construction and secure query processing, as shown in Figure 3 and Figure 4, respectively. Given an object set 𝑂 = (𝑉 , 𝐴), the DO constructs the secure index in three phases. First, it encrypts the vector set 𝑉 using DCPE and DCE, producing 𝐶𝑉DCPE and 𝐶𝑉DCE , respectively. Second, it constructs a range-aware N-ary tree T over the attribute set 𝐴. Third, it builds an HNSW subindex 𝐺𝑡𝑛 for each tree node 𝑡𝑛 ∈ T . After index construction, the DO distributes the DCPE and DCE secret keys, denoted by 𝑆𝐾DCPE and 𝑆𝐾DCE , together with T , to the QU. Meanwhile, 𝐶𝑉DCPE , 𝐶𝑉DCE , and the HNSW sub-indices are outsourced to the CS. During secure query processing, the QU and the CS perform distinct tasks: the QU locally interprets the range predicate and generates encrypted query trapdoors, whereas the CS executes the vector search over the encrypted sub-indices selected by the QU. Specifically, for a query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘), the QU generates the query trapdoor 𝑇𝑞 = (𝑇𝑞DCPE,𝑇𝑞DCE ) using 𝑆𝐾DCPE and 𝑆𝐾DCE , respectively. It then evaluates the range predicate over T to identify the set 𝐼𝑞 of matching tree nodes and sends (𝑇𝑞 , 𝐼𝑞 ) to the CS. Upon receiving them, the CS employs a filter-and-refine strategy to answer the query.

4.2

Secure Index Construction

As in Figure 3, the secure index construction consists of three phases, i.e., vector encryption, N-ary tree construction and HNSW sub-indices construction. Vector Encryption. The DO encrypts each vector 𝑣 ∈ 𝑉 using both DCPE and DCE, which serve different purposes in our scheme. The DCPE ciphertexts are used to construct and search the HNSW sub-indices, while the DCE ciphertexts are used for exact secure distance comparisons. 5

[1, 16]

contain approximately the same number of objects. The recursive partitioning terminates when only one attribute value remains. Consequently, each tree node 𝑡𝑛 maintains its interval [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ] and the identifiers of the objects whose attribute values fall within that interval. The resulting tree T enables a range predicate to be decomposed into a small set of tree nodes whose intervals are fully contained in the query range. HNSW Sub-index Construction. After constructing the N-ary tree T , the DO builds an HNSW sub-index for each tree node in a bottom-up manner. For a tree node 𝑡𝑛, let 𝑉𝑡𝑛 = {𝑣𝑖 ∈ 𝑉 | 𝑜𝑖 ∈ 𝑂𝑡𝑛 } denote its associated vector set, and let 𝐶𝑉DCPE = {𝐶 𝑣DCPE | 𝑣𝑖 ∈ 𝑉𝑡𝑛 } 𝑖 𝑡𝑛 denote the corresponding DCPE ciphertext set. The HNSW subindex associated with 𝑡𝑛 is denoted by 𝐺𝑡𝑛 and indexes 𝐶𝑉DCPE . 𝑡𝑛 The DO constructs the sub-indices by traversing T in post-order, such that the sub-indices of all child nodes are available before constructing that of their parent. For each leaf node 𝑡𝑛, the DO directly builds 𝐺𝑡𝑛 over 𝐶𝑉DCPE . In particular, if the leaf contains 𝑡𝑛 only one object, 𝐺𝑡𝑛 consists of a single indexed vector. Consider an internal node 𝑡𝑛 with child nodes {𝑡𝑛 1, . . . , 𝑡𝑛𝑚 }, where 𝑚 ≤ 𝑏. Since 𝑂𝑡𝑛 is partitioned by its child nodes, its vector set satisfies Ð 𝑉𝑡𝑛 = 𝑚 𝑗=1 𝑉𝑡𝑛 𝑗 . To avoid constructing 𝐺𝑡𝑛 from scratch, the DO selects one child node 𝑡𝑛 ∗ as the base node and initializes 𝐺𝑡𝑛 with a copy of 𝐺𝑡𝑛∗ . The child with the largest vector set is selected, i.e., 𝑡𝑛 ∗ = arg max𝑡𝑛 𝑗 |𝑉𝑡𝑛 𝑗 |, so as to minimize the number of subsequent insertions. The DO then inserts every DCPE ciphertext in 𝐶𝑉DCPE 𝑡𝑛

[1, 8] [1, 4]

[5, 8]

[9, 12]

[13, 16]

[1, 2]

[3, 4]

[5, 6]

[7, 8]

[9, 10] [11, 12] [13, 14] [15, 16]

11 12 13 14 15 16 [10, 16]

Matched Node

Query Range

Figure 5: The illustration of range localization over T

CS adopts a filter-and-refine strategy: it first performs coarse search over the matched HNSW sub-indices to obtain a candidate set, and then applies DCE-based exact distance comparisons to refine the candidates and return the final top-𝑘 results. Query Preparation. Given 𝑞, the QU first performs range localization over its local N-ary tree T . Starting from the root, the QU prunes a node if its interval does not overlap with the query range, selects a node if its interval is fully contained in the query range, and recursively visits its children otherwise. Once a node is selected, its descendants are not further examined. The resulting matched node set, denoted by 𝐼𝑞 , compactly represents the query range and determines the HNSW sub-indices to be searched by the CS. We illustrate an example of range localization in Figure 5. The QU then encrypts 𝑣𝑞 using DCPE and DCE to generate the query trapdoor 𝑇𝑞 = (𝑇𝑞DCPE,𝑇𝑞DCE ). Finally, it sends (𝐼𝑞 ,𝑇𝑞 , 𝑘) to the CS for secure query execution.

𝑗

for each 𝑡𝑛 𝑗 ≠ 𝑡𝑛 ∗ into 𝐺𝑡𝑛 using the native insertion operation of HNSW. Consequently, the resulting sub-index contains exactly the vectors associated with 𝑡𝑛, i.e., 𝐺𝑡𝑛 indexes 𝐶𝑉DCPE . 𝑡𝑛 This procedure is repeatedly applied from the leaf level to the root until an HNSW sub-index has been constructed for every node in T . Finally, the DO obtains the set of HNSW sub-indices G = {𝐺𝑡𝑛 | 𝑡𝑛 ∈ T }. Index Outsourcing and Key Distribution. After completing the vector encryption and index construction, the DO distributes the generated data to the CS and the QU according to their respective roles. Specifically, the DO sends the set of HNSW sub-indices G to the CS. Each sub-index is associated with the identifier of its corresponding tree node, allowing the CS to locate the required subindices according to the matched node set received from the QU. The DO also sends 𝐶𝑉DCPE and 𝐶𝑉DCE to the CS for coarse retrieval and exact secure distance comparisons, respectively. In contrast, the DO distributes the N-ary tree T , together with the complete secret keys 𝑆𝐾DCPE and 𝑆𝐾DCE , to the QU. The tree T enables the QU to locally evaluate a range predicate and identify its matched node set, whereas the two secret keys are used to generate the DCPE and DCE trapdoors. The CS receives no component of either secret key. Consequently, the QU holds {T , 𝑆𝐾DCPE, 𝑆𝐾DCE }, while the CS holds {G, 𝐶𝑉DCPE, 𝐶𝑉DCE } and the necessary auxiliary metadata for secure query processing.

4.3

[9, 16]

Theorem 4.1 (Exact Range Localization). Let 𝐼𝑞 be the matched node set obtained for the query range [𝑙𝑞 , 𝑟𝑞 ]. For every matched node 𝑡𝑛 ∈ 𝐼𝑞 , its associated interval satisfies [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ] ⊆ [𝑙𝑞 , 𝑟𝑞 ]. Moreover, the object sets associated with the matched nodes are pairwise disjoint and exactly cover all objects satisfying the range predicate: Ð 𝑡𝑛∈𝐼𝑞 𝑂 𝑡𝑛 = {𝑜 𝑖 ∈ 𝑂 | 𝑎𝑖 ∈ [𝑙𝑞 , 𝑟𝑞 ]}. Consequently, every object indexed by the HNSW sub-indices associated with 𝐼𝑞 satisfies the query range, and no additional range post-filtering is required at the CS. Proof. A node is added to 𝐼𝑞 only when its interval is fully contained in [𝑙𝑞 , 𝑟𝑞 ]. Hence, for every 𝑡𝑛 ∈ 𝐼𝑞 , [𝑙𝑡𝑛 , 𝑟𝑡𝑛 ] ⊆ [𝑙𝑞 , 𝑟𝑞 ], and every object 𝑜𝑖 ∈ 𝑂𝑡𝑛 satisfies 𝑎𝑖 ∈ [𝑙𝑞 , 𝑟𝑞 ]. We next show that every object satisfying the range predicate is covered by a matched node. Consider any object 𝑜𝑖 such that 𝑎𝑖 ∈ [𝑙𝑞 , 𝑟𝑞 ]. During the top-down traversal, any node containing 𝑜𝑖 cannot be pruned, because its interval contains 𝑎𝑖 and therefore overlaps with the query range. If such a node is fully contained in the query range, it is added to 𝐼𝑞 and 𝑜𝑖 is covered. Otherwise, the traversal continues along the unique child whose object set contains 𝑜𝑖 . Since the tree is recursively partitioned until each leaf corresponds to a single attribute value, the traversal eventually reaches a node whose interval is contained in [𝑙𝑞 , 𝑟𝑞 ]. Thus, every qualifying object belongs to the object set of some matched node. Finally, once a node is added to 𝐼𝑞 , its descendants are not visited. Therefore, no matched node is an ancestor of another matched

Secure Query Processing

Given a query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘), secure query processing consists of query preparation at the QU and query execution at the CS. The QU locally identifies the tree nodes in T matching the query range, generates the DCPE and DCE trapdoors for 𝑣𝑞 , and sends the resulting query request to the CS. Upon receiving the request, the 6

Query Processing Cost. Query processing consists of query preparation at the QU and filter-and-refine search at the CS. At the QU side, range localization over T costs 𝑂 (log𝑏 |𝐴|). Generating the DCPE and DCE trapdoors costs 𝑂 (𝑑) and 𝑂 (𝑑 2 ), respectively. Therefore, the query preparation cost at the QU is 𝑂 (𝑑 2 + log𝑏 |𝐴|). At the CS side, the filtering phase searches |𝐼𝑞 | matched HNSW sub-indices. Since searching one HNSW sub-index costs 𝑂 (𝑑 log 𝑛) in the worst case, the total sub-index search cost is 𝑂 (|𝐼𝑞 |𝑑 log 𝑛). Each sub-index returns at most 𝑘 0 candidates, and the returned list is already ordered. Therefore, the merge cost of those lists is 𝑂 (𝑘 0 |𝐼𝑞 | log |𝐼𝑞 |), and the CS then retains the top-𝑘 ′ candidates for refinement. During refinement, the CS computes DCE-based secure distances for these 𝑘 ′ candidates and maintains a max-heap of size 𝑘 to obtain the final top-𝑘 results. Each DCE comparison costs 𝑂 (𝑑), and each heap update costs 𝑂 (log 𝑘). Therefore, the refinement phase costs 𝑂 (𝑘 ′ (𝑑 + log 𝑘)). Overall, the CS side costs 𝑂 (|𝐼𝑞 |𝑑 log 𝑛 + 𝑘 0 |𝐼𝑞 | log |𝐼𝑞 | + 𝑘 ′ (𝑑 + log 𝑘)). During query processing, the QU and the CS exchange two messages. First, the QU sends the DCPE and DCE trapdoors, the matched node identifiers, and the parameter 𝑘 to the CS. The two trapdoors occupy 𝑂 (𝑑) space, while the matched node identifiers occupy 𝑂 (|𝐼𝑞 |) space. Second, the CS returns the identifiers of the final top-𝑘 results, which requires 𝑂 (𝑘) space. Hence, the total communication overhead is 𝑂 (𝑑 + |𝐼𝑞 | + 𝑘). Space Complexity. Let 𝑁𝑇 denote the number of nodes in the Nary tree T . At the QU side, the N-ary tree requires 𝑂 (𝑁𝑇 ) space. The QU also stores 𝑆𝐾DCPE of space 𝑂 (1) and 𝑆𝐾DCE of space 𝑂 (𝑑 2 ). Thus, the QU-side storage is 𝑂 (𝑁𝑇 + 𝑑 2 ). At the CS side, the DCPE and DCE ciphertexts require 𝑂 (𝑛𝑑) space. Since each object appears in the HNSW sub-indices along a root-to-leaf path of length 𝑂 (log𝑏 |𝐴|), the total number of indexed object appearances is 𝑂 (𝑛 log𝑏 |𝐴|). Given the HNSW degree parameter 𝑀, all HNSW sub-indices require 𝑂 (𝑀𝑛 log𝑏 |𝐴|) space. Thus, the CS-side storage is 𝑂 (𝑛𝑑 + 𝑀𝑛 log𝑏 |𝐴|).

node. Since sibling subtrees contain disjoint object sets, the object sets associated with different matched nodes are pairwise disjoint. Ð It follows that 𝑡𝑛∈𝐼𝑞 𝑂𝑡𝑛 = {𝑜𝑖 ∈ 𝑂 | 𝑎𝑖 ∈ [𝑙𝑞 , 𝑟𝑞 ]}. Therefore, all objects searched by the CS already satisfy the range predicate, eliminating the need for range post-filtering. □

CS-side Filtering. Upon receiving the query request (𝐼𝑞 ,𝑇𝑞 , 𝑘), the CS performs coarse retrieval over the HNSW sub-indices associated with the matched nodes. For each 𝑡𝑛 ∈ 𝐼𝑞 , the CS searches 𝐺𝑡𝑛 using the DCPE trapdoor 𝑇𝑞DCPE and retrieves a local candidate list 𝑅𝑡𝑛 containing at most 𝑘 0 objects. Since the local candidate lists are returned from different sub-indices, the CS further merges them into a unified candidate set. Specifically, it uses the distances computed over the DCPE ciphertexts to approximately compare Ð and rank the candidates in 𝑡𝑛∈𝐼𝑞 𝑅𝑡𝑛 . It then retains the top-𝑘 ′ candidates, denoted by 𝑅𝑞 , where 𝑘 ′ ≥ 𝑘 is a refinement parameter. Since DCPE approximately preserves distance ordering, 𝑅𝑞 contains high-quality candidates without revealing the plaintext vectors or their plaintext distances. CS-side Refinement. Given the coarse candidate set 𝑅𝑞 , the CS performs exact secure ranking using the DCE trapdoor 𝑇𝑞DCE . Specifically, it maintains a max-heap 𝐻 of size at most 𝑘, which stores the current top-𝑘 results. Each candidate in 𝑅𝑞 is inserted into 𝐻 according to the exact distance ordering obtained through the DCE distance-comparison operation. Once 𝐻 contains 𝑘 candidates, a new candidate is retained only if it is closer to 𝑣𝑞 than the current farthest candidate in 𝐻 . After all candidates in 𝑅𝑞 have been examined, the objects retained in 𝐻 form the final top-𝑘 result set. Since DCE reveals only the outcomes of distance comparisons, the CS can determine the exact ranking among the candidates without learning their plaintext vectors or exact distance values. Moreover, by Theorem 4.1, no additional range post-filtering is required. The CS finally returns the identifiers of the objects in 𝐻 to the QU.

4.4

Cost Analysis

SECURITY ANALYSIS

In this section, we analyze the security of the proposed PP-RFANNS scheme against the honest-but-curious CS. Our scheme employs two existing encryption primitives, namely DCPE and DCE, to protect vectors and support encrypted distance comparisons. Instead of claiming a new simulation-based security result for the complete composition of DCPE, DCE, and the HNSW sub-indices, we rely on the security guarantees established for the underlying primitives and explicitly characterize the additional information revealed by the complete PP-RFANNS protocol.

In this section, we analyze the computation, communication, and storage costs of PP-RFANNS. We consider secure index construction, query processing at the QU and CS, communication between them, and overall space complexity. Let |𝐼𝑞 | denote the number of matched nodes, 𝑘 0 the number of candidates retrieved from each matched sub-index, and 𝑘 ′ the number retained for refinement. Index Construction Cost. During secure index construction, the DO first encrypts all database vectors using both DCPE and DCE. Since encrypting one vector with DCPE and DCE requires 𝑂 (𝑑) and 𝑂 (𝑑 2 ) time, respectively, the total vector encryption cost is 𝑂 (𝑛𝑑 2 ). The DO then builds the N-ary tree T over 𝐴, which costs 𝑂 (𝑛 log𝑏 |𝐴|). Finally, the DO constructs an HNSW sub-index for each tree node in a bottom-up manner. For each node 𝑡𝑛 ∈ T , let 𝑛𝑡𝑛 be the number of vectors associated with 𝑡𝑛. Constructing the corresponding HNSW sub-index costs 𝑂 (𝑑𝑛𝑡𝑛 log 𝑛𝑡𝑛 ). Since evÍ ery vector appears in 𝑂 (log𝑏 |𝐴|) tree nodes, we have 𝑡𝑛∈ T 𝑛𝑡𝑛 = 𝑂 (𝑛 log𝑏 |𝐴|). Moreover, log 𝑛𝑡𝑛 ≤ log 𝑛. Therefore, the total cost of constructing all HNSW sub-indices is 𝑂 (𝑑𝑛 log𝑏 |𝐴| log 𝑛). Combining the above costs, the overall index construction complexity is 𝑂 (𝑛𝑑 2 + 𝑛 log𝑏 |𝐴| + 𝑑𝑛 log𝑏 |𝐴| log 𝑛).

5.1

Security of the Underlying Primitives

DCPE Security. The proposed scheme adopts the Scale-and-Perturb construction of DCPE [9]. Given a vector 𝑣, its DCPE ciphertext is generated as 𝐶 𝑣DCPE = 𝑠 · 𝑣 + 𝜆𝑣 , where 𝑠 is a secret scaling factor and 𝜆𝑣 is a random perturbation vector. DCPE is designed to preserve approximate distance-comparison relationships while preventing direct recovery of plaintext vector coordinates under its original security model. The CS receives only the DCPE ciphertexts and does not obtain the secret parameters 𝑠 and 𝛽. Therefore, the plaintext vectors cannot be directly recovered without violating 7

the security guarantee of DCPE. Nevertheless, DCPE intentionally reveals approximate geometric relationships. In particular, the CS can compute distances between DCPE ciphertexts and use them to construct and traverse the HNSW sub-indices. Hence, DCPE does not hide ciphertext-space distances or the approximate distance orders induced by these distances. DCE Security. DCE [20] enables the CS to compare the exact distances between two encrypted vectors and an encrypted query without revealing the underlying vectors or their exact plaintext distance values. The DCE construction is IND-KPA secure under its specified distance-comparison leakage. Specifically, the CS learns the outcomes of the distance comparisons invoked during query processing, but does not learn the plaintext vector coordinates, query vector coordinates, or exact distance values. In our scheme, DCPE and DCE use independent secret keys and randomness. A vector or query vector is encrypted separately under the two primitives. Consequently, information obtained from one ciphertext representation does not provide the secret key or randomness used by the other encryption scheme.

5.2

the HNSW sub-indices to be searched. Therefore, the CS does not directly learn the numerical query bounds. However, because the CS knows the object identifiers contained in each matched sub-index, it can derive the set of objects 𝑂𝑞 = Ð 𝑡𝑛∈𝐼𝑞 𝑂 𝑡𝑛 in the query range. Thus, the proposed scheme hides the numerical semantics of the query range, but does not hide the access pattern of the objects covered by the range. For repeated queries, the CS may additionally observe whether two queries access the same sub-indices or overlapping object sets. Consequently, equality, containment, and overlap relationships between different range queries may be inferred from their access patterns, even though their numerical endpoints remain hidden.

5.4

Database Privacy

The CS receives the DCPE and DCE ciphertexts, the HNSW subindices, and the associated object identifiers. The CS does not receive the plaintext vectors in 𝑉 or the secret keys of either encryption scheme. Recovering the coordinates of a database vector from its DCPE or DCE ciphertext would therefore require violating the security guarantee of the corresponding primitive. The use of two encrypted representations does not by itself reveal the plaintext vector, since the representations are generated with independent keys and randomness. The plaintext numerical attributes in 𝐴 are not outsourced to the CS. They are used by the DO to construct the range-aware N-ary tree, which is subsequently distributed to authorized QUs rather than the CS. Therefore, the CS does not directly observe the numerical value 𝑎𝑖 associated with an object. However, each HNSW sub-index corresponds to an N-ary tree node, and the CS observes the object identifiers associated with each sub-index. Consequently, the CS learns the object-to-sub-index membership relation and can infer set-containment relationships among sub-indices, as well as the repeated occurrence of an object in multiple sub-indices along the tree hierarchy. This information may reveal that the attributes of certain objects fall within the same hidden interval, although it does not directly disclose the interval boundaries or the exact attribute values.

5.3

Leakage Characterization

We now summarize the information revealed to the CS during secure index construction and query processing. Construction Leakage. After secure index construction, the CS observes Lconstruct (𝑂) = (𝑛, 𝑑, pp, Topo(G), Mem(G), e Δ𝑉 ). Here, ➊ 𝑛 and 𝑑 denote the number and dimensionality of the database vectors, respectively; ➋ pp contains the public index and query parameters, including the HNSW parameters, the ciphertext dimensions, and the parameters 𝑘 0 and 𝑘 ′ ; ➌ Topo(G) denotes the number, sizes, levels, vertices, and edges of the outsourced HNSW sub-indices; ➍ Mem(G) = {(𝑡𝑛, 𝑖) | 𝑜𝑖 ∈ 𝑂𝑡𝑛 } denotes the membership relationship between object identifiers and HNSW sub-indices; ➎e Δ𝑉 denotes the pairwise DCPE ciphertext-space distances among all encrypted database vectors, which are directly computable by the CS from the outsourced DCPE ciphertext set. The components of Lconstruct are jointly determined by the real index construction procedure. In particular, the HNSW topology depends on the sub-index memberships, DCPE distance relationships, insertion order, index parameters, and the randomness used during HNSW construction. They should therefore be understood as a mutually consistent server-side view rather than independently generated leakage values. Query Leakage. For a query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘), the CS observes Lquery (𝑂, 𝑞) = (𝐼𝑞 , 𝑂𝑞 , AP𝑞HNSW, e Δ𝑉 ,𝑞 , Cand𝑞 , 𝑅𝑞 , 𝜋 DCE, Out𝑞 ). Here, 𝑅𝑞 ,𝑞

➊ 𝐼𝑞 is the set of matched tree-node identifiers sent by the QU; ➋ Ð 𝑂𝑞 = 𝑡𝑛∈𝐼𝑞 𝑂𝑡𝑛 is the set of object identifiers covered by the matched sub-indices; ➌ AP𝑞HNSW denotes the HNSW access pattern, including the sub-indices, vertices, and edges examined during filtering; ➍ e Δ𝑉 ,𝑞 denotes the DCPE ciphertext-space distances between the query trapdoor and all encrypted database vectors, which are directly computable by the CS after receiving the DCPE query trapdoor. ➎ Cand𝑞 = {𝑅𝑡𝑛 | 𝑡𝑛 ∈ 𝐼𝑞 } denotes the local candidate lists returned from the matched HNSW sub-indices; ➏ 𝑅𝑞 is the candidate set retained after merging the local candidate lists and is a derived component of the filtering leakage; ➐ 𝜋𝑅DCE denotes 𝑞 ,𝑞 the exact relative distance order revealed by the DCE comparisons over 𝑅𝑞 ; ➑ Out𝑞 denotes the identifiers of the final top-𝑘 results. The HNSW access pattern is determined by the matched subindices, their graph topology, the DCPE comparison outcomes, and the search parameters. It is listed explicitly because it is directly observable by the CS during query execution.

Query Privacy

For a query 𝑞 = (𝑣𝑞 , [𝑙𝑞 , 𝑟𝑞 ], 𝑘), the QU locally generates the DCPE and DCE trapdoors 𝑇𝑞 = (𝑇𝑞DCPE,𝑇𝑞DCE ). Under the security guarantees of DCPE and DCE, the CS cannot directly recover the plaintext 𝑣𝑞 from the trapdoors. The DCPE trapdoor nevertheless reveals the ciphertext-space distances and approximate ordering information required for HNSW search, while the DCE trapdoor reveals the outcomes of the exact comparisons performed during refinement. The query range [𝑙𝑞 , 𝑟𝑞 ] is processed locally by the QU over the N-ary tree. The numerical endpoints 𝑙𝑞 and 𝑟𝑞 are never sent to the CS. Instead, the QU sends the matched node set 𝐼𝑞 , which identifies 8

Table 1: Dataset statistics.

For a sequence of queries, repeated matched nodes, candidate identifiers, and result identifiers reveal equality and overlap patterns across query executions. These cross-query relations are derivable from the per-query leakage described above.

5.5

Dataset Sift1M Gist GloVe Deep1M

Leakage Comparisons

We compare our scheme with the secure adaptations instantiated in Section 3.4. All three adaptations use the same iSHE-based rangechecking protocol. We focus on the view of the primary CS and assume that the auxiliary server does not collude with it. Under their respective cryptographic assumptions, all four schemes protect plaintext vectors, numerical attributes, query vectors, query bounds, and exact distance values, subject to their explicitly characterized leakage. Secure Pre-filtering reveals the access pattern of its encrypted range index, the records subjected to iSHE-based checking, the range-checking outcomes, the complete qualifiedobject set, and the DCE comparison outcomes. Secure Post-filtering reveals the access pattern, the DCE comparison outcomes, and the candidate set of global PP-ANNS, and the iSHE checking outcomes over the retrieved candidates. PP-iRangeGraph reveals the DCPE-guided graph traversal trace, including the inspected vertices and edges, the iSHE range-checking outcomes for inspected neighbors, the coarse candidate set retained after traversal, and the DCE comparison outcomes over the final refinement set. Our scheme avoids online encrypted range checking, but reveals the matched node set and, through object-to-sub-index memberships, the complete qualified-object set. Secure Pre-filtering reveals the same qualified-object set together with its encrypted-index access pattern, whereas Secure Post-filtering and PP-iRangeGraph reveal range-checking outcomes only for the candidates examined. Secure Post-filtering, PP-iRangeGraph, and our scheme all use DCPE for coarse filtering and DCE for exact refinement; their principal difference is the stage at which the range predicate restricts encrypted vector search. Thus, our scheme should not be viewed as strictly more secure than the baselines. Rather, it trades matchednode and qualified-set leakage for lower online query overhead and avoids the additional non-collusion assumption required by our two-server baseline instantiations.

5.6

#dimensions 128 960 100 96

#objects 1,000,000 1,000,000 1,183,514 1,000,000

#queries 10,000 1,000 10,000 10,000

the explicitly characterized structural, access-pattern, and distancecomparison leakage. Our analysis assumes a static database and an honest-but-curious CS. Dynamic updates, malicious-server behavior, and result verifiability are outside the scope of this work.

EXPERIMENTS

In this section, we conduct extensive experiments to demonstrate the superiority of our scheme over the baselines. We first present the experimental settings and then report our findings.

6.1

Experimental Settings

Datasets. We construct object sets by associating each vector with a numerical attribute. Specifically, we use four widely adopted 𝑘ANNS benchmark datasets: Sift1M 2 , Gist 2 , GloVe 3 , and Deep1M 4 . Each vector is assigned an integer attribute independently and uniformly sampled from the domain [1, 10000]. For each query vector, we randomly generate an interval within the same domain as the range predicate. Table 1 summarizes the dataset statistics. For the scalability evaluation, we further construct datasets containing different numbers of vectors randomly sampled from Sift1B 2 and Deep1B 5 . Their numerical attributes and query ranges are generated following the same procedure. Unless otherwise specified, we use mixed-selectivity setting by default, where each query range is generated by first uniformly sampling its left endpoint from the attribute domain and then uniformly sampling its right endpoint from the remaining domain to the right. Performance Metrics. We evaluate query efficiency using queries per second (QPS) and the query latency, and estimate the accuracy by 𝑅𝑒𝑐𝑎𝑙𝑙@𝑘. QPS is calculated as the total number of queries divided by their total processing time. For a query 𝑞, let 𝑁 ∗ (𝑞) denote the exact 𝑘-nearest neighbors among the vectors satisfying its range predicate, and let 𝑁 (𝑞) denote the results returned by a PP-RFANNS |𝑁 ∗ (𝑞)∩𝑁 (𝑞) | method. The recall of 𝑞 is defined as Recall@𝑘 (𝑞) = . 𝑘 We report 𝑅𝑒𝑐𝑎𝑙𝑙@𝑘 averaged over all queries. Unless otherwise specified, we set 𝑘 = 10. Baselines. We compare our scheme with the secure adaptations introduced in Section 3: Secure Pre-filtering, Secure Post-filtering, and PP-iRangeGraph. All methods operate in an outsourced encryptedsearch setting. For a fair comparison, all methods use the same datasets, queries, and settings for the cryptographic primitives shared among them. Following prior work [20], we set 𝑀 = 40 and efConstruction = 600 for all HNSW-based indices. We vary the principal search parameters of each approximate method to obtain its QPS–𝑅𝑒𝑐𝑎𝑙𝑙@𝑘 trade-offs. Specifically, PP-RFANNS varies

Summary

Based on the security guarantees of DCPE and DCE, our scheme protects the plaintext coordinates of the vectors in 𝑉 , the plaintext numerical values in 𝐴, the plaintext query vector 𝑣𝑞 , the query bounds 𝑙𝑞 and 𝑟𝑞 , the exact plaintext distance values, and the secret keys against the honest-but-curious CS. At the same time, our scheme explicitly allows the leakage of the encrypted HNSW topology, object-to-sub-index memberships, DCPE ciphertext-space distance relationships, matched-node access patterns, HNSW traversal traces, candidate identifiers, DCE comparison outcomes, and final result identifiers. In particular, the CS can determine the qualified encrypted objects, although it does not directly learn the query range or the corresponding plaintext attribute values. Therefore, the security guarantee of our scheme should be understood as follows: under the established security properties of DCPE and DCE, the scheme prevents the CS from directly recovering the protected plaintext database and query contents, subject to

2 http://corpus-texmex.irisa.fr/ 3 https://nlp.stanford.edu/projects/glove/ 4 http://sites.skoltech.ru/compvision/noimi/ 5 https://disk.yandex.ru/d/11eDCm7Dsn9GA/

−1

−3

0.80

0.85

0.90

0.95

10 10

Secure Post-filtering selectivity = 10%

−1

0.80

0.85

0.90

0.95

−3

Recall@10

selectivity = mixed

selectivity = 1%

1.00

0.80

0.85

0.90

0.95

selectivity = 40%

−1

−3

−2

1.00

PP-iRangeGraph selectivity = 20%

1.00

0.80

QPS

Secure Pre-filtering

selectivity = 1%

QPS

selectivity = mixed

QPS

PP-RFANNS 3

0.85

Recall@10

0.90

0.95

−1

−3

1.00

0.80

0.85

Recall@10

0.90

0.95

1.00

Recall@10

−1

−3

0.80

0.85

0.90

0.95

1.00

−1

−3

0.80

0.85

Recall@10

0.90

0.95

−1

−3

1.00

0.80

selectivity = 10%

0.85

Recall@10

0.90

0.95

−1

−3

1.00

0.80

selectivity = 20%

QPS

(a) Sift1M

0.85

Recall@10

0.90

0.95

−1

−3

1.00

0.80

selectivity = 40%

0.85

Recall@10

0.90

0.95

1.00

Recall@10

(b) Gist

10 10

−2

−4

0.80

0.85

0.90

0.95

−1

−3

1.00

0.80

0.85

0.90

0.95

Recall@10

selectivity = mixed

selectivity = 1%

1.00

selectivity = 20%

selectivity = 40%

−2

−4

0.80

0.85

0.90

0.95

−2

−4

1.00

0.80

QPS

selectivity = 10% 10

QPS

selectivity = 1%

QPS

selectivity = mixed 10

0.85

Recall@10

0.90

0.95

−2

−4

1.00

0.80

0.85

Recall@10

0.90

0.95

1.00

Recall@10

−3

0.80

0.85

0.90

0.95

Recall@10

1.00

10 10

selectivity = 10%

selectivity = 20%

−1

−3

selectivity = 40%

−1

−3

QPS

−1

QPS

−1

−3

−2

0.80

0.85

0.90

0.95

1.00

0.80

0.85

Recall@10

0.90

0.95

Recall@10

1.00

0.80

0.85

0.90

0.95

1.00

Recall@10

0.80

0.85

0.90

0.95

1.00

Recall@10

(d) Deep1M

Figure 6: Comparisons of search performance of PP-RFANNS queries. (Exp. 1) 𝑘 0 , 𝑘 ′ , and the HNSW search breadth; Secure Post-filtering varies the search breadth of its global encrypted HNSW index and the number 𝑘 ′ of retrieved candidates; and PP-iRangeGraph varies its sub-index search breadth. Secure Pre-filtering exhaustively evaluates all qualified vectors using DCE and therefore returns the exact top-𝑘 results. Computing Environments. All experiments are conducted on a server equipped with two 10-core Intel(R) Xeon(R) Silver 4210 CPUs and 256 GiB of RAM, running CentOS 7.9.2009. Three baselines additionally use a non-colluding auxiliary server with the same hardware configuration to support iSHE-based secure range checking, whereas PP-RFANNS operates with a single cloud server. All methods are implemented in C++, and the query-processing operations on each server are executed using a single thread unless otherwise specified. Under this setting, one end-to-end iSHE-based range check takes 0.0312 seconds on average, including all cryptographic operations and inter-server communication.

6.2

Experimental Results

Exp. 1: Search Performance of PP-RFANNS Queries. We compare PP-RFANNS with the three baselines under mixed and fixed query selectivities from 1% to 40%. As shown in Figure 6, PPRFANNS consistently achieves the best QPS–Recall trade-off. Even at 40% selectivity, where Secure Post-filtering is relatively favorable, PP-RFANNS still achieves 595x to 2600x speedups at 𝑅𝑒𝑐𝑎𝑙𝑙@10 = 0.95. Secure Pre-filtering achieves 𝑅𝑒𝑐𝑎𝑙𝑙@10 = 1, but its QPS is always less than 0.2. Although its secure range index reduces the number of iSHE checks, the remaining checks still incur substantial computation and interaction overhead. It also performs exhaustive DCE-based search over all qualified vectors, making it increasingly expensive at high selectivity. PP-iRangeGraph repeatedly invokes iSHE during graph traversal, so its QPS is generally below 0.01. In contrast, PP-RFANNS reaches 68–1,288 QPS at 𝑅𝑒𝑐𝑎𝑙𝑙@10 = 0.95. All three baselines incur online iSHE range-checking and interserver interaction. PP-RFANNS instead localizes the range at the QU and searches only the matched encrypted sub-indices on a single CS, achieving better QPS–Recall trade-offs across different selectivities. 10

Latency

Sift1M - Selectivity = 1% 10

−2

−4

Table 2: Index cost: each entry reports index building time in seconds / index size in GiB (Exp. 3)

QU Cost iSHE Range Checks CS Candidate Search DCE Refinement

Method

NS FAN PP-R

ring

-filte

re Pre

Secu

ering

st-filt

re Po

Secu

ph eGra

Rang

PP-i

Latency

Sift1M - Selectivity = 40% 10

−2

−4

QU Cost iSHE Range Checks CS Candidate Search DCE Refinement

N FAN PP-R

S Sec

re-f ure P

ng filteri

ilteri

Sec

osture P

eGra

ang P-iR

Sift1M

Gist

GloVe

Deep1M

PP-RFANNS 418 / 2.51 2531 / 2.51 768 / 5.39 411 / 2.51 Secure Pre 0.03 / 0.005 0.03 / 0.005 0.03 / 0.006 0.03 / 0.005 Secure Post 150 / 0.79 1139 / 3.89 204 / 0.82 138 / 0.68 PP-iRangeGraph 3071 / 1.49 10373 / 1.40 4780 / 1.47 2865 / 1.62 DCPE Encryption 6 / 0.47 31 / 3.57 6 / 0.44 5 / 0.35 DCE Encryption 29 / 8.10 287 / 57.69 26 / 7.61 18 / 6.19

Secure Pre-filtering and Secure Post-filtering incur relatively low index costs because the former only builds a lightweight Btree, whereas the latter maintains a single global HNSW index. In contrast, PP-RFANNS and PP-iRangeGraph construct hierarchical range-aware graph indices and therefore require substantially more construction time and storage. Between the two hierarchical methods, PP-RFANNS is faster to build than PP-iRangeGraph. This improvement mainly results from its shallower N-ary-tree hierarchy. The depths of PP-RFANNS are 7, 7, 14, and 7 on Sift1M, Gist, GloVe, and Deep1M, respectively, compared with 20, 20, 21, and 20 for PP-iRangeGraph. Because graph indices are constructed repeatedly along root-to-leaf paths, the reduced hierarchy depth considerably lowers the overall construction workload. PP-RFANNS, however, requires more index space than PP-iRangeGraph, due to their underlying graph-index implementations. Overall, PP-RFANNS trades additional storage for substantially faster index construction. Exp. 4: Effect of the Branching Factor 𝑏. The branching factor 𝑏 controls the structure of the N-ary tree and the decomposition of a query range. Increasing 𝑏 reduces the tree height, but may produce more matched nodes and consequently require the CS to search more HNSW sub-indices. Figure 8 evaluates the effect of 𝑏 on the QPS–Recall trade-off. On Sift1M, Gist, and Deep1M, query performance first improves and then degrades as 𝑏 increases, with 𝑏 = 4 generally achieving the best trade-off. On GloVe, performance decreases with increasing 𝑏, indicating that the additional sub-index searches outweigh the benefit of a shallower tree. Based on these results, we set 𝑏 to 4, 4, 2, and 4 for Sift1M, Gist, GloVe, and Deep1M, respectively, in Exp. 1. Exp. 5: Effect of the Search Parameter 𝑘 0 . The parameter 𝑘 0 controls the number of candidates retrieved from each matched HNSW sub-index during the filtering phase. As shown in Figure 9, increasing 𝑘 0 generally improves 𝑅𝑒𝑐𝑎𝑙𝑙@10 but reduces QPS. A larger 𝑘 0 expands the candidate pool and increases the likelihood of retaining the true nearest neighbors, at the cost of additional sub-index search, candidate merging, and refinement overhead. These results demonstrate the expected QPS–Recall trade-off controlled by 𝑘 0 . Exp. 6: Effect of the Search Parameter 𝑘 ′ . The parameter 𝑘 ′ controls the number of coarse candidates retained after merging the local candidate lists for DCE-based refinement. A larger 𝑘 ′ increases the likelihood that the true nearest neighbors are included in the refinement set, but also enlarges the number of expensive DCE comparisons. To evaluate this trade-off, we fix 𝑘 0 = 40 and vary 𝑘 ′ . As shown in Figure 10, 𝑅𝑒𝑐𝑎𝑙𝑙@10 generally improves as 𝑘 ′ increases and gradually converges, while the additional refinement

Figure 7: Cost decomposition on Sift1M at 𝑅𝑒𝑐𝑎𝑙𝑙@10 = 0.95 (Exp. 2)

Exp. 2: Cost Decomposition of PP-RFANNS Queries. We decompose the per-query latency of each method to identify its dominant cost components and explain the observed performance differences. Figure 7 reports the latency breakdown on Sift1M at 𝑅𝑒𝑐𝑎𝑙𝑙@10 = 0.95. The decomposition shows that the query latency of all three baselines is dominated by iSHE-based secure range checking. Secure Pre-filtering uses iSHE to identify the qualified objects before vector search, Secure Post-filtering applies iSHE to the candidates retrieved from the global encrypted HNSW index, and PP-iRangeGraph repeatedly invokes iSHE for newly inspected neighbors during graph traversal. These online checks incur expensive homomorphic computation, decryption, and inter-server interaction. In contrast, PP-RFANNS performs range localization locally at the QU before server-side vector search and therefore eliminates this dominant online iSHE cost. This result directly demonstrates the advantage of decoupling range localization from encrypted vector search. Among the remaining CS-side components, the vector search costs differ across the baselines. Secure Pre-filtering directly performs exhaustive DCE-based distance comparisons over all qualified vectors. Its DCE cost therefore grows with the number of objects satisfying the range predicate and becomes substantial at high selectivity. In contrast, others use DCPE for coarse candidate search and DCE only for final refinement. Their DCPE-based search repeatedly evaluates ciphertext-space distances during HNSW or graph traversal and may inspect many vertices before obtaining a sufficiently accurate candidate set. Although an individual DCE comparison is more expensive, DCE is applied only to the much smaller refinement set retained after coarse retrieval, so its total cost remains relatively low. Exp. 3: Index Cost. We evaluate the index cost of each method in terms of building time and index size. Table 2 reports both metrics on the four datasets. Since DCPE and DCE encryption are independent of index construction, their encryption time and ciphertext size are reported separately in the last two rows. 11

6 4 2 0.80

0.85

0.90 Recall@10

0.95

0 0.80

1.00

0.85

0.90

0.95

2 1 0 0.80

1.00

QPS(×102 )

b=6 b=8

QPS(×102 )

b=2 b=4

5 3

Recall@10

0.90 Recall@10

(b) Gist

(a) Sift1M

0.85

0.95

0.80

1.00

0.85

0.90

0.95

1.00

Recall@10 (d) Deep1M

4 2 0.80

0.85

0.90

0.95

0 0.80

1.00

0.85

0.90

0.95

1.00

QPS(×102 )

k0 = 40 k0 = 50 k0 = 60

QPS(×102 )

k0 = 10 k0 = 20 k0 = 30

QPS(×102 )

Figure 8: Effects of the branching factor 𝑏 on query performance (Exp. 4)

6 4 2

0.65

0.75

0.85

0.80

0.95

0.85

0.90

0.95

Recall@10

(a) Sift1M

(b) Gist

(d) Deep1M

1.00

QPS(×102 )

k ′ = 10 k ′ = 20 k ′ = 30 k ′ = 40 k ′ = 50 k ′ = 60

QPS(×102 )

Figure 9: Effects of the candidate number 𝑘 0 on query performance (Exp. 5)

0.85

0.90

0.95

1.00

3 2

0.80

0.75 0.80 0.85 0.90 0.95 1.00

0.70 0.75 0.80 0.85 0.90 0.95

0.80

0.85

0.90

Recall@10

(a) Sift1M

(b) Gist

(d) Deep1M

0.95

1.00

Figure 10: Effects of the parameter 𝑘 ′ on query performance (Exp. 6) Recall@10=0.90 Recall@10=0.95

10.32

10 6.56 4.80

5 1.55

3.00

10.0

16.63

25M

Latency (ms)

Recall@10=0.90 Recall@10=0.95

7.5

5.96 4.50

5.0

0.0

Sift Deep

25M 5M

25M

(b) Deep

Index Size (GiB)

Building Time (s)

5.09

1.80 2.10

2.5

(a) Sift 10

increases gradually with the database size and remains below 17 ms even at 25M vectors. Figures 11(c) and 11(d) report the index construction time and index size, respectively. The index size increases from about 2.5 GiB at 1M vectors to about 62.6 GiB at 25M vectors. This growth is expected because the N-ary tree has ℎ = 𝑂 (log𝑏 |𝐴|) levels, and each object is indexed by the HNSW sub-indices along its root-to-leaf path, resulting in 𝑂 (𝑛 log𝑏 |𝐴|) total indexed object occurrences. The construction time also grows faster than linearly because each object must be inserted into HNSW sub-indices at multiple tree levels. Nevertheless, index construction is performed only once offline. Overall, PP-RFANNS maintains low query latency as the database grows, while exhibiting the expected hierarchicalindex construction and storage costs.

8.49

25M

Sift Deep

40 20

5M 1M

(d) Index Size

Figure 11: The scalability of our scheme (Exp. 7).

CONCLUSION

In this paper, we study privacy-preserving range-filtered approximate nearest neighbor search over outsourced encrypted data. We proposed a PP-RFANNS scheme that combines an N-ary tree– HNSW hybrid index with DCPE-based filtering and DCE-based refinement. The scheme performs range localization at the query user and restricts encrypted vector search to the matched HNSW sub-indices, thereby avoiding online encrypted range checking. We analyze its cost and security under the honest-but-curious model. Experiments show that PP-RFANNS achieves better QPS–Recall trade-offs than secure pre-filtering, secure post-filtering, and PPiRangeGraph across different query selectivities, and scales effectively to larger datasets.

cost reduces query efficiency. This result indicates that most true nearest neighbors appear near the top of the merged candidate list. GloVe exhibits a larger recall variation than the other datasets, suggesting that its candidate quality is more sensitive to 𝑘 ′ . Exp. 7: Scalability Test. We evaluate the scalability of PP-RFANNS on random samples of Sift1B and Deep1B containing 1M, 5M, and 25M vectors. The attribute values and range-filtered queries are generated following the procedure described in the experimental setup. Figure 11 reports both the online search performance and the offline index cost. Figures 11(a) and 11(b) show the query latency at Recall@10 values of 0.90 and 0.95. On both datasets, the latency 12

REFERENCES

of Information Security 22, 4 (2023), 785–798. [25] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. Proceedings of the ACM on Management of Data 2, 3 (2024), 1 – 27. [26] Yanguo Peng, Jiangtao Cui, Hui Li, and Jianfeng Ma. 2017. A reusable and singleinteractive model for secure approximate k-nearest neighbor query in cloud. Information Sciences 387 (2017), 146–164. [27] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021. Learning transferable visual models from natural language supervision. In International conference on Machine Learning. PMLR, 8748–8763. [28] Sacha Servan-Schreiber, Simon Langowski, and Srinivas Devadas. 2022. Private Approximate Nearest Neighbor Search with Sublinear Communication. In S&P 2022. IEEE, 911–929. [29] Jiafan Wang and Sherman SM Chow. 2019. Forward and backward-secure rangesearchable symmetric encryption. Cryptology ePrint Archive (2019). [30] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD ’21: International Conference on Management of Data. ACM, 2614–2627. [31] Liang Wang, Nan Yang, Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. 2024. Improving text embeddings with large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 11897–11916. [32] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. PVLDB 14, 11 (2021), 1964–1978. [33] Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [34] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data. PVLDB 13, 12 (2020), 3152–3165. [35] Wai Kit Wong, David Wai-lok Cheung, Ben Kao, and Nikos Mamoulis. 2009. Secure kNN computation on encrypted databases. In SIGMOD. 139–152. [36] Jiadong Xie, Jeffrey Xu Yu, and Yingfan Liu. 2025. Graph Based K-Nearest Neighbor Search Revisited. ACM Trans. Database Syst. (May 2025). [37] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2025. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 6 (2025), 1–26. [38] Wenzhuo Xue, Hui Li, Yanguo Peng, Jiangtao Cui, and Yu Shi. 2018. Secure k Nearest Neighbors Query for High-Dimensional Vectors in Outsourced Environments. IEEE Transactions on Big Data 4, 4 (2018), 586–599. [39] Jiawei Yuan and Yifan Tian. 2019. Practical Privacy-Preserving MapReduce Based K-Means Clustering Over Large-Scale Dataset. IEEE Transactions on Cloud Computing 7, 2 (2019), 568–579. [40] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023. USENIX Association, 377–395. [41] Songnian Zhang, Rongxing Lu, Hui Zhu, Yandong Zheng, Yunguo Guan, and Fengwei Wang. 2024. Performance Enhanced Secure Spatial Keyword Similarity Query With Arbitrary Spatial Ranges. IEEE TIFS 19 (2024), 5272–5285. [42] Yandong Zheng, Rongxing Lu, Yunguo Guan, Jun Shao, and Hui Zhu. 2021. Efficient and privacy-preserving similarity range query over encrypted time series data. IEEE Transactions on Dependable and Secure Computing 19, 4 (2021), 2501–2516. [43] Yandong Zheng, Rongxing Lu, Songnian Zhang, Jun Shao, and Hui Zhu. 2024. Achieving Practical and Privacy-Preserving kNN Query over Encrypted Data. IEEE TDSC (2024). [44] Mingxun Zhou, Elaine Shi, and Giulia Fanti. 2025. Pacmann: Efficient Private Approximate Nearest Neighbor Search. In ICLR 2025. 99396–99416. [45] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 1 (2024), 1 – 26.

[1] Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. 2023. Retrieval-based Language Models and Applications. ACL Tutorial (2023). [2] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art. Proc. ACM Manag. Data 3, 1 (2025), 43:1–43:31. [3] Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O’neill. 2009. Order-preserving symmetric encryption. In Annual international conference on the theory and applications of cryptographic techniques. Springer, 224–241. [4] Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya P. Razenshteyn, and M. Sadegh Riazi. 2020. SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search. In USENIX Security 2020. USENIX Association, 2111–2128. [5] Ioannis Demertzis, Stavros Papadopoulos, Odysseas Papapetrou, Antonios Deligiannakis, and Minos Garofalakis. 2016. Practical private range search revisited. In Proceedings of the 2016 International Conference on Management of Data. 185– 198. [6] Josh Engels, Ben Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. In ICML. 12469 – 12490. [7] Fangxiaoyu Feng, Yinfei Yang, Daniel Cer, Naveen Arivazhagan, and Wei Wang. 2022. Language-agnostic BERT sentence embedding. In Proceedings of the 60th annual meeting of the association for computational linguistics (volume 1: Long papers). 878–891. [8] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB 12, 5 (2019), 461–474. [9] Georg Fuchsbauer, Riddhi Ghosal, Nathan Hauke, and Adam O’Neill. 2022. Approximate Distance-Comparison-Preserving Symmetric Encryption. In SCN 2022 (Lecture Notes in Computer Science), Vol. 13409. Springer, 117–144. [10] Teddy Furon, Hervé Jégou, Laurent Amsaleg, and Benjamin Mathon. 2013. Fast and secure similarity search in high dimensional space. In WIFS 2013. IEEE, 73–78. [11] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. 2022. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 16000–16009. [12] Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Guanhao Hou, Jieming Shi, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter. Proc. ACM Manag. Data 3, 3 (2025), 148:1–148:26. [13] Florian Kerschbaum. 2015. Frequency-hiding order-preserving encryption. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 656–667. [14] Kevin Lewi and David J Wu. 2016. Order-revealing encryption: New constructions, applications, and lower bounds. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 1167–1178. [15] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive NLP tasks. NeurIPS 33 (2020), 9459–9474. [16] Rui Li, Alex X. Liu, Ying Liu, Huanle Xu, and Huaqiang Yuan. 2019. Insecurity and Hardness of Nearest Neighbor Queries Over Encrypted Data. In ICDE 2019. IEEE, 1614–1617. [17] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data – experiments, analyses, and improvement. IEEE TKDE 32, 8 (2019), 1475– 1488. [18] Weipeng Lin, Ke Wang, Zhilin Zhang, and Hong Chen. 2017. Revisiting security risks of asymmetric scalar product preserving encryption and its variants. In ICDCS. IEEE, 1116–1125. [19] Yingfan Liu, Tong Wu, Jiadong Xie, Yang Zhao, Jeffrey Xu Yu, and Jiangtao Cui. 2026. Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap. In KDD. Association for Computing Machinery. [20] Yingfan Liu, Yandi Zhang, Jiadong Xie, Hui Li, Jeffrey Xu Yu, and Jiangtao Cui. 2025. Privacy-Preserving Approximate Nearest Neighbor Search on HighDimensional Data. In ICDE 2025. IEEE, 3017–3029. [21] Hassan Mahdikhani, Rongxing Lu, Yandong Zheng, Jun Shao, and Ali A. Ghorbani. 2020. Achieving O(log3 𝑛 ) Communication-Efficient Privacy-Preserving Range Query in Fog-Based IoT. IEEE Internet of Things Journal 7, 6 (2020), 5220–5232. [22] Yury Malkov and Dmitry Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI 42, 4 (2018), 824–836. [23] Yinbin Miao, Yutao Yang, Xinghua Li, Linfeng Wei, Zhiquan Liu, and Robert H Deng. 2023. Efficient privacy-preserving spatial data query in cloud computing. IEEE TKDE (2023). [24] Eirini Molla, Panagiotis Rizomiliotis, and Stefanos Gritzalis. 2023. Efficient searchable symmetric encryption supporting range queries. International Journal 13

Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search

Analyze & explore related research in Conceptio

Related documents