CS Paper Radar

Failure-Resilient and Verifiable Distributed Approximate Nearest-Neighbor Retrieval

Abdullah Al-Mamun

cs.DC ·submitted 2026-10-25 22:15 UTC · v1

Abstract

Distributed vector databases increasingly support security-sensitive applications, yet existing systems primarily protect index integrity or replica availability rather than the trustworthiness of retrieved results. Consequently, a compromised replica can return a plausible but manipulated result that remains cryptographically valid, while conventional replication and Byzantine defenses do not directly establish whether the retrieved results are trustworthy. We present TrustANN, a middleware layer that provides query-level trust for distributed approximate nearest-neighbor (ANN) retrieval without modifying the underlying ANN algorithm. TrustANN introduces three complementary protocols: TrustBind, which verifies retrieval trust from authenticated, consistent, and failure-domain-independent replica evidence; CoordShift, which asynchronously constructs reusable coordination epochs outside the query critical path; and AvailGuard, which performs bounded recovery when replicas are unavailable, stale, or conflicting while preserving the trust criterion. Queries are marked Trusted only when sufficient independent evidence exists for every relevant shard; otherwise, TrustANN returns Unverified. On an AWS deployment using distributed FAISS HNSW, TrustANN reduces retrieval attack success rate from 1.000 to 0.000 under the tested Byzantine-retrieval attack with two-of-three replica verification. The verification layer increases clean p95 latency by only 9.36%. Under replica crashes, TrustANN maintains trusted retrieval through 33% failures and correctly returns Unverified when sufficient evidence is unavailable.

Closest papers

Nearest neighbours by meaning across the whole index.

Authenticated Approximate Nearest Neighbor Search in Outsourced Vector Databases

cs.DB cs.CR ·2026-11-12 ·Yuanhang Zhou, Xinyi Zhang, Cheng Xu, Jianliang Xu
similarity 0.69
Abstract

Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.

0.09

HNSecW: A Logarithmic-Time MPC Protocol for Approximate Nearest Neighbor Search

cs.CR cs.DB ·2026-10-25 ·Fahong Zhang, Weijie Jin, Lixu Wang, Ning Luo, Xiao Wang +1 more
hot direction similarity 0.63
Abstract · 14 pages, 10 figures

As a core component of modern RAG systems, approximate nearest neighbor (ANN) search has been extensively studied for decades. In practice, deploying ANN often requires symmetric privacy, where the querier's query and the database owner's data must remain hidden from each other, necessitating a secure multi-party computation (MPC) solution. So far, most MPC-based ANN protocols follow a cluster-based approach: they evaluate distances for the query over a large candidate set and rely on heavyweight primitives such as distributed ORAM to hide access patterns. As a result, each search typically requires $O(\sqrt{N})$ time. We propose HNSecW, a novel MPC protocol for ANN search that achieves the $O(\log N)$ search time for the first time. We first study the single-query setting. Starting from HNSW, the state-of-the-art ANN algorithm, we redesign its control flow and data structures to achieve fully data-independent execution. To further achieve logarithmic search time, we employ offline reshuffling and partial database duplication. Furthermore, we extend our protocol to support multiple sequential queries by introducing a "double visited" caching structure that eliminates redundant cross-query memory accesses, thereby avoiding per-query online shuffling. In addition, we develop a batch-query protocol that exploits higher parallelism to reduce both round complexity and the circuit's critical path. Our experiments show that HNSecW preserves the high accuracy of plaintext HNSW ($\geq 90\%$ recall) and delivers over a $20\times$ efficiency improvement over prior work on million-scale datasets.

0.38

Semord: Learned Semantic-Preserving Placement and Low-Fanout Routing for Distributed Vector Search

cs.NI ·2026-09-22 ·Shengze Wang, Yi Liu, Yifan Hua, Xiaoxue Zhang, Chen Qian
similarity 0.62
Abstract · 19 pages, 14 figures, 4 tables. Includes appendix

Vector databases are increasingly deployed in distributed settings where different users, sites, or domains maintain vector data. Existing vector databases rely on a coordinator to record which shards store which parts of the vector space and to route each query to those shards. In a decentralized setting, peers may join, leave, or move data without a trusted node tracking every change, and outdated routing information can therefore send queries to the wrong peers or require contacting many peers, reducing vector retrieval recall and increasing network latency. We present Semord, a decentralized vector search overlay system that achieves high recall by routing each ANN query to a small set of relevant peers, without relying on a centralized coordinator. Semord addresses this problem by making semantic locality routable: 1) We propose VHash to place semantically related vectors near each other in the overlay key space while avoiding load imbalance, so that each query only needs to contact a small neighborhood of peers for distributed local ANN ranking. 2) We design VecDHT, a communication protocol that maintains decentralized routing, region metadata, churn resilience, and VHash updates under membership and workload changes. Our extensive experiments on a real testbed show that Semord improves recall by more than 15% and reduces contacted peers by over 60% compared with decentralized baselines. Semord also approaches the recall and latency of a centralized oracle baseline while reducing peak peer-local ANN index memory by more than 2X. Controlled large-scale simulations further show that Semord scales across real-world embedding workloads and remains robust under churn for scoped vector retrieval as a decentralized overlay.

0.11

Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search

cs.DB cs.IR ·2026-08-17 ·Haoyu Wang, Yandi Zhang, Jiadong Xie, Yingfan Liu, Hui Li +2 more
similarity 0.61
Abstract · According to the best of our knowledge, this work is the first attempt to study privacy-preserving range-filterd ANN search problem. This is…

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.

0.15

Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity

cs.DC cs.CRcs.IT ·2026-08-25 ·Thomas Locher, Yvonne-Anne Pignolet
published similarity 0.61
Abstract · Published at SPAA 2026 (July 6-10, 2026, London, UK)

The primary goal of a distributed storage system is to ensure that clients can both write and read data in a reliable and consistent manner, even in the presence of failures. While existing asynchronous verifiable information dispersal (AVID) protocols achieve optimal space complexity for storage and communication complexity for data retrieval in a Byzantine setting, the crucial operations of data dispersal and node recovery have received less attention. We propose an efficient AVID protocol that simultaneously guarantees low complexities for dispersal, storage, retrieval, and recovery. At the core of the proposed protocol lies a novel mechanism to encode data in a two-dimensional matrix and a bespoke dispersal algorithm. The protocol maintains an optimal communication complexity for retrieval while substantially improving upon the state of the art for recovery. Additionally, we describe how the protocol can be modified in order to reduce the space complexity and the communication complexity for dispersal, at the expense of a higher communication complexity for retrieval and recovery. As the proposed protocols strike a balance across all considered metrics, they are suitable for a broad range of real-world use cases.

0.46

Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

cs.CR cs.IRcs.LG ·2026-09-03 ·Peichun Hua, Yunming Xiao
similarity 0.60
Abstract · 23 pages, 10 tables, 6 figures

Retrieval-Augmented Generation (RAG) has made dense retrieval over large document collections a standard building block. Organizations increasingly outsource vector indexes to untrusted clouds, exposing proprietary corpora and user queries. Cryptographic protection is challenging because each query searches corpus-scale state, causing computation, correlated randomness, and communication to grow with the corpus. At million-document scale, a naive secure implementation takes minutes and about 90 GB of communication per query. Even recent optimized systems require 10--22 seconds. We propose Spruce (Scalable Private Outsourced Retrieval Using Compact Embeddings), which co-designs representations with the cryptographic protocol. Spruce learns compact binary codes that preserve candidates for full-precision reranking, replacing corpus-wide embedding scoring with efficient Hamming-distance computation under two-server multi-party computation (MPC). A corpus-calibrated fixed-radius protocol avoids multi-round candidate selection while preserving retrieval quality. Spruce also provides private cluster pruning, which trades minor quality loss for substantially less computation, and a one-core owner-operated dealer that removes cloud OT preprocessing bottlenecks. Across four corpora containing 383K--5.42M documents, Spruce preserves the original search quality with median candidate sets of only 382--1,952. At 10 Gbps inter-server bandwidth, full scans take 0.21--2.97 seconds, $4.8$--$6.7\times$ faster than the closest measured prior work. Private pruning takes 0.06--1.09 seconds, achieves $13.1$--$22.9\times$ speedups, and retains $93.9\%$--$97.3\%$ of full-float NDCG. On the largest corpus, pruning and the dealer jointly improve sustained throughput by $31.5\times$ at 1 Gbps per link.

0.36

TCDA: Tunable Coded Distributed Arrays for Data Availability Sampling

cs.DC cs.NI ·2026-10-15 ·Duc A. Tran, Dung Truong, Duy Le
similarity 0.59
Abstract

Data availability sampling (DAS) lets blockchain nodes verify a block's data availability by downloading only a few random pieces of it. Its network layer must disseminate each block in time for validators to attest (PUT), store it, and serve any piece on request (GET). A trustless DAS must sustain any number of Byzantine peers. The only known design with this guarantee, Robust Distributed Arrays (RDA), achieves it by full replication: each group of nodes responsible for part of a block stores that part in full, so a single good node per group suffices. The price to pay is a PUT load on the critical path to finality that grows with the network and cannot be tuned, hence the data may not reach validators before the attestation deadline. Coding is the natural remedy, but it was not known when a coded layer remains robust against an unbounded adversary, what it costs, or what it gains. We propose TCDA, a coded layer that is provably robust given enough good nodes, wherever they lie, with a tunable knob: how much of its assigned data each node keeps. Turning the knob trades PUT and storage costs against GET cost. It can be set per data type and adjusted as the good-node population changes. At Ethereum's parameters, our evaluation for a 32 MiB block at the recommended uplink shows that RDA misses the attestation deadline at any network size, whereas TCDA can be tuned to meet it from 868 good nodes up to the 40,000 tested, storing 1.7 to 32 times less per node than replication, at the price of 2.5 to 7.7 round-trips per sample instead of about one.

0.20

Merkle-Tree-Based Verifiable Public Data Auditing for Cloud Object Storage Using Smart Contracts

cs.CR cs.DC ·2026-10-26 ·Siri Reddy Tadi, K. Gangadhara Rao, M. Venu Gopalachari, C. Chetann Reddy, Jaswanth Bhimireddy
similarity 0.58
Abstract · 15 pages, 12 figures, 11 tables

Owners of data in cloud object storage cannot directly check whether the provider still keeps every object unchanged. Existing research mostly checks blocks inside files or relies on third-party auditors, and less attention has been given to checking each object against a public blockchain reference while measuring the cost. A full-data audit downloads every object and compares it with a saved hash list, which is slow and only as reliable as that list. We propose a public auditing system in which the SHA-256 hash of each object and its name forms a leaf of a Merkle tree, so the whole dataset is represented by one Merkle root. This root is stored in an Ethereum smart contract as a trusted public record, while the objects stay with the provider. An auditor downloads an object, rebuilds the root using a short Merkle proof and compares it with the stored root, marking the object as intact, modified or missing. In five experiments on an S3-compatible store and a local Hardhat blockchain (normal audit, single- and multiple-object tampering, deletion and scalability), the system detected 15 of 15 single modifications, 2,205 of 2,205 modified objects and 830 of 830 deleted objects with no false alarms. The proof needed only 14 hashes for 10,000 objects, so checking one object took about 10 ms and a 100-object sample about 150 ms regardless of dataset size, while a full audit of 10,000 objects (14.3 s) took about as long as downloading them (13.5 s). Storing the root cost 91,863 gas, 252 times less than storing 1,000 hashes on-chain. The system thus shows exactly which objects were modified or are missing, with its main savings coming from checking selected objects.

0.24