Metraipolis › archive › dc_f63ea24610b5

O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search — arXiv:2611.03415

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03415
License (as archived)
CC0-1.0
Archived
2026-11-03T11:17:21.840Z
SHA-256 of the archived text
f98df3361200dcb31a698e3c065b751d39938f9092e4d8163efafe1fb56aedce
Stable URL of this page
https://metraipolis.com/documento/dc_f63ea24610b5

How to cite

O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search — arXiv:2611.03415 — arXiv (en), https://arxiv.org/abs/2611.03415 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f63ea24610b5 (Metraipolis archive dc_f63ea24610b5, sha256 f98df3361200dcb31a698e3c065b751d39938f9092e4d8163efafe1fb56aedce)
BibTeX
@misc{dcf63ea24610b5,
  title = {O2N2: Efficient Doubly Oblivious Approximate Nearest Neighbor Search — arXiv:2611.03415},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03415},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f63ea24610b5; sha256 f98df3361200dcb31a698e3c065b751d39938f9092e4d8163efafe1fb56aedce},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03415. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Cryptography and Security (cs.CR) ; Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2611.03415 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:07.238Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).