Holo nn enables fast private nearest neighbor search with compressive sensing
Holo-NN: Holographic Nearest Neighbor Search via Compressive Sensing
Cryptography and SecurityDatabasesInformation RetrievalMachine Learning
Summary
Finding similar items quickly while keeping data private is hard because usual methods rely on complex steps that don't work well with encrypted data. The authors introduce Holo-NN, which packs the entire database into a special matrix using mathematics that keeps nearby items easy to find. When searching, it needs just one simple mathematical step on encrypted data, making the process faster, private, and scalable. This new way avoids back-and-forth communication and heavy computations, running efficiently on common computer hardware.
What this means in practice
- •For cloud service operators: Enable private search on encrypted user data using efficient single-step computations without needing client-side indexes or multiple communication rounds.
- •For image retrieval engineers: Accelerate privacy-aware image similarity searches by compressing large image databases into a compact representation that supports encrypted queries.
Authors
Bryant Gipson
Abstract
In the age of AI, privacy-preserving approximate nearest neighbor (ANN) search over high-dimensional embeddings has emerged as a critical yet frustratingly challenging domain, dominated by tradeoffs between speed, privacy, and accuracy. Traditional tree and graph-based indexing structures (e.g., HNSW, ScaNN) rely fundamentally on non-linear operations that are computationally intractable under Fully Homomorphic Encryption (FHE) or blind server-side constraints. In this paper, we introduce Holo-NN (Holographic Nearest Neighbor Search), an algebraic framework that replaces data-dependent branching with a single linear projection. Our key observation is that while distances across a database are dense, neighborhood membership is inherently sparse: only a handful of points ever lie close to a query. By pairing locality-preserving feature transforms with Compressive Sensing, Holo-NN folds the entire database offline into a compact holographic sensing matrix. At query time, encrypted search reduces to a single, non-interactive matrix-vector multiplication---requiring no FHE bootstrapping, no multi-round interaction, and no client-side index state. This turns private retrieval into an embarrassingly parallel, accuracy-tunable computation that runs out of the box on both CPUs and GPUs, scaling efficiently to production databases. We offer a comparison against other state-of-the-art Private ANN algorithms to help situate the method in the broader context of production-grade private retrieval.