Paper 2026/923

Practical and Verifiable Encrypted Vector Search for Retrieval-Augmented Generation

Abstract

Retrieval-augmented generation (RAG) systems critically depend on a vector-retrieval stage that selects relevant documents from a large embedding database. When this stage is outsourced to a RAG-as-a-Service provider, query embeddings can reveal sensitive user intent, the outsourced index can leak proprietary corpus information, and a malicious provider can silently manipulate retrieval results. This motivates privacy-preserving verifiable retrieval. The client must be able to confirm that the returned top-$k$ identifiers were produced by faithfully executing an agreed approximate nearest neighbor (ANN) algorithm on a committed encrypted index, while leaking no non-public database information beyond the functional baseline induced by the returned top-$k$ identifiers. We present VeriANN, the \emph{first} encrypted ANN retrieval framework, to our knowledge, that simultaneously achieves \emph{query privacy}, \emph{database confidentiality}, and \emph{verifiability of retrieval results} against malicious servers, under a two-server non-colluding trust model. VeriANN couples distributed-point-function--based PIR over locality-sensitive hashing indexes with authenticated garbled circuits, so that the entire top-$k$ pipeline---bucket decryption, Merkle-root reconstruction, frequency counting, and top-$k$ selection---is executed obliviously and with end-to-end integrity. Making this integration practical requires three new techniques: (i) a sort-based hierarchical oblivious frequency-counting algorithm that enables a distance-free post-processing stage, reducing top-$k$ aggregation from quadratic to quasi-linear complexity; (ii) an end-to-end authenticated verification design that binds the full retrieval pipeline against selective-failure attacks while reducing client-side verification to a single hash check against the published Merkle root; and (iii) a modular state-pool design with an authenticated state-transfer mechanism that dynamically composes precomputed garbled states across query parameters while preserving cross-circuit verifiability. On million-scale corpora, VeriANN achieves second-scale end-to-end latency with KB-scale client-to-server communication, while adding minimal online overhead over a non-verifiable baseline.