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 present Compass, a semantic search system for encrypted data that achieves high accuracy, matching state-of-the-art plaintext search quality, while ensuring the privacy of data, queries, and results, even if the server is compromised. Compass contributes a novel way to traverse a state-of-the-art graph-based semantic search index and a white-box co-design with Oblivious RAM, a cryptographic primitive that hides access patterns, to enable efficient search over encrypted embeddings. With our techniques, Directional Neighbor Filtering, Speculative Neighbor Prefetch, and Graph-Traversal Tailored ORAM, Compass achieves user-perceived latencies within or around a second and is orders of magnitude faster than baselines under various network conditions.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. OSDI'25
- Keywords
- Encrypted SearchORAMSemantic Search
- Contact author(s)
-
jinhao zhu @ berkeley edu
lianapat @ stanford edu
matei @ berkeley edu
raluca popa @ berkeley edu - History
- 2025-06-09: last of 3 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}
}
