Technical Summary: Auditing Privacy in Multi-Tenant RAG under Account Collusion

1. Problem Statement

Production Retrieval-Augmented Generation (RAG) services (e.g., Microsoft 365 Copilot, OpenAI Assistants) typically operate as multi-tenant systems where a shared infrastructure serves thousands of customer accounts. Current privacy guarantees for these systems are framed at the per-account level: each account's queries are promised to satisfy $(\epsilon_{acc}, \delta_{acc})$-differential privacy (DP) with respect to the tenant's index.

The paper identifies a critical privacy-boundary failure: this per-account framing is insufficient when an adversary controls $k$ accounts (a coalition) that coordinate to query the same tenant index. While standard DP theory suggests that $k$ independent queries might degrade privacy linearly ($k \cdot \epsilon_{acc}$) or remain flat, the authors demonstrate that for Gaussian-noised retrieval mechanisms, the joint leakage degrades at a rate of $\Theta(\sqrt{k} \cdot \epsilon_{acc})$.

This gap implies that a service advertising a safe per-account budget (e.g., $\epsilon_{acc}=1$) may inadvertently expose a significantly weaker joint guarantee (e.g., $\approx 3.2$ for $k=10$) if a coalition forms. Existing defenses modify the deployment to reduce leakage per query, but none provide a mechanism to audit the joint leakage of an unmodified deployment without revealing the underlying index or model weights.

2. Methodology

2.1 Threat Model

The authors formalize a $(\epsilon, \delta, k)$-collusion DP model. The adversary controls $k \ge 1$ accounts within a single tenant (same-tenant collusion) or across tenants (cross-tenant/external collusion, contingent on access-control failure). The adversary possesses:

• Shared posterior: A unified probabilistic belief over the target index.
• Adaptive coordination: Queries from account $a_i$ can depend on the full transcript of all other accounts up to time $t-1$.
• Rate-limit awareness: Queries are scheduled to maximize the aggregate budget while staying within individual per-account limits.
• Shared output channel: All retrieval responses are pooled before the adversary's estimator runs.

The analysis assumes independent fresh Gaussian noise per query and a deterministic embedder within the audit window.

2.2 Theoretical Analysis

The paper specializes advanced DP composition theory to the RAG setting:

• Upper Bound: By reducing $k$ coordinated accounts to a single adaptive analyst with a budget of $kn$ queries, the authors apply the Advanced Composition Theorem. For Gaussian-noised score release, they prove the joint privacy parameter $\epsilon_k$ scales as:
  $$\epsilon_k = \Theta\left(\sqrt{k} \cdot \epsilon_{acc}\right)$$
  This is strictly worse than the advertised per-account budget but better than the naive linear group-privacy bound.
• Lower Bound: The authors construct a specific attack (a probe query against neighboring indices differing by one document) where a coalition of $k$ accounts achieves a membership inference advantage (MIA) of $\Omega(\sqrt{k} \cdot \epsilon_{acc})$.
• Rényi DP (RDP): The analysis is refined using RDP and the moments accountant to provide tighter numerical bounds for practical audit reporting.

2.3 Audit Protocol

To make this gap verifiable, the paper designs a four-phase audit protocol that operates on unmodified RAG deployments without requiring index disclosure:

1. Commitment: The provider commits to the embedder, index content (via vector commitments), noise seed, and policy parameters (including a declared coalition cap $k_{max}$) using cryptographic hashes and Merkle trees.
2. Per-Query Attestation: For every query, the provider generates a Zero-Knowledge (ZK) proof attesting that:
   • The embedding was computed using the committed embedder.
   • Gaussian noise was derived from the committed seed.
   • The Top-K selection was performed on the noisy scores (noise-then-select).
   • The retrieval was confined to the correct tenant index.
3. Coalition-Size Estimation: The provider submits an estimate of the coalition size ($\hat{k}$) based on query correlation (clustering similar queries in the public ledger), accompanied by a ZK proof.
4. Verification: A third-party verifier checks the proofs and the ledger consistency. If the estimated coalition size is within the policy cap ($k_{max}$), the verifier issues a quantitative verdict: (PASS, $\epsilon_{audit}$), where $\epsilon_{audit}$ is the calculated joint leakage bound.

3. Key Contributions

1. Threat Model Identification: The paper defines same-index multi-account collusion as a structural failure of per-account DP guarantees in RAG, establishing the $\Theta(\sqrt{k})$ degradation rate for Gaussian-noised retrieval.
2. Falsifiable Empirical Predictions: The authors derive a specific prediction for the Membership Inference Attack (MIA) Area Under the Curve (AUC): $AUC_k = \frac{1}{2} + \Theta(\sqrt{k} \cdot \epsilon_{acc})$. They commit to two falsification gates (slope and tightness) to validate the theory.
3. Verifier-Runnable Audit Protocol: The first protocol to audit joint leakage in unmodified RAG deployments. It uses a combination of generic cryptographic primitives (Merkle ledgers, ZK proofs) and RAG-specific primitives (embedder commitment, noise-then-select attestation) to issue a quantitative $(PASS, \epsilon_{audit})$ verdict without exposing the index or model weights.
4. Numerical Privacy Tracking: The integration of RDP and the moments accountant allows for exact numerical evaluation of privacy loss, providing tighter bounds than closed-form approximations for moderate coalition sizes.

4. Experimental Results

The authors validated their theoretical predictions using a synthetic multi-tenant FAISS-based harness and a trained embedder (BAAI/bge-small-en-v1.5).

• Scaling Validation: Experiments with coalition sizes $k \in \{1, 2, 5, 10, 20\}$ confirmed the predicted $\sqrt{k}$ scaling. For example, at $\epsilon_{acc}=4$, the empirical MIA advantage grew from 0.070 ($k=1$) to 0.281 ($k=20$), closely matching the predicted growth factor of $\sqrt{20} \approx 4.5$.
• Top-K Post-Processing: The $\sqrt{k}$ trend was observed to persist even when the output was restricted to a binary "Top-K hit" indicator, though the absolute advantage was reduced by a constant factor (approx. 30% lower than the raw score attack).
• Robustness Checks:
  • Alternative Adversaries: Variants using Bayes log-likelihood ratios or diversified multi-target splitting did not exceed the baseline $\sqrt{k}$ rate; diversification actually degraded the advantage.
  • Embedder Transfer: The rate held for a trained 384-dimensional embedder, with the advantage scaling linearly with the realized score gap ($\Delta$).
  • External vs. Same-Tenant: Under the assumption of access-control failure (M4), external attackers achieved leakage rates statistically indistinguishable from same-tenant coalitions.
• Production Scale: Tests on a $10^6$-document HNSW index confirmed that while user-observable Top-K hits offer near-zero leakage at scale, the auditor-observable pooled noisy scores (accessible via the audit protocol) still exhibit the $\sqrt{k}$ leakage trend.

5. Significance and Claims

The paper positions itself as a technical foundation rather than a deployed specification. Its primary significance lies in:

• Exposing Structural Vulnerability: It argues that multi-account abuse (e.g., sock puppets) is not just a fraud issue but a fundamental privacy boundary failure that current per-account DP guarantees do not cover.
• Enabling Third-Party Audits: The protocol provides a mechanism for regulators and third parties to verify privacy claims (e.g., under the EU AI Act or DSA) without requiring the provider to disclose proprietary data or models.
• Operationalizing $\epsilon_{audit}$: It proposes shifting the regulatory disclosure unit from the per-account budget ($\epsilon_{acc}$) to the joint audit bound ($\epsilon_{audit}$), which reflects the reality of coordinated attacks.

The authors explicitly scope out generation-channel privacy (LLM output conditioned on selected documents) and embedding inversion attacks, treating them as separate audit predicates. They acknowledge that the protocol's effectiveness relies on the provider declaring a meaningful coalition cap ($k_{max}$) and that the coalition-size estimator can be evaded by adversaries who deliberately diversify their queries. The paper concludes that while the gap is structural and requires architectural changes to fully close, the proposed audit protocol offers a verifiable, immediate step toward transparency in production RAG services.