CS Paper Radar

O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search

Zhechen Li, Zimai Guo, Mingxun Zhou, Chang Shi, Cheng Hong

cs.CR cs.DB ·submitted 2026-11-02 16:38 UTC · v1

Abstract

Privacy-preserving approximate nearest neighbor (ANN) search allows clients to search from an untrusted server without revealing sensitive queries, and is useful in scenarios like medical diagnostics and credit scoring. Among the various privacy-preserving primitives, trusted execution environments (TEEs) have much lower overhead than heavy cryptographic ones, yet they leak memory access patterns, enabling adversaries to infer query contents. Oblivious RAM (ORAM) can be used to hide those access patterns at $\mathrm{O}(\log N)$ asymptotic cost, but existing high-performance ANN search algorithms (e.g., IVF or HNSW) exhibit complex, data-dependent access patterns that are unfriendly for ORAM. Furthermore, standard ORAM constructions typically assume there exists a small amount of trusted storage, which weakens the security guarantees and is not always feasible. Solutions that eliminate such trusted storage (known as {\em double obliviousness}) typically degrade performance further to $\mathrm{O}(\log^2 N)$. We introduce O2N2, a doubly oblivious ANN framework built around single-path search in randomly rotated $k$-d tree forests. A pointer-based Circuit ORAM stores the search structure, with separate storage for compact internal nodes and vector-bearing leaves. Each visited leaf is processed by an oblivious selection network, and fixed-schedule duplicate removal and selection combine the local results into the final top-$k$. We evaluate O2N2 on real-world datasets and further test its scalability on 100 million vectors. For 10-NN and 100-NN search at the specified high-recall targets, it achieves a $9.8$--$125.9\times$ speedup over the fastest doubly oblivious baselines.

Closest papers

Nearest neighbours by meaning across the whole index.

Hoss: Fast Oblivious Semantic Search with Heterogeneous GPU-CPU-TEE Architecture

cs.CR ·2026-09-03 ·Jianzhang Du, Weijie Huang, Chenghong Wang, Nicolas Tsagareli, Yukui Luo +2 more
benchmark similarity 0.72
Abstract

Semantic search is widely deployed in modern AI systems, but protecting both data contents and access patterns remains challenging. The current state-of-the-art system, Compass, achieves oblivious semantic search by building an optimized ORAM over HNSW graphs. However, even with aggressive optimizations, it still incurs large overheads. Closing this performance gap is fundamentally difficult: Compass has already removed most cryptographic overheads, leaving ORAM accesses as the dominant cost, which are constrained by well-known Omega(log N) bandwidth lower bounds. Our key insight is that traditional ORAM overhead stems from the assumption of limited private memory, whereas modern GPU TEEs provide large private memory (Pmem) that blinds internal access patterns (Hunt et al., NSDI '23). This shift opens a new design space. We therefore propose Hoss, a first-of-its-kind oblivious semantic search system with a heterogeneous CPU-GPU TEE architecture that supports fast, scalable search with low cost of ownership. In Hoss, the GPU TEE's large Pmem hosts the hot-path HNSW traversal, while the lower layers of the graph, if they exceed GPU capacity, are offloaded to CPU TEEs. The system invokes oblivious primitives only when accessing these lower layers. The availability of large Pmem also enables new optimization opportunities. For example, Hoss features a host-access ORAM mechanism that goes beyond traditional performance constraints and incorporates several data-dependent optimizations that are not possible in prior designs. We implement a prototype of Hoss and benchmark it against Compass. Our results show that Hoss achieves up to 67x speedup while maintaining high recall, with larger gains at scale.

0.17

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.71
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

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.64
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

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.59
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

NOMAI: Scalable Federated Learning with Private Weights

cs.CR ·2026-10-15 ·Yiyi Sun, Mushtari Sadia, Amrita Roy Chowdhury
similarity 0.59
Abstract

The twin goals of privacy-preserving federated learning (FL) -- harnessing distributed data while protecting the parties who contribute it -- demands three properties: model privacy, data privacy, and integrity. Achieving all three in a realistic deployment -- with a single coordinator and millions of users -- remains an open challenge that prior work has yet to fully resolve. We present NOMAI, the first scalable MPC-based FL system to provide all three guarantees simultaneously. NOMAI operates under an honest-majority assumption in the semi-honest model, with an extension to the malicious-with-abort setting. At its core, NOMAI combines a multi-committee MPC architecture with packed Shamir secret sharing, enabling SIMD-style secure computation that scales far beyond what monolithic n-party protocols can support. We further introduce ML-aware optimizations and new cryptographic primitives that substantially reduce per-user overhead. Our evaluation shows NOMAI is practically deployable at unprecedented scale: it reduces per-user computation to just <350 ms (semi-honest) and <700 ms (malicious) for per iteration of training MNIST, achieving three orders-of-magnitude improvements over prior work while seamlessly supporting populations of over 106 users. This demonstrates, for the first time, that MPC-based FL can meet the scale demands of real-world systems without compromising on privacy or integrity.

0.13

Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale

cs.CR cs.AIcs.IRcs.LG ·2026-08-26 ·Peichun Hua, Danyang Chen, Junan Zhang, Haifeng Sun, Jingyu Wang +3 more
similarity 0.59
Abstract · 31 pages, 9 figures, 16 tables

Hosted retrieval-augmented generation (RAG) and semantic search allow users to query valuable provider-held corpora, raising two competing demands: to hide each query and chosen result, yet reveal only the documents that the user is authorized to receive. Existing cryptographic approaches either make this costly by processing the entire corpus for every query, or sacrifice quality for efficiency by scanning a few clusters. We repurpose learned deep hashing as a private filter: a randomized binary code points the provider to a short candidate list, while encrypted reranking and oblivious key transfer protect the precise query and final selection. This shortlist short-circuits full-corpus cryptographic search without sacrificing retrieval quality: with 200-500 candidates, it closely matches full-corpus retrieval across five zero-shot corpora spanning 25K to 5.4M documents. On the full 2.68M-passage NQ corpus over a 10-Gbps link, our protocol only adds 0.73 seconds, or 10 percent, to a 128-token Qwen3-32B RAG pipeline. The released code satisfies directional metric differential privacy (DP) and substantially reduces embedding-inversion and property-inference leakage, demonstrating that a carefully learned shortlist can make private dense retrieval both accurate and practical.

0.46

Communication-Oblivious Permutation and Sorting

cs.DS ·2026-10-29 ·Qi Dong, Yilei Wang, Ke Yi
theory similarity 0.59
Abstract

With the help of secure hardware such as trusted execution environments (TEEs), private data can be uploaded and computed in untrusted cloud clusters, so that an adversary controlling the cloud can only see the data in encrypted form. However, the communication pattern between the processors may still reveal sensitive information about the data, so it is important to develop parallel algorithms in the BSP model whose communication pattern is independent of the input data, a property known as \textit{communication obliviousness}. In this paper, we study such algorithms for three fundamental problems: permutation, sorting, and 0-1 sorting. For the first two problems, we prove a tight (up to lower-order terms) communication complexity of $(2-2/p)n\pm o(n)$. Here, $p$ is the number of processors and $n$ is the input size, assuming $2\le p$ and $p=o(n^{1/3})$. Our lower bound holds regardless of the number of rounds and local memory size, while for balanced permutation and sorting the upper bound is achieved in a constant number of rounds with load at most $n/p+o(n/p)$. For 0-1 sorting, we also derive a tight communication complexity of $C_{\mathrm{cut}}(p) \cdot n \pm o(n)$, where $C_{\mathrm{cut}}(p)$ is the optimal value of a linear program parameterized by $p$. Although there appears to be no closed-form for $C_{\mathrm{cut}}(p)$, we show that it is strictly smaller than $2-2/p$ for all $p\ge 3$, thus separating 0-1 sorting from general sorting in terms of their communication complexity.

0.28

Doubly-Efficient Private Information Retrieval from Modular Forms

cs.CR math.NT ·2026-11-09 ·Alexandra Henzinger, Seyoon Ragavan
similarity 0.59
Abstract

We present new information-theoretic protocols for $s$-server, doubly-efficient private information retrieval (PIR) in sublinear server time and one extra bit of space on the servers, for every constant $s \geq 2$. On an $n$-bit database, each of the $s$ PIR servers first builds and stores a preprocessing data structure consisting of $n+1$ bits (which is unique to each server, and after which the server may discard the original database). Then, each server answers a PIR query in time $T_s(n)$, by reading at most $T_s$ bits of its data structure and sending them to the user. In the two server setting ($s=2$), our PIR protocols achieve $T_2 = n^{0.82}$, matching the server time of the state-of-the-art schemes of Henzinger and Ragavan (EUROCRYPT 2026) while shrinking their storage from $O(n\sqrt{\log n})$ to $n+1$ bits. With $s \geq 3$ servers, our PIR protocols retain the $n+1$ bits of storage and additionally improve on the server time of all prior information-theoretic $s$-server schemes with $n^{1+o(1)}$ storage: for example, achieving $T_3 = n^{0.74}$ and $T_{10} = n^{0.61}$ (previously $n^{0.79}$ and $n^{0.75}$). Asymptotically, as the server count $s$ grows, we shrink the number of servers required to achieve a given server-work exponent from $s^{3.9}$ to $s$. Our results draw inspiration from matching-vector techniques (Efremenko, STOC 2009), which we generalize to handle degree-two computations in the exponent. Using this generalization, we build doubly-efficient PIR from the new intermediate abstraction of Fourier-sparse cone-delta functions. Then, we construct such Fourier-sparse cone-delta functions via a connection to modular forms and complex analysis: if a Fourier-sparse cone-delta function does not exist, then there exists a modular form which has too many roots, contradicting the valence formula.

0.25