Compass

Encrypted Semantic Search with High Accuracy

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.


Contributors

Jinhao Zhu, Liana Patel, Matei Zaharia, Raluca Ada Popa