Paper 2024/1255
Compass: Encrypted Semantic Search with High Accuracy
, University of California, Berkeley, Stanford University, University of California, Berkeley, University of California, BerkeleyAbstract
We introduce Compass, a semantic search system over encrypted data that offers high accuracy, comparable to state-of-the-art plaintext search algorithms while protecting data, queries and search results from a fully compromised server. Additionally, Compass enables privacy-preserving RAG where both the RAG database and the query are protected. Compass contributes a novel way to traverse the Hierarchical Navigable Small Worlds (HNSW) graph, a top-performing nearest neighbor search index, over Oblivious RAM, a cryptographic primitive with strong security guarantees. Our techniques, Directional Neighbor Filtering, Speculative Greedy Search, and HNSW-tailored Path ORAM ensure that Compass achieves user-perceived latencies of a few seconds and is orders of magnitude faster than baselines for encrypted embeddings search.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Encrypted SearchORAM
- Contact author(s)
-
jinhao zhu @ berkeley edu
lianapat @ stanford edu
matei @ berkeley edu
raluca popa @ berkeley edu - History
- 2024-09-05: last of 2 revisions
- 2024-08-08: received
- See all versions
- Short URL
- https://ia.cr/2024/1255
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1255,
author = {Jinhao Zhu and Liana Patel and Matei Zaharia and Raluca Ada Popa},
title = {Compass: Encrypted Semantic Search with High Accuracy},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1255},
year = {2024},
url = {https://eprint.iacr.org/2024/1255}
}
