# SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search

arXiv: https://arxiv.org/abs/1904.02033 · HTML: https://mlsanity.com/paper/1904.02033/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2019.

## Built on by (most cited first, 12 of 12)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Reasoning over Public and Private Data in Retrieval-Based Systems](https://mlsanity.com/paper/2203.11027/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings](https://mlsanity.com/paper/2609.03376/) (2026)
- [P2RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-k Retrieval](https://mlsanity.com/paper/2603.14778/) (2026)
- [Hybrid privacy-aware semantic search: SVD-truncated document geometry and CKKS-encrypted query reranking under a restricted threat model](https://mlsanity.com/paper/2606.26373/) (2026)
- [Pointing the Way, Hiding the Destination: Practical Private Dense Retrieval at Scale](https://mlsanity.com/paper/2608.25735/) (2026)
- [Balancing Privacy and Efficiency: Music Information Retrieval via Additive Homomorphic Encryption](https://mlsanity.com/paper/2508.07044/) (2025)
- [PRAG: End-to-End Privacy-Preserving Retrieval-Augmented Generation](https://mlsanity.com/paper/2604.26525/) (2026)
- [TurboVec: A Case Study in Cost-Efficient Private Retrieval for Enterprise RAG via Codebook-Oblivious Quantization](https://mlsanity.com/paper/2607.16973/) (2026)
- [Quantization Enables Private Dense Retrieval against Malicious Service Providers](https://mlsanity.com/paper/2609.36376/) (2026)

## Abstract (arXiv)

The k-Nearest Neighbor Search (k-NNS) is the backbone of several cloud-based services such as recommender systems, face recognition, and database search on text and images. In these services, the client sends the query to the cloud server and receives the response in which case the query and response are revealed to the service provider. Such data disclosures are unacceptable in several scenarios due to the sensitivity of data and/or privacy laws. In this paper, we introduce SANNS, a system for secure k-NNS that keeps client's query and the search result confidential. SANNS comprises two protocols: an optimized linear scan and a protocol based on a novel sublinear time clustering-based algorithm. We prove the security of both protocols in the standard semi-honest model. The protocols are built upon several state-of-the-art cryptographic primitives such as lattice-based additively homomorphic encryption, distributed oblivious RAM, and garbled circuits. We provide several contributions to each of these primitives which are applicable to other secure computation tasks. Both of our protocols rely on a new circuit for the approximate top-k selection from n numbers that is built from O(n + k2) comparators. We have implemented our proposed system and performed extensive experimental results on four datasets in two different computation environments, demonstrating more than 18-31× faster response time compared to optimally implemented protocols from the prior work. Moreover, SANNS is the first work that scales to the database of 10 million entries, pushing the limit by more than two orders of magnitude.