Auditing Privacy in Multi-Tenant RAG under Account Collusion

Abstract

Multi-tenant RAG services often treat the account as the privacy boundary: each account receives an $({\epsilon }_{\text{acc}},\hat{I}{´}_{\text{acc}})$-DP retrieval guarantee against the tenant index. We show that this framing understates leakage under same-index account collusion. For Gaussian noise-then-select retrieval, $k$ coordinated same-tenant accounts compose to joint leakage $\hat{I}˜(\sqrt{k}{\epsilon }_{\text{acc}})$, not ${\epsilon }_{\text{acc}}$; we give a matching membership-inference attack and validate the predicted $\sqrt{k}$ AUC trend in scalar, top-$K$, trained-embedder, and production-scale HNSW settings. We then give a verifier-runnable audit protocol that attests noise-then-select retrieval and reports $(\text{PASS},{\epsilon }_{\text{audit}})$ for coalitions up to a declared cap $k_{\max }$, without disclosing the index or changing the retrieval decision rule. The claim is retrieval-channel only: generation-channel leakage and adversarially robust coalition-size estimation are complementary audit predicates.