BiSON: Billion-Scale Oblivious Nearest-NeighborSearch in Milliseconds

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 BiSON , the first secure nearest-neighbor search protocol capable of supporting billion-scale encrypted vector databases. Even at this scale, 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, BiSON
reduces communication up to 28×, improves end-to-end latency by up to 23.5×, and scales to datasets that are two orders of magnitude larger.

A central contribution of 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 BiSON the first practical and scalable solution for secure semantic search at cloud scale.