Paper 2026/1343

BiSON: Billion-Scale Oblivious Nearest-Neighbor Search in Milliseconds

Abstract

Semantic search over vector databases is a fundamental problem in both theory and practice, with large-scale systems relying on approximate nearest-neighbor (ANN) algorithms to retrieve semantically similar results efficiently. Achieving this capability securely while keeping both data and queries hidden remains a major challenge. Existing secure semantic search systems incur high latency and fail to scale to realistic database sizes. We present $\mathsf{BiSON}$, the first secure nearest-neighbor search protocol capable of supporting billion-scale encrypted vector databases. Even at this scale, $\mathsf{BiSON}$ answers queries in mere milliseconds and maintains search accuracy comparable to state-of-the-art insecure ANN algorithms, demonstrating that secure semantic search can be both private and truly high-performance. Compared to Compass, the prior state-of-the-art system, $\mathsf{BiSON}$ reduces communication up to $28\times$, improves end-to-end latency by up to $23.5\times$, and scales to datasets that are two orders of magnitude larger. A central contribution of $\mathsf{BiSON}$ is a new disk-compatible Oblivious RAM (ORAM) architecture that enables seamless scaling to billion-point datasets without compromising latency or privacy. Together, these innovations make $\mathsf{BiSON}$ the first practical and scalable solution for secure semantic search at cloud scale.