New method boosts privacy safe nearest neighbor search speed
O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search
Cryptography and SecurityDatabases
Summary
Finding similar items quickly while keeping search queries private is important in fields like medicine and finance. The authors present O2N2, a new method that improves the speed of privacy-protecting searches on large datasets without revealing sensitive query information. O2N2 uses clever tree data structures and special memory techniques to hide access patterns that could leak information. Their experiments show much faster search speeds compared to previous private search methods, even on very large datasets.
What this means in practice
- •For medical data teams: Enable fast patient data similarity searches while keeping sensitive queries confidential using a privacy-aware data structure and memory access method.
- •For financial risk analysts: Support secure credit scoring by performing approximate nearest neighbor searches that hide query details to protect client privacy.
Authors
Zhechen Li, Zimai Guo, Mingxun Zhou, Chang Shi, Cheng Hong
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.