Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search
Proposes PP-RFANNS combining N-ary trees and HNSW for privacy-preserving range filtered ANN over encrypted vectors, achieving high efficiency on large datasets.
Key Findings
Methodology
The proposed PP-RFANNS scheme decouples range localization from encrypted vector search by leveraging a local N-ary tree to map query ranges to a compact set of nodes. The cloud server maintains encrypted HNSW sub-indices for each tree node, enabling targeted search. The process involves encrypting vectors with DCPE for approximate distance preservation and DCE for exact comparisons. During querying, the user locally maps the range predicate to relevant tree nodes, generating trapdoors sent to the server. The server performs coarse candidate retrieval using DCPE ciphertexts, then refines the top candidates with DCE-based exact distance comparisons. This filter-and-refine pipeline reduces cryptographic overhead while maintaining high search accuracy. The scheme's security, storage, and communication costs are analyzed, demonstrating scalability and robustness in large datasets.
Key Results
- Experiments on datasets such as SIFT, GloVe, Deep1M, and ImageNet show that at Recall@10=0.95, PP-RFANNS achieves query throughput improvements of over 100x compared to secure baseline methods. The approach scales efficiently to millions of vectors, with a significant reduction in query latency and communication overhead. Performance evaluations indicate that the method maintains high accuracy across various query ranges and dataset sizes, outperforming existing secure adaptations in both efficiency and retrieval quality.
- Compared to existing approaches like iRangeGraph and secure HNSW variants, PP-RFANNS reduces average query time by approximately 70%, especially in low-selectivity scenarios. The use of DCPE ciphertexts for approximate distance filtering accelerates candidate retrieval, while DCE-based exact comparisons ensure ranking precision. Ablation studies confirm that the combination of range mapping and filter-refine strategy is crucial for balancing efficiency and accuracy.
- The experiments also demonstrate that the dual encryption scheme (DCPE and DCE) effectively preserves the proximity order and enables efficient encrypted graph traversal. The scheme's ability to handle high-dimensional vectors (up to 1024 dimensions) with minimal performance degradation highlights its robustness. Overall, the results validate that PP-RFANNS can support large-scale, privacy-preserving vector search with practical query throughput and high retrieval fidelity.
Significance
This work marks a significant advancement in privacy-preserving vector search by integrating range filtering with encrypted ANN indices. It addresses the critical challenge of protecting sensitive data in outsourced environments while maintaining high search efficiency. The scheme's ability to perform range-constrained approximate nearest neighbor search over encrypted data opens new avenues for secure AI-powered applications, such as confidential multimedia retrieval, privacy-sensitive recommendation systems, and secure multi-modal data analysis. Its scalable design and rigorous security analysis provide a solid foundation for industrial deployment, bridging the gap between privacy needs and large-scale vector data management.
Technical Contribution
The paper's key technical innovations include: 1) a hybrid index structure combining a local N-ary tree for range localization with encrypted HNSW sub-indices, enabling targeted search over encrypted vectors; 2) a dual encryption framework using DCPE for approximate distance preservation and DCE for exact comparisons, balancing privacy and accuracy; 3) a filter-and-refine query pipeline that first retrieves coarse candidates via DCPE ciphertexts and then refines with DCE, significantly reducing cryptographic operations; 4) comprehensive analysis of the scheme's security, storage, and communication costs, demonstrating its scalability and robustness in large datasets. These contributions collectively push forward the state-of-the-art in privacy-preserving vector search.
Novelty
This research is the first to decouple range localization from encrypted vector search using a hierarchical N-ary tree combined with HNSW indices, addressing the limitations of prior methods that either lack range filtering or incur high cryptographic costs. Unlike existing schemes that rely solely on either plaintext or single-layer encryption, this approach integrates a multi-layered encryption scheme with a hybrid index, enabling efficient, privacy-preserving range-constrained ANN search. The innovative use of a local N-ary tree for range mapping and the filter-refine pipeline distinguishes this work from prior art, offering a novel solution to a long-standing challenge in secure vector retrieval.
Limitations
- The scheme's performance may degrade in extremely high-dimensional spaces (e.g., >1024 dimensions), due to increased index complexity and encryption overhead, requiring further optimization for such scenarios.
- The security model assumes honest-but-curious servers; malicious adversaries or collusion among multiple servers could potentially compromise data privacy, necessitating additional cryptographic safeguards.
- Dynamic updates to the encrypted index, such as insertions or deletions, are not extensively addressed; maintaining efficiency in dynamic environments remains an open challenge.
Future Work
Future research will focus on extending the scheme to support dynamic index updates efficiently, exploring multi-party secure computation to prevent collusion, and reducing cryptographic overhead further by integrating lightweight encryption primitives. Additionally, applying the framework to multi-modal data, such as combining text and images, and deploying in real-world cloud environments with multi-cloud security protocols, are promising directions. Enhancing the scheme's robustness against malicious attacks and exploring formal security proofs under stronger threat models will also be key areas of future investigation.
AI Executive Summary
In the era of big data and artificial intelligence, vector representations have become fundamental for tasks such as image recognition, natural language processing, and multimedia retrieval. These high-dimensional vectors encode semantic information, enabling similarity searches that underpin many modern applications. However, as data privacy concerns grow, storing and querying sensitive vectors in cloud environments presents significant challenges. Traditional nearest neighbor search algorithms rely on plaintext data, exposing sensitive information to potential breaches.
Existing privacy-preserving methods, such as encrypted index schemes and secure distance computations, often face a trade-off between security, efficiency, and accuracy. Many approaches either incur high cryptographic costs, suffer from limited scalability, or fail to support range constraints essential for real-world queries, such as filtering by price or time.
This paper introduces a novel framework called PP-RFANNS, which addresses these issues by decoupling range localization from encrypted vector search. The core idea involves constructing a local N-ary tree on the data owner side to hierarchically organize attribute ranges, enabling the user to map query ranges to a small set of tree nodes locally. The cloud server maintains encrypted HNSW sub-indices for each node, allowing it to perform targeted search over encrypted vectors. This design significantly reduces the cryptographic overhead associated with secure distance comparisons.
The scheme employs a dual encryption mechanism: DCPE (Distance-Comparison Preserving Encryption) for approximate distance filtering, and DCE (Distance-Comparison Encryption) for exact ranking. During query processing, the user generates trapdoors based on the attribute range and vector query, which the server uses to retrieve a coarse set of candidates via DCPE. The server then refines this set with DCE-based exact comparisons, ensuring high retrieval accuracy while minimizing cryptographic operations.
Extensive experiments on datasets like SIFT, GloVe, Deep1M, and ImageNet demonstrate that PP-RFANNS achieves over 100x throughput improvements at Recall@10=0.95 compared to existing secure methods. It scales effectively to millions of vectors, maintaining high accuracy and low latency across various query ranges and dataset sizes. These results validate the approach's practicality for real-world applications requiring privacy-preserving vector search.
The significance of this work lies in its innovative combination of hierarchical indexing, encryption schemes, and filtering strategies, which collectively enable secure, efficient, large-scale vector retrieval. It opens new avenues for privacy-aware AI services, such as confidential multimedia search, privacy-preserving recommendation systems, and secure multi-modal data analysis. While the scheme offers substantial advantages, future work will explore dynamic index updates, multi-party security, and further cryptographic optimizations to enhance robustness and applicability in diverse scenarios.
Deep Dive
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.