BiSON — secure semantic search over a billion encrypted vectors

Microsoft Research has unveiled BiSON (Billion-Scale Oblivious Nearest-Neighbor Search) — a system for quickly searching for similar objects in encrypted vector databases. According to the researchers, it can operate on a database of a billion vectors, while keeping response times in the millisecond range. The paper was presented at IEEE EuroS&P 2026.

The development addresses one of the key challenges facing modern AI systems: how to perform semantic searches in the cloud without revealing the contents of the database, the search query, or the algorithm's data access patterns to the provider.

Why conventional encryption is not enough

Semantic search operates on vector representations. Documents, images, and other objects are converted into sets of numbers that describe their meaning. The user's query is also converted into a vector, after which the system searches for the most similar objects.

This approach is used in vector databases, recommendation systems, and RAG (retrieval-augmented generation). For large datasets, approximate nearest-neighbor (ANN) search is typically used to avoid comparing the query with every object individually.

However, if such a database is hosted in the cloud, basic encryption is not enough. The server can still observe which areas of storage the algorithm queries, and analyze recurring access patterns. BiSON is designed to conceal this information as well.

How BiSON works

The system is built on Oblivious RAM (ORAM) — a technology that conceals a client's actual data accesses. The server performs read and write operations but cannot determine which specific data the client is accessing at a given moment. However, ORAM typically requires a large number of additional operations and substantial network traffic, making it too costly to apply to vector databases containing hundreds of millions or billions of objects.

In BiSON, Microsoft developed an ORAM variant designed for disk storage. This means the protected index does not need to reside entirely in memory, allowing the system to scale to billion-record datasets. The system is based on DiskANN — a nearest-vector search algorithm developed by Microsoft and optimized for storing large indexes on SSDs. In BiSON, this index is transformed into a protected ORAM structure.

According to Microsoft, BiSON maintains search quality close to that of modern unprotected ANN systems, while a query against a database of one billion vectors can be completed in milliseconds.

Compared with the previous private search system, Compass, the developers report: – a reduction in the volume of transmitted data by up to 28×; – a reduction in end-to-end query latency by up to 23.5×; – an increase in the supported database size of approximately two orders of magnitude.

Existing approaches already enabled private nearest-neighbor searches, but they generally performed poorly at the scale typical of large cloud and AI services.

Where it can be used

BiSON is designed for scenarios in which an organization wants to use cloud computing without revealing either its vector database or its search queries to the provider.

This could be useful for: – enterprise search across internal documents; – RAG systems working with confidential information; – medical and financial applications; – personal AI assistants; – searches across sensitive user data.

Tool: https://github.com/r-dott/bison