Technical Summary: SHARD – Cell-Keyed Residual Splitting for Alignment-Resistant Private Dense Retrieval

1. Problem Statement

Dense embeddings are the foundation of modern semantic search and Retrieval-Augmented Generation (RAG). However, a leaked vector store effectively compromises the underlying text, as demonstrated by recent attacks including few-shot alignment, zero-shot inversion, and unsupervised cross-space translation. These attacks exploit a fundamental weakness in existing lightweight defenses: the protected vector store is a single global geometry.

Current defenses often rely on a "global-linear" approach: compressing embeddings via SVD truncation, applying a single secret orthogonal rotation, and using Product Quantization (PQ) for indexing. The paper argues that this approach is fragile because any single global geometry can be aligned to a known reference space. Once an attacker recovers the secret rotation (using approximately $k = d/2$ known plaintext pairs via Orthogonal Procrustes), the protection collapses, allowing for near-exact text recovery. Furthermore, standard defenses face a trade-off: Differential Privacy (DP) destroys ranking utility before providing meaningful privacy, while Fully Homomorphic Encryption (FHE) is too computationally expensive for large-scale top-$k$ search.

2. Methodology: The Shard Construction

The paper introduces Shard, a retrieval-preserving embedding transform designed to eliminate the "weak axis" of global alignment rather than masking distortion. Shard splits the embedding space into two components and applies distinct protections to each:

1. Public Prefix ($u$): The embedding is centered and rotated. The top $d_{pub}$ principal components (high-variance directions) form a short public prefix. This is used for coarse Stage-1 retrieval (ANN) via a public Product Quantization index.
2. Private Residual ($r$): The remaining dimensions ($d_{priv} = d - d_{pub}$) form the private residual.
   • Cell-Keyed Splitting: The residual space is partitioned into $C$ coarse cells (defined by the public prefix $u$).
   • Local Keys: Each cell $c$ is assigned a unique secret orthogonal key $H_c$ (a product of Householder reflections).
   • Storage: The server stores the prefix $u_i$ and the keyed residual shard $z_i = H_{c(i)} r_i$.
   • Query Processing:
     • Stage 1: The client uses the public prefix $u_q$ to retrieve a short-list of candidates locally.
     • Stage 2 (Reranking): For each candidate, the client encrypts the query residual $r_q$ under CKKS (homomorphic encryption) as $H_{c(i)} r_q$. The server computes the inner product $\langle H_{c(i)} r_q, z_i \rangle$ in ciphertext-plaintext mode.
     • Exact Recovery: Because $H_c$ is orthogonal, the keys cancel out: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$. The server returns encrypted scores that decrypt to the exact inner product of the original residuals.

The parameter $C$ interpolates between the global baseline ($C=1$, one global key) and per-document micro-keys ($C=N$, one key per document).

3. Key Contributions

The paper makes the following specific contributions relative to prior work (specifically the authors' previous global-linear hybrid system):

• Cell-Keyed Residual Splitting: A construction that replaces a single global geometry with $C$ locally keyed subspaces, preventing a single alignment attack from recovering the entire store.
• Full-Dimensional Reranking: Unlike SVD-truncation baselines that rerank in a reduced space, Shard reranks in the full-dimensional space (prefix + residual), recovering raw retrieval quality lost by truncation.
• Scalable Alignment Resistance: The paper establishes a scaling law where the cost of a diffuse known-plaintext alignment attack grows by a factor of $\approx C$. Recovering the native frame requires $O(C \cdot d_{priv})$ anchors rather than $O(d)$.
• Reduced Public Leakage: By exposing only a short prefix ($d_{pub} \ll d$) instead of half the space, the public index leaks significantly less neighbor structure.
• Attack-Aware Evaluation: The paper evaluates Shard against stronger attacker families (learned-linear, non-linear MLP, and unsupervised) and compares it against distortion-aware defenses (DP noise), demonstrating that keying provides resistance where noise fails.

4. Experimental Results

Experiments were conducted on cached embeddings from five encoders (including multilingual-E5 and BGE-M3) across BEIR, MIRACL, and a 1-million-document Russian Wikipedia corpus.

• Utility (nDCG@10): Shard recovers the raw-space ranking ceiling. On BEIR tasks where SVD truncation caused a 2–8 point drop in nDCG@10, Shard matched the raw baseline (e.g., 0.638 vs. 0.637 raw) while exposing a public channel only 1/4 to 1/2 as wide.
• Alignment Resistance:
  • Global Baseline: Recovered with ~200 anchors (for $d=384$).
  • Shard ($C=64$): Required ~25,600 anchors.
  • Shard ($C=256$): Required ~102,400 anchors (median).
  • Attacker Robustness: Learned-linear, non-linear MLP, and unsupervised attackers performed no better than the standard Orthogonal Procrustes attack; none surpassed the $d_{priv}$ anchor threshold for a single cell.
• Public Index Leakage: The public prefix revealed significantly less neighbor structure than the baseline. For a $d/4$ prefix, NN-overlap@10 dropped from 0.76 (baseline) to 0.55 (Shard).
• Micro-Key Limit: When $C=N$ (per-document keys), the residual graph leak drops to 0.00, and the system becomes unlinkable (re-keying AUC $\approx 0.5$).
• Comparison to DP Noise: A distortion-aware DP defense matched Shard's utility only at $\sigma=0$ (no noise), where de-anonymization was 100%. Any noise added to reduce de-anonymization degraded utility below Shard's performance. Shard achieved high utility with 0% de-anonymization.
• Limitations Observed:
  • Targeted Attacks: A targeted attacker concentrating anchors in a specific victim's cell needs only $\approx d_{priv}$ anchors, independent of $C$.
  • Overlap Reference: If an attacker possesses an overlapping reference corpus, the public prefix (even if keyed with a single global key) allows de-anonymization once that key is recovered.
  • Access Patterns: Like the baseline, Shard does not hide access patterns (which documents are reranked).

5. Significance and Claims

The paper positions Shard as an attack-aware geometric defense, explicitly stating it is not a cryptographic guarantee for the stored documents.

• Core Achievement: Shard shifts the privacy/accuracy trade-off by removing the "single global geometry" vulnerability. It allows for exact, full-dimensional reranking (preserving utility) while making the alignment of the private residual computationally expensive for diffuse attackers.
• Design Philosophy: The work moves embedding privacy from optimizing against a distortion surrogate ($\sigma_{rec}$) to hardening against specific attack surfaces (alignment and index leakage).
• Modest Claims: The authors are explicit about what Shard does not do:
  • It does not protect against targeted attacks concentrating on a single cell.
  • It does not prevent de-anonymization via overlapping reference corpora if the public prefix key is recovered.
  • It does not hide access patterns.
  • The secret rotation is an empirical obfuscation layer, not a cryptographic primitive.

The paper concludes that Shard offers a tunable family of transforms (via parameter $C$) that can be revoked at the cell level, providing a practical, measured defense against modern alignment attacks in dense retrieval systems, provided the system is composed with other primitives (like PIR) to handle access patterns and reference overlaps.