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.<\/p>\n\n\n\n
<\/p>\n\n\n\n
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\u00d7, improves end-to-end latency by up to 23.5\u00d7, and scales to datasets that are two orders of magnitude larger.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":[{"type":"text","value":"Sankha Das","user_id":0},{"type":"text","value":"Rohan Ravi","user_id":0},{"type":"user_nicename","value":"Nishanth Chandran","user_id":"33084"},{"type":"user_nicename","value":"Divya Gupta","user_id":"37766"}],"msr_publishername":"IEEE Xplore","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"IEEE","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"","msr_doi":"","msr_arxiv_id":"","msr_mag_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_release_tracker_id":"","msr_highlight_type":"","msr_date_display_format":"","msr_main_download_label":"","msr_external_link_label":"","msr_doi_label":"","msr_published_date":"2026-07","msr_startdate":"","msr_presentation_date":"","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"https:\/\/eurosp2026.ieee-security.org\/","msr_journal_url":"","msr_year":2026,"msr_month":7,"msr_day":0,"msr_microsoftintellectualproperty":true,"msr_pub_id":"","msr_publication_uploader":[{"type":"url","title":"https:\/\/eprint.iacr.org\/2026\/1343.pdf","label_id":252679,"id":false,"viewUrl":false}],"msr_related_uploader":[],"msr_original_fields_of_study":[],"msr_s2_paper_id":"","msr_s2_pdf_url":"","msr_citation_count_updated":"","msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13558],"msr-publication-type":[193716],"msr-publisher":[],"msr-publication-cta":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[269873,254197,251407],"msr-conference":[270679],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-1190566","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us","msr-field-of-study-ai-security","msr-field-of-study-cryptography","msr-field-of-study-security"],"msr_publishername":"IEEE Xplore","msr_edition":"","msr_affiliation":"","msr_published_date":"2026-07","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"IEEE","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"https:\/\/eprint.iacr.org\/2026\/1343.pdf","label_id":252679,"id":false,"viewUrl":false}],"msr_related_uploader":[],"msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Sankha Das","user_id":0,"rest_url":false},{"type":"text","value":"Rohan Ravi","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Nishanth Chandran","user_id":33084,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Nishanth Chandran"},{"type":"user_nicename","value":"Divya Gupta","user_id":37766,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Divya Gupta"}],"msr_impact_theme":[],"msr_research_lab":[199562],"msr_event":[],"msr_group":[],"msr_project":[507611],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":507611,"post_title":"EzPC (Easy Secure Multi-party Computation)","post_name":"ezpc-easy-secure-multi-party-computation","post_type":"msr-project","post_date":"2018-10-10 01:30:32","post_modified":"2025-01-15 20:59:33","post_status":"publish","permalink":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/project\/ezpc-easy-secure-multi-party-computation\/","post_excerpt":"Consider the following scenario: Two hospitals, each having sensitive patient data, must compute statistical information about their joint data. Or, one of the hospitals has a pre-trained ML model based on sensitive patient data and another hospital either wants to learn inference results for its sensitive patient data or the accuracy of the model for its sensitive patient data. In all cases, privacy regulations forbid them from sharing the data and\/or the model in the…","_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/507611"}]}}]},"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1190566","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1190566\/revisions"}],"predecessor-version":[{"id":1190568,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1190566\/revisions\/1190568"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=1190566"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=1190566"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=1190566"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=1190566"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=1190566"},{"taxonomy":"msr-publication-cta","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-cta?post=1190566"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=1190566"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=1190566"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=1190566"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=1190566"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=1190566"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=1190566"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=1190566"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=1190566"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}